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 a reference to the value in the map. 00115 //////////////////////////////////////////////////////////////////// 00116 template<class Key, class Value, class Compare> 00117 Value &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, _table[0]._data); 00122 new_table(); 00123 size_t index = get_hash(key); 00124 store_new_element(index, key, data); 00125 ++_num_entries; 00126 return _table[index]._data; 00127 } 00128 00129 size_t index = get_hash(key); 00130 if (!has_element(index)) { 00131 if (consider_expand_table()) { 00132 return store(key, data); 00133 } 00134 store_new_element(index, key, data); 00135 ++_num_entries; 00136 return _table[index]._data; 00137 } 00138 if (is_element(index, key)) { 00139 _table[index]._data = data; 00140 return _table[index]._data; 00141 } 00142 00143 // There was some other key at the hashed slot. That's a hash 00144 // conflict. Record this entry at a later position. 00145 size_t i = index; 00146 i = (i + 1) & (_table_size - 1); 00147 while (i != index) { 00148 if (!has_element(i)) { 00149 if (consider_expand_table()) { 00150 return store(key, data); 00151 } 00152 store_new_element(i, key, data); 00153 ++_num_entries; 00154 return _table[i]._data; 00155 } 00156 if (is_element(i, key)) { 00157 _table[i]._data = data; 00158 return _table[i]._data; 00159 } 00160 i = (i + 1) & (_table_size - 1); 00161 } 00162 00163 // Shouldn't get here unless _num_entries == _table_size, which 00164 // shouldn't be possible due to consider_expand_table(). 00165 nassertr(false, _table[0]._data); 00166 return _table[0]._data; // To satisfy compiler 00167 } 00168 00169 //////////////////////////////////////////////////////////////////// 00170 // Function: SimpleHashMap::remove 00171 // Access: Public 00172 // Description: Removes the indicated key and its associated data 00173 // from the table. Returns true if the key was removed, 00174 // false if it was not present. 00175 //////////////////////////////////////////////////////////////////// 00176 template<class Key, class Value, class Compare> 00177 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00178 remove(const Key &key) { 00179 int index = find(key); 00180 if (index == -1) { 00181 return false; 00182 } 00183 remove_element(index); 00184 return true; 00185 } 00186 00187 //////////////////////////////////////////////////////////////////// 00188 // Function: SimpleHashMap::clear 00189 // Access: Public 00190 // Description: Completely empties the table. 00191 //////////////////////////////////////////////////////////////////// 00192 template<class Key, class Value, class Compare> 00193 void SimpleHashMap<Key, Value, Compare>:: 00194 clear() { 00195 if (_table_size != 0) { 00196 for (size_t i = 0; i < _table_size; ++i) { 00197 if (has_element(i)) { 00198 clear_element(i); 00199 } 00200 } 00201 00202 _deleted_chain->deallocate(_table, TypeHandle::none()); 00203 _table = NULL; 00204 _deleted_chain = NULL; 00205 _table_size = 0; 00206 _num_entries = 0; 00207 } 00208 } 00209 00210 //////////////////////////////////////////////////////////////////// 00211 // Function: SimpleHashMap::operator [] 00212 // Access: Public 00213 // Description: Returns a modifiable reference to the data associated 00214 // with the indicated key, or creates a new data entry 00215 // and returns its reference. 00216 //////////////////////////////////////////////////////////////////// 00217 template<class Key, class Value, class Compare> 00218 INLINE Value &SimpleHashMap<Key, Value, Compare>:: 00219 operator [] (const Key &key) { 00220 int index = find(key); 00221 if (index != -1) { 00222 return modify_data(index); 00223 } 00224 return store(key, Value()); 00225 } 00226 00227 //////////////////////////////////////////////////////////////////// 00228 // Function: SimpleHashMap::get_size 00229 // Access: Public 00230 // Description: Returns the total number of slots in the table. 00231 //////////////////////////////////////////////////////////////////// 00232 template<class Key, class Value, class Compare> 00233 INLINE int SimpleHashMap<Key, Value, Compare>:: 00234 get_size() const { 00235 return _table_size; 00236 } 00237 00238 //////////////////////////////////////////////////////////////////// 00239 // Function: SimpleHashMap::has_element 00240 // Access: Public 00241 // Description: Returns true if there is an element stored in the nth 00242 // slot, false otherwise. 00243 // 00244 // n should be in the range 0 <= n < get_size(). 00245 //////////////////////////////////////////////////////////////////// 00246 template<class Key, class Value, class Compare> 00247 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00248 has_element(int n) const { 00249 nassertr(n >= 0 && n < (int)_table_size, false); 00250 return (get_exists_array()[n] != 0); 00251 } 00252 00253 //////////////////////////////////////////////////////////////////// 00254 // Function: SimpleHashMap::get_key 00255 // Access: Public 00256 // Description: Returns the key in the nth slot of the table. 00257 // 00258 // It is an error to call this if there is nothing 00259 // stored in the nth slot (use has_element() to check 00260 // this first). n should be in the range 0 <= n < 00261 // get_size(). 00262 //////////////////////////////////////////////////////////////////// 00263 template<class Key, class Value, class Compare> 00264 INLINE const Key &SimpleHashMap<Key, Value, Compare>:: 00265 get_key(int n) const { 00266 nassertr(has_element(n), _table[n]._key); 00267 return _table[n]._key; 00268 } 00269 00270 //////////////////////////////////////////////////////////////////// 00271 // Function: SimpleHashMap::get_data 00272 // Access: Public 00273 // Description: Returns the data in the nth slot of the table. 00274 // 00275 // It is an error to call this if there is nothing 00276 // stored in the nth slot (use has_element() to check 00277 // this first). n should be in the range 0 <= n < 00278 // get_size(). 00279 //////////////////////////////////////////////////////////////////// 00280 template<class Key, class Value, class Compare> 00281 INLINE const Value &SimpleHashMap<Key, Value, Compare>:: 00282 get_data(int n) const { 00283 nassertr(has_element(n), _table[n]._data); 00284 return _table[n]._data; 00285 } 00286 00287 //////////////////////////////////////////////////////////////////// 00288 // Function: SimpleHashMap::modify_data 00289 // Access: Public 00290 // Description: Returns a modifiable reference to the data in the nth 00291 // 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 Value &SimpleHashMap<Key, Value, Compare>:: 00300 modify_data(int n) { 00301 nassertr(has_element(n), _table[n]._data); 00302 return _table[n]._data; 00303 } 00304 00305 //////////////////////////////////////////////////////////////////// 00306 // Function: SimpleHashMap::set_data 00307 // Access: Public 00308 // Description: Changes the data for the nth slot of the table. 00309 // 00310 // It is an error to call this if there is nothing 00311 // stored in the nth slot (use has_element() to check 00312 // this first). n should be in the range 0 <= n < 00313 // get_size(). 00314 //////////////////////////////////////////////////////////////////// 00315 template<class Key, class Value, class Compare> 00316 INLINE void SimpleHashMap<Key, Value, Compare>:: 00317 set_data(int n, const Value &data) { 00318 nassertv(has_element(n)); 00319 _table[n]._data = data; 00320 } 00321 00322 //////////////////////////////////////////////////////////////////// 00323 // Function: SimpleHashMap::remove_element 00324 // Access: Public 00325 // Description: Removes the nth slot from the table. 00326 // 00327 // It is an error to call this if there is nothing 00328 // stored in the nth slot (use has_element() to check 00329 // this first). n should be in the range 0 <= n < 00330 // get_size(). 00331 //////////////////////////////////////////////////////////////////// 00332 template<class Key, class Value, class Compare> 00333 void SimpleHashMap<Key, Value, Compare>:: 00334 remove_element(int n) { 00335 nassertv(has_element(n)); 00336 00337 clear_element(n); 00338 nassertv(_num_entries > 0); 00339 --_num_entries; 00340 00341 // Now we have put a hole in the table. If there was a hash 00342 // conflict in the slot following this one, we have to move it down 00343 // to close the hole. 00344 size_t i = n; 00345 i = (i + 1) & (_table_size - 1); 00346 while (has_element(i)) { 00347 size_t wants_index = get_hash(_table[i]._key); 00348 if (wants_index != i) { 00349 // This one was a hash conflict; try to put it where it belongs. 00350 // We can't just put it in n, since maybe it belongs somewhere 00351 // after n. 00352 while (wants_index != i && has_element(wants_index)) { 00353 wants_index = (wants_index + 1) & (_table_size - 1); 00354 } 00355 if (wants_index != i) { 00356 store_new_element(wants_index, _table[i]._key, _table[i]._data); 00357 clear_element(i); 00358 } 00359 } 00360 00361 // Continue until we encounter the next unused slot. Until we do, 00362 // we can't be sure we've found all of the potential hash 00363 // conflicts. 00364 i = (i + 1) & (_table_size - 1); 00365 } 00366 } 00367 00368 //////////////////////////////////////////////////////////////////// 00369 // Function: SimpleHashMap::get_num_entries 00370 // Access: Public 00371 // Description: Returns the number of active entries in the table. 00372 // This is not necessarily related to the number of 00373 // slots in the table as reported by get_size(). Use 00374 // get_size() to iterate through all of the slots, not 00375 // get_num_entries(). 00376 //////////////////////////////////////////////////////////////////// 00377 template<class Key, class Value, class Compare> 00378 INLINE int SimpleHashMap<Key, Value, Compare>:: 00379 get_num_entries() const { 00380 return _num_entries; 00381 } 00382 00383 //////////////////////////////////////////////////////////////////// 00384 // Function: SimpleHashMap::is_empty 00385 // Access: Public 00386 // Description: Returns true if the table is empty; 00387 // i.e. get_num_entries() == 0. 00388 //////////////////////////////////////////////////////////////////// 00389 template<class Key, class Value, class Compare> 00390 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00391 is_empty() const { 00392 return (_num_entries == 0); 00393 } 00394 00395 //////////////////////////////////////////////////////////////////// 00396 // Function: SimpleHashMap::output 00397 // Access: Public 00398 // Description: 00399 //////////////////////////////////////////////////////////////////// 00400 template<class Key, class Value, class Compare> 00401 void SimpleHashMap<Key, Value, Compare>:: 00402 output(ostream &out) const { 00403 out << "SimpleHashMap (" << _num_entries << " entries): ["; 00404 for (size_t i = 0; i < _table_size; ++i) { 00405 if (!has_element(i)) { 00406 out << " *"; 00407 00408 } else { 00409 out << " " << _table[i]._key; 00410 size_t index = get_hash(_table[i]._key); 00411 if (index != i) { 00412 // This was misplaced as the result of a hash conflict. 00413 // Report how far off it is. 00414 out << "(" << ((_table_size + i - index) & (_table_size - 1)) << ")"; 00415 } 00416 } 00417 } 00418 out << " ]"; 00419 } 00420 00421 //////////////////////////////////////////////////////////////////// 00422 // Function: SimpleHashMap::write 00423 // Access: Public 00424 // Description: 00425 //////////////////////////////////////////////////////////////////// 00426 template<class Key, class Value, class Compare> 00427 void SimpleHashMap<Key, Value, Compare>:: 00428 write(ostream &out) const { 00429 output(out); 00430 out << "\n"; 00431 } 00432 00433 //////////////////////////////////////////////////////////////////// 00434 // Function: SimpleHashMap::validate 00435 // Access: Public 00436 // Description: Returns true if the internal table appears to be 00437 // consistent, false if there are some internal errors. 00438 //////////////////////////////////////////////////////////////////// 00439 template<class Key, class Value, class Compare> 00440 bool SimpleHashMap<Key, Value, Compare>:: 00441 validate() const { 00442 size_t count = 0; 00443 00444 for (size_t i = 0; i < _table_size; ++i) { 00445 if (has_element(i)) { 00446 ++count; 00447 size_t ideal_index = get_hash(_table[i]._key); 00448 size_t wants_index = ideal_index; 00449 while (wants_index != i && has_element(wants_index)) { 00450 wants_index = (wants_index + 1) & (_table_size - 1); 00451 } 00452 if (wants_index != i) { 00453 util_cat.error() 00454 << "SimpleHashMap is invalid: key " << _table[i]._key 00455 << " should be in slot " << wants_index << " instead of " 00456 << i << " (ideal is " << ideal_index << ")\n"; 00457 write(util_cat.error(false)); 00458 return false; 00459 } 00460 } 00461 } 00462 00463 if (count != _num_entries) { 00464 util_cat.error() 00465 << "SimpleHashMap is invalid: reports " << _num_entries 00466 << " entries, actually has " << count << "\n"; 00467 write(util_cat.error(false)); 00468 return false; 00469 } 00470 00471 return true; 00472 } 00473 00474 //////////////////////////////////////////////////////////////////// 00475 // Function: SimpleHashMap::get_hash 00476 // Access: Private 00477 // Description: Computes an appropriate index number to store the 00478 // given pointer. 00479 //////////////////////////////////////////////////////////////////// 00480 template<class Key, class Value, class Compare> 00481 INLINE size_t SimpleHashMap<Key, Value, Compare>:: 00482 get_hash(const Key &key) const { 00483 /* 00484 // We want a hash constant 0 < k < 1. This one is suggested by 00485 // Knuth: 00486 static const double hash_constant = (sqrt(5.0) - 1.0) / 2.0; 00487 double f = ((double)_comp(key) * hash_constant); 00488 f -= floor(f); 00489 return (size_t)floor(f * _table_size); 00490 */ 00491 00492 return ((_comp(key) * (size_t)9973) >> 8) & (_table_size - 1); 00493 } 00494 00495 //////////////////////////////////////////////////////////////////// 00496 // Function: SimpleHashMap::is_element 00497 // Access: Private 00498 // Description: Returns true if element n matches key. 00499 //////////////////////////////////////////////////////////////////// 00500 template<class Key, class Value, class Compare> 00501 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00502 is_element(int n, const Key &key) const { 00503 nassertr(has_element(n), false); 00504 return _comp.is_equal(_table[n]._key, key); 00505 } 00506 00507 //////////////////////////////////////////////////////////////////// 00508 // Function: SimpleHashMap::store_new_element 00509 // Access: Private 00510 // Description: Constructs a new TableEntry at position n, storing 00511 // the indicated key and value. 00512 //////////////////////////////////////////////////////////////////// 00513 template<class Key, class Value, class Compare> 00514 INLINE void SimpleHashMap<Key, Value, Compare>:: 00515 store_new_element(int n, const Key &key, const Value &data) { 00516 new(&_table[n]) TableEntry(key, data); 00517 get_exists_array()[n] = true; 00518 } 00519 00520 //////////////////////////////////////////////////////////////////// 00521 // Function: SimpleHashMap::clear_element 00522 // Access: Private 00523 // Description: Destructs the TableEntry at position n. 00524 //////////////////////////////////////////////////////////////////// 00525 template<class Key, class Value, class Compare> 00526 INLINE void SimpleHashMap<Key, Value, Compare>:: 00527 clear_element(int n) { 00528 _table[n].~TableEntry(); 00529 get_exists_array()[n] = false; 00530 } 00531 00532 //////////////////////////////////////////////////////////////////// 00533 // Function: SimpleHashMap::get_exists_array 00534 // Access: Private 00535 // Description: Returns the beginning of the array of _table_size 00536 // unsigned chars that are the boolean flags for whether 00537 // each element exists (has been constructed) within the 00538 // table. 00539 //////////////////////////////////////////////////////////////////// 00540 template<class Key, class Value, class Compare> 00541 INLINE unsigned char *SimpleHashMap<Key, Value, Compare>:: 00542 get_exists_array() const { 00543 return (unsigned char *)(_table + _table_size); 00544 } 00545 00546 //////////////////////////////////////////////////////////////////// 00547 // Function: SimpleHashMap::new_table 00548 // Access: Private 00549 // Description: Allocates a brand new table. 00550 //////////////////////////////////////////////////////////////////// 00551 template<class Key, class Value, class Compare> 00552 void SimpleHashMap<Key, Value, Compare>:: 00553 new_table() { 00554 nassertv(_table_size == 0 && _num_entries == 0); 00555 00556 // Pick a good initial table size. For now, we make it as small as 00557 // possible. Maybe that's the right answer. 00558 _table_size = 2; 00559 00560 // We allocate enough bytes for _table_size elements of TableEntry, 00561 // plus _table_size more bytes at the end (for the exists array). 00562 size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size; 00563 00564 _deleted_chain = memory_hook->get_deleted_chain(alloc_size); 00565 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none()); 00566 memset(get_exists_array(), 0, _table_size); 00567 } 00568 00569 //////////////////////////////////////////////////////////////////// 00570 // Function: SimpleHashMap::consider_expand_table 00571 // Access: Private 00572 // Description: Expands the table if it will need it (assuming one 00573 // more element is about to be added). Returns true if 00574 // expanded, false otherwise. 00575 //////////////////////////////////////////////////////////////////// 00576 template<class Key, class Value, class Compare> 00577 INLINE bool SimpleHashMap<Key, Value, Compare>:: 00578 consider_expand_table() { 00579 if (_num_entries >= (_table_size >> 1)) { 00580 expand_table(); 00581 return true; 00582 } 00583 return false; 00584 } 00585 00586 //////////////////////////////////////////////////////////////////// 00587 // Function: SimpleHashMap::expand_table 00588 // Access: Private 00589 // Description: Doubles the size of the existing table. 00590 //////////////////////////////////////////////////////////////////// 00591 template<class Key, class Value, class Compare> 00592 void SimpleHashMap<Key, Value, Compare>:: 00593 expand_table() { 00594 nassertv(_table_size != 0); 00595 00596 SimpleHashMap<Key, Value, Compare> old_map(_comp); 00597 swap(old_map); 00598 00599 _table_size = (old_map._table_size << 1); 00600 nassertv(_table == NULL); 00601 00602 // We allocate enough bytes for _table_size elements of TableEntry, 00603 // plus _table_size more bytes at the end (for the exists array). 00604 size_t alloc_size = _table_size * sizeof(TableEntry) + _table_size; 00605 _deleted_chain = memory_hook->get_deleted_chain(alloc_size); 00606 _table = (TableEntry *)_deleted_chain->allocate(alloc_size, TypeHandle::none()); 00607 memset(get_exists_array(), 0, _table_size); 00608 00609 // Now copy the entries from the old table into the new table. 00610 for (size_t i = 0; i < old_map._table_size; ++i) { 00611 if (old_map.has_element(i)) { 00612 store(old_map._table[i]._key, old_map._table[i]._data); 00613 } 00614 } 00615 00616 nassertv(old_map._num_entries == _num_entries); 00617 }