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 * 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 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 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 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 * 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 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 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 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 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 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 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 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 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 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 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 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 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 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 422 aura_dict_eof(struct aura_dict *d) 423 { 424 return(d->cursor == NULL); 425 } 426 427 void 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 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 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