2 * Copyright 2003-2004 Brandon Long
5 * ClearSilver Templating System
7 * This code is made available under the terms of the ClearSilver License.
8 * http://www.clearsilver.net/license.hdf
12 #include "cs_config.h"
21 static NEOERR
*_hash_resize(NE_HASH
*hash
);
22 static NE_HASHNODE
**_hash_lookup_node (NE_HASH
*hash
, void *key
, UINT32
*hashv
);
24 NEOERR
*ne_hash_init (NE_HASH
**hash
, NE_HASH_FUNC hash_func
, NE_COMP_FUNC comp_func
)
26 NE_HASH
*my_hash
= NULL
;
28 my_hash
= (NE_HASH
*) calloc(1, sizeof(NE_HASH
));
30 return nerr_raise(NERR_NOMEM
, "Unable to allocate memory for NE_HASH");
34 my_hash
->hash_func
= hash_func
;
35 my_hash
->comp_func
= comp_func
;
37 my_hash
->nodes
= (NE_HASHNODE
**) calloc (my_hash
->size
, sizeof(NE_HASHNODE
*));
38 if (my_hash
->nodes
== NULL
)
41 return nerr_raise(NERR_NOMEM
, "Unable to allocate memory for NE_HASHNODES");
49 void ne_hash_destroy (NE_HASH
**hash
)
52 NE_HASHNODE
*node
, *next
;
55 if (hash
== NULL
|| *hash
== NULL
)
60 for (x
= 0; x
< my_hash
->size
; x
++)
62 node
= my_hash
->nodes
[x
];
71 my_hash
->nodes
= NULL
;
76 NEOERR
*ne_hash_insert(NE_HASH
*hash
, void *key
, void *value
)
81 node
= _hash_lookup_node(hash
, key
, &hashv
);
85 (*node
)->value
= value
;
89 *node
= (NE_HASHNODE
*) malloc(sizeof(NE_HASHNODE
));
91 return nerr_raise(NERR_NOMEM
, "Unable to allocate NE_HASHNODE");
93 (*node
)->hashv
= hashv
;
95 (*node
)->value
= value
;
100 return _hash_resize(hash
);
103 void *ne_hash_lookup(NE_HASH
*hash
, void *key
)
107 node
= *_hash_lookup_node(hash
, key
, NULL
);
109 return (node
) ? node
->value
: NULL
;
112 void *ne_hash_remove(NE_HASH
*hash
, void *key
)
114 NE_HASHNODE
**node
, *rem
;
117 node
= _hash_lookup_node(hash
, key
, NULL
);
129 static NE_HASHNODE
**_hash_lookup_node (NE_HASH
*hash
, void *key
, UINT32
*o_hashv
)
131 UINT32 hashv
, bucket
;
134 hashv
= hash
->hash_func(key
);
135 if (o_hashv
) *o_hashv
= hashv
;
136 bucket
= hashv
& (hash
->size
- 1);
137 /* ne_warn("Lookup %s %d %d", key, hashv, bucket); */
139 node
= &(hash
->nodes
[bucket
]);
143 while (*node
&& !(hash
->comp_func((*node
)->key
, key
)))
144 node
= &(*node
)->next
;
148 /* No comp_func means we're doing pointer comparisons */
149 while (*node
&& (*node
)->key
!= key
)
150 node
= &(*node
)->next
;
153 /* ne_warn("Node %x", node); */
157 /* Ok, we're doing some weirdness here... */
158 static NEOERR
*_hash_resize(NE_HASH
*hash
)
160 NE_HASHNODE
**new_nodes
;
161 NE_HASHNODE
*entry
, *prev
;
163 int orig_size
= hash
->size
;
166 if (hash
->size
> hash
->num
)
169 /* We always double in size */
170 new_nodes
= (NE_HASHNODE
**) realloc (hash
->nodes
, (hash
->size
*2) * sizeof(NE_HASHNODE
*));
171 if (new_nodes
== NULL
)
172 return nerr_raise(NERR_NOMEM
, "Unable to allocate memory to resize NE_HASH");
174 hash
->nodes
= new_nodes
;
175 orig_size
= hash
->size
;
176 hash
->size
= hash
->size
*2;
178 /* Initialize new parts */
179 for (x
= orig_size
; x
< hash
->size
; x
++)
181 hash
->nodes
[x
] = NULL
;
184 hash_mask
= hash
->size
- 1;
186 for (x
= 0; x
< orig_size
; x
++)
189 next_bucket
= x
+ orig_size
;
190 for (entry
= hash
->nodes
[x
];
192 entry
= prev
? prev
->next
: hash
->nodes
[x
])
194 if ((entry
->hashv
& hash_mask
) != x
)
198 prev
->next
= entry
->next
;
202 hash
->nodes
[x
] = entry
->next
;
204 entry
->next
= hash
->nodes
[next_bucket
];
205 hash
->nodes
[next_bucket
] = entry
;