17template<
class Key,
class Value,
class Compare>
21 _deleted_chain(nullptr),
31template<
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);
60template<
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;
78template<
class Key,
class Value,
class Compare>
87template<
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());
131template<
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;
151template<
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;
175template<
class Key,
class Value,
class Compare>
177find(
const Key &key)
const {
178 if (_table_size == 0) {
183 int slot = find_slot(key);
185 return get_index_array()[slot];
196template<
class Key,
class Value,
class Compare>
198store(
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);
273template<
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);
350template<
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;
370template<
class Key,
class Value,
class Compare>
373 int index = find(key);
375 index = store(key, Value());
377 return modify_data(index);
383template<
class Key,
class Value,
class Compare>
394template<
class Key,
class Value,
class Compare>
397 nassertr(n < _num_entries, _table[n]._key);
398 return _table[n]._key;
406template<
class Key,
class Value,
class Compare>
409 nassertr(n < _num_entries, _table[n].get_data());
410 return _table[n].get_data();
418template<
class Key,
class Value,
class Compare>
421 nassertr(n < _num_entries, _table[n].modify_data());
422 return _table[n].modify_data();
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);
442template<
class Key,
class Value,
class Compare>
445 nassertv(n < _num_entries);
446 _table[n].set_data(std::move(data));
454template<
class Key,
class Value,
class Compare>
457 nassertv(n < _num_entries);
458 remove(_table[n]._key);
464template<
class Key,
class Value,
class Compare>
473template<
class Key,
class Value,
class Compare>
476 return (_num_entries == 0);
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)) {
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)) <<
")";
509template<
class Key,
class Value,
class Compare>
511write(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";
523template<
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) {
535 write(util_cat->error()
536 <<
"SimpleHashMap " <<
this <<
" is invalid: slot " << slot
537 <<
" contains index " << index <<
" which is past the end of the"
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);
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");
557 if (count != _num_entries) {
558 write(util_cat->error()
559 <<
"SimpleHashMap " <<
this <<
" is invalid: reports " << _num_entries
560 <<
" entries, actually has " << count <<
"\n");
570template<
class Key,
class Value,
class Compare>
581 return ((_comp(key) * (
size_t)9973) >> 8) & ((_table_size * sparsity) - 1);
587template<
class Key,
class Value,
class Compare>
590 return (hash + 1) & ((_table_size * sparsity) - 1);
596template<
class Key,
class Value,
class Compare>
599 const int *index_array = get_index_array();
600 size_t hash = get_hash(key);
601 int index = index_array[hash];
606 if (is_element((
size_t)index, key)) {
614 size_t slot = next_hash(hash);
615 while (slot != hash && has_slot(slot)) {
616 if (is_element((
size_t)index_array[slot], key)) {
619 slot = next_hash(slot);
628template<
class Key,
class Value,
class Compare>
631 return get_index_array()[slot] >= 0;
637template<
class Key,
class Value,
class Compare>
640 nassertr(n < _num_entries,
false);
641 return _comp.is_equal(_table[n]._key, key);
648template<
class Key,
class Value,
class Compare>
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;
663template<
class Key,
class Value,
class Compare>
666 return (
int *)(_table + _table_size);
672template<
class Key,
class Value,
class Compare>
675 nassertv(_table_size == 0 && _num_entries == 0);
683 size_t alloc_size = _table_size * (
sizeof(TableEntry) +
sizeof(
int) * sparsity);
686 _table = (TableEntry *)_deleted_chain->
allocate(alloc_size, TypeHandle::none());
687 memset(get_index_array(), -1, _table_size *
sizeof(
int) * sparsity);
694template<
class Key,
class Value,
class Compare>
697 if (_num_entries < _table_size) {
700 resize_table(_table_size << 1);
709template<
class Key,
class Value,
class Compare>
714 if (_table_size <= 16 || _num_entries >= (_table_size >> 3)) {
717 size_t new_size = _table_size;
720 }
while (new_size >= 16 && _num_entries < (new_size >> 2));
721 resize_table(new_size);
729template<
class Key,
class Value,
class Compare>
732 nassertv(_table_size != 0);
733 nassertv(new_size >= _num_entries);
736 TableEntry *old_table = _table;
738 _table_size = new_size;
742 size_t alloc_size = _table_size *
sizeof(TableEntry) + _table_size * sparsity *
sizeof(
int);
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);
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();
757 old_chain->
deallocate(old_table, TypeHandle::none());
760 for (
size_t i = 0; i < _num_entries; ++i) {
761 size_t slot = get_hash(_table[i]._key);
763 while (has_slot(slot)) {
765 slot = next_hash(slot);
767 index_array[slot] = (int)i;
770 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.