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 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 */
350template<class Key, class Value, class Compare>
352clear() {
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 */
370template<class Key, class Value, class Compare>
372operator [] (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 */
383template<class Key, class Value, class Compare>
385size() 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 */
394template<class Key, class Value, class Compare>
396get_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 */
406template<class Key, class Value, class Compare>
408get_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 */
418template<class Key, class Value, class Compare>
420modify_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 */
430template<class Key, class Value, class Compare>
432set_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 */
442template<class Key, class Value, class Compare>
444set_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 */
454template<class Key, class Value, class Compare>
456remove_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 */
464template<class Key, class Value, class Compare>
466get_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 */
473template<class Key, class Value, class Compare>
475is_empty() const {
476 return (_num_entries == 0);
477}
478
479/**
480 *
481 */
482template<class Key, class Value, class Compare>
484output(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 */
509template<class Key, class Value, class Compare>
511write(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 */
523template<class Key, class Value, class Compare>
525validate() 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 write(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 return false;
540 }
541 nassertd(index < _num_entries) continue;
542 size_t ideal_slot = get_hash(_table[index]._key);
543 size_t wants_slot = ideal_slot;
544 while (wants_slot != slot && has_slot(wants_slot)) {
545 wants_slot = next_hash(wants_slot);
546 }
547 if (wants_slot != slot) {
548 write(util_cat->error()
549 << "SimpleHashMap " << this << " is invalid: key "
550 << _table[index]._key << " should be in slot " << wants_slot
551 << " instead of " << slot << " (ideal is " << ideal_slot << ")\n");
552 return false;
553 }
554 }
555 }
556
557 if (count != _num_entries) {
558 write(util_cat->error()
559 << "SimpleHashMap " << this << " is invalid: reports " << _num_entries
560 << " entries, actually has " << count << "\n");
561 return false;
562 }
563
564 return true;
565}
566
567/**
568 * Computes an appropriate index number to store the given pointer.
569 */
570template<class Key, class Value, class Compare>
572get_hash(const Key &key) const {
573 /*
574 // We want a hash constant 0 < k < 1. This one is suggested by Knuth:
575 static const double hash_constant = (sqrt(5.0) - 1.0) / 2.0;
576 double f = ((double)_comp(key) * hash_constant);
577 f -= floor(f);
578 return (size_t)floor(f * _table_size);
579 */
580
581 return ((_comp(key) * (size_t)9973) >> 8) & ((_table_size * sparsity) - 1);
582}
583
584/**
585 * Given a hash value, increments it, looping around the hash space.
586 */
587template<class Key, class Value, class Compare>
589next_hash(size_t hash) const {
590 return (hash + 1) & ((_table_size * sparsity) - 1);
591}
592
593/**
594 * Finds the slot in which the given key should fit.
595 */
596template<class Key, class Value, class Compare>
598find_slot(const Key &key) const {
599 const int *index_array = get_index_array();
600 size_t hash = get_hash(key);
601 int index = index_array[hash];
602 if (index < 0) {
603 return -1;
604 }
605
606 if (is_element((size_t)index, key)) {
607 return hash;
608 }
609
610 // There was some other key at the hashed slot. That's a hash conflict.
611 // Maybe our entry was recorded at a later slot position; scan the
612 // subsequent positions until we find the entry or an unused slot,
613 // indicating the end of the scan.
614 size_t slot = next_hash(hash);
615 while (slot != hash && has_slot(slot)) {
616 if (is_element((size_t)index_array[slot], key)) {
617 return (int)slot;
618 }
619 slot = next_hash(slot);
620 }
621
622 return -1;
623}
624
625/**
626 * Returns true if the given slot refers to an element.
627 */
628template<class Key, class Value, class Compare>
630has_slot(size_t slot) const {
631 return get_index_array()[slot] >= 0;
632}
633
634/**
635 * Returns true if element n matches key.
636 */
637template<class Key, class Value, class Compare>
639is_element(size_t n, const Key &key) const {
640 nassertr(n < _num_entries, false);
641 return _comp.is_equal(_table[n]._key, key);
642}
643
644/**
645 * Constructs a new TableEntry with the given slot, storing the indicated key
646 * and value.
647 */
648template<class Key, class Value, class Compare>
650store_new_element(size_t slot, const Key &key, const Value &data) {
651 size_t index = _num_entries++;
652 new(&_table[index]) TableEntry(key, data);
653 nassertr(get_index_array()[slot] == -1, index)
654 get_index_array()[slot] = index;
655 return index;
656}
657
658/**
659 * Returns the beginning of the array of _table_size ints that are the indices
660 * pointing to the location within the table where the elements are stored.
661 * within the table.
662 */
663template<class Key, class Value, class Compare>
665get_index_array() const {
666 return (int *)(_table + _table_size);
667}
668
669/**
670 * Allocates a brand new table.
671 */
672template<class Key, class Value, class Compare>
674new_table() {
675 nassertv(_table_size == 0 && _num_entries == 0);
676
677 // Pick a good initial table size. For now, we make it really small. Maybe
678 // that's the right answer.
679 _table_size = 2;
680
681 // We allocate enough bytes for _table_size elements of TableEntry, plus
682 // _table_size * 4 more ints at the end (for the index array).
683 size_t alloc_size = _table_size * (sizeof(TableEntry) + sizeof(int) * sparsity);
684
685 _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
686 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
687 memset(get_index_array(), -1, _table_size * sizeof(int) * sparsity);
688}
689
690/**
691 * Expands the table if it will need it (assuming one more element is about to
692 * be added). Returns true if expanded, false otherwise.
693 */
694template<class Key, class Value, class Compare>
697 if (_num_entries < _table_size) {
698 return false;
699 } else {
700 resize_table(_table_size << 1);
701 return true;
702 }
703}
704
705/**
706 * Shrinks the table if the allocated storage is significantly larger than the
707 * number of elements in it. Returns true if shrunk, false otherwise.
708 */
709template<class Key, class Value, class Compare>
712 // If the number of elements gets less than an eighth of the table size, we
713 // know it's probably time to shrink it down.
714 if (_table_size <= 16 || _num_entries >= (_table_size >> 3)) {
715 return false;
716 } else {
717 size_t new_size = _table_size;
718 do {
719 new_size >>= 1;
720 } while (new_size >= 16 && _num_entries < (new_size >> 2));
721 resize_table(new_size);
722 return true;
723 }
724}
725
726/**
727 * Resizes the existing table.
728 */
729template<class Key, class Value, class Compare>
731resize_table(size_t new_size) {
732 nassertv(_table_size != 0);
733 nassertv(new_size >= _num_entries);
734
735 DeletedBufferChain *old_chain = _deleted_chain;
736 TableEntry *old_table = _table;
737
738 _table_size = new_size;
739
740 // We allocate enough bytes for _table_size elements of TableEntry, plus
741 // _table_size * sparsity more ints at the end (for the sparse index array).
742 size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size * sparsity * sizeof(int);
743 _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
744 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
745 int *index_array = get_index_array();
746 memset(index_array, -1, _table_size * sizeof(int) * sparsity);
747
748 // Now copy the entries from the old table into the new table. We don't
749 // have to reorder these, fortunately. Hopefully, a smart compiler will
750 // optimize this to a memcpy.
751 for (size_t i = 0; i < _num_entries; ++i) {
752 new(&_table[i]) TableEntry(std::move(old_table[i]));
753 old_table[i].~TableEntry();
754 }
755
756 // We don't need this old thing anymore.
757 old_chain->deallocate(old_table, TypeHandle::none());
758
759 // Reindex the table.
760 for (size_t i = 0; i < _num_entries; ++i) {
761 size_t slot = get_hash(_table[i]._key);
762
763 while (has_slot(slot)) {
764 // Hash conflict; look for a better spot. This has to succeed.
765 slot = next_hash(slot);
766 }
767 index_array[slot] = (int)i;
768 }
769
770 nassertv(validate());
771}
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.