Panda3D
Loading...
Searching...
No Matches
simpleHashMap.h
Go to the documentation of this file.
1/**
2 * PANDA 3D SOFTWARE
3 * Copyright (c) Carnegie Mellon University. All rights reserved.
4 *
5 * All use of this software is subject to the terms of the revised BSD
6 * license. You should have received a copy of this license along
7 * with this source code in a file named "LICENSE."
8 *
9 * @file simpleHashMap.h
10 * @author drose
11 * @date 2007-07-19
12 */
13
14#ifndef SIMPLEHASHMAP_H
15#define SIMPLEHASHMAP_H
16
17#include "pandabase.h"
18#include "pvector.h"
19#include "config_putil.h"
20
21/**
22 * Entry in the SimpleHashMap.
23 */
24template<class Key, class Value>
26public:
27 INLINE SimpleKeyValuePair(const Key &key, const Value &data) :
28 _key(key),
29 _data(data) {}
30
31 Key _key;
32
33 ALWAYS_INLINE const Value &get_data() const {
34 return _data;
35 }
36 ALWAYS_INLINE Value &modify_data() {
37 return _data;
38 }
39 ALWAYS_INLINE void set_data(const Value &data) {
40 _data = data;
41 }
42 ALWAYS_INLINE void set_data(Value &&data) {
43 _data = std::move(data);
44 }
45
46private:
47 Value _data;
48};
49
50/**
51 * Specialisation of SimpleKeyValuePair to not waste memory for nullptr_t
52 * values. This allows effectively using SimpleHashMap as a set.
53 */
54template<class Key>
55class SimpleKeyValuePair<Key, std::nullptr_t> {
56public:
57 INLINE SimpleKeyValuePair(const Key &key, std::nullptr_t data) :
58 _key(key) {}
59
60 Key _key;
61
62 ALWAYS_INLINE constexpr static std::nullptr_t get_data() { return nullptr; }
63 ALWAYS_INLINE constexpr static std::nullptr_t modify_data() { return nullptr; }
64 ALWAYS_INLINE static void set_data(std::nullptr_t) {}
65};
66
67/**
68 * This template class implements an unordered map of keys to data,
69 * implemented as a hashtable. It is similar to STL's hash_map, but
70 * (a) it has a simpler interface (we don't mess around with iterators),
71 * (b) it wants an additional method on the Compare object,
72 Compare::is_equal(a, b),
73 * (c) it doesn't depend on the system STL providing hash_map,
74 * (d) it allows for efficient iteration over the entries,
75 * (e) permits removal and resizing during forward iteration, and
76 * (f) it has a constexpr constructor.
77 *
78 * It can also be used as a set, by using nullptr_t as Value typename.
79 */
80template<class Key, class Value, class Compare = method_hash<Key, std::less<Key> > >
82 // Per-entry overhead is determined by sizeof(int) * sparsity. Should be a
83 // power of two.
84 static const unsigned int sparsity = 2u;
85
86public:
87#ifndef CPPPARSER
88 constexpr SimpleHashMap(const Compare &comp = Compare());
89 INLINE SimpleHashMap(const SimpleHashMap &copy);
90 INLINE SimpleHashMap(SimpleHashMap &&from) noexcept;
91 INLINE ~SimpleHashMap();
92
93 INLINE SimpleHashMap &operator = (const SimpleHashMap &copy);
94 INLINE SimpleHashMap &operator = (SimpleHashMap &&from) noexcept;
95
96 INLINE void swap(SimpleHashMap &other);
97
98 int find(const Key &key) const;
99 int store(const Key &key, const Value &data);
100 INLINE bool remove(const Key &key);
101 void clear();
102
103 INLINE Value &operator [] (const Key &key);
104 constexpr size_t size() const;
105
106 INLINE const Key &get_key(size_t n) const;
107 INLINE const Value &get_data(size_t n) const;
108 INLINE Value &modify_data(size_t n);
109 INLINE void set_data(size_t n, const Value &data);
110 INLINE void set_data(size_t n, Value &&data);
111 void remove_element(size_t n);
112
113 INLINE size_t get_num_entries() const;
114 INLINE bool is_empty() const;
115
116 void output(std::ostream &out) const;
117 void write(std::ostream &out) const;
118 bool validate() const;
119
120 INLINE bool consider_shrink_table();
121
122private:
123 INLINE size_t get_hash(const Key &key) const;
124 INLINE size_t next_hash(size_t hash) const;
125
126 INLINE int find_slot(const Key &key) const;
127 INLINE bool has_slot(size_t slot) const;
128 INLINE bool is_element(size_t n, const Key &key) const;
129 INLINE size_t store_new_element(size_t n, const Key &key, const Value &data);
130 INLINE int *get_index_array() const;
131
132 void new_table();
133 INLINE bool consider_expand_table();
134 void resize_table(size_t new_size);
135
136public:
138 TableEntry *_table;
139 DeletedBufferChain *_deleted_chain;
140 size_t _table_size;
141 size_t _num_entries;
142
143 Compare _comp;
144#endif // CPPPARSER
145};
146
147template<class Key, class Value, class Compare>
148inline std::ostream &operator << (std::ostream &out, const SimpleHashMap<Key, Value, Compare> &shm) {
149 shm.output(out);
150 return out;
151}
152
153#ifndef CPPPARSER
154#include "simpleHashMap.I"
155#endif // CPPPARSER
156
157#endif
This template class can be used to provide faster allocation/deallocation for many Panda objects.
This template class implements an unordered map of keys to data, implemented as a hashtable.
Value & modify_data(size_t n)
Returns a modifiable reference to the data in the nth entry of the table.
const Key & get_key(size_t n) const
Returns the key in the nth entry of the table.
int store(const Key &key, const Value &data)
Records the indicated key/data pair in the map.
bool validate() const
Returns true if the internal table appears to be consistent, false if there are some internal errors.
constexpr size_t size() const
Returns the total number of entries in the table.
void clear()
Completely empties the table.
const Value & get_data(size_t n) const
Returns the data in the nth entry of the table.
int find(const Key &key) const
Searches for the indicated key in the table.
bool remove(const Key &key)
Removes the indicated key and its associated data from the table.
bool consider_shrink_table()
Shrinks the table if the allocated storage is significantly larger than the number of elements in it.
void swap(SimpleHashMap &other)
Quickly exchanges the contents of this map and the other map.
void remove_element(size_t n)
Removes the nth entry from the table.
bool is_empty() const
Returns true if the table is empty; i.e.
void set_data(size_t n, const Value &data)
Changes the data for the nth entry of the table.
size_t get_num_entries() const
Returns the number of active entries in the table.
Value & operator[](const Key &key)
Returns a modifiable reference to the data associated with the indicated key, or creates a new data e...
Entry in the SimpleHashMap.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
STL namespace.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.