Panda3D
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  */
24 template<class Key, class Value>
26 public:
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 
46 private:
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  */
54 template<class Key>
55 class SimpleKeyValuePair<Key, std::nullptr_t> {
56 public:
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  */
80 template<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 
86 public:
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 
122 private:
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 
136 public:
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 
147 template<class Key, class Value, class Compare>
148 inline 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
SimpleKeyValuePair
Entry in the SimpleHashMap.
Definition: simpleHashMap.h:25
config_putil.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
SimpleHashMap::get_data
const Value & get_data(size_t n) const
Returns the data in the nth entry of the table.
Definition: simpleHashMap.I:387
pandabase.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
pvector.h
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
SimpleHashMap::remove
bool remove(const Key &key)
Removes the indicated key and its associated data from the table.
Definition: simpleHashMap.I:254
SimpleHashMap::get_key
const Key & get_key(size_t n) const
Returns the key in the nth entry of the table.
Definition: simpleHashMap.I:375
SimpleHashMap::validate
bool validate() const
Returns true if the internal table appears to be consistent, false if there are some internal errors.
Definition: simpleHashMap.I:504
SimpleHashMap
This template class implements an unordered map of keys to data, implemented as a hashtable.
Definition: simpleHashMap.h:81
SimpleHashMap::swap
void swap(SimpleHashMap &other)
Quickly exchanges the contents of this map and the other map.
Definition: simpleHashMap.I:132
SimpleHashMap::find
int find(const Key &key) const
Searches for the indicated key in the table.
Definition: simpleHashMap.I:156
SimpleHashMap::store
int store(const Key &key, const Value &data)
Records the indicated key/data pair in the map.
Definition: simpleHashMap.I:177
SimpleHashMap::modify_data
Value & modify_data(size_t n)
Returns a modifiable reference to the data in the nth entry of the table.
Definition: simpleHashMap.I:399
simpleHashMap.I
PANDA 3D SOFTWARE Copyright (c) Carnegie Mellon University.
SimpleHashMap::is_empty
bool is_empty() const
Returns true if the table is empty; i.e.
Definition: simpleHashMap.I:454
SimpleHashMap::operator[]
Value & operator[](const Key &key)
Returns a modifiable reference to the data associated with the indicated key, or creates a new data e...
Definition: simpleHashMap.I:351
SimpleHashMap::clear
void clear()
Completely empties the table.
Definition: simpleHashMap.I:331
SimpleHashMap::size
constexpr size_t size() const
Returns the total number of entries in the table.
Definition: simpleHashMap.I:364
DeletedBufferChain
This template class can be used to provide faster allocation/deallocation for many Panda objects.
Definition: deletedBufferChain.h:58
SimpleHashMap::get_num_entries
size_t get_num_entries() const
Returns the number of active entries in the table.
Definition: simpleHashMap.I:445
SimpleHashMap::consider_shrink_table
bool consider_shrink_table()
Shrinks the table if the allocated storage is significantly larger than the number of elements in it.
Definition: simpleHashMap.I:693
SimpleHashMap::set_data
void set_data(size_t n, const Value &data)
Changes the data for the nth entry of the table.
Definition: simpleHashMap.I:411
SimpleHashMap::remove_element
void remove_element(size_t n)
Removes the nth entry from the table.
Definition: simpleHashMap.I:435