libbanshee/engine/termhash.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 "termhash.h"
  33 #include "hash.h"
  34 #include "termhash.h"
  35 #include "util.h"
  36
  37 #define UB(n) ((1<<n)-1)
  38 #define CAP(n) (1<<n)
  39 #define INITIAL_TABLE_SIZE 8 /* the initial table size is 2^8 */
  40
  41 /*  An individual entry in the table consists of an array of stamps  */
  42 /*  (same arity as the expr's constructor) in addition to the expr */
  43 /*  itself. */
  44 typedef struct hash_entry *hash_entry;
  45
  46 /*  A term_bucket is a list of entries (an list of exprs that have  */
  47 /*  collided after hashing) */
  48 typedef struct term_bucket *term_bucket;
  49
  50 struct hash_entry
  51 {
  52   int length;
  53   stamp *stamps;
  54   gen_e e;
  55 };
  56
  57 struct term_bucket
  58 {
  59   hash_entry entry;
  60   struct term_bucket *next;
  61 };
  62
  63 #define scan_term_bucket(b,var) for(var = b; var; var = var->next)
  64
  65 /*  size: initial_table_size + number of rehashes */
  66 /*  capacity: 2^size (for array size) */
  67 /*  ub: 2^size-1 (for array indexing) */
  68 /*  inserts: num of elements inserted into the array */
  69 struct term_hash
  70 {
  71   term_bucket * term_buckets;
  72   region rgn;
  73   int ub;
  74   int size;
  75   int capacity;
  76   int inserts;
  77 };
  78
  79 static int hash(int ub, stamp stamps[], int len);
  80 static void post_insert(term_hash tab) deletes;
  81 static void rehash(term_hash tab) deletes;
  82 static void reinsert(term_hash tab, term_bucket b);
  83 static void insert(term_hash tab, gen_e e, stamp * stamps, int len);
  84 static void insert_entry(term_hash tab, struct hash_entry *entry);
  85 static gen_e walk(term_bucket b, stamp * stamps, int len);
  86
  87 static const int primes[] =
  88   { 83, 1789, 5189, 5449, 5659, 6703, 7517, 7699, 8287, 8807, 9067, 9587,
  89     10627, 10939, 11239};
  90 /*
  91 static const int prime_1 = 83;
  92 static const int prime_2 = 1789;
  93 */
  94 static const int initial_table_size = INITIAL_TABLE_SIZE;
  95
  96 term_hash make_term_hash(region rgn)
  97 {
  98   int ub, n;
  99   int i;
 100
 101   region r;
 102
 103   term_hash tab = ralloc(rgn, struct term_hash);
 104
 105   r = newregion();
 106   ub = UB(initial_table_size);
 107   n = CAP(initial_table_size);
 108
 109
 110   tab->term_buckets = rarrayalloc(r, n, term_bucket);
 111
 112   for (i = 0; i < n; i++)
 113     {
 114       tab->term_buckets[i] = NULL;
 115     }
 116
 117   tab->rgn = r;
 118   tab->ub = ub;
 119   tab->size = initial_table_size;
 120   tab->capacity = n;
 121   tab->inserts = 0;
 122   return tab;
 123 }
 124
 125 void term_hash_delete(term_hash tab) deletes
 126 {
 127   deleteregion(tab->rgn);
 128 }
 129
 130 gen_e term_hash_find(term_hash tab, stamp stamps[], int len)
 131 {
 132   int hash_val;
 133
 134   term_bucket b;
 135   hash_val = hash(tab->ub, stamps, len);
 136   b = tab->term_buckets[hash_val];
 137   return walk(b, stamps, len);
 138 }
 139
 140 static gen_e walk(term_bucket b, stamp stamps[], int len)
 141 {
 142   term_bucket cur;
 143   scan_term_bucket(b,cur)
 144     {
 145       if (len == cur->entry->length
 146           && (memcmp(stamps, cur->entry->stamps, sizeof(int)*len) == 0) )
 147         return cur->entry->e;
 148     }
 149   return NULL;
 150 }
 151
 152 /*  Should call t_hash_find to see if a gen_e with the given stamp  */
 153 /*  signature is already in the table. If so, insert should return */
 154 /*  true and do nothing. */
 155 bool term_hash_insert(term_hash tab, gen_e e, stamp * stamps, int len) deletes
 156 {
 157   if (term_hash_find(tab, stamps, len) != NULL)
 158     {
 159       return TRUE;
 160     }
 161   insert(tab, e, stamps, len);
 162   post_insert(tab);
 163   return FALSE;
 164 }
 165
 166
 167 /*  Insert an expression e represented by the given stamp array into */
 168 /*  the hash table. */
 169 static void insert(term_hash tab, gen_e e, stamp stamps[], int len)
 170 {
 171   hash_entry entry;
 172   stamp * stamp_cpy;
 173   int i;
 174
 175
 176   entry = ralloc(tab->rgn, struct hash_entry);
 177
 178   stamp_cpy = rarrayalloc(tab->rgn, len, stamp);
 179   for (i = 0; i < len; i++)
 180     {
 181       stamp_cpy[i] = stamps[i];
 182     }
 183
 184   entry->length = len;
 185   entry->stamps = stamp_cpy;
 186   entry->e = e;
 187   insert_entry(tab, entry);
 188 }
 189
 190 static void insert_entry(term_hash tab, hash_entry entry)
 191 {
 192   int hash_val;
 193
 194   term_bucket b, new_term_bucket;
 195   hash_val = hash(tab->ub, entry->stamps, entry->length);
 196   b = tab->term_buckets[hash_val];
 197   new_term_bucket = ralloc(tab->rgn, struct term_bucket);
 198
 199   new_term_bucket->entry = entry;
 200   new_term_bucket->next = b;
 201   tab->term_buckets[hash_val] = new_term_bucket;
 202 }
 203
 204 static void post_insert(term_hash tab) deletes
 205 {
 206   if (tab->capacity == ++tab->inserts)
 207     {
 208       rehash(tab);
 209     }
 210 }
 211
 212 /*  Double the size of the hash table and reinsert all of the elements. */
 213 static void rehash(term_hash tab) deletes
 214 {
 215   region old_rgn;
 216   term_bucket * old_term_buckets;
 217   int i;
 218   int old_table_size = tab->capacity;
 219
 220   old_term_buckets = tab->term_buckets;
 221   tab->capacity *= 2;
 222   tab->ub = UB(++tab->size);
 223   old_rgn = tab->rgn;
 224   tab->rgn = newregion();
 225
 226
 227   tab->term_buckets = rarrayalloc(tab->rgn, tab->capacity, term_bucket);
 228   for (i = 0; i < old_table_size; i++)
 229     {
 230       if (old_term_buckets[i] != NULL && old_term_buckets[i]->entry != NULL)
 231         reinsert(tab, old_term_buckets[i]);
 232     }
 233
 234   deleteregion(old_rgn);
 235
 236
 237 }
 238
 239 static void reinsert(term_hash tab, term_bucket b)
 240 {
 241   term_bucket cur;
 242   scan_term_bucket(b,cur)
 243     insert(tab, cur->entry->e, cur->entry->stamps, cur->entry->length);
 244 }
 245
 246 static int hash(int ub, stamp stamps[], int len)
 247 {
 248   int i, n;
 249
 250   n = 0;
 251   for (i = 0; i < len; i++)
 252     {
 253       n = (n + (primes[i % 15] * abs(stamps[i]))) & ub;
 254     }
 255   return n;
 256 }
 257
 258
 259
 260
 261
 262