21 template<
class Key,
class Value,
class Compare>
37 template<
class Key,
class Value,
class Compare>
49 template<
class Key,
class Value,
class Compare>
52 TableEntry *t0 = _table;
53 _table = other._table;
57 _deleted_chain = other._deleted_chain;
58 other._deleted_chain = t1;
60 size_t t2 = _table_size;
61 _table_size = other._table_size;
62 other._table_size = t2;
64 size_t t3 = _num_entries;
65 _num_entries = other._num_entries;
66 other._num_entries = t3;
76 template<
class Key,
class Value,
class Compare>
78 find(
const Key &key)
const {
79 if (_table_size == 0) {
84 size_t index = get_hash(key);
85 if (!has_element(index)) {
88 if (is_element(index, key)) {
97 i = (i + 1) & (_table_size - 1);
98 while (i != index && has_element(i)) {
99 if (is_element(i, key)) {
102 i = (i + 1) & (_table_size - 1);
116 template<
class Key,
class Value,
class Compare>
118 store(
const Key &key,
const Value &data) {
119 if (_table_size == 0) {
121 nassertr(_num_entries == 0, -1);
123 size_t index = get_hash(key);
124 store_new_element(index, key, data);
127 nassertr(validate(), index);
132 size_t index = get_hash(key);
133 if (!has_element(index)) {
135 if (consider_expand_table()) {
136 return store(key, data);
138 store_new_element(index, key, data);
141 nassertr(validate(), index);
145 if (is_element(index, key)) {
148 _table[index]._data = data;
150 nassertr(validate(), index);
158 i = (i + 1) & (_table_size - 1);
160 if (!has_element(i)) {
161 if (consider_expand_table()) {
162 return store(key, data);
164 store_new_element(i, key, data);
167 nassertr(validate(), i);
171 if (is_element(i, key)) {
172 _table[i]._data = data;
174 nassertr(validate(), i);
178 i = (i + 1) & (_table_size - 1);
194 template<
class Key,
class Value,
class Compare>
197 int index = find(key);
201 remove_element(index);
210 template<
class Key,
class Value,
class Compare>
213 if (_table_size != 0) {
214 for (
size_t i = 0; i < _table_size; ++i) {
215 if (has_element(i)) {
222 _deleted_chain = NULL;
235 template<
class Key,
class Value,
class Compare>
238 int index = find(key);
240 index = store(key, Value());
242 return modify_data(index);
250 template<
class Key,
class Value,
class Compare>
264 template<
class Key,
class Value,
class Compare>
267 nassertr(n >= 0 && n < (
int)_table_size,
false);
268 return (get_exists_array()[n] != 0);
281 template<
class Key,
class Value,
class Compare>
284 nassertr(has_element(n), _table[n]._key);
285 return _table[n]._key;
298 template<
class Key,
class Value,
class Compare>
301 nassertr(has_element(n), _table[n]._data);
302 return _table[n]._data;
316 template<
class Key,
class Value,
class Compare>
319 nassertr(has_element(n), _table[n]._data);
320 return _table[n]._data;
333 template<
class Key,
class Value,
class Compare>
336 nassertv(has_element(n));
337 _table[n]._data = data;
350 template<
class Key,
class Value,
class Compare>
353 nassertv(has_element(n));
356 nassertv(_num_entries > 0);
363 i = (i + 1) & (_table_size - 1);
364 while (has_element(i)) {
365 size_t wants_index = get_hash(_table[i]._key);
366 if (wants_index != i) {
370 while (wants_index != i && has_element(wants_index)) {
371 wants_index = (wants_index + 1) & (_table_size - 1);
373 if (wants_index != i) {
374 store_new_element(wants_index, _table[i]._key, _table[i]._data);
382 i = (i + 1) & (_table_size - 1);
386 nassertv(validate());
399 template<
class Key,
class Value,
class Compare>
411 template<
class Key,
class Value,
class Compare>
414 return (_num_entries == 0);
422 template<
class Key,
class Value,
class Compare>
424 output(ostream &out)
const {
425 out <<
"SimpleHashMap (" << _num_entries <<
" entries): [";
426 for (
size_t i = 0; i < _table_size; ++i) {
427 if (!has_element(i)) {
431 out <<
" " << _table[i]._key;
432 size_t index = get_hash(_table[i]._key);
436 out <<
"(" << ((_table_size + i - index) & (_table_size - 1)) <<
")";
448 template<
class Key,
class Value,
class Compare>
450 write(ostream &out)
const {
461 template<
class Key,
class Value,
class Compare>
466 for (
size_t i = 0; i < _table_size; ++i) {
467 if (has_element(i)) {
469 size_t ideal_index = get_hash(_table[i]._key);
470 size_t wants_index = ideal_index;
471 while (wants_index != i && has_element(wants_index)) {
472 wants_index = (wants_index + 1) & (_table_size - 1);
474 if (wants_index != i) {
476 <<
"SimpleHashMap is invalid: key " << _table[i]._key
477 <<
" should be in slot " << wants_index <<
" instead of "
478 << i <<
" (ideal is " << ideal_index <<
")\n";
479 write(util_cat.error(
false));
485 if (count != _num_entries) {
487 <<
"SimpleHashMap is invalid: reports " << _num_entries
488 <<
" entries, actually has " << count <<
"\n";
489 write(util_cat.error(
false));
502 template<
class Key,
class Value,
class Compare>
514 return ((_comp(key) * (
size_t)9973) >> 8) & (_table_size - 1);
522 template<
class Key,
class Value,
class Compare>
525 nassertr(has_element(n),
false);
526 return _comp.is_equal(_table[n]._key, key);
535 template<
class Key,
class Value,
class Compare>
538 new(&_table[n]) TableEntry(key, data);
539 get_exists_array()[n] =
true;
547 template<
class Key,
class Value,
class Compare>
550 _table[n].~TableEntry();
551 get_exists_array()[n] =
false;
562 template<
class Key,
class Value,
class Compare>
565 return (
unsigned char *)(_table + _table_size);
573 template<
class Key,
class Value,
class Compare>
576 nassertv(_table_size == 0 && _num_entries == 0);
584 size_t alloc_size = _table_size *
sizeof(TableEntry) + _table_size;
588 memset(get_exists_array(), 0, _table_size);
598 template<
class Key,
class Value,
class Compare>
601 if (_num_entries >= (_table_size >> 1)) {
613 template<
class Key,
class Value,
class Compare>
616 nassertv(_table_size != 0);
622 size_t old_table_size = old_map._table_size;
623 _table_size = (old_table_size << 1);
624 nassertv(_table == NULL);
628 size_t alloc_size = _table_size *
sizeof(TableEntry) + _table_size;
631 unsigned char *exists_array = get_exists_array();
632 memset(exists_array, 0, _table_size);
633 nassertv(_num_entries == 0);
637 for (
size_t i = 0; i < old_table_size; ++i) {
638 if (old_map.has_element(i)) {
639 size_t new_index = get_hash(old_map._table[i]._key);
641 while (exists_array[new_index] != 0) {
643 new_index = (new_index + 1) & (_table_size - 1);
646 #ifdef USE_MOVE_SEMANTICS
649 new(&_table[new_index]) TableEntry(move(old_map._table[i]));
651 new(&_table[new_index]) TableEntry(old_map._table[i]);
653 exists_array[new_index] =
true;
658 nassertv(validate());
659 nassertv(old_map.validate());
661 nassertv(_num_entries == old_map._num_entries);
int find(const Key &key) const
Searches for the indicated key in the table.
DeletedBufferChain * get_deleted_chain(size_t buffer_size)
Returns a pointer to a global DeletedBufferChain object suitable for allocating arrays of the indicat...
static TypeHandle none()
Returns a special zero-valued TypeHandle that is used to indicate no type.
int 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...
int store(const Key &key, const Value &data)
Records the indicated key/data pair in the map.
This template class implements an unordered map of keys to data, implemented as a hashtable...
void clear()
Completely empties the table.
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 ...
Value & modify_data(int n)
Returns a modifiable reference to the data in the nth slot of the table.
bool is_empty() const
Returns true if the table is empty; i.e.
int get_size() const
Returns the total number of slots in the table.
void set_data(int n, const Value &data)
Changes the data for the nth slot of the table.
bool validate() const
Returns true if the internal table appears to be consistent, false if there are some internal errors...
const Value & get_data(int n) const
Returns the data in the nth slot of the table.
This template class can be used to provide faster allocation/deallocation for many Panda objects...
void remove_element(int n)
Removes the nth slot from the table.
bool remove(const Key &key)
Removes the indicated key and its associated data from the table.
const Key & get_key(int n) const
Returns the key in the nth slot of the table.
void swap(SimpleHashMap &other)
Quickly exchanges the contents of this map and the other map.
bool has_element(int n) const
Returns true if there is an element stored in the nth slot, false otherwise.