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

   1 #include "hash.h"
   2 #include "../debug.h"
   3 #include "threads/malloc.h"
   4
   5 static struct list *find_bucket (struct hash *, hash_elem *);
   6 static struct list_elem *find_elem (struct hash *, struct list *, hash_elem *);
   7 static void insert_elem (struct hash *, struct list *, hash_elem *);
   8 static void remove_elem (struct hash *, hash_elem *);
   9 static void rehash (struct hash *);
  10
  11 /* Initializes hash table H to compute hash values using HASH and
  12    compare hash elements using LESS, given auxiliary data AUX. */
  13 bool
  14 hash_init (struct hash *h,
  15            hash_hash_func *hash, hash_less_func *less, void *aux)
  16 {
  17   h->elem_cnt = 0;
  18   h->bucket_cnt = 4;
  19   h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
  20   h->hash = hash;
  21   h->less = less;
  22   h->aux = aux;
  23
  24   if (h->buckets != NULL)
  25     {
  26       hash_clear (h);
  27       return true;
  28     }
  29   else
  30     return false;
  31 }
  32
  33 /* Removes all the elements from H. */
  34 void
  35 hash_clear (struct hash *h)
  36 {
  37   size_t i;
  38
  39   for (i = 0; i < h->bucket_cnt; i++)
  40     list_init (&h->buckets[i]);
  41   h->elem_cnt = 0;
  42 }
  43
  44 /* Destroys hash table H. */
  45 void
  46 hash_destroy (struct hash *h)
  47 {
  48   free (h->buckets);
  49 }
  50
  51 /* Inserts NEW into hash table H and returns a null pointer, if
  52    no equal element is already in the table.
  53    If an equal element is already in the table, returns it
  54    without inserting NEW. */
  55 hash_elem *
  56 hash_insert (struct hash *h, hash_elem *new)
  57 {
  58   struct list *bucket = find_bucket (h, new);
  59   struct list_elem *old = find_elem (h, bucket, new);
  60
  61   if (old == NULL)
  62     insert_elem (h, bucket, new);
  63
  64   rehash (h);
  65
  66   return old;
  67 }
  68
  69 /* Inserts NEW into hash table H, replacing any equal element
  70    already in the table, which is returned. */
  71 hash_elem *
  72 hash_replace (struct hash *h, hash_elem *new)
  73 {
  74   struct list *bucket = find_bucket (h, new);
  75   struct list_elem *old = find_elem (h, bucket, new);
  76
  77   if (old != NULL)
  78     remove_elem (h, old);
  79   insert_elem (h, bucket, new);
  80
  81   rehash (h);
  82
  83   return old;
  84 }
  85
  86 /* Finds and returns an element equal to E in hash table H, or a
  87    null pointer if no equal element exists in the table. */
  88 hash_elem *
  89 hash_find (struct hash *h, hash_elem *e)
  90 {
  91   return find_elem (h, find_bucket (h, e), e);
  92 }
  93
  94 /* Finds, removes, and returns an element equal to E in hash
  95    table H.  Returns a null pointer if no equal element existed
  96    in the table. */
  97 hash_elem *
  98 hash_delete (struct hash *h, hash_elem *e)
  99 {
 100   struct list_elem *found = find_elem (h, find_bucket (h, e), e);
 101   if (found != NULL)
 102     {
 103       remove_elem (h, found);
 104       rehash (h);
 105     }
 106   return found;
 107 }
 108
 109 /* Initializes I for iterating hash table H.
 110
 111    Iteration idiom:
 112
 113       struct hash_iterator i;
 114
 115       hash_first (&i, h);
 116       while (hash_next (&i))
 117         {
 118           struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
 119           ...do something with f...
 120         }
 121
 122    NOTE: Modifying a hash table during iteration invalidates all
 123    iterators.
 124 */
 125 void
 126 hash_first (struct hash_iterator *i, struct hash *h)
 127 {
 128   ASSERT (i != NULL);
 129   ASSERT (h != NULL);
 130
 131   i->hash = h;
 132   i->bucket = i->hash->buckets;
 133   i->elem = list_head (i->bucket);
 134 }
 135
 136 /* Advances I to the next element in the hash table and returns
 137    it.  Returns a null pointer if no elements are left.  Elements
 138    are returned in arbitrary order.
 139
 140    NOTE: Modifying a hash table during iteration invalidates all
 141    iterators. */
 142 hash_elem *
 143 hash_next (struct hash_iterator *i)
 144 {
 145   ASSERT (i != NULL);
 146
 147   i->elem = list_next (i->elem);
 148   while (i->elem == list_end (i->bucket))
 149     {
 150       if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
 151         {
 152           i->elem = NULL;
 153           break;
 154         }
 155       i->elem = list_begin (i->bucket);
 156     }
 157
 158   return i->elem;
 159 }
 160
 161 /* Returns the current element in the hash table iteration, or a
 162    null pointer at the end of the table.  Undefined behavior
 163    after calling hash_first() but before hash_next(). */
 164 hash_elem *
 165 hash_cur (struct hash_iterator *i)
 166 {
 167   return i->elem;
 168 }
 169
 170 /* Returns the number of elements in H. */
 171 size_t
 172 hash_size (struct hash *h)
 173 {
 174   return h->elem_cnt;
 175 }
 176
 177 /* Returns true if H contains no elements, false otherwise. */
 178 bool
 179 hash_empty (struct hash *h)
 180 {
 181   return h->elem_cnt == 0;
 182 }
 183
 184 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
 185 #define FNV_32_PRIME 16777619u
 186 #define FNV_32_BASIS 2166136261u
 187
 188 /* Returns a hash of the SIZE bytes in BUF. */
 189 unsigned
 190 hash_bytes (const void *buf_, size_t size)
 191 {
 192   /* Fowler-Noll-Vo 32-bit hash, for bytes. */
 193   const unsigned char *buf = buf_;
 194   unsigned hash;
 195
 196   ASSERT (buf != NULL);
 197
 198   hash = FNV_32_BASIS;
 199   while (size-- > 0)
 200     hash = (hash * FNV_32_PRIME) ^ *buf++;
 201
 202   return hash;
 203 }
 204
 205 /* Returns a hash of string S. */
 206 unsigned
 207 hash_string (const char *s_)
 208 {
 209   const unsigned char *s = s_;
 210   unsigned hash;
 211
 212   ASSERT (s != NULL);
 213
 214   hash = FNV_32_BASIS;
 215   while (*s != '\0')
 216     hash = (hash * FNV_32_PRIME) ^ *s++;
 217
 218   return hash;
 219 }
 220
 221 /* Returns a hash of integer I. */
 222 unsigned
 223 hash_int (int i)
 224 {
 225   return hash_bytes (&i, sizeof i);
 226 }
 227 \f
 228 /* Returns the bucket in H that E belongs in. */
 229 static struct list *
 230 find_bucket (struct hash *h, hash_elem *e)
 231 {
 232   size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
 233   return &h->buckets[bucket_idx];
 234 }
 235
 236 /* Searches BUCKET in H for a hash element equal to E.  Returns
 237    it if found or a null pointer otherwise. */
 238 static struct list_elem *
 239 find_elem (struct hash *h, struct list *bucket, hash_elem *e)
 240 {
 241   struct list_elem *i;
 242
 243   for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
 244     if (!h->less (i, e, h->aux) && !h->less (e, i, h->aux))
 245       return i;
 246   return NULL;
 247 }
 248
 249 /* Returns X with its lowest-order bit set to 1 turned off. */
 250 static inline size_t
 251 turn_off_least_1bit (size_t x)
 252 {
 253   return x & (x - 1);
 254 }
 255
 256 /* Returns true if X is a power of 2, otherwise false. */
 257 static inline size_t
 258 is_power_of_2 (size_t x)
 259 {
 260   return x != 0 && turn_off_least_1bit (x) == 0;
 261 }
 262
 263 /* Element per bucket ratios. */
 264 #define MIN_ELEMS_PER_BUCKET  1 /* Elems/bucket < 1: reduce # of buckets. */
 265 #define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */
 266 #define MAX_ELEMS_PER_BUCKET  4 /* Elems/bucket > 4: increase # of buckets. */
 267
 268 /* Changes the number of buckets in hash table H to match the
 269    ideal.  This function can fail because of an out-of-memory
 270    condition, but that'll just make hash accesses less efficient;
 271    we can still continue. */
 272 static void
 273 rehash (struct hash *h)
 274 {
 275   size_t old_bucket_cnt, new_bucket_cnt;
 276   struct list *new_buckets, *old_buckets;
 277   size_t i;
 278
 279   ASSERT (h != NULL);
 280
 281   /* Save old bucket info for later use. */
 282   old_buckets = h->buckets;
 283   old_bucket_cnt = h->bucket_cnt;
 284
 285   /* Calculate the number of buckets to use now.
 286      We want one bucket for about every BEST_ELEMS_PER_BUCKET.
 287      We must have at least four buckets, and the number of
 288      buckets must be a power of 2. */
 289   new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
 290   if (new_bucket_cnt < 4)
 291     new_bucket_cnt = 4;
 292   while (!is_power_of_2 (new_bucket_cnt))
 293     new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
 294
 295   /* Don't do anything if the bucket count wouldn't change. */
 296   if (new_bucket_cnt == old_bucket_cnt)
 297     return;
 298
 299   /* Allocate new buckets and initialize them as empty. */
 300   new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
 301   if (new_buckets == NULL)
 302     {
 303       /* Allocation failed.  This means that use of the hash table will
 304          be less efficient.  However, it is still usable, so
 305          there's no reason for it to be an error. */
 306       return;
 307     }
 308   for (i = 0; i < new_bucket_cnt; i++)
 309     list_init (&new_buckets[i]);
 310
 311   /* Install new bucket info. */
 312   h->buckets = new_buckets;
 313   h->bucket_cnt = new_bucket_cnt;
 314
 315   /* Move each old element into the appropriate new bucket. */
 316   for (i = 0; i < old_bucket_cnt; i++)
 317     {
 318       struct list *old_bucket;
 319       struct list_elem *elem, *next;
 320
 321       old_bucket = &old_buckets[i];
 322       for (elem = list_begin (old_bucket);
 323            elem != list_end (old_bucket); elem = next)
 324         {
 325           struct list *new_bucket = find_bucket (h, elem);
 326           next = list_next (elem);
 327           list_remove (elem);
 328           list_push_front (new_bucket, elem);
 329         }
 330     }
 331
 332   free (old_buckets);
 333 }
 334
 335 /* Inserts E into BUCKET (in hash table H). */
 336 static void
 337 insert_elem (struct hash *h, struct list *bucket, hash_elem *e)
 338 {
 339   h->elem_cnt++;
 340   list_push_front (bucket, e);
 341 }
 342
 343 /* Removes E from hash table H. */
 344 static void
 345 remove_elem (struct hash *h, hash_elem *e)
 346 {
 347   h->elem_cnt--;
 348   list_remove (e);
 349 }
 350