Panda3D
 All Classes Functions Variables Enumerations
simpleHashMap.I
1 // Filename: simpleHashMap.I
2 // Created by: drose (19Jul07)
3 //
4 ////////////////////////////////////////////////////////////////////
5 //
6 // PANDA 3D SOFTWARE
7 // Copyright (c) Carnegie Mellon University. All rights reserved.
8 //
9 // All use of this software is subject to the terms of the revised BSD
10 // license. You should have received a copy of this license along
11 // with this source code in a file named "LICENSE."
12 //
13 ////////////////////////////////////////////////////////////////////
14 
15 
16 ////////////////////////////////////////////////////////////////////
17 // Function: SimpleHashMap::Constructor
18 // Access: Public
19 // Description:
20 ////////////////////////////////////////////////////////////////////
21 template<class Key, class Value, class Compare>
23 SimpleHashMap(const Compare &comp) :
24  _table(NULL),
25  _deleted_chain(NULL),
26  _table_size(0),
27  _num_entries(0),
28  _comp(comp)
29 {
30 }
31 
32 ////////////////////////////////////////////////////////////////////
33 // Function: SimpleHashMap::Destructor
34 // Access: Public
35 // Description:
36 ////////////////////////////////////////////////////////////////////
37 template<class Key, class Value, class Compare>
40  clear();
41 }
42 
43 ////////////////////////////////////////////////////////////////////
44 // Function: SimpleHashMap::swap
45 // Access: Public
46 // Description: Quickly exchanges the contents of this map and the
47 // other map.
48 ////////////////////////////////////////////////////////////////////
49 template<class Key, class Value, class Compare>
52  TableEntry *t0 = _table;
53  _table = other._table;
54  other._table = t0;
55 
56  DeletedBufferChain *t1 = _deleted_chain;
57  _deleted_chain = other._deleted_chain;
58  other._deleted_chain = t1;
59 
60  size_t t2 = _table_size;
61  _table_size = other._table_size;
62  other._table_size = t2;
63 
64  size_t t3 = _num_entries;
65  _num_entries = other._num_entries;
66  other._num_entries = t3;
67 }
68 
69 ////////////////////////////////////////////////////////////////////
70 // Function: SimpleHashMap::find
71 // Access: Public
72 // Description: Searches for the indicated key in the table. Returns
73 // its index number if it is found, or -1 if it is not
74 // present in the table.
75 ////////////////////////////////////////////////////////////////////
76 template<class Key, class Value, class Compare>
78 find(const Key &key) const {
79  if (_table_size == 0) {
80  // Special case: the table is empty.
81  return -1;
82  }
83 
84  size_t index = get_hash(key);
85  if (!has_element(index)) {
86  return -1;
87  }
88  if (is_element(index, key)) {
89  return index;
90  }
91 
92  // There was some other key at the hashed slot. That's a hash
93  // conflict. Maybe our entry was recorded at a later slot position;
94  // scan the subsequent positions until we find the entry or an
95  // unused slot, indicating the end of the scan.
96  size_t i = index;
97  i = (i + 1) & (_table_size - 1);
98  while (i != index && has_element(i)) {
99  if (is_element(i, key)) {
100  return i;
101  }
102  i = (i + 1) & (_table_size - 1);
103  }
104 
105  // The key is not in the table.
106  return -1;
107 }
108 
109 ////////////////////////////////////////////////////////////////////
110 // Function: SimpleHashMap::store
111 // Access: Public
112 // Description: Records the indicated key/data pair in the map. If
113 // the key was already present, silently replaces it.
114 // Returns the index at which it was stored.
115 ////////////////////////////////////////////////////////////////////
116 template<class Key, class Value, class Compare>
118 store(const Key &key, const Value &data) {
119  if (_table_size == 0) {
120  // Special case: the first key in an empty table.
121  nassertr(_num_entries == 0, -1);
122  new_table();
123  size_t index = get_hash(key);
124  store_new_element(index, key, data);
125  ++_num_entries;
126 #ifdef _DEBUG
127  nassertr(validate(), index);
128 #endif
129  return index;
130  }
131 
132  size_t index = get_hash(key);
133  if (!has_element(index)) {
134  // This element is not already in the map; add it.
135  if (consider_expand_table()) {
136  return store(key, data);
137  }
138  store_new_element(index, key, data);
139  ++_num_entries;
140 #ifdef _DEBUG
141  nassertr(validate(), index);
142 #endif
143  return index;
144  }
145  if (is_element(index, key)) {
146  // This element is already in the map; replace the data at that
147  // key.
148  _table[index]._data = data;
149 #ifdef _DEBUG
150  nassertr(validate(), index);
151 #endif
152  return index;
153  }
154 
155  // There was some other key at the hashed slot. That's a hash
156  // conflict. Record this entry at a later position.
157  size_t i = index;
158  i = (i + 1) & (_table_size - 1);
159  while (i != index) {
160  if (!has_element(i)) {
161  if (consider_expand_table()) {
162  return store(key, data);
163  }
164  store_new_element(i, key, data);
165  ++_num_entries;
166 #ifdef _DEBUG
167  nassertr(validate(), i);
168 #endif
169  return i;
170  }
171  if (is_element(i, key)) {
172  _table[i]._data = data;
173 #ifdef _DEBUG
174  nassertr(validate(), i);
175 #endif
176  return i;
177  }
178  i = (i + 1) & (_table_size - 1);
179  }
180 
181  // Shouldn't get here unless _num_entries == _table_size, which
182  // shouldn't be possible due to consider_expand_table().
183  nassertr(false, -1);
184  return -1; // To satisfy compiler
185 }
186 
187 ////////////////////////////////////////////////////////////////////
188 // Function: SimpleHashMap::remove
189 // Access: Public
190 // Description: Removes the indicated key and its associated data
191 // from the table. Returns true if the key was removed,
192 // false if it was not present.
193 ////////////////////////////////////////////////////////////////////
194 template<class Key, class Value, class Compare>
196 remove(const Key &key) {
197  int index = find(key);
198  if (index == -1) {
199  return false;
200  }
201  remove_element(index);
202  return true;
203 }
204 
205 ////////////////////////////////////////////////////////////////////
206 // Function: SimpleHashMap::clear
207 // Access: Public
208 // Description: Completely empties the table.
209 ////////////////////////////////////////////////////////////////////
210 template<class Key, class Value, class Compare>
212 clear() {
213  if (_table_size != 0) {
214  for (size_t i = 0; i < _table_size; ++i) {
215  if (has_element(i)) {
216  clear_element(i);
217  }
218  }
219 
220  _deleted_chain->deallocate(_table, TypeHandle::none());
221  _table = NULL;
222  _deleted_chain = NULL;
223  _table_size = 0;
224  _num_entries = 0;
225  }
226 }
227 
228 ////////////////////////////////////////////////////////////////////
229 // Function: SimpleHashMap::operator []
230 // Access: Public
231 // Description: Returns a modifiable reference to the data associated
232 // with the indicated key, or creates a new data entry
233 // and returns its reference.
234 ////////////////////////////////////////////////////////////////////
235 template<class Key, class Value, class Compare>
237 operator [] (const Key &key) {
238  int index = find(key);
239  if (index == -1) {
240  index = store(key, Value());
241  }
242  return modify_data(index);
243 }
244 
245 ////////////////////////////////////////////////////////////////////
246 // Function: SimpleHashMap::get_size
247 // Access: Public
248 // Description: Returns the total number of slots in the table.
249 ////////////////////////////////////////////////////////////////////
250 template<class Key, class Value, class Compare>
252 get_size() const {
253  return _table_size;
254 }
255 
256 ////////////////////////////////////////////////////////////////////
257 // Function: SimpleHashMap::has_element
258 // Access: Public
259 // Description: Returns true if there is an element stored in the nth
260 // slot, false otherwise.
261 //
262 // n should be in the range 0 <= n < get_size().
263 ////////////////////////////////////////////////////////////////////
264 template<class Key, class Value, class Compare>
266 has_element(int n) const {
267  nassertr(n >= 0 && n < (int)_table_size, false);
268  return (get_exists_array()[n] != 0);
269 }
270 
271 ////////////////////////////////////////////////////////////////////
272 // Function: SimpleHashMap::get_key
273 // Access: Public
274 // Description: Returns the key in the nth slot of the table.
275 //
276 // It is an error to call this if there is nothing
277 // stored in the nth slot (use has_element() to check
278 // this first). n should be in the range 0 <= n <
279 // get_size().
280 ////////////////////////////////////////////////////////////////////
281 template<class Key, class Value, class Compare>
282 INLINE const Key &SimpleHashMap<Key, Value, Compare>::
283 get_key(int n) const {
284  nassertr(has_element(n), _table[n]._key);
285  return _table[n]._key;
286 }
287 
288 ////////////////////////////////////////////////////////////////////
289 // Function: SimpleHashMap::get_data
290 // Access: Public
291 // Description: Returns the data in the nth slot of the table.
292 //
293 // It is an error to call this if there is nothing
294 // stored in the nth slot (use has_element() to check
295 // this first). n should be in the range 0 <= n <
296 // get_size().
297 ////////////////////////////////////////////////////////////////////
298 template<class Key, class Value, class Compare>
299 INLINE const Value &SimpleHashMap<Key, Value, Compare>::
300 get_data(int n) const {
301  nassertr(has_element(n), _table[n]._data);
302  return _table[n]._data;
303 }
304 
305 ////////////////////////////////////////////////////////////////////
306 // Function: SimpleHashMap::modify_data
307 // Access: Public
308 // Description: Returns a modifiable reference to the data in the nth
309 // slot of the table.
310 //
311 // It is an error to call this if there is nothing
312 // stored in the nth slot (use has_element() to check
313 // this first). n should be in the range 0 <= n <
314 // get_size().
315 ////////////////////////////////////////////////////////////////////
316 template<class Key, class Value, class Compare>
318 modify_data(int n) {
319  nassertr(has_element(n), _table[n]._data);
320  return _table[n]._data;
321 }
322 
323 ////////////////////////////////////////////////////////////////////
324 // Function: SimpleHashMap::set_data
325 // Access: Public
326 // Description: Changes the data for the nth slot of the table.
327 //
328 // It is an error to call this if there is nothing
329 // stored in the nth slot (use has_element() to check
330 // this first). n should be in the range 0 <= n <
331 // get_size().
332 ////////////////////////////////////////////////////////////////////
333 template<class Key, class Value, class Compare>
335 set_data(int n, const Value &data) {
336  nassertv(has_element(n));
337  _table[n]._data = data;
338 }
339 
340 ////////////////////////////////////////////////////////////////////
341 // Function: SimpleHashMap::remove_element
342 // Access: Public
343 // Description: Removes the nth slot from the table.
344 //
345 // It is an error to call this if there is nothing
346 // stored in the nth slot (use has_element() to check
347 // this first). n should be in the range 0 <= n <
348 // get_size().
349 ////////////////////////////////////////////////////////////////////
350 template<class Key, class Value, class Compare>
353  nassertv(has_element(n));
354 
355  clear_element(n);
356  nassertv(_num_entries > 0);
357  --_num_entries;
358 
359  // Now we have put a hole in the table. If there was a hash
360  // conflict in the slot following this one, we have to move it down
361  // to close the hole.
362  size_t i = n;
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) {
367  // This one was a hash conflict; try to put it where it belongs.
368  // We can't just put it in n, since maybe it belongs somewhere
369  // after n.
370  while (wants_index != i && has_element(wants_index)) {
371  wants_index = (wants_index + 1) & (_table_size - 1);
372  }
373  if (wants_index != i) {
374  store_new_element(wants_index, _table[i]._key, _table[i]._data);
375  clear_element(i);
376  }
377  }
378 
379  // Continue until we encounter the next unused slot. Until we do,
380  // we can't be sure we've found all of the potential hash
381  // conflicts.
382  i = (i + 1) & (_table_size - 1);
383  }
384 
385 #ifdef _DEBUG
386  nassertv(validate());
387 #endif
388 }
389 
390 ////////////////////////////////////////////////////////////////////
391 // Function: SimpleHashMap::get_num_entries
392 // Access: Public
393 // Description: Returns the number of active entries in the table.
394 // This is not necessarily related to the number of
395 // slots in the table as reported by get_size(). Use
396 // get_size() to iterate through all of the slots, not
397 // get_num_entries().
398 ////////////////////////////////////////////////////////////////////
399 template<class Key, class Value, class Compare>
402  return _num_entries;
403 }
404 
405 ////////////////////////////////////////////////////////////////////
406 // Function: SimpleHashMap::is_empty
407 // Access: Public
408 // Description: Returns true if the table is empty;
409 // i.e. get_num_entries() == 0.
410 ////////////////////////////////////////////////////////////////////
411 template<class Key, class Value, class Compare>
413 is_empty() const {
414  return (_num_entries == 0);
415 }
416 
417 ////////////////////////////////////////////////////////////////////
418 // Function: SimpleHashMap::output
419 // Access: Public
420 // Description:
421 ////////////////////////////////////////////////////////////////////
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)) {
428  out << " *";
429 
430  } else {
431  out << " " << _table[i]._key;
432  size_t index = get_hash(_table[i]._key);
433  if (index != i) {
434  // This was misplaced as the result of a hash conflict.
435  // Report how far off it is.
436  out << "(" << ((_table_size + i - index) & (_table_size - 1)) << ")";
437  }
438  }
439  }
440  out << " ]";
441 }
442 
443 ////////////////////////////////////////////////////////////////////
444 // Function: SimpleHashMap::write
445 // Access: Public
446 // Description:
447 ////////////////////////////////////////////////////////////////////
448 template<class Key, class Value, class Compare>
450 write(ostream &out) const {
451  output(out);
452  out << "\n";
453 }
454 
455 ////////////////////////////////////////////////////////////////////
456 // Function: SimpleHashMap::validate
457 // Access: Public
458 // Description: Returns true if the internal table appears to be
459 // consistent, false if there are some internal errors.
460 ////////////////////////////////////////////////////////////////////
461 template<class Key, class Value, class Compare>
463 validate() const {
464  size_t count = 0;
465 
466  for (size_t i = 0; i < _table_size; ++i) {
467  if (has_element(i)) {
468  ++count;
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);
473  }
474  if (wants_index != i) {
475  util_cat.error()
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));
480  return false;
481  }
482  }
483  }
484 
485  if (count != _num_entries) {
486  util_cat.error()
487  << "SimpleHashMap is invalid: reports " << _num_entries
488  << " entries, actually has " << count << "\n";
489  write(util_cat.error(false));
490  return false;
491  }
492 
493  return true;
494 }
495 
496 ////////////////////////////////////////////////////////////////////
497 // Function: SimpleHashMap::get_hash
498 // Access: Private
499 // Description: Computes an appropriate index number to store the
500 // given pointer.
501 ////////////////////////////////////////////////////////////////////
502 template<class Key, class Value, class Compare>
504 get_hash(const Key &key) const {
505  /*
506  // We want a hash constant 0 < k < 1. This one is suggested by
507  // Knuth:
508  static const double hash_constant = (sqrt(5.0) - 1.0) / 2.0;
509  double f = ((double)_comp(key) * hash_constant);
510  f -= floor(f);
511  return (size_t)floor(f * _table_size);
512  */
513 
514  return ((_comp(key) * (size_t)9973) >> 8) & (_table_size - 1);
515 }
516 
517 ////////////////////////////////////////////////////////////////////
518 // Function: SimpleHashMap::is_element
519 // Access: Private
520 // Description: Returns true if element n matches key.
521 ////////////////////////////////////////////////////////////////////
522 template<class Key, class Value, class Compare>
524 is_element(int n, const Key &key) const {
525  nassertr(has_element(n), false);
526  return _comp.is_equal(_table[n]._key, key);
527 }
528 
529 ////////////////////////////////////////////////////////////////////
530 // Function: SimpleHashMap::store_new_element
531 // Access: Private
532 // Description: Constructs a new TableEntry at position n, storing
533 // the indicated key and value.
534 ////////////////////////////////////////////////////////////////////
535 template<class Key, class Value, class Compare>
537 store_new_element(int n, const Key &key, const Value &data) {
538  new(&_table[n]) TableEntry(key, data);
539  get_exists_array()[n] = true;
540 }
541 
542 ////////////////////////////////////////////////////////////////////
543 // Function: SimpleHashMap::clear_element
544 // Access: Private
545 // Description: Destructs the TableEntry at position n.
546 ////////////////////////////////////////////////////////////////////
547 template<class Key, class Value, class Compare>
549 clear_element(int n) {
550  _table[n].~TableEntry();
551  get_exists_array()[n] = false;
552 }
553 
554 ////////////////////////////////////////////////////////////////////
555 // Function: SimpleHashMap::get_exists_array
556 // Access: Private
557 // Description: Returns the beginning of the array of _table_size
558 // unsigned chars that are the boolean flags for whether
559 // each element exists (has been constructed) within the
560 // table.
561 ////////////////////////////////////////////////////////////////////
562 template<class Key, class Value, class Compare>
563 INLINE unsigned char *SimpleHashMap<Key, Value, Compare>::
564 get_exists_array() const {
565  return (unsigned char *)(_table + _table_size);
566 }
567 
568 ////////////////////////////////////////////////////////////////////
569 // Function: SimpleHashMap::new_table
570 // Access: Private
571 // Description: Allocates a brand new table.
572 ////////////////////////////////////////////////////////////////////
573 template<class Key, class Value, class Compare>
575 new_table() {
576  nassertv(_table_size == 0 && _num_entries == 0);
577 
578  // Pick a good initial table size. For now, we make it really
579  // small. Maybe that's the right answer.
580  _table_size = 4;
581 
582  // We allocate enough bytes for _table_size elements of TableEntry,
583  // plus _table_size more bytes at the end (for the exists array).
584  size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size;
585 
586  _deleted_chain = memory_hook->get_deleted_chain(alloc_size);
587  _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none());
588  memset(get_exists_array(), 0, _table_size);
589 }
590 
591 ////////////////////////////////////////////////////////////////////
592 // Function: SimpleHashMap::consider_expand_table
593 // Access: Private
594 // Description: Expands the table if it will need it (assuming one
595 // more element is about to be added). Returns true if
596 // expanded, false otherwise.
597 ////////////////////////////////////////////////////////////////////
598 template<class Key, class Value, class Compare>
601  if (_num_entries >= (_table_size >> 1)) {
602  expand_table();
603  return true;
604  }
605  return false;
606 }
607 
608 ////////////////////////////////////////////////////////////////////
609 // Function: SimpleHashMap::expand_table
610 // Access: Private
611 // Description: Doubles the size of the existing table.
612 ////////////////////////////////////////////////////////////////////
613 template<class Key, class Value, class Compare>
615 expand_table() {
616  nassertv(_table_size != 0);
617 
618  SimpleHashMap<Key, Value, Compare> old_map(_comp);
619  swap(old_map);
620 
621  // Double the table size.
622  size_t old_table_size = old_map._table_size;
623  _table_size = (old_table_size << 1);
624  nassertv(_table == NULL);
625 
626  // We allocate enough bytes for _table_size elements of TableEntry,
627  // plus _table_size more bytes at the end (for the exists array).
628  size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size;
629  _deleted_chain = memory_hook->get_deleted_chain(alloc_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);
634 
635  // Now copy the entries from the old table into the new table.
636  int num_added = 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);
640 
641  while (exists_array[new_index] != 0) {
642  // Hash conflict; look for a better spot. This has to succeed.
643  new_index = (new_index + 1) & (_table_size - 1);
644  }
645 
646 #ifdef USE_MOVE_SEMANTICS
647  // Use C++11 rvalue references to invoke the move constructor,
648  // which may be more efficient.
649  new(&_table[new_index]) TableEntry(move(old_map._table[i]));
650 #else
651  new(&_table[new_index]) TableEntry(old_map._table[i]);
652 #endif
653  exists_array[new_index] = true;
654  ++_num_entries;
655  }
656  }
657 
658  nassertv(validate());
659  nassertv(old_map.validate());
660 
661  nassertv(_num_entries == old_map._num_entries);
662 }
int find(const Key &key) const
Searches for the indicated key in the table.
Definition: simpleHashMap.I:78
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.
Definition: typeHandle.I:274
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...
Definition: simpleHashMap.h:33
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.
Definition: simpleHashMap.I:51
bool has_element(int n) const
Returns true if there is an element stored in the nth slot, false otherwise.