Coverage Report

Created: 2023-09-25 06:03

/src/libxml2-2.11.5/hash.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * hash.c: chained hash tables
3
 *
4
 * Reference: Your favorite introductory book on algorithms
5
 *
6
 * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard.
7
 *
8
 * Permission to use, copy, modify, and distribute this software for any
9
 * purpose with or without fee is hereby granted, provided that the above
10
 * copyright notice and this permission notice appear in all copies.
11
 *
12
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
13
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
14
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
15
 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
16
 *
17
 * Author: breese@users.sourceforge.net
18
 */
19
20
#define IN_LIBXML
21
#include "libxml.h"
22
23
#include <string.h>
24
#include <stdlib.h>
25
#include <time.h>
26
27
/*
28
 * Following http://www.ocert.org/advisories/ocert-2011-003.html
29
 * it seems that having hash randomization might be a good idea
30
 * when using XML with untrusted data
31
 */
32
#if !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION)
33
#define HASH_RANDOMIZATION
34
#endif
35
36
#include <libxml/parser.h>
37
#include <libxml/hash.h>
38
#include <libxml/xmlmemory.h>
39
#include <libxml/xmlerror.h>
40
#include <libxml/globals.h>
41
42
#include "private/dict.h"
43
44
12.4k
#define MAX_HASH_LEN 8
45
46
/* #define DEBUG_GROW */
47
48
/*
49
 * A single entry in the hash table
50
 */
51
typedef struct _xmlHashEntry xmlHashEntry;
52
typedef xmlHashEntry *xmlHashEntryPtr;
53
struct _xmlHashEntry {
54
    struct _xmlHashEntry *next;
55
    xmlChar *name;
56
    xmlChar *name2;
57
    xmlChar *name3;
58
    void *payload;
59
    int valid;
60
};
61
62
/*
63
 * The entire hash table
64
 */
65
struct _xmlHashTable {
66
    struct _xmlHashEntry *table;
67
    int size;
68
    int nbElems;
69
    xmlDictPtr dict;
70
#ifdef HASH_RANDOMIZATION
71
    int random_seed;
72
#endif
73
};
74
75
/*
76
 * xmlHashComputeKey:
77
 * Calculate the hash key
78
 */
79
#ifdef __clang__
80
ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
81
ATTRIBUTE_NO_SANITIZE("unsigned-shift-base")
82
#endif
83
static unsigned long
84
xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
85
81.4k
            const xmlChar *name2, const xmlChar *name3) {
86
81.4k
    unsigned long value = 0L;
87
81.4k
    unsigned long ch;
88
89
#ifdef HASH_RANDOMIZATION
90
    value = table->random_seed;
91
#endif
92
81.4k
    if (name != NULL) {
93
81.4k
  value += 30 * (*name);
94
2.69M
  while ((ch = *name++) != 0) {
95
2.61M
      value = value ^ ((value << 5) + (value >> 3) + ch);
96
2.61M
  }
97
81.4k
    }
98
81.4k
    value = value ^ ((value << 5) + (value >> 3));
99
81.4k
    if (name2 != NULL) {
100
605k
  while ((ch = *name2++) != 0) {
101
556k
      value = value ^ ((value << 5) + (value >> 3) + ch);
102
556k
  }
103
49.5k
    }
104
81.4k
    value = value ^ ((value << 5) + (value >> 3));
105
81.4k
    if (name3 != NULL) {
106
0
  while ((ch = *name3++) != 0) {
107
0
      value = value ^ ((value << 5) + (value >> 3) + ch);
108
0
  }
109
0
    }
110
81.4k
    return (value % table->size);
111
81.4k
}
112
113
#ifdef __clang__
114
ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
115
ATTRIBUTE_NO_SANITIZE("unsigned-shift-base")
116
#endif
117
static unsigned long
118
xmlHashComputeQKey(xmlHashTablePtr table,
119
       const xmlChar *prefix, const xmlChar *name,
120
       const xmlChar *prefix2, const xmlChar *name2,
121
8.05k
       const xmlChar *prefix3, const xmlChar *name3) {
122
8.05k
    unsigned long value = 0L;
123
8.05k
    unsigned long ch;
124
125
#ifdef HASH_RANDOMIZATION
126
    value = table->random_seed;
127
#endif
128
8.05k
    if (prefix != NULL)
129
553
  value += 30 * (*prefix);
130
7.50k
    else
131
7.50k
  value += 30 * (*name);
132
133
8.05k
    if (prefix != NULL) {
134
1.86k
  while ((ch = *prefix++) != 0) {
135
1.30k
      value = value ^ ((value << 5) + (value >> 3) + ch);
136
1.30k
  }
137
553
  value = value ^ ((value << 5) + (value >> 3) + ':');
138
553
    }
139
8.05k
    if (name != NULL) {
140
20.3k
  while ((ch = *name++) != 0) {
141
12.2k
      value = value ^ ((value << 5) + (value >> 3) + ch);
142
12.2k
  }
143
8.05k
    }
144
8.05k
    value = value ^ ((value << 5) + (value >> 3));
145
8.05k
    if (prefix2 != NULL) {
146
6.96k
  while ((ch = *prefix2++) != 0) {
147
5.59k
      value = value ^ ((value << 5) + (value >> 3) + ch);
148
5.59k
  }
149
1.37k
  value = value ^ ((value << 5) + (value >> 3) + ':');
150
1.37k
    }
151
8.05k
    if (name2 != NULL) {
152
31.0k
  while ((ch = *name2++) != 0) {
153
23.0k
      value = value ^ ((value << 5) + (value >> 3) + ch);
154
23.0k
  }
155
8.05k
    }
156
8.05k
    value = value ^ ((value << 5) + (value >> 3));
157
8.05k
    if (prefix3 != NULL) {
158
0
  while ((ch = *prefix3++) != 0) {
159
0
      value = value ^ ((value << 5) + (value >> 3) + ch);
160
0
  }
161
0
  value = value ^ ((value << 5) + (value >> 3) + ':');
162
0
    }
163
8.05k
    if (name3 != NULL) {
164
0
  while ((ch = *name3++) != 0) {
165
0
      value = value ^ ((value << 5) + (value >> 3) + ch);
166
0
  }
167
0
    }
168
8.05k
    return (value % table->size);
169
8.05k
}
170
171
/**
172
 * xmlHashCreate:
173
 * @size: the size of the hash table
174
 *
175
 * Create a new xmlHashTablePtr.
176
 *
177
 * Returns the newly created object, or NULL if an error occurred.
178
 */
