3 #include "threads/malloc.h"
5 #define list_elem_to_hash_elem(LIST_ELEM) \
6 list_entry(LIST_ELEM, struct hash_elem, list_elem)
8 static struct list *find_bucket (struct hash *, struct hash_elem *);
9 static struct hash_elem *find_elem (struct hash *, struct list *,
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 *);
15 /* Initializes hash table H to compute hash values using HASH and
16 compare hash elements using LESS, given auxiliary data AUX. */
18 hash_init (struct hash *h,
19 hash_hash_func *hash, hash_less_func *less, void *aux)
23 h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
28 if (h->buckets != NULL)
37 /* Removes all the elements from H.
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. */
47 hash_clear (struct hash *h, hash_action_func *destructor)
51 for (i = 0; i < h->bucket_cnt; i++)
53 struct list *bucket = &h->buckets[i];
55 if (destructor != NULL)
56 while (!list_empty (bucket))
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);
69 /* Destroys hash table H.
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
80 hash_destroy (struct hash *h, hash_action_func *destructor)
82 if (destructor != NULL)
83 hash_clear (h, destructor);
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. */
92 hash_insert (struct hash *h, struct hash_elem *new)
94 struct list *bucket = find_bucket (h, new);
95 struct hash_elem *old = find_elem (h, bucket, new);
98 insert_elem (h, bucket, new);
105 /* Inserts NEW into hash table H, replacing any equal element
106 already in the table, which is returned. */
108 hash_replace (struct hash *h, struct hash_elem *new)
110 struct list *bucket = find_bucket (h, new);
111 struct hash_elem *old = find_elem (h, bucket, new);
114 remove_elem (h, old);
115 insert_elem (h, bucket, new);
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. */
125 hash_find (struct hash *h, struct hash_elem *e)
127 return find_elem (h, find_bucket (h, e), e);
130 /* Finds, removes, and returns an element equal to E in hash
131 table H. Returns a null pointer if no equal element existed
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. */
138 hash_delete (struct hash *h, struct hash_elem *e)
140 struct hash_elem *found = find_elem (h, find_bucket (h, e), e);
143 remove_elem (h, found);
149 /* Calls ACTION for each element in hash table H in arbitrary
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. */
156 hash_apply (struct hash *h, hash_action_func *action)
160 ASSERT (action != NULL);
162 for (i = 0; i < h->bucket_cnt; i++)
164 struct list *bucket = &h->buckets[i];
165 struct list_elem *elem, *next;
167 for (elem = list_begin (bucket); elem != list_end (bucket); elem = next)
169 next = list_next (elem);
170 action (list_elem_to_hash_elem (elem), h->aux);
175 /* Initializes I for iterating hash table H.
179 struct hash_iterator i;
182 while (hash_next (&i))
184 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
185 ...do something with f...
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
193 hash_first (struct hash_iterator *i, struct hash *h)
199 i->bucket = i->hash->buckets;
200 i->elem = list_elem_to_hash_elem (list_head (i->bucket));
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.
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
212 hash_next (struct hash_iterator *i)
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)))
219 if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
224 i->elem = list_elem_to_hash_elem (list_begin (i->bucket));
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(). */
234 hash_cur (struct hash_iterator *i)
239 /* Returns the number of elements in H. */
241 hash_size (struct hash *h)
246 /* Returns true if H contains no elements, false otherwise. */
248 hash_empty (struct hash *h)
250 return h->elem_cnt == 0;
253 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
254 #define FNV_32_PRIME 16777619u
255 #define FNV_32_BASIS 2166136261u
257 /* Returns a hash of the SIZE bytes in BUF. */
259 hash_bytes (const void *buf_, size_t size)
261 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
262 const unsigned char *buf = buf_;
265 ASSERT (buf != NULL);
269 hash = (hash * FNV_32_PRIME) ^ *buf++;
274 /* Returns a hash of string S. */
276 hash_string (const char *s_)
278 const unsigned char *s = (const unsigned char *) s_;
285 hash = (hash * FNV_32_PRIME) ^ *s++;
290 /* Returns a hash of integer I. */
294 return hash_bytes (&i, sizeof i);
297 /* Returns the bucket in H that E belongs in. */
299 find_bucket (struct hash *h, struct hash_elem *e)
301 size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
302 return &h->buckets[bucket_idx];
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)
312 for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
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))
321 /* Returns X with its lowest-order bit set to 1 turned off. */
323 turn_off_least_1bit (size_t x)
328 /* Returns true if X is a power of 2, otherwise false. */
330 is_power_of_2 (size_t x)
332 return x != 0 && turn_off_least_1bit (x) == 0;
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. */
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. */
345 rehash (struct hash *h)
347 size_t old_bucket_cnt, new_bucket_cnt;
348 struct list *new_buckets, *old_buckets;
353 /* Save old bucket info for later use. */
354 old_buckets = h->buckets;
355 old_bucket_cnt = h->bucket_cnt;
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)
364 while (!is_power_of_2 (new_bucket_cnt))
365 new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
367 /* Don't do anything if the bucket count wouldn't change. */
368 if (new_bucket_cnt == old_bucket_cnt)
371 /* Allocate new buckets and initialize them as empty. */
372 new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
373 if (new_buckets == NULL)
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. */
380 for (i = 0; i < new_bucket_cnt; i++)
381 list_init (&new_buckets[i]);
383 /* Install new bucket info. */
384 h->buckets = new_buckets;
385 h->bucket_cnt = new_bucket_cnt;
387 /* Move each old element into the appropriate new bucket. */
388 for (i = 0; i < old_bucket_cnt; i++)
390 struct list *old_bucket;
391 struct list_elem *elem, *next;
393 old_bucket = &old_buckets[i];
394 for (elem = list_begin (old_bucket);
395 elem != list_end (old_bucket); elem = next)
397 struct list *new_bucket
398 = find_bucket (h, list_elem_to_hash_elem (elem));
399 next = list_next (elem);
401 list_push_front (new_bucket, elem);
408 /* Inserts E into BUCKET (in hash table H). */
410 insert_elem (struct hash *h, struct list *bucket, struct hash_elem *e)
413 list_push_front (bucket, &e->list_elem);
416 /* Removes E from hash table H. */
418 remove_elem (struct hash *h, struct hash_elem *e)
421 list_remove (&e->list_elem);