Panda3D
simpleHashMap.I
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.I
10  * @author drose
11  * @date 2007-07-19
12  */
13 
14 /**
15  *
16  */
17 template<class Key, class Value, class Compare>
19 SimpleHashMap(const Compare &comp) :
20  _table(nullptr),
21  _deleted_chain(nullptr),
22  _table_size(0),
23  _num_entries(0),
24  _comp(comp)
25 {
26 }
27 
28 /**
29  *
30  */
31 template<class Key, class Value, class Compare>
33 SimpleHashMap(const SimpleHashMap &copy) :
34  _table(nullptr),
35  _deleted_chain(nullptr),
36  _table_size(copy._table_size),
37  _num_entries(copy._num_entries),
38  _comp(copy._comp) {
39 
40  // We allocate enough bytes for _table_size elements of TableEntry, plus
41  // _table_size * 4 more ints at the end (for the index array).
42  if (_table_size > 0) {
43  size_t alloc_size = _table_size * (sizeof(TableEntry) + sizeof(int) * sparsity);
44 
45  _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
46  _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
47 
48  for (size_t i = 0; i < _num_entries; ++i) {
49  new(&_table[i]) TableEntry(copy._table[i]);
50  }
51 
52  // Copy the index array.
53  memcpy(get_index_array(), copy.get_index_array(), _table_size * sizeof(int) * sparsity);
54  }
55 }
56 
57 /**
58  *
59  */
60 template<class Key, class Value, class Compare>
62 SimpleHashMap(SimpleHashMap &&from) noexcept :
63  _table(from._table),
64  _deleted_chain(from._deleted_chain),
65  _table_size(from._table_size),
66  _num_entries(from._num_entries),
67  _comp(std::move(from._comp))
68 {
69  from._table = nullptr;
70  from._deleted_chain = nullptr;
71  from._table_size = 0;
72  from._num_entries = 0;
73 }
74 
75 /**
76  *
77  */
78 template<class Key, class Value, class Compare>
81  clear();
82 }
83 
84 /**
85  *
86  */
87 template<class Key, class Value, class Compare>
90  if (this != &copy) {
91  TableEntry *old_table = _table;
92  DeletedBufferChain *old_deleted_chain = _deleted_chain;
93  size_t old_num_entries = _num_entries;
94 
95  _table_size = copy._table_size;
96  _num_entries = copy._num_entries;
97  _comp = copy._comp;
98 
99  if (_table_size > 0) {
100  // We allocate enough bytes for _table_size elements of TableEntry, plus
101  // _table_size * 4 more ints at the end (for the index array).
102  size_t alloc_size = _table_size * (sizeof(TableEntry) + sizeof(int) * sparsity);
103 
104  _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
105  _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
106  for (size_t i = 0; i < _num_entries; ++i) {
107  new(&_table[i]) TableEntry(copy._table[i]);
108  }
109 
110  // Copy the index array.
111  memcpy(get_index_array(), copy.get_index_array(), _table_size * sizeof(int) * sparsity);
112  } else {
113  _table = nullptr;
114  _deleted_chain = nullptr;
115  }
116 
117  if (old_table != nullptr) {
118  for (size_t i = 0; i < old_num_entries; ++i) {
119  old_table[i].~TableEntry();
120  }
121 
122  old_deleted_chain->deallocate(old_table, TypeHandle::none());
123  }
124  }
125  return *this;
126 }
127 
128 /**
129  *
130  */
131 template<class Key, class Value, class Compare>
134  if (this != &from) {
135  _table = from._table;
136  _deleted_chain = from._deleted_chain;
137  _table_size = from._table_size;
138  _num_entries = from._num_entries;
139  _comp = std::move(from._comp);
140 
141  from._table = nullptr;
142  from._deleted_chain = nullptr;
143  from._table_size = 0;
144  from._num_entries = 0;
145  }
146 }
147 
148 /**
149  * Quickly exchanges the contents of this map and the other map.
150  */
151 template<class Key, class Value, class Compare>
154  TableEntry *t0 = _table;
155  _table = other._table;
156  other._table = t0;
157 
158  DeletedBufferChain *t1 = _deleted_chain;
159  _deleted_chain = other._deleted_chain;
160  other._deleted_chain = t1;
161 
162  size_t t2 = _table_size;
163  _table_size = other._table_size;
164  other._table_size = t2;
165 
166  size_t t3 = _num_entries;
167  _num_entries = other._num_entries;
168  other._num_entries = t3;
169 }
170 
171 /**
172  * Searches for the indicated key in the table. Returns its index number if
173  * it is found, or -1 if it is not present in the table.
174  */
175 template<class Key, class Value, class Compare>
177 find(const Key &key) const {
178  if (_table_size == 0) {
179  // Special case: the table is empty.
180  return -1;
181  }
182 
183  int slot = find_slot(key);
184  if (slot >= 0) {
185  return get_index_array()[slot];
186  } else {
187  // The key is not in the table.
188  return -1;
189  }
190 }
191 
192 /**
193  * Records the indicated key/data pair in the map. If the key was already
194  * present, silently replaces it. Returns the index at which it was stored.
195  */
196 template<class Key, class Value, class Compare>
198 store(const Key &key, const Value &data) {
199  if (_table_size == 0) {
200  // Special case: the first key in an empty table.
201  nassertr(_num_entries == 0, -1);
202  new_table();
203  int pos = store_new_element(get_hash(key), key, data);
204 #ifdef _DEBUG
205  nassertr(validate(), pos);
206 #endif
207  return pos;
208  }
209  consider_expand_table();
210 
211  const int *index_array = get_index_array();
212  size_t hash = get_hash(key);
213  int index = index_array[hash];
214  if (index < 0) {
215  // This element is not already in the map; add it.
216  if (consider_expand_table()) {
217  return store(key, data);
218  }
219  index = store_new_element(hash, key, data);
220 #ifdef _DEBUG
221  nassertr(validate(), index);
222 #endif
223  return index;
224  }
225  if (is_element(index, key)) {
226  // This element is already in the map; replace the data at that key.
227  set_data(index, data);
228 #ifdef _DEBUG
229  nassertr(validate(), index);
230 #endif
231  return index;
232  }
233 
234  // There was some other key at the hashed slot. That's a hash conflict.
235  // Record this entry at a later position.
236  size_t slot = next_hash(hash);
237  while (slot != hash) {
238  index = index_array[slot];
239  if (index < 0) {
240  if (consider_expand_table()) {
241  return store(key, data);
242  }
243  index = store_new_element(slot, key, data);
244 #ifdef _DEBUG
245  nassertr(validate(), index);
246 #endif
247  return index;
248  }
249  if (is_element(index, key)) {
250  set_data(index, data);
251 #ifdef _DEBUG
252  nassertr(validate(), index);
253 #endif
254  return index;
255  }
256  slot = next_hash(slot);
257  }
258 
259  // Shouldn't get here unless _num_entries == _table_size, which shouldn't be
260  // possible due to consider_expand_table().
261  nassertr(false, -1);
262  return -1; // To satisfy compiler
263 }
264 
265 /**
266  * Removes the indicated key and its associated data from the table. Returns
267  * true if the key was removed, false if it was not present.
268  *
269  * Iterator safety: To perform removal during iteration, revisit the element
270  * at the current index if removal succeeds, keeping in mind that the number
271  * of elements has now shrunk by one.
272  */
273 template<class Key, class Value, class Compare>
275 remove(const Key &key) {
276  if (_num_entries == 0) {
277  // Special case: the table is empty.
278  return false;
279  }
280 
281  int *index_array = get_index_array();
282  size_t slot = (size_t)find_slot(key);
283  if (slot == (size_t)-1) {
284  // It wasn't in the hash map.
285  return false;
286  }
287 
288  // Now remove this element.
289  size_t last = _num_entries - 1;
290  size_t index = (size_t)index_array[slot];
291  if (index < _num_entries) {
292  // Find the last element in the index array.
293  int other_slot = find_slot(_table[last]._key);
294  nassertr(other_slot != -1, false);
295  nassertr(index_array[(size_t)other_slot] == (int)last, false);
296 
297  // Swap it with the last one, so that we don't get any gaps in the table
298  // of entries.
299  _table[index] = std::move(_table[last]);
300  index_array[(size_t)other_slot] = index;
301  }
302 
303  _table[last].~TableEntry();
304  _num_entries = last;
305 
306  // It's important that we do this after the second find_slot, above, since
307  // it might otherwise fail due to the unexpected gap, since some indices may
308  // not be at their ideal positions right now.
309  index_array[slot] = -1;
310 
311  //if (consider_shrink_table()) {
312  // // No need to worry about that gap; resize_table() will rebuild the index.
313  // return true;
314  //}
315 
316  // Now we have put a hole in the index array. If there was a hash conflict
317  // in the slot after this one, we have to move it down to close the hole.
318  slot = next_hash(slot);
319  while (has_slot(slot)) {
320  size_t index = (size_t)index_array[slot];
321  size_t wants_slot = get_hash(_table[index]._key);
322  if (wants_slot != slot) {
323  // This one was a hash conflict; try to put it where it belongs. We
324  // can't just put it in n, since maybe it belongs somewhere after n.
325  while (wants_slot != slot && has_slot(wants_slot)) {
326  wants_slot = next_hash(wants_slot);
327  }
328  if (wants_slot != slot) {
329  // We just have to flip the slots in the index array; we can keep the
330  // elements in the table where they are.
331  index_array[wants_slot] = index;
332  index_array[slot] = -1;
333  }
334  }
335 
336  // Continue until we encounter the next unused slot. Until we do, we
337  // can't be sure we've found all of the potential hash conflicts.
338  slot = next_hash(slot);
339  }
340 
341 #ifdef _DEBUG
342  nassertr(validate(), true);
343 #endif
344  return true;
345 }
346 
347 /**
348  * Completely empties the table.
349  */
350 template<class Key, class Value, class Compare>
352 clear() {
353  if (_table_size != 0) {
354  for (size_t i = 0; i < _num_entries; ++i) {
355  _table[i].~TableEntry();
356  }
357 
358  _deleted_chain->deallocate(_table, TypeHandle::none());
359  _table = nullptr;
360  _deleted_chain = nullptr;
361  _table_size = 0;
362  _num_entries = 0;
363  }
364 }
365 
366 /**
367  * Returns a modifiable reference to the data associated with the indicated
368  * key, or creates a new data entry and returns its reference.
369  */
370 template<class Key, class Value, class Compare>
372 operator [] (const Key &key) {
373  int index = find(key);
374  if (index == -1) {
375  index = store(key, Value());
376  }
377  return modify_data(index);
378 }
379 
380 /**
381  * Returns the total number of entries in the table. Same as get_num_entries.
382  */
383 template<class Key, class Value, class Compare>
385 size() const {
386  return _num_entries;
387 }
388 
389 /**
390  * Returns the key in the nth entry of the table.
391  *
392  * @param n should be in the range 0 <= n < size().
393  */
394 template<class Key, class Value, class Compare>
396 get_key(size_t n) const {
397  nassertr(n < _num_entries, _table[n]._key);
398  return _table[n]._key;
399 }
400 
401 /**
402  * Returns the data in the nth entry of the table.
403  *
404  * @param n should be in the range 0 <= n < size().
405  */
406 template<class Key, class Value, class Compare>
408 get_data(size_t n) const {
409  nassertr(n < _num_entries, _table[n].get_data());
410  return _table[n].get_data();
411 }
412 
413 /**
414  * Returns a modifiable reference to the data in the nth entry of the table.
415  *
416  * @param n should be in the range 0 <= n < size().
417  */
418 template<class Key, class Value, class Compare>
420 modify_data(size_t n) {
421  nassertr(n < _num_entries, _table[n].modify_data());
422  return _table[n].modify_data();
423 }
424 
425 /**
426  * Changes the data for the nth entry of the table.
427  *
428  * @param n should be in the range 0 <= n < size().
429  */
430 template<class Key, class Value, class Compare>
432 set_data(size_t n, const Value &data) {
433  nassertv(n < _num_entries);
434  _table[n].set_data(data);
435 }
436 
437 /**
438  * Changes the data for the nth entry of the table.
439  *
440  * @param n should be in the range 0 <= n < size().
441  */
442 template<class Key, class Value, class Compare>
444 set_data(size_t n, Value &&data) {
445  nassertv(n < _num_entries);
446  _table[n].set_data(std::move(data));
447 }
448 
449 /**
450  * Removes the nth entry from the table.
451  *
452  * @param n should be in the range 0 <= n < size().
453  */
454 template<class Key, class Value, class Compare>
456 remove_element(size_t n) {
457  nassertv(n < _num_entries);
458  remove(_table[n]._key);
459 }
460 
461 /**
462  * Returns the number of active entries in the table. Same as size().
463  */
464 template<class Key, class Value, class Compare>
466 get_num_entries() const {
467  return _num_entries;
468 }
469 
470 /**
471  * Returns true if the table is empty; i.e. get_num_entries() == 0.
472  */
473 template<class Key, class Value, class Compare>
475 is_empty() const {
476  return (_num_entries == 0);
477 }
478 
479 /**
480  *
481  */
482 template<class Key, class Value, class Compare>
484 output(std::ostream &out) const {
485  out << "SimpleHashMap (" << _num_entries << " entries): [";
486  const int *index_array = get_index_array();
487  size_t num_slots = _table_size * sparsity;
488  for (size_t slot = 0; slot < num_slots; ++slot) {
489  if (!has_slot(slot)) {
490  out << " *";
491 
492  } else {
493  size_t index = (size_t)index_array[slot];
494  out << " " << index;
495  size_t ideal_slot = get_hash(_table[index]._key);
496  if (ideal_slot != slot) {
497  // This was misplaced as the result of a hash conflict. Report how
498  // far off it is.
499  out << "(" << ((_table_size + slot - ideal_slot) & (num_slots - 1)) << ")";
500  }
501  }
502  }
503  out << " ]";
504 }
505 
506 /**
507  *
508  */
509 template<class Key, class Value, class Compare>
511 write(std::ostream &out) const {
512  output(out);
513  out << "\n";
514  for (size_t i = 0; i < _num_entries; ++i) {
515  out << " " << _table[i]._key << " (hash " << get_hash(_table[i]._key) << ")\n";
516  }
517 }
518 
519 /**
520  * Returns true if the internal table appears to be consistent, false if there
521  * are some internal errors.
522  */
523 template<class Key, class Value, class Compare>
525 validate() const {
526  size_t count = 0;
527 
528  const int *index_array = get_index_array();
529  size_t num_slots = _table_size * sparsity;
530  for (size_t slot = 0; slot < num_slots; ++slot) {
531  if (has_slot(slot)) {
532  size_t index = (size_t)index_array[slot];
533  ++count;
534  if (index >= _num_entries) {
535  util_cat.error()
536  << "SimpleHashMap " << this << " is invalid: slot " << slot
537  << " contains index " << index << " which is past the end of the"
538  " table\n";
539  write(util_cat.error(false));
540  return false;
541  }
542  nassertd(index < _num_entries) continue;
543  size_t ideal_slot = get_hash(_table[index]._key);
544  size_t wants_slot = ideal_slot;
545  while (wants_slot != slot && has_slot(wants_slot)) {
546  wants_slot = next_hash(wants_slot);
547  }
548  if (wants_slot != slot) {
549  util_cat.error()
550  << "SimpleHashMap " << this << " is invalid: key "
551  << _table[index]._key << " should be in slot " << wants_slot
552  << " instead of " << slot << " (ideal is " << ideal_slot << ")\n";
553  write(util_cat.error(false));
554  return false;
555  }
556  }
557  }
558 
559  if (count != _num_entries) {
560  util_cat.error()
561  << "SimpleHashMap " << this << " is invalid: reports " << _num_entries
562  << " entries, actually has " << count << "\n";
563  write(util_cat.error(false));
564  return false;
565  }
566 
567  return true;
568 }
569 
570 /**
571  * Computes an appropriate index number to store the given pointer.
572  */
573 template<class Key, class Value, class Compare>
575 get_hash(const Key &key) const {
576  /*
577  // We want a hash constant 0 < k < 1. This one is suggested by Knuth:
578  static const double hash_constant = (sqrt(5.0) - 1.0) / 2.0;
579  double f = ((double)_comp(key) * hash_constant);
580  f -= floor(f);
581  return (size_t)floor(f * _table_size);
582  */
583 
584  return ((_comp(key) * (size_t)9973) >> 8) & ((_table_size * sparsity) - 1);
585 }
586 
587 /**
588  * Given a hash value, increments it, looping around the hash space.
589  */
590 template<class Key, class Value, class Compare>
592 next_hash(size_t hash) const {
593  return (hash + 1) & ((_table_size * sparsity) - 1);
594 }
595 
596 /**
597  * Finds the slot in which the given key should fit.
598  */
599 template<class Key, class Value, class Compare>
601 find_slot(const Key &key) const {
602  const int *index_array = get_index_array();
603  size_t hash = get_hash(key);
604  int index = index_array[hash];
605  if (index < 0) {
606  return -1;
607  }
608 
609  if (is_element((size_t)index, key)) {
610  return hash;
611  }
612 
613  // There was some other key at the hashed slot. That's a hash conflict.
614  // Maybe our entry was recorded at a later slot position; scan the
615  // subsequent positions until we find the entry or an unused slot,
616  // indicating the end of the scan.
617  size_t slot = next_hash(hash);
618  while (slot != hash && has_slot(slot)) {
619  if (is_element((size_t)index_array[slot], key)) {
620  return (int)slot;
621  }
622  slot = next_hash(slot);
623  }
624 
625  return -1;
626 }
627 
628 /**
629  * Returns true if the given slot refers to an element.
630  */
631 template<class Key, class Value, class Compare>
633 has_slot(size_t slot) const {
634  return get_index_array()[slot] >= 0;
635 }
636 
637 /**
638  * Returns true if element n matches key.
639  */
640 template<class Key, class Value, class Compare>
642 is_element(size_t n, const Key &key) const {
643  nassertr(n < _num_entries, false);
644  return _comp.is_equal(_table[n]._key, key);
645 }
646 
647 /**
648  * Constructs a new TableEntry with the given slot, storing the indicated key
649  * and value.
650  */
651 template<class Key, class Value, class Compare>
653 store_new_element(size_t slot, const Key &key, const Value &data) {
654  size_t index = _num_entries++;
655  new(&_table[index]) TableEntry(key, data);
656  nassertr(get_index_array()[slot] == -1, index)
657  get_index_array()[slot] = index;
658  return index;
659 }
660 
661 /**
662  * Returns the beginning of the array of _table_size ints that are the indices
663  * pointing to the location within the table where the elements are stored.
664  * within the table.
665  */
666 template<class Key, class Value, class Compare>
668 get_index_array() const {
669  return (int *)(_table + _table_size);
670 }
671 
672 /**
673  * Allocates a brand new table.
674  */
675 template<class Key, class Value, class Compare>
677 new_table() {
678  nassertv(_table_size == 0 && _num_entries == 0);
679 
680  // Pick a good initial table size. For now, we make it really small. Maybe
681  // that's the right answer.
682  _table_size = 2;
683 
684  // We allocate enough bytes for _table_size elements of TableEntry, plus
685  // _table_size * 4 more ints at the end (for the index array).
686  size_t alloc_size = _table_size * (sizeof(TableEntry) + sizeof(int) * sparsity);
687 
688  _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
689  _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
690  memset(get_index_array(), -1, _table_size * sizeof(int) * sparsity);
691 }
692 
693 /**
694  * Expands the table if it will need it (assuming one more element is about to
695  * be added). Returns true if expanded, false otherwise.
696  */
697 template<class Key, class Value, class Compare>
700  if (_num_entries < _table_size) {
701  return false;
702  } else {
703  resize_table(_table_size << 1);
704  return true;
705  }
706 }
707 
708 /**
709  * Shrinks the table if the allocated storage is significantly larger than the
710  * number of elements in it. Returns true if shrunk, false otherwise.
711  */
712 template<class Key, class Value, class Compare>
715  // If the number of elements gets less than an eighth of the table size, we
716  // know it's probably time to shrink it down.
717  if (_table_size <= 16 || _num_entries >= (_table_size >> 3)) {
718  return false;
719  } else {
720  size_t new_size = _table_size;
721  do {
722  new_size >>= 1;
723  } while (new_size >= 16 && _num_entries < (new_size >> 2));
724  resize_table(new_size);
725  return true;
726  }
727 }
728 
729 /**
730  * Resizes the existing table.
731  */
732 template<class Key, class Value, class Compare>
734 resize_table(size_t new_size) {
735  nassertv(_table_size != 0);
736  nassertv(new_size >= _num_entries);
737 
738  DeletedBufferChain *old_chain = _deleted_chain;
739  TableEntry *old_table = _table;
740 
741  _table_size = new_size;
742 
743  // We allocate enough bytes for _table_size elements of TableEntry, plus
744  // _table_size * sparsity more ints at the end (for the sparse index array).
745  size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size * sparsity * sizeof(int);
746  _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
747  _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
748  int *index_array = get_index_array();
749  memset(index_array, -1, _table_size * sizeof(int) * sparsity);
750 
751  // Now copy the entries from the old table into the new table. We don't
752  // have to reorder these, fortunately. Hopefully, a smart compiler will
753  // optimize this to a memcpy.
754  for (size_t i = 0; i < _num_entries; ++i) {
755  new(&_table[i]) TableEntry(std::move(old_table[i]));
756  old_table[i].~TableEntry();
757  }
758 
759  // We don't need this old thing anymore.
760  old_chain->deallocate(old_table, TypeHandle::none());
761 
762  // Reindex the table.
763  for (size_t i = 0; i < _num_entries; ++i) {
764  size_t slot = get_hash(_table[i]._key);
765 
766  while (has_slot(slot)) {
767  // Hash conflict; look for a better spot. This has to succeed.
768  slot = next_hash(slot);
769  }
770  index_array[slot] = (int)i;
771  }
772 
773  nassertv(validate());
774 }
This template class can be used to provide faster allocation/deallocation for many Panda objects.
void deallocate(void *ptr, TypeHandle type_handle)
Frees the memory for a buffer previously allocated via allocate().
void * allocate(size_t size, TypeHandle type_handle)
Allocates the memory for a new buffer of the indicated size (which must be no greater than the fixed ...
DeletedBufferChain * get_deleted_chain(size_t buffer_size)
Returns a pointer to a global DeletedBufferChain object suitable for allocating arrays of the indicat...
Definition: memoryHook.cxx:598
This template class implements an unordered map of keys to data, implemented as a hashtable.
Definition: simpleHashMap.h:81
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.
Definition: simpleHashMap.h:25