1/*
2 * Copyright 2003-2004 Brandon Long
3 * All Rights Reserved.
4 *
5 * ClearSilver Templating System
6 *
7 * This code is made available under the terms of the ClearSilver License.
8 * http://www.clearsilver.net/license.hdf
9 *
10 */
11
12#include "cs_config.h"
13
14#include <stdlib.h>
15#include <string.h>
16
17#include "neo_misc.h"
18#include "neo_err.h"
19#include "neo_hash.h"
20
21static NEOERR *_hash_resize(NE_HASH *hash);
22static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *hashv);
23
24NEOERR *ne_hash_init (NE_HASH **hash, NE_HASH_FUNC hash_func, NE_COMP_FUNC comp_func)
25{
26  NE_HASH *my_hash = NULL;
27
28  my_hash = (NE_HASH *) calloc(1, sizeof(NE_HASH));
29  if (my_hash == NULL)
30    return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASH");
31
32  my_hash->size = 256;
33  my_hash->num = 0;
34  my_hash->hash_func = hash_func;
35  my_hash->comp_func = comp_func;
36
37  my_hash->nodes = (NE_HASHNODE **) calloc (my_hash->size, sizeof(NE_HASHNODE *));
38  if (my_hash->nodes == NULL)
39  {
40    free(my_hash);
41    return nerr_raise(NERR_NOMEM, "Unable to allocate memory for NE_HASHNODES");
42  }
43
44  *hash = my_hash;
45
46  return STATUS_OK;
47}
48
49void ne_hash_destroy (NE_HASH **hash)
50{
51  NE_HASH *my_hash;
52  NE_HASHNODE *node, *next;
53  int x;
54
55  if (hash == NULL || *hash == NULL)
56    return;
57
58  my_hash = *hash;
59
60  for (x = 0; x < my_hash->size; x++)
61  {
62    node = my_hash->nodes[x];
63    while (node)
64    {
65      next = node->next;
66      free(node);
67      node = next;
68    }
69  }
70  free(my_hash->nodes);
71  my_hash->nodes = NULL;
72  free(my_hash);
73  *hash = NULL;
74}
75
76NEOERR *ne_hash_insert(NE_HASH *hash, void *key, void *value)
77{
78  UINT32 hashv;
79  NE_HASHNODE **node;
80
81  node = _hash_lookup_node(hash, key, &hashv);
82
83  if (*node)
84  {
85    (*node)->value = value;
86  }
87  else
88  {
89    *node = (NE_HASHNODE *) malloc(sizeof(NE_HASHNODE));
90    if (node == NULL)
91      return nerr_raise(NERR_NOMEM, "Unable to allocate NE_HASHNODE");
92
93    (*node)->hashv = hashv;
94    (*node)->key = key;
95    (*node)->value = value;
96    (*node)->next = NULL;
97  }
98  hash->num++;
99
100  return _hash_resize(hash);
101}
102
103void *ne_hash_lookup(NE_HASH *hash, void *key)
104{
105  NE_HASHNODE *node;
106
107  node = *_hash_lookup_node(hash, key, NULL);
108
109  return (node) ? node->value : NULL;
110}
111
112void *ne_hash_remove(NE_HASH *hash, void *key)
113{
114  NE_HASHNODE **node, *remove;
115  void *value = NULL;
116
117  node = _hash_lookup_node(hash, key, NULL);
118  if (*node)
119  {
120    remove = *node;
121    *node = remove->next;
122    value = remove->value;
123    free(remove);
124    hash->num--;
125  }
126  return value;
127}
128
129int ne_hash_has_key(NE_HASH *hash, void *key)
130{
131  NE_HASHNODE *node;
132
133  node = *_hash_lookup_node(hash, key, NULL);
134
135  if (node) return 1;
136  return 0;
137}
138
139void *ne_hash_next(NE_HASH *hash, void **key)
140{
141  NE_HASHNODE **node = 0;
142  UINT32 hashv, bucket;
143
144  if (*key)
145  {
146    node = _hash_lookup_node(hash, key, NULL);
147
148    if (*node)
149    {
150      bucket = (*node)->hashv & (hash->size - 1);
151    }
152    else
153    {
154      hashv = hash->hash_func(*key);
155      bucket = hashv & (hash->size - 1);
156    }
157  }
158  else
159  {
160    bucket = 0;
161  }
162
163  if (*node)
164  {
165    if ((*node)->next)
166    {
167      *key = (*node)->next->key;
168      return (*node)->next->value;
169    }
170    bucket++;
171  }
172
173  while (bucket < hash->size)
174  {
175    if (hash->nodes[bucket])
176    {
177      *key = hash->nodes[bucket]->key;
178      return hash->nodes[bucket]->value;
179    }
180    bucket++;
181  }
182
183  return NULL;
184}
185
186static NE_HASHNODE **_hash_lookup_node (NE_HASH *hash, void *key, UINT32 *o_hashv)
187{
188  UINT32 hashv, bucket;
189  NE_HASHNODE **node;
190
191  hashv = hash->hash_func(key);
192  if (o_hashv) *o_hashv = hashv;
193  bucket = hashv & (hash->size - 1);
194  /* ne_warn("Lookup %s %d %d", key, hashv, bucket); */
195
196  node = &(hash->nodes[bucket]);
197
198  if (hash->comp_func)
199  {
200    while (*node && !(hash->comp_func((*node)->key, key)))
201      node = &(*node)->next;
202  }
203  else
204  {
205    /* No comp_func means we're doing pointer comparisons */
206    while (*node && (*node)->key != key)
207      node = &(*node)->next;
208  }
209
210  /* ne_warn("Node %x", node); */
211  return node;
212}
213
214/* Ok, we're doing some weirdness here... */
215static NEOERR *_hash_resize(NE_HASH *hash)
216{
217  NE_HASHNODE **new_nodes;
218  NE_HASHNODE *entry, *prev;
219  int x, next_bucket;
220  int orig_size = hash->size;
221  UINT32 hash_mask;
222
223  if (hash->size > hash->num)
224    return STATUS_OK;
225
226  /* We always double in size */
227  new_nodes = (NE_HASHNODE **) realloc (hash->nodes, (hash->size*2) * sizeof(NE_HASHNODE));
228  if (new_nodes == NULL)
229    return nerr_raise(NERR_NOMEM, "Unable to allocate memory to resize NE_HASH");
230
231  hash->nodes = new_nodes;
232  orig_size = hash->size;
233  hash->size = hash->size*2;
234
235  /* Initialize new parts */
236  for (x = orig_size; x < hash->size; x++)
237  {
238    hash->nodes[x] = NULL;
239  }
240
241  hash_mask = hash->size - 1;
242
243  for (x = 0; x < orig_size; x++)
244  {
245    prev = NULL;
246    next_bucket = x + orig_size;
247    for (entry = hash->nodes[x];
248	 entry;
249	 entry = prev ? prev->next : hash->nodes[x])
250    {
251      if ((entry->hashv & hash_mask) != x)
252      {
253	if (prev)
254	{
255	  prev->next = entry->next;
256	}
257	else
258	{
259	  hash->nodes[x] = entry->next;
260	}
261	entry->next = hash->nodes[next_bucket];
262	hash->nodes[next_bucket] = entry;
263      }
264      else
265      {
266	prev = entry;
267      }
268    }
269  }
270
271  return STATUS_OK;
272}
273
274int ne_hash_str_comp(const void *a, const void *b)
275{
276  return !strcmp((const char *)a, (const char *)b);
277}
278
279UINT32 ne_hash_str_hash(const void *a)
280{
281  return ne_crc((unsigned char *)a, strlen((const char *)a));
282}
283
284int ne_hash_int_comp(const void *a, const void *b)
285{
286  if (a == b) return 1;
287  return 0;
288}
289
290UINT32 ne_hash_int_hash(const void *a)
291{
292  return (UINT32)(long)(a);
293}
294