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 /*** INTERNAL PROTOTYPES ***/ 49 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); 52 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); 61 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); 72 73 /*** CONSTRUCTOR ***/ 74 75 /* 76 * Create a new dictionary with the given number of buckets. 77 */ 78 struct aura_dict * 79 aura_dict_new(size_t num_buckets, int method) 80 { 81 struct aura_dict *d; 82 size_t i; 83 84 AURA_MALLOC(d, aura_dict); 85 86 d->num_buckets = num_buckets; 87 d->b = malloc(sizeof(struct bucket *) * num_buckets); 88 for (i = 0; i < num_buckets; i++) { 89 d->b[i] = NULL; 90 } 91 d->cursor = NULL; 92 d->cur_bucket = 0; 93 94 switch (method) { 95 case AURA_DICT_HASH: 96 d->fetch = aura_dict_fetch_hash; 97 d->store = aura_dict_store_hash; 98 break; 99 case AURA_DICT_LIST: 100 d->fetch = aura_dict_fetch_list; 101 d->store = aura_dict_store_list; 102 break; 103 case AURA_DICT_SORTED_LIST: 104 d->fetch = aura_dict_fetch_list; 105 d->store = aura_dict_store_list_sorted; 106 break; 107 } 108 109 return(d); 110 } 111 112 /*** DESTRUCTORS ***/ 113 114 void 115 aura_bucket_free(struct aura_bucket *b) 116 { 117 if (b == NULL) 118 return; 119 if (b->key != NULL) 120 free(b->key); 121 if (b->data != NULL) 122 free(b->data); 123 AURA_FREE(b, aura_bucket); 124 } 125 126 void 127 aura_dict_free(struct aura_dict *d) 128 { 129 struct aura_bucket *b; 130 size_t bucket_no = 0; 131 132 while (bucket_no < d->num_buckets) { 133 b = d->b[bucket_no]; 134 while (b != NULL) { 135 d->b[bucket_no] = b->next; 136 aura_bucket_free(b); 137 b = d->b[bucket_no]; 138 } 139 bucket_no++; 140 } 141 AURA_FREE(d, aura_dict); 142 } 143 144 /*** UTILITIES ***/ 145 146 /* 147 * Hash function, taken from "Compilers: Principles, Techniques, and Tools" 148 * by Aho, Sethi, & Ullman (a.k.a. "The Dragon Book", 2nd edition.) 149 */ 150 size_t 151 hashpjw(const void *key, size_t key_size, size_t table_size) { 152 const char *k = (const char *)key; 153 const char *p; 154 size_t h = 0, g; 155 156 for (p = k; p < k + key_size; p++) { 157 h = (h << 4) + (*p); 158 if ((g = h & 0xf0000000)) 159 h = (h ^ (g >> 24)) ^ g; 160 } 161 162 return(h % table_size); 163 } 164 165 /* 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. 169 */ 170 struct aura_bucket * 171 aura_bucket_new(const void *key, size_t key_size, const void *data, size_t data_size) 172 { 173 struct aura_bucket *b; 174 175 AURA_MALLOC(b, aura_bucket); 176 177 b->next = NULL; 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; 184 185 return(b); 186 } 187 188 /* 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.) 191 */ 192 void 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) 195 { 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) 199 break; 200 } 201 } 202 203 /* 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.) 206 */ 207 void 208 aura_dict_locate_list(struct aura_dict *d, const void *key, size_t key_size, 209 struct aura_bucket **b) 210 { 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) 213 break; 214 } 215 } 216 217 /*** IMPLEMENTATIONS ***/ 218 219 /***** HASH TABLE *****/ 220 221 void 222 aura_dict_fetch_hash(struct aura_dict *d, const void *key, size_t key_size, 223 void **data, size_t *data_size) 224 { 225 struct aura_bucket *b; 226 size_t i; 227 228 aura_dict_locate_hash(d, key, key_size, &i, &b); 229 if (b != NULL) { 230 *data = b->data; 231 *data_size = b->data_size; 232 } else { 233 *data = NULL; 234 } 235 } 236 237 void 238 aura_dict_store_hash(struct aura_dict *d, const void *key, size_t key_size, 239 const void *data, size_t data_size) 240 { 241 struct aura_bucket *b; 242 size_t i; 243 244 aura_dict_locate_hash(d, key, key_size, &i, &b); 245 if (b == NULL) { 246 /* Bucket does not exist, add a new one. */ 247 b = aura_bucket_new(key, key_size, data, data_size); 248 b->next = d->b[i]; 249 d->b[i] = b; 250 } else { 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; 256 } 257 } 258 259 /***** LIST *****/ 260 261 void 262 aura_dict_fetch_list(struct aura_dict *d, const void *key, size_t key_size, 263 void **data, size_t *data_size) 264 { 265 struct aura_bucket *b; 266 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) { 269 *data = b->data; 270 *data_size = b->data_size; 271 return; 272 } 273 } 274 *data = NULL; 275 } 276 277 void 278 aura_dict_store_list(struct aura_dict *d, const void *key, size_t key_size, 279 const void *data, size_t data_size) 280 { 281 struct aura_bucket *b; 282 283 aura_dict_locate_list(d, key, key_size, &b); 284 if (b == NULL) { 285 /* Bucket does not exist, add a new one. */ 286 b = aura_bucket_new(key, key_size, data, data_size); 287 b->next = d->b[0]; 288 d->b[0] = b; 289 } else { 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; 295 } 296 } 297 298 /***** SORTED LIST *****/ 299 300 int 301 keycmp(const void *key, size_t key_size, struct aura_bucket *b) 302 { 303 int r; 304 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) 308 return(-1); 309 if (key_size > b->key_size) 310 return(1); 311 return(0); 312 } 313 return(r); 314 } 315 316 void 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) 319 { 320 struct aura_bucket *b, *new_b, *prev = NULL; 321 int added = 0; 322 323 /* XXX could be more efficient. */ 324 aura_dict_locate_list(d, key, key_size, &b); 325 if (b == NULL) { 326 new_b = aura_bucket_new(key, key_size, data, data_size); 327 if (d->b[0] == NULL) { 328 /* 329 * Special case: insert at head 330 * if bucket is empty. 331 */ 332 new_b->next = NULL; 333 d->b[0] = new_b; 334 } else { 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) { 338 if (prev != NULL) 339 prev->next = new_b; 340 else 341 d->b[0] = new_b; 342 new_b->next = b; 343 added = 1; 344 break; 345 } 346 prev = b; 347 } 348 if (!added) { 349 prev->next = new_b; 350 new_b->next = NULL; 351 } 352 } 353 } else { 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; 359 } 360 } 361 362 /*** INTERFACE ***/ 363 364 /* 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. 368 */ 369 void 370 aura_dict_fetch(struct aura_dict *d, const void *key, size_t key_size, 371 void **data, size_t *data_size) 372 { 373 d->fetch(d, key, key_size, data, data_size); 374 } 375 376 int 377 aura_dict_exists(struct aura_dict *d, const void *key, size_t key_size) 378 { 379 void *data; 380 size_t data_size; 381 382 d->fetch(d, key, key_size, &data, &data_size); 383 return(data != NULL); 384 } 385 386 /* 387 * Insert a value into a dictionary, if it does not exist. 388 */ 389 void 390 aura_dict_store(struct aura_dict *d, const void *key, size_t key_size, 391 const void *data, size_t data_size) 392 { 393 d->store(d, key, key_size, data, data_size); 394 } 395 396 /* 397 * Finds the next bucket with data in it. 398 * If d->cursor == NULL after this, there is no more data. 399 */ 400 void 401 aura_dict_advance(struct aura_dict *d) 402 { 403 while (d->cursor == NULL) { 404 if (d->cur_bucket == d->num_buckets - 1) { 405 /* We're at eof. Do nothing. */ 406 break; 407 } else { 408 d->cur_bucket++; 409 d->cursor = d->b[d->cur_bucket]; 410 } 411 } 412 } 413 414 void 415 aura_dict_rewind(struct aura_dict *d) 416 { 417 d->cur_bucket = 0; 418 d->cursor = d->b[d->cur_bucket]; 419 aura_dict_advance(d); 420 } 421 422 int 423 aura_dict_eof(struct aura_dict *d) 424 { 425 return(d->cursor == NULL); 426 } 427 428 void 429 aura_dict_get_current_key(struct aura_dict *d, void **key, size_t *key_size) 430 { 431 if (d->cursor == NULL) { 432 *key = NULL; 433 } else { 434 *key = d->cursor->key; 435 *key_size = d->cursor->key_size; 436 } 437 } 438 439 void 440 aura_dict_next(struct aura_dict *d) 441 { 442 if (d->cursor != NULL) 443 d->cursor = d->cursor->next; 444 aura_dict_advance(d); 445 } 446 447 size_t 448 aura_dict_size(struct aura_dict *d) 449 { 450 struct aura_bucket *b; 451 size_t bucket_no = 0; 452 size_t count = 0; 453 454 while (bucket_no < d->num_buckets) { 455 b = d->b[bucket_no]; 456 while (b != NULL) { 457 b = b->next; 458 count++; 459 } 460 bucket_no++; 461 } 462 463 return(count); 464 } 465