Coverage Report

Created: 2023-09-28 22:19

/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
499k
#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
1.69M
            const xmlChar *name2, const xmlChar *name3) {
85
1.69M
    unsigned long value = 0L;
86
1.69M
    unsigned long ch;
87
88
#ifdef HASH_RANDOMIZATION
89
    value = table->random_seed;
90
#endif
91
1.69M
    if (name != NULL) {
92
1.69M
  value += 30 * (*name);
93
12.0M
  while ((ch = *name++) != 0) {
94
10.3M
      value = value ^ ((value << 5) + (value >> 3) + ch);
95
10.3M
  }
96
1.69M
    }
97
1.69M
    value = value ^ ((value << 5) + (value >> 3));
98
1.69M
    if (name2 != NULL) {
99
15.9M
  while ((ch = *name2++) != 0) {
100
15.3M
      value = value ^ ((value << 5) + (value >> 3) + ch);
101
15.3M
  }
102
562k
    }
103
1.69M
    value = value ^ ((value << 5) + (value >> 3));
104
1.69M
    if (name3 != NULL) {
105
0
  while ((ch = *name3++) != 0) {
106
0
      value = value ^ ((value << 5) + (value >> 3) + ch);
107
0
  }
108
0
    }
109
1.69M
    return (value % table->size);
110
1.69M
}
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
43.5k
xmlHashCreate(int size) {
179
43.5k
    xmlHashTablePtr table;
180
181
43.5k
    if (size <= 0)
182
16.6k
        size = 256;
183
184
43.5k
    table = xmlMalloc(sizeof(xmlHashTable));
185
43.5k
    if (table) {
186
43.5k
        table->dict = NULL;
187
43.5k
        table->size = size;
188
43.5k
  table->nbElems = 0;
189
43.5k
        table->table = xmlMalloc(size * sizeof(xmlHashEntry));
190
43.5k
        if (table->table) {
191
43.5k
      memset(table->table, 0, size * sizeof(xmlHashEntry));
192
#ifdef HASH_RANDOMIZATION
193
            table->random_seed = __xmlRandom();
194
#endif
195
43.5k
      return(table);
196
43.5k
        }
197
0
        xmlFree(table);
198
0
    }
199
0
    return(NULL);
200
43.5k
}
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
17.0k
xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
325
17.0k
    int i;
326
17.0k
    xmlHashEntryPtr iter;
327
17.0k
    xmlHashEntryPtr next;
328
17.0k
    int inside_table = 0;
329
17.0k
    int nbElems;
330
331
17.0k
    if (table == NULL)
332
11.1k
  return;
333
5.87k
    if (table->table) {
334
5.87k
  nbElems = table->nbElems;
335
1.42M
  for(i = 0; (i < table->size) && (nbElems > 0); i++) {
336
1.41M
      iter = &(table->table[i]);
337
1.41M
      if (iter->valid == 0)
338
1.26M
    continue;
339
151k
      inside_table = 1;
340
309k
      while (iter) {
341
157k
    next = iter->next;
342
157k
    if ((f != NULL) && (iter->payload != NULL))
343
1.70k
        f(iter->payload, iter->name);
344
157k
    if (table->dict == NULL) {
345
157k
        if (iter->name)
346
157k
      xmlFree(iter->name);
347
157k
        if (iter->name2)
348
5.57k
      xmlFree(iter->name2);
349
157k
        if (iter->name3)
350
0
      xmlFree(iter->name3);
351
157k
    }
352
157k
    iter->payload = NULL;
353
157k
    if (!inside_table)
354
5.90k
        xmlFree(iter);
355
157k
    nbElems--;
356
157k
    inside_table = 0;
357
157k
    iter = next;
358
157k
      }
359
151k
  }
360
5.87k
  xmlFree(table->table);
361
5.87k
    }
362
5.87k
    if (table->dict)
363
0
        xmlDictFree(table->dict);
364
5.87k
    xmlFree(table);
365
5.87k
}
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
1.70k
xmlHashDefaultDeallocator(void *entry, const xmlChar *name ATTRIBUTE_UNUSED) {
376
1.70k
    xmlFree(entry);
377
1.70k
}
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
13.7k
xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
392
13.7k
    return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
393
13.7k
}
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
485k
          const xmlChar *name2, void *userdata) {
410
485k
    return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
411
485k
}
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
40.7k
             void *userdata, xmlHashDeallocator f) {
429
40.7k
    return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
430
40.7k
}
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
318k
       xmlHashDeallocator f) {
450
318k
    return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
451
318k
}
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
567k
xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
464
567k
    return(xmlHashLookup3(table, name, NULL, NULL));
