diff options
Diffstat (limited to 'kernel')
| -rw-r--r-- | kernel/hashlib.h | 120 |
1 files changed, 108 insertions, 12 deletions
diff --git a/kernel/hashlib.h b/kernel/hashlib.h index 4e8c00026..5f977c5f1 100644 --- a/kernel/hashlib.h +++ b/kernel/hashlib.h @@ -175,6 +175,7 @@ class dict std::vector<int> hashtable; std::vector<entry_t> entries; int free_list, counter, begin_n; + int begin_seek_count; OPS ops; void init() @@ -182,6 +183,7 @@ class dict free_list = -1; counter = 0; begin_n = -1; + begin_seek_count = 0; } void init_from(const dict<K, T, OPS> &other) @@ -209,6 +211,43 @@ class dict return hash; } + void upd_begin_n() + { + if (begin_n < -1) { + begin_n = -(begin_n+2); + if (begin_n > int(entries.size())) + begin_n = int(entries.size()); + do { + if (begin_seek_count++ > int(entries.size())) + refree(); + else + begin_n--; + } while (begin_n >= 0 && entries[begin_n].is_free()); + } + } + + void refree() + { + free_list = -1; + begin_n = -1; + + int last_free = -1; + for (int i = 0; i < int(entries.size()); i++) + if (entries[i].is_free()) { + if (last_free != -1) + entries[last_free].set_next_free(i); + else + free_list = i; + last_free = i; + } else + begin_n = i; + + if (last_free != -1) + entries[last_free].set_next_free(-1); + + begin_seek_count = 0; + } + void rehash() { free_list = -1; @@ -217,16 +256,25 @@ class dict for (auto &h : hashtable) h = -1; + int last_free = -1; for (int i = 0; i < int(entries.size()); i++) if (entries[i].is_free()) { - entries[i].set_next_free(free_list); - free_list = i; + if (last_free != -1) + entries[last_free].set_next_free(i); + else + free_list = i; + last_free = i; } else { int hash = mkhash(entries[i].udata.first); entries[i].set_next_used(hashtable[hash]); hashtable[hash] = i; begin_n = i; } + + if (last_free != -1) + entries[last_free].set_next_free(-1); + + begin_seek_count = 0; } int do_erase(const K &key, int hash) @@ -247,7 +295,7 @@ class dict if (--counter == 0) clear(); else if (index == begin_n) - do begin_n--; while (begin_n >= 0 && entries[begin_n].is_free()); + begin_n = -(begin_n+2); return 1; } last_index = index; @@ -287,7 +335,7 @@ class dict entries[i].udata = value; entries[i].set_next_used(hashtable[hash]); hashtable[hash] = i; - if (begin_n < i) + if ((begin_n < -1 && -(begin_n+2) <= i) || (begin_n >= -1 && begin_n <= i)) begin_n = i; counter++; return i; @@ -486,10 +534,10 @@ public: bool empty() const { return counter == 0; } void clear() { hashtable.clear(); entries.clear(); init(); } - iterator begin() { return iterator(this, begin_n); } + iterator begin() { upd_begin_n(); return iterator(this, begin_n); } iterator end() { return iterator(this, -1); } - const_iterator begin() const { return const_iterator(this, begin_n); } + const_iterator begin() const { ((dict*)this)->upd_begin_n(); return const_iterator(this, begin_n); } const_iterator end() const { return const_iterator(this, -1); } }; @@ -514,6 +562,7 @@ class pool std::vector<int> hashtable; std::vector<entry_t> entries; int free_list, counter, begin_n; + int begin_seek_count; OPS ops; void init() @@ -521,6 +570,7 @@ class pool free_list = -1; counter = 0; begin_n = -1; + begin_seek_count = 0; } void init_from(const pool<K, OPS> &other) @@ -548,6 +598,43 @@ class pool return hash; } + void upd_begin_n() + { + if (begin_n < -1) { + begin_n = -(begin_n+2); + if (begin_n > int(entries.size())) + begin_n = int(entries.size()); + do { + if (begin_seek_count++ > int(entries.size())) + refree(); + else + begin_n--; + } while (begin_n >= 0 && entries[begin_n].is_free()); + } + } + + void refree() + { + free_list = -1; + begin_n = -1; + + int last_free = -1; + for (int i = 0; i < int(entries.size()); i++) + if (entries[i].is_free()) { + if (last_free != -1) + entries[last_free].set_next_free(i); + else + free_list = i; + last_free = i; + } else + begin_n = i; + + if (last_free != -1) + entries[last_free].set_next_free(-1); + + begin_seek_count = 0; + } + void rehash() { free_list = -1; @@ -556,16 +643,25 @@ class pool for (auto &h : hashtable) h = -1; + int last_free = -1; for (int i = 0; i < int(entries.size()); i++) if (entries[i].is_free()) { - entries[i].set_next_free(free_list); - free_list = i; + if (last_free != -1) + entries[last_free].set_next_free(i); + else + free_list = i; + last_free = i; } else { int hash = mkhash(entries[i].key); entries[i].set_next_used(hashtable[hash]); hashtable[hash] = i; begin_n = i; } + + if (last_free != -1) + entries[last_free].set_next_free(-1); + + begin_seek_count = 0; } int do_erase(const K &key, int hash) @@ -586,7 +682,7 @@ class pool if (--counter == 0) clear(); else if (index == begin_n) - do begin_n--; while (begin_n >= 0 && entries[begin_n].is_free()); + begin_n = -(begin_n+2); return 1; } last_index = index; @@ -626,7 +722,7 @@ class pool entries[i].key = key; entries[i].set_next_used(hashtable[hash]); hashtable[hash] = i; - if (begin_n < i) + if ((begin_n < -1 && -(begin_n+2) <= i) || (begin_n >= -1 && begin_n <= i)) begin_n = i; counter++; return i; @@ -805,10 +901,10 @@ public: bool empty() const { return counter == 0; } void clear() { hashtable.clear(); entries.clear(); init(); } - iterator begin() { return iterator(this, begin_n); } + iterator begin() { upd_begin_n(); return iterator(this, begin_n); } iterator end() { return iterator(this, -1); } - const_iterator begin() const { return const_iterator(this, begin_n); } + const_iterator begin() const { ((pool*)this)->upd_begin_n(); return const_iterator(this, begin_n); } const_iterator end() const { return const_iterator(this, -1); } }; |