MT_hashtable.h

Go to the documentation of this file.

/** @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


 ****************************************************************************/
#ifndef MT_HASHTABLE_H_
#define MT_HASHTABLE_H_
//#include "Lock.h"

#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():cur_buck(-1), ppcur(NULL) {
  }

  int cur_buck;
  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) (void) = NULL) {
    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(void)
  {
    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;
          delete 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) (void);

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) (void) = NULL) {
    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];
    }
  }
  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;
};

#endif /* MT_HASHTABLE_H_ */