1 /*
2 * Copyright (c) 2004 The DragonFly Project. All rights reserved.
3 *
4 * This code is derived from software contributed to The DragonFly Project
5 * by Chris Pressey <cpressey@catseye.mine.nu>.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
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
16 * distribution.
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.
20 *
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
32 * SUCH DAMAGE.
33 */
34
35 /*
36 * dict.c
37 * $Id: dict.c,v 1.4 2005/02/06 06:57:30 cpressey Exp $
38 * Routines to manipulate dictionaries.
39 */
40
41 #include <stdlib.h>
42 #include <string.h>
43
44 #include "mem.h"
45
46 #include "dict.h"
47
48 void aura_dict_locate_hash(struct aura_dict *d, const void *key, size_t key_size,
49 size_t *b_index, struct aura_bucket **b);
50 void aura_dict_locate_list(struct aura_dict *d, const void *key, size_t key_size,
51 struct aura_bucket **b);
52 void aura_dict_advance(struct aura_dict *d);
53
54 static void aura_dict_fetch_hash(struct aura_dict *d, const void *key, size_t key_size,
55 void **data, size_t *data_size);
56 static void aura_dict_store_hash(struct aura_dict *d, const void *key, size_t key_size,
57 const void *data, size_t data_size);
58 static void aura_dict_fetch_list(struct aura_dict *d, const void *key, size_t key_size,
59 void **data, size_t *data_size);
60 static void aura_dict_store_list(struct aura_dict *d, const void *key, size_t key_size,
61 const void *data, size_t data_size);
62 static void aura_dict_store_list_sorted(struct aura_dict *d, const void *key, size_t key_size,
63 const void *data, size_t data_size);
64
65 /*** CONSTRUCTOR ***/
66
67 /*
68 * Create a new dictionary with the given number of buckets.
69 */
70 struct aura_dict *
aura_dict_new(size_t num_buckets,int method)71 aura_dict_new(size_t num_buckets, int method)
72 {
73 struct aura_dict *d;
74 size_t i;
75
76 AURA_MALLOC(d, aura_dict);
77
78 switch (method) {
79 case AURA_DICT_HASH:
80 d->fetch = aura_dict_fetch_hash;
81 d->store = aura_dict_store_hash;
82 break;
83 case AURA_DICT_LIST:
84 d->fetch = aura_dict_fetch_list;
85 d->store = aura_dict_store_list;
86 break;
87 case AURA_DICT_SORTED_LIST:
88 d->fetch = aura_dict_fetch_list;
89 d->store = aura_dict_store_list_sorted;
90 break;
91 default:
92 AURA_FREE(d, aura_dict);
93 return NULL;
94 }
95
96 d->num_buckets = num_buckets;
97 d->b = malloc(sizeof(struct bucket *) * num_buckets);
98 if (d->b == NULL) {
99 AURA_FREE(d, aura_dict);
100 return NULL;
101 }
102 for (i = 0; i < num_buckets; i++) {
103 d->b[i] = NULL;
104 }
105 d->cursor = NULL;
106 d->cur_bucket = 0;
107
108 return(d);
109 }
110
111 /*** DESTRUCTORS ***/
112
113 static void
aura_bucket_free(struct aura_bucket * b)114 aura_bucket_free(struct aura_bucket *b)
115 {
116 if (b == NULL)
117 return;
118 if (b->key != NULL)
119 free(b->key);
120 if (b->data != NULL)
121 free(b->data);
122 AURA_FREE(b, aura_bucket);
123 }
124
125 void
aura_dict_free(struct aura_dict * d)126 aura_dict_free(struct aura_dict *d)
127 {
128 struct aura_bucket *b;
129 size_t bucket_no = 0;
130
131 while (bucket_no < d->num_buckets) {
132 b = d->b[bucket_no];
133 while (b != NULL) {
134 d->b[bucket_no] = b->next;
135 aura_bucket_free(b);
136 b = d->b[bucket_no];
137 }
138 bucket_no++;
139 }
140 AURA_FREE(d, aura_dict);
141 }
142
143 /*** UTILITIES ***/
144
145 /*
146 * Hash function, taken from "Compilers: Principles, Techniques, and Tools"
147 * by Aho, Sethi, & Ullman (a.k.a. "The Dragon Book", 2nd edition.)
148 */
149 static size_t
hashpjw(const void * key,size_t key_size,size_t table_size)150 hashpjw(const void *key, size_t key_size, size_t table_size) {
151 const char *k = (const char *)key;
152 const char *p;
153 size_t h = 0, g;
154
155 for (p = k; p < k + key_size; p++) {
156 h = (h << 4) + (*p);
157 if ((g = h & 0xf0000000))
158 h = (h ^ (g >> 24)) ^ g;
159 }
160
161 return(h % table_size);
162 }
163
164 /*
165 * Create a new bucket (not called directly by client code.)
166 * Uses a copy of key and data for the bucket, so the dictionary
167 * code is responsible for cleaning it up itself.
168 */
169 static struct aura_bucket *
aura_bucket_new(const void * key,size_t key_size,const void * data,size_t data_size)170 aura_bucket_new(const void *key, size_t key_size, const void *data, size_t data_size)
171 {
172 struct aura_bucket *b;
173
174 AURA_MALLOC(b, aura_bucket);
175
176 b->next = NULL;
177 b->key = aura_malloc(key_size, "dictionary key");
178 memcpy(b->key, key, key_size);
179 b->key_size = key_size;
180 b->data = aura_malloc(data_size, "dictionary value");
181 memcpy(b->data, data, data_size);
182 b->data_size = data_size;
183
184 return(b);
185 }
186
187 /*
188 * Locate the bucket number a particular key would be located in, and the
189 * bucket itself if such a key exists (or NULL if it could not be found.)
190 */
191 void
aura_dict_locate_hash(struct aura_dict * d,const void * key,size_t key_size,size_t * b_index,struct aura_bucket ** b)192 aura_dict_locate_hash(struct aura_dict *d, const void *key, size_t key_size,
193 size_t *b_index, struct aura_bucket **b)
194 {
195 *b_index = hashpjw(key, key_size, d->num_buckets);
196 for (*b = d->b[*b_index]; *b != NULL; *b = (*b)->next) {
197 if (key_size == (*b)->key_size && memcmp(key, (*b)->key, key_size) == 0)
198 break;
199 }
200 }
201
202 /*
203 * Locate the bucket a particular key would be located in
204 * if such a key exists (or NULL if it could not be found.)
205 */
206 void
aura_dict_locate_list(struct aura_dict * d,const void * key,size_t key_size,struct aura_bucket ** b)207 aura_dict_locate_list(struct aura_dict *d, const void *key, size_t key_size,
208 struct aura_bucket **b)
209 {
210 for (*b = d->b[0]; *b != NULL; *b = (*b)->next) {
211 if (key_size == (*b)->key_size && memcmp(key, (*b)->key, key_size) == 0)
212 break;
213 }
214 }
215
216 /*** IMPLEMENTATIONS ***/
217
218 /***** HASH TABLE *****/
219
220 static void
aura_dict_fetch_hash(struct aura_dict * d,const void * key,size_t key_size,void ** data,size_t * data_size)221 aura_dict_fetch_hash(struct aura_dict *d, const void *key, size_t key_size,
222 void **data, size_t *data_size)
223 {
224 struct aura_bucket *b;
225 size_t i;
226
227 aura_dict_locate_hash(d, key, key_size, &i, &b);
228 if (b != NULL) {
229 *data = b->data;
230 *data_size = b->data_size;
231 } else {
232 *data = NULL;
233 }
234 }
235
236 static void
aura_dict_store_hash(struct aura_dict * d,const void * key,size_t key_size,const void * data,size_t data_size)237 aura_dict_store_hash(struct aura_dict *d, const void *key, size_t key_size,
238 const void *data, size_t data_size)
239 {
240 struct aura_bucket *b;
241 size_t i;
242
243 aura_dict_locate_hash(d, key, key_size, &i, &b);
244 if (b == NULL) {
245 /* Bucket does not exist, add a new one. */
246 b = aura_bucket_new(key, key_size, data, data_size);
247 b->next = d->b[i];
248 d->b[i] = b;
249 } else {
250 /* Bucket already exists, replace the value. */
251 aura_free(b->data, "dictionary value");
252 b->data = aura_malloc(data_size, "dictionary value");
253 memcpy(b->data, data, data_size);
254 b->data_size = data_size;
255 }
256 }
257
258 /***** LIST *****/
259
260 static void
aura_dict_fetch_list(struct aura_dict * d,const void * key,size_t key_size,void ** data,size_t * data_size)261 aura_dict_fetch_list(struct aura_dict *d, const void *key, size_t key_size,
262 void **data, size_t *data_size)
263 {
264 struct aura_bucket *b;
265
266 for (b = d->b[0]; b != NULL; b = b->next) {
267 if (key_size == b->key_size && memcmp(key, b->key, key_size) == 0) {
268 *data = b->data;
269 *data_size = b->data_size;
270 return;
271 }
272 }
273 *data = NULL;
274 }
275
276 static void
aura_dict_store_list(struct aura_dict * d,const void * key,size_t key_size,const void * data,size_t data_size)277 aura_dict_store_list(struct aura_dict *d, const void *key, size_t key_size,
278 const void *data, size_t data_size)
279 {
280 struct aura_bucket *b;
281
282 aura_dict_locate_list(d, key, key_size, &b);
283 if (b == NULL) {
284 /* Bucket does not exist, add a new one. */
285 b = aura_bucket_new(key, key_size, data, data_size);
286 b->next = d->b[0];
287 d->b[0] = b;
288 } else {
289 /* Bucket already exists, replace the value. */
290 aura_free(b->data, "dictionary value");
291 b->data = aura_malloc(data_size, "dictionary value");
292 memcpy(b->data, data, data_size);
293 b->data_size = data_size;
294 }
295 }
296
297 /***** SORTED LIST *****/
298
299 static int
keycmp(const void * key,size_t key_size,struct aura_bucket * b)300 keycmp(const void *key, size_t key_size, struct aura_bucket *b)
301 {
302 int r;
303
304 if ((r = memcmp(key, b->key,
305 b->key_size < key_size ? b->key_size : key_size)) == 0) {
306 if (key_size < b->key_size)
307 return(-1);
308 if (key_size > b->key_size)
309 return(1);
310 return(0);
311 }
312 return(r);
313 }
314
315 static void
aura_dict_store_list_sorted(struct aura_dict * d,const void * key,size_t key_size,const void * data,size_t data_size)316 aura_dict_store_list_sorted(struct aura_dict *d, const void *key, size_t key_size,
317 const void *data, size_t data_size)
318 {
319 struct aura_bucket *b, *new_b, *prev = NULL;
320 int added = 0;
321
322 /* XXX could be more efficient. */
323 aura_dict_locate_list(d, key, key_size, &b);
324 if (b == NULL) {
325 new_b = aura_bucket_new(key, key_size, data, data_size);
326 if (d->b[0] == NULL) {
327 /*
328 * Special case: insert at head
329 * if bucket is empty.
330 */
331 new_b->next = NULL;
332 d->b[0] = new_b;
333 } else {
334 for (b = d->b[0]; b != NULL; b = b->next) {
335 /* XXX if identical - no need for above fetch */
336 if (keycmp(key, key_size, b) < 0) {
337 if (prev != NULL)
338 prev->next = new_b;
339 else
340 d->b[0] = new_b;
341 new_b->next = b;
342 added = 1;
343 break;
344 }
345 prev = b;
346 }
347 if (!added) {
348 prev->next = new_b;
349 new_b->next = NULL;
350 }
351 }
352 } else {
353 /* Bucket already exists, replace the value. */
354 aura_free(b->data, "dictionary value");
355 b->data = aura_malloc(data_size, "dictionary value");
356 memcpy(b->data, data, data_size);
357 b->data_size = data_size;
358 }
359 }
360
361 /*** INTERFACE ***/
362
363 /*
364 * Retrieve a value from a dictionary, give its key. The value and its
365 * size are returned in *data and *data_size. If no value could be
366 * found, *data is set to NULL.
367 */
368 void
aura_dict_fetch(struct aura_dict * d,const void * key,size_t key_size,void ** data,size_t * data_size)369 aura_dict_fetch(struct aura_dict *d, const void *key, size_t key_size,
370 void **data, size_t *data_size)
371 {
372 d->fetch(d, key, key_size, data, data_size);
373 }
374
375 int
aura_dict_exists(struct aura_dict * d,const void * key,size_t key_size)376 aura_dict_exists(struct aura_dict *d, const void *key, size_t key_size)
377 {
378 void *data;
379 size_t data_size;
380
381 d->fetch(d, key, key_size, &data, &data_size);
382 return(data != NULL);
383 }
384
385 /*
386 * Insert a value into a dictionary, if it does not exist.
387 */
388 void
aura_dict_store(struct aura_dict * d,const void * key,size_t key_size,const void * data,size_t data_size)389 aura_dict_store(struct aura_dict *d, const void *key, size_t key_size,
390 const void *data, size_t data_size)
391 {
392 d->store(d, key, key_size, data, data_size);
393 }
394
395 /*
396 * Finds the next bucket with data in it.
397 * If d->cursor == NULL after this, there is no more data.
398 */
399 void
aura_dict_advance(struct aura_dict * d)400 aura_dict_advance(struct aura_dict *d)
401 {
402 while (d->cursor == NULL) {
403 if (d->cur_bucket == d->num_buckets - 1) {
404 /* We're at eof. Do nothing. */
405 break;
406 } else {
407 d->cur_bucket++;
408 d->cursor = d->b[d->cur_bucket];
409 }
410 }
411 }
412
413 void
aura_dict_rewind(struct aura_dict * d)414 aura_dict_rewind(struct aura_dict *d)
415 {
416 d->cur_bucket = 0;
417 d->cursor = d->b[d->cur_bucket];
418 aura_dict_advance(d);
419 }
420
421 int
aura_dict_eof(struct aura_dict * d)422 aura_dict_eof(struct aura_dict *d)
423 {
424 return(d->cursor == NULL);
425 }
426
427 void
aura_dict_get_current_key(struct aura_dict * d,void ** key,size_t * key_size)428 aura_dict_get_current_key(struct aura_dict *d, void **key, size_t *key_size)
429 {
430 if (d->cursor == NULL) {
431 *key = NULL;
432 } else {
433 *key = d->cursor->key;
434 *key_size = d->cursor->key_size;
435 }
436 }
437
438 void
aura_dict_next(struct aura_dict * d)439 aura_dict_next(struct aura_dict *d)
440 {
441 if (d->cursor != NULL)
442 d->cursor = d->cursor->next;
443 aura_dict_advance(d);
444 }
445
446 size_t
aura_dict_size(struct aura_dict * d)447 aura_dict_size(struct aura_dict *d)
448 {
449 struct aura_bucket *b;
450 size_t bucket_no = 0;
451 size_t count = 0;
452
453 while (bucket_no < d->num_buckets) {
454 b = d->b[bucket_no];
455 while (b != NULL) {
456 b = b->next;
457 count++;
458 }
459 bucket_no++;
460 }
461
462 return(count);
463 }
464