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

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