Coverage Report

Created: 2025-07-01 06:26

/src/libxml2/hash.c
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