Coverage Report

Created: 2024-01-20 12:31

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