Coverage Report

Created: 2024-01-20 12:30

/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
64.4M
#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
785M
            const xmlChar *name2, const xmlChar *name3) {
85
785M
    unsigned long value = 0L;
86
785M
    unsigned long ch;
87
88
#ifdef HASH_RANDOMIZATION
89
    value = table->random_seed;
90
#endif
91
785M
    if (name != NULL) {
92
785M
  value += 30 * (*name);
93
13.4G
  while ((ch = *name++) != 0) {
94
12.6G
      value = value ^ ((value << 5) + (value >> 3) + ch);
95
12.6G
  }
96
785M
    }
97
785M
    value = value ^ ((value << 5) + (value >> 3));
98
785M
    if (name2 != NULL) {
99
314M
  while ((ch = *name2++) != 0) {
100
261M
      value = value ^ ((value << 5) + (value >> 3) + ch);
101
261M
  }
102
53.3M
    }
103
785M
    value = value ^ ((value << 5) + (value >> 3));
104
785M
    if (name3 != NULL) {
105
452M
  while ((ch = *name3++) != 0) {
106
382M
      value = value ^ ((value << 5) + (value >> 3) + ch);
107
382M
  }
108
69.7M
    }
109
785M
    return (value % table->size);
110
785M
}
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
19.0M
       const xmlChar *prefix3, const xmlChar *name3) {
120
19.0M
    unsigned long value = 0L;
121
19.0M
    unsigned long ch;
122
123
#ifdef HASH_RANDOMIZATION
124
    value = table->random_seed;
125
#endif
126
19.0M
    if (prefix != NULL)
127
293k
  value += 30 * (*prefix);
128
18.7M
    else
129
18.7M
  value += 30 * (*name);
130
131
19.0M
    if (prefix != NULL) {
132
1.24M
  while ((ch = *prefix++) != 0) {
133
953k
      value = value ^ ((value << 5) + (value >> 3) + ch);
134
953k
  }
135
293k
  value = value ^ ((value << 5) + (value >> 3) + ':');
136
293k
    }
137
19.0M
    if (name != NULL) {
138
109M
  while ((ch = *name++) != 0) {
139
90.4M
      value = value ^ ((value << 5) + (value >> 3) + ch);
140
90.4M
  }
141
19.0M
    }
142
19.0M
    value = value ^ ((value << 5) + (value >> 3));
143
19.0M
    if (prefix2 != NULL) {
144
1.31M
  while ((ch = *prefix2++) != 0) {
145
1.00M
      value = value ^ ((value << 5) + (value >> 3) + ch);
146
1.00M
  }
147
305k
  value = value ^ ((value << 5) + (value >> 3) + ':');
148
305k
    }
149
19.0M
    if (name2 != NULL) {
150
76.2M
  while ((ch = *name2++) != 0) {
151
57.2M
      value = value ^ ((value << 5) + (value >> 3) + ch);
152
57.2M
  }
153
19.0M
    }
154
19.0M
    value = value ^ ((value << 5) + (value >> 3));
155
19.0M
    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
19.0M
    if (name3 != NULL) {
162
0
  while ((ch = *name3++) != 0) {
163
0
      value = value ^ ((value << 5) + (value >> 3) + ch);
164
0
  }
165
0
    }
166
19.0M
    return (value % table->size);
167
19.0M
}
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
1.48M
xmlHashCreate(int size) {
179
1.48M
    xmlHashTablePtr table;
180
181
1.48M
    if (size <= 0)
182
985k
        size = 256;
183
184
1.48M
    table = xmlMalloc(sizeof(xmlHashTable));
185
1.48M
    if (table) {
186
1.48M
        table->dict = NULL;
187
1.48M
        table->size = size;
188
1.48M
  table->nbElems = 0;
189
1.48M
        table->table = xmlMalloc(size * sizeof(xmlHashEntry));
190
1.48M
        if (table->table) {
191
1.48M
      memset(table->table, 0, size * sizeof(xmlHashEntry));
192
#ifdef HASH_RANDOMIZATION
193
            table->random_seed = __xmlRandom();
194
#endif
195
1.48M
      return(table);
196
1.48M
        }
197
0
        xmlFree(table);
198
0
    }
199
0
    return(NULL);
200
1.48M
}
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
1.20M
xmlHashCreateDict(int size, xmlDictPtr dict) {
213
1.20M
    xmlHashTablePtr table;
214
215
1.20M
    table = xmlHashCreate(size);
216
1.20M
    if (table != NULL) {
217
1.20M
        table->dict = dict;
218
1.20M
  xmlDictReference(dict);
219
1.20M
    }
220
1.20M
    return(table);
221
1.20M
}
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
71.8k
xmlHashGrow(xmlHashTablePtr table, int size) {
234
71.8k
    unsigned long key;
235
71.8k
    int oldsize, i;
236
71.8k
    xmlHashEntryPtr iter, next;
237
71.8k
    struct _xmlHashEntry *oldtable;
238
#ifdef DEBUG_GROW
239
    unsigned long nbElem = 0;
240
#endif
241
242
71.8k
    if (table == NULL)
243
0
  return(-1);
244
71.8k
    if (size < 8)
245
0
        return(-1);
246
71.8k
    if (size > 8 * 2048)
247
0
  return(-1);
248
249
71.8k
    oldsize = table->size;
250
71.8k
    oldtable = table->table;
251
71.8k
    if (oldtable == NULL)
252
0
        return(-1);
253
254
71.8k
    table->table = xmlMalloc(size * sizeof(xmlHashEntry));
255
71.8k
    if (table->table == NULL) {
256
0
  table->table = oldtable;
257
0
  return(-1);
258
0
    }
259
71.8k
    memset(table->table, 0, size * sizeof(xmlHashEntry));
260
71.8k
    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
1.58M
    for (i = 0; i < oldsize; i++) {
269
1.51M
  if (oldtable[i].valid == 0)
270
15.0k
      continue;
271
1.49M
  key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
272
1.49M
        oldtable[i].name3);
273
1.49M
  memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
274
1.49M
  table->table[key].next = NULL;
275
1.49M
    }
