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. */
32 unsigned int keyval
; /* for quick comparisons */
35 /* This structure overlays the one handed to hashenter(). */
36 /* It's actual size is given to hashinit(). */
40 /* rest of user data */
52 * the hash table, just an array of item pointers
59 int bloat
; /* tab.nel / items.nel */
60 int inel
; /* initial number of elements */
63 * the array of records, maintained by these routines
64 * essentially a microallocator
67 int more
; /* how many more ITEMs fit in lists[ list ] */
68 char *next
; /* where to put more ITEMs in lists[ list ] */
69 int datalen
; /* length of records in this hash table */
70 int size
; /* sizeof(ITEM) + aligned datalen */
71 int nel
; /* total ITEMs held by all lists[] */
72 int list
; /* index into lists[] */
75 int nel
; /* total ITEMs held by this list */
76 char *base
; /* base of ITEMs array */
80 const char *name
; /* just for hashstats() */
84 static void hashrehash (struct hash
*hp
);
85 static void hashstat (struct hash
*hp
);
89 * hashitem() - find a record in the table, and optionally enter a new one
91 int hashitem (struct hash
*hp
, HASHDATA
**data
, int enter
) {
94 unsigned char *b
= (unsigned char *)(*data
)->key
;
97 if (enter
&& !hp
->items
.more
) hashrehash(hp
);
98 if (!enter
&& !hp
->items
.nel
) return 0;
100 while (*b
) keyval
= keyval
*2147059363 + *b
++;
101 base
= hp
->tab
.base
+(keyval
%hp
->tab
.nel
);
102 for (i
= *base
; i
; i
= i
->hdr
.next
) {
103 if (keyval
== i
->hdr
.keyval
&& !strcmp(i
->data
.key
, (*data
)->key
)) {
109 i
= (ITEM
*)hp
->items
.next
;
110 hp
->items
.next
+= hp
->items
.size
;
112 memcpy((char *)&i
->data
, (char *)*data
, hp
->items
.datalen
);
113 i
->hdr
.keyval
= keyval
;
123 * hashrehash() - resize and rebuild hp->tab, the hash table
125 static void hashrehash (struct hash
*hp
) {
126 int i
= ++hp
->items
.list
;
128 hp
->items
.more
= i
? 2 * hp
->items
.nel
: hp
->inel
;
129 hp
->items
.next
= (char *)malloc(hp
->items
.more
* hp
->items
.size
);
131 hp
->items
.lists
[i
].nel
= hp
->items
.more
;
132 hp
->items
.lists
[i
].base
= hp
->items
.next
;
133 hp
->items
.nel
+= hp
->items
.more
;
135 if (hp
->tab
.base
) free((char *)hp
->tab
.base
);
137 hp
->tab
.nel
= hp
->items
.nel
* hp
->bloat
;
138 hp
->tab
.base
= (ITEM
**)malloc(hp
->tab
.nel
* sizeof(ITEM
**));
140 memset((char *)hp
->tab
.base
, '\0', hp
->tab
.nel
* sizeof(ITEM
*));
142 for (i
= 0; i
< hp
->items
.list
; i
++) {
143 int nel
= hp
->items
.lists
[i
].nel
;
144 char *next
= hp
->items
.lists
[i
].base
;
146 for (; nel
--; next
+= hp
->items
.size
) {
147 ITEM
*i
= (ITEM
*)next
;
148 ITEM
**ip
= hp
->tab
.base
+ i
->hdr
.keyval
% hp
->tab
.nel
;
158 # define ALIGNED(x) ((x + sizeof(ITEM) - 1) & ~(sizeof(ITEM) - 1))
162 * hashinit() - initialize a hash table, returning a handle
164 struct hash
*hashinit (int datalen
, const char *name
) {
165 struct hash
*hp
= (struct hash
*)malloc(sizeof(*hp
));
169 hp
->tab
.base
= (ITEM
**)0;
171 hp
->items
.datalen
= datalen
;
172 hp
->items
.size
= sizeof(struct hashhdr
) + ALIGNED(datalen
);
183 * hashdone() - free a hash table, given its handle
185 void hashdone (struct hash
*hp
) {
189 if (DEBUG_MEM
) hashstat(hp
);
190 if (hp
->tab
.base
) free((char *)hp
->tab
.base
);
191 for (i
= 0; i
<= hp
->items
.list
; i
++) free(hp
->items
.lists
[i
].base
);
198 static void hashstat (struct hash
*hp
) {
199 ITEM
**tab
= hp
->tab
.base
;
200 int nel
= hp
->tab
.nel
;
203 int run
= (tab
[nel
-1] != (ITEM
*)0);
206 for (i
= nel
; i
> 0; i
--) {
207 if ((here
= (*tab
++ != (ITEM
*)0))) count
++;
208 if (here
&& !run
) sets
++;
211 printf("%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
216 hp
->items
.nel
* hp
->items
.size
/ 1024,
217 hp
->tab
.nel
* sizeof(ITEM
**) / 1024,
218 (float)count
/ (float)sets