pintos-os.org Git - pintos-anon/blob - src/lib/hash.c

   1 #include "hash.h"
   2 #include "malloc.h"
   3
   4 bool
   5 hash_init (struct hash *h,
   6            hash_less_func *less, hash_hash_func *hash, void *aux)
   7 {
   8   h->elem_cnt = 0;
   9   h->bucket_cnt = 4;
  10   h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
  11   h->less = less;
  12   h->hash = hash;
  13   h->aux = aux;
  14
  15   if (h->buckets != NULL)
  16     {
  17       hash_clear (h);
  18       return true;
  19     }
  20   else
  21     return false;
  22 }
  23
  24 struct list *
  25 find_bucket (struct hash *h, hash_elem *e)
  26 {
  27   size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
  28   return h->buckets[bucket_idx];
  29 }
  30
  31 struct list_elem *
  32 find_elem (struct list *bucket, hash_elem *e)
  33 {
  34   struct list_elem *i;
  35
  36   for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
  37     if (equal (i, e))
  38       return i;
  39   return NULL;
  40 }
  41
  42 size_t
  43 turn_off_least_1bit (size_t x)
  44 {
  45   return x & (x - 1);
  46 }
  47
  48 size_t
  49 is_power_of_2 (size_t x)
  50 {
  51   return turn_off_least_1bit (x) == 0;
  52 }
  53
  54 #define MIN_ELEMS_PER_BUCKET  1
  55 #define BEST_ELEMS_PER_BUCKET 2
  56 #define MAX_ELEMS_PER_BUCKET  4
  57
  58 void
  59 rehash (struct hash *h)
  60 {
  61   size_t old_bucket_cnt, new_bucket_cnt;
  62   struct list *new_buckets, *old_buckets;
  63   size_t i;
  64
  65   ASSERT (h != NULL);
  66
  67   /* Save old bucket info for later use. */
  68   old_buckets = h->buckets;
  69   old_bucket_cnt = h->bucket_cnt;
  70
  71   /* Calculate the number of buckets to use now.
  72      We want one bucket for about every BEST_ELEMS_PER_BUCKET.
  73      We must have at least four buckets, and the number of
  74      buckets must be a power of 2. */
  75   new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
  76   if (new_bucket_cnt < 4)
  77     new_bucket_cnt = 4;
  78   while (!is_power_of_2 (new_bucket_cnt))
  79     new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
  80
  81   /* Don't do anything if the bucket count doesn't change. */
  82   if (new_bucket_cnt == old_bucket_cnt)
  83     return;
  84
  85   /* Allocate new buckets and initialize them as empty. */
  86   new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
  87   if (new_buckets == NULL)
  88     {
  89       /* Allocation failed.  This means that use of the hash table will
  90          be less efficient.  However, it is still usable, so
  91          there's no reason for it to be an error. */
  92       return;
  93     }
  94   for (i = 0; i < new_bucket_cnt; i++)
  95     list_init (&new_buckets[i]);
  96
  97   /* Install new bucket info. */
  98   h->buckets = new_buckets;
  99   h->bucket_cnt = new_bucket_cnt;
 100
 101   /* Move each old element into the appropriate new bucket. */
 102   for (i = 0; i < old_bucket_cnt; i++)
 103     {
 104       struct list *old_bucket, *new_bucket;
 105       struct list_elem *elem, *next;
 106
 107       old_bucket = &old_buckets[i];
 108       for (elem = list_begin (old_bucket);
 109            elem != list_end (old_bucket); elem = next)
 110         {
 111           struct list *new_bucket = find_bucket (h, e);
 112           next = list_next (elem);
 113           list_push_front (new_bucket, elem);
 114         }
 115     }
 116 }
 117
 118 void
 119 insert_elem (struct list *bucket, hash_elem *e)
 120 {
 121   h->elem_cnt++;
 122   if (h->elem_cnt > h->bucket_cnt * MAX_ELEMS_PER_BUCKET)
 123     rehash (h);
 124   list_push_front (bucket, e);
 125 }
 126
 127 void
 128 remove_elem (struct hash *h, hash_elem *e)
 129 {
 130   h->elem_cnt--;
 131   if (h->elem_cnt < h->bucket_cnt * MIN_ELEMS_PER_BUCKET)
 132     rehash (h);
 133   list_remove (e);
 134 }
 135
 136 hash_elem *
 137 hash_insert (struct hash *h, hash_elem *new)
 138 {
 139   struct list *bucket = find_bucket (h, new);
 140   struct list_elem *old = find_elem (bucket, new);
 141
 142   if (old == NULL)
 143     insert_elem (bucket, new);
 144   return old;
 145 }
 146
 147 hash_elem *
 148 hash_replace (struct hash *h, hash_elem *new)
 149 {
 150   struct list *bucket = find_bucket (h, new);
 151   struct list_elem *old = find_elem (bucket, new);
 152
 153   if (old != NULL)
 154     remove_elem (h, old);
 155
 156   insert_elem (bucket, new);
 157   return old;
 158 }
 159
 160 hash_elem *
 161 hash_find (struct hash *h, hash_elem *e)
 162 {
 163   struct list *bucket = find_bucket (h, e);
 164   return find_elem (bucket, new);
 165 }
 166
 167 hash_elem *
 168 hash_delete (struct hash *h, hash_elem *target)
 169 {
 170   struct list *bucket = find_bucket (h, e);
 171   struct list_elem *found = find_elem (bucket, new);
 172   if (found != NULL)
 173     remove_elem (h, found);
 174   return found;
 175 }
 176
 177 void
 178 hash_clear (struct hash *h)
 179 {
 180   size_t i;
 181
 182   for (i = 0; i < h->bucket_cnt; h++)
 183     list_init (&h->buckets[i]);
 184   h->elem_cnt = 0;
 185 }
 186
 187 void
 188 hash_first (struct hash_iterator *i, struct hash *h)
 189 {
 190   i->hash = h;
 191   i->bucket = i->hash->buckets;
 192   i->elem = list_begin (*i->bucket);
 193 }
 194
 195 hash_elem *
 196 hash_next (struct hash_iterator *i)
 197 {
 198   ASSERT (i->elem != NULL);
 199
 200   i->elem = list_next (i->elem);
 201   while (i->elem == list_end (*i->bucket))
 202     if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
 203       {
 204         i->elem = NULL;
 205         break;
 206       }
 207
 208   return i->elem;
 209 }
 210
 211 hash_elem *
 212 hash_cur (struct hash_iterator *i)
 213 {
 214   return i->elem;
 215 }
 216
 217 size_t hash_size (struct hash *h)
 218 {
 219   return h->elem_cnt;
 220 }
 221
 222 bool
 223 hash_empty (struct hash *h)
 224 {
 225   return h->elem_cnt == 0;
 226 }
 227
 228 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
 229 #define FNV_32_PRIME 16777619u
 230 #define FNV_32_BASIS 2166136261u
 231
 232 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
 233 unsigned
 234 hsh_hash_bytes (const void *buf_, size_t size)
 235 {
 236   const unsigned char *buf = buf_;
 237   unsigned hash;
 238
 239   assert (buf != NULL);
 240
 241   hash = FNV_32_BASIS;
 242   while (size-- > 0)
 243     hash = (hash * FNV_32_PRIME) ^ *buf++;
 244
 245   return hash;
 246 }
 247
 248 /* Fowler-Noll-Vo 32-bit hash, for strings. */
 249 unsigned
 250 hash_string (const char *s_)
 251 {
 252   const unsigned char *s = s_;
 253   unsigned hash;
 254
 255   assert (s != NULL);
 256
 257   hash = FNV_32_BASIS;
 258   while (*s != '\0')
 259     hash = (hash * FNV_32_PRIME) ^ *s++;
 260
 261   return hash;
 262 }
 263
 264 /* Hash for ints. */
 265 unsigned
 266 hash_int (int i)
 267 {
 268   return hsh_hash_bytes (&i, sizeof i);
 269 }