Panda3D
Loading...
Searching...
No Matches
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 */
17template<class Key, class Value, class Compare>
19SimpleHashMap(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 */
31template<class Key, class Value, class Compare>
33SimpleHashMap(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 */
60template<class Key, class Value, class Compare>
62SimpleHashMap(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 */
78template<class Key, class Value, class Compare>
81 clear();
82}
83
84/**
85 *
86 */
87template<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;
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);
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]);
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();
121
122 old_deleted_chain->deallocate(old_table, TypeHandle::none());
123 }
124 }
125 return *this;
126}
127
128/**
129 *
130 */
131template<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 */
151template<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 */
175template<class Key, class Value, class Compare>
177find(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 */
196template<class Key, class Value, class Compare>
198store(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 */
273template<class Key, class Value, class Compare>
275remove(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 int index = index_array[slot];
291 if ((size_t)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[(size_t)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 index = index_array[slot];
320 while (index >= 0) {
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 && index_array[wants_slot] >= 0) {
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 index = index_array[slot];
340 }
341
342#ifdef _DEBUG
343 nassertr(validate(), true);
344#endif
345 return true;
346}
347
348/**
349 * Completely empties the table.
350 */
351template<class Key, class Value, class Compare>
353clear() {
354 if (_table_size != 0) {
355 for (size_t i = 0; i < _num_entries; ++i) {
356 _table[i].~TableEntry();
357 }
358
359 _deleted_chain->deallocate(_table, TypeHandle::none());
360 _table = nullptr;
361 _deleted_chain = nullptr;
362 _table_size = 0;
363 _num_entries = 0;
364 }
365}
366
367/**
368 * Returns a modifiable reference to the data associated with the indicated
369 * key, or creates a new data entry and returns its reference.
370 */
371template<class Key, class Value, class Compare>
373operator [] (const Key &key) {
374 int index = find(key);
375 if (index == -1) {
376 index = store(key, Value());
377 }
378 return modify_data(index);
379}
380
381/**
382 * Returns the total number of entries in the table. Same as get_num_entries.
383 */
384template<class Key, class Value, class Compare>
386size() const {
387 return _num_entries;
388}
389
390/**
391 * Returns the key in the nth entry of the table.
392 *
393 * @param n should be in the range 0 <= n < size().
394 */
395template<class Key, class Value, class Compare>
397get_key(size_t n) const {
398 nassertr(n < _num_entries, _table[n]._key);
399 return _table[n]._key;
400}
401
402/**
403 * Returns the data in the nth entry of the table.
404 *
405 * @param n should be in the range 0 <= n < size().
406 */
407template<class Key, class Value, class Compare>
409get_data(size_t n) const {
410 nassertr(n < _num_entries, _table[n].get_data());
411 return _table[n].get_data();
412}
413
414/**
415 * Returns a modifiable reference to the data in the nth entry of the table.
416 *
417 * @param n should be in the range 0 <= n < size().
418 */
419template<class Key, class Value, class Compare>
421modify_data(size_t n) {
422 nassertr(n < _num_entries, _table[n].modify_data());
423 return _table[n].modify_data();
424}
425
426/**
427 * Changes the data for the nth entry of the table.
428 *
429 * @param n should be in the range 0 <= n < size().
430 */
431template<class Key, class Value, class Compare>
433set_data(size_t n, const Value &data) {
434 nassertv(n < _num_entries);
435 _table[n].set_data(data);
436}
437
438/**
439 * Changes the data for the nth entry of the table.
440 *
441 * @param n should be in the range 0 <= n < size().
442 */
443template<class Key, class Value, class Compare>
445set_data(size_t n, Value &&data) {
446 nassertv(n < _num_entries);
447 _table[n].set_data(std::move(data));
448}
449
450/**
451 * Removes the nth entry from the table.
452 *
453 * @param n should be in the range 0 <= n < size().
454 */
455template<class Key, class Value, class Compare>
457remove_element(size_t n) {
458 nassertv(n < _num_entries);
459 remove(_table[n]._key);
460}
461
462/**
463 * Returns the number of active entries in the table. Same as size().
464 */
465template<class Key, class Value, class Compare>
467get_num_entries() const {
468 return _num_entries;
469}
470
471/**
472 * Returns true if the table is empty; i.e. get_num_entries() == 0.
473 */
474template<class Key, class Value, class Compare>
476is_empty() const {
477 return (_num_entries == 0);
478}
479
480/**
481 *
482 */
483template<class Key, class Value, class Compare>
485output(std::ostream &out) const {
486 out << "SimpleHashMap (" << _num_entries << " entries): [";
487 const int *index_array = get_index_array();
488 size_t num_slots = _table_size * sparsity;
489 for (size_t slot = 0; slot < num_slots; ++slot) {
490 if (!has_slot(slot)) {
491 out << " *";
492
493 } else {
494 size_t index = (size_t)index_array[slot];
495 out << " " << index;
496 size_t ideal_slot = get_hash(_table[index]._key);
497 if (ideal_slot != slot) {
498 // This was misplaced as the result of a hash conflict. Report how
499 // far off it is.
500 out << "(" << ((_table_size + slot - ideal_slot) & (num_slots - 1)) << ")";
501 }
502 }
503 }
504 out << " ]";
505}
506
507/**
508 *
509 */
510template<class Key, class Value, class Compare>
512write(std::ostream &out) const {
513 output(out);
514 out << "\n";
515 for (size_t i = 0; i < _num_entries; ++i) {
516 out << " " << _table[i]._key << " (hash " << get_hash(_table[i]._key) << ")\n";
517 }
518}
519
520/**
521 * Returns true if the internal table appears to be consistent, false if there
522 * are some internal errors.
523 */
524template<class Key, class Value, class Compare>
526validate() const {
527 size_t count = 0;
528
529 const int *index_array = get_index_array();
530 size_t num_slots = _table_size * sparsity;
531 for (size_t slot = 0; slot < num_slots; ++slot) {
532 if (has_slot(slot)) {
533 size_t index = (size_t)index_array[slot];
534 ++count;
535 if (index >= _num_entries) {
536 write(util_cat->error()
537 << "SimpleHashMap " << this << " is invalid: slot " << slot
538 << " contains index " << index << " which is past the end of the"
539 " table\n");
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 write(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 return false;
554 }
555 }
556 }
557
558 if (count != _num_entries) {
559 write(util_cat->error()
560 << "SimpleHashMap " << this << " is invalid: reports " << _num_entries
561 << " entries, actually has " << count << "\n");
562 return false;
563 }
564
565 return true;
566}
567
568/**
569 * Computes an appropriate index number to store the given pointer.
570 */
571template<class Key, class Value, class Compare>
573get_hash(const Key &key) const {
574 /*
575 // We want a hash constant 0 < k < 1. This one is suggested by Knuth:
576 static const double hash_constant = (sqrt(5.0) - 1.0) / 2.0;
577 double f = ((double)_comp(key) * hash_constant);
578 f -= floor(f);
579 return (size_t)floor(f * _table_size);
580 */
581
582 return ((_comp(key) * (size_t)9973) >> 8) & ((_table_size * sparsity) - 1);
583}
584
585/**
586 * Given a hash value, increments it, looping around the hash space.
587 */
588template<class Key, class Value, class Compare>
590next_hash(size_t hash) const {
591 return (hash + 1) & ((_table_size * sparsity) - 1);
592}
593
594/**
595 * Finds the slot in which the given key should fit.
596 */
597template<class Key, class Value, class Compare>
599find_slot(const Key &key) const {
600 const int *index_array = get_index_array();
601 size_t hash = get_hash(key);
602 int index = index_array[hash];
603 if (index < 0) {
604 return -1;
605 }
606
607 if (is_element((size_t)index, key)) {
608 return hash;
609 }
610
611 // There was some other key at the hashed slot. That's a hash conflict.
612 // Maybe our entry was recorded at a later slot position; scan the
613 // subsequent positions until we find the entry or an unused slot,
614 // indicating the end of the scan.
615 size_t slot = next_hash(hash);
616 while (slot != hash && has_slot(slot)) {
617 if (is_element((size_t)index_array[slot], key)) {
618 return (int)slot;
619 }
620 slot = next_hash(slot);
621 }
622
623 return -1;
624}
625
626/**
627 * Returns true if the given slot refers to an element.
628 */
629template<class Key, class Value, class Compare>
631has_slot(size_t slot) const {
632 return get_index_array()[slot] >= 0;
633}
634
635/**
636 * Returns true if element n matches key.
637 */
638template<class Key, class Value, class Compare>
640is_element(size_t n, const Key &key) const {
641 nassertr(n < _num_entries, false);
642 return _comp.is_equal(_table[n]._key, key);
643}
644
645/**
646 * Constructs a new TableEntry with the given slot, storing the indicated key
647 * and value.
648 */
649template<class Key, class Value, class Compare>
651store_new_element(size_t slot, const Key &key, const Value &data) {
652 size_t index = _num_entries++;
653 new(&_table[index]) TableEntry(key, data);
654 nassertr(get_index_array()[slot] == -1, index)
655 get_index_array()[slot] = index;
656 return index;
657}
658
659/**
660 * Returns the beginning of the array of _table_size ints that are the indices
661 * pointing to the location within the table where the elements are stored.
662 * within the table.
663 */
664template<class Key, class Value, class Compare>
666get_index_array() const {
667 return (int *)(_table + _table_size);
668}
669
670/**
671 * Allocates a brand new table.
672 */
673template<class Key, class Value, class Compare>
675new_table() {
676 nassertv(_table_size == 0 && _num_entries == 0);
677
678 // Pick a good initial table size. For now, we make it really small. Maybe
679 // that's the right answer.
680 _table_size = 2;
681
682 // We allocate enough bytes for _table_size elements of TableEntry, plus
683 // _table_size * 4 more ints at the end (for the index array).
684 size_t alloc_size = _table_size * (sizeof(TableEntry) + sizeof(int) * sparsity);
685
686 _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
687 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
688 memset(get_index_array(), -1, _table_size * sizeof(int) * sparsity);
689}
690
691/**
692 * Expands the table if it will need it (assuming one more element is about to
693 * be added). Returns true if expanded, false otherwise.
694 */
695template<class Key, class Value, class Compare>
698 if (_num_entries < _table_size) {
699 return false;
700 } else {
701 resize_table(_table_size << 1);
702 return true;
703 }
704}
705
706/**
707 * Shrinks the table if the allocated storage is significantly larger than the
708 * number of elements in it. Returns true if shrunk, false otherwise.
709 */
710template<class Key, class Value, class Compare>
713 // If the number of elements gets less than an eighth of the table size, we
714 // know it's probably time to shrink it down.
715 if (_table_size <= 16 || _num_entries >= (_table_size >> 3)) {
716 return false;
717 } else {
718 size_t new_size = _table_size;
719 do {
720 new_size >>= 1;
721 } while (new_size >= 16 && _num_entries < (new_size >> 2));
722 resize_table(new_size);
723 return true;
724 }
725}
726
727/**
728 * Resizes the existing table.
729 */
730template<class Key, class Value, class Compare>
732resize_table(size_t new_size) {
733 nassertv(_table_size != 0);
734 nassertv(new_size >= _num_entries);
735
736 DeletedBufferChain *old_chain = _deleted_chain;
737 TableEntry *old_table = _table;
738
739 _table_size = new_size;
740
741 // We allocate enough bytes for _table_size elements of TableEntry, plus
742 // _table_size * sparsity more ints at the end (for the sparse index array).
743 size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size * sparsity * sizeof(int);
744 _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
745 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
746 int *index_array = get_index_array();
747 memset(index_array, -1, _table_size * sizeof(int) * sparsity);
748
749 // Now copy the entries from the old table into the new table. We don't
750 // have to reorder these, fortunately. Hopefully, a smart compiler will
751 // optimize this to a memcpy.
752 for (size_t i = 0; i < _num_entries; ++i) {
753 new(&_table[i]) TableEntry(std::move(old_table[i]));
754 old_table[i].~TableEntry();
755 }
756
757 // We don't need this old thing anymore.
758 old_chain->deallocate(old_table, TypeHandle::none());
759
760 // Reindex the table.
761 for (size_t i = 0; i < _num_entries; ++i) {
762 size_t slot = get_hash(_table[i]._key);
763
764 while (has_slot(slot)) {
765 // Hash conflict; look for a better spot. This has to succeed.
766 slot = next_hash(slot);
767 }
768 index_array[slot] = (int)i;
769 }
770
771 nassertv(validate());
772}
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...
This template class implements an unordered map of keys to data, implemented as a hashtable.
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.