Line data Source code
1 : /* SPDX-License-Identifier: MIT OR GPL-3.0-only */
2 : /* hash.c
3 : ** strophe XMPP client library -- hash table implementation
4 : **
5 : ** Copyright (C) 2005-2009 Collecta, Inc.
6 : **
7 : ** This software is provided AS-IS with no warranty, either express
8 : ** or implied.
9 : **
10 : ** This program is dual licensed under the MIT or GPLv3 licenses.
11 : */
12 :
13 : /** @file
14 : * Hash tables.
15 : */
16 :
17 : #include <stdlib.h>
18 : #include <string.h>
19 :
20 : #include "strophe.h"
21 : #include "common.h"
22 : #include "hash.h"
23 :
24 : /* private types */
25 : typedef struct _hashentry_t hashentry_t;
26 :
27 : struct _hashentry_t {
28 : hashentry_t *next;
29 : char *key;
30 : void *value;
31 : };
32 :
33 : struct _hash_t {
34 : unsigned int ref;
35 : xmpp_ctx_t *ctx;
36 : hash_free_func free;
37 : int length;
38 : int num_keys;
39 : hashentry_t **entries;
40 : };
41 :
42 : struct _hash_iterator_t {
43 : unsigned int ref;
44 : hash_t *table;
45 : hashentry_t *entry;
46 : int index;
47 : };
48 :
49 : /** allocate and initialize a new hash table */
50 38 : hash_t *hash_new(xmpp_ctx_t *ctx, int size, hash_free_func free_func)
51 : {
52 38 : hash_t *result = NULL;
53 :
54 38 : result = strophe_alloc(ctx, sizeof(hash_t));
55 38 : if (result != NULL) {
56 38 : result->entries = strophe_alloc(ctx, size * sizeof(hashentry_t *));
57 38 : if (result->entries == NULL) {
58 0 : strophe_free(ctx, result);
59 0 : return NULL;
60 : }
61 38 : memset(result->entries, 0, size * sizeof(hashentry_t *));
62 38 : result->length = size;
63 :
64 38 : result->ctx = ctx;
65 38 : result->free = free_func;
66 38 : result->num_keys = 0;
67 : /* give the caller a reference */
68 38 : result->ref = 1;
69 : }
70 :
71 : return result;
72 : }
73 :
74 : /** obtain a new reference to an existing hash table */
75 32 : hash_t *hash_clone(hash_t *table)
76 : {
77 32 : table->ref++;
78 32 : return table;
79 : }
80 :
81 : /** release a hash table that is no longer needed */
82 70 : void hash_release(hash_t *table)
83 : {
84 70 : xmpp_ctx_t *ctx = table->ctx;
85 70 : hashentry_t *entry, *next;
86 70 : int i;
87 :
88 70 : if (table->ref > 1)
89 32 : table->ref--;
90 : else {
91 534 : for (i = 0; i < table->length; i++) {
92 496 : entry = table->entries[i];
93 541 : while (entry != NULL) {
94 45 : next = entry->next;
95 45 : strophe_free(ctx, entry->key);
96 45 : if (table->free)
97 45 : table->free(ctx, entry->value);
98 45 : strophe_free(ctx, entry);
99 45 : entry = next;
100 : }
101 : }
102 38 : strophe_free(ctx, table->entries);
103 38 : strophe_free(ctx, table);
104 : }
105 70 : }
106 :
107 : /** hash a key for our table lookup */
108 164 : static int _hash_key(hash_t *table, const char *key)
109 : {
110 164 : unsigned hash = 0;
111 164 : unsigned shift = 0;
112 164 : const unsigned char *c = (const unsigned char *)key;
113 :
114 871 : while (*c != 0) {
115 : /* assume 32 bit ints */
116 707 : hash ^= ((unsigned)*c++ << shift);
117 707 : shift += 8;
118 707 : if (shift > 24)
119 134 : shift = 0;
120 : }
121 164 : return hash % (unsigned)table->length;
122 : }
123 :
124 113 : hashentry_t *_hash_entry_find(hash_t *table, const char *key)
125 : {
126 113 : hashentry_t *entry;
127 113 : int table_index = _hash_key(table, key);
128 :
129 : /* look up the hash entry */
130 113 : entry = table->entries[table_index];
131 127 : while (entry != NULL) {
132 : /* traverse the linked list looking for the key */
133 78 : if (!strcmp(key, entry->key)) {
134 : /* match */
135 : break;
136 : }
137 14 : entry = entry->next;
138 : }
139 113 : return entry;
140 : }
141 :
142 : /** add a key, value pair to a hash table.
143 : * each key can appear only once; the value of any
144 : * identical key will be replaced
145 : */
146 48 : int hash_add(hash_t *table, const char *key, void *data)
147 : {
148 48 : xmpp_ctx_t *ctx = table->ctx;
149 48 : hashentry_t *entry = NULL;
150 48 : int table_index = _hash_key(table, key);
151 :
152 : /* find and replace existing entry, if any */
153 48 : entry = _hash_entry_find(table, key);
154 :
155 48 : if (entry == NULL) {
156 : /* allocate and fill a new entry */
157 47 : entry = strophe_alloc(ctx, sizeof(hashentry_t));
158 47 : if (!entry)
159 : return -1;
160 47 : entry->key = strophe_strdup(ctx, key);
161 47 : if (!entry->key) {
162 0 : strophe_free(ctx, entry);
163 0 : return -1;
164 : }
165 : /* insert ourselves in the linked list */
166 47 : entry->next = table->entries[table_index];
167 47 : table->entries[table_index] = entry;
168 47 : table->num_keys++;
169 : } else {
170 1 : if (table->free)
171 1 : table->free(ctx, entry->value);
172 : }
173 :
174 48 : entry->value = data;
175 :
176 48 : return 0;
177 : }
178 :
179 : /** look up a key in a hash table */
180 65 : void *hash_get(hash_t *table, const char *key)
181 : {
182 65 : hashentry_t *entry;
183 :
184 65 : entry = _hash_entry_find(table, key);
185 65 : return entry == NULL ? NULL : entry->value;
186 : }
187 :
188 : /** delete a key from a hash table */
189 3 : int hash_drop(hash_t *table, const char *key)
190 : {
191 3 : xmpp_ctx_t *ctx = table->ctx;
192 3 : hashentry_t *entry, *prev;
193 3 : int table_index = _hash_key(table, key);
194 :
195 : /* look up the hash entry */
196 3 : entry = table->entries[table_index];
197 3 : prev = NULL;
198 3 : while (entry != NULL) {
199 : /* traverse the linked list looking for the key */
200 2 : if (!strcmp(key, entry->key)) {
201 : /* match, remove the entry */
202 2 : strophe_free(ctx, entry->key);
203 2 : if (table->free)
204 2 : table->free(ctx, entry->value);
205 2 : if (prev == NULL) {
206 2 : table->entries[table_index] = entry->next;
207 : } else {
208 0 : prev->next = entry->next;
209 : }
210 2 : strophe_free(ctx, entry);
211 2 : table->num_keys--;
212 2 : return 0;
213 : }
214 0 : prev = entry;
215 0 : entry = entry->next;
216 : }
217 : /* no match */
218 : return -1;
219 : }
220 :
221 14 : int hash_num_keys(hash_t *table)
222 : {
223 14 : return table->num_keys;
224 : }
225 :
226 : /** allocate and initialize a new iterator */
227 32 : hash_iterator_t *hash_iter_new(hash_t *table)
228 : {
229 32 : xmpp_ctx_t *ctx = table->ctx;
230 32 : hash_iterator_t *iter;
231 :
232 32 : iter = strophe_alloc(ctx, sizeof(*iter));
233 32 : if (iter != NULL) {
234 32 : iter->ref = 1;
235 32 : iter->table = hash_clone(table);
236 32 : iter->entry = NULL;
237 32 : iter->index = -1;
238 : }
239 :
240 32 : return iter;
241 : }
242 :
243 : /** release an iterator that is no longer needed */
244 32 : void hash_iter_release(hash_iterator_t *iter)
245 : {
246 32 : xmpp_ctx_t *ctx = iter->table->ctx;
247 :
248 32 : iter->ref--;
249 :
250 32 : if (iter->ref == 0) { // ref is unsigned!!!
251 32 : hash_release(iter->table);
252 32 : strophe_free(ctx, iter);
253 : }
254 32 : }
255 :
256 : /** return the next hash table key from the iterator.
257 : the returned key should not be freed */
258 58 : const char *hash_iter_next(hash_iterator_t *iter)
259 : {
260 58 : hash_t *table = iter->table;
261 58 : hashentry_t *entry = iter->entry;
262 58 : int i;
263 :
264 : /* advance until we find the next entry */
265 58 : if (entry != NULL)
266 26 : entry = entry->next;
267 26 : if (entry == NULL) {
268 : /* we're off the end of list, search for a new entry */
269 54 : i = iter->index + 1;
270 672 : while (i < iter->table->length) {
271 640 : entry = table->entries[i];
272 640 : if (entry != NULL) {
273 22 : iter->index = i;
274 22 : break;
275 : }
276 618 : i++;
277 : }
278 : }
279 :
280 54 : if (entry == NULL) {
281 : /* no more keys! */
282 : return NULL;
283 : }
284 :
285 : /* remember our current match */
286 26 : iter->entry = entry;
287 26 : return entry->key;
288 : }
|