276
277
1.58M
    for (i = 0; i < oldsize; i++) {
278
1.51M
  iter = oldtable[i].next;
279
7.66M
  while (iter) {
280
6.15M
      next = iter->next;
281
282
      /*
283
       * put back the entry in the new table
284
       */
285
286
6.15M
      key = xmlHashComputeKey(table, iter->name, iter->name2,
287
6.15M
                        iter->name3);
288
6.15M
      if (table->table[key].valid == 0) {
289
4.11M
    memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
290
4.11M
    table->table[key].next = NULL;
291
4.11M
    xmlFree(iter);
292
4.11M
      } else {
293
2.04M
    iter->next = table->table[key].next;
294
2.04M
    table->table[key].next = iter;
295
2.04M
      }
296
297
#ifdef DEBUG_GROW
298
      nbElem++;
299
#endif
300
301
6.15M
      iter = next;
302
6.15M
  }
303
1.51M
    }
304
305
71.8k
    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
71.8k
    return(0);
313
71.8k
}
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
1.48M
xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
325
1.48M
    int i;
326
1.48M
    xmlHashEntryPtr iter;
327
1.48M
    xmlHashEntryPtr next;
328
1.48M
    int inside_table = 0;
329
1.48M
    int nbElems;
330
331
1.48M
    if (table == NULL)
332
0
  return;
333
1.48M
    if (table->table) {
334
1.48M
  nbElems = table->nbElems;
335
231M
  for(i = 0; (i < table->size) && (nbElems > 0); i++) {
336
230M
      iter = &(table->table[i]);
337
230M
      if (iter->valid == 0)
338
189M
    continue;
339
41.0M
      inside_table = 1;
340
101M
      while (iter) {
341
60.5M
    next = iter->next;
342
60.5M
    if ((f != NULL) && (iter->payload != NULL))
343
47.0M
        f(iter->payload, iter->name);
344
60.5M
    if (table->dict == NULL) {
345
12.8M
        if (iter->name)
346
12.8M
      xmlFree(iter->name);
347
12.8M
        if (iter->name2)
348
264k
      xmlFree(iter->name2);
349
12.8M
        if (iter->name3)
350
5.83M
      xmlFree(iter->name3);
351
12.8M
    }
352
60.5M
    iter->payload = NULL;
353
60.5M
    if (!inside_table)
354
19.5M
        xmlFree(iter);
355
60.5M
    nbElems--;
356
60.5M
    inside_table = 0;
357
60.5M
    iter = next;
358
60.5M
      }
359
41.0M
  }
360
1.48M
  xmlFree(table->table);
361
1.48M
    }
