Fix comment.
[pintos-anon] / 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