2 * Copyright (c) 2000-2001
3 * The Regents of the University of California. All rights reserved.
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
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.
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
37 #define UB(n) ((1<<n)-1)
39 #define INITIAL_TABLE_SIZE 8 /* the initial table size is 2^8 */
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 */
44 typedef struct hash_entry *hash_entry;
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;
60 struct term_bucket *next;
63 #define scan_term_bucket(b,var) for(var = b; var; var = var->next)
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 */
71 term_bucket * term_buckets;
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);
87 static const int primes[] =
88 { 83, 1789, 5189, 5449, 5659, 6703, 7517, 7699, 8287, 8807, 9067, 9587,
91 static const int prime_1 = 83;
92 static const int prime_2 = 1789;
94 static const int initial_table_size = INITIAL_TABLE_SIZE;
96 term_hash make_term_hash(region rgn)
103 term_hash tab = ralloc(rgn, struct term_hash);
106 ub = UB(initial_table_size);
107 n = CAP(initial_table_size);
110 tab->term_buckets = rarrayalloc(r, n, term_bucket);
112 for (i = 0; i < n; i++)
114 tab->term_buckets[i] = NULL;
119 tab->size = initial_table_size;
125 void term_hash_delete(term_hash tab) deletes
127 deleteregion(tab->rgn);
130 gen_e term_hash_find(term_hash tab, stamp stamps[], int len)
135 hash_val = hash(tab->ub, stamps, len);
136 b = tab->term_buckets[hash_val];
137 return walk(b, stamps, len);
140 static gen_e walk(term_bucket b, stamp stamps[], int len)
143 scan_term_bucket(b,cur)
145 if (len == cur->entry->length
146 && (memcmp(stamps, cur->entry->stamps, sizeof(int)*len) == 0) )
147 return cur->entry->e;
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
157 if (term_hash_find(tab, stamps, len) != NULL)
161 insert(tab, e, stamps, len);
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)
176 entry = ralloc(tab->rgn, struct hash_entry);
178 stamp_cpy = rarrayalloc(tab->rgn, len, stamp);
179 for (i = 0; i < len; i++)
181 stamp_cpy[i] = stamps[i];
185 entry->stamps = stamp_cpy;
187 insert_entry(tab, entry);
190 static void insert_entry(term_hash tab, hash_entry entry)
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);
199 new_term_bucket->entry = entry;
200 new_term_bucket->next = b;
201 tab->term_buckets[hash_val] = new_term_bucket;
204 static void post_insert(term_hash tab) deletes
206 if (tab->capacity == ++tab->inserts)
212 /* Double the size of the hash table and reinsert all of the elements. */
213 static void rehash(term_hash tab) deletes
216 term_bucket * old_term_buckets;
218 int old_table_size = tab->capacity;
220 old_term_buckets = tab->term_buckets;
222 tab->ub = UB(++tab->size);
224 tab->rgn = newregion();
227 tab->term_buckets = rarrayalloc(tab->rgn, tab->capacity, term_bucket);
228 for (i = 0; i < old_table_size; i++)
230 if (old_term_buckets[i] != NULL && old_term_buckets[i]->entry != NULL)
231 reinsert(tab, old_term_buckets[i]);
234 deleteregion(old_rgn);
239 static void reinsert(term_hash tab, term_bucket b)
242 scan_term_bucket(b,cur)
243 insert(tab, cur->entry->e, cur->entry->stamps, cur->entry->length);
246 static int hash(int ub, stamp stamps[], int len)
251 for (i = 0; i < len; i++)
253 n = (n + (primes[i % 15] * abs(stamps[i]))) & ub;