5 hash_init (struct hash *h,
6 hash_less_func *less, hash_hash_func *hash, void *aux)
10 h->buckets = malloc (sizeof *h->buckets * h->bucket_cnt);
15 if (h->buckets != NULL)
25 find_bucket (struct hash *h, hash_elem *e)
27 size_t bucket_idx = h->hash (e, h->aux) & (h->bucket_cnt - 1);
28 return h->buckets[bucket_idx];
32 find_elem (struct list *bucket, hash_elem *e)
36 for (i = list_begin (bucket); i != list_end (bucket); i = list_next (i))
43 turn_off_least_1bit (size_t x)
49 is_power_of_2 (size_t x)
51 return turn_off_least_1bit (x) == 0;
54 #define MIN_ELEMS_PER_BUCKET 1
55 #define BEST_ELEMS_PER_BUCKET 2
56 #define MAX_ELEMS_PER_BUCKET 4
59 rehash (struct hash *h)
61 size_t old_bucket_cnt, new_bucket_cnt;
62 struct list *new_buckets, *old_buckets;
67 /* Save old bucket info for later use. */
68 old_buckets = h->buckets;
69 old_bucket_cnt = h->bucket_cnt;
71 /* Calculate the number of buckets to use now.
72 We want one bucket for about every BEST_ELEMS_PER_BUCKET.
73 We must have at least four buckets, and the number of
74 buckets must be a power of 2. */
75 new_bucket_cnt = h->elem_cnt / BEST_ELEMS_PER_BUCKET;
76 if (new_bucket_cnt < 4)
78 while (!is_power_of_2 (new_bucket_cnt))
79 new_bucket_cnt = turn_off_least_1bit (new_bucket_cnt);
81 /* Don't do anything if the bucket count doesn't change. */
82 if (new_bucket_cnt == old_bucket_cnt)
85 /* Allocate new buckets and initialize them as empty. */
86 new_buckets = malloc (sizeof *new_buckets * new_bucket_cnt);
87 if (new_buckets == NULL)
89 /* Allocation failed. This means that use of the hash table will
90 be less efficient. However, it is still usable, so
91 there's no reason for it to be an error. */
94 for (i = 0; i < new_bucket_cnt; i++)
95 list_init (&new_buckets[i]);
97 /* Install new bucket info. */
98 h->buckets = new_buckets;
99 h->bucket_cnt = new_bucket_cnt;
101 /* Move each old element into the appropriate new bucket. */
102 for (i = 0; i < old_bucket_cnt; i++)
104 struct list *old_bucket, *new_bucket;
105 struct list_elem *elem, *next;
107 old_bucket = &old_buckets[i];
108 for (elem = list_begin (old_bucket);
109 elem != list_end (old_bucket); elem = next)
111 struct list *new_bucket = find_bucket (h, e);
112 next = list_next (elem);
113 list_push_front (new_bucket, elem);
119 insert_elem (struct list *bucket, hash_elem *e)
122 if (h->elem_cnt > h->bucket_cnt * MAX_ELEMS_PER_BUCKET)
124 list_push_front (bucket, e);
128 remove_elem (struct hash *h, hash_elem *e)
131 if (h->elem_cnt < h->bucket_cnt * MIN_ELEMS_PER_BUCKET)
137 hash_insert (struct hash *h, hash_elem *new)
139 struct list *bucket = find_bucket (h, new);
140 struct list_elem *old = find_elem (bucket, new);
143 insert_elem (bucket, new);
148 hash_replace (struct hash *h, hash_elem *new)
150 struct list *bucket = find_bucket (h, new);
151 struct list_elem *old = find_elem (bucket, new);
154 remove_elem (h, old);
156 insert_elem (bucket, new);
161 hash_find (struct hash *h, hash_elem *e)
163 struct list *bucket = find_bucket (h, e);
164 return find_elem (bucket, new);
168 hash_delete (struct hash *h, hash_elem *target)
170 struct list *bucket = find_bucket (h, e);
171 struct list_elem *found = find_elem (bucket, new);
173 remove_elem (h, found);
178 hash_clear (struct hash *h)
182 for (i = 0; i < h->bucket_cnt; h++)
183 list_init (&h->buckets[i]);
188 hash_first (struct hash_iterator *i, struct hash *h)
191 i->bucket = i->hash->buckets;
192 i->elem = list_begin (*i->bucket);
196 hash_next (struct hash_iterator *i)
198 ASSERT (i->elem != NULL);
200 i->elem = list_next (i->elem);
201 while (i->elem == list_end (*i->bucket))
202 if (++i->bucket >= i->hash->buckets + i->hash->bucket_cnt)
212 hash_cur (struct hash_iterator *i)
217 size_t hash_size (struct hash *h)
223 hash_empty (struct hash *h)
225 return h->elem_cnt == 0;
228 /* Fowler-Noll-Vo hash constants, for 32-bit word sizes. */
229 #define FNV_32_PRIME 16777619u
230 #define FNV_32_BASIS 2166136261u
232 /* Fowler-Noll-Vo 32-bit hash, for bytes. */
234 hsh_hash_bytes (const void *buf_, size_t size)
236 const unsigned char *buf = buf_;
239 assert (buf != NULL);
243 hash = (hash * FNV_32_PRIME) ^ *buf++;
248 /* Fowler-Noll-Vo 32-bit hash, for strings. */
250 hash_string (const char *s_)
252 const unsigned char *s = s_;
259 hash = (hash * FNV_32_PRIME) ^ *s++;
268 return hsh_hash_bytes (&i, sizeof i);