1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
/** \file     my_hash.c
 *  \brief    A simple implementation of a chained-hash table (without delete operation)
 *  \author   Takahisa Toda
 */
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "my_def.h"
#include "my_hash.h"


#define DEFAULT_HASH_SIZE         (UINTMAX_C(1) << 24)  //!< The default number of buckets
#define HASH_ENLARGEMENT_WIDTH    (2)                   //!< the width of bitshift for enlargement
#define HASHCONST                 (31415926525)


/** \brief    Create a hash table.
 *  \param    n     The number of buckets to be created
 *  \return   Pointer to a hash table if successful; otherwise, NULL.
 *  \note     Set a default value to n if n == 0. 
 *  \see      ht_destroy
 */
my_hash *ht_create(uintmax_t n)
{
  n = (n == 0? DEFAULT_HASH_SIZE: n);

  my_hash *h = (my_hash*) malloc(sizeof(my_hash));
  ENSURE_TRUE_MSG(h != NULL,"memory allocation failed");

  h->bucket_count = n;
  h->entry_count  = 0;
  h->table        = (struct ht_entry**) malloc(sizeof(struct ht_entry*) * n);
  ENSURE_TRUE_MSG(h->table != NULL, "memory allocation failed");
  for(uintmax_t i = 0; i < n; i++) h->table[i] = NULL;

  return h;
}


/** \brief    Free memory area used by a hash table.
 *  \param    h     Pointer to a hash table
 *  \see      ht_create
 */
void ht_destroy(my_hash *h)
{
  assert(h != NULL);
  const uintmax_t n = h->bucket_count;
  for(uintmax_t i = 0; i < n; i++) {
      for(struct ht_entry *e = h->table[i]; e != NULL; ) {
        struct ht_entry *t = e->nx;
        free(e);
        e = t;
      }
  }
  free(h->table); h->table  = NULL;
  free(h);        h         = NULL;
}

/** \brief    Calculate a hash value.
 *  \param    k     Key (of pointer size)
 *  \param    n     The number of buckets
 *  \return   The calculated hash value
 */
static inline uintmax_t ht_hash(uintptr_t k, uintmax_t n)
{
  assert(n > 0);
  return (uintmax_t)(HASHCONST * (k >> 3))%n;
}

/** \brief    Insert a new entry to the head of a linked list.
 *  \param    k     Key (of pointer size)
 *  \param    v     Value associated with key (of pointer size)
 *  \param    h     Pointer to a hash table
 *  \see      ht_search
 */
void ht_insert(uintptr_t k, uintptr_t v, my_hash *h)
{
  assert(h != NULL);
  struct ht_entry *e = (struct ht_entry*)malloc(sizeof(struct ht_entry));
  ENSURE_TRUE_MSG(e != NULL, "memory allocation failed");
  e->key = k;
  e->val = v;

  const uintmax_t i = ht_hash(k, h->bucket_count);
  e->nx             = h->table[i];
  h->table[i]       = e;

  h->entry_count++;
}


/** \brief    Find a hash entry. If found, copy the associated value to the location pointed to by pv.
 *  \param    k     key (of pointer size)
 *  \param    pv    Pointer to a variable, in which the associated value (of pointer size) is copied.
 *  \param    h     Pointer to a hash table
 *  \return   true if found; otherwise, false.
 *  \see      ht_insert
 *  \note
 *  - Value will not be copied if pd == NULL.
 */
bool ht_search(uintptr_t k, uintptr_t *pv, const my_hash *h)
{
  assert(h != NULL);
  const uintmax_t i = ht_hash(k, h->bucket_count);
  for(struct ht_entry *e = h->table[i]; e != NULL; e = e->nx) {
    if(e->key == k) {
      if(pv != NULL) *pv = e->val;
      return true;
    }
  }
  return false;
}


/** \brief   Enlarge a hash table.
 *  \param   h     Pointer to a hash table
 *  \see     ht_create, ht_destroy
 */
void ht_enlarge(my_hash *h)
{
  const uintmax_t oldcnt = h->bucket_count;
  ENSURE_TRUE_MSG(oldcnt < (UINTMAX_MAX >> HASH_ENLARGEMENT_WIDTH), "bucket count overflow");
  const uintmax_t newcnt = oldcnt << HASH_ENLARGEMENT_WIDTH;
#ifdef HT_LOG
  printf("hashtable_resizing\t%ju\t%ju\n", oldcnt, newcnt);
#endif /*HT_LOG*/
  struct ht_entry **oldtable = h->table;
  struct ht_entry **newtable = (struct ht_entry**) malloc(sizeof(struct ht_entry*) * newcnt);
  ENSURE_TRUE_MSG(newtable != NULL, "memory allocation failed");
  for(uintmax_t i = 0; i < newcnt; i++) newtable[i] = NULL;
  for(uintmax_t i = 0; i < oldcnt; i++) {
    for(struct ht_entry *e = oldtable[i]; e != NULL;) {
      struct ht_entry *t  = e->nx;
      const uintmax_t j   = ht_hash(e->key, newcnt);
      e->nx       = newtable[j];
      newtable[j] = e;      
      e           = t;
    }
  }
  free(oldtable); oldtable = NULL;
  h->bucket_count = newcnt;
  h->table        = newtable;
}