00001
00003 #ifndef __gdtmap__
00004 #define __gdtmap__
00005
00006 #include <iostream>
00007 #include <assert.h>
00008 #include <math.h>
00009
00010 #include "ptr.h"
00011
00012 #define MIN_TABLE_SIZE 2
00013 #define UPPER_THRESHOLD 1.28
00014
00015
00016 #define HASH_POINTER_SHIFT 4
00017
00018
00019
00020 namespace gdt {
00021
00022 #ifdef __x86_64__
00023 inline int Hash(void* p){return int((long long)(p)>> HASH_POINTER_SHIFT);};
00024 #else
00025
00026 #ifdef GDTWRAPPER_EXPORTS
00027 inline int Hash(void* p){return int((long long)(p)>> HASH_POINTER_SHIFT);};
00028 #else
00029 inline int Hash(void* p){return int((long)(p)>> HASH_POINTER_SHIFT);};
00030
00031 #endif
00032 #endif
00033
00034 inline int Hash(int p){return p;};
00035
00036 int gdtceil(double f);
00037
00038 template<class Key, class Value>
00039 class gdtmap {
00040
00041 private:
00042
00043 struct Rec {
00044 bool used;
00045 Key key;
00046 Ptr ptr;
00047 Rec *next;
00048 };
00049
00050
00051 Value xdef;
00052
00053
00054 unsigned long table_size;
00055 unsigned long table_size_1;
00056
00057
00058 unsigned long extra_size;
00059
00060
00061 unsigned long number_of_entries;
00062
00063
00064
00065 unsigned long max_number_of_entries;
00066
00067
00068 Rec* table;
00069 Rec* extra;
00070 Rec* end;
00071
00072
00073 void double_table();
00074
00075
00076
00077 inline Rec* get_free_slot();
00078
00079 inline bool no_more_slots() const;
00080
00081
00082
00083
00084
00085
00086 inline Rec* simple_add_entry(const Key& key, const Value& value, Rec *rec);
00087
00088 inline Rec* reinsert_entry(const Key& key, Ptr& ptr, Rec *rec);
00089
00090 inline Rec* add_entry(Rec * prec, const Key& key, const Value& value);
00091
00092 inline Rec* find_key(Rec *first, const Key& key) const;
00093
00094
00095 inline Rec* HASH(Key key) const;
00096
00097 inline double load_factor() const;
00098
00099 void copy(const gdtmap<Key,Value>& M);
00100
00101 protected:
00102
00103 void init_table(unsigned long size = MIN_TABLE_SIZE);
00104
00105 void delete_table();
00106
00107 void set_default(Value x);
00108
00109 public:
00110
00111 bool consistency_check();
00112
00113 typedef void* item;
00114
00115 void show(std::ostream& os) const;
00116
00117
00118
00119
00120
00121
00122
00123 gdtmap();
00124
00125 gdtmap(Value x);
00126
00127 gdtmap(Value x, unsigned long table_sz);
00128
00129 gdtmap<Key,Value>& operator = (const gdtmap<Key,Value>& M);
00130
00131 gdtmap(const gdtmap<Key,Value>& M);
00132
00133 ~gdtmap();
00134
00135
00136
00137
00138
00139
00140
00141 inline const Value& operator[](const Key& key) const;
00142
00143 inline Value& operator[](const Key& key);
00144
00145 bool defined(const Key& key) const;
00146
00147 void undefine(const Key& key);
00148
00149 void clear();
00150
00151 void clear(Value x);
00152
00153 void statistics() const;
00154
00155
00156
00157
00158
00159
00160
00161 item first_item() const;
00162
00163 item next_item(item _it) const;
00164
00165 Key key(item _it) const;
00166
00167 inline Value& inf(item _it) const;
00168 };
00169
00170 template <class Key, class Value>
00171 void gdtmap<Key,Value>::double_table() {
00172
00173 assert(table_size > 0 && extra_size > 0);
00174
00175
00176 Rec* old_table = table;
00177 Rec* old_end = end;
00178 unsigned long old_table_size = table_size;
00179 unsigned long old_extra_size = extra_size;
00180
00181
00182 table = new Rec[ old_table_size * 2 + old_extra_size * 2];
00183
00184
00185 table_size = old_table_size * 2;
00186 table_size_1 = table_size - 1;
00187 extra_size = old_extra_size * 2;
00188 max_number_of_entries = (unsigned long)floor(table_size * UPPER_THRESHOLD);
00189
00190 extra = table + table_size;
00191 end = extra + extra_size;
00192
00193
00194 Rec *it;
00195 for (it = table; it < end; ++it) {
00196 it->used = false;
00197 }
00198
00199
00200 for (it = old_table; it < old_end; ++it) {
00201 if (it->used)
00202 reinsert_entry(it->key, it->ptr, HASH(it->key));
00203 }
00204
00205
00206 delete [] old_table;
00207
00208 assert(consistency_check());
00209 }
00210
00211 template <class Key, class Value>
00212 inline bool gdtmap<Key,Value>::no_more_slots() const {
00213 return extra == end;
00214 }
00215
00216
00217
00218 template <class Key, class Value>
00219 inline typename gdtmap<Key,Value>::Rec* gdtmap<Key,Value>::get_free_slot() {
00220 assert(extra != end);
00221 return extra++;
00222 }
00223
00224
00225
00226
00227
00228
00229
00230
00231 template <class Key, class Value>
00232 inline typename gdtmap<Key,Value>::Rec* gdtmap<Key,Value>::simple_add_entry(const Key& key, const Value& value, Rec *rec) {
00233
00234 if (rec->used) {
00235 Rec * old_second = rec->next;
00236 Rec * new_rec = get_free_slot();
00237 rec->next = new_rec;
00238 new_rec->used = true;
00239 new_rec->key = key;
00240 new_rec->ptr = ptr_copy(value);
00241 new_rec->next = old_second;
00242 return new_rec;
00243 }
00244 else {
00245 rec->used = true;
00246 rec->key = key;
00247 rec->ptr = ptr_copy(value);
00248 rec->next = NULL;
00249 return rec;
00250 }
00251
00252
00253 }
00254
00255 template <class Key, class Value>
00256 inline typename gdtmap<Key,Value>::Rec* gdtmap<Key,Value>::reinsert_entry(const Key& key, Ptr& ptr, Rec *rec) {
00257
00258 if (rec->used) {
00259 Rec * old_second = rec->next;
00260 Rec * new_rec = get_free_slot();
00261 rec->next = new_rec;
00262 new_rec->used = true;
00263 new_rec->key = key;
00264 new_rec->ptr = ptr;
00265 new_rec->next = old_second;
00266 return new_rec;
00267 }
00268 else {
00269 rec->used = true;
00270 rec->key = key;
00271 rec->ptr = ptr;
00272 rec->next = NULL;
00273 return rec;
00274 }
00275
00276
00277 }
00278
00279 template <class Key, class Value>
00280 inline typename gdtmap<Key,Value>::Rec* gdtmap<Key,Value>::add_entry(Rec * prec, const Key& key, const Value& value) {
00281
00282 Rec* res;
00283
00284 if (number_of_entries > max_number_of_entries) {
00285 double_table();
00286 res = simple_add_entry(key, value, HASH(key));
00287 }
00288 else {
00289 if (prec->used && no_more_slots()) {
00290 double_table();
00291 res = simple_add_entry(key, value, HASH(key));
00292 }
00293 else {
00294 res = simple_add_entry(key, value, prec);
00295 }
00296 }
00297 ++number_of_entries;
00298
00299 assert(consistency_check());
00300 return res;
00301 }
00302
00303 template <class Key, class Value>
00304 inline typename gdtmap<Key,Value>::Rec* gdtmap<Key,Value>::find_key(Rec *first, const Key& key) const {
00305 assert(first && first >= table && first < (table + table_size));
00306 if (first->used) {
00307 Rec *it = first;
00308 while (it && it->key != key) {
00309 assert(it >= table && it < end);
00310 it = it->next;
00311 }
00312 assert((it && it->key == key) || !it);
00313 return it;
00314 }
00315 else
00316 return NULL;
00317 }
00318
00319
00320 template <class Key, class Value>
00321 inline typename gdtmap<Key,Value>::Rec* gdtmap<Key,Value>::HASH(Key key) const {
00322 Rec* res = table + (((unsigned long) Hash(key)) & table_size_1);
00323 assert(res < table + table_size);
00324 return res;
00325 }
00326
00327 template <class Key, class Value>
00328 inline double gdtmap<Key,Value>::load_factor() const {
00329 return (double) (number_of_entries + 1) / table_size;
00330 }
00331
00332 template <class Key, class Value>
00333 void gdtmap<Key,Value>::copy(const gdtmap<Key,Value>& M) {
00334
00335 assert(table);
00336
00337
00338
00339
00340
00341
00342 Rec* itM = M.table;
00343
00344 Rec* it = table;
00345 for (; it < end; ++it, ++itM) {
00346 assert(itM < M.end);
00347 if (itM->used) {
00348 ++number_of_entries;
00349
00350 it->used = true;
00351 it->key = itM->key;
00352 it->ptr = ptr_copy(PTR_ACCESS(Value,itM->ptr));
00353 it->next = itM->next ? (itM->next - M.table) + table : NULL;
00354 }
00355 }
00356
00357
00358 extra = (M.extra - M.table) + table;
00359 xdef = M.xdef;
00360
00361 assert(consistency_check());
00362 }
00363
00364 template <class Key, class Value>
00365 void gdtmap<Key,Value>::init_table(unsigned long size) {
00366
00367
00368 size = size > MIN_TABLE_SIZE ? size : MIN_TABLE_SIZE;
00369
00371
00372
00374
00375 size = 1 << (int) (gdtceil(log10(double(size))/log10(2.)));
00376
00377
00378 table_size = size;
00379 table_size_1 = table_size - 1;
00380 extra_size = size / 2;
00381
00382 table = new Rec[table_size + extra_size];
00383 assert(table);
00384
00385 number_of_entries = 0;
00386 max_number_of_entries = (unsigned long) floor((double) size * UPPER_THRESHOLD);
00387
00388 unsigned long all_size = table_size + extra_size;
00389 for (unsigned long i = 0; i < all_size; ++i) {
00390 table[i].used = false;
00391 }
00392
00393
00394 extra = table + table_size;
00395
00396
00397 end = extra + extra_size;
00398
00399 assert(consistency_check());
00400
00401 }
00402
00403 template <class Key, class Value>
00404 void gdtmap<Key,Value>::delete_table() {
00405 if (table) {
00406 for (Rec* rec = table; rec < end; ++rec) {
00407 if (rec->used) PTR_DELETE(Value, rec->ptr);
00408 }
00409 delete [] table;
00410 table = NULL;
00411 }
00412 }
00413
00414 template <class Key, class Value>
00415 void gdtmap<Key,Value>::set_default(Value x) {
00416 xdef = x;
00417 }
00418
00419 template <class Key, class Value>
00420 bool gdtmap<Key,Value>::consistency_check() {
00421 assert(table);
00422 if (table_size < 0)
00423 std::cout << "table_size < 0" << std::endl;
00424 assert(table_size_1 == table_size - 1);
00425 assert(extra_size > 0);
00426 assert(table + table_size + extra_size == end);
00427 return true;
00428 }
00429
00430 template <class Key, class Value>
00431 void gdtmap<Key,Value>::show(std::ostream& os) const {
00432 std::cout << "Table size " << table_size << std::endl;
00433 std::cout << "Entries " << number_of_entries << std::endl;
00434 std::cout << "Load factor " << load_factor() << std::endl;
00435 for (unsigned long i = 0; i < table_size; ++i) {
00436 Rec* it = table + i;
00437 os << "Index " << i << " ";
00438 if (it->used) {
00439 while (it) {
00440 os << "(" << it->key << "," << it << "," << it->ptr << ") ";
00441 it = it->next;
00442 }
00443
00444 }
00445 os << std::endl;
00446 }
00447 os << "---" << std::endl;
00448 }
00449
00450
00451
00452
00453
00454
00455
00456 template <class Key, class Value>
00457 gdtmap<Key,Value>::gdtmap() {
00458 table = NULL;
00459 init_table();
00460 assert(consistency_check());
00461 }
00462
00463 template <class Key, class Value>
00464 gdtmap<Key,Value>::gdtmap(Value x) : xdef(x) {
00465 table = NULL;
00466 init_table();
00467 assert(consistency_check());
00468 }
00469
00470 template <class Key, class Value>
00471 gdtmap<Key,Value>::gdtmap(Value x, unsigned long table_sz) : xdef(x) {
00472 table =NULL;
00473 init_table(table_sz);
00474 assert(consistency_check());
00475 }
00476
00477 template <class Key, class Value>
00478 gdtmap<Key,Value>& gdtmap<Key,Value>::operator = (const gdtmap<Key,Value>& M) {
00479
00480 delete_table();
00481
00482 init_table(M.table_size);
00483 copy(M);
00484
00485 assert(consistency_check());
00486 return *this;
00487 }
00488
00489 template <class Key, class Value>
00490 gdtmap<Key,Value>::gdtmap(const gdtmap<Key,Value>& M) {
00491 init_table(M.table_size);
00492
00493 copy(M);
00494 assert(consistency_check());
00495 }
00496
00497 template <class Key, class Value>
00498 gdtmap<Key,Value>::~gdtmap() {
00499 gdtmap<Key,Value>::delete_table();
00500 }
00501
00502
00503
00504
00505
00506
00507
00508 template <class Key, class Value>
00509 const Value& gdtmap<Key,Value>::operator[](const Key& key) const {
00510 Rec* it = find_key(HASH(key), key);
00511 return it ? PTR_CONST_ACCESS(Value, it->ptr) : xdef;
00512 }
00513
00514 template <class Key, class Value>
00515 Value& gdtmap<Key,Value>::operator[](const Key& key) {
00516 Rec* first = HASH(key);
00517 Rec* it = find_key(first, key);
00518 assert(it ? (it->key == key) : true);
00519 return PTR_ACCESS(Value, it ? it->ptr : add_entry(first, key, xdef)->ptr);
00520 }
00521
00522 template <class Key, class Value>
00523 bool gdtmap<Key,Value>::defined(const Key& key) const {
00524 return find_key(HASH(key), key) != NULL;
00525 }
00526
00527 template <class Key, class Value>
00528 void gdtmap<Key,Value>::undefine(const Key& key) {
00529 Rec* first = HASH(key);
00530 if (first->used) {
00531 Rec *it = first;
00532
00533 while (it && it->key != key) {
00534 it = it->next;
00535 }
00536 if (it) {
00537 PTR_DELETE(Value, it->ptr);
00538 PTR_DEFAULT_INIT(Value,it->ptr);
00539 }
00540
00541 }
00542 }
00543
00544 template <class Key, class Value>
00545 void gdtmap<Key,Value>::clear() {
00546 delete_table();
00547 init_table();
00548 assert(consistency_check());
00549 }
00550
00551 template <class Key, class Value>
00552 void gdtmap<Key,Value>::clear(Value x) {
00553 xdef = x;
00554 clear();
00555 assert(consistency_check());
00556 }
00557
00558 template <class Key, class Value>
00559 void gdtmap<Key,Value>::statistics() const {
00560 std::cout << "table_size: " << table_size << std::endl;
00561 std::cout << "number of entries: " << number_of_entries << std::endl;
00562
00563 unsigned long used_slots = 0;
00564 for (unsigned long i = 0; i < table_size; ++i) {
00565 if (table[i].used) ++used_slots;
00566 }
00567
00568 std::cout << "fraction of entries in first position: " << ((double) used_slots / number_of_entries) << std::endl;
00569 std::cout << "fraction of empty lists: " << ((double) (table_size - used_slots)/number_of_entries) << std::endl<< std::flush;
00570 }
00571
00572
00573
00574
00575
00576
00577
00578 template <class Key, class Value>
00579 typename gdtmap<Key,Value>::item gdtmap<Key,Value>::first_item() const {
00580 if (table == NULL) return NULL;
00581 Rec *it = table;
00582 for (; it < end && !it->used; ++it);
00583 return (void*) it != end ? it : NULL;
00584 }
00585
00586 template <class Key, class Value>
00587 typename gdtmap<Key,Value>::item gdtmap<Key,Value>::next_item(item _it) const {
00588 Rec* it = (Rec*) _it;
00589 if (it && it < end) {
00590 ++it;
00591 for (; it < end && !it->used; ++it);
00592 return it < end ? it : NULL;
00593 }
00594 else
00595 return NULL;
00596 }
00597
00598 template <class Key, class Value>
00599 Key gdtmap<Key,Value>::key(item _it) const {
00600 Rec* it = (Rec*) _it;
00601 assert(it && it->used);
00602 return it->key;
00603 }
00604
00605 template <class Key, class Value>
00606 Value& gdtmap<Key,Value>::inf(item _it) const {
00607 Rec* it = (Rec*) _it;
00608 assert(it && it->used);
00609 return PTR_ACCESS(Value, it->ptr);
00610 }
00611
00612 }
00613
00614 #endif