3 #include "threads/malloc.h"
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 *);
11 /* Initializes hash table H to compute hash values using HASH and
12 compare hash elements using LESS, given auxiliary data AUX. */
14 hash_init (struct hash *h,
15 hash_hash_func *hash, hash_less_func *less, void *aux)
19 h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
24 if (h->buckets != NULL)
33 /* Removes all the elements from H. */
35 hash_clear (struct hash *h)
39 for (i = 0; i < h->bucket_cnt; h++)
40 list_init (&h->buckets[i]);
44 /* Destroys hash table H. */
46 hash_destroy (struct hash *h)
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. */
56 hash_insert (struct hash *h, hash_elem *new)
58 struct list *bucket = find_bucket (h, new);
59 struct list_elem *old = find_elem (h, bucket, new);
62 insert_elem (h, bucket, new);
66 /* Inserts NEW into hash table H, replacing any equal element
67 already in the table, which is returned. */
69 hash_replace (struct hash *h, hash_elem *new)
71 struct list *bucket = find_bucket (h, new);
72 struct list_elem *old = find_elem (h, bucket, new);
77 insert_elem (h, bucket, new);
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. */
84 hash_find (struct hash *h, hash_elem *e)
86 return find_elem (h, find_bucket (h, e), e);
89 /* Finds, removes, and returns an element equal to E in hash
90 table H. Returns a null pointer if no equal element existed
93 hash_delete (struct hash *h, hash_elem *e)
95 struct list_elem *found = find_elem (h, find_bucket (h, e), e);
97 remove_elem (h, found);
101 /* Initializes I for iterating hash table H.
105 struct hash_iterator i;
108 while (hash_next (&i, h))
110 struct foo *f = list_entry (hash_cur (&i), struct foo, elem);
111 ...do something with f...
114 NOTE: Modifying a hash table during iteration invalidates all
118 hash_first (struct hash_iterator *i, struct hash *h)
124 i->bucket = i->hash->buckets;
125 i->elem = list_head (i->bucket);
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.
132 NOTE: Modifying a hash table during iteration invalidates all
135 hash_next (struct hash_iterator *i)
139 i->elem = list_next (i->elem);
140 while (i->elem == list_end (i->bucket))
142 if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
147 i->elem = list_begin (i->bucket);
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(). */
157 hash_cur (struct hash_iterator *i)
162 /* Returns the number of elements in H. */
164 hash_size (struct hash *h)
169 /* Returns true if H contains no elements, false otherwise. */
171 hash_empty (struct hash *h)
173 return h->elem_cnt == 0;
176 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
177 #define FNV_32_PRIME 16777619u
178 #define FNV_32_BASIS 2166136261u
180 /* Returns a hash of the SIZE bytes in BUF. */
182 hash_bytes (const void *buf_, size_t size)
184 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
185 const unsigned char *buf = buf_;
188 ASSERT (buf != NULL);
192 hash = (hash * FNV_32_PRIME) ^ *buf++;
197 /* Returns a hash of string S. */
199 hash_string (const char *s_)
201 const unsigned char *s = s_;
208 hash = (hash * FNV_32_PRIME) ^ *s++;
213 /* Returns a hash of integer I. */
217 return hash_bytes (&i, sizeof i);
220 /* Returns the bucket in H that E belongs in. */
222 find_bucket (struct hash *h, hash_elem *e)
224 size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
225 return &h->buckets[bucket_idx];
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)
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))
241 /* Returns X with its lowest-order bit set to 1 turned off. */
243 turn_off_least_1bit (size_t x)
248 /* Returns true if X is a power of 2, otherwise false. */
250 is_power_of_2 (size_t x)
252 return x != 0 && turn_off_least_1bit (x) == 0;
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. */
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. */
265 rehash (struct hash *h)
267 size_t old_bucket_cnt, new_bucket_cnt;
268 struct list *new_buckets, *old_buckets;
273 /* Save old bucket info for later use. */
274 old_buckets = h->buckets;
275 old_bucket_cnt = h->bucket_cnt;
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)
284 while (!is_power_of_2 (new_bucket_cnt))
285 new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
287 /* Don't do anything if the bucket count wouldn't change. */
288 if (new_bucket_cnt == old_bucket_cnt)
291 /* Allocate new buckets and initialize them as empty. */
292 new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
293 if (new_buckets == NULL)
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. */
300 for (i = 0; i < new_bucket_cnt; i++)
301 list_init (&new_buckets[i]);
303 /* Install new bucket info. */
304 h->buckets = new_buckets;
305 h->bucket_cnt = new_bucket_cnt;
307 /* Move each old element into the appropriate new bucket. */
308 for (i = 0; i < old_bucket_cnt; i++)
310 struct list *old_bucket;
311 struct list_elem *elem, *next;
313 old_bucket = &old_buckets[i];
314 for (elem = list_begin (old_bucket);
315 elem != list_end (old_bucket); elem = next)
317 struct list *new_bucket = find_bucket (h, elem);
318 next = list_next (elem);
319 list_push_front (new_bucket, elem);
324 /* Inserts E into BUCKET (in hash table H).
325 Rehashes if this increases elems/bucket above
326 MAX_ELEMS_PER_BUCKET. */
328 insert_elem (struct hash *h, struct list *bucket, hash_elem *e)
331 if (h->elem_cnt > h->bucket_cnt * MAX_ELEMS_PER_BUCKET)
333 list_push_front (bucket, e);
336 /* Removes E from hash table H.
337 Rehashes if this decreases elems/bucket below
338 MIN_ELEMS_PER_BUCKET. */
340 remove_elem (struct hash *h, hash_elem *e)
343 if (h->elem_cnt < h->bucket_cnt * MIN_ELEMS_PER_BUCKET)