libbanshee/engine/hash.c

   1 /*
   2  * Copyright (c) 2000-2001
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  * 3. Neither the name of the University nor the names of its contributors
  14  *    may be used to endorse or promote products derived from this software
  15  *    without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  *
  29  */
  30
  31 #include <string.h>
  32 #include "hash.h"
  33 #include "util.h"
  34
  35 struct bucket
  36 {
  37   hash_key key;
  38   hash_data data;
  39   struct bucket *next;
  40 };
  41
  42 #define scan_bucket(b, var) for (var = b; var; var = var->next)
  43
  44 struct Hash_table
  45 {
  46   region r;          /* Region for this table */
  47   hash_fn hash;      /* Function for hashing keys */
  48   keyeq_fn cmp;      /* Function for comparing keys */
  49
  50   int size;          /* Number of buckets */
  51   int elts;          /* Number of elements */
  52   bool internal_rgn; /* TRUE if the ht uses an internal region */
  53   bucket *table;     /* Array of (size) buckets */
  54 };
  55
  56 static void rehash(hash_table ht) deletes;
  57
  58 /* Make a new hash table, with size buckets initially.  The actual
  59    table is allocated in a local region, which is discarded on rehashing. */
  60 hash_table make_hash_table(region r, int size, hash_fn hash,
  61                            keyeq_fn cmp, bool internal_rgn)
  62 {
  63   hash_table result;
  64
  65   assert(size > 0);
  66   result = ralloc(r, struct Hash_table);
  67
  68   if (internal_rgn)
  69     result->r = newregion();
  70   else
  71     result->r = r;
  72
  73   result->internal_rgn = internal_rgn;
  74   result->hash = hash;
  75   result->cmp = cmp;
  76   result->size = size;
  77   result->elts = 0;
  78   result->table = rarrayalloc(result->r, size, bucket);
  79
  80   return result;
  81 }
  82
  83 /* Hash a string */
  84 static int string_hash(char *str)
  85 {
  86   char *c;
  87   int h;
  88
  89   c = str;
  90   h = 0;
  91   if (!c)
  92     return 0;
  93   while (*c)
  94     h = 33*h + 720 + *c++; /* SML/NJ's string hash function */
  95   return h;
  96 }
  97
  98 /* Return TRUE iff s1 == s2 */
  99 static bool string_eq(char *s1, char *s2)
 100 {
 101   return !strcmp(s1, s2);
 102 }
 103
 104 /* Make a hash table for strings. */
 105 hash_table make_string_hash_table(region rhash, int size, bool internal_rgn)
 106 {
 107   return make_hash_table(rhash, size, (hash_fn) string_hash,
 108                          (keyeq_fn) string_eq,internal_rgn);
 109 }
 110
 111 /* Zero out ht.  Doesn't reclaim bucket space. */
 112 void hash_table_reset(hash_table ht) deletes
 113 {
 114   int i;
 115
 116   if (ht->internal_rgn)
 117     {
 118       deleteregion(ht->r);
 119       ht->r = newregion();
 120     }
 121
 122   ht->elts = 0;
 123   for (i = 0; i < ht->size; i++)
 124     ht->table[i] = NULL;
 125 }
 126
 127 void hash_table_delete(hash_table ht) deletes
 128 {
 129   if (ht->internal_rgn)
 130     deleteregion(ht->r);
 131 }
 132
 133
 134 /* Return the number of entries in ht */
 135 int hash_table_size(hash_table ht)
 136 {
 137   return ht->elts;
 138 }
 139
 140 /* Return the bucket corresponding to k in ht */
 141 static inline bucket *find_bucket(hash_table ht, hash_key k)
 142 {
 143   int hash;
 144
 145   hash = ht->hash(k);
 146   if (hash < 0)
 147     hash = -1*hash;
 148   return &ht->table[hash % ht->size];
 149 }
 150
 151 /* Lookup k in ht.  Returns corresponding data in *d, and function
 152    result is TRUE if the k was in ht, false otherwise. */
 153 bool hash_table_lookup(hash_table ht, hash_key k, hash_data *d)
 154 {
 155   bucket cur;
 156
 157   cur = *find_bucket(ht, k);
 158   while (cur)
 159     {
 160       if (ht->cmp(k, cur->key))
 161         {
 162           if (d)
 163             *d = cur->data;
 164           return TRUE;
 165         }
 166       cur = cur->next;
 167     }
 168   return FALSE;
 169 }
 170
 171
 172 /* Add k:d to ht.  If k was already in ht, replace old entry by k:d.
 173    Rehash if necessary.  Returns TRUE if k was not already in ht. */
 174 bool hash_table_insert(hash_table ht, hash_key k, hash_data d) deletes
 175 {
 176   bucket *cur;
 177
 178   if (ht->elts > ht->size*15)
 179     rehash(ht);
 180   cur = find_bucket(ht, k);
 181   while (*cur)
 182     {
 183       if (ht->cmp(k, (*cur)->key))
 184         {
 185           (*cur)->data = d;
 186           return FALSE; /* Replace */
 187         }
 188       cur = &(*cur)->next;
 189     }
 190   *cur = ralloc(ht->r, struct bucket);
 191   (*cur)->key = k;
 192   (*cur)->data = d;
 193   (*cur)->next = NULL;
 194   ht->elts++;
 195   return TRUE; /* New key */
 196 }
 197
 198 /* Remove mapping for k in ht.  Returns TRUE if k was in ht. */
 199 bool hash_table_remove(hash_table ht, hash_key k)
 200 {
 201   bucket *cur;
 202   bucket *prev = NULL;
 203
 204   cur = find_bucket(ht, k);
 205   while (*cur)
 206     {
 207       if (ht->cmp(k, (*cur)->key))
 208         {
 209           if (!*prev)
 210             (*prev)->next = (*cur)->next;
 211           else
 212             *cur = NULL;
 213           ht->elts--;
 214           return TRUE;
 215         }
 216       prev = cur;
 217       cur = &(*cur)->next;
 218     }
 219   return FALSE;
 220 }
 221
 222 /* Return a copy of ht */
 223 hash_table hash_table_copy(region r, hash_table ht)
 224 {
 225   int i;
 226   hash_table result;
 227   bucket cur, newbucket, *prev;
 228
 229   result = make_hash_table(r, ht->size, ht->hash, ht->cmp,ht->internal_rgn);
 230   result->elts = ht->elts;
 231
 232   for (i = 0; i < ht->size; i++)
 233     {
 234       prev = &result->table[i];
 235       scan_bucket(ht->table[i], cur)
 236         {
 237           newbucket = ralloc(result->r, struct bucket);
 238           newbucket->key = cur->key;
 239           newbucket->data = cur->data;
 240           newbucket->next = NULL;
 241           assert(!*prev);
 242           *prev = newbucket;
 243           prev = &newbucket->next;
 244         }
 245     }
 246   return result;
 247   /*
 248   hash_table result;
 249   hash_table_scanner hts;
 250   hash_key k;
 251   hash_data d;
 252
 253   result = make_hash_table(r, ht->size, ht->hash, ht->cmp);
 254   hash_table_scan(ht, &hts);
 255   while (hash_table_next(&hts, &k, &d))
 256     insist(hash_table_insert(result, k, d));
 257
 258   return result;
 259   */
 260 }
 261
 262 /* Increase size of ht (double it) and reinsert all the elements */
 263 static void rehash(hash_table ht) deletes
 264 {
 265   int old_table_size, i;
 266   bucket *old_table, cur;
 267   region old_region;
 268
 269 #ifdef DEBUG
 270   printf("Rehash table size=%d, elts=%d\n", ht->size, ht->elts);
 271 #endif
 272
 273   old_table_size = ht->size;
 274   old_table = ht->table;
 275   old_region = ht->r;
 276
 277   if (ht->internal_rgn)
 278     ht->r = newregion();
 279
 280   ht->size = ht->size*2;
 281   ht->elts = 0;
 282   ht->table = rarrayalloc(ht->r, ht->size, bucket);
 283
 284   for (i = 0; i < old_table_size; i++)
 285     scan_bucket(old_table[i], cur)
 286       insist(hash_table_insert(ht, cur->key, cur->data));
 287
 288   if (ht->internal_rgn)
 289     deleteregion(old_region);
 290 }
 291
 292 /* Begin scanning ht */
 293 void hash_table_scan(hash_table ht, hash_table_scanner *hts)
 294 {
 295   hts->ht = ht;
 296   hts->i = 0;
 297   hts->cur = hts->ht->table[0];
 298 }
 299
 300 /* Get next elt in table, storing the elt in *k and *d if k and d are
 301    non-NULL, respectively.  Returns TRUE if there is a next elt, FALSE
 302    otherwise. */
 303 bool hash_table_next(hash_table_scanner *hts, hash_key *k, hash_data *d)
 304 {
 305   while (hts->cur == NULL)
 306     {
 307       hts->i++;
 308       if (hts->i < hts->ht->size)
 309         hts->cur = hts->ht->table[hts->i];
 310       else
 311         break;
 312     }
 313
 314   if (hts->i == hts->ht->size)
 315     {
 316       return FALSE;
 317     }
 318   else
 319     {
 320       if (k)
 321         *k = hts->cur->key;
 322       if (d)
 323         *d = hts->cur->data;
 324       hts->cur = hts->cur->next;
 325     }
 326   return TRUE;
 327 }
 328
 329 /* Apply f to all elements of ht, in some arbitrary order */
 330 void hash_table_apply(hash_table ht, hash_apply_fn f, void *arg)
 331 {
 332   int i;
 333   bucket cur;
 334
 335   for (i = 0; i < ht->size; i++)
 336     scan_bucket(ht->table[i], cur)
 337       f(cur->key, cur->data, arg);
 338 }
 339
 340 /* Map f to all elements on ht, creating a new hash table */
 341 hash_table hash_table_map(hash_table ht, hash_map_fn f, void *arg)
 342 {
 343   int i;
 344   hash_table result;
 345   bucket cur, newbucket, *prev;
 346
 347   result = make_hash_table(ht->r, ht->size, ht->hash, ht->cmp,ht->internal_rgn);
 348   result->elts = ht->elts;
 349
 350   for (i = 0; i < ht->size; i++)
 351     {
 352       prev = &result->table[i];
 353       scan_bucket(ht->table[i], cur)
 354         {
 355           newbucket = ralloc(ht->r, struct bucket);
 356           newbucket->key = cur->key;
 357           newbucket->data = f(cur->key, cur->data, arg);
 358           newbucket->next = NULL;
 359           assert(!*prev);
 360           *prev = newbucket;
 361           prev = &newbucket->next;
 362         }
 363     }
 364   return result;
 365   /*
 366   hash_table result;
 367   int i;
 368   bucket cur;
 369
 370   result = make_hash_table(ht->r, ht->size, ht->hash, ht->cmp);
 371   for (i = 0; i < ht->size; i++)
 372     scan_bucket(ht->table[i], cur)
 373       insist(hash_table_insert(result, cur->key, f(cur->key, cur->data, arg)));
 374   return result;
 375   */
 376 }
 377
 378 static keycmp_fn cur_cmp = NULL;
 379
 380 static int entry_cmp(const void *a, const void *b)
 381 {
 382   struct sorted_entry *ae = (struct sorted_entry *) a;
 383   struct sorted_entry *be = (struct sorted_entry *) b;
 384   return cur_cmp(ae->k, be->k);
 385 }
 386
 387 /* Begin scanning ht in sorted order according to f */
 388 void hash_table_scan_sorted(hash_table ht, keycmp_fn f,
 389                             hash_table_scanner_sorted *htss)
 390 {
 391   hash_table_scanner hts;
 392   int i;
 393
 394   htss->r = newregion();
 395   htss->size = hash_table_size(ht);
 396   htss->entries = rarrayalloc(htss->r, htss->size, struct sorted_entry);
 397   htss->i = 0;
 398
 399   hash_table_scan(ht, &hts);
 400   i = 0;
 401   while (hash_table_next(&hts, &htss->entries[i].k,
 402                          &htss->entries[i].d))
 403     i++;
 404   assert(i == htss->size);
 405   cur_cmp = f;
 406   qsort(htss->entries, htss->size, sizeof(struct sorted_entry), entry_cmp);
 407   cur_cmp = NULL;
 408 }
 409
 410 /* Just like hash_table_next, but scans in sorted order */
 411 bool hash_table_next_sorted(hash_table_scanner_sorted *htss, hash_key *k,
 412                             hash_data *d) deletes
 413 {
 414   if (htss->i < htss->size)
 415     {
 416       *k = htss->entries[htss->i].k;
 417       *d = htss->entries[htss->i].d;
 418       htss->i++;
 419       return TRUE;
 420     }
 421   else
 422     {
 423       deleteregion(htss->r);
 424       htss->r = NULL;
 425       return FALSE;
 426     }
 427 }