00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
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
00034
00035
00036
00037 template<class Key, class Value, class Compare>
00038 INLINE SimpleHashMap<Key, Value, Compare>::
00039 ~SimpleHashMap() {
00040 clear();
00041 }
00042
00043
00044
00045
00046
00047
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
00071
00072
00073
00074
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
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
00093
00094
00095
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
00106 return -1;
00107 }
00108
00109
00110
00111
00112
00113
00114
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
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
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
00147
00148 _table[index]._data = data;
00149 #ifdef _DEBUG
00150 nassertr(validate(), index);
00151 #endif
00152 return index;
00153 }
00154
00155
00156
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
00182
00183 nassertr(false, -1);
00184 return -1;
00185 }
00186
00187
00188
00189
00190
00191
00192
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
00207
00208
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
00230
00231
00232
00233
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
00247
00248
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
00258
00259
00260
00261
00262
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
00273
00274
00275
00276
00277
00278
00279
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
00290
00291
00292
00293
00294
00295
00296
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
00307
00308
00309
00310
00311
00312
00313
00314
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
00325
00326
00327
00328
00329
00330
00331
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
00342
00343
00344
00345
00346
00347
00348
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
00360
00361
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
00368
00369
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
00380
00381
00382 i = (i + 1) & (_table_size - 1);
00383 }
00384
00385 #ifdef _DEBUG
00386 nassertv(validate());
00387 #endif
00388 }
00389
00390
00391
00392
00393
00394
00395
00396
00397
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
00407
00408
00409
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
00419
00420
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
00435
00436 out << "(" << ((_table_size + i - index) & (_table_size - 1)) << ")";
00437 }
00438 }
00439 }
00440 out << " ]";
00441 }
00442
00443
00444
00445
00446
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
00457
00458
00459
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
00498
00499
00500
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
00507
00508
00509
00510
00511
00512
00513
00514 return ((_comp(key) * (size_t)9973) >> 8) & (_table_size - 1);
00515 }
00516
00517
00518
00519
00520
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
00531
00532
00533
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
00544
00545
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
00556
00557
00558
00559
00560
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
00570
00571
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
00579
00580 _table_size = 2;
00581
00582
00583
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
00593
00594
00595
00596
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
00610
00611
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
00625
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
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 }