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