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

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