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