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);
88 if (is_element(index, key)) {
97 i = (i + 1) & (_table_size - 1);
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);
132 size_t index = get_hash(key);
135 if (consider_expand_table()) {
136 return store(key, data);
138 store_new_element(index, key, data);
145 if (is_element(index, key)) {
148 _table[index]._data = data;
158 i = (i + 1) & (_table_size - 1);
161 if (consider_expand_table()) {
162 return store(key, data);
164 store_new_element(i, key, data);
171 if (is_element(i, key)) {
172 _table[i]._data = data;
178 i = (i + 1) & (_table_size - 1);
194 template<
class Key,
class Value,
class Compare>
197 int index =
find(key);
210 template<
class Key,
class Value,
class Compare>
213 if (_table_size != 0) {
214 for (
size_t i = 0; i < _table_size; ++i) {
222 _deleted_chain = NULL;
235 template<
class Key,
class Value,
class Compare>
238 int index =
find(key);
240 index =
store(key, Value());
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>
285 return _table[n]._key;
298 template<
class Key,
class Value,
class Compare>
302 return _table[n]._data;
316 template<
class Key,
class Value,
class Compare>
320 return _table[n]._data;
333 template<
class Key,
class Value,
class Compare>
337 _table[n]._data = data;
350 template<
class Key,
class Value,
class Compare>
356 nassertv(_num_entries > 0);
363 i = (i + 1) & (_table_size - 1);
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);
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) {
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) {
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>
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;
587 _table = (TableEntry *)_deleted_chain->allocate(alloc_size,
TypeHandle::none());
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;
630 _table = (TableEntry *)_deleted_chain->allocate(alloc_size,
TypeHandle::none());
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) {
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;
661 nassertv(_num_entries == old_map._num_entries);
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.
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...
const Key & get_key(int n) const
Returns the key in the nth slot of the table.
void clear()
Completely empties the table.
int get_num_entries() const
Returns the number of active entries in the table.
Value & modify_data(int n)
Returns a modifiable reference to the data in the nth slot of the table.
bool has_element(int n) const
Returns true if there is an element stored in the nth slot, false otherwise.
void deallocate(void *ptr, TypeHandle type_handle)
Frees the memory for a buffer previously allocated via allocate().
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.
void set_data(int n, const Value &data)
Changes the data for the nth slot of the table.
bool is_empty() const
Returns true if the table is empty; i.e.
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.
int get_size() const
Returns the total number of slots in the table.
void swap(SimpleHashMap &other)
Quickly exchanges the contents of this map and the other map.
int find(const Key &key) const
Searches for the indicated key in the table.