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