179
xmlHashTablePtr
180
1.71k
xmlHashCreate(int size) {
181
1.71k
    xmlHashTablePtr table;
182
183
1.71k
    xmlInitParser();
184
185
1.71k
    if (size <= 0)
186
505
        size = 256;
187
188
1.71k
    table = xmlMalloc(sizeof(xmlHashTable));
189
1.71k
    if (table) {
190
1.71k
        table->dict = NULL;
191
1.71k
        table->size = size;
192
1.71k
  table->nbElems = 0;
193
1.71k
        table->table = xmlMalloc(size * sizeof(xmlHashEntry));
194
1.71k
        if (table->table) {
195
1.71k
      memset(table->table, 0, size * sizeof(xmlHashEntry));
196
#ifdef HASH_RANDOMIZATION
197
            table->random_seed = __xmlRandom();
198
#endif
199
1.71k
      return(table);
200
1.71k
        }
201
0
        xmlFree(table);
202
0
    }
203
0
    return(NULL);
204
1.71k
}
205
206
/**
207
 * xmlHashCreateDict:
208
 * @size: the size of the hash table
209
 * @dict: a dictionary to use for the hash
210
 *
211
 * Create a new xmlHashTablePtr which will use @dict as the internal dictionary
212
 *
213
 * Returns the newly created object, or NULL if an error occurred.
214
 */
215
xmlHashTablePtr
216
1.71k
xmlHashCreateDict(int size, xmlDictPtr dict) {
217
1.71k
    xmlHashTablePtr table;
218
219
1.71k
    table = xmlHashCreate(size);
220
1.71k
    if (table != NULL) {
221
1.71k
        table->dict = dict;
222
1.71k
  xmlDictReference(dict);
223
1.71k
    }
224
1.71k
    return(table);
225
1.71k
}
226
227
/**
228
 * xmlHashGrow:
229
 * @table: the hash table
230
 * @size: the new size of the hash table
231
 *
232
 * resize the hash table
233
 *
234
 * Returns 0 in case of success, -1 in case of failure
235
 */
236
static int
237
80
xmlHashGrow(xmlHashTablePtr table, int size) {
238
80
    unsigned long key;
239
80
    int oldsize, i;
240
80
    xmlHashEntryPtr iter, next;
241
80
    struct _xmlHashEntry *oldtable;
242
#ifdef DEBUG_GROW
243
    unsigned long nbElem = 0;
244
#endif
245
246
80
    if (table == NULL)
247
0
  return(-1);
248
80
    if (size < 8)
249
0
        return(-1);
250
80
    if (size > 8 * 2048)
251
0
  return(-1);
252
253
80
    oldsize = table->size;
254
80
    oldtable = table->table;
255
80
    if (oldtable == NULL)
256
0
        return(-1);
257
258
80
    table->table = xmlMalloc(size * sizeof(xmlHashEntry));
259
80
    if (table->table == NULL) {
260
0
  table->table = oldtable;
261
0
  return(-1);
262
0
    }
263
80
    memset(table->table, 0, size * sizeof(xmlHashEntry));
264
80
    table->size = size;
265
266
    /*  If the two loops are merged, there would be situations where
267
  a new entry needs to allocated and data copied into it from
268
  the main table. So instead, we run through the array twice, first
269
  copying all the elements in the main array (where we can't get
270
  conflicts) and then the rest, so we only free (and don't allocate)
271
    */
272
1.86k
    for (i = 0; i < oldsize; i++) {
273
1.78k
  if (oldtable[i].valid == 0)
274
152
      continue;
275
1.62k
  key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
276
1.62k
        oldtable[i].name3);
277
1.62k
  memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
278
1.62k
  table->table[key].next = NULL;
279
1.62k
    }
