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; i++)
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);
69 /* Inserts NEW into hash table H, replacing any equal element
70 already in the table, which is returned. */
72 hash_replace (struct hash *h, hash_elem *new)
74 struct list *bucket = find_bucket (h, new);
75 struct list_elem *old = find_elem (h, bucket, new);
79 insert_elem (h, bucket, new);
86 /* Finds and returns an element equal to E in hash table H, or a
87 null pointer if no equal element exists in the table. */
89 hash_find (struct hash *h, hash_elem *e)
91 return find_elem (h, find_bucket (h, e), e);
94 /* Finds, removes, and returns an element equal to E in hash
95 table H. Returns a null pointer if no equal element existed
98 hash_delete (struct hash *h, hash_elem *e)
100 struct list_elem *found = find_elem (h, find_bucket (h, e), e);
103 remove_elem (h, found);
109 /* Initializes I for iterating hash table H.
113 struct hash_iterator i;
116 while (hash_next (&i))
118 struct foo *f = hash_entry (hash_cur (&i), struct foo, elem);
119 ...do something with f...
122 NOTE: Modifying a hash table during iteration invalidates all
126 hash_first (struct hash_iterator *i, struct hash *h)
132 i->bucket = i->hash->buckets;
133 i->elem = list_head (i->bucket);
136 /* Advances I to the next element in the hash table and returns
137 it. Returns a null pointer if no elements are left. Elements
138 are returned in arbitrary order.
140 NOTE: Modifying a hash table during iteration invalidates all
143 hash_next (struct hash_iterator *i)
147 i->elem = list_next (i->elem);
148 while (i->elem == list_end (i->bucket))
150 if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
155 i->elem = list_begin (i->bucket);
161 /* Returns the current element in the hash table iteration, or a
162 null pointer at the end of the table. Undefined behavior
163 after calling hash_first() but before hash_next(). */
165 hash_cur (struct hash_iterator *i)
170 /* Returns the number of elements in H. */
172 hash_size (struct hash *h)
177 /* Returns true if H contains no elements, false otherwise. */
179 hash_empty (struct hash *h)
181 return h->elem_cnt == 0;
184 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
185 #define FNV_32_PRIME 16777619u
186 #define FNV_32_BASIS 2166136261u
188 /* Returns a hash of the SIZE bytes in BUF. */
190 hash_bytes (const void *buf_, size_t size)
192 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
193 const unsigned char *buf = buf_;
196 ASSERT (buf != NULL);
200 hash = (hash * FNV_32_PRIME) ^ *buf++;
205 /* Returns a hash of string S. */
207 hash_string (const char *s_)
209 const unsigned char *s = s_;
216 hash = (hash * FNV_32_PRIME) ^ *s++;
221 /* Returns a hash of integer I. */
225 return hash_bytes (&i, sizeof i);
228 /* Returns the bucket in H that E belongs in. */
230 find_bucket (struct hash *h, hash_elem *e)
232 size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
233 return &h->buckets[bucket_idx];
236 /* Searches BUCKET in H for a hash element equal to E. Returns
237 it if found or a null pointer otherwise. */
238 static struct list_elem *
239 find_elem (struct hash *h, struct list *bucket, hash_elem *e)
243 for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
244 if (!h->less (i, e, h->aux) && !h->less (e, i, h->aux))
249 /* Returns X with its lowest-order bit set to 1 turned off. */
251 turn_off_least_1bit (size_t x)
256 /* Returns true if X is a power of 2, otherwise false. */
258 is_power_of_2 (size_t x)
260 return x != 0 && turn_off_least_1bit (x) == 0;
263 /* Element per bucket ratios. */
264 #define MIN_ELEMS_PER_BUCKET 1 /* Elems/bucket < 1: reduce # of buckets. */
265 #define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */
266 #define MAX_ELEMS_PER_BUCKET 4 /* Elems/bucket > 4: increase # of buckets. */
268 /* Changes the number of buckets in hash table H to match the
269 ideal. This function can fail because of an out-of-memory
270 condition, but that'll just make hash accesses less efficient;
271 we can still continue. */
273 rehash (struct hash *h)
275 size_t old_bucket_cnt, new_bucket_cnt;
276 struct list *new_buckets, *old_buckets;
281 /* Save old bucket info for later use. */
282 old_buckets = h->buckets;
283 old_bucket_cnt = h->bucket_cnt;
285 /* Calculate the number of buckets to use now.
286 We want one bucket for about every BEST_ELEMS_PER_BUCKET.
287 We must have at least four buckets, and the number of
288 buckets must be a power of 2. */
289 new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
290 if (new_bucket_cnt < 4)
292 while (!is_power_of_2 (new_bucket_cnt))
293 new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
295 /* Don't do anything if the bucket count wouldn't change. */
296 if (new_bucket_cnt == old_bucket_cnt)
299 /* Allocate new buckets and initialize them as empty. */
300 new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
301 if (new_buckets == NULL)
303 /* Allocation failed. This means that use of the hash table will
304 be less efficient. However, it is still usable, so
305 there's no reason for it to be an error. */
308 for (i = 0; i < new_bucket_cnt; i++)
309 list_init (&new_buckets[i]);
311 /* Install new bucket info. */
312 h->buckets = new_buckets;
313 h->bucket_cnt = new_bucket_cnt;
315 /* Move each old element into the appropriate new bucket. */
316 for (i = 0; i < old_bucket_cnt; i++)
318 struct list *old_bucket;
319 struct list_elem *elem, *next;
321 old_bucket = &old_buckets[i];
322 for (elem = list_begin (old_bucket);
323 elem != list_end (old_bucket); elem = next)
325 struct list *new_bucket = find_bucket (h, elem);
326 next = list_next (elem);
328 list_push_front (new_bucket, elem);
335 /* Inserts E into BUCKET (in hash table H). */
337 insert_elem (struct hash *h, struct list *bucket, hash_elem *e)
340 list_push_front (bucket, e);
343 /* Removes E from hash table H. */
345 remove_elem (struct hash *h, hash_elem *e)