usr.sbin/installer/libaura/dict.c

   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 }