Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | * hash.c: hash tables |
3 | | * |
4 | | * Hash table with open addressing, linear probing and |
5 | | * Robin Hood reordering. |
6 | | * |
7 | | * See Copyright for the status of this software. |
8 | | */ |
9 | | |
10 | | #define IN_LIBXML |
11 | | #include "libxml.h" |
12 | | |
13 | | #include <string.h> |
14 | | #include <limits.h> |
15 | | |
16 | | #include <libxml/parser.h> |
17 | | #include <libxml/hash.h> |
18 | | #include <libxml/dict.h> |
19 | | #include <libxml/xmlmemory.h> |
20 | | #include <libxml/xmlstring.h> |
21 | | |
22 | | #include "private/dict.h" |
23 | | |
24 | | #ifndef SIZE_MAX |
25 | | #define SIZE_MAX ((size_t) -1) |
26 | | #endif |
27 | | |
28 | 0 | #define MAX_FILL_NUM 7 |
29 | 0 | #define MAX_FILL_DENOM 8 |
30 | 0 | #define MIN_HASH_SIZE 8 |
31 | 0 | #define MAX_HASH_SIZE (1u << 31) |
32 | | |
33 | | /* |
34 | | * A single entry in the hash table |
35 | | */ |
36 | | typedef struct { |
37 | | unsigned hashValue; /* 0 means unoccupied, occupied entries have the |
38 | | * MAX_HASH_SIZE bit set to 1 */ |
39 | | xmlChar *key; |
40 | | xmlChar *key2; /* TODO: Don't allocate possibly empty keys */ |
41 | | xmlChar *key3; |
42 | | void *payload; |
43 | | } xmlHashEntry; |
44 | | |
45 | | /* |
46 | | * The entire hash table |
47 | | */ |
48 | | struct _xmlHashTable { |
49 | | xmlHashEntry *table; |
50 | | unsigned size; /* power of two */ |
51 | | unsigned nbElems; |
52 | | xmlDictPtr dict; |
53 | | unsigned randomSeed; |
54 | | }; |
55 | | |
56 | | static int |
57 | | xmlHashGrow(xmlHashTablePtr hash, unsigned size); |
58 | | |
59 | | ATTRIBUTE_NO_SANITIZE_INTEGER |
60 | | static unsigned |
61 | | xmlHashValue(unsigned seed, const xmlChar *key, const xmlChar *key2, |
62 | 0 | const xmlChar *key3, size_t *lengths) { |
63 | 0 | unsigned h1, h2; |
64 | 0 | size_t i; |
65 | |
|
66 | 0 | HASH_INIT(h1, h2, seed); |
67 | |
|
68 | 0 | for (i = 0; key[i] != 0; i++) { |
69 | 0 | HASH_UPDATE(h1, h2, key[i]); |
70 | 0 | } |
71 | 0 | if (lengths) |
72 | 0 | lengths[0] = i; |
73 | |
|
74 | 0 | HASH_UPDATE(h1, h2, 0); |
75 | |
|
76 | 0 | if (key2 != NULL) { |
77 | 0 | for (i = 0; key2[i] != 0; i++) { |
78 | 0 | HASH_UPDATE(h1, h2, key2[i]); |
79 | 0 | } |
80 | 0 | if (lengths) |
81 | 0 | lengths[1] = i; |
82 | 0 | } |
83 | |
|
84 | 0 | HASH_UPDATE(h1, h2, 0); |
85 | |
|
86 | 0 | if (key3 != NULL) { |
87 | 0 | for (i = 0; key3[i] != 0; i++) { |
88 | 0 | HASH_UPDATE(h1, h2, key3[i]); |
89 | 0 | } |
90 | 0 | if (lengths) |
91 | 0 | lengths[2] = i; |
92 | 0 | } |
93 | |
|
94 | 0 | HASH_FINISH(h1, h2); |
95 | |
|
96 | 0 | return(h2); |
97 | 0 | } |
98 | | |
99 | | ATTRIBUTE_NO_SANITIZE_INTEGER |
100 | | static unsigned |
101 | | xmlHashQNameValue(unsigned seed, |
102 | | const xmlChar *prefix, const xmlChar *name, |
103 | | const xmlChar *prefix2, const xmlChar *name2, |
104 | 0 | const xmlChar *prefix3, const xmlChar *name3) { |
105 | 0 | unsigned h1, h2, ch; |
106 | |
|
107 | 0 | HASH_INIT(h1, h2, seed); |
108 | |
|
109 | 0 | if (prefix != NULL) { |
110 | 0 | while ((ch = *prefix++) != 0) { |
111 | 0 | HASH_UPDATE(h1, h2, ch); |
112 | 0 | } |
113 | 0 | HASH_UPDATE(h1, h2, ':'); |
114 | 0 | } |
115 | 0 | if (name != NULL) { |
116 | 0 | while ((ch = *name++) != 0) { |
117 | 0 | HASH_UPDATE(h1, h2, ch); |
118 | 0 | } |
119 | 0 | } |
120 | 0 | HASH_UPDATE(h1, h2, 0); |
121 | 0 | if (prefix2 != NULL) { |
122 | 0 | while ((ch = *prefix2++) != 0) { |
123 | 0 | HASH_UPDATE(h1, h2, ch); |
124 | 0 | } |
125 | 0 | HASH_UPDATE(h1, h2, ':'); |
126 | 0 | } |
127 | 0 | if (name2 != NULL) { |
128 | 0 | while ((ch = *name2++) != 0) { |
129 | 0 | HASH_UPDATE(h1, h2, ch); |
130 | 0 | } |
131 | 0 | } |
132 | 0 | HASH_UPDATE(h1, h2, 0); |
133 | 0 | if (prefix3 != NULL) { |
134 | 0 | while ((ch = *prefix3++) != 0) { |
135 | 0 | HASH_UPDATE(h1, h2, ch); |
136 | 0 | } |
137 | 0 | HASH_UPDATE(h1, h2, ':'); |
138 | 0 | } |
139 | 0 | if (name3 != NULL) { |
140 | 0 | while ((ch = *name3++) != 0) { |
141 | 0 | HASH_UPDATE(h1, h2, ch); |
142 | 0 | } |
143 | 0 | } |
144 | |
|
145 | 0 | HASH_FINISH(h1, h2); |
146 | |
|
147 | 0 | return(h2); |
148 | 0 | } |
149 | | |
150 | | /** |
151 | | * Create a new hash table. Set size to zero if the number of entries |
152 | | * can't be estimated. |
153 | | * |
154 | | * @param size initial size of the hash table |
155 | | * @returns the newly created object, or NULL if a memory allocation failed. |
156 | | */ |
157 | | xmlHashTable * |
158 | 0 | xmlHashCreate(int size) { |
159 | 0 | xmlHashTablePtr hash; |
160 | |
|
161 | 0 | xmlInitParser(); |
162 | |
|
163 | 0 | hash = xmlMalloc(sizeof(*hash)); |
164 | 0 | if (hash == NULL) |
165 | 0 | return(NULL); |
166 | 0 | hash->dict = NULL; |
167 | 0 | hash->size = 0; |
168 | 0 | hash->table = NULL; |
169 | 0 | hash->nbElems = 0; |
170 | 0 | hash->randomSeed = xmlRandom(); |
171 | 0 | #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION |
172 | 0 | hash->randomSeed = 0; |
173 | 0 | #endif |
174 | | |
175 | | /* |
176 | | * Unless a larger size is passed, the backing table is created |
177 | | * lazily with MIN_HASH_SIZE capacity. In practice, there are many |
178 | | * hash tables which are never filled. |
179 | | */ |
180 | 0 | if (size > MIN_HASH_SIZE) { |
181 | 0 | unsigned newSize = MIN_HASH_SIZE * 2; |
182 | |
|
183 | 0 | while ((newSize < (unsigned) size) && (newSize < MAX_HASH_SIZE)) |
184 | 0 | newSize *= 2; |
185 | |
|
186 | 0 | if (xmlHashGrow(hash, newSize) != 0) { |
187 | 0 | xmlFree(hash); |
188 | 0 | return(NULL); |
189 | 0 | } |
190 | 0 | } |
191 | | |
192 | 0 | return(hash); |
193 | 0 | } |
194 | | |
195 | | /** |
196 | | * Create a new hash table backed by a dictionary. This can reduce |
197 | | * resource usage considerably if most keys passed to API functions |
198 | | * originate from this dictionary. |
199 | | * |
200 | | * @param size the size of the hash table |
201 | | * @param dict a dictionary to use for the hash |
202 | | * @returns the newly created object, or NULL if a memory allocation failed. |
203 | | */ |
204 | | xmlHashTable * |
205 | 0 | xmlHashCreateDict(int size, xmlDict *dict) { |
206 | 0 | xmlHashTablePtr hash; |
207 | |
|
208 | 0 | hash = xmlHashCreate(size); |
209 | 0 | if (hash != NULL) { |
210 | 0 | hash->dict = dict; |
211 | 0 | xmlDictReference(dict); |
212 | 0 | } |
213 | 0 | return(hash); |
214 | 0 | } |
215 | | |
216 | | /** |
217 | | * Free the hash and its contents. The payload is deallocated with |
218 | | * `dealloc` if provided. |
219 | | * |
220 | | * @param hash hash table |
221 | | * @param dealloc deallocator function or NULL |
222 | | */ |
223 | | void |
224 | 0 | xmlHashFree(xmlHashTable *hash, xmlHashDeallocator dealloc) { |
225 | 0 | if (hash == NULL) |
226 | 0 | return; |
227 | | |
228 | 0 | if (hash->table) { |
229 | 0 | const xmlHashEntry *end = &hash->table[hash->size]; |
230 | 0 | const xmlHashEntry *entry; |
231 | |
|
232 | 0 | for (entry = hash->table; entry < end; entry++) { |
233 | 0 | if (entry->hashValue == 0) |
234 | 0 | continue; |
235 | 0 | if ((dealloc != NULL) && (entry->payload != NULL)) |
236 | 0 | dealloc(entry->payload, entry->key); |
237 | 0 | if (hash->dict == NULL) { |
238 | 0 | if (entry->key) |
239 | 0 | xmlFree(entry->key); |
240 | 0 | if (entry->key2) |
241 | 0 | xmlFree(entry->key2); |
242 | 0 | if (entry->key3) |
243 | 0 | xmlFree(entry->key3); |
244 | 0 | } |
245 | 0 | } |
246 | |
|
247 | 0 | xmlFree(hash->table); |
248 | 0 | } |
249 | |
|
250 | 0 | if (hash->dict) |
251 | 0 | xmlDictFree(hash->dict); |
252 | |
|
253 | 0 | xmlFree(hash); |
254 | 0 | } |
255 | | |
256 | | /** |
257 | | * Compare two strings for equality, allowing NULL values. |
258 | | * |
259 | | * @param s1 string |
260 | | * @param s2 string |
261 | | */ |
262 | | static int |
263 | 0 | xmlFastStrEqual(const xmlChar *s1, const xmlChar *s2) { |
264 | 0 | if (s1 == NULL) |
265 | 0 | return(s2 == NULL); |
266 | 0 | else |
267 | 0 | return((s2 != NULL) && |
268 | 0 | (strcmp((const char *) s1, (const char *) s2) == 0)); |
269 | 0 | } |
270 | | |
271 | | /** |
272 | | * Try to find a matching hash table entry. If an entry was found, set |
273 | | * `found` to 1 and return the entry. Otherwise, set `found` to 0 and return |
274 | | * the location where a new entry should be inserted. |
275 | | * |
276 | | * @param hash hash table, non-NULL, size > 0 |
277 | | * @param key first string key, non-NULL |
278 | | * @param key2 second string key |
279 | | * @param key3 third string key |
280 | | * @param hashValue valid hash value of keys |
281 | | * @param pfound result of search |
282 | | */ |
283 | | ATTRIBUTE_NO_SANITIZE_INTEGER |
284 | | static xmlHashEntry * |
285 | | xmlHashFindEntry(const xmlHashTable *hash, const xmlChar *key, |
286 | | const xmlChar *key2, const xmlChar *key3, |
287 | 0 | unsigned hashValue, int *pfound) { |
288 | 0 | xmlHashEntry *entry; |
289 | 0 | unsigned mask, pos, displ; |
290 | 0 | int found = 0; |
291 | |
|
292 | 0 | mask = hash->size - 1; |
293 | 0 | pos = hashValue & mask; |
294 | 0 | entry = &hash->table[pos]; |
295 | |
|
296 | 0 | if (entry->hashValue != 0) { |
297 | | /* |
298 | | * Robin hood hashing: abort if the displacement of the entry |
299 | | * is smaller than the displacement of the key we look for. |
300 | | * This also stops at the correct position when inserting. |
301 | | */ |
302 | 0 | displ = 0; |
303 | 0 | hashValue |= MAX_HASH_SIZE; |
304 | |
|
305 | 0 | do { |
306 | 0 | if (entry->hashValue == hashValue) { |
307 | 0 | if (hash->dict) { |
308 | 0 | if ((entry->key == key) && |
309 | 0 | (entry->key2 == key2) && |
310 | 0 | (entry->key3 == key3)) { |
311 | 0 | found = 1; |
312 | 0 | break; |
313 | 0 | } |
314 | 0 | } |
315 | 0 | if ((strcmp((const char *) entry->key, |
316 | 0 | (const char *) key) == 0) && |
317 | 0 | (xmlFastStrEqual(entry->key2, key2)) && |
318 | 0 | (xmlFastStrEqual(entry->key3, key3))) { |
319 | 0 | found = 1; |
320 | 0 | break; |
321 | 0 | } |
322 | 0 | } |
323 | | |
324 | 0 | displ++; |
325 | 0 | pos++; |
326 | 0 | entry++; |
327 | 0 | if ((pos & mask) == 0) |
328 | 0 | entry = hash->table; |
329 | 0 | } while ((entry->hashValue != 0) && |
330 | 0 | (((pos - entry->hashValue) & mask) >= displ)); |
331 | 0 | } |
332 | | |
333 | 0 | *pfound = found; |
334 | 0 | return(entry); |
335 | 0 | } |
336 | | |
337 | | /** |
338 | | * Resize the hash table. |
339 | | * |
340 | | * @param hash hash table |
341 | | * @param size new size of the hash table |
342 | | * @returns 0 in case of success, -1 if a memory allocation failed. |
343 | | */ |
344 | | static int |
345 | 0 | xmlHashGrow(xmlHashTablePtr hash, unsigned size) { |
346 | 0 | const xmlHashEntry *oldentry, *oldend, *end; |
347 | 0 | xmlHashEntry *table; |
348 | 0 | unsigned oldsize, i; |
349 | | |
350 | | /* Add 0 to avoid spurious -Wtype-limits warning on 64-bit GCC */ |
351 | 0 | if ((size_t) size + 0 > SIZE_MAX / sizeof(table[0])) |
352 | 0 | return(-1); |
353 | 0 | table = xmlMalloc(size * sizeof(table[0])); |
354 | 0 | if (table == NULL) |
355 | 0 | return(-1); |
356 | 0 | memset(table, 0, size * sizeof(table[0])); |
357 | |
|
358 | 0 | oldsize = hash->size; |
359 | 0 | if (oldsize == 0) |
360 | 0 | goto done; |
361 | | |
362 | 0 | oldend = &hash->table[oldsize]; |
363 | 0 | end = &table[size]; |
364 | | |
365 | | /* |
366 | | * Robin Hood sorting order is maintained if we |
367 | | * |
368 | | * - compute hash indices with modulo |
369 | | * - resize by an integer factor |
370 | | * - start to copy from the beginning of a probe sequence |
371 | | */ |
372 | 0 | oldentry = hash->table; |
373 | 0 | while (oldentry->hashValue != 0) { |
374 | 0 | if (++oldentry >= oldend) |
375 | 0 | oldentry = hash->table; |
376 | 0 | } |
377 | |
|
378 | 0 | for (i = 0; i < oldsize; i++) { |
379 | 0 | if (oldentry->hashValue != 0) { |
380 | 0 | xmlHashEntry *entry = &table[oldentry->hashValue & (size - 1)]; |
381 | |
|
382 | 0 | while (entry->hashValue != 0) { |
383 | 0 | if (++entry >= end) |
384 | 0 | entry = table; |
385 | 0 | } |
386 | 0 | *entry = *oldentry; |
387 | 0 | } |
388 | |
|
389 | 0 | if (++oldentry >= oldend) |
390 | 0 | oldentry = hash->table; |
391 | 0 | } |
392 | |
|
393 | 0 | xmlFree(hash->table); |
394 | |
|
395 | 0 | done: |
396 | 0 | hash->table = table; |
397 | 0 | hash->size = size; |
398 | |
|
399 | 0 | return(0); |
400 | 0 | } |
401 | | |
402 | | /** |
403 | | * Internal function to add or update hash entries. |
404 | | * |
405 | | * @param hash hash table |
406 | | * @param key first string key |
407 | | * @param key2 second string key |
408 | | * @param key3 third string key |
409 | | * @param payload pointer to the payload |
410 | | * @param dealloc deallocator function for replaced item or NULL |
411 | | * @param update whether existing entries should be updated |
412 | | */ |
413 | | ATTRIBUTE_NO_SANITIZE_INTEGER |
414 | | static int |
415 | | xmlHashUpdateInternal(xmlHashTable *hash, const xmlChar *key, |
416 | | const xmlChar *key2, const xmlChar *key3, |
417 | 0 | void *payload, xmlHashDeallocator dealloc, int update) { |
418 | 0 | xmlChar *copy, *copy2, *copy3; |
419 | 0 | xmlHashEntry *entry = NULL; |
420 | 0 | size_t lengths[3] = {0, 0, 0}; |
421 | 0 | unsigned hashValue, newSize; |
422 | |
|
423 | 0 | if ((hash == NULL) || (key == NULL)) |
424 | 0 | return(-1); |
425 | | |
426 | 0 | hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, lengths); |
427 | | |
428 | | /* |
429 | | * Check for an existing entry |
430 | | */ |
431 | 0 | if (hash->size == 0) { |
432 | 0 | newSize = MIN_HASH_SIZE; |
433 | 0 | } else { |
434 | 0 | int found = 0; |
435 | |
|
436 | 0 | entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); |
437 | |
|
438 | 0 | if (found) { |
439 | 0 | if (update) { |
440 | 0 | if (dealloc) |
441 | 0 | dealloc(entry->payload, entry->key); |
442 | 0 | entry->payload = payload; |
443 | 0 | } |
444 | |
|
445 | 0 | return(0); |
446 | 0 | } |
447 | | |
448 | 0 | if (hash->nbElems + 1 > hash->size / MAX_FILL_DENOM * MAX_FILL_NUM) { |
449 | | /* This guarantees that nbElems < INT_MAX */ |
450 | 0 | if (hash->size >= MAX_HASH_SIZE) |
451 | 0 | return(-1); |
452 | 0 | newSize = hash->size * 2; |
453 | 0 | } else { |
454 | 0 | newSize = 0; |
455 | 0 | } |
456 | 0 | } |
457 | | |
458 | | /* |
459 | | * Grow the hash table if needed |
460 | | */ |
461 | 0 | if (newSize > 0) { |
462 | 0 | unsigned mask, displ, pos; |
463 | |
|
464 | 0 | if (xmlHashGrow(hash, newSize) != 0) |
465 | 0 | return(-1); |
466 | | |
467 | | /* |
468 | | * Find new entry |
469 | | */ |
470 | 0 | mask = hash->size - 1; |
471 | 0 | displ = 0; |
472 | 0 | pos = hashValue & mask; |
473 | 0 | entry = &hash->table[pos]; |
474 | |
|
475 | 0 | if (entry->hashValue != 0) { |
476 | 0 | do { |
477 | 0 | displ++; |
478 | 0 | pos++; |
479 | 0 | entry++; |
480 | 0 | if ((pos & mask) == 0) |
481 | 0 | entry = hash->table; |
482 | 0 | } while ((entry->hashValue != 0) && |
483 | 0 | ((pos - entry->hashValue) & mask) >= displ); |
484 | 0 | } |
485 | 0 | } |
486 | | |
487 | | /* |
488 | | * Copy keys |
489 | | */ |
490 | 0 | if (hash->dict != NULL) { |
491 | 0 | if (xmlDictOwns(hash->dict, key)) { |
492 | 0 | copy = (xmlChar *) key; |
493 | 0 | } else { |
494 | 0 | copy = (xmlChar *) xmlDictLookup(hash->dict, key, -1); |
495 | 0 | if (copy == NULL) |
496 | 0 | return(-1); |
497 | 0 | } |
498 | | |
499 | 0 | if ((key2 == NULL) || (xmlDictOwns(hash->dict, key2))) { |
500 | 0 | copy2 = (xmlChar *) key2; |
501 | 0 | } else { |
502 | 0 | copy2 = (xmlChar *) xmlDictLookup(hash->dict, key2, -1); |
503 | 0 | if (copy2 == NULL) |
504 | 0 | return(-1); |
505 | 0 | } |
506 | 0 | if ((key3 == NULL) || (xmlDictOwns(hash->dict, key3))) { |
507 | 0 | copy3 = (xmlChar *) key3; |
508 | 0 | } else { |
509 | 0 | copy3 = (xmlChar *) xmlDictLookup(hash->dict, key3, -1); |
510 | 0 | if (copy3 == NULL) |
511 | 0 | return(-1); |
512 | 0 | } |
513 | 0 | } else { |
514 | 0 | copy = xmlMalloc(lengths[0] + 1); |
515 | 0 | if (copy == NULL) |
516 | 0 | return(-1); |
517 | 0 | memcpy(copy, key, lengths[0] + 1); |
518 | |
|
519 | 0 | if (key2 != NULL) { |
520 | 0 | copy2 = xmlMalloc(lengths[1] + 1); |
521 | 0 | if (copy2 == NULL) { |
522 | 0 | xmlFree(copy); |
523 | 0 | return(-1); |
524 | 0 | } |
525 | 0 | memcpy(copy2, key2, lengths[1] + 1); |
526 | 0 | } else { |
527 | 0 | copy2 = NULL; |
528 | 0 | } |
529 | | |
530 | 0 | if (key3 != NULL) { |
531 | 0 | copy3 = xmlMalloc(lengths[2] + 1); |
532 | 0 | if (copy3 == NULL) { |
533 | 0 | xmlFree(copy); |
534 | 0 | xmlFree(copy2); |
535 | 0 | return(-1); |
536 | 0 | } |
537 | 0 | memcpy(copy3, key3, lengths[2] + 1); |
538 | 0 | } else { |
539 | 0 | copy3 = NULL; |
540 | 0 | } |
541 | 0 | } |
542 | | |
543 | | /* |
544 | | * Shift the remainder of the probe sequence to the right |
545 | | */ |
546 | 0 | if (entry->hashValue != 0) { |
547 | 0 | const xmlHashEntry *end = &hash->table[hash->size]; |
548 | 0 | const xmlHashEntry *cur = entry; |
549 | |
|
550 | 0 | do { |
551 | 0 | cur++; |
552 | 0 | if (cur >= end) |
553 | 0 | cur = hash->table; |
554 | 0 | } while (cur->hashValue != 0); |
555 | |
|
556 | 0 | if (cur < entry) { |
557 | | /* |
558 | | * If we traversed the end of the buffer, handle the part |
559 | | * at the start of the buffer. |
560 | | */ |
561 | 0 | memmove(&hash->table[1], hash->table, |
562 | 0 | (char *) cur - (char *) hash->table); |
563 | 0 | cur = end - 1; |
564 | 0 | hash->table[0] = *cur; |
565 | 0 | } |
566 | |
|
567 | 0 | memmove(&entry[1], entry, (char *) cur - (char *) entry); |
568 | 0 | } |
569 | | |
570 | | /* |
571 | | * Populate entry |
572 | | */ |
573 | 0 | entry->key = copy; |
574 | 0 | entry->key2 = copy2; |
575 | 0 | entry->key3 = copy3; |
576 | 0 | entry->payload = payload; |
577 | | /* OR with MAX_HASH_SIZE to make sure that the value is non-zero */ |
578 | 0 | entry->hashValue = hashValue | MAX_HASH_SIZE; |
579 | |
|
580 | 0 | hash->nbElems++; |
581 | |
|
582 | 0 | return(1); |
583 | 0 | } |
584 | | |
585 | | /** |
586 | | * Free a hash table entry with xmlFree. |
587 | | * |
588 | | * @param entry hash table entry |
589 | | * @param key the entry's string key |
590 | | */ |
591 | | void |
592 | 0 | xmlHashDefaultDeallocator(void *entry, const xmlChar *key ATTRIBUTE_UNUSED) { |
593 | 0 | xmlFree(entry); |
594 | 0 | } |
595 | | |
596 | | /** |
597 | | * Add a hash table entry. If an entry with this key already exists, |
598 | | * payload will not be updated and 0 is returned. This return value |
599 | | * can't be distinguished from out-of-memory errors, so this function |
600 | | * should be used with care. |
601 | | * |
602 | | * @since 2.13.0 |
603 | | * |
604 | | * @param hash hash table |
605 | | * @param key string key |
606 | | * @param payload pointer to the payload |
607 | | * @returns 1 on success, 0 if an entry exists and -1 in case of error. |
608 | | */ |
609 | | int |
610 | 0 | xmlHashAdd(xmlHashTable *hash, const xmlChar *key, void *payload) { |
611 | 0 | return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0)); |
612 | 0 | } |
613 | | |
614 | | /** |
615 | | * Add a hash table entry with two strings as key. |
616 | | * |
617 | | * See #xmlHashAdd. |
618 | | * |
619 | | * @since 2.13.0 |
620 | | * |
621 | | * @param hash hash table |
622 | | * @param key first string key |
623 | | * @param key2 second string key |
624 | | * @param payload pointer to the payload |
625 | | * @returns 1 on success, 0 if an entry exists and -1 in case of error. |
626 | | */ |
627 | | int |
628 | | xmlHashAdd2(xmlHashTable *hash, const xmlChar *key, |
629 | 0 | const xmlChar *key2, void *payload) { |
630 | 0 | return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0)); |
631 | 0 | } |
632 | | |
633 | | /** |
634 | | * Add a hash table entry with three strings as key. |
635 | | * |
636 | | * See #xmlHashAdd. |
637 | | * |
638 | | * @since 2.13.0 |
639 | | * |
640 | | * @param hash hash table |
641 | | * @param key first string key |
642 | | * @param key2 second string key |
643 | | * @param key3 third string key |
644 | | * @param payload pointer to the payload |
645 | | * @returns 1 on success, 0 if an entry exists and -1 in case of error. |
646 | | */ |
647 | | int |
648 | | xmlHashAdd3(xmlHashTable *hash, const xmlChar *key, |
649 | | const xmlChar *key2, const xmlChar *key3, |
650 | 0 | void *payload) { |
651 | 0 | return(xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0)); |
652 | 0 | } |
653 | | |
654 | | /** |
655 | | * Add a hash table entry. If an entry with this key already exists, |
656 | | * payload will not be updated and -1 is returned. This return value |
657 | | * can't be distinguished from out-of-memory errors, so this function |
658 | | * should be used with care. |
659 | | * |
660 | | * NOTE: This function doesn't allow to distinguish malloc failures from |
661 | | * existing entries. Use #xmlHashAdd instead. |
662 | | * |
663 | | * @param hash hash table |
664 | | * @param key string key |
665 | | * @param payload pointer to the payload |
666 | | * @returns 0 on success and -1 in case of error. |
667 | | */ |
668 | | int |
669 | 0 | xmlHashAddEntry(xmlHashTable *hash, const xmlChar *key, void *payload) { |
670 | 0 | int res = xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0); |
671 | |
|
672 | 0 | if (res == 0) |
673 | 0 | res = -1; |
674 | 0 | else if (res == 1) |
675 | 0 | res = 0; |
676 | |
|
677 | 0 | return(res); |
678 | 0 | } |
679 | | |
680 | | /** |
681 | | * Add a hash table entry with two strings as key. |
682 | | * |
683 | | * See #xmlHashAddEntry. |
684 | | * |
685 | | * @param hash hash table |
686 | | * @param key first string key |
687 | | * @param key2 second string key |
688 | | * @param payload pointer to the payload |
689 | | * @returns 0 on success and -1 in case of error. |
690 | | */ |
691 | | int |
692 | | xmlHashAddEntry2(xmlHashTable *hash, const xmlChar *key, |
693 | 0 | const xmlChar *key2, void *payload) { |
694 | 0 | int res = xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0); |
695 | |
|
696 | 0 | if (res == 0) |
697 | 0 | res = -1; |
698 | 0 | else if (res == 1) |
699 | 0 | res = 0; |
700 | |
|
701 | 0 | return(res); |
702 | 0 | } |
703 | | |
704 | | /** |
705 | | * Add a hash table entry with three strings as key. |
706 | | * |
707 | | * See #xmlHashAddEntry. |
708 | | * |
709 | | * @param hash hash table |
710 | | * @param key first string key |
711 | | * @param key2 second string key |
712 | | * @param key3 third string key |
713 | | * @param payload pointer to the payload |
714 | | * @returns 0 on success and -1 in case of error. |
715 | | */ |
716 | | int |
717 | | xmlHashAddEntry3(xmlHashTable *hash, const xmlChar *key, |
718 | | const xmlChar *key2, const xmlChar *key3, |
719 | 0 | void *payload) { |
720 | 0 | int res = xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0); |
721 | |
|
722 | 0 | if (res == 0) |
723 | 0 | res = -1; |
724 | 0 | else if (res == 1) |
725 | 0 | res = 0; |
726 | |
|
727 | 0 | return(res); |
728 | 0 | } |
729 | | |
730 | | /** |
731 | | * Add a hash table entry. If an entry with this key already exists, |
732 | | * the old payload will be freed and updated with the new value. |
733 | | * |
734 | | * @param hash hash table |
735 | | * @param key string key |
736 | | * @param payload pointer to the payload |
737 | | * @param dealloc deallocator function for replaced item or NULL |
738 | | * @returns 0 in case of success, -1 if a memory allocation failed. |
739 | | */ |
740 | | int |
741 | | xmlHashUpdateEntry(xmlHashTable *hash, const xmlChar *key, |
742 | 0 | void *payload, xmlHashDeallocator dealloc) { |
743 | 0 | int res = xmlHashUpdateInternal(hash, key, NULL, NULL, payload, |
744 | 0 | dealloc, 1); |
745 | |
|
746 | 0 | if (res == 1) |
747 | 0 | res = 0; |
748 | |
|
749 | 0 | return(res); |
750 | 0 | } |
751 | | |
752 | | /** |
753 | | * Add a hash table entry with two strings as key. |
754 | | * |
755 | | * See #xmlHashUpdateEntry. |
756 | | * |
757 | | * @param hash hash table |
758 | | * @param key first string key |
759 | | * @param key2 second string key |
760 | | * @param payload pointer to the payload |
761 | | * @param dealloc deallocator function for replaced item or NULL |
762 | | * @returns 0 on success and -1 in case of error. |
763 | | */ |
764 | | int |
765 | | xmlHashUpdateEntry2(xmlHashTable *hash, const xmlChar *key, |
766 | | const xmlChar *key2, void *payload, |
767 | 0 | xmlHashDeallocator dealloc) { |
768 | 0 | int res = xmlHashUpdateInternal(hash, key, key2, NULL, payload, |
769 | 0 | dealloc, 1); |
770 | |
|
771 | 0 | if (res == 1) |
772 | 0 | res = 0; |
773 | |
|
774 | 0 | return(res); |
775 | 0 | } |
776 | | |
777 | | /** |
778 | | * Add a hash table entry with three strings as key. |
779 | | * |
780 | | * See #xmlHashUpdateEntry. |
781 | | * |
782 | | * @param hash hash table |
783 | | * @param key first string key |
784 | | * @param key2 second string key |
785 | | * @param key3 third string key |
786 | | * @param payload pointer to the payload |
787 | | * @param dealloc deallocator function for replaced item or NULL |
788 | | * @returns 0 on success and -1 in case of error. |
789 | | */ |
790 | | int |
791 | | xmlHashUpdateEntry3(xmlHashTable *hash, const xmlChar *key, |
792 | | const xmlChar *key2, const xmlChar *key3, |
793 | 0 | void *payload, xmlHashDeallocator dealloc) { |
794 | 0 | int res = xmlHashUpdateInternal(hash, key, key2, key3, payload, |
795 | 0 | dealloc, 1); |
796 | |
|
797 | 0 | if (res == 1) |
798 | 0 | res = 0; |
799 | |
|
800 | 0 | return(res); |
801 | 0 | } |
802 | | |
803 | | /** |
804 | | * Find the entry specified by `key`. |
805 | | * |
806 | | * @param hash hash table |
807 | | * @param key string key |
808 | | * @returns a pointer to the payload or NULL if no entry was found. |
809 | | */ |
810 | | void * |
811 | 0 | xmlHashLookup(xmlHashTable *hash, const xmlChar *key) { |
812 | 0 | return(xmlHashLookup3(hash, key, NULL, NULL)); |
813 | 0 | } |
814 | | |
815 | | /** |
816 | | * Find the payload specified by the (`key`, `key2`) tuple. |
817 | | * |
818 | | * @param hash hash table |
819 | | * @param key first string key |
820 | | * @param key2 second string key |
821 | | * @returns a pointer to the payload or NULL if no entry was found. |
822 | | */ |
823 | | void * |
824 | | xmlHashLookup2(xmlHashTable *hash, const xmlChar *key, |
825 | 0 | const xmlChar *key2) { |
826 | 0 | return(xmlHashLookup3(hash, key, key2, NULL)); |
827 | 0 | } |
828 | | |
829 | | /** |
830 | | * Find the payload specified by the QName `prefix:name` or `name`. |
831 | | * |
832 | | * @param hash hash table |
833 | | * @param prefix prefix of the string key |
834 | | * @param name local name of the string key |
835 | | * @returns a pointer to the payload or NULL if no entry was found. |
836 | | */ |
837 | | void * |
838 | | xmlHashQLookup(xmlHashTable *hash, const xmlChar *prefix, |
839 | 0 | const xmlChar *name) { |
840 | 0 | return(xmlHashQLookup3(hash, prefix, name, NULL, NULL, NULL, NULL)); |
841 | 0 | } |
842 | | |
843 | | /** |
844 | | * Find the payload specified by the QNames tuple. |
845 | | * |
846 | | * @param hash hash table |
847 | | * @param prefix first prefix |
848 | | * @param name first local name |
849 | | * @param prefix2 second prefix |
850 | | * @param name2 second local name |
851 | | * @returns a pointer to the payload or NULL if no entry was found. |
852 | | */ |
853 | | void * |
854 | | xmlHashQLookup2(xmlHashTable *hash, const xmlChar *prefix, |
855 | | const xmlChar *name, const xmlChar *prefix2, |
856 | 0 | const xmlChar *name2) { |
857 | 0 | return(xmlHashQLookup3(hash, prefix, name, prefix2, name2, NULL, NULL)); |
858 | 0 | } |
859 | | |
860 | | /** |
861 | | * Find the payload specified by the (`key`, `key2`, `key3`) tuple. |
862 | | * |
863 | | * @param hash hash table |
864 | | * @param key first string key |
865 | | * @param key2 second string key |
866 | | * @param key3 third string key |
867 | | * @returns a pointer to the payload or NULL if no entry was found. |
868 | | */ |
869 | | void * |
870 | | xmlHashLookup3(xmlHashTable *hash, const xmlChar *key, |
871 | 0 | const xmlChar *key2, const xmlChar *key3) { |
872 | 0 | const xmlHashEntry *entry; |
873 | 0 | unsigned hashValue; |
874 | 0 | int found; |
875 | |
|
876 | 0 | if ((hash == NULL) || (hash->size == 0) || (key == NULL)) |
877 | 0 | return(NULL); |
878 | 0 | hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); |
879 | 0 | entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); |
880 | 0 | if (found) |
881 | 0 | return(entry->payload); |
882 | 0 | return(NULL); |
883 | 0 | } |
884 | | |
885 | | /** |
886 | | * Find the payload specified by the QNames tuple. |
887 | | * |
888 | | * @param hash hash table |
889 | | * @param prefix first prefix |
890 | | * @param name first local name |
891 | | * @param prefix2 second prefix |
892 | | * @param name2 second local name |
893 | | * @param prefix3 third prefix |
894 | | * @param name3 third local name |
895 | | * @returns a pointer to the payload or NULL if no entry was found. |
896 | | */ |
897 | | ATTRIBUTE_NO_SANITIZE_INTEGER |
898 | | void * |
899 | | xmlHashQLookup3(xmlHashTable *hash, |
900 | | const xmlChar *prefix, const xmlChar *name, |
901 | | const xmlChar *prefix2, const xmlChar *name2, |
902 | 0 | const xmlChar *prefix3, const xmlChar *name3) { |
903 | 0 | const xmlHashEntry *entry; |
904 | 0 | unsigned hashValue, mask, pos, displ; |
905 | |
|
906 | 0 | if ((hash == NULL) || (hash->size == 0) || (name == NULL)) |
907 | 0 | return(NULL); |
908 | | |
909 | 0 | hashValue = xmlHashQNameValue(hash->randomSeed, prefix, name, prefix2, |
910 | 0 | name2, prefix3, name3); |
911 | 0 | mask = hash->size - 1; |
912 | 0 | pos = hashValue & mask; |
913 | 0 | entry = &hash->table[pos]; |
914 | |
|
915 | 0 | if (entry->hashValue != 0) { |
916 | 0 | displ = 0; |
917 | 0 | hashValue |= MAX_HASH_SIZE; |
918 | |
|
919 | 0 | do { |
920 | 0 | if ((hashValue == entry->hashValue) && |
921 | 0 | (xmlStrQEqual(prefix, name, entry->key)) && |
922 | 0 | (xmlStrQEqual(prefix2, name2, entry->key2)) && |
923 | 0 | (xmlStrQEqual(prefix3, name3, entry->key3))) |
924 | 0 | return(entry->payload); |
925 | | |
926 | 0 | displ++; |
927 | 0 | pos++; |
928 | 0 | entry++; |
929 | 0 | if ((pos & mask) == 0) |
930 | 0 | entry = hash->table; |
931 | 0 | } while ((entry->hashValue != 0) && |
932 | 0 | (((pos - entry->hashValue) & mask) >= displ)); |
933 | 0 | } |
934 | | |
935 | 0 | return(NULL); |
936 | 0 | } |
937 | | |
938 | | typedef struct { |
939 | | xmlHashScanner scan; |
940 | | void *data; |
941 | | } stubData; |
942 | | |
943 | | static void |
944 | | stubHashScannerFull(void *payload, void *data, const xmlChar *key, |
945 | | const xmlChar *key2 ATTRIBUTE_UNUSED, |
946 | 0 | const xmlChar *key3 ATTRIBUTE_UNUSED) { |
947 | 0 | stubData *sdata = (stubData *) data; |
948 | 0 | sdata->scan(payload, sdata->data, key); |
949 | 0 | } |
950 | | |
951 | | /** |
952 | | * Scan the hash `table` and apply `scan` to each value. |
953 | | * |
954 | | * @param hash hash table |
955 | | * @param scan scanner function for items in the hash |
956 | | * @param data extra data passed to `scan` |
957 | | */ |
958 | | void |
959 | 0 | xmlHashScan(xmlHashTable *hash, xmlHashScanner scan, void *data) { |
960 | 0 | stubData sdata; |
961 | 0 | sdata.data = data; |
962 | 0 | sdata.scan = scan; |
963 | 0 | xmlHashScanFull(hash, stubHashScannerFull, &sdata); |
964 | 0 | } |
965 | | |
966 | | /** |
967 | | * Scan the hash `table` and apply `scan` to each value. |
968 | | * |
969 | | * @param hash hash table |
970 | | * @param scan scanner function for items in the hash |
971 | | * @param data extra data passed to `scan` |
972 | | */ |
973 | | void |
974 | 0 | xmlHashScanFull(xmlHashTable *hash, xmlHashScannerFull scan, void *data) { |
975 | 0 | const xmlHashEntry *entry, *end; |
976 | 0 | xmlHashEntry old; |
977 | 0 | unsigned i; |
978 | |
|
979 | 0 | if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) |
980 | 0 | return; |
981 | | |
982 | | /* |
983 | | * We must handle the case that a scanned entry is removed when executing |
984 | | * the callback (xmlCleanSpecialAttr and possibly other places). |
985 | | * |
986 | | * Find the start of a probe sequence to avoid scanning entries twice if |
987 | | * a deletion happens. |
988 | | */ |
989 | 0 | entry = hash->table; |
990 | 0 | end = &hash->table[hash->size]; |
991 | 0 | while (entry->hashValue != 0) { |
992 | 0 | if (++entry >= end) |
993 | 0 | entry = hash->table; |
994 | 0 | } |
995 | |
|
996 | 0 | for (i = 0; i < hash->size; i++) { |
997 | 0 | if ((entry->hashValue != 0) && (entry->payload != NULL)) { |
998 | | /* |
999 | | * Make sure to rescan after a possible deletion. |
1000 | | */ |
1001 | 0 | do { |
1002 | 0 | old = *entry; |
1003 | 0 | scan(entry->payload, data, entry->key, entry->key2, entry->key3); |
1004 | 0 | } while ((entry->hashValue != 0) && |
1005 | 0 | (entry->payload != NULL) && |
1006 | 0 | ((entry->key != old.key) || |
1007 | 0 | (entry->key2 != old.key2) || |
1008 | 0 | (entry->key3 != old.key3))); |
1009 | 0 | } |
1010 | 0 | if (++entry >= end) |
1011 | 0 | entry = hash->table; |
1012 | 0 | } |
1013 | 0 | } |
1014 | | |
1015 | | /** |
1016 | | * Scan the hash `table` and apply `scan` to each value matching |
1017 | | * (`key`, `key2`, `key3`) tuple. If one of the keys is null, |
1018 | | * the comparison is considered to match. |
1019 | | * |
1020 | | * @param hash hash table |
1021 | | * @param key first string key or NULL |
1022 | | * @param key2 second string key or NULL |
1023 | | * @param key3 third string key or NULL |
1024 | | * @param scan scanner function for items in the hash |
1025 | | * @param data extra data passed to `scan` |
1026 | | */ |
1027 | | void |
1028 | | xmlHashScan3(xmlHashTable *hash, const xmlChar *key, |
1029 | | const xmlChar *key2, const xmlChar *key3, |
1030 | 0 | xmlHashScanner scan, void *data) { |
1031 | 0 | stubData sdata; |
1032 | 0 | sdata.data = data; |
1033 | 0 | sdata.scan = scan; |
1034 | 0 | xmlHashScanFull3(hash, key, key2, key3, stubHashScannerFull, &sdata); |
1035 | 0 | } |
1036 | | |
1037 | | /** |
1038 | | * Scan the hash `table` and apply `scan` to each value matching |
1039 | | * (`key`, `key2`, `key3`) tuple. If one of the keys is null, |
1040 | | * the comparison is considered to match. |
1041 | | * |
1042 | | * @param hash hash table |
1043 | | * @param key first string key or NULL |
1044 | | * @param key2 second string key or NULL |
1045 | | * @param key3 third string key or NULL |
1046 | | * @param scan scanner function for items in the hash |
1047 | | * @param data extra data passed to `scan` |
1048 | | */ |
1049 | | void |
1050 | | xmlHashScanFull3(xmlHashTable *hash, const xmlChar *key, |
1051 | | const xmlChar *key2, const xmlChar *key3, |
1052 | 0 | xmlHashScannerFull scan, void *data) { |
1053 | 0 | const xmlHashEntry *entry, *end; |
1054 | 0 | xmlHashEntry old; |
1055 | 0 | unsigned i; |
1056 | |
|
1057 | 0 | if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) |
1058 | 0 | return; |
1059 | | |
1060 | | /* |
1061 | | * We must handle the case that a scanned entry is removed when executing |
1062 | | * the callback (xmlCleanSpecialAttr and possibly other places). |
1063 | | * |
1064 | | * Find the start of a probe sequence to avoid scanning entries twice if |
1065 | | * a deletion happens. |
1066 | | */ |
1067 | 0 | entry = hash->table; |
1068 | 0 | end = &hash->table[hash->size]; |
1069 | 0 | while (entry->hashValue != 0) { |
1070 | 0 | if (++entry >= end) |
1071 | 0 | entry = hash->table; |
1072 | 0 | } |
1073 | |
|
1074 | 0 | for (i = 0; i < hash->size; i++) { |
1075 | 0 | if ((entry->hashValue != 0) && (entry->payload != NULL)) { |
1076 | | /* |
1077 | | * Make sure to rescan after a possible deletion. |
1078 | | */ |
1079 | 0 | do { |
1080 | 0 | if (((key != NULL) && (strcmp((const char *) key, |
1081 | 0 | (const char *) entry->key) != 0)) || |
1082 | 0 | ((key2 != NULL) && (!xmlFastStrEqual(key2, entry->key2))) || |
1083 | 0 | ((key3 != NULL) && (!xmlFastStrEqual(key3, entry->key3)))) |
1084 | 0 | break; |
1085 | 0 | old = *entry; |
1086 | 0 | scan(entry->payload, data, entry->key, entry->key2, entry->key3); |
1087 | 0 | } while ((entry->hashValue != 0) && |
1088 | 0 | (entry->payload != NULL) && |
1089 | 0 | ((entry->key != old.key) || |
1090 | 0 | (entry->key2 != old.key2) || |
1091 | 0 | (entry->key3 != old.key3))); |
1092 | 0 | } |
1093 | 0 | if (++entry >= end) |
1094 | 0 | entry = hash->table; |
1095 | 0 | } |
1096 | 0 | } |
1097 | | |
1098 | | /** |
1099 | | * @param hash hash table |
1100 | | * @param copyFunc copier function for items in the hash |
1101 | | * @param deallocFunc deallocation function in case of errors |
1102 | | * |
1103 | | * Copy the hash table using `copyFunc` to copy payloads. |
1104 | | * |
1105 | | * @since 2.13.0 |
1106 | | * |
1107 | | * @returns the new table or NULL if a memory allocation failed. |
1108 | | */ |
1109 | | xmlHashTable * |
1110 | | xmlHashCopySafe(xmlHashTable *hash, xmlHashCopier copyFunc, |
1111 | 0 | xmlHashDeallocator deallocFunc) { |
1112 | 0 | const xmlHashEntry *entry, *end; |
1113 | 0 | xmlHashTablePtr ret; |
1114 | |
|
1115 | 0 | if ((hash == NULL) || (copyFunc == NULL)) |
1116 | 0 | return(NULL); |
1117 | | |
1118 | 0 | ret = xmlHashCreate(hash->size); |
1119 | 0 | if (ret == NULL) |
1120 | 0 | return(NULL); |
1121 | | |
1122 | 0 | if (hash->size == 0) |
1123 | 0 | return(ret); |
1124 | | |
1125 | 0 | end = &hash->table[hash->size]; |
1126 | |
|
1127 | 0 | for (entry = hash->table; entry < end; entry++) { |
1128 | 0 | if (entry->hashValue != 0) { |
1129 | 0 | void *copy; |
1130 | |
|
1131 | 0 | copy = copyFunc(entry->payload, entry->key); |
1132 | 0 | if (copy == NULL) |
1133 | 0 | goto error; |
1134 | 0 | if (xmlHashAdd3(ret, entry->key, entry->key2, entry->key3, |
1135 | 0 | copy) <= 0) { |
1136 | 0 | if (deallocFunc != NULL) |
1137 | 0 | deallocFunc(copy, entry->key); |
1138 | 0 | goto error; |
1139 | 0 | } |
1140 | 0 | } |
1141 | 0 | } |
1142 | | |
1143 | 0 | return(ret); |
1144 | | |
1145 | 0 | error: |
1146 | 0 | xmlHashFree(ret, deallocFunc); |
1147 | 0 | return(NULL); |
1148 | 0 | } |
1149 | | |
1150 | | /** |
1151 | | * @param hash hash table |
1152 | | * @param copy copier function for items in the hash |
1153 | | * |
1154 | | * @deprecated Leaks memory in error case. |
1155 | | * |
1156 | | * Copy the hash table using `copy` to copy payloads. |
1157 | | * |
1158 | | * @returns the new table or NULL if a memory allocation failed. |
1159 | | */ |
1160 | | xmlHashTable * |
1161 | 0 | xmlHashCopy(xmlHashTable *hash, xmlHashCopier copy) { |
1162 | 0 | return(xmlHashCopySafe(hash, copy, NULL)); |
1163 | 0 | } |
1164 | | |
1165 | | /** |
1166 | | * Query the number of elements in the hash table. |
1167 | | * |
1168 | | * @param hash hash table |
1169 | | * @returns the number of elements in the hash table or |
1170 | | * -1 in case of error. |
1171 | | */ |
1172 | | int |
1173 | 0 | xmlHashSize(xmlHashTable *hash) { |
1174 | 0 | if (hash == NULL) |
1175 | 0 | return(-1); |
1176 | 0 | return(hash->nbElems); |
1177 | 0 | } |
1178 | | |
1179 | | /** |
1180 | | * Find the entry specified by the `key` and remove it from the hash table. |
1181 | | * Payload will be freed with `dealloc`. |
1182 | | * |
1183 | | * @param hash hash table |
1184 | | * @param key string key |
1185 | | * @param dealloc deallocator function for removed item or NULL |
1186 | | * @returns 0 on success and -1 if no entry was found. |
1187 | | */ |
1188 | | int xmlHashRemoveEntry(xmlHashTable *hash, const xmlChar *key, |
1189 | 0 | xmlHashDeallocator dealloc) { |
1190 | 0 | return(xmlHashRemoveEntry3(hash, key, NULL, NULL, dealloc)); |
1191 | 0 | } |
1192 | | |
1193 | | /** |
1194 | | * Remove an entry with two strings as key. |
1195 | | * |
1196 | | * See #xmlHashRemoveEntry. |
1197 | | * |
1198 | | * @param hash hash table |
1199 | | * @param key first string key |
1200 | | * @param key2 second string key |
1201 | | * @param dealloc deallocator function for removed item or NULL |
1202 | | * @returns 0 on success and -1 in case of error. |
1203 | | */ |
1204 | | int |
1205 | | xmlHashRemoveEntry2(xmlHashTable *hash, const xmlChar *key, |
1206 | 0 | const xmlChar *key2, xmlHashDeallocator dealloc) { |
1207 | 0 | return(xmlHashRemoveEntry3(hash, key, key2, NULL, dealloc)); |
1208 | 0 | } |
1209 | | |
1210 | | /** |
1211 | | * Remove an entry with three strings as key. |
1212 | | * |
1213 | | * See #xmlHashRemoveEntry. |
1214 | | * |
1215 | | * @param hash hash table |
1216 | | * @param key first string key |
1217 | | * @param key2 second string key |
1218 | | * @param key3 third string key |
1219 | | * @param dealloc deallocator function for removed item or NULL |
1220 | | * @returns 0 on success and -1 in case of error. |
1221 | | */ |
1222 | | ATTRIBUTE_NO_SANITIZE_INTEGER |
1223 | | int |
1224 | | xmlHashRemoveEntry3(xmlHashTable *hash, const xmlChar *key, |
1225 | | const xmlChar *key2, const xmlChar *key3, |
1226 | 0 | xmlHashDeallocator dealloc) { |
1227 | 0 | xmlHashEntry *entry, *cur, *next; |
1228 | 0 | unsigned hashValue, mask, pos, nextpos; |
1229 | 0 | int found; |
1230 | |
|
1231 | 0 | if ((hash == NULL) || (hash->size == 0) || (key == NULL)) |
1232 | 0 | return(-1); |
1233 | | |
1234 | 0 | hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); |
1235 | 0 | entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); |
1236 | 0 | if (!found) |
1237 | 0 | return(-1); |
1238 | | |
1239 | 0 | if ((dealloc != NULL) && (entry->payload != NULL)) |
1240 | 0 | dealloc(entry->payload, entry->key); |
1241 | 0 | if (hash->dict == NULL) { |
1242 | 0 | if (entry->key) |
1243 | 0 | xmlFree(entry->key); |
1244 | 0 | if (entry->key2) |
1245 | 0 | xmlFree(entry->key2); |
1246 | 0 | if (entry->key3) |
1247 | 0 | xmlFree(entry->key3); |
1248 | 0 | } |
1249 | | |
1250 | | /* |
1251 | | * Find end of probe sequence. Entries at their initial probe |
1252 | | * position start a new sequence. |
1253 | | */ |
1254 | 0 | mask = hash->size - 1; |
1255 | 0 | pos = entry - hash->table; |
1256 | 0 | cur = entry; |
1257 | |
|
1258 | 0 | while (1) { |
1259 | 0 | nextpos = pos + 1; |
1260 | 0 | next = cur + 1; |
1261 | 0 | if ((nextpos & mask) == 0) |
1262 | 0 | next = hash->table; |
1263 | |
|
1264 | 0 | if ((next->hashValue == 0) || |
1265 | 0 | (((next->hashValue - nextpos) & mask) == 0)) |
1266 | 0 | break; |
1267 | | |
1268 | 0 | cur = next; |
1269 | 0 | pos = nextpos; |
1270 | 0 | } |
1271 | | |
1272 | | /* |
1273 | | * Backward shift |
1274 | | */ |
1275 | 0 | next = entry + 1; |
1276 | |
|
1277 | 0 | if (cur < entry) { |
1278 | 0 | xmlHashEntry *end = &hash->table[hash->size]; |
1279 | |
|
1280 | 0 | memmove(entry, next, (char *) end - (char *) next); |
1281 | 0 | entry = hash->table; |
1282 | 0 | end[-1] = *entry; |
1283 | 0 | next = entry + 1; |
1284 | 0 | } |
1285 | |
|
1286 | 0 | memmove(entry, next, (char *) cur - (char *) entry); |
1287 | | |
1288 | | /* |
1289 | | * Update entry |
1290 | | */ |
1291 | 0 | cur->hashValue = 0; |
1292 | |
|
1293 | 0 | hash->nbElems--; |
1294 | |
|
1295 | 0 | return(0); |
1296 | 0 | } |
1297 | | |