Panda3D
|
00001 // Filename: simpleHashMap.I 00002 // Created by: drose (19Jul07) 00003 // 00004 //////////////////////////////////////////////////////////////////// 00005 // 00006 // PANDA 3D SOFTWARE 00007 // Copyright (c) Carnegie Mellon University. All rights reserved. 00008 // 00009 // All use of this software is subject to the terms of the revised BSD 00010 // license. You should have received a copy of this license along 00011 // with this source code in a file named "LICENSE." 00012 // 00013 //////////////////////////////////////////////////////////////////// 00014 00015 00016 //////////////////////////////////////////////////////////////////// 00017 // Function: SimpleHashMap::Constructor 00018 // Access: Public 00019 // Description: 00020 //////////////////////////////////////////////////////////////////// 00021 template<class Key, class Value, class Compare> 00022 INLINE SimpleHashMap<Key, Value, Compare>:: 00023 SimpleHashMap(const Compare &comp) : 00024 _table(NULL), 00025 _deleted_chain(NULL), 00026 _table_size(0), 00027 _num_entries(0), 00028 _comp(comp) 00029 { 00030 } 00031 00032 //////////////////////////////////////////////////////////////////// 00033 // Function: SimpleHashMap::Destructor 00034 // Access: Public 00035 // Description: 00036 //////////////////////////////////////////////////////////////////// 00037 template<class Key, class Value, class Compare> 00038 INLINE SimpleHashMap<Key, Value, Compare>:: 00039 ~SimpleHashMap() { 00040 clear(); 00041 } 00042 00043 //////////////////////////////////////////////////////////////////// 00044 // Function: SimpleHashMap::swap 00045 // Access: Public 00046 // Description: Quickly exchanges the contents of this map and the 00047 // other map. 00048 //////////////////////////////////////////////////////////////////// 00049 template<class Key, class Value, class Compare> 00050 INLINE void SimpleHashMap<Key, Value, Compare>:: 00051 swap(SimpleHashMap<Key, Value, Compare> &other) { 00052 TableEntry *t0 = _table; 00053 _table = other._table; 00054 other._table = t0; 00055 00056 DeletedBufferChain *t1 = _deleted_chain; 00057 _deleted_chain = other._deleted_chain; 00058 other._deleted_chain = t1; 00059 00060 size_t t2 = _table_size; 00061 _table_size = other._table_size; 00062 other._table_size = t2; 00063 00064 size_t t3 = _num_entries; 00065 _num_entries = other._num_entries; 00066 other._num_entries = t3; 00067 } 00068 00069 //////////////////////////////////////////////////////////////////// 00070 // Function: SimpleHashMap::find 00071 // Access: Public 00072 // Description: Searches for the indicated key in the table. Returns 00073 // its index number if it is found, or -1 if it is not 00074 // present in the table. 00075 //////////////////////////////////////////////////////////////////// 00076 template<class Key, class Value, class Compare> 00077 int SimpleHashMap<Key, Value, Compare>:: 00078 find(const Key &key) const { 00079 if (_table_size == 0) { 00080 // Special case: the table is empty. 00081 return -1; 00082 } 00083 00084 size_t index = get_hash(key); 00085 if (!has_element(index)) { 00086 return -1; 00087 } 00088 if (is_element(index, key)) { 00089 return index; 00090 } 00091 00092 // There was some other key at the hashed slot. That's a hash 00093 // conflict. Maybe our entry was recorded at a later slot position; 00094 // scan the subsequent positions until we find the entry or an 00095 // unused slot, indicating the end of the scan. 00096 size_t i = index; 00097 i = (i + 1) & (_table_size - 1); 00098 while (i != index && has_element(i)) { 00099 if (is_element(i, key)) { 00100 return i; 00101 } 00102 i = (i + 1) & (_table_size - 1); 00103 } 00104 00105 // The key is not in the table. 00106 return -1; 00107 } 00108 00109 //////////////////////////////////////////////////////////////////// 00110 // Function: SimpleHashMap::store 00111 // Access: Public 00112 // Description: Records the indicated key/data pair in the map. If 00113 // the key was already present, silently replaces it. 00114 // Returns the index at which it was stored. 00115 //////////////////////////////////////////////////////////////////// 00116 template<class Key, class Value, class Compare> 00117 int SimpleHashMap<Key, Value, Compare>:: 00118 store(const Key &key, const Value &data) { 00119 if (_table_size == 0) { 00120 // Special case: the first key in an empty table. 00121 nassertr(_num_entries == 0, -1); 00122 new_table(); 00123 size_t index = get_hash(key); 00124 store_new_element(index, key, data); 00125 ++_num_entries; 00126 #ifdef _DEBUG 00127 nassertr(validate(), index); 00128 #endif 00129 return index; 00130 } 00131 00132 size_t index = get_hash(key); 00133 if (!has_element(index)) { 00134 // This element is not already in the map; add it. 00135 if (consider_expand_table()) { 00136 return store(key, data); 00137 } 00138 store_new_element(index, key, data); 00139 ++_num_entries; 00140 #ifdef _DEBUG 00141 nassertr(validate(), index); 00142 #endif 00143 return index; 00144 } 00145 if (is_element(index, key)) { 00146 // This element is already in the map; replace the data at that 00147 // key. 00148 _table[index]._data = data; 00149 #ifdef _DEBUG 00150 nassertr(validate(), index); 00151 #endif 00152 return index; 00153 } 00154 00155 // There was some other key at the hashed slot. That's a hash 00156 // conflict. Record this entry at a later position. 00157 size_t i = index; 00158 i = (i + 1) & (_table_size - 1); 00159 while (i != index) { 00160 if (!has_element(i)) { 00161 if (consider_expand_table()) { 00162 return store(key, data); 00163 } 00164 store_new_element(i, key, data); 00165 ++_num_entries; 00166 #ifdef _DEBUG 00167 nassertr(validate(), i); 00168 #endif 00169 return i; 00170 } 00171 if (is_element(i, key)) { 00172 _table[i]._data = data; 00173 #ifdef _DEBUG 00174 nassertr(validate(), i); 00175 #endif 00176 return i; 00177 } 00178 i = (i + 1) & (_table_size - 1); 00179 } 00180 00181 // Shouldn't get here unless _num_entries == _table_size, which 00182 // shouldn't be possible due to consider_expand_table(). 00183 nassertr(false, -1); 00184 return -1; // To satisfy compiler 00185 } 00186 00187 //////////////////////////////////////////////////////////////////// 00188 // Function: SimpleHashMap::remove 00189 // Access: Public 00190 // Description: Removes the indicated key and its associated data 00191 // from the table. Returns true if the key was removed, 00192 // false if it was not present. 00193 //////////////////////////////////////////////////////////////////// 00194 template<class Key, class Value, class Compare> 00195 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00196 remove(const Key &key) { 00197 int index = find(key); 00198 if (index == -1) { 00199 return false; 00200 } 00201 remove_element(index); 00202 return true; 00203 } 00204 00205 //////////////////////////////////////////////////////////////////// 00206 // Function: SimpleHashMap::clear 00207 // Access: Public 00208 // Description: Completely empties the table. 00209 //////////////////////////////////////////////////////////////////// 00210 template<class Key, class Value, class Compare> 00211 void SimpleHashMap<Key, Value, Compare>:: 00212 clear() { 00213 if (_table_size != 0) { 00214 for (size_t i = 0; i < _table_size; ++i) { 00215 if (has_element(i)) { 00216 clear_element(i); 00217 } 00218 } 00219 00220 _deleted_chain->deallocate(_table, TypeHandle::none()); 00221 _table = NULL; 00222 _deleted_chain = NULL; 00223 _table_size = 0; 00224 _num_entries = 0; 00225 } 00226 } 00227 00228 //////////////////////////////////////////////////////////////////// 00229 // Function: SimpleHashMap::operator [] 00230 // Access: Public 00231 // Description: Returns a modifiable reference to the data associated 00232 // with the indicated key, or creates a new data entry 00233 // and returns its reference. 00234 //////////////////////////////////////////////////////////////////// 00235 template<class Key, class Value, class Compare> 00236 INLINE Value &SimpleHashMap<Key, Value, Compare>:: 00237 operator [] (const Key &key) { 00238 int index = find(key); 00239 if (index == -1) { 00240 index = store(key, Value()); 00241 } 00242 return modify_data(index); 00243 } 00244 00245 //////////////////////////////////////////////////////////////////// 00246 // Function: SimpleHashMap::get_size 00247 // Access: Public 00248 // Description: Returns the total number of slots in the table. 00249 //////////////////////////////////////////////////////////////////// 00250 template<class Key, class Value, class Compare> 00251 INLINE int SimpleHashMap<Key, Value, Compare>:: 00252 get_size() const { 00253 return _table_size; 00254 } 00255 00256 //////////////////////////////////////////////////////////////////// 00257 // Function: SimpleHashMap::has_element 00258 // Access: Public 00259 // Description: Returns true if there is an element stored in the nth 00260 // slot, false otherwise. 00261 // 00262 // n should be in the range 0 <= n < get_size(). 00263 //////////////////////////////////////////////////////////////////// 00264 template<class Key, class Value, class Compare> 00265 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00266 has_element(int n) const { 00267 nassertr(n >= 0 && n < (int)_table_size, false); 00268 return (get_exists_array()[n] != 0); 00269 } 00270 00271 //////////////////////////////////////////////////////////////////// 00272 // Function: SimpleHashMap::get_key 00273 // Access: Public 00274 // Description: Returns the key in the nth slot of the table. 00275 // 00276 // It is an error to call this if there is nothing 00277 // stored in the nth slot (use has_element() to check 00278 // this first). n should be in the range 0 <= n < 00279 // get_size(). 00280 //////////////////////////////////////////////////////////////////// 00281 template<class Key, class Value, class Compare> 00282 INLINE const Key &SimpleHashMap<Key, Value, Compare>:: 00283 get_key(int n) const { 00284 nassertr(has_element(n), _table[n]._key); 00285 return _table[n]._key; 00286 } 00287 00288 //////////////////////////////////////////////////////////////////// 00289 // Function: SimpleHashMap::get_data 00290 // Access: Public 00291 // Description: Returns the data in the nth slot of the table. 00292 // 00293 // It is an error to call this if there is nothing 00294 // stored in the nth slot (use has_element() to check 00295 // this first). n should be in the range 0 <= n < 00296 // get_size(). 00297 //////////////////////////////////////////////////////////////////// 00298 template<class Key, class Value, class Compare> 00299 INLINE const Value &SimpleHashMap<Key, Value, Compare>:: 00300 get_data(int n) const { 00301 nassertr(has_element(n), _table[n]._data); 00302 return _table[n]._data; 00303 } 00304 00305 //////////////////////////////////////////////////////////////////// 00306 // Function: SimpleHashMap::modify_data 00307 // Access: Public 00308 // Description: Returns a modifiable reference to the data in the nth 00309 // slot of the table. 00310 // 00311 // It is an error to call this if there is nothing 00312 // stored in the nth slot (use has_element() to check 00313 // this first). n should be in the range 0 <= n < 00314 // get_size(). 00315 //////////////////////////////////////////////////////////////////// 00316 template<class Key, class Value, class Compare> 00317 INLINE Value &SimpleHashMap<Key, Value, Compare>:: 00318 modify_data(int n) { 00319 nassertr(has_element(n), _table[n]._data); 00320 return _table[n]._data; 00321 } 00322 00323 //////////////////////////////////////////////////////////////////// 00324 // Function: SimpleHashMap::set_data 00325 // Access: Public 00326 // Description: Changes the data for the nth slot of the table. 00327 // 00328 // It is an error to call this if there is nothing 00329 // stored in the nth slot (use has_element() to check 00330 // this first). n should be in the range 0 <= n < 00331 // get_size(). 00332 //////////////////////////////////////////////////////////////////// 00333 template<class Key, class Value, class Compare> 00334 INLINE void SimpleHashMap<Key, Value, Compare>:: 00335 set_data(int n, const Value &data) { 00336 nassertv(has_element(n)); 00337 _table[n]._data = data; 00338 } 00339 00340 //////////////////////////////////////////////////////////////////// 00341 // Function: SimpleHashMap::remove_element 00342 // Access: Public 00343 // Description: Removes the nth slot from the table. 00344 // 00345 // It is an error to call this if there is nothing 00346 // stored in the nth slot (use has_element() to check 00347 // this first). n should be in the range 0 <= n < 00348 // get_size(). 00349 //////////////////////////////////////////////////////////////////// 00350 template<class Key, class Value, class Compare> 00351 void SimpleHashMap<Key, Value, Compare>:: 00352 remove_element(int n) { 00353 nassertv(has_element(n)); 00354 00355 clear_element(n); 00356 nassertv(_num_entries > 0); 00357 --_num_entries; 00358 00359 // Now we have put a hole in the table. If there was a hash 00360 // conflict in the slot following this one, we have to move it down 00361 // to close the hole. 00362 size_t i = n; 00363 i = (i + 1) & (_table_size - 1); 00364 while (has_element(i)) { 00365 size_t wants_index = get_hash(_table[i]._key); 00366 if (wants_index != i) { 00367 // This one was a hash conflict; try to put it where it belongs. 00368 // We can't just put it in n, since maybe it belongs somewhere 00369 // after n. 00370 while (wants_index != i && has_element(wants_index)) { 00371 wants_index = (wants_index + 1) & (_table_size - 1); 00372 } 00373 if (wants_index != i) { 00374 store_new_element(wants_index, _table[i]._key, _table[i]._data); 00375 clear_element(i); 00376 } 00377 } 00378 00379 // Continue until we encounter the next unused slot. Until we do, 00380 // we can't be sure we've found all of the potential hash 00381 // conflicts. 00382 i = (i + 1) & (_table_size - 1); 00383 } 00384 00385 #ifdef _DEBUG 00386 nassertv(validate()); 00387 #endif 00388 } 00389 00390 //////////////////////////////////////////////////////////////////// 00391 // Function: SimpleHashMap::get_num_entries 00392 // Access: Public 00393 // Description: Returns the number of active entries in the table. 00394 // This is not necessarily related to the number of 00395 // slots in the table as reported by get_size(). Use 00396 // get_size() to iterate through all of the slots, not 00397 // get_num_entries(). 00398 //////////////////////////////////////////////////////////////////// 00399 template<class Key, class Value, class Compare> 00400 INLINE int SimpleHashMap<Key, Value, Compare>:: 00401 get_num_entries() const { 00402 return _num_entries; 00403 } 00404 00405 //////////////////////////////////////////////////////////////////// 00406 // Function: SimpleHashMap::is_empty 00407 // Access: Public 00408 // Description: Returns true if the table is empty; 00409 // i.e. get_num_entries() == 0. 00410 //////////////////////////////////////////////////////////////////// 00411 template<class Key, class Value, class Compare> 00412 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00413 is_empty() const { 00414 return (_num_entries == 0); 00415 } 00416 00417 //////////////////////////////////////////////////////////////////// 00418 // Function: SimpleHashMap::output 00419 // Access: Public 00420 // Description: 00421 //////////////////////////////////////////////////////////////////// 00422 template<class Key, class Value, class Compare> 00423 void SimpleHashMap<Key, Value, Compare>:: 00424 output(ostream &out) const { 00425 out << "SimpleHashMap (" << _num_entries << " entries): ["; 00426 for (size_t i = 0; i < _table_size; ++i) { 00427 if (!has_element(i)) { 00428 out << " *"; 00429 00430 } else { 00431 out << " " << _table[i]._key; 00432 size_t index = get_hash(_table[i]._key); 00433 if (index != i) { 00434 // This was misplaced as the result of a hash conflict. 00435 // Report how far off it is. 00436 out << "(" << ((_table_size + i - index) & (_table_size - 1)) << ")"; 00437 } 00438 } 00439 } 00440 out << " ]"; 00441 } 00442 00443 //////////////////////////////////////////////////////////////////// 00444 // Function: SimpleHashMap::write 00445 // Access: Public 00446 // Description: 00447 //////////////////////////////////////////////////////////////////// 00448 template<class Key, class Value, class Compare> 00449 void SimpleHashMap<Key, Value, Compare>:: 00450 write(ostream &out) const { 00451 output(out); 00452 out << "\n"; 00453 } 00454 00455 //////////////////////////////////////////////////////////////////// 00456 // Function: SimpleHashMap::validate 00457 // Access: Public 00458 // Description: Returns true if the internal table appears to be 00459 // consistent, false if there are some internal errors. 00460 //////////////////////////////////////////////////////////////////// 00461 template<class Key, class Value, class Compare> 00462 bool SimpleHashMap<Key, Value, Compare>:: 00463 validate() const { 00464 size_t count = 0; 00465 00466 for (size_t i = 0; i < _table_size; ++i) { 00467 if (has_element(i)) { 00468 ++count; 00469 size_t ideal_index = get_hash(_table[i]._key); 00470 size_t wants_index = ideal_index; 00471 while (wants_index != i && has_element(wants_index)) { 00472 wants_index = (wants_index + 1) & (_table_size - 1); 00473 } 00474 if (wants_index != i) { 00475 util_cat.error() 00476 << "SimpleHashMap is invalid: key " << _table[i]._key 00477 << " should be in slot " << wants_index << " instead of " 00478 << i << " (ideal is " << ideal_index << ")\n"; 00479 write(util_cat.error(false)); 00480 return false; 00481 } 00482 } 00483 } 00484 00485 if (count != _num_entries) { 00486 util_cat.error() 00487 << "SimpleHashMap is invalid: reports " << _num_entries 00488 << " entries, actually has " << count << "\n"; 00489 write(util_cat.error(false)); 00490 return false; 00491 } 00492 00493 return true; 00494 } 00495 00496 //////////////////////////////////////////////////////////////////// 00497 // Function: SimpleHashMap::get_hash 00498 // Access: Private 00499 // Description: Computes an appropriate index number to store the 00500 // given pointer. 00501 //////////////////////////////////////////////////////////////////// 00502 template<class Key, class Value, class Compare> 00503 INLINE size_t SimpleHashMap<Key, Value, Compare>:: 00504 get_hash(const Key &key) const { 00505 /* 00506 // We want a hash constant 0 < k < 1. This one is suggested by 00507 // Knuth: 00508 static const double hash_constant = (sqrt(5.0) - 1.0) / 2.0; 00509 double f = ((double)_comp(key) * hash_constant); 00510 f -= floor(f); 00511 return (size_t)floor(f * _table_size); 00512 */ 00513 00514 return ((_comp(key) * (size_t)9973) >> 8) & (_table_size - 1); 00515 } 00516 00517 //////////////////////////////////////////////////////////////////// 00518 // Function: SimpleHashMap::is_element 00519 // Access: Private 00520 // Description: Returns true if element n matches key. 00521 //////////////////////////////////////////////////////////////////// 00522 template<class Key, class Value, class Compare> 00523 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00524 is_element(int n, const Key &key) const { 00525 nassertr(has_element(n), false); 00526 return _comp.is_equal(_table[n]._key, key); 00527 } 00528 00529 //////////////////////////////////////////////////////////////////// 00530 // Function: SimpleHashMap::store_new_element 00531 // Access: Private 00532 // Description: Constructs a new TableEntry at position n, storing 00533 // the indicated key and value. 00534 //////////////////////////////////////////////////////////////////// 00535 template<class Key, class Value, class Compare> 00536 INLINE void SimpleHashMap<Key, Value, Compare>:: 00537 store_new_element(int n, const Key &key, const Value &data) { 00538 new(&_table[n]) TableEntry(key, data); 00539 get_exists_array()[n] = true; 00540 } 00541 00542 //////////////////////////////////////////////////////////////////// 00543 // Function: SimpleHashMap::clear_element 00544 // Access: Private 00545 // Description: Destructs the TableEntry at position n. 00546 //////////////////////////////////////////////////////////////////// 00547 template<class Key, class Value, class Compare> 00548 INLINE void SimpleHashMap<Key, Value, Compare>:: 00549 clear_element(int n) { 00550 _table[n].~TableEntry(); 00551 get_exists_array()[n] = false; 00552 } 00553 00554 //////////////////////////////////////////////////////////////////// 00555 // Function: SimpleHashMap::get_exists_array 00556 // Access: Private 00557 // Description: Returns the beginning of the array of _table_size 00558 // unsigned chars that are the boolean flags for whether 00559 // each element exists (has been constructed) within the 00560 // table. 00561 //////////////////////////////////////////////////////////////////// 00562 template<class Key, class Value, class Compare> 00563 INLINE unsigned char *SimpleHashMap<Key, Value, Compare>:: 00564 get_exists_array() const { 00565 return (unsigned char *)(_table + _table_size); 00566 } 00567 00568 //////////////////////////////////////////////////////////////////// 00569 // Function: SimpleHashMap::new_table 00570 // Access: Private 00571 // Description: Allocates a brand new table. 00572 //////////////////////////////////////////////////////////////////// 00573 template<class Key, class Value, class Compare> 00574 void SimpleHashMap<Key, Value, Compare>:: 00575 new_table() { 00576 nassertv(_table_size == 0 && _num_entries == 0); 00577 00578 // Pick a good initial table size. For now, we make it as small as 00579 // possible. Maybe that's the right answer. 00580 _table_size = 2; 00581 00582 // We allocate enough bytes for _table_size elements of TableEntry, 00583 // plus _table_size more bytes at the end (for the exists array). 00584 size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size; 00585 00586 _deleted_chain = memory_hook->get_deleted_chain(alloc_size); 00587 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none()); 00588 memset(get_exists_array(), 0, _table_size); 00589 } 00590 00591 //////////////////////////////////////////////////////////////////// 00592 // Function: SimpleHashMap::consider_expand_table 00593 // Access: Private 00594 // Description: Expands the table if it will need it (assuming one 00595 // more element is about to be added). Returns true if 00596 // expanded, false otherwise. 00597 //////////////////////////////////////////////////////////////////// 00598 template<class Key, class Value, class Compare> 00599 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00600 consider_expand_table() { 00601 if (_num_entries >= (_table_size >> 1)) { 00602 expand_table(); 00603 return true; 00604 } 00605 return false; 00606 } 00607 00608 //////////////////////////////////////////////////////////////////// 00609 // Function: SimpleHashMap::expand_table 00610 // Access: Private 00611 // Description: Doubles the size of the existing table. 00612 //////////////////////////////////////////////////////////////////// 00613 template<class Key, class Value, class Compare> 00614 void SimpleHashMap<Key, Value, Compare>:: 00615 expand_table() { 00616 nassertv(_table_size != 0); 00617 00618 SimpleHashMap<Key, Value, Compare> old_map(_comp); 00619 swap(old_map); 00620 00621 _table_size = (old_map._table_size << 1); 00622 nassertv(_table == NULL); 00623 00624 // We allocate enough bytes for _table_size elements of TableEntry, 00625 // plus _table_size more bytes at the end (for the exists array). 00626 size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size; 00627 _deleted_chain = memory_hook->get_deleted_chain(alloc_size); 00628 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none()); 00629 memset(get_exists_array(), 0, _table_size); 00630 nassertv(_num_entries == 0); 00631 00632 // Now copy the entries from the old table into the new table. 00633 int num_added = 0; 00634 for (size_t i = 0; i < old_map._table_size; ++i) { 00635 if (old_map.has_element(i)) { 00636 store(old_map._table[i]._key, old_map._table[i]._data); 00637 ++num_added; 00638 } 00639 } 00640 00641 nassertv(validate()); 00642 nassertv(old_map.validate()); 00643 00644 nassertv(_num_entries == old_map._num_entries); 00645 }