280
281
1.86k
    for (i = 0; i < oldsize; i++) {
282
1.78k
  iter = oldtable[i].next;
283
7.51k
  while (iter) {
284
5.73k
      next = iter->next;
285
286
      /*
287
       * put back the entry in the new table
288
       */
289
290
5.73k
      key = xmlHashComputeKey(table, iter->name, iter->name2,
291
5.73k
                        iter->name3);
292
5.73k
      if (table->table[key].valid == 0) {
293
3.78k
    memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
294
3.78k
    table->table[key].next = NULL;
295
3.78k
    xmlFree(iter);
296
3.78k
      } else {
297
1.95k
    iter->next = table->table[key].next;
298
1.95k
    table->table[key].next = iter;
299
1.95k
      }
300
301
#ifdef DEBUG_GROW
302
      nbElem++;
303
#endif
304
305
5.73k
      iter = next;
306
5.73k
  }
307
1.78k
    }
308
309
80
    xmlFree(oldtable);
310
311
#ifdef DEBUG_GROW
312
    xmlGenericError(xmlGenericErrorContext,
313
      "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
314
#endif
315
316
80
    return(0);
317
80
}
318
319
/**
320
 * xmlHashFree:
321
 * @table: the hash table
322
 * @f:  the deallocator function for items in the hash
323
 *
324
 * Free the hash @table and its contents. The userdata is
325
 * deallocated with @f if provided.
326
 */
327
void
328
1.71k
xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
329
1.71k
    int i;
330
1.71k
    xmlHashEntryPtr iter;
331
1.71k
    xmlHashEntryPtr next;
332
1.71k
    int inside_table = 0;
333
1.71k
    int nbElems;
334
335
1.71k
    if (table == NULL)
336
0
  return;
337
1.71k
    if (table->table) {
338
1.71k
  nbElems = table->nbElems;
339
101k
  for(i = 0; (i < table->size) && (nbElems > 0); i++) {
340
99.7k
      iter = &(table->table[i]);
341
99.7k
      if (iter->valid == 0)
342
91.0k
    continue;
343
8.62k
      inside_table = 1;
344
22.8k
      while (iter) {
345
14.2k
    next = iter->next;
346
14.2k
    if ((f != NULL) && (iter->payload != NULL))
347
2.73k
        f(iter->payload, iter->name);
348
14.2k
    if (table->dict == NULL) {
349
727
        if (iter->name)
350
727
      xmlFree(iter->name);
351
727
        if (iter->name2)
352
0
      xmlFree(iter->name2);
353
727
        if (iter->name3)
354
0
      xmlFree(iter->name3);
355
727
    }
356
14.2k
    iter->payload = NULL;
357
14.2k
    if (!inside_table)
358
5.62k
        xmlFree(iter);
359
14.2k
    nbElems--;
360
14.2k
    inside_table = 0;
361
14.2k
    iter = next;
362
14.2k
      }
363
8.62k
  }
364
1.71k
  xmlFree(table->table);
365
1.71k
    }
366
1.71k
    if (table->dict)
367
1.20k
        xmlDictFree(table->dict);
368
1.71k
    xmlFree(table);
369
1.71k
}
370
371
/**
372
 * xmlHashDefaultDeallocator:
373
 * @entry: the hash table entry
374
 * @name: the entry's name
375
 *
376
 * Free a hash table entry with xmlFree.
377
 */
378
void
379
2.01k
xmlHashDefaultDeallocator(void *entry, const xmlChar *name ATTRIBUTE_UNUSED) {
380
2.01k
    xmlFree(entry);
381
2.01k
}
382
383
/**
384
 * xmlHashAddEntry:
385
 * @table: the hash table
386
 * @name: the name of the userdata
387
 * @userdata: a pointer to the userdata
388
 *
389
 * Add the @userdata to the hash @table. This can later be retrieved
390
 * by using the @name. Duplicate names generate errors.
391
 *
392
 * Returns 0 the addition succeeded and -1 in case of error.
393
 */
394
int
395
10.4k
xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
396
10.4k
    return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
397
10.4k
}
398
399
/**
400
 * xmlHashAddEntry2:
401
 * @table: the hash table
402
 * @name: the name of the userdata
403
 * @name2: a second name of the userdata
404
 * @userdata: a pointer to the userdata
405
 *
406
 * Add the @userdata to the hash @table. This can later be retrieved
407
 * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
408
 *
409
 * Returns 0 the addition succeeded and -1 in case of error.
410
 */
411
int
412
xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
413
11.6k
          const xmlChar *name2, void *userdata) {
414
11.6k
    return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
415
11.6k
}
416
417
/**
418
 * xmlHashUpdateEntry:
419
 * @table: the hash table
420
 * @name: the name of the userdata
421
 * @userdata: a pointer to the userdata
422
 * @f: the deallocator function for replaced item (if any)
423
 *
424
 * Add the @userdata to the hash @table. This can later be retrieved
425
 * by using the @name. Existing entry for this @name will be removed
426
 * and freed with @f if found.
427
 *
428
 * Returns 0 the addition succeeded and -1 in case of error.
429
 */
430
int
431
xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
432
0
             void *userdata, xmlHashDeallocator f) {
433
0
    return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
434
0
}
435
436
/**
437
 * xmlHashUpdateEntry2:
438
 * @table: the hash table
439
 * @name: the name of the userdata
440
 * @name2: a second name of the userdata
441
 * @userdata: a pointer to the userdata
442
 * @f: the deallocator function for replaced item (if any)
443
 *
444
 * Add the @userdata to the hash @table. This can later be retrieved
445
 * by using the (@name, @name2) tuple. Existing entry for this tuple will
446
 * be removed and freed with @f if found.
447
 *
448
 * Returns 0 the addition succeeded and -1 in case of error.
449
 */