362
1.48M
    if (table->dict)
363
923k
        xmlDictFree(table->dict);
364
1.48M
    xmlFree(table);
365
1.48M
}
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.12M
xmlHashDefaultDeallocator(void *entry, const xmlChar *name ATTRIBUTE_UNUSED) {
376
1.12M
    xmlFree(entry);
377
1.12M
}
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
16.2M
xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
392
16.2M
    return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
393
16.2M
}
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
26.1M
          const xmlChar *name2, void *userdata) {
410
26.1M
    return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
411
26.1M
}
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
0
             void *userdata, xmlHashDeallocator f) {
429
0
    return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
430
0
}
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
694k
       xmlHashDeallocator f) {
450
694k
    return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
451
694k
}
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
524M
xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
464
524M
    return(xmlHashLookup3(table, name, NULL, NULL));
465
524M
}
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
141M
        const xmlChar *name2) {
480
141M
    return(xmlHashLookup3(table, name, name2, NULL));
481
141M
}
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
19.0M
          const xmlChar *name2) {
515
19.0M
    return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
516
19.0M
}
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
65.4M
     void *userdata) {
536
65.4M
    unsigned long key, len = 0;
537
65.4M
    xmlHashEntryPtr entry;
538
65.4M
    xmlHashEntryPtr insert;
539
540
65.4M
    if ((table == NULL) || (name == NULL))
541
0
  return(-1);
542
543
    /*
544
     * If using a dict internalize if needed
545
     */
546
65.4M
    if (table->dict) {
547
52.4M
        if (!xmlDictOwns(table->dict, name)) {
548
5.98M
      name = xmlDictLookup(table->dict, name, -1);
549
5.98M
      if (name == NULL)
550
0
          return(-1);
551
5.98M
  }
552
52.4M
        if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
553
127k
      name2 = xmlDictLookup(table->dict, name2, -1);
554
127k
      if (name2 == NULL)
555
0
          return(-1);
556
127k
  }
557
52.4M
        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
52.4M
    }
563
564
    /*
565
     * Check for duplicate and insertion location.
566
     */
567
65.4M
    key = xmlHashComputeKey(table, name, name2, name3);
568
65.4M
    if (table->table[key].valid == 0) {
569
37.7M
  insert = NULL;
570
37.7M
    } else {
571
27.6M
        if (table->dict) {
572
50.8M
      for (insert = &(table->table[key]); insert->next != NULL;
573
26.7M
     insert = insert->next) {
574
26.7M
    if ((insert->name == name) &&
575
26.7M
        (insert->name2 == name2) &&
576
26.7M
        (insert->name3 == name3))
577
36.6k
        return(-1);
578
26.6M
    len++;
579
26.6M
      }
580
24.1M
      if ((insert->name == name) &&
581
24.1M
    (insert->name2 == name2) &&
582
24.1M
    (insert->name3 == name3))
583
884k
    return(-1);
584
24.1M
  } else {
585
4.71M
      for (insert = &(table->table[key]); insert->next != NULL;
586
3.46M
     insert = insert->next) {
587
1.27M
    if ((xmlStrEqual(insert->name, name)) &&
588
1.27M
        (xmlStrEqual(insert->name2, name2)) &&
589
1.27M
        (xmlStrEqual(insert->name3, name3)))
590
21.7k
        return(-1);
591
1.25M
    len++;
592
1.25M
      }
593
3.44M
      if ((xmlStrEqual(insert->name, name)) &&
594
3.44M
    (xmlStrEqual(insert->name2, name2)) &&
595
3.44M
    (xmlStrEqual(insert->name3, name3)))
596
151k
    return(-1);
597
3.44M
  }
598
27.6M
    }
