2 * Copyright 1993, 1995 Christopher Seiwald.
4 * This file is part of Jam - see jam.c for Copyright information.
8 * hash.c - simple in-memory hashing routines
12 * hashinit() - initialize a hash table, returning a handle
13 * hashitem() - find a record in the table, and optionally enter a new one
14 * hashdone() - free a hash table, given its handle
18 * hashrehash() - resize and rebuild hp->tab, the hash table
20 * 4/29/93 - ensure ITEM's are aligned
21 * 11/04/02 (seiwald) - const-ing for string literals
22 * 01/31/02 (seiwald) - keyval now unsigned (cray-ziness)
28 /* header attached to all data items entered into a hash table. */
31 unsigned int keyval
; /* for quick comparisons */
35 /* this structure overlays the one handed to hashenter() */
36 /* it's actual size is given to hashinit() */
39 /* rest of user data */
49 #define MAX_LISTS (32)
51 /* the hash table, just an array of item pointers */
56 int bloat
; /* tab.nel / items.nel */
57 int inel
; /* initial number of elements */
58 /* the array of records, maintained by these routines essentially a microallocator */
60 int more
; /* how many more ITEMs fit in lists[ list ] */
61 char *next
; /* where to put more ITEMs in lists[ list ] */
62 int datalen
; /* length of records in this hash table */
63 int size
; /* sizeof(ITEM) + aligned datalen */
64 int nel
; /* total ITEMs held by all lists[] */
65 int list
; /* index into lists[] */
67 int nel
; /* total ITEMs held by this list */
68 char *base
; /* base of ITEMs array */
71 const char *name
; /* just for hashstats() */
75 #define ALIGNED(x) ((x+sizeof(ITEM)-1)&(~(sizeof(ITEM)-1)))
78 static void hashstat (struct hash
*hp
) {
79 ITEM
**tab
= hp
->tab
.base
;
80 int nel
= hp
->tab
.nel
;
83 int run
= (tab
[nel
-1] != (ITEM
*)0);
86 for (i
= nel
; i
> 0; --i
) {
87 if ((here
= (*tab
++ != (ITEM
*)0))) ++count
;
88 if (here
&& !run
) ++sets
;
92 printf("%s table: %d+%d+%d (%dK+%dK) items+table+hash, density: count=%d; sets=%d\n",
97 hp
->items
.nel
*hp
->items
.size
/1024,
98 (int)(hp
->tab
.nel
*sizeof(ITEM
**)/1024),
102 printf("%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
107 hp
->items
.nel
*hp
->items
.size
/1024,
108 (int)(hp
->tab
.nel
*sizeof(ITEM
**)/1024),
109 (float)count
/(float)sets
116 * hashrehash() - resize and rebuild hp->tab, the hash table
118 static void hashrehash (struct hash
*hp
) {
119 int i
= ++hp
->items
.list
;
121 hp
->items
.more
= i
? 2*hp
->items
.nel
: hp
->inel
;
122 hp
->items
.next
= (char *)malloc(hp
->items
.more
*hp
->items
.size
);
124 hp
->items
.lists
[i
].nel
= hp
->items
.more
;
125 hp
->items
.lists
[i
].base
= hp
->items
.next
;
126 hp
->items
.nel
+= hp
->items
.more
;
128 if (hp
->tab
.base
) free((char *)hp
->tab
.base
);
130 hp
->tab
.nel
= hp
->items
.nel
*hp
->bloat
;
131 hp
->tab
.base
= (ITEM
**)malloc(hp
->tab
.nel
*sizeof(ITEM
**));
133 memset((char *)hp
->tab
.base
, '\0', hp
->tab
.nel
*sizeof(ITEM
*));
135 for (i
= 0; i
< hp
->items
.list
; ++i
) {
136 int nel
= hp
->items
.lists
[i
].nel
;
137 char *next
= hp
->items
.lists
[i
].base
;
139 for (; nel
--; next
+= hp
->items
.size
) {
140 ITEM
*i
= (ITEM
*)next
;
141 ITEM
**ip
= hp
->tab
.base
+i
->hdr
.keyval
%hp
->tab
.nel
;
149 int hashiterate (struct hash
*hp
, HashIteratorCB itercb
, void *udata
) {
150 ITEM
**tab
= hp
->tab
.base
;
153 for (i
= hp
->tab
.nel
; i
> 0; --i
, ++tab
) {
155 int res
= itercb(&((*tab
)->data
), udata
);
165 * hashitem() - find a record in the table, and optionally enter a new one
167 int hashitem (struct hash
*hp
, HASHDATA
**data
, int enter
) {
170 unsigned char *b
= (unsigned char *)(*data
)->key
;
173 if (enter
&& !hp
->items
.more
) hashrehash(hp
);
174 if (!enter
&& !hp
->items
.nel
) return 0;
176 while (*b
) keyval
= keyval
*2147059363 + *b
++;
177 base
= hp
->tab
.base
+(keyval
%hp
->tab
.nel
);
178 for (i
= *base
; i
; i
= i
->hdr
.next
) {
179 if (keyval
== i
->hdr
.keyval
&& !strcmp(i
->data
.key
, (*data
)->key
)) {
185 i
= (ITEM
*)hp
->items
.next
;
186 hp
->items
.next
+= hp
->items
.size
;
188 memcpy((char *)&i
->data
, (char *)*data
, hp
->items
.datalen
);
189 i
->hdr
.keyval
= keyval
;
199 * hashinit() - initialize a hash table, returning a handle
201 struct hash
*hashinit (int datalen
, const char *name
) {
202 struct hash
*hp
= (struct hash
*)malloc(sizeof(*hp
));
206 hp
->tab
.base
= (ITEM
**)0;
208 hp
->items
.datalen
= datalen
;
209 hp
->items
.size
= sizeof(struct hashhdr
)+ALIGNED(datalen
);
219 * hashdone() - free a hash table, given its handle
221 void hashdone (struct hash
*hp
) {
225 if (DEBUG_MEM
) hashstat(hp
);
226 if (hp
->tab
.base
) free((char *)hp
->tab
.base
);
227 for (i
= 0; i
<= hp
->items
.list
; i
++) free(hp
->items
.lists
[i
].base
);