Panda3D

simpleHashMap.I

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 }
 All Classes Functions Variables Enumerations