Panda3D
 All Classes Functions Variables Enumerations
simpleHashMap.h
1 // Filename: simpleHashMap.h
2 // Created by: drose (19Jul07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 #ifndef SIMPLEHASHMAP_H
16 #define SIMPLEHASHMAP_H
17 
18 #include "pandabase.h"
19 #include "pvector.h"
20 #include "config_util.h"
21 
22 ////////////////////////////////////////////////////////////////////
23 // Class : SimpleHashMap
24 // Description : This template class implements an unordered map of
25 // keys to data, implemented as a hashtable. It is
26 // similar to STL's hash_map, but (a) it has a simpler
27 // interface (we don't mess around with iterators), (b)
28 // it wants an additional method on the Compare object,
29 // Compare::is_equal(a, b), and (c) it doesn't depend on
30 // the system STL providing hash_map.
31 ////////////////////////////////////////////////////////////////////
32 template<class Key, class Value, class Compare = method_hash<Key, less<Key> > >
34 public:
35 #ifndef CPPPARSER
36  INLINE SimpleHashMap(const Compare &comp = Compare());
37  INLINE ~SimpleHashMap();
38 
39  INLINE void swap(SimpleHashMap &other);
40 
41  int find(const Key &key) const;
42  int store(const Key &key, const Value &data);
43  INLINE bool remove(const Key &key);
44  void clear();
45 
46  INLINE Value &operator [] (const Key &key);
47 
48  INLINE int get_size() const;
49  INLINE bool has_element(int n) const;
50  INLINE const Key &get_key(int n) const;
51  INLINE const Value &get_data(int n) const;
52  INLINE Value &modify_data(int n);
53  INLINE void set_data(int n, const Value &data);
54  void remove_element(int n);
55 
56  INLINE int get_num_entries() const;
57  INLINE bool is_empty() const;
58 
59  void output(ostream &out) const;
60  void write(ostream &out) const;
61  bool validate() const;
62 
63 private:
64  class TableEntry;
65 
66  INLINE size_t get_hash(const Key &key) const;
67 
68  INLINE bool is_element(int n, const Key &key) const;
69  INLINE void store_new_element(int n, const Key &key, const Value &data);
70  INLINE void clear_element(int n);
71  INLINE unsigned char *get_exists_array() const;
72 
73  void new_table();
74  INLINE bool consider_expand_table();
75  void expand_table();
76 
77  class TableEntry {
78  public:
79  INLINE TableEntry(const Key &key, const Value &data) :
80  _key(key),
81  _data(data) {}
82  INLINE TableEntry(const TableEntry &copy) :
83  _key(copy._key),
84  _data(copy._data) {}
85 #ifdef USE_MOVE_SEMANTICS
86  INLINE TableEntry(TableEntry &&from) NOEXCEPT :
87  _key(move(from._key)),
88  _data(move(from._data)) {}
89 #endif
90  Key _key;
91  Value _data;
92  };
93 
94  TableEntry *_table;
95  DeletedBufferChain *_deleted_chain;
96  size_t _table_size;
97  size_t _num_entries;
98 
99  Compare _comp;
100 #endif // CPPPARSER
101 };
102 
103 template<class Key, class Value, class Compare>
104 inline ostream &operator << (ostream &out, const SimpleHashMap<Key, Value, Compare> &shm) {
105  shm.output(out);
106  return out;
107 }
108 
109 #ifndef CPPPARSER
110 #include "simpleHashMap.I"
111 #endif // CPPPARSER
112 
113 #endif
int find(const Key &key) const
Searches for the indicated key in the table.
Definition: simpleHashMap.I:78
int 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...
int store(const Key &key, const Value &data)
Records the indicated key/data pair in the map.
This template class implements an unordered map of keys to data, implemented as a hashtable...
Definition: simpleHashMap.h:33
void clear()
Completely empties the table.
Value & modify_data(int n)
Returns a modifiable reference to the data in the nth slot of the table.
bool is_empty() const
Returns true if the table is empty; i.e.
int get_size() const
Returns the total number of slots in the table.
void set_data(int n, const Value &data)
Changes the data for the nth slot of the table.
bool validate() const
Returns true if the internal table appears to be consistent, false if there are some internal errors...
const Value & get_data(int n) const
Returns the data in the nth slot of the table.
This template class can be used to provide faster allocation/deallocation for many Panda objects...
void remove_element(int n)
Removes the nth slot from the table.
const Key & get_key(int n) const
Returns the key in the nth slot of the table.
void swap(SimpleHashMap &other)
Quickly exchanges the contents of this map and the other map.
Definition: simpleHashMap.I:51
bool has_element(int n) const
Returns true if there is an element stored in the nth slot, false otherwise.