599
600
64.3M
    if (insert == NULL) {
601
37.7M
  entry = &(table->table[key]);
602
37.7M
    } else {
603
26.5M
  entry = xmlMalloc(sizeof(xmlHashEntry));
604
26.5M
  if (entry == NULL)
605
0
       return(-1);
606
26.5M
    }
607
608
64.3M
    if (table->dict != NULL) {
609
51.4M
        entry->name = (xmlChar *) name;
610
51.4M
        entry->name2 = (xmlChar *) name2;
611
51.4M
        entry->name3 = (xmlChar *) name3;
612
51.4M
    } else {
613
12.8M
  entry->name = xmlStrdup(name);
614
12.8M
  entry->name2 = xmlStrdup(name2);
615
12.8M
  entry->name3 = xmlStrdup(name3);
616
12.8M
    }
617
64.3M
    entry->payload = userdata;
618
64.3M
    entry->next = NULL;
619
64.3M
    entry->valid = 1;
620
621
622
64.3M
    if (insert != NULL)
623
26.5M
  insert->next = entry;
624
625
64.3M
    table->nbElems++;
626
627
64.3M
    if (len > MAX_HASH_LEN)
628
71.8k
  xmlHashGrow(table, MAX_HASH_LEN * table->size);
629
630
64.3M
    return(0);
631
64.3M
}
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
694k
       void *userdata, xmlHashDeallocator f) {
652
694k
    unsigned long key;
653
694k
    xmlHashEntryPtr entry;
654
694k
    xmlHashEntryPtr insert;
655
656
694k
    if ((table == NULL) || name == NULL)
657
0
  return(-1);
658
659
    /*
660
     * If using a dict internalize if needed
661
     */
662
694k
    if (table->dict) {
663
694k
        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
694k
        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
694k
        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
694k
    }
679
680
    /*
681
     * Check for duplicate and insertion location.
682
     */
683
694k
    key = xmlHashComputeKey(table, name, name2, name3);
684
694k
    if (table->table[key].valid == 0) {
685
458k
  insert = NULL;
686
458k
    } else {
687
236k
        if (table ->dict) {
688
315k
      for (insert = &(table->table[key]); insert->next != NULL;
689
236k
     insert = insert->next) {
690
79.1k
    if ((insert->name == name) &&
691
79.1k
        (insert->name2 == name2) &&
692
79.1k
        (insert->name3 == name3)) {
693
131
        if (f)
694
0
      f(insert->payload, insert->name);
695
131
        insert->payload = userdata;
696
131
        return(0);
697
131
    }
698
79.1k
      }
699
235k
      if ((insert->name == name) &&
700
235k
    (insert->name2 == name2) &&
701
235k
    (insert->name3 == name3)) {
702
1.90k
    if (f)
703
0
        f(insert->payload, insert->name);
704
1.90k
    insert->payload = userdata;
705
1.90k
    return(0);
706
1.90k
      }
707
235k
  } else {
708
0
      for (insert = &(table->table[key]); insert->next != NULL;
709
0
     insert = insert->next) {
710
0
    if ((xmlStrEqual(insert->name, name)) &&
711
0
        (xmlStrEqual(insert->name2, name2)) &&
712
0
        (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
0
      }
719
0
      if ((xmlStrEqual(insert->name, name)) &&
720
0
    (xmlStrEqual(insert->name2, name2)) &&
721
0
    (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
0
  }
728
236k
    }
729
730
692k
    if (insert == NULL) {
731
458k
  entry =  &(table->table[key]);
732
458k
    } else {
733
234k
  entry = xmlMalloc(sizeof(xmlHashEntry));
734
234k
  if (entry == NULL)
735
0
       return(-1);
736
234k
    }
737
738
692k
    if (table->dict != NULL) {
739
692k
        entry->name = (xmlChar *) name;
740
692k
        entry->name2 = (xmlChar *) name2;
741
692k
        entry->name3 = (xmlChar *) name3;
742
692k
    } else {
743
0
  entry->name = xmlStrdup(name);
744
0
  entry->name2 = xmlStrdup(name2);
745
0
  entry->name3 = xmlStrdup(name3);
746
0
    }
747
692k
    entry->payload = userdata;
748
692k
    entry->next = NULL;
749
692k
    entry->valid = 1;
750
692k
    table->nbElems++;
751
752
753
692k
    if (insert != NULL) {
754
234k
  insert->next = entry;
755
234k
    }
756
692k
    return(0);
757
692k
}
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
712M
         const xmlChar *name2, const xmlChar *name3) {
773
712M
    unsigned long key;
774
712M
    xmlHashEntryPtr entry;
775
776
712M
    if (table == NULL)
777
5.40M
  return(NULL);
778
707M
    if (name == NULL)
779
0
  return(NULL);
780
707M
    key = xmlHashComputeKey(table, name, name2, name3);
781
707M
    if (table->table[key].valid == 0)
782
152M
  return(NULL);
783
555M
    if (table->dict) {
784
654M
  for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
785
474M
      if ((entry->name == name) &&
786
474M
    (entry->name2 == name2) &&
787
474M
    (entry->name3 == name3))
788
230M
    return(entry->payload);
789
474M
  }
790
410M
    }
791
416M
    for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
792
377M
  if ((xmlStrEqual(entry->name, name)) &&
793
377M
      (xmlStrEqual(entry->name2, name2)) &&
794
377M
      (xmlStrEqual(entry->name3, name3)))
795
285M
      return(entry->payload);
796
377M
    }
797
38.7M
    return(NULL);
798
324M
}
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
19.0M
    const xmlChar *prefix3, const xmlChar *name3) {
819
19.0M
    unsigned long key;
820
19.0M
    xmlHashEntryPtr entry;
821
822
19.0M
    if (table == NULL)
823
0
  return(NULL);
824
19.0M
    if (name == NULL)
825
0
  return(NULL);
826
19.0M
    key = xmlHashComputeQKey(table, prefix, name, prefix2,
827
19.0M
                             name2, prefix3, name3);
828
19.0M
    if (table->table[key].valid == 0)
829
2.07M
  return(NULL);
830
52.5M
    for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
831
48.3M
  if ((xmlStrQEqual(prefix, name, entry->name)) &&
832
48.3M
      (xmlStrQEqual(prefix2, name2, entry->name2)) &&
833
48.3M
      (xmlStrQEqual(prefix3, name3, entry->name3)))
834
12.7M
      return(entry->payload);
835
48.3M
    }