450
int
451
xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
452
             const xmlChar *name2, void *userdata,
453
3.38k
       xmlHashDeallocator f) {
454
3.38k
    return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
455
3.38k
}
456
457
/**
458
 * xmlHashLookup:
459
 * @table: the hash table
460
 * @name: the name of the userdata
461
 *
462
 * Find the userdata specified by the @name.
463
 *
464
 * Returns the pointer to the userdata
465
 */
466
void *
467
0
xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
468
0
    return(xmlHashLookup3(table, name, NULL, NULL));
469
0
}
470
471
/**
472
 * xmlHashLookup2:
473
 * @table: the hash table
474
 * @name: the name of the userdata
475
 * @name2: a second name of the userdata
476
 *
477
 * Find the userdata specified by the (@name, @name2) tuple.
478
 *
479
 * Returns the pointer to the userdata
480
 */
481
void *
482
xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
483
48.4k
        const xmlChar *name2) {
484
48.4k
    return(xmlHashLookup3(table, name, name2, NULL));
485
48.4k
}
486
487
/**
488
 * xmlHashQLookup:
489
 * @table: the hash table
490
 * @prefix: the prefix of the userdata
491
 * @name: the name of the userdata
492
 *
493
 * Find the userdata specified by the QName @prefix:@name/@name.
494
 *
495
 * Returns the pointer to the userdata
496
 */
497
void *
498
xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
499
0
               const xmlChar *name) {
500
0
    return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
501
0
}
502
503
/**
504
 * xmlHashQLookup2:
505
 * @table: the hash table
506
 * @prefix: the prefix of the userdata
507
 * @name: the name of the userdata
508
 * @prefix2: the second prefix of the userdata
509
 * @name2: a second name of the userdata
510
 *
511
 * Find the userdata specified by the QNames tuple
512
 *
513
 * Returns the pointer to the userdata
514
 */
515
void *
516
xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
517
                const xmlChar *name, const xmlChar *prefix2,
518
8.05k
          const xmlChar *name2) {
519
8.05k
    return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
520
8.05k
}
521
522
/**
523
 * xmlHashAddEntry3:
524
 * @table: the hash table
525
 * @name: the name of the userdata
526
 * @name2: a second name of the userdata
527
 * @name3: a third name of the userdata
528
 * @userdata: a pointer to the userdata
529
 *
530
 * Add the @userdata to the hash @table. This can later be retrieved
531
 * by using the tuple (@name, @name2, @name3). Duplicate entries generate
532
 * errors.
533
 *
534
 * Returns 0 the addition succeeded and -1 in case of error.
535
 */
536
int
537
xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
538
           const xmlChar *name2, const xmlChar *name3,
539
22.0k
     void *userdata) {
540
22.0k
    unsigned long key, len = 0;
541
22.0k
    xmlHashEntryPtr entry;
542
22.0k
    xmlHashEntryPtr insert;
543
544
22.0k
    if ((table == NULL) || (name == NULL))
545
0
  return(-1);
546
547
    /*
548
     * If using a dict internalize if needed
549
     */
550
22.0k
    if (table->dict) {
551
11.6k
        if (!xmlDictOwns(table->dict, name)) {
552
0
      name = xmlDictLookup(table->dict, name, -1);
553
0
      if (name == NULL)
554
0
          return(-1);
555
0
  }
556
11.6k
        if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
557
0
      name2 = xmlDictLookup(table->dict, name2, -1);
558
0
      if (name2 == NULL)
559
0
          return(-1);
560
0
  }
561
11.6k
        if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
562
0
      name3 = xmlDictLookup(table->dict, name3, -1);
563
0
      if (name3 == NULL)
564
0
          return(-1);
565
0
  }
566
11.6k
    }
567
568
    /*
569
     * Check for duplicate and insertion location.
570
     */
571
22.0k
    key = xmlHashComputeKey(table, name, name2, name3);
572
22.0k
    if (table->table[key].valid == 0) {
573
3.94k
  insert = NULL;
574
18.1k
    } else {
575
18.1k
        if (table->dict) {
576
24.9k
      for (insert = &(table->table[key]); insert->next != NULL;
577
16.5k
     insert = insert->next) {
578
16.5k
    if ((insert->name == name) &&
579
16.5k
        (insert->name2 == name2) &&
580
16.5k
        (insert->name3 == name3))
581
0
        return(-1);
582
16.5k
    len++;
583
16.5k
      }
584
8.36k
      if ((insert->name == name) &&
585
8.36k
    (insert->name2 == name2) &&
586
8.36k
    (insert->name3 == name3))
587
0
    return(-1);
588
9.77k
  } else {
589
10.8k
      for (insert = &(table->table[key]); insert->next != NULL;
590
9.77k
     insert = insert->next) {
591
1.99k
    if ((xmlStrEqual(insert->name, name)) &&
592
1.99k
        (xmlStrEqual(insert->name2, name2)) &&
593
1.99k
        (xmlStrEqual(insert->name3, name3)))
594
955
        return(-1);
595
1.03k
    len++;
596
1.03k
      }
597
8.81k
      if ((xmlStrEqual(insert->name, name)) &&
598
8.81k
    (xmlStrEqual(insert->name2, name2)) &&
599
8.81k
    (xmlStrEqual(insert->name3, name3)))
600
8.76k
    return(-1);
601
8.81k
  }
602
18.1k
    }
