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