465
567k
}
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
273k
        const xmlChar *name2) {
480
273k
    return(xmlHashLookup3(table, name, name2, NULL));
481
273k
}
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
499k
     void *userdata) {
536
499k
    unsigned long key, len = 0;
537
499k
    xmlHashEntryPtr entry;
538
499k
    xmlHashEntryPtr insert;
539
540
499k
    if ((table == NULL) || (name == NULL))
541
0
  return(-1);
542
543
    /*
544
     * If using a dict internalize if needed
545
     */
546
499k
    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
499k
    key = xmlHashComputeKey(table, name, name2, name3);
568
499k
    if (table->table[key].valid == 0) {
569
433k
  insert = NULL;
570
433k
    } else {
571
65.3k
        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
65.3k
  } else {
585
110k
      for (insert = &(table->table[key]); insert->next != NULL;
586
65.3k
     insert = insert->next) {
587
45.1k
    if ((xmlStrEqual(insert->name, name)) &&
588
45.1k
        (xmlStrEqual(insert->name2, name2)) &&
589
45.1k
        (xmlStrEqual(insert->name3, name3)))
590
0
        return(-1);
591
45.1k
    len++;
592
45.1k
      }
593
65.3k
      if ((xmlStrEqual(insert->name, name)) &&
594
65.3k
    (xmlStrEqual(insert->name2, name2)) &&
595
65.3k
    (xmlStrEqual(insert->name3, name3)))
596
0
    return(-1);
597
65.3k
  }
598
65.3k
    }
599
600
499k
    if (insert == NULL) {
601
433k
  entry = &(table->table[key]);
602
433k
    } else {
603
65.3k
  entry = xmlMalloc(sizeof(xmlHashEntry));
604
65.3k
  if (entry == NULL)
605
0
       return(-1);
606
65.3k
    }
607
608
499k
    if (table->dict != NULL) {
609
0
        entry->name = (xmlChar *) name;
610
0
        entry->name2 = (xmlChar *) name2;
611
0
        entry->name3 = (xmlChar *) name3;
612
499k
    } else {
613
499k
  entry->name = xmlStrdup(name);
614
499k
  entry->name2 = xmlStrdup(name2);
615
499k
  entry->name3 = xmlStrdup(name3);
616
499k
    }
617
499k
    entry->payload = userdata;
618
499k
    entry->next = NULL;
619
499k
    entry->valid = 1;
620
621
622
499k
    if (insert != NULL)
623
65.3k
  insert->next = entry;
624
625
499k
    table->nbElems++;
626
627
499k
    if (len > MAX_HASH_LEN)
628
2
  xmlHashGrow(table, MAX_HASH_LEN * table->size);
629
630
499k
    return(0);
631
499k
}
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
358k
       void *userdata, xmlHashDeallocator f) {
652
358k
    unsigned long key;
653
358k
    xmlHashEntryPtr entry;
654
358k
    xmlHashEntryPtr insert;
655
656
358k
    if ((table == NULL) || name == NULL)
657
0
  return(-1);
658
659
    /*
660
     * If using a dict internalize if needed
661
     */
662
358k
    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
358k
    key = xmlHashComputeKey(table, name, name2, name3);
684
358k
    if (table->table[key].valid == 0) {
685
114k
  insert = NULL;
686
244k
    } else {
687
244k
        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
244k
  } else {
708
1.03M
      for (insert = &(table->table[key]); insert->next != NULL;
709
795k
     insert = insert->next) {
710
795k
    if ((xmlStrEqual(insert->name, name)) &&
711
795k
        (xmlStrEqual(insert->name2, name2)) &&
712
795k
        (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
795k
      }
719
244k
      if ((xmlStrEqual(insert->name, name)) &&
720
244k
    (xmlStrEqual(insert->name2, name2)) &&
721
244k
    (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
244k
  }
728
244k
    }
729
730
358k
    if (insert == NULL) {
731
114k
  entry =  &(table->table[key]);
732
244k
    } else {
733
244k
  entry = xmlMalloc(sizeof(xmlHashEntry));
734
244k
  if (entry == NULL)
735
0
       return(-1);
736
244k
    }
737
738
358k
    if (table->dict != NULL) {
739
0
        entry->name = (xmlChar *) name;
740
0
        entry->name2 = (xmlChar *) name2;
741
0
        entry->name3 = (xmlChar *) name3;
742
358k
    } else {
743
358k
  entry->name = xmlStrdup(name);
744
358k
  entry->name2 = xmlStrdup(name2);
745
358k
  entry->name3 = xmlStrdup(name3);
746
358k
    }
747
358k
    entry->payload = userdata;
748
358k
    entry->next = NULL;
749
358k
    entry->valid = 1;
750
358k
    table->nbElems++;
751
752
753
358k
    if (insert != NULL) {
754
244k
  insert->next = entry;
755
244k
    }
756
358k
    return(0);
757
358k
}
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
840k
         const xmlChar *name2, const xmlChar *name3) {
773
840k
    unsigned long key;
774
840k
    xmlHashEntryPtr entry;
775
776
840k
    if (table == NULL)
777
0
  return(NULL);
778
840k
    if (name == NULL)
779
0
  return(NULL);
780
840k
    key = xmlHashComputeKey(table, name, name2, name3);
781
840k
    if (table->table[key].valid == 0)
782
86.4k
  return(NULL);
783
753k
    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.28M
    for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
792
1.20M
  if ((xmlStrEqual(entry->name, name)) &&
793
1.20M
      (xmlStrEqual(entry->name2, name2)) &&
794
1.20M
      (xmlStrEqual(entry->name3, name3)))
795
675k
      return(entry->payload);
796
1.20M
    }
797
78.8k
    return(NULL);
798
753k
}
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
171k
xmlHashSize(xmlHashTablePtr table) {
1037
171k
    if (table == NULL)
1038
171k
  return(-1);
1039
0
    return(table->nbElems);
1040
171k
}
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