17 template<
class Key,
class Value,
class Compare>
21 _deleted_chain(nullptr),
31 template<
class Key,
class Value,
class Compare>
35 _deleted_chain(nullptr),
36 _table_size(copy._table_size),
37 _num_entries(copy._num_entries),
42 if (_table_size > 0) {
43 size_t alloc_size = _table_size * (
sizeof(TableEntry) +
sizeof(
int) * sparsity);
46 _table = (TableEntry *)_deleted_chain->
allocate(alloc_size, TypeHandle::none());
48 for (
size_t i = 0; i < _num_entries; ++i) {
49 new(&_table[i]) TableEntry(copy._table[i]);
53 memcpy(get_index_array(), copy.get_index_array(), _table_size *
sizeof(
int) * sparsity);
60 template<
class Key,
class Value,
class Compare>
64 _deleted_chain(from._deleted_chain),
65 _table_size(from._table_size),
66 _num_entries(from._num_entries),
67 _comp(std::move(from._comp))
69 from._table =
nullptr;
70 from._deleted_chain =
nullptr;
72 from._num_entries = 0;
78 template<
class Key,
class Value,
class Compare>
87 template<
class Key,
class Value,
class Compare>
91 TableEntry *old_table = _table;
93 size_t old_num_entries = _num_entries;
95 _table_size = copy._table_size;
96 _num_entries = copy._num_entries;
99 if (_table_size > 0) {
102 size_t alloc_size = _table_size * (
sizeof(
TableEntry) +
sizeof(
int) * sparsity);
106 for (
size_t i = 0; i < _num_entries; ++i) {
111 memcpy(get_index_array(), copy.get_index_array(), _table_size *
sizeof(
int) * sparsity);
114 _deleted_chain =
nullptr;
117 if (old_table !=
nullptr) {
118 for (
size_t i = 0; i < old_num_entries; ++i) {
119 old_table[i].~TableEntry();
122 old_deleted_chain->
deallocate(old_table, TypeHandle::none());
131 template<
class Key,
class Value,
class Compare>
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);
141 from._table =
nullptr;
142 from._deleted_chain =
nullptr;
143 from._table_size = 0;
144 from._num_entries = 0;
151 template<
class Key,
class Value,
class Compare>
155 _table = other._table;
159 _deleted_chain = other._deleted_chain;
160 other._deleted_chain = t1;
162 size_t t2 = _table_size;
163 _table_size = other._table_size;
164 other._table_size = t2;
166 size_t t3 = _num_entries;
167 _num_entries = other._num_entries;
168 other._num_entries = t3;
175 template<
class Key,
class Value,
class Compare>
177 find(
const Key &key)
const {
178 if (_table_size == 0) {
183 int slot = find_slot(key);
185 return get_index_array()[slot];
196 template<
class Key,
class Value,
class Compare>
198 store(
const Key &key,
const Value &data) {
199 if (_table_size == 0) {
201 nassertr(_num_entries == 0, -1);
203 int pos = store_new_element(get_hash(key), key, data);
205 nassertr(validate(), pos);
209 consider_expand_table();
211 const int *index_array = get_index_array();
212 size_t hash = get_hash(key);
213 int index = index_array[hash];
216 if (consider_expand_table()) {
217 return store(key, data);
219 index = store_new_element(hash, key, data);
221 nassertr(validate(), index);
225 if (is_element(index, key)) {
227 set_data(index, data);
229 nassertr(validate(), index);
236 size_t slot = next_hash(hash);
237 while (slot != hash) {
238 index = index_array[slot];
240 if (consider_expand_table()) {
241 return store(key, data);
243 index = store_new_element(slot, key, data);
245 nassertr(validate(), index);
249 if (is_element(index, key)) {
250 set_data(index, data);
252 nassertr(validate(), index);
256 slot = next_hash(slot);
273 template<
class Key,
class Value,
class Compare>
276 if (_num_entries == 0) {
281 int *index_array = get_index_array();
282 size_t slot = (size_t)find_slot(key);
283 if (slot == (
size_t)-1) {
289 size_t last = _num_entries - 1;
290 size_t index = (size_t)index_array[slot];
291 if (index < _num_entries) {
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);
299 _table[index] = std::move(_table[last]);
300 index_array[(size_t)other_slot] = index;
303 _table[last].~TableEntry();
309 index_array[slot] = -1;
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) {
325 while (wants_slot != slot && has_slot(wants_slot)) {
326 wants_slot = next_hash(wants_slot);
328 if (wants_slot != slot) {
331 index_array[wants_slot] = index;
332 index_array[slot] = -1;
338 slot = next_hash(slot);
342 nassertr(validate(),
true);
350 template<
class Key,
class Value,
class Compare>
353 if (_table_size != 0) {
354 for (
size_t i = 0; i < _num_entries; ++i) {
355 _table[i].~TableEntry();
358 _deleted_chain->deallocate(_table, TypeHandle::none());
360 _deleted_chain =
nullptr;
370 template<
class Key,
class Value,
class Compare>
373 int index = find(key);
375 index = store(key, Value());
377 return modify_data(index);
383 template<
class Key,
class Value,
class Compare>
394 template<
class Key,
class Value,
class Compare>
397 nassertr(n < _num_entries, _table[n]._key);
398 return _table[n]._key;
406 template<
class Key,
class Value,
class Compare>
409 nassertr(n < _num_entries, _table[n].get_data());
410 return _table[n].get_data();
418 template<
class Key,
class Value,
class Compare>
421 nassertr(n < _num_entries, _table[n].modify_data());
422 return _table[n].modify_data();
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);
442 template<
class Key,
class Value,
class Compare>
445 nassertv(n < _num_entries);
446 _table[n].set_data(std::move(data));
454 template<
class Key,
class Value,
class Compare>
457 nassertv(n < _num_entries);
458 remove(_table[n]._key);
464 template<
class Key,
class Value,
class Compare>
473 template<
class Key,
class Value,
class Compare>
476 return (_num_entries == 0);
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)) {
493 size_t index = (size_t)index_array[slot];
495 size_t ideal_slot = get_hash(_table[index]._key);
496 if (ideal_slot != slot) {
499 out <<
"(" << ((_table_size + slot - ideal_slot) & (num_slots - 1)) <<
")";
509 template<
class Key,
class Value,
class Compare>
511 write(std::ostream &out)
const {
514 for (
size_t i = 0; i < _num_entries; ++i) {
515 out <<
" " << _table[i]._key <<
" (hash " << get_hash(_table[i]._key) <<
")\n";
523 template<
class Key,
class Value,
class Compare>
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];
534 if (index >= _num_entries) {
536 <<
"SimpleHashMap " <<
this <<
" is invalid: slot " << slot
537 <<
" contains index " << index <<
" which is past the end of the"
539 write(util_cat.error(
false));
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);
548 if (wants_slot != slot) {
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));
559 if (count != _num_entries) {
561 <<
"SimpleHashMap " <<
this <<
" is invalid: reports " << _num_entries
562 <<
" entries, actually has " << count <<
"\n";
563 write(util_cat.error(
false));
573 template<
class Key,
class Value,
class Compare>
584 return ((_comp(key) * (
size_t)9973) >> 8) & ((_table_size * sparsity) - 1);
590 template<
class Key,
class Value,
class Compare>
593 return (hash + 1) & ((_table_size * sparsity) - 1);
599 template<
class Key,
class Value,
class Compare>
602 const int *index_array = get_index_array();
603 size_t hash = get_hash(key);
604 int index = index_array[hash];
609 if (is_element((
size_t)index, key)) {
617 size_t slot = next_hash(hash);
618 while (slot != hash && has_slot(slot)) {
619 if (is_element((
size_t)index_array[slot], key)) {
622 slot = next_hash(slot);
631 template<
class Key,
class Value,
class Compare>
634 return get_index_array()[slot] >= 0;
640 template<
class Key,
class Value,
class Compare>
643 nassertr(n < _num_entries,
false);
644 return _comp.is_equal(_table[n]._key, key);
651 template<
class Key,
class Value,
class Compare>
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;
666 template<
class Key,
class Value,
class Compare>
669 return (
int *)(_table + _table_size);
675 template<
class Key,
class Value,
class Compare>
678 nassertv(_table_size == 0 && _num_entries == 0);
686 size_t alloc_size = _table_size * (
sizeof(TableEntry) +
sizeof(
int) * sparsity);
689 _table = (TableEntry *)_deleted_chain->
allocate(alloc_size, TypeHandle::none());
690 memset(get_index_array(), -1, _table_size *
sizeof(
int) * sparsity);
697 template<
class Key,
class Value,
class Compare>
700 if (_num_entries < _table_size) {
703 resize_table(_table_size << 1);
712 template<
class Key,
class Value,
class Compare>
717 if (_table_size <= 16 || _num_entries >= (_table_size >> 3)) {
720 size_t new_size = _table_size;
723 }
while (new_size >= 16 && _num_entries < (new_size >> 2));
724 resize_table(new_size);
732 template<
class Key,
class Value,
class Compare>
735 nassertv(_table_size != 0);
736 nassertv(new_size >= _num_entries);
739 TableEntry *old_table = _table;
741 _table_size = new_size;
745 size_t alloc_size = _table_size *
sizeof(TableEntry) + _table_size * sparsity *
sizeof(
int);
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);
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();
760 old_chain->
deallocate(old_table, TypeHandle::none());
763 for (
size_t i = 0; i < _num_entries; ++i) {
764 size_t slot = get_hash(_table[i]._key);
766 while (has_slot(slot)) {
768 slot = next_hash(slot);
770 index_array[slot] = (int)i;
773 nassertv(validate());
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.