836
4.15M
    return(NULL);
837
16.9M
}
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
9.64M
         const xmlChar *name3 ATTRIBUTE_UNUSED) {
848
9.64M
    stubData *stubdata = (stubData *) data;
849
9.64M
    stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
850
9.64M
}
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
182k
xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
862
182k
    stubData stubdata;
863
182k
    stubdata.data = data;
864
182k
    stubdata.hashscanner = f;
865
182k
    xmlHashScanFull (table, stubHashScannerFull, &stubdata);
866
182k
}
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
281k
xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
878
281k
    int i, nb;
879
281k
    xmlHashEntryPtr iter;
880
281k
    xmlHashEntryPtr next;
881
882
281k
    if (table == NULL)
883
6.67k
  return;
884
274k
    if (f == NULL)
885
0
  return;
886
887
274k
    if (table->table) {
888
53.8M
  for(i = 0; i < table->size; i++) {
889
53.5M
      if (table->table[i].valid == 0)
890
40.6M
    continue;
891
12.9M
      iter = &(table->table[i]);
892
37.1M
      while (iter) {
893
24.2M
    next = iter->next;
894
24.2M
                nb = table->nbElems;
895
24.2M
    if ((f != NULL) && (iter->payload != NULL))
896
24.2M
        f(iter->payload, data, iter->name,
897
24.2M
          iter->name2, iter->name3);
898
24.2M
                if (nb != table->nbElems) {
899
                    /* table was modified by the callback, be careful */
900
4.46M
                    if (iter == &(table->table[i])) {
901
2.42M
                        if (table->table[i].valid == 0)
902
1.34M
                            iter = NULL;
903
2.42M
                        if (table->table[i].next != next)
904
1.07M
          iter = &(table->table[i]);
905
2.42M
                    } else
906
2.04M
            iter = next;
907
4.46M
                } else
908
19.7M
        iter = next;
909
24.2M
      }
910
12.9M
  }
911
274k
    }
