Panda3D
simpleHashMap.I
1 // Filename: simpleHashMap.I
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 
16 ////////////////////////////////////////////////////////////////////
17 // Function: SimpleHashMap::Constructor
18 // Access: Public
19 // Description:
20 ////////////////////////////////////////////////////////////////////
21 template<class Key, class Value, class Compare>
23 SimpleHashMap(const Compare &comp) :
24  _table(NULL),
25  _deleted_chain(NULL),
26  _table_size(0),
27  _num_entries(0),
28  _comp(comp)
29 {
30 }
31 
32 ////////////////////////////////////////////////////////////////////
33 // Function: SimpleHashMap::Destructor
34 // Access: Public
35 // Description:
36 ////////////////////////////////////////////////////////////////////
37 template<class Key, class Value, class Compare>
40  clear();
41 }
42 
43 ////////////////////////////////////////////////////////////////////
44 // Function: SimpleHashMap::swap
45 // Access: Public
46 // Description: Quickly exchanges the contents of this map and the
47 // other map.
48 ////////////////////////////////////////////////////////////////////
49 template<class Key, class Value, class Compare>
52  TableEntry *t0 = _table;
53  _table = other._table;
54  other._table = t0;
55 
56  DeletedBufferChain *t1 = _deleted_chain;
57  _deleted_chain = other._deleted_chain;
58  other._deleted_chain = t1;
59 
60  size_t t2 = _table_size;
61  _table_size = other._table_size;
62  other._table_size = t2;
63 
64  size_t t3 = _num_entries;
65  _num_entries = other._num_entries;
66  other._num_entries = t3;
67 }
68 
69 ////////////////////////////////////////////////////////////////////
70 // Function: SimpleHashMap::find
71 // Access: Public
72 // Description: Searches for the indicated key in the table. Returns
73 // its index number if it is found, or -1 if it is not
74 // present in the table.
75 ////////////////////////////////////////////////////////////////////
76 template<class Key, class Value, class Compare>
78 find(const Key &key) const {
79  if (_table_size == 0) {
80  // Special case: the table is empty.
81  return -1;
82  }
83 
84  size_t index = get_hash(key);
85  if (!has_element(index)) {
86  return -1;
87  }
88  if (is_element(index, key)) {
89  return index;
90  }
91 
92  // There was some other key at the hashed slot. That's a hash
93  // conflict. Maybe our entry was recorded at a later slot position;
94  // scan the subsequent positions until we find the entry or an
95  // unused slot, indicating the end of the scan.
96  size_t i = index;
97  i = (i + 1) & (_table_size - 1);
98  while (i != index && has_element(i)) {
99  if (is_element(i, key)) {
100  return i;
101  }
102  i = (i + 1) & (_table_size - 1);
103  }
104 
105  // The key is not in the table.
106  return -1;
107 }
108 
109 ////////////////////////////////////////////////////////////////////
110 // Function: SimpleHashMap::store
111 // Access: Public
112 // Description: Records the indicated key/data pair in the map. If
113 // the key was already present, silently replaces it.
114 // Returns the index at which it was stored.
115 ////////////////////////////////////////////////////////////////////
116 template<class Key, class Value, class Compare>
118 store(const Key &key, const Value &data) {
119  if (_table_size == 0) {
120  // Special case: the first key in an empty table.
121  nassertr(_num_entries == 0, -1);
122  new_table();
123  size_t index = get_hash(key);
124  store_new_element(index, key, data);
125  ++_num_entries;
126 #ifdef _DEBUG
127  nassertr(validate(), index);
128 #endif
129  return index;
130  }
131 
132  size_t index = get_hash(key);
133  if (!has_element(index)) {
134  // This element is not already in the map; add it.
135  if (consider_expand_table()) {
136  return store(key, data);
137  }
138  store_new_element(index, key, data);
139  ++_num_entries;
140 #ifdef _DEBUG
141  nassertr(validate(), index);
142 #endif
143  return index;
144  }
145  if (is_element(index, key)) {
146  // This element is already in the map; replace the data at that
147  // key.
148  _table[index]._data = data;
149 #ifdef _DEBUG
150  nassertr(validate(), index);
151 #endif
152  return index;
153  }
154 
155  // There was some other key at the hashed slot. That's a hash
156  // conflict. Record this entry at a later position.
157  size_t i = index;
158  i = (i + 1) & (_table_size - 1);
159  while (i != index) {
160  if (!has_element(i)) {
161  if (consider_expand_table()) {
162  return store(key, data);
163  }
164  store_new_element(i, key, data);
165  ++_num_entries;
166 #ifdef _DEBUG
167  nassertr(validate(), i);
168 #endif
169  return i;
170  }
171  if (is_element(i, key)) {
172  _table[i]._data = data;
173 #ifdef _DEBUG
174  nassertr(validate(), i);
175 #endif
176  return i;
177  }
178  i = (i + 1) & (_table_size - 1);
179  }
180 
181  // Shouldn't get here unless _num_entries == _table_size, which
182  // shouldn't be possible due to consider_expand_table().
183  nassertr(false, -1);
184  return -1; // To satisfy compiler
185 }
186 
187 ////////////////////////////////////////////////////////////////////
188 // Function: SimpleHashMap::remove
189 // Access: Public
190 // Description: Removes the indicated key and its associated data
191 // from the table. Returns true if the key was removed,
192 // false if it was not present.
193 ////////////////////////////////////////////////////////////////////
194 template<class Key, class Value, class Compare>
196 remove(const Key &key) {
197  int index = find(key);
198  if (index == -1) {
199  return false;
200  }
201  remove_element(index);
202  return true;
203 }
204 
205 ////////////////////////////////////////////////////////////////////
206 // Function: SimpleHashMap::clear
207 // Access: Public
208 // Description: Completely empties the table.
209 ////////////////////////////////////////////////////////////////////
210 template<class Key, class Value, class Compare>
212 clear() {
213  if (_table_size != 0) {
214  for (size_t i = 0; i < _table_size; ++i) {
215  if (has_element(i)) {
216  clear_element(i);
217  }
218  }
219 
220  _deleted_chain->deallocate(_table, TypeHandle::none());
221  _table = NULL;
222  _deleted_chain = NULL;
223  _table_size = 0;
224  _num_entries = 0;
225  }
226 }
227 
228 ////////////////////////////////////////////////////////////////////
229 // Function: SimpleHashMap::operator []
230 // Access: Public
231 // Description: Returns a modifiable reference to the data associated
232 // with the indicated key, or creates a new data entry
233 // and returns its reference.
234 ////////////////////////////////////////////////////////////////////
235 template<class Key, class Value, class Compare>
237 operator [] (const Key &key) {
238  int index = find(key);
239  if (index == -1) {
240  index = store(key, Value());
241  }
242  return modify_data(index);
243 }
244 
245 ////////////////////////////////////////////////////////////////////
246 // Function: SimpleHashMap::get_size
247 // Access: Public
248 // Description: Returns the total number of slots in the table.
249 ////////////////////////////////////////////////////////////////////
250 template<class Key, class Value, class Compare>
252 get_size() const {
253  return _table_size;
254 }
255 
256 ////////////////////////////////////////////////////////////////////
257 // Function: SimpleHashMap::has_element
258 // Access: Public
259 // Description: Returns true if there is an element stored in the nth
260 // slot, false otherwise.
261 //
262 // n should be in the range 0 <= n < get_size().
263 ////////////////////////////////////////////////////////////////////
264 template<class Key, class Value, class Compare>
266 has_element(int n) const {
267  nassertr(n >= 0 && n < (int)_table_size, false);
268  return (get_exists_array()[n] != 0);
269 }
270 
271 ////////////////////////////////////////////////////////////////////
272 // Function: SimpleHashMap::get_key
273 // Access: Public
274 // Description: Returns the key in the nth slot of the table.
275 //
276 // It is an error to call this if there is nothing
277 // stored in the nth slot (use has_element() to check
278 // this first). n should be in the range 0 <= n <
279 // get_size().
280 ////////////////////////////////////////////////////////////////////
281 template<class Key, class Value, class Compare>
282 INLINE const Key &SimpleHashMap<Key, Value, Compare>::
283 get_key(int n) const {
284  nassertr(has_element(n), _table[n]._key);
285  return _table[n]._key;
286 }
287 
288 ////////////////////////////////////////////////////////////////////
289 // Function: SimpleHashMap::get_data
290 // Access: Public
291 // Description: Returns the data in the nth slot of the table.
292 //
293 // It is an error to call this if there is nothing
294 // stored in the nth slot (use has_element() to check
295 // this first). n should be in the range 0 <= n <
296 // get_size().
297 ////////////////////////////////////////////////////////////////////
298 template<class Key, class Value, class Compare>
299 INLINE const Value &SimpleHashMap<Key, Value, Compare>::
300 get_data(int n) const {
301  nassertr(has_element(n), _table[n]._data);
302  return _table[n]._data;
303 }
304 
305 ////////////////////////////////////////////////////////////////////
306 // Function: SimpleHashMap::modify_data
307 // Access: Public
308 // Description: Returns a modifiable reference to the data in the nth
309 // slot of the table.
310 //
311 // It is an error to call this if there is nothing
312 // stored in the nth slot (use has_element() to check
313 // this first). n should be in the range 0 <= n <
314 // get_size().
315 ////////////////////////////////////////////////////////////////////
316 template<class Key, class Value, class Compare>
318 modify_data(int n) {
319  nassertr(has_element(n), _table[n]._data);
320  return _table[n]._data;
321 }
322 
323 ////////////////////////////////////////////////////////////////////
324 // Function: SimpleHashMap::set_data
325 // Access: Public
326 // Description: Changes the data for the nth slot of the table.
327 //
328 // It is an error to call this if there is nothing
329 // stored in the nth slot (use has_element() to check
330 // this first). n should be in the range 0 <= n <
331 // get_size().
332 ////////////////////////////////////////////////////////////////////
333 template<class Key, class Value, class Compare>
335 set_data(int n, const Value &data) {
336  nassertv(has_element(n));
337  _table[n]._data = data;
338 }
339 
340 ////////////////////////////////////////////////////////////////////
341 // Function: SimpleHashMap::remove_element
342 // Access: Public
343 // Description: Removes the nth slot from the table.
344 //
345 // It is an error to call this if there is nothing
346 // stored in the nth slot (use has_element() to check
347 // this first). n should be in the range 0 <= n <
348 // get_size().
349 ////////////////////////////////////////////////////////////////////
350 template<class Key, class Value, class Compare>
353  nassertv(has_element(n));
354 
355  clear_element(n);
356  nassertv(_num_entries > 0);
357  --_num_entries;
358 
359  // Now we have put a hole in the table. If there was a hash
360  // conflict in the slot following this one, we have to move it down
361  // to close the hole.
362  size_t i = n;
363  i = (i + 1) & (_table_size - 1);
364  while (has_element(i)) {
365  size_t wants_index = get_hash(_table[i]._key);
366  if (wants_index != i) {
367  // This one was a hash conflict; try to put it where it belongs.
368  // We can't just put it in n, since maybe it belongs somewhere
369  // after n.
370  while (wants_index != i && has_element(wants_index)) {
371  wants_index = (wants_index + 1) & (_table_size - 1);
372  }
373  if (wants_index != i) {
374  store_new_element(wants_index, _table[i]._key, _table[i]._data);
375  clear_element(i);
376  }
377  }
378 
379  // Continue until we encounter the next unused slot. Until we do,
380  // we can't be sure we've found all of the potential hash
381  // conflicts.
382  i = (i + 1) & (_table_size - 1);
383  }
384 
385 #ifdef _DEBUG
386  nassertv(validate());
387 #endif
388 }
389 
390 ////////////////////////////////////////////////////////////////////
391 // Function: SimpleHashMap::get_num_entries
392 // Access: Public
393 // Description: Returns the number of active entries in the table.
394 // This is not necessarily related to the number of
395 // slots in the table as reported by get_size(). Use
396 // get_size() to iterate through all of the slots, not
397 // get_num_entries().
398 ////////////////////////////////////////////////////////////////////
399 template<class Key, class Value, class Compare>
402  return _num_entries;
403 }
404 
405 ////////////////////////////////////////////////////////////////////
406 // Function: SimpleHashMap::is_empty
407 // Access: Public
408 // Description: Returns true if the table is empty;
409 // i.e. get_num_entries() == 0.
410 ////////////////////////////////////////////////////////////////////
411 template<class Key, class Value, class Compare>
413 is_empty() const {
414  return (_num_entries == 0);
415 }
416 
417 ////////////////////////////////////////////////////////////////////
418 // Function: SimpleHashMap::output
419 // Access: Public
420 // Description:
421 ////////////////////////////////////////////////////////////////////
422 template<class Key, class Value, class Compare>
424 output(ostream &out) const {
425  out << "SimpleHashMap (" << _num_entries << " entries): [";
426  for (size_t i = 0; i < _table_size; ++i) {
427  if (!has_element(i)) {
428  out << " *";
429 
430  } else {
431  out << " " << _table[i]._key;
432  size_t index = get_hash(_table[i]._key);
433  if (index != i) {
434  // This was misplaced as the result of a hash conflict.
435  // Report how far off it is.
436  out << "(" << ((_table_size + i - index) & (_table_size - 1)) << ")";
437  }
438  }
439  }
440  out << " ]";
441 }
442 
443 ////////////////////////////////////////////////////////////////////
444 // Function: SimpleHashMap::write
445 // Access: Public
446 // Description:
447 ////////////////////////////////////////////////////////////////////
448 template<class Key, class Value, class Compare>
450 write(ostream &out) const {
451  output(out);
452  out << "\n";
453 }
454 
455 ////////////////////////////////////////////////////////////////////
456 // Function: SimpleHashMap::validate
457 // Access: Public
458 // Description: Returns true if the internal table appears to be
459 // consistent, false if there are some internal errors.
460 ////////////////////////////////////////////////////////////////////
461 template<class Key, class Value, class Compare>
463 validate() const {
464  size_t count = 0;
465 
466  for (size_t i = 0; i < _table_size; ++i) {
467  if (has_element(i)) {
468  ++count;
469  size_t ideal_index = get_hash(_table[i]._key);
470  size_t wants_index = ideal_index;
471  while (wants_index != i && has_element(wants_index)) {
472  wants_index = (wants_index + 1) & (_table_size - 1);
473  }
474  if (wants_index != i) {
475  util_cat.error()
476  << "SimpleHashMap is invalid: key " << _table[i]._key
477  << " should be in slot " << wants_index << " instead of "
478  << i << " (ideal is " << ideal_index << ")\n";
479  write(util_cat.error(false));
480  return false;
481  }
482  }
483  }
484 
485  if (count != _num_entries) {
486  util_cat.error()
487  << "SimpleHashMap is invalid: reports " << _num_entries
488  << " entries, actually has " << count << "\n";
489  write(util_cat.error(false));
490  return false;
491  }
492 
493  return true;
494 }
495 
496 ////////////////////////////////////////////////////////////////////
497 // Function: SimpleHashMap::get_hash
498 // Access: Private
499 // Description: Computes an appropriate index number to store the
500 // given pointer.
501 ////////////////////////////////////////////////////////////////////
502 template<class Key, class Value, class Compare>
504 get_hash(const Key &key) const {
505  /*
506  // We want a hash constant 0 < k < 1. This one is suggested by
507  // Knuth:
508  static const double hash_constant = (sqrt(5.0) - 1.0) / 2.0;
509  double f = ((double)_comp(key) * hash_constant);
510  f -= floor(f);
511  return (size_t)floor(f * _table_size);
512  */
513 
514  return ((_comp(key) * (size_t)9973) >> 8) & (_table_size - 1);
515 }
516 
517 ////////////////////////////////////////////////////////////////////
518 // Function: SimpleHashMap::is_element
519 // Access: Private
520 // Description: Returns true if element n matches key.
521 ////////////////////////////////////////////////////////////////////
522 template<class Key, class Value, class Compare>
524 is_element(int n, const Key &key) const {
525  nassertr(has_element(n), false);
526  return _comp.is_equal(_table[n]._key, key);
527 }
528 
529 ////////////////////////////////////////////////////////////////////
530 // Function: SimpleHashMap::store_new_element
531 // Access: Private
532 // Description: Constructs a new TableEntry at position n, storing
533 // the indicated key and value.
534 ////////////////////////////////////////////////////////////////////
535 template<class Key, class Value, class Compare>
537 store_new_element(int n, const Key &key, const Value &data) {
538  new(&_table[n]) TableEntry(key, data);
539  get_exists_array()[n] = true;
540 }
541 
542 ////////////////////////////////////////////////////////////////////
543 // Function: SimpleHashMap::clear_element
544 // Access: Private
545 // Description: Destructs the TableEntry at position n.
546 ////////////////////////////////////////////////////////////////////
547 template<class Key, class Value, class Compare>
549 clear_element(int n) {
550  _table[n].~TableEntry();
551  get_exists_array()[n] = false;
552 }
553 
554 ////////////////////////////////////////////////////////////////////
555 // Function: SimpleHashMap::get_exists_array
556 // Access: Private
557 // Description: Returns the beginning of the array of _table_size
558 // unsigned chars that are the boolean flags for whether
559 // each element exists (has been constructed) within the
560 // table.
561 ////////////////////////////////////////////////////////////////////
562 template<class Key, class Value, class Compare>
563 INLINE unsigned char *SimpleHashMap<Key, Value, Compare>::
564 get_exists_array() const {
565  return (unsigned char *)(_table + _table_size);
566 }
567 
568 ////////////////////////////////////////////////////////////////////
569 // Function: SimpleHashMap::new_table
570 // Access: Private
571 // Description: Allocates a brand new table.
572 ////////////////////////////////////////////////////////////////////
573 template<class Key, class Value, class Compare>
575 new_table() {
576  nassertv(_table_size == 0 && _num_entries == 0);
577 
578  // Pick a good initial table size. For now, we make it really
579  // small. Maybe that's the right answer.
580  _table_size = 4;
581 
582  // We allocate enough bytes for _table_size elements of TableEntry,
583  // plus _table_size more bytes at the end (for the exists array).
584  size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size;
585 
586  _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
587  _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
588  memset(get_exists_array(), 0, _table_size);
589 }
590 
591 ////////////////////////////////////////////////////////////////////
592 // Function: SimpleHashMap::consider_expand_table
593 // Access: Private
594 // Description: Expands the table if it will need it (assuming one
595 // more element is about to be added). Returns true if
596 // expanded, false otherwise.
597 ////////////////////////////////////////////////////////////////////
598 template<class Key, class Value, class Compare>
601  if (_num_entries >= (_table_size >> 1)) {
602  expand_table();
603  return true;
604  }
605  return false;
606 }
607 
608 ////////////////////////////////////////////////////////////////////
609 // Function: SimpleHashMap::expand_table
610 // Access: Private
611 // Description: Doubles the size of the existing table.
612 ////////////////////////////////////////////////////////////////////
613 template<class Key, class Value, class Compare>
615 expand_table() {
616  nassertv(_table_size != 0);
617 
618  SimpleHashMap<Key, Value, Compare> old_map(_comp);
619  swap(old_map);
620 
621  // Double the table size.
622  size_t old_table_size = old_map._table_size;
623  _table_size = (old_table_size << 1);
624  nassertv(_table == NULL);
625 
626  // We allocate enough bytes for _table_size elements of TableEntry,
627  // plus _table_size more bytes at the end (for the exists array).
628  size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size;
629  _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
630  _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
631  unsigned char *exists_array = get_exists_array();
632  memset(exists_array, 0, _table_size);
633  nassertv(_num_entries == 0);
634 
635  // Now copy the entries from the old table into the new table.
636  int num_added = 0;
637  for (size_t i = 0; i < old_table_size; ++i) {
638  if (old_map.has_element(i)) {
639  size_t new_index = get_hash(old_map._table[i]._key);
640 
641  while (exists_array[new_index] != 0) {
642  // Hash conflict; look for a better spot. This has to succeed.
643  new_index = (new_index + 1) & (_table_size - 1);
644  }
645 
646 #ifdef USE_MOVE_SEMANTICS
647  // Use C++11 rvalue references to invoke the move constructor,
648  // which may be more efficient.
649  new(&_table[new_index]) TableEntry(move(old_map._table[i]));
650 #else
651  new(&_table[new_index]) TableEntry(old_map._table[i]);
652 #endif
653  exists_array[new_index] = true;
654  ++_num_entries;
655  }
656  }
657 
658  nassertv(validate());
659  nassertv(old_map.validate());
660 
661  nassertv(_num_entries == old_map._num_entries);
662 }
DeletedBufferChain * get_deleted_chain(size_t buffer_size)
Returns a pointer to a global DeletedBufferChain object suitable for allocating arrays of the indicat...
static TypeHandle none()
Returns a special zero-valued TypeHandle that is used to indicate no type.
Definition: typeHandle.I:274
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
const Key & get_key(int n) const
Returns the key in the nth slot of the table.
void clear()
Completely empties the table.
int get_num_entries() const
Returns the number of active entries in the table.
Value & modify_data(int n)
Returns a modifiable reference to the data in the nth slot of the table.
bool has_element(int n) const
Returns true if there is an element stored in the nth slot, false otherwise.
void deallocate(void *ptr, TypeHandle type_handle)
Frees the memory for a buffer previously allocated via allocate().
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.
void set_data(int n, const Value &data)
Changes the data for the nth slot of the table.
bool is_empty() const
Returns true if the table is empty; i.e.
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.
bool remove(const Key &key)
Removes the indicated key and its associated data from the table.
int get_size() const
Returns the total number of slots in the table.
void swap(SimpleHashMap &other)
Quickly exchanges the contents of this map and the other map.
Definition: simpleHashMap.I:51
int find(const Key &key) const
Searches for the indicated key in the table.
Definition: simpleHashMap.I:78