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 hash_clear (struct hash *h)
43 for (i = 0; i < h->bucket_cnt; i++)
44 list_init (&h->buckets[i]);
48 /* Destroys hash table H. */
50 hash_destroy (struct hash *h)
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. */
60 hash_insert (struct hash *h, struct hash_elem *new)
62 struct list *bucket = find_bucket (h, new);
63 struct hash_elem *old = find_elem (h, bucket, new);
66 insert_elem (h, bucket, new);
73 /* Inserts NEW into hash table H, replacing any equal element
74 already in the table, which is returned. */
76 hash_replace (struct hash *h, struct hash_elem *new)
78 struct list *bucket = find_bucket (h, new);
79 struct hash_elem *old = find_elem (h, bucket, new);
83 insert_elem (h, bucket, new);
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. */
93 hash_find (struct hash *h, struct hash_elem *e)
95 return find_elem (h, find_bucket (h, e), e);
98 /* Finds, removes, and returns an element equal to E in hash
99 table H. Returns a null pointer if no equal element existed
102 hash_delete (struct hash *h, struct hash_elem *e)
104 struct hash_elem *found = find_elem (h, find_bucket (h, e), e);
107 remove_elem (h, found);
113 /* Initializes I for iterating hash table H.
117 struct hash_iterator i;
120 while (hash_next (&i))
122 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
123 ...do something with f...
126 NOTE: Modifying a hash table during iteration invalidates all
130 hash_first (struct hash_iterator *i, struct hash *h)
136 i->bucket = i->hash->buckets;
137 i->elem = list_elem_to_hash_elem (list_head (i->bucket));
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.
144 NOTE: Modifying a hash table during iteration invalidates all
147 hash_next (struct hash_iterator *i)
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)))
154 if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
159 i->elem = list_elem_to_hash_elem (list_begin (i->bucket));
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(). */
169 hash_cur (struct hash_iterator *i)
174 /* Returns the number of elements in H. */
176 hash_size (struct hash *h)
181 /* Returns true if H contains no elements, false otherwise. */
183 hash_empty (struct hash *h)
185 return h->elem_cnt == 0;
188 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
189 #define FNV_32_PRIME 16777619u
190 #define FNV_32_BASIS 2166136261u
192 /* Returns a hash of the SIZE bytes in BUF. */
194 hash_bytes (const void *buf_, size_t size)
196 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
197 const unsigned char *buf = buf_;
200 ASSERT (buf != NULL);
204 hash = (hash * FNV_32_PRIME) ^ *buf++;
209 /* Returns a hash of string S. */
211 hash_string (const char *s_)
213 const unsigned char *s = s_;
220 hash = (hash * FNV_32_PRIME) ^ *s++;
225 /* Returns a hash of integer I. */
229 return hash_bytes (&i, sizeof i);
232 /* Returns the bucket in H that E belongs in. */
234 find_bucket (struct hash *h, struct hash_elem *e)
236 size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
237 return &h->buckets[bucket_idx];
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)
247 for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
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))
256 /* Returns X with its lowest-order bit set to 1 turned off. */
258 turn_off_least_1bit (size_t x)
263 /* Returns true if X is a power of 2, otherwise false. */
265 is_power_of_2 (size_t x)
267 return x != 0 && turn_off_least_1bit (x) == 0;
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. */
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. */
280 rehash (struct hash *h)
282 size_t old_bucket_cnt, new_bucket_cnt;
283 struct list *new_buckets, *old_buckets;
288 /* Save old bucket info for later use. */
289 old_buckets = h->buckets;
290 old_bucket_cnt = h->bucket_cnt;
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)
299 while (!is_power_of_2 (new_bucket_cnt))
300 new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
302 /* Don't do anything if the bucket count wouldn't change. */
303 if (new_bucket_cnt == old_bucket_cnt)
306 /* Allocate new buckets and initialize them as empty. */
307 new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
308 if (new_buckets == NULL)
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. */
315 for (i = 0; i < new_bucket_cnt; i++)
316 list_init (&new_buckets[i]);
318 /* Install new bucket info. */
319 h->buckets = new_buckets;
320 h->bucket_cnt = new_bucket_cnt;
322 /* Move each old element into the appropriate new bucket. */
323 for (i = 0; i < old_bucket_cnt; i++)
325 struct list *old_bucket;
326 struct list_elem *elem, *next;
328 old_bucket = &old_buckets[i];
329 for (elem = list_begin (old_bucket);
330 elem != list_end (old_bucket); elem = next)
332 struct list *new_bucket
333 = find_bucket (h, list_elem_to_hash_elem (elem));
334 next = list_next (elem);
336 list_push_front (new_bucket, elem);
343 /* Inserts E into BUCKET (in hash table H). */
345 insert_elem (struct hash *h, struct list *bucket, struct hash_elem *e)
348 list_push_front (bucket, &e->list_elem);
351 /* Removes E from hash table H. */
353 remove_elem (struct hash *h, struct hash_elem *e)
356 list_remove (&e->list_elem);