912
274k
}
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
2.71M
       xmlHashScanner f, void *data) {
931
2.71M
    stubData stubdata;
932
2.71M
    stubdata.data = data;
933
2.71M
    stubdata.hashscanner = f;
934
2.71M
    xmlHashScanFull3(table, name, name2, name3, stubHashScannerFull,
935
2.71M
                     &stubdata);
936
2.71M
}
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
2.71M
     xmlHashScannerFull f, void *data) {
955
2.71M
    int i;
956
2.71M
    xmlHashEntryPtr iter;
957
2.71M
    xmlHashEntryPtr next;
958
959
2.71M
    if (table == NULL)
960
2.56M
  return;
961
144k
    if (f == NULL)
962
0
  return;
963
964
144k
    if (table->table) {
965
37.2M
  for(i = 0; i < table->size; i++) {
966
37.0M
      if (table->table[i].valid == 0)
967
19.1M
    continue;
968
17.8M
      iter = &(table->table[i]);
969
58.6M
      while (iter) {
970
40.7M
    next = iter->next;
971
40.7M
    if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
972
40.7M
        ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
973
40.7M
        ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
974
40.7M
        (iter->payload != NULL)) {
975
24
        f(iter->payload, data, iter->name,
976
24
          iter->name2, iter->name3);
977
24
    }
978
40.7M
    iter = next;
979
40.7M
      }
980
17.8M
  }
981
144k
    }
982
144k
}
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
98.2k
xmlHashSize(xmlHashTablePtr table) {
1037
98.2k
    if (table == NULL)
1038
0
  return(-1);
1039
98.2k
    return(table->nbElems);
1040
98.2k
}
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
540
           xmlHashDeallocator f) {
1056
540
    return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
1057
540
}
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
4.47M
      const xmlChar *name2, xmlHashDeallocator f) {
1075
4.47M
    return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
1076
4.47M
}
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
4.47M
    const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
1095
4.47M
    unsigned long key;
1096
4.47M
    xmlHashEntryPtr entry;
1097
4.47M
    xmlHashEntryPtr prev = NULL;
1098
1099
4.47M
    if (table == NULL || name == NULL)
1100
0
        return(-1);
1101
1102
4.47M
    key = xmlHashComputeKey(table, name, name2, name3);
1103
4.47M
    if (table->table[key].valid == 0) {
1104
0
        return(-1);
1105
4.47M
    } else {
1106
7.95M
        for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
1107
7.95M
            if (xmlStrEqual(entry->name, name) &&
1108
7.95M
                    xmlStrEqual(entry->name2, name2) &&
1109
7.95M
                    xmlStrEqual(entry->name3, name3)) {
1110
4.47M
                if ((f != NULL) && (entry->payload != NULL))
1111
540
                    f(entry->payload, entry->name);
1112
4.47M
                entry->payload = NULL;
1113
4.47M
    if (table->dict == NULL) {
1114
660
        if(entry->name)
1115
660
      xmlFree(entry->name);
1116
660
        if(entry->name2)
1117
156
      xmlFree(entry->name2);
1118
660
        if(entry->name3)
1119
0
      xmlFree(entry->name3);
1120
660
    }
1121
4.47M
                if(prev) {
1122
2.04M
                    prev->next = entry->next;
1123
2.04M
        xmlFree(entry);
1124
2.42M
    } else {
1125
2.42M
        if (entry->next == NULL) {
1126
1.34M
      entry->valid = 0;
1127
1.34M
        } else {
1128
1.07M
      entry = entry->next;
1129
1.07M
      memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
1130
1.07M
      xmlFree(entry);
1131
1.07M
        }
1132
2.42M
    }
1133
4.47M
                table->nbElems--;
1134
4.47M
                return(0);
1135
4.47M
            }
1136
3.48M
            prev = entry;
1137
3.48M
        }
1138
0
        return(-1);
1139
4.47M
    }
1140
4.47M
}
1141