| /** @file |
| |
| A brief file description |
| |
| @section license License |
| |
| Licensed to the Apache Software Foundation (ASF) under one |
| or more contributor license agreements. See the NOTICE file |
| distributed with this work for additional information |
| regarding copyright ownership. The ASF licenses this file |
| to you under the Apache License, Version 2.0 (the |
| "License"); you may not use this file except in compliance |
| with the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, software |
| distributed under the License is distributed on an "AS IS" BASIS, |
| WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| See the License for the specific language governing permissions and |
| limitations under the License. |
| */ |
| |
| /**************************************************************************** |
| |
| MT_hashtable.h |
| |
| Multithread Safe Hash table implementation |
| |
| |
| ****************************************************************************/ |
| #pragma once |
| |
| #define MT_HASHTABLE_PARTITION_BITS 6 |
| #define MT_HASHTABLE_PARTITIONS (1 << MT_HASHTABLE_PARTITION_BITS) |
| #define MT_HASHTABLE_PARTITION_MASK (MT_HASHTABLE_PARTITIONS - 1) |
| #define MT_HASHTABLE_MAX_CHAIN_AVG_LEN 4 |
| template <class key_t, class data_t> struct HashTableEntry { |
| key_t key; |
| data_t data; |
| HashTableEntry *next; |
| |
| static HashTableEntry * |
| alloc() |
| { |
| return (HashTableEntry *)ats_malloc(sizeof(HashTableEntry)); |
| } |
| |
| static void |
| free(HashTableEntry *entry) |
| { |
| ats_free(entry); |
| } |
| }; |
| |
| /* |
| struct MT_ListEntry{ |
| MT_ListEntry():next(NULL),prev(NULL){} |
| MT_ListEntry* next; |
| MT_ListEntry* prev; |
| }; |
| |
| #define INIT_CHAIN_HEAD(h) {(h)->next = (h)->prev = (h);} |
| #define APPEND_TO_CHAIN(h, p) {(p)->next = (h)->next; (h)->next->prev = (p); (p)->prev = (h); (h)->next = (p);} |
| #define REMOVE_FROM_CHAIN(p) {(p)->next->prev = (p)->prev; (p)->prev->next = (p)->next; (p)->prev = (p)->next = NULL;} |
| #define GET_OBJ_PTR(p, type, offset) ((type*)((char*)(p) - offset)) |
| */ |
| |
| template <class key_t, class data_t> class HashTableIteratorState |
| { |
| public: |
| HashTableIteratorState() : ppcur(NULL) {} |
| int cur_buck = -1; |
| HashTableEntry<key_t, data_t> **ppcur; |
| }; |
| |
| template <class key_t, class data_t> class IMTHashTable |
| { |
| public: |
| IMTHashTable(int size, bool (*gc_func)(data_t) = NULL, void (*pre_gc_func)() = nullptr) |
| { |
| m_gc_func = gc_func; |
| m_pre_gc_func = pre_gc_func; |
| bucket_num = size; |
| cur_size = 0; |
| buckets = new HashTableEntry<key_t, data_t> *[bucket_num]; |
| memset(buckets, 0, bucket_num * sizeof(HashTableEntry<key_t, data_t> *)); |
| } |
| ~IMTHashTable() { reset(); } |
| int |
| getBucketNum() |
| { |
| return bucket_num; |
| } |
| int |
| getCurSize() |
| { |
| return cur_size; |
| } |
| |
| int |
| bucket_id(key_t key, int a_bucket_num) |
| { |
| return (int)(((key >> MT_HASHTABLE_PARTITION_BITS) ^ key) % a_bucket_num); |
| } |
| |
| int |
| bucket_id(key_t key) |
| { |
| return bucket_id(key, bucket_num); |
| } |
| |
| void |
| reset() |
| { |
| HashTableEntry<key_t, data_t> *tmp; |
| for (int i = 0; i < bucket_num; i++) { |
| tmp = buckets[i]; |
| while (tmp) { |
| buckets[i] = tmp->next; |
| HashTableEntry<key_t, data_t>::free(tmp); |
| tmp = buckets[i]; |
| } |
| } |
| delete[] buckets; |
| buckets = NULL; |
| } |
| |
| data_t insert_entry(key_t key, data_t data); |
| data_t remove_entry(key_t key); |
| data_t lookup_entry(key_t key); |
| |
| data_t first_entry(int bucket_id, HashTableIteratorState<key_t, data_t> *s); |
| static data_t next_entry(HashTableIteratorState<key_t, data_t> *s); |
| static data_t cur_entry(HashTableIteratorState<key_t, data_t> *s); |
| data_t remove_entry(HashTableIteratorState<key_t, data_t> *s); |
| |
| void |
| GC() |
| { |
| if (m_gc_func == NULL) { |
| return; |
| } |
| if (m_pre_gc_func) { |
| m_pre_gc_func(); |
| } |
| for (int i = 0; i < bucket_num; i++) { |
| HashTableEntry<key_t, data_t> *cur = buckets[i]; |
| HashTableEntry<key_t, data_t> *prev = NULL; |
| HashTableEntry<key_t, data_t> *next = NULL; |
| while (cur != NULL) { |
| next = cur->next; |
| if (m_gc_func(cur->data)) { |
| if (prev != NULL) { |
| prev->next = next; |
| } else { |
| buckets[i] = next; |
| } |
| ats_free(cur); |
| cur_size--; |
| } else { |
| prev = cur; |
| } |
| cur = next; |
| } |
| } |
| } |
| |
| void |
| resize(int size) |
| { |
| int new_bucket_num = size; |
| HashTableEntry<key_t, data_t> **new_buckets = new HashTableEntry<key_t, data_t> *[new_bucket_num]; |
| memset(new_buckets, 0, new_bucket_num * sizeof(HashTableEntry<key_t, data_t> *)); |
| |
| for (int i = 0; i < bucket_num; i++) { |
| HashTableEntry<key_t, data_t> *cur = buckets[i]; |
| HashTableEntry<key_t, data_t> *next = NULL; |
| while (cur != NULL) { |
| next = cur->next; |
| int new_id = bucket_id(cur->key, new_bucket_num); |
| cur->next = new_buckets[new_id]; |
| new_buckets[new_id] = cur; |
| cur = next; |
| } |
| buckets[i] = NULL; |
| } |
| delete[] buckets; |
| buckets = new_buckets; |
| bucket_num = new_bucket_num; |
| } |
| |
| private: |
| HashTableEntry<key_t, data_t> **buckets; |
| int cur_size; |
| int bucket_num; |
| bool (*m_gc_func)(data_t); |
| void (*m_pre_gc_func)(); |
| |
| private: |
| IMTHashTable(); |
| IMTHashTable(IMTHashTable &); |
| }; |
| |
| /* |
| * we can use ClassAllocator here if the malloc performance becomes a problem |
| */ |
| |
| template <class key_t, class data_t> |
| inline data_t |
| IMTHashTable<key_t, data_t>::insert_entry(key_t key, data_t data) |
| { |
| int id = bucket_id(key); |
| HashTableEntry<key_t, data_t> *cur = buckets[id]; |
| while (cur != NULL && cur->key != key) { |
| cur = cur->next; |
| } |
| if (cur != NULL) { |
| if (data == cur->data) { |
| return (data_t)0; |
| } else { |
| data_t tmp = cur->data; |
| cur->data = data; |
| // potential memory leak, need to check the return value by the caller |
| return tmp; |
| } |
| } |
| |
| HashTableEntry<key_t, data_t> *newEntry = HashTableEntry<key_t, data_t>::alloc(); |
| newEntry->key = key; |
| newEntry->data = data; |
| newEntry->next = buckets[id]; |
| buckets[id] = newEntry; |
| cur_size++; |
| if (cur_size / bucket_num > MT_HASHTABLE_MAX_CHAIN_AVG_LEN) { |
| GC(); |
| if (cur_size / bucket_num > MT_HASHTABLE_MAX_CHAIN_AVG_LEN) { |
| resize(bucket_num * 2); |
| } |
| } |
| return (data_t)0; |
| } |
| |
| template <class key_t, class data_t> |
| inline data_t |
| IMTHashTable<key_t, data_t>::remove_entry(key_t key) |
| { |
| int id = bucket_id(key); |
| data_t ret = (data_t)0; |
| HashTableEntry<key_t, data_t> *cur = buckets[id]; |
| HashTableEntry<key_t, data_t> *prev = NULL; |
| while (cur != NULL && cur->key != key) { |
| prev = cur; |
| cur = cur->next; |
| } |
| if (cur != NULL) { |
| if (prev != NULL) { |
| prev->next = cur->next; |
| } else { |
| buckets[id] = cur->next; |
| } |
| ret = cur->data; |
| HashTableEntry<key_t, data_t>::free(cur); |
| cur_size--; |
| } |
| |
| return ret; |
| } |
| |
| template <class key_t, class data_t> |
| inline data_t |
| IMTHashTable<key_t, data_t>::lookup_entry(key_t key) |
| { |
| int id = bucket_id(key); |
| data_t ret = (data_t)0; |
| HashTableEntry<key_t, data_t> *cur = buckets[id]; |
| while (cur != NULL && cur->key != key) { |
| cur = cur->next; |
| } |
| if (cur != NULL) { |
| ret = cur->data; |
| } |
| return ret; |
| } |
| |
| template <class key_t, class data_t> |
| inline data_t |
| IMTHashTable<key_t, data_t>::first_entry(int bucket_id, HashTableIteratorState<key_t, data_t> *s) |
| { |
| s->cur_buck = bucket_id; |
| s->ppcur = &(buckets[bucket_id]); |
| if (*(s->ppcur) != NULL) { |
| return (*(s->ppcur))->data; |
| } |
| return (data_t)0; |
| } |
| |
| template <class key_t, class data_t> |
| inline data_t |
| IMTHashTable<key_t, data_t>::next_entry(HashTableIteratorState<key_t, data_t> *s) |
| { |
| if ((*(s->ppcur)) != NULL) { |
| s->ppcur = &((*(s->ppcur))->next); |
| if (*(s->ppcur) != NULL) { |
| return (*(s->ppcur))->data; |
| } |
| } |
| return (data_t)0; |
| } |
| |
| template <class key_t, class data_t> |
| inline data_t |
| IMTHashTable<key_t, data_t>::cur_entry(HashTableIteratorState<key_t, data_t> *s) |
| { |
| if (*(s->ppcur) == NULL) { |
| return (data_t)0; |
| } |
| return (*(s->ppcur))->data; |
| } |
| |
| template <class key_t, class data_t> |
| inline data_t |
| IMTHashTable<key_t, data_t>::remove_entry(HashTableIteratorState<key_t, data_t> *s) |
| { |
| data_t data = (data_t)0; |
| HashTableEntry<key_t, data_t> *pEntry = *(s->ppcur); |
| if (pEntry != NULL) { |
| data = pEntry->data; |
| (*(s->ppcur)) = pEntry->next; |
| HashTableEntry<key_t, data_t>::free(pEntry); |
| cur_size--; |
| } |
| return data; |
| } |
| |
| template <class key_t, class data_t> class MTHashTable |
| { |
| public: |
| MTHashTable(int size, bool (*gc_func)(data_t) = NULL, void (*pre_gc_func)() = nullptr) |
| { |
| for (int i = 0; i < MT_HASHTABLE_PARTITIONS; i++) { |
| locks[i] = new_ProxyMutex(); |
| hashTables[i] = new IMTHashTable<key_t, data_t>(size, gc_func, pre_gc_func); |
| // INIT_CHAIN_HEAD(&chain_heads[i]); |
| // last_GC_time[i] = 0; |
| } |
| // cur_items = 0; |
| } |
| ~MTHashTable() |
| { |
| for (int i = 0; i < MT_HASHTABLE_PARTITIONS; i++) { |
| locks[i] = NULL; |
| delete hashTables[i]; |
| } |
| } |
| |
| Ptr<ProxyMutex> |
| lock_for_key(key_t key) |
| { |
| return locks[part_num(key)]; |
| } |
| |
| int |
| getSize() |
| { |
| return MT_HASHTABLE_PARTITIONS; |
| } |
| int |
| part_num(key_t key) |
| { |
| return (int)(key & MT_HASHTABLE_PARTITION_MASK); |
| } |
| data_t |
| insert_entry(key_t key, data_t data) |
| { |
| // ink_atomic_increment(&cur_items, 1); |
| return hashTables[part_num(key)]->insert_entry(key, data); |
| } |
| data_t |
| remove_entry(key_t key) |
| { |
| // ink_atomic_increment(&cur_items, -1); |
| return hashTables[part_num(key)]->remove_entry(key); |
| } |
| data_t |
| lookup_entry(key_t key) |
| { |
| return hashTables[part_num(key)]->lookup_entry(key); |
| } |
| |
| data_t |
| first_entry(int part_id, HashTableIteratorState<key_t, data_t> *s) |
| { |
| data_t ret = (data_t)0; |
| for (int i = 0; i < hashTables[part_id]->getBucketNum(); i++) { |
| ret = hashTables[part_id]->first_entry(i, s); |
| if (ret != (data_t)0) { |
| return ret; |
| } |
| } |
| return (data_t)0; |
| } |
| |
| data_t |
| cur_entry(int part_id, HashTableIteratorState<key_t, data_t> *s) |
| { |
| data_t data = IMTHashTable<key_t, data_t>::cur_entry(s); |
| if (!data) { |
| data = next_entry(part_id, s); |
| } |
| return data; |
| }; |
| data_t |
| next_entry(int part_id, HashTableIteratorState<key_t, data_t> *s) |
| { |
| data_t ret = IMTHashTable<key_t, data_t>::next_entry(s); |
| if (ret != (data_t)0) { |
| return ret; |
| } |
| for (int i = s->cur_buck + 1; i < hashTables[part_id]->getBucketNum(); i++) { |
| ret = hashTables[part_id]->first_entry(i, s); |
| if (ret != (data_t)0) { |
| return ret; |
| } |
| } |
| return (data_t)0; |
| } |
| data_t |
| remove_entry(int part_id, HashTableIteratorState<key_t, data_t> *s) |
| { |
| // ink_atomic_increment(&cur_items, -1); |
| return hashTables[part_id]->remove_entry(s); |
| } |
| |
| private: |
| IMTHashTable<key_t, data_t> *hashTables[MT_HASHTABLE_PARTITIONS]; |
| Ptr<ProxyMutex> locks[MT_HASHTABLE_PARTITIONS]; |
| // MT_ListEntry chain_heads[MT_HASHTABLE_PARTITIONS]; |
| // int last_GC_time[MT_HASHTABLE_PARTITIONS]; |
| // int32_t cur_items; |
| }; |