2 * Copyright (c) 2004 The DragonFly Project. All rights reserved.
4 * This code is derived from software contributed to The DragonFly Project
5 * by Chris Pressey <cpressey@catseye.mine.nu>.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * 1. Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * 3. Neither the name of The DragonFly Project nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific, prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED
29 * AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
30 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
31 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * $Id: dict.c,v 1.4 2005/02/06 06:57:30 cpressey Exp $
38 * Routines to manipulate dictionaries.
48 /*** INTERNAL PROTOTYPES ***/
50 size_t hashpjw(const void *key, size_t key_size, size_t table_size);
51 int keycmp(const void *key, size_t key_size, struct aura_bucket *b);
53 struct aura_bucket *aura_bucket_new(const void *key, size_t key_size,
54 const void *data, size_t data_size);
55 void aura_bucket_free(struct aura_bucket *b);
56 void aura_dict_locate_hash(struct aura_dict *d, const void *key, size_t key_size,
57 size_t *b_index, struct aura_bucket **b);
58 void aura_dict_locate_list(struct aura_dict *d, const void *key, size_t key_size,
59 struct aura_bucket **b);
60 void aura_dict_advance(struct aura_dict *d);
62 void aura_dict_fetch_hash(struct aura_dict *d, const void *key, size_t key_size,
63 void **data, size_t *data_size);
64 void aura_dict_store_hash(struct aura_dict *d, const void *key, size_t key_size,
65 const void *data, size_t data_size);
66 void aura_dict_fetch_list(struct aura_dict *d, const void *key, size_t key_size,
67 void **data, size_t *data_size);
68 void aura_dict_store_list(struct aura_dict *d, const void *key, size_t key_size,
69 const void *data, size_t data_size);
70 void aura_dict_store_list_sorted(struct aura_dict *d, const void *key, size_t key_size,
71 const void *data, size_t data_size);
76 * Create a new dictionary with the given number of buckets.
79 aura_dict_new(size_t num_buckets, int method)
84 AURA_MALLOC(d, aura_dict);
86 d->num_buckets = num_buckets;
87 d->b = malloc(sizeof(struct bucket *) * num_buckets);
88 for (i = 0; i < num_buckets; i++) {
96 d->fetch = aura_dict_fetch_hash;
97 d->store = aura_dict_store_hash;
100 d->fetch = aura_dict_fetch_list;
101 d->store = aura_dict_store_list;
103 case AURA_DICT_SORTED_LIST:
104 d->fetch = aura_dict_fetch_list;
105 d->store = aura_dict_store_list_sorted;
112 /*** DESTRUCTORS ***/
115 aura_bucket_free(struct aura_bucket *b)
123 AURA_FREE(b, aura_bucket);
127 aura_dict_free(struct aura_dict *d)
129 struct aura_bucket *b;
130 size_t bucket_no = 0;
132 while (bucket_no < d->num_buckets) {
135 d->b[bucket_no] = b->next;
141 AURA_FREE(d, aura_dict);
147 * Hash function, taken from "Compilers: Principles, Techniques, and Tools"
148 * by Aho, Sethi, & Ullman (a.k.a. "The Dragon Book", 2nd edition.)
151 hashpjw(const void *key, size_t key_size, size_t table_size) {
152 const char *k = (const char *)key;
156 for (p = k; p < k + key_size; p++) {
158 if ((g = h & 0xf0000000))
159 h = (h ^ (g >> 24)) ^ g;
162 return(h % table_size);
166 * Create a new bucket (not called directly by client code.)
167 * Uses a copy of key and data for the bucket, so the dictionary
168 * code is responsible for cleaning it up itself.
171 aura_bucket_new(const void *key, size_t key_size, const void *data, size_t data_size)
173 struct aura_bucket *b;
175 AURA_MALLOC(b, aura_bucket);
178 b->key = aura_malloc(key_size, "dictionary key");
179 memcpy(b->key, key, key_size);
180 b->key_size = key_size;
181 b->data = aura_malloc(data_size, "dictionary value");
182 memcpy(b->data, data, data_size);
183 b->data_size = data_size;
189 * Locate the bucket number a particular key would be located in, and the
190 * bucket itself if such a key exists (or NULL if it could not be found.)
193 aura_dict_locate_hash(struct aura_dict *d, const void *key, size_t key_size,
194 size_t *b_index, struct aura_bucket **b)
196 *b_index = hashpjw(key, key_size, d->num_buckets);
197 for (*b = d->b[*b_index]; *b != NULL; *b = (*b)->next) {
198 if (key_size == (*b)->key_size && memcmp(key, (*b)->key, key_size) == 0)
204 * Locate the bucket a particular key would be located in
205 * if such a key exists (or NULL if it could not be found.)
208 aura_dict_locate_list(struct aura_dict *d, const void *key, size_t key_size,
209 struct aura_bucket **b)
211 for (*b = d->b[0]; *b != NULL; *b = (*b)->next) {
212 if (key_size == (*b)->key_size && memcmp(key, (*b)->key, key_size) == 0)
217 /*** IMPLEMENTATIONS ***/
219 /***** HASH TABLE *****/
222 aura_dict_fetch_hash(struct aura_dict *d, const void *key, size_t key_size,
223 void **data, size_t *data_size)
225 struct aura_bucket *b;
228 aura_dict_locate_hash(d, key, key_size, &i, &b);
231 *data_size = b->data_size;
238 aura_dict_store_hash(struct aura_dict *d, const void *key, size_t key_size,
239 const void *data, size_t data_size)
241 struct aura_bucket *b;
244 aura_dict_locate_hash(d, key, key_size, &i, &b);
246 /* Bucket does not exist, add a new one. */
247 b = aura_bucket_new(key, key_size, data, data_size);
251 /* Bucket already exists, replace the value. */
252 aura_free(b->data, "dictionary value");
253 b->data = aura_malloc(data_size, "dictionary value");
254 memcpy(b->data, data, data_size);
255 b->data_size = data_size;
262 aura_dict_fetch_list(struct aura_dict *d, const void *key, size_t key_size,
263 void **data, size_t *data_size)
265 struct aura_bucket *b;
267 for (b = d->b[0]; b != NULL; b = b->next) {
268 if (key_size == b->key_size && memcmp(key, b->key, key_size) == 0) {
270 *data_size = b->data_size;
278 aura_dict_store_list(struct aura_dict *d, const void *key, size_t key_size,
279 const void *data, size_t data_size)
281 struct aura_bucket *b;
283 aura_dict_locate_list(d, key, key_size, &b);
285 /* Bucket does not exist, add a new one. */
286 b = aura_bucket_new(key, key_size, data, data_size);
290 /* Bucket already exists, replace the value. */
291 aura_free(b->data, "dictionary value");
292 b->data = aura_malloc(data_size, "dictionary value");
293 memcpy(b->data, data, data_size);
294 b->data_size = data_size;
298 /***** SORTED LIST *****/
301 keycmp(const void *key, size_t key_size, struct aura_bucket *b)
305 if ((r = memcmp(key, b->key,
306 b->key_size < key_size ? b->key_size : key_size)) == 0) {
307 if (key_size < b->key_size)
309 if (key_size > b->key_size)
317 aura_dict_store_list_sorted(struct aura_dict *d, const void *key, size_t key_size,
318 const void *data, size_t data_size)
320 struct aura_bucket *b, *new_b, *prev = NULL;
323 /* XXX could be more efficient. */
324 aura_dict_locate_list(d, key, key_size, &b);
326 new_b = aura_bucket_new(key, key_size, data, data_size);
327 if (d->b[0] == NULL) {
329 * Special case: insert at head
330 * if bucket is empty.
335 for (b = d->b[0]; b != NULL; b = b->next) {
336 /* XXX if identical - no need for above fetch */
337 if (keycmp(key, key_size, b) < 0) {
354 /* Bucket already exists, replace the value. */
355 aura_free(b->data, "dictionary value");
356 b->data = aura_malloc(data_size, "dictionary value");
357 memcpy(b->data, data, data_size);
358 b->data_size = data_size;
365 * Retrieve a value from a dictionary, give its key. The value and its
366 * size are returned in *data and *data_size. If no value could be
367 * found, *data is set to NULL.
370 aura_dict_fetch(struct aura_dict *d, const void *key, size_t key_size,
371 void **data, size_t *data_size)
373 d->fetch(d, key, key_size, data, data_size);
377 aura_dict_exists(struct aura_dict *d, const void *key, size_t key_size)
382 d->fetch(d, key, key_size, &data, &data_size);
383 return(data != NULL);
387 * Insert a value into a dictionary, if it does not exist.
390 aura_dict_store(struct aura_dict *d, const void *key, size_t key_size,
391 const void *data, size_t data_size)
393 d->store(d, key, key_size, data, data_size);
397 * Finds the next bucket with data in it.
398 * If d->cursor == NULL after this, there is no more data.
401 aura_dict_advance(struct aura_dict *d)
403 while (d->cursor == NULL) {
404 if (d->cur_bucket == d->num_buckets - 1) {
405 /* We're at eof. Do nothing. */
409 d->cursor = d->b[d->cur_bucket];
415 aura_dict_rewind(struct aura_dict *d)
418 d->cursor = d->b[d->cur_bucket];
419 aura_dict_advance(d);
423 aura_dict_eof(struct aura_dict *d)
425 return(d->cursor == NULL);
429 aura_dict_get_current_key(struct aura_dict *d, void **key, size_t *key_size)
431 if (d->cursor == NULL) {
434 *key = d->cursor->key;
435 *key_size = d->cursor->key_size;
440 aura_dict_next(struct aura_dict *d)
442 if (d->cursor != NULL)
443 d->cursor = d->cursor->next;
444 aura_dict_advance(d);
448 aura_dict_size(struct aura_dict *d)
450 struct aura_bucket *b;
451 size_t bucket_no = 0;
454 while (bucket_no < d->num_buckets) {