1/*
2 * Copyright 1993, 1995 Christopher Seiwald.
3 *
4 * This file is part of Jam - see jam.c for Copyright information.
5 */
6
7/*
8 * hash.c - simple in-memory hashing routines
9 *
10 * External routines:
11 *
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
15 *
16 * Internal routines:
17 *
18 *     hashrehash() - resize and rebuild hp->tab, the hash table
19 *
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)
23 */
24
25# include "jam.h"
26# include "hash.h"
27
28/* Header attached to all data items entered into a hash table. */
29
30struct hashhdr {
31	struct item *next;
32	unsigned int keyval;		/* for quick comparisons */
33} ;
34
35/* This structure overlays the one handed to hashenter(). */
36/* It's actual size is given to hashinit(). */
37
38struct hashdata {
39	char	*key;
40	/* rest of user data */
41} ;
42
43typedef struct item {
44	struct hashhdr hdr;
45	struct hashdata data;
46} ITEM ;
47
48# define MAX_LISTS 32
49
50struct hash
51{
52	/*
53	 * the hash table, just an array of item pointers
54	 */
55	struct {
56		int nel;
57		ITEM **base;
58	} tab;
59
60	int bloat;	/* tab.nel / items.nel */
61	int inel; 	/* initial number of elements */
62
63	/*
64	 * the array of records, maintained by these routines
65	 * essentially a microallocator
66	 */
67	struct {
68		int more;	/* how many more ITEMs fit in lists[ list ] */
69		char *next;	/* where to put more ITEMs in lists[ list ] */
70		int datalen;	/* length of records in this hash table */
71		int size;	/* sizeof( ITEM ) + aligned datalen */
72		int nel;	/* total ITEMs held by all lists[] */
73		int list;	/* index into lists[] */
74
75		struct {
76			int nel;	/* total ITEMs held by this list */
77			char *base;	/* base of ITEMs array */
78		} lists[ MAX_LISTS ];
79	} items;
80
81	const char *name;	/* just for hashstats() */
82} ;
83
84static void hashrehash( struct hash *hp );
85static void hashstat( struct hash *hp );
86
87/*
88 * hashitem() - find a record in the table, and optionally enter a new one
89 */
90
91int
92hashitem(
93	register struct hash *hp,
94	HASHDATA **data,
95	int enter )
96{
97	ITEM **base;
98	register ITEM *i;
99	unsigned char *b = (unsigned char *)(*data)->key;
100	unsigned int keyval;
101
102	if( enter && !hp->items.more )
103	    hashrehash( hp );
104
105	if( !enter && !hp->items.nel )
106	    return 0;
107
108	keyval = *b;
109
110	while( *b )
111		keyval = keyval * 2147059363 + *b++;
112
113	base = hp->tab.base + ( keyval % hp->tab.nel );
114
115	for( i = *base; i; i = i->hdr.next )
116	    if( keyval == i->hdr.keyval &&
117		!strcmp( i->data.key, (*data)->key ) )
118	{
119		*data = &i->data;
120		return !0;
121	}
122
123	if( enter )
124	{
125		i = (ITEM *)hp->items.next;
126		hp->items.next += hp->items.size;
127		hp->items.more--;
128		memcpy( (char *)&i->data, (char *)*data, hp->items.datalen );
129		i->hdr.keyval = keyval;
130		i->hdr.next = *base;
131		*base = i;
132		*data = &i->data;
133	}
134
135	return 0;
136}
137
138/*
139 * hashrehash() - resize and rebuild hp->tab, the hash table
140 */
141
142static void hashrehash( register struct hash *hp )
143{
144	int i = ++hp->items.list;
145
146	hp->items.more = i ? 2 * hp->items.nel : hp->inel;
147	hp->items.next = (char *)malloc( hp->items.more * hp->items.size );
148
149	hp->items.lists[i].nel = hp->items.more;
150	hp->items.lists[i].base = hp->items.next;
151	hp->items.nel += hp->items.more;
152
153	if( hp->tab.base )
154		free( (char *)hp->tab.base );
155
156	hp->tab.nel = hp->items.nel * hp->bloat;
157	hp->tab.base = (ITEM **)malloc( hp->tab.nel * sizeof(ITEM **) );
158
159	memset( (char *)hp->tab.base, '\0', hp->tab.nel * sizeof( ITEM * ) );
160
161	for( i = 0; i < hp->items.list; i++ )
162	{
163		int nel = hp->items.lists[i].nel;
164		char *next = hp->items.lists[i].base;
165
166		for( ; nel--; next += hp->items.size )
167		{
168			register ITEM *i = (ITEM *)next;
169			ITEM **ip = hp->tab.base + i->hdr.keyval % hp->tab.nel;
170
171			i->hdr.next = *ip;
172			*ip = i;
173		}
174	}
175}
176
177/* --- */
178
179# define ALIGNED(x) ( ( x + sizeof( ITEM ) - 1 ) & ~( sizeof( ITEM ) - 1 ) )
180
181/*
182 * hashinit() - initialize a hash table, returning a handle
183 */
184
185struct hash *
186hashinit(
187	int datalen,
188	const char *name )
189{
190	struct hash *hp = (struct hash *)malloc( sizeof( *hp ) );
191
192	hp->bloat = 3;
193	hp->tab.nel = 0;
194	hp->tab.base = (ITEM **)0;
195	hp->items.more = 0;
196	hp->items.datalen = datalen;
197	hp->items.size = sizeof( struct hashhdr ) + ALIGNED( datalen );
198	hp->items.list = -1;
199	hp->items.nel = 0;
200	hp->inel = 11;
201	hp->name = name;
202
203	return hp;
204}
205
206/*
207 * hashdone() - free a hash table, given its handle
208 */
209
210void
211hashdone( struct hash *hp )
212{
213	int i;
214
215	if( !hp )
216	    return;
217
218	if( DEBUG_MEM )
219	    hashstat( hp );
220
221	if( hp->tab.base )
222		free( (char *)hp->tab.base );
223	for( i = 0; i <= hp->items.list; i++ )
224		free( hp->items.lists[i].base );
225	free( (char *)hp );
226}
227
228/* ---- */
229
230static void
231hashstat( struct hash *hp )
232{
233	ITEM **tab = hp->tab.base;
234	int nel = hp->tab.nel;
235	int count = 0;
236	int sets = 0;
237	int run = ( tab[ nel - 1 ] != (ITEM *)0 );
238	int i, here;
239
240	for( i = nel; i > 0; i-- )
241	{
242		if( here = ( *tab++ != (ITEM *)0 ) )
243			count++;
244		if( here && !run )
245			sets++;
246		run = here;
247	}
248
249	printf( "%s table: %d+%d+%d (%dK+%dK) items+table+hash, %f density\n",
250		hp->name,
251		count,
252		hp->items.nel,
253		hp->tab.nel,
254		hp->items.nel * hp->items.size / 1024,
255		(int)(hp->tab.nel * sizeof( ITEM ** ) / 1024),
256		(float)count / (float)sets );
257}
258