4 static struct list *find_bucket (struct hash *, hash_elem *);
5 static struct list_elem *find_elem (struct hash *, struct list *, hash_elem *);
6 static void insert_elem (struct hash *, struct list *, hash_elem *);
7 static void remove_elem (struct hash *, hash_elem *);
8 static void rehash (struct hash *);
10 /* Initializes hash table H to compute hash values using HASH and
11 compare hash elements using LESS, given auxiliary data AUX. */
13 hash_init (struct hash *h,
14 hash_hash_func *hash, hash_less_func *less, void *aux)
18 h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
23 if (h->buckets != NULL)
32 /* Removes all the elements from H. */
34 hash_clear (struct hash *h)
38 for (i = 0; i < h->bucket_cnt; h++)
39 list_init (&h->buckets[i]);
43 /* Destroys hash table H. */
45 hash_destroy (struct hash *h)
50 /* Inserts NEW into hash table H and returns a null pointer, if
51 no equal element is already in the table.
52 If an equal element is already in the table, returns it
53 without inserting NEW. */
55 hash_insert (struct hash *h, hash_elem *new)
57 struct list *bucket = find_bucket (h, new);
58 struct list_elem *old = find_elem (h, bucket, new);
61 insert_elem (h, bucket, new);
65 /* Inserts NEW into hash table H, replacing any equal element
66 already in the table, which is returned. */
68 hash_replace (struct hash *h, hash_elem *new)
70 struct list *bucket = find_bucket (h, new);
71 struct list_elem *old = find_elem (h, bucket, new);
76 insert_elem (h, bucket, new);
80 /* Finds and returns an element equal to E in hash table H, or a
81 null pointer if no equal element exists in the table. */
83 hash_find (struct hash *h, hash_elem *e)
85 return find_elem (h, find_bucket (h, e), e);
88 /* Finds, removes, and returns an element equal to E in hash
89 table H. Returns a null pointer if no equal element existed
92 hash_delete (struct hash *h, hash_elem *e)
94 struct list_elem *found = find_elem (h, find_bucket (h, e), e);
96 remove_elem (h, found);
100 /* Initializes I for iterating hash table H.
104 struct hash_iterator i;
107 while (hash_next (&i, h))
109 struct foo *f = list_entry (hash_cur (&i), struct foo, elem);
110 ...do something with f...
113 NOTE: Modifying a hash table during iteration invalidates all
117 hash_first (struct hash_iterator *i, struct hash *h)
123 i->bucket = i->hash->buckets;
124 i->elem = list_head (i->bucket);
127 /* Advances I to the next element in the hash table and returns
128 it. Returns a null pointer if no elements are left. Elements
129 are returned in arbitrary order.
131 NOTE: Modifying a hash table during iteration invalidates all
134 hash_next (struct hash_iterator *i)
138 i->elem = list_next (i->elem);
139 while (i->elem == list_end (i->bucket))
141 if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
146 i->elem = list_begin (i->bucket);
152 /* Returns the current element in the hash table iteration, or a
153 null pointer at the end of the table. Undefined behavior
154 after calling hash_first() but before hash_next(). */
156 hash_cur (struct hash_iterator *i)
161 /* Returns the number of elements in H. */
163 hash_size (struct hash *h)
168 /* Returns true if H contains no elements, false otherwise. */
170 hash_empty (struct hash *h)
172 return h->elem_cnt == 0;
175 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
176 #define FNV_32_PRIME 16777619u
177 #define FNV_32_BASIS 2166136261u
179 /* Returns a hash of the SIZE bytes in BUF. */
181 hash_bytes (const void *buf_, size_t size)
183 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
184 const unsigned char *buf = buf_;
187 ASSERT (buf != NULL);
191 hash = (hash * FNV_32_PRIME) ^ *buf++;
196 /* Returns a hash of string S. */
198 hash_string (const char *s_)
200 const unsigned char *s = s_;
207 hash = (hash * FNV_32_PRIME) ^ *s++;
212 /* Returns a hash of integer I. */
216 return hash_bytes (&i, sizeof i);
219 /* Returns the bucket in H that E belongs in. */
221 find_bucket (struct hash *h, hash_elem *e)
223 size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
224 return &h->buckets[bucket_idx];
227 /* Searches BUCKET in H for a hash element equal to E. Returns
228 it if found or a null pointer otherwise. */
229 static struct list_elem *
230 find_elem (struct hash *h, struct list *bucket, hash_elem *e)
234 for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
235 if (!h->less (i, e, h->aux) && !h->less (e, i, h->aux))
240 /* Returns X with its lowest-order bit set to 1 turned off. */
242 turn_off_least_1bit (size_t x)
247 /* Returns true if X is a power of 2, otherwise false. */
249 is_power_of_2 (size_t x)
251 return x != 0 && turn_off_least_1bit (x) == 0;
254 /* Element per bucket ratios. */
255 #define MIN_ELEMS_PER_BUCKET 1 /* Elems/bucket < 1: reduce # of buckets. */
256 #define BEST_ELEMS_PER_BUCKET 2 /* Ideal elems/bucket. */
257 #define MAX_ELEMS_PER_BUCKET 4 /* Elems/bucket > 4: increase # of buckets. */
259 /* Changes the number of buckets in hash table H to match the
260 ideal. This function can fail because of an out-of-memory
261 condition, but that'll just make hash accesses less efficient;
262 we can still continue. */
264 rehash (struct hash *h)
266 size_t old_bucket_cnt, new_bucket_cnt;
267 struct list *new_buckets, *old_buckets;
272 /* Save old bucket info for later use. */
273 old_buckets = h->buckets;
274 old_bucket_cnt = h->bucket_cnt;
276 /* Calculate the number of buckets to use now.
277 We want one bucket for about every BEST_ELEMS_PER_BUCKET.
278 We must have at least four buckets, and the number of
279 buckets must be a power of 2. */
280 new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
281 if (new_bucket_cnt < 4)
283 while (!is_power_of_2 (new_bucket_cnt))
284 new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
286 /* Don't do anything if the bucket count wouldn't change. */
287 if (new_bucket_cnt == old_bucket_cnt)
290 /* Allocate new buckets and initialize them as empty. */
291 new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
292 if (new_buckets == NULL)
294 /* Allocation failed. This means that use of the hash table will
295 be less efficient. However, it is still usable, so
296 there's no reason for it to be an error. */
299 for (i = 0; i < new_bucket_cnt; i++)
300 list_init (&new_buckets[i]);
302 /* Install new bucket info. */
303 h->buckets = new_buckets;
304 h->bucket_cnt = new_bucket_cnt;
306 /* Move each old element into the appropriate new bucket. */
307 for (i = 0; i < old_bucket_cnt; i++)
309 struct list *old_bucket;
310 struct list_elem *elem, *next;
312 old_bucket = &old_buckets[i];
313 for (elem = list_begin (old_bucket);
314 elem != list_end (old_bucket); elem = next)
316 struct list *new_bucket = find_bucket (h, elem);
317 next = list_next (elem);
318 list_push_front (new_bucket, elem);
323 /* Inserts E into BUCKET (in hash table H).
324 Rehashes if this increases elems/bucket above
325 MAX_ELEMS_PER_BUCKET. */
327 insert_elem (struct hash *h, struct list *bucket, hash_elem *e)
330 if (h->elem_cnt > h->bucket_cnt * MAX_ELEMS_PER_BUCKET)
332 list_push_front (bucket, e);
335 /* Removes E from hash table H.
336 Rehashes if this decreases elems/bucket below
337 MIN_ELEMS_PER_BUCKET. */
339 remove_elem (struct hash *h, hash_elem *e)
342 if (h->elem_cnt < h->bucket_cnt * MIN_ELEMS_PER_BUCKET)