603
604
12.3k
    if (insert == NULL) {
605
3.94k
  entry = &(table->table[key]);
606
8.42k
    } else {
607
8.42k
  entry = xmlMalloc(sizeof(xmlHashEntry));
608
8.42k
  if (entry == NULL)
609
0
       return(-1);
610
8.42k
    }
611
612
12.3k
    if (table->dict != NULL) {
613
11.6k
        entry->name = (xmlChar *) name;
614
11.6k
        entry->name2 = (xmlChar *) name2;
615
11.6k
        entry->name3 = (xmlChar *) name3;
616
11.6k
    } else {
617
727
  entry->name = xmlStrdup(name);
618
727
        if (entry->name == NULL) {
619
0
            entry->name2 = NULL;
620
0
            goto error;
621
0
        }
622
727
        if (name2 == NULL) {
623
727
            entry->name2 = NULL;
624
727
        } else {
625
0
      entry->name2 = xmlStrdup(name2);
626
0
            if (entry->name2 == NULL)
627
0
                goto error;
628
0
        }
629
727
        if (name3 == NULL) {
630
727
            entry->name3 = NULL;
631
727
        } else {
632
0
      entry->name3 = xmlStrdup(name3);
633
0
            if (entry->name3 == NULL)
634
0
                goto error;
635
0
        }
636
727
    }
637
12.3k
    entry->payload = userdata;
638
12.3k
    entry->next = NULL;
639
12.3k
    entry->valid = 1;
640
641
642
12.3k
    if (insert != NULL)
643
8.42k
  insert->next = entry;
644
645
12.3k
    table->nbElems++;
646
647
12.3k
    if (len > MAX_HASH_LEN)
648
80
  xmlHashGrow(table, MAX_HASH_LEN * table->size);
649
650
12.3k
    return(0);
651
652
0
error:
653
0
    xmlFree(entry->name2);
654
0
    xmlFree(entry->name);
655
0
    if (insert != NULL)
656
0
        xmlFree(entry);
657
0
    return(-1);
658
12.3k
}
659
660
/**
661
 * xmlHashUpdateEntry3:
662
 * @table: the hash table
663
 * @name: the name of the userdata
664
 * @name2: a second name of the userdata
665
 * @name3: a third name of the userdata
666
 * @userdata: a pointer to the userdata
667
 * @f: the deallocator function for replaced item (if any)
668
 *
669
 * Add the @userdata to the hash @table. This can later be retrieved
670
 * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
671
 * will be removed and freed with @f if found.
672
 *
673
 * Returns 0 the addition succeeded and -1 in case of error.
674
 */
675
int
676
xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
677
             const xmlChar *name2, const xmlChar *name3,
678
3.38k
       void *userdata, xmlHashDeallocator f) {
679
3.38k
    unsigned long key;
680
3.38k
    xmlHashEntryPtr entry;
681
3.38k
    xmlHashEntryPtr insert;
682
683
3.38k
    if ((table == NULL) || name == NULL)
684
0
  return(-1);
685
686
    /*
687
     * If using a dict internalize if needed
688
     */
689
3.38k
    if (table->dict) {
690
3.38k
        if (!xmlDictOwns(table->dict, name)) {
691
0
      name = xmlDictLookup(table->dict, name, -1);
692
0
      if (name == NULL)
693
0
          return(-1);
694
0
  }
695
3.38k
        if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
696
0
      name2 = xmlDictLookup(table->dict, name2, -1);
697
0
      if (name2 == NULL)
698
0
          return(-1);
699
0
  }
700
3.38k
        if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
701
0
      name3 = xmlDictLookup(table->dict, name3, -1);
702
0
      if (name3 == NULL)
703
0
          return(-1);
704
0
  }
705
3.38k
    }
706
707
    /*
708
     * Check for duplicate and insertion location.
709
     */
710
3.38k
    key = xmlHashComputeKey(table, name, name2, name3);
711
3.38k
    if (table->table[key].valid == 0) {
712
967
  insert = NULL;
713
2.41k
    } else {
714
2.41k
        if (table ->dict) {
715
7.27k
      for (insert = &(table->table[key]); insert->next != NULL;
716
4.87k
     insert = insert->next) {
717
4.87k
    if ((insert->name == name) &&
718
4.87k
        (insert->name2 == name2) &&
719
4.87k
        (insert->name3 == name3)) {
720
13
        if (f)
721
0
      f(insert->payload, insert->name);
722
13
        insert->payload = userdata;
723
13
        return(0);
724
13
    }
725
4.87k
      }
726
2.40k
      if ((insert->name == name) &&
727
2.40k
    (insert->name2 == name2) &&
728
2.40k
    (insert->name3 == name3)) {
729
1.35k
    if (f)
730
0
        f(insert->payload, insert->name);
731
1.35k
    insert->payload = userdata;
732
1.35k
    return(0);
733
1.35k
      }
734
2.40k
  } else {
735
0
      for (insert = &(table->table[key]); insert->next != NULL;
736
0
     insert = insert->next) {
737
0
    if ((xmlStrEqual(insert->name, name)) &&
738
0
        (xmlStrEqual(insert->name2, name2)) &&
739
0
        (xmlStrEqual(insert->name3, name3))) {
740
0
        if (f)
741
0
      f(insert->payload, insert->name);
742
0
        insert->payload = userdata;
743
0
        return(0);
744
0
    }
745
0
      }
746
0
      if ((xmlStrEqual(insert->name, name)) &&
747
0
    (xmlStrEqual(insert->name2, name2)) &&
748
0
    (xmlStrEqual(insert->name3, name3))) {
749
0
    if (f)
750
0
        f(insert->payload, insert->name);
751
0
    insert->payload = userdata;
752
0
    return(0);
753
0
      }
754
0
  }
755
2.41k
    }
