1/*
2 * Copyright (c) 1997 Kungliga Tekniska Högskolan
3 * (Royal Institute of Technology, Stockholm, Sweden).
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, this list of conditions and the following disclaimer.
12 *
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 *
17 * 3. Neither the name of the Institute nor the names of its contributors
18 *    may be used to endorse or promote products derived from this software
19 *    without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
22 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24 * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
25 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31 * SUCH DAMAGE.
32 */
33
34/*
35 * Hash table functions
36 */
37
38#include "gen_locl.h"
39
40RCSID("$Id$");
41
42static Hashentry *_search(Hashtab * htab,	/* The hash table */
43			  void *ptr);	/* And key */
44
45Hashtab *
46hashtabnew(int sz,
47	   int (*cmp) (void *, void *),
48	   unsigned (*hash) (void *))
49{
50    Hashtab *htab;
51    int i;
52
53    assert(sz > 0);
54
55    htab = (Hashtab *) malloc(sizeof(Hashtab) + (sz - 1) * sizeof(Hashentry *));
56    if (htab == NULL)
57	return NULL;
58
59    for (i = 0; i < sz; ++i)
60	htab->tab[i] = NULL;
61
62    htab->cmp = cmp;
63    htab->hash = hash;
64    htab->sz = sz;
65    return htab;
66}
67
68/* Intern search function */
69
70static Hashentry *
71_search(Hashtab * htab, void *ptr)
72{
73    Hashentry *hptr;
74
75    assert(htab && ptr);
76
77    for (hptr = htab->tab[(*htab->hash) (ptr) % htab->sz];
78	 hptr;
79	 hptr = hptr->next)
80	if ((*htab->cmp) (ptr, hptr->ptr) == 0)
81	    break;
82    return hptr;
83}
84
85/* Search for element in hash table */
86
87void *
88hashtabsearch(Hashtab * htab, void *ptr)
89{
90    Hashentry *tmp;
91
92    tmp = _search(htab, ptr);
93    return tmp ? tmp->ptr : tmp;
94}
95
96/* add element to hash table */
97/* if already there, set new value */
98/* !NULL if succesful */
99
100void *
101hashtabadd(Hashtab * htab, void *ptr)
102{
103    Hashentry *h = _search(htab, ptr);
104    Hashentry **tabptr;
105
106    assert(htab && ptr);
107
108    if (h)
109	free((void *) h->ptr);
110    else {
111	h = (Hashentry *) malloc(sizeof(Hashentry));
112	if (h == NULL) {
113	    return NULL;
114	}
115	tabptr = &htab->tab[(*htab->hash) (ptr) % htab->sz];
116	h->next = *tabptr;
117	*tabptr = h;
118	h->prev = tabptr;
119	if (h->next)
120	    h->next->prev = &h->next;
121    }
122    h->ptr = ptr;
123    return h;
124}
125
126/* delete element with key key. Iff freep, free Hashentry->ptr */
127
128int
129_hashtabdel(Hashtab * htab, void *ptr, int freep)
130{
131    Hashentry *h;
132
133    assert(htab && ptr);
134
135    h = _search(htab, ptr);
136    if (h) {
137	if (freep)
138	    free(h->ptr);
139	if ((*(h->prev) = h->next))
140	    h->next->prev = h->prev;
141	free(h);
142	return 0;
143    } else
144	return -1;
145}
146
147/* Do something for each element */
148
149void
150hashtabforeach(Hashtab * htab, int (*func) (void *ptr, void *arg),
151	       void *arg)
152{
153    Hashentry **h, *g;
154
155    assert(htab);
156
157    for (h = htab->tab; h < &htab->tab[htab->sz]; ++h)
158	for (g = *h; g; g = g->next)
159	    if ((*func) (g->ptr, arg))
160		return;
161}
162
163/* standard hash-functions for strings */
164
165unsigned
166hashadd(const char *s)
167{				/* Standard hash function */
168    unsigned i;
169
170    assert(s);
171
172    for (i = 0; *s; ++s)
173	i += *s;
174    return i;
175}
176
177unsigned
178hashcaseadd(const char *s)
179{				/* Standard hash function */
180    unsigned i;
181
182    assert(s);
183
184    for (i = 0; *s; ++s)
185	i += toupper((unsigned char)*s);
186    return i;
187}
188
189#define TWELVE (sizeof(unsigned))
190#define SEVENTYFIVE (6*sizeof(unsigned))
191#define HIGH_BITS (~((unsigned)(~0) >> TWELVE))
192
193unsigned
194hashjpw(const char *ss)
195{				/* another hash function */
196    unsigned h = 0;
197    unsigned g;
198    const unsigned char *s = (const unsigned char *)ss;
199
200    for (; *s; ++s) {
201	h = (h << TWELVE) + *s;
202	if ((g = h & HIGH_BITS))
203	    h = (h ^ (g >> SEVENTYFIVE)) & ~HIGH_BITS;
204    }
205    return h;
206}
207