17 template<
class Key,
class Value,
class Compare>
21 _deleted_chain(nullptr),
31 template<
class Key,
class Value,
class Compare>
34 _table_size(copy._table_size),
35 _num_entries(copy._num_entries),
40 size_t alloc_size = _table_size * (
sizeof(TableEntry) +
sizeof(
int) * sparsity);
43 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
45 for (
size_t i = 0; i < _num_entries; ++i) {
46 new(&_table[i]) TableEntry(copy._table[i]);
50 memcpy(get_index_array(), copy.get_index_array(), _table_size *
sizeof(
int) * sparsity);
56 template<
class Key,
class Value,
class Compare>
60 _deleted_chain(from._deleted_chain),
61 _table_size(from._table_size),
62 _num_entries(from._num_entries),
63 _comp(std::move(from._comp))
65 from._table =
nullptr;
66 from._deleted_chain =
nullptr;
68 from._num_entries = 0;
74 template<
class Key,
class Value,
class Compare>
83 template<
class Key,
class Value,
class Compare>
87 _table_size = copy._table_size;
88 _num_entries = copy._num_entries;
93 size_t alloc_size = _table_size * (
sizeof(TableEntry) +
sizeof(
int) * sparsity);
97 for (
size_t i = 0; i < _num_entries; ++i) {
102 memcpy(get_index_array(), copy.get_index_array(), _table_size *
sizeof(
int) * sparsity);
110 template<
class Key,
class Value,
class Compare>
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);
120 from._table =
nullptr;
121 from._deleted_chain =
nullptr;
122 from._table_size = 0;
123 from._num_entries = 0;
130 template<
class Key,
class Value,
class Compare>
134 _table = other._table;
138 _deleted_chain = other._deleted_chain;
139 other._deleted_chain = t1;
141 size_t t2 = _table_size;
142 _table_size = other._table_size;
143 other._table_size = t2;
145 size_t t3 = _num_entries;
146 _num_entries = other._num_entries;
147 other._num_entries = t3;
154 template<
class Key,
class Value,
class Compare>
156 find(
const Key &key)
const {
157 if (_table_size == 0) {
162 int slot = find_slot(key);
164 return get_index_array()[slot];
175 template<
class Key,
class Value,
class Compare>
177 store(
const Key &key,
const Value &data) {
178 if (_table_size == 0) {
180 nassertr(_num_entries == 0, -1);
182 int pos = store_new_element(get_hash(key), key, data);
184 nassertr(validate(), pos);
188 consider_expand_table();
190 const int *index_array = get_index_array();
191 size_t hash = get_hash(key);
192 int index = index_array[hash];
195 if (consider_expand_table()) {
196 return store(key, data);
198 index = store_new_element(hash, key, data);
200 nassertr(validate(), index);
204 if (is_element(index, key)) {
206 set_data(index, data);
208 nassertr(validate(), index);
215 size_t slot = next_hash(hash);
216 while (slot != hash) {
217 index = index_array[slot];
219 if (consider_expand_table()) {
220 return store(key, data);
222 index = store_new_element(slot, key, data);
224 nassertr(validate(), index);
228 if (is_element(index, key)) {
229 set_data(index, data);
231 nassertr(validate(), index);
235 slot = next_hash(slot);
252 template<
class Key,
class Value,
class Compare>
255 if (_num_entries == 0) {
260 int *index_array = get_index_array();
261 size_t slot = (size_t)find_slot(key);
262 if (slot == (
size_t)-1) {
268 size_t last = _num_entries - 1;
269 size_t index = (size_t)index_array[slot];
270 if (index < _num_entries) {
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);
278 _table[index] = std::move(_table[last]);
279 index_array[(size_t)other_slot] = index;
282 _table[last].~TableEntry();
288 index_array[slot] = -1;
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) {
304 while (wants_slot != slot && has_slot(wants_slot)) {
305 wants_slot = next_hash(wants_slot);
307 if (wants_slot != slot) {
310 index_array[wants_slot] = index;
311 index_array[slot] = -1;
317 slot = next_hash(slot);
321 nassertr(validate(),
true);
329 template<
class Key,
class Value,
class Compare>
332 if (_table_size != 0) {
333 for (
size_t i = 0; i < _num_entries; ++i) {
334 _table[i].~TableEntry();
337 _deleted_chain->deallocate(_table, TypeHandle::none());
339 _deleted_chain =
nullptr;
349 template<
class Key,
class Value,
class Compare>
352 int index = find(key);
354 index = store(key, Value());
356 return modify_data(index);
362 template<
class Key,
class Value,
class Compare>
373 template<
class Key,
class Value,
class Compare>
376 nassertr(n < _num_entries, _table[n]._key);
377 return _table[n]._key;
385 template<
class Key,
class Value,
class Compare>
388 nassertr(n < _num_entries, _table[n].get_data());
389 return _table[n].get_data();
397 template<
class Key,
class Value,
class Compare>
400 nassertr(n < _num_entries, _table[n].modify_data());
401 return _table[n].modify_data();
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);
421 template<
class Key,
class Value,
class Compare>
424 nassertv(n < _num_entries);
425 _table[n].set_data(std::move(data));
433 template<
class Key,
class Value,
class Compare>
436 nassertv(n < _num_entries);
437 remove(_table[n]._key);
443 template<
class Key,
class Value,
class Compare>
452 template<
class Key,
class Value,
class Compare>
455 return (_num_entries == 0);
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)) {
472 size_t index = (size_t)index_array[slot];
474 size_t ideal_slot = get_hash(_table[index]._key);
475 if (ideal_slot != slot) {
478 out <<
"(" << ((_table_size + slot - ideal_slot) & (num_slots - 1)) <<
")";
488 template<
class Key,
class Value,
class Compare>
490 write(std::ostream &out)
const {
493 for (
size_t i = 0; i < _num_entries; ++i) {
494 out <<
" " << _table[i]._key <<
" (hash " << get_hash(_table[i]._key) <<
")\n";
502 template<
class Key,
class Value,
class Compare>
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];
513 if (index >= _num_entries) {
515 <<
"SimpleHashMap " <<
this <<
" is invalid: slot " << slot
516 <<
" contains index " << index <<
" which is past the end of the"
518 write(util_cat.error(
false));
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);
527 if (wants_slot != slot) {
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));
538 if (count != _num_entries) {
540 <<
"SimpleHashMap " <<
this <<
" is invalid: reports " << _num_entries
541 <<
" entries, actually has " << count <<
"\n";
542 write(util_cat.error(
false));
552 template<
class Key,
class Value,
class Compare>
563 return ((_comp(key) * (
size_t)9973) >> 8) & ((_table_size * sparsity) - 1);
569 template<
class Key,
class Value,
class Compare>
572 return (hash + 1) & ((_table_size * sparsity) - 1);
578 template<
class Key,
class Value,
class Compare>
581 const int *index_array = get_index_array();
582 size_t hash = get_hash(key);
583 int index = index_array[hash];
588 if (is_element((
size_t)index, key)) {
596 size_t slot = next_hash(hash);
597 while (slot != hash && has_slot(slot)) {
598 if (is_element((
size_t)index_array[slot], key)) {
601 slot = next_hash(slot);
610 template<
class Key,
class Value,
class Compare>
613 return get_index_array()[slot] >= 0;
619 template<
class Key,
class Value,
class Compare>
622 nassertr(n < _num_entries,
false);
623 return _comp.is_equal(_table[n]._key, key);
630 template<
class Key,
class Value,
class Compare>
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;
645 template<
class Key,
class Value,
class Compare>
648 return (
int *)(_table + _table_size);
654 template<
class Key,
class Value,
class Compare>
657 nassertv(_table_size == 0 && _num_entries == 0);
665 size_t alloc_size = _table_size * (
sizeof(TableEntry) +
sizeof(
int) * sparsity);
668 _table = (TableEntry *)_deleted_chain->
allocate(alloc_size, TypeHandle::none());
669 memset(get_index_array(), -1, _table_size *
sizeof(
int) * sparsity);
676 template<
class Key,
class Value,
class Compare>
679 if (_num_entries < _table_size) {
682 resize_table(_table_size << 1);
691 template<
class Key,
class Value,
class Compare>
696 if (_table_size <= 16 || _num_entries >= (_table_size >> 3)) {
699 size_t new_size = _table_size;
702 }
while (new_size >= 16 && _num_entries < (new_size >> 2));
703 resize_table(new_size);
711 template<
class Key,
class Value,
class Compare>
714 nassertv(_table_size != 0);
715 nassertv(new_size >= _num_entries);
718 TableEntry *old_table = _table;
720 _table_size = new_size;
724 size_t alloc_size = _table_size *
sizeof(TableEntry) + _table_size * sparsity *
sizeof(
int);
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);
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();
739 old_chain->
deallocate(old_table, TypeHandle::none());
742 for (
size_t i = 0; i < _num_entries; ++i) {
743 size_t slot = get_hash(_table[i]._key);
745 while (has_slot(slot)) {
747 slot = next_hash(slot);
749 index_array[slot] = (int)i;
752 nassertv(validate());