756
757
2.01k
    if (insert == NULL) {
758
967
  entry =  &(table->table[key]);
759
1.04k
    } else {
760
1.04k
  entry = xmlMalloc(sizeof(xmlHashEntry));
761
1.04k
  if (entry == NULL)
762
0
       return(-1);
763
1.04k
    }
764
765
2.01k
    if (table->dict != NULL) {
766
2.01k
        entry->name = (xmlChar *) name;
767
2.01k
        entry->name2 = (xmlChar *) name2;
768
2.01k
        entry->name3 = (xmlChar *) name3;
769
2.01k
    } else {
770
0
  entry->name = xmlStrdup(name);
771
0
        if (entry->name == NULL) {
772
0
            entry->name2 = NULL;
773
0
            goto error;
774
0
        }
775
0
        if (name2 == NULL) {
776
0
            entry->name2 = NULL;
777
0
        } else {
778
0
      entry->name2 = xmlStrdup(name2);
779
0
            if (entry->name2 == NULL)
780
0
                goto error;
781
0
        }
782
0
        if (name3 == NULL) {
783
0
            entry->name3 = NULL;
784
0
        } else {
785
0
      entry->name3 = xmlStrdup(name3);
786
0
            if (entry->name3 == NULL)
787
0
                goto error;
788
0
        }
789
0
    }
790
2.01k
    entry->payload = userdata;
791
2.01k
    entry->next = NULL;
792
2.01k
    entry->valid = 1;
793
2.01k
    table->nbElems++;
794
795
796
2.01k
    if (insert != NULL) {
797
1.04k
  insert->next = entry;
798
1.04k
    }
799
2.01k
    return(0);
800
801
0
error:
802
0
    xmlFree(entry->name2);
803
0
    xmlFree(entry->name);
804
0
    if (insert != NULL)
805
0
        xmlFree(entry);
806
0
    return(-1);
807
2.01k
}
808
809
/**
810
 * xmlHashLookup3:
811
 * @table: the hash table
812
 * @name: the name of the userdata
813
 * @name2: a second name of the userdata
814
 * @name3: a third name of the userdata
815
 *
816
 * Find the userdata specified by the (@name, @name2, @name3) tuple.
817
 *
818
 * Returns the a pointer to the userdata
819
 */
820
void *
821
xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
822
48.4k
         const xmlChar *name2, const xmlChar *name3) {
823
48.4k
    unsigned long key;
824
48.4k
    xmlHashEntryPtr entry;
825
826
48.4k
    if (table == NULL)
827
0
  return(NULL);
828
48.4k
    if (name == NULL)
829
0
  return(NULL);
830
48.4k
    key = xmlHashComputeKey(table, name, name2, name3);
831
48.4k
    if (table->table[key].valid == 0)
832
12.7k
  return(NULL);
833
35.7k
    if (table->dict) {
834
100k
  for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
835
82.8k
      if ((entry->name == name) &&
836
82.8k
    (entry->name2 == name2) &&
837
82.8k
    (entry->name3 == name3))
838
18.2k
    return(entry->payload);
839
82.8k
  }
840
35.7k
    }
841
71.0k
    for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
842
53.5k
  if ((xmlStrEqual(entry->name, name)) &&
843
53.5k
      (xmlStrEqual(entry->name2, name2)) &&
844
53.5k
      (xmlStrEqual(entry->name3, name3)))
845
0
      return(entry->payload);
846
53.5k
    }
847
17.4k
    return(NULL);
848
17.4k
}
849
850
/**
851
 * xmlHashQLookup3:
852
 * @table: the hash table
853
 * @prefix: the prefix of the userdata
854
 * @name: the name of the userdata
855
 * @prefix2: the second prefix of the userdata
856
 * @name2: a second name of the userdata
857
 * @prefix3: the third prefix of the userdata
858
 * @name3: a third name of the userdata
859
 *
860
 * Find the userdata specified by the (@name, @name2, @name3) tuple.
861
 *
862
 * Returns the a pointer to the userdata
863
 */
864
void *
865
xmlHashQLookup3(xmlHashTablePtr table,
866
                const xmlChar *prefix, const xmlChar *name,
867
    const xmlChar *prefix2, const xmlChar *name2,
868
8.05k
    const xmlChar *prefix3, const xmlChar *name3) {
869
8.05k
    unsigned long key;
870
8.05k
    xmlHashEntryPtr entry;
871
872
8.05k
    if (table == NULL)
873
0
  return(NULL);
874
8.05k
    if (name == NULL)
875
0
  return(NULL);
876
8.05k
    key = xmlHashComputeQKey(table, prefix, name, prefix2,
877
8.05k
                             name2, prefix3, name3);
878
8.05k
    if (table->table[key].valid == 0)
879
2.79k
  return(NULL);
880
8.64k
    for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
881
7.32k
  if ((xmlStrQEqual(prefix, name, entry->name)) &&
882
7.32k
      (xmlStrQEqual(prefix2, name2, entry->name2)) &&
883
7.32k
      (xmlStrQEqual(prefix3, name3, entry->name3)))
884
3.94k
      return(entry->payload);
885
7.32k
    }
