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