1/*
2 * Copyright (c) 2007,2008 Paulo Cesar Pereira de Andrade
3 *
4 * Permission is hereby granted, free of charge, to any person obtaining a
5 * copy of this software and associated documentation files (the "Software"),
6 * to deal in the Software without restriction, including without limitation
7 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
8 * and/or sell copies of the Software, and to permit persons to whom the
9 * Software is furnished to do so, subject to the following conditions:
10 *
11 * The above copyright notice and this permission notice (including the next
12 * paragraph) shall be included in all copies or substantial portions of the
13 * Software.
14 *
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
18 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
20 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
21 * DEALINGS IN THE SOFTWARE.
22 *
23 * Author: Paulo Cesar Pereira de Andrade
24 */
25
26#include "util.h"
27#include <stdlib.h>
28#include <string.h>
29
30/*
31 *   This is a very simplified and adapted version of the hash tables I am
32 * using in a personal project. It was added to try to have a single hash
33 * table implementation in xedit. The lisp (for user code) version was not
34 * converted, but the following hastables have been converted:
35 *  ispell.c - list of replace and ignore words
36 *  hook.c   - list of auto replace words
37 *  internal lisp data structures:
38 *	atoms
39 *	strings
40 *	packages
41 *	opaque types
42 *   also, all code traversing hash tables is now using
43 *	hash_iter_first() and hash_iter_next()
44 *  conversion isn't as good as I originally wanted, code is using hash_check
45 *  instead of hash_get, but this is due to the code not having a basic
46 *  { void *data; int length; } object to store string like objects
47 *
48 *   Also, this hash table implementation was added mainly for the tags
49 * support.
50 */
51
52/*
53 * Prototypes
54 */
55static int hash_equal(hash_table *hash, hash_key *left, hash_key *right);
56static unsigned int hash_value(hash_key *key);
57
58
59/*
60 * Implementation
61 */
62static int
63hash_equal(hash_table *hash, hash_key *left, hash_key *right)
64{
65    if (left->length == right->length) {
66	if (left == right)
67	    return (1);
68	if (hash->compare)
69	    return (hash->compare(left, right));
70	return (memcmp(left->value, right->value, left->length) == 0);
71    }
72
73    return (0);
74}
75
76static unsigned int
77hash_data(const char *value, unsigned int length)
78{
79    const char		*ptr;
80    unsigned int	i, key;
81
82    for (i = key = 0, ptr = value; i < length; i++)
83	key = (key << (key & 1)) ^ ptr[i];
84
85    return (key);
86}
87
88static unsigned int
89hash_value(hash_key *key)
90{
91    return (hash_data(key->value, key->length));
92}
93
94hash_table *
95hash_new(unsigned int length, hash_compare compare)
96{
97    hash_table	*hash;
98
99    hash = calloc(1, sizeof(hash_table));
100    if (hash) {
101	hash->entries = calloc(length, sizeof(hash_entry *));
102	if (hash->entries) {
103	    hash->length = length;
104	    hash->compare = compare;
105	    hash->iter.offset = -1;
106	}
107	else {
108	    free(hash);
109	    hash = (hash_table *)0;
110	}
111    }
112
113    return (hash);
114}
115
116hash_entry *
117hash_put(hash_table *hash, hash_entry *entry)
118{
119    unsigned int	key;
120    hash_entry		*prev, *ptr;
121
122    /* Offset in hash table vector for this entry */
123    key = hash_value(entry->key) % hash->length;
124
125    /* We hope this is nil for most calls */
126    ptr = hash->entries[key];
127
128    /* Check if clashed with another entry */
129    for (prev = ptr; ptr; prev = ptr, ptr = ptr->next) {
130	/* Replace current entry */
131	if (hash_equal(hash, entry->key, ptr->key)) {
132	    /* If not trying to readd same value */
133	    if (entry != ptr) {
134		if (ptr == prev)
135		    hash->entries[key] = entry;
136		else
137		    prev->next = entry;
138		entry->next = ptr->next;
139		/* Finished */
140	    }
141	    else
142		ptr = (hash_entry *)0;
143	    goto hash_put_done;
144	}
145    }
146
147    /* Add new entry */
148    if (prev == (hash_entry *)0)
149	/* If no entry in offset */
150	hash->entries[key] = entry;
151    else
152	/* Add to end of clashing list */
153	prev->next = entry;
154    entry->next = (hash_entry *)0;
155
156    /* Increase sum of entries counter*/
157    ++hash->count;
158
159hash_put_done:
160    /* ptr will be nil if no entry was replaced, of tried to add
161     * again an entry already in the hash table */
162    return (ptr);
163}
164
165hash_entry *
166hash_get(hash_table *hash, hash_key *name)
167{
168    unsigned int	key;
169    hash_entry		*entry;
170
171    key = hash_value(name) % hash->length;
172    for (entry = hash->entries[key]; entry; entry = entry->next) {
173	if (hash_equal(hash, name, entry->key)) {
174
175	    return (entry);
176	}
177    }
178
179    return ((hash_entry *)0);
180}
181
182hash_entry *
183hash_check(hash_table *hash, const char *name, unsigned int length)
184{
185    unsigned int	key;
186    hash_entry		*entry;
187
188    key = hash_data(name, length) % hash->length;
189    for (entry = hash->entries[key]; entry; entry = entry->next) {
190	if (length == entry->key->length &&
191	    memcmp(name, entry->key->value, length) == 0) {
192
193	    return (entry);
194	}
195    }
196
197    return ((hash_entry *)0);
198}
199
200hash_entry *
201hash_rem_no_free(hash_table *hash, hash_entry *entry)
202{
203    unsigned int	key;
204    hash_entry		*ptr, *prev;
205
206    key = hash_value(entry->key) % hash->length;
207    for (ptr = prev = hash->entries[key]; ptr; prev = ptr, ptr = ptr->next) {
208	if (ptr == entry) {
209	    --hash->count;
210	    if (ptr == prev)
211		hash->entries[key] = ptr->next;
212	    else
213		prev->next = ptr->next;
214	    break;
215	}
216    }
217
218    if (ptr && ptr == hash->iter.entry)
219	hash->iter.entry = ptr->next;
220
221    /* If entry wasn't in hash table ptr will be nil */
222    return (ptr);
223}
224
225void
226hash_rem(hash_table *hash, hash_entry *entry)
227{
228    entry = hash_rem_no_free(hash, entry);
229    if (entry) {
230	free(entry->key->value);
231	free(entry->key);
232	free(entry);
233    }
234}
235
236void
237hash_rehash(hash_table *hash, unsigned int length)
238{
239    unsigned int	i, key;
240    hash_entry		*entry, *next, **entries;
241
242    entries = (hash_entry **)calloc(length, sizeof(hash_entry *));
243    if (entries) {
244	/* Populate the new table, note that clashes are now in reverse order */
245	for (i = 0; i < hash->length; i++) {
246	    for (entry = hash->entries[i]; entry; entry = next) {
247		next = entry->next;
248		key = hash_value(entry->key) % length;
249		entry->next = entries[key];
250		entries[key] = entry;
251	    }
252	}
253
254	/* Finish updating hash table */
255	free(hash->entries);
256	hash->entries = entries;
257	hash->length = length;
258    }
259    hash->iter.offset = -1;
260}
261
262hash_entry *
263hash_iter_first(hash_table *hash)
264{
265    hash->iter.offset = 0;
266    hash->iter.entry = (hash_entry *)0;
267
268    return (hash_iter_next(hash));
269}
270
271hash_entry *
272hash_iter_next(hash_table *hash)
273{
274    if (hash->iter.offset >= 0) {
275	if (hash->iter.entry) {
276	    if ((hash->iter.entry = hash->iter.entry->next))
277		return (hash->iter.entry);
278	    ++hash->iter.offset;
279	}
280	for (; hash->iter.offset < hash->length; hash->iter.offset++) {
281	    if ((hash->iter.entry = hash->entries[hash->iter.offset]))
282		return (hash->iter.entry);
283	}
284	hash->iter.entry = (hash_entry *)0;
285	hash->iter.offset = -1;
286    }
287
288    return ((hash_entry *)0);
289}
290
291void
292hash_clr(hash_table *hash)
293{
294    unsigned int	i;
295    hash_entry		*entry, *next;
296
297    /* Extra data should be free'd with the iterator */
298    for (i = 0; i < hash->length; i++) {
299	entry = hash->entries[i];
300	if (entry) {
301	    for (next = entry; entry; entry = next) {
302		next = entry->next;
303		free(entry->key->value);
304		free(entry->key);
305		free(entry);
306	    }
307	    hash->entries[i] = (hash_entry *)0;
308	}
309    }
310
311    hash->count = 0;
312    hash->iter.offset = -1;
313}
314
315void
316hash_del(hash_table *hash)
317{
318    hash_clr(hash);
319    free(hash->entries);
320    free(hash);
321}
322