886
1.32k
    return(NULL);
887
5.26k
}
888
889
typedef struct {
890
    xmlHashScanner hashscanner;
891
    void *data;
892
} stubData;
893
894
static void
895
stubHashScannerFull (void *payload, void *data, const xmlChar *name,
896
                     const xmlChar *name2 ATTRIBUTE_UNUSED,
897
0
         const xmlChar *name3 ATTRIBUTE_UNUSED) {
898
0
    stubData *stubdata = (stubData *) data;
899
0
    stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
900
0
}
901
902
/**
903
 * xmlHashScan:
904
 * @table: the hash table
905
 * @f:  the scanner function for items in the hash
906
 * @data:  extra data passed to f
907
 *
908
 * Scan the hash @table and applied @f to each value.
909
 */
910
void
911
0
xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
912
0
    stubData stubdata;
913
0
    stubdata.data = data;
914
0
    stubdata.hashscanner = f;
915
0
    xmlHashScanFull (table, stubHashScannerFull, &stubdata);
916
0
}
917
918
/**
919
 * xmlHashScanFull:
920
 * @table: the hash table
921
 * @f:  the scanner function for items in the hash
922
 * @data:  extra data passed to f
923
 *
924
 * Scan the hash @table and applied @f to each value.
925
 */
926
void
927
463
xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
928
463
    int i, nb;
929
463
    xmlHashEntryPtr iter;
930
463
    xmlHashEntryPtr next;
931
932
463
    if (table == NULL)
933
0
  return;
934
463
    if (f == NULL)
935
0
  return;
936
937
463
    if (table->table) {
938
7.54k
  for(i = 0; i < table->size; i++) {
939
7.08k
      if (table->table[i].valid == 0)
940
5.33k
    continue;
941
1.74k
      iter = &(table->table[i]);
942
4.26k
      while (iter) {
943
2.51k
    next = iter->next;
944
2.51k
                nb = table->nbElems;
945
2.51k
    if ((f != NULL) && (iter->payload != NULL))
946
2.51k
        f(iter->payload, data, iter->name,
947
2.51k
          iter->name2, iter->name3);
948
2.51k
                if (nb != table->nbElems) {
949
                    /* table was modified by the callback, be careful */
950
129
                    if (iter == &(table->table[i])) {
951
85
                        if (table->table[i].valid == 0)
952
65
                            iter = NULL;
953
85
                        if (table->table[i].next != next)
954
20
          iter = &(table->table[i]);
955
85
                    } else
956
44
            iter = next;
957
129
                } else
958
2.38k
        iter = next;
959
2.51k
      }
960
1.74k
  }
961
463
    }
962
463
}
963
964
/**
965
 * xmlHashScan3:
966
 * @table: the hash table
967
 * @name: the name of the userdata or NULL
968
 * @name2: a second name of the userdata or NULL
969
 * @name3: a third name of the userdata or NULL
970
 * @f:  the scanner function for items in the hash
971
 * @data:  extra data passed to f
972
 *
973
 * Scan the hash @table and applied @f to each value matching
974
 * (@name, @name2, @name3) tuple. If one of the names is null,
975
 * the comparison is considered to match.
976
 */
977
void
978
xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
979
       const xmlChar *name2, const xmlChar *name3,
980
0
       xmlHashScanner f, void *data) {
981
0
    stubData stubdata;
982
0
    stubdata.data = data;
983
0
    stubdata.hashscanner = f;
984
0
    xmlHashScanFull3(table, name, name2, name3, stubHashScannerFull,
985
0
                     &stubdata);
986
0
}
987
988
/**
989
 * xmlHashScanFull3:
990
 * @table: the hash table
991
 * @name: the name of the userdata or NULL
992
 * @name2: a second name of the userdata or NULL
993
 * @name3: a third name of the userdata or NULL
994
 * @f:  the scanner function for items in the hash
995
 * @data:  extra data passed to f
996
 *
997
 * Scan the hash @table and applied @f to each value matching
998
 * (@name, @name2, @name3) tuple. If one of the names is null,
999
 * the comparison is considered to match.
1000
 */
1001
void
1002
xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
1003
     const xmlChar *name2, const xmlChar *name3,
1004
0
     xmlHashScannerFull f, void *data) {
1005
0
    int i;
1006
0
    xmlHashEntryPtr iter;
1007
0
    xmlHashEntryPtr next;
1008
1009
0
    if (table == NULL)
1010
0
  return;
1011
0
    if (f == NULL)
1012
0
  return;
1013
1014
0
    if (table->table) {
1015
0
  for(i = 0; i < table->size; i++) {
1016
0
      if (table->table[i].valid == 0)
1017
0
    continue;
1018
0
      iter = &(table->table[i]);
1019
0
      while (iter) {
1020
0
    next = iter->next;
1021
0
    if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
1022
0
        ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
1023
0
        ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
1024
0
        (iter->payload != NULL)) {
1025
0
        f(iter->payload, data, iter->name,
1026
0
          iter->name2, iter->name3);
1027
0
    }
1028
0
    iter = next;
1029
0
      }
1030
0
  }
1031
0
    }
1032
0
}
1033
1034
/**
1035
 * xmlHashCopy:
1036
 * @table: the hash table
1037
 * @f:  the copier function for items in the hash
1038
 *
1039
 * Scan the hash @table and applied @f to each value.
1040
 *
1041
 * Returns the new table or NULL in case of error.
1042
 */
1043
xmlHashTablePtr
1044
0
xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
1045
0
    int i;
1046
0
    xmlHashEntryPtr iter;
1047
0
    xmlHashEntryPtr next;
1048
0
    xmlHashTablePtr ret;
1049
1050
0
    if (table == NULL)
1051
0
  return(NULL);
1052
0
    if (f == NULL)
1053
0
  return(NULL);
1054
1055
0
    ret = xmlHashCreate(table->size);
1056
0
    if (ret == NULL)
1057
0
        return(NULL);
1058
1059
0
    if (table->table) {
1060
0
  for(i = 0; i < table->size; i++) {
1061
0
      if (table->table[i].valid == 0)
1062
0
    continue;
1063
0
      iter = &(table->table[i]);
1064
0
      while (iter) {
1065
0
    next = iter->next;
1066
0
    xmlHashAddEntry3(ret, iter->name, iter->name2,
1067
0
               iter->name3, f(iter->payload, iter->name));
1068
0
    iter = next;
1069
0
      }
1070
0
  }
1071
0
    }
1072
0
    ret->nbElems = table->nbElems;
1073
0
    return(ret);
1074
0
}
1075
1076
/**
1077
 * xmlHashSize:
1078
 * @table: the hash table
1079
 *
1080
 * Query the number of elements installed in the hash @table.
1081
 *
1082
 * Returns the number of elements in the hash table or
1083
 * -1 in case of error
1084
 */
1085
int
1086
463
xmlHashSize(xmlHashTablePtr table) {
1087
463
    if (table == NULL)
1088
0
  return(-1);
1089
463
    return(table->nbElems);
1090
463
}
1091
1092
/**
1093
 * xmlHashRemoveEntry:
1094
 * @table: the hash table
1095
 * @name: the name of the userdata
1096
 * @f: the deallocator function for removed item (if any)
1097
 *
1098
 * Find the userdata specified by the @name and remove
1099
 * it from the hash @table. Existing userdata for this tuple will be removed
1100
 * and freed with @f.
1101
 *
1102
 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1103
 */
1104
int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
1105
0
           xmlHashDeallocator f) {
1106
0
    return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
1107
0
}
1108
1109
/**
1110
 * xmlHashRemoveEntry2:
1111
 * @table: the hash table
1112
 * @name: the name of the userdata
1113
 * @name2: a second name of the userdata
1114
 * @f: the deallocator function for removed item (if any)
1115
 *
1116
 * Find the userdata specified by the (@name, @name2) tuple and remove
1117
 * it from the hash @table. Existing userdata for this tuple will be removed
1118
 * and freed with @f.
1119
 *
1120
 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1121
 */
1122
int
1123
xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
1124
129
      const xmlChar *name2, xmlHashDeallocator f) {
1125
129
    return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
1126
129
}
1127
1128
/**
1129
 * xmlHashRemoveEntry3:
1130
 * @table: the hash table
1131
 * @name: the name of the userdata
1132
 * @name2: a second name of the userdata
1133
 * @name3: a third name of the userdata
1134
 * @f: the deallocator function for removed item (if any)
1135
 *
1136
 * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
1137
 * it from the hash @table. Existing userdata for this tuple will be removed
1138
 * and freed with @f.
1139
 *
1140
 * Returns 0 if the removal succeeded and -1 in case of error or not found.
1141
 */
1142
int
1143
xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
1144
129
    const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
1145
129
    unsigned long key;
1146
129
    xmlHashEntryPtr entry;
1147
129
    xmlHashEntryPtr prev = NULL;
1148
1149
129
    if (table == NULL || name == NULL)
1150
0
        return(-1);
1151
1152
129
    key = xmlHashComputeKey(table, name, name2, name3);
1153
129
    if (table->table[key].valid == 0) {
1154
0
        return(-1);
1155
129
    } else {
1156
225
        for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
1157
225
            if (xmlStrEqual(entry->name, name) &&
1158
225
                    xmlStrEqual(entry->name2, name2) &&
1159
225
                    xmlStrEqual(entry->name3, name3)) {
1160
129
                if ((f != NULL) && (entry->payload != NULL))
1161
0
                    f(entry->payload, entry->name);
1162
129
                entry->payload = NULL;
1163
129
    if (table->dict == NULL) {
1164
0
        if(entry->name)
1165
0
      xmlFree(entry->name);
1166
0
        if(entry->name2)
1167
0
      xmlFree(entry->name2);
1168
0
        if(entry->name3)
1169
0
      xmlFree(entry->name3);
1170
0
    }
1171
129
                if(prev) {
1172
44
                    prev->next = entry->next;
1173
44
        xmlFree(entry);
1174
85
    } else {
1175
85
        if (entry->next == NULL) {
1176
65
      entry->valid = 0;
1177
65
        } else {
1178
20
      entry = entry->next;
1179
20
      memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
1180
20
      xmlFree(entry);
1181
20
        }
1182
85
    }
1183
129
                table->nbElems--;
1184
129
                return(0);
1185
129
            }
1186
96
            prev = entry;
1187
96
        }
1188
0
        return(-1);
1189
129
    }
1190
129
}
1191