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