1 /*
2 * dict.c: dictionary of reusable strings, just used to avoid allocation
3 * and freeing operations.
4 *
5 * Copyright (C) 2003-2012 Daniel Veillard.
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
12 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
14 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
15 *
16 * Author: daniel@veillard.com
17 */
18
19 #define IN_LIBXML
20 #include "libxml.h"
21
22 #include <limits.h>
23 #ifdef HAVE_STDLIB_H
24 #include <stdlib.h>
25 #endif
26 #ifdef HAVE_TIME_H
27 #include <time.h>
28 #endif
29
30 /*
31 * Following http://www.ocert.org/advisories/ocert-2011-003.html
32 * it seems that having hash randomization might be a good idea
33 * when using XML with untrusted data
34 * Note1: that it works correctly only if compiled with WITH_BIG_KEY
35 * which is the default.
36 * Note2: the fast function used for a small dict won't protect very
37 * well but since the attack is based on growing a very big hash
38 * list we will use the BigKey algo as soon as the hash size grows
39 * over MIN_DICT_SIZE so this actually works
40 */
41 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME) && \
42 !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION)
43 #define DICT_RANDOMIZATION
44 #endif
45
46 #include <string.h>
47 #ifdef HAVE_STDINT_H
48 #include <stdint.h>
49 #else
50 #ifdef HAVE_INTTYPES_H
51 #include <inttypes.h>
52 #elif defined(_WIN32)
53 typedef unsigned __int32 uint32_t;
54 #endif
55 #endif
56 #include <libxml/tree.h>
57 #include <libxml/dict.h>
58 #include <libxml/xmlmemory.h>
59 #include <libxml/xmlerror.h>
60 #include <libxml/globals.h>
61
62 /* #define DEBUG_GROW */
63 /* #define DICT_DEBUG_PATTERNS */
64
65 #define MAX_HASH_LEN 3
66 #define MIN_DICT_SIZE 128
67 #define MAX_DICT_HASH 8 * 2048
68 #define WITH_BIG_KEY
69
70 #ifdef WITH_BIG_KEY
71 #define xmlDictComputeKey(dict, name, len) \
72 (((dict)->size == MIN_DICT_SIZE) ? \
73 xmlDictComputeFastKey(name, len, (dict)->seed) : \
74 xmlDictComputeBigKey(name, len, (dict)->seed))
75
76 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
77 (((prefix) == NULL) ? \
78 (xmlDictComputeKey(dict, name, len)) : \
79 (((dict)->size == MIN_DICT_SIZE) ? \
80 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \
81 xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
82
83 #else /* !WITH_BIG_KEY */
84 #define xmlDictComputeKey(dict, name, len) \
85 xmlDictComputeFastKey(name, len, (dict)->seed)
86 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
87 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
88 #endif /* WITH_BIG_KEY */
89
90 /*
91 * An entry in the dictionary
92 */
93 typedef struct _xmlDictEntry xmlDictEntry;
94 typedef xmlDictEntry *xmlDictEntryPtr;
95 struct _xmlDictEntry {
96 struct _xmlDictEntry *next;
97 const xmlChar *name;
98 unsigned int len;
99 int valid;
100 unsigned long okey;
101 };
102
103 typedef struct _xmlDictStrings xmlDictStrings;
104 typedef xmlDictStrings *xmlDictStringsPtr;
105 struct _xmlDictStrings {
106 xmlDictStringsPtr next;
107 xmlChar *free;
108 xmlChar *end;
109 size_t size;
110 size_t nbStrings;
111 xmlChar array[1];
112 };
113 /*
114 * The entire dictionary
115 */
116 struct _xmlDict {
117 int ref_counter;
118
119 struct _xmlDictEntry *dict;
120 size_t size;
121 unsigned int nbElems;
122 xmlDictStringsPtr strings;
123
124 struct _xmlDict *subdict;
125 /* used for randomization */
126 int seed;
127 /* used to impose a limit on size */
128 size_t limit;
129 };
130
131 /*
132 * A mutex for modifying the reference counter for shared
133 * dictionaries.
134 */
135 static xmlRMutexPtr xmlDictMutex = NULL;
136
137 /*
138 * Whether the dictionary mutex was initialized.
139 */
140 static int xmlDictInitialized = 0;
141
142 #ifdef DICT_RANDOMIZATION
143 #ifdef HAVE_RAND_R
144 /*
145 * Internal data for random function, protected by xmlDictMutex
146 */
147 static unsigned int rand_seed = 0;
148 #endif
149 #endif
150
151 /**
152 * xmlInitializeDict:
153 *
154 * Do the dictionary mutex initialization.
155 * this function is deprecated
156 *
157 * Returns 0 if initialization was already done, and 1 if that
158 * call led to the initialization
159 */
xmlInitializeDict(void)160 int xmlInitializeDict(void) {
161 return(0);
162 }
163
164 /**
165 * __xmlInitializeDict:
166 *
167 * This function is not public
168 * Do the dictionary mutex initialization.
169 * this function is not thread safe, initialization should
170 * normally be done once at setup when called from xmlOnceInit()
171 * we may also land in this code if thread support is not compiled in
172 *
173 * Returns 0 if initialization was already done, and 1 if that
174 * call led to the initialization
175 */
__xmlInitializeDict(void)176 int __xmlInitializeDict(void) {
177 if (xmlDictInitialized)
178 return(1);
179
180 if ((xmlDictMutex = xmlNewRMutex()) == NULL)
181 return(0);
182 xmlRMutexLock(xmlDictMutex);
183
184 #ifdef DICT_RANDOMIZATION
185 #ifdef HAVE_RAND_R
186 rand_seed = time(NULL);
187 rand_r(& rand_seed);
188 #else
189 srand(time(NULL));
190 #endif
191 #endif
192 xmlDictInitialized = 1;
193 xmlRMutexUnlock(xmlDictMutex);
194 return(1);
195 }
196
197 #ifdef DICT_RANDOMIZATION
__xmlRandom(void)198 int __xmlRandom(void) {
199 int ret;
200
201 if (xmlDictInitialized == 0)
202 __xmlInitializeDict();
203
204 xmlRMutexLock(xmlDictMutex);
205 #ifdef HAVE_RAND_R
206 ret = rand_r(& rand_seed);
207 #else
208 ret = rand();
209 #endif
210 xmlRMutexUnlock(xmlDictMutex);
211 return(ret);
212 }
213 #endif
214
215 /**
216 * xmlDictCleanup:
217 *
218 * Free the dictionary mutex. Do not call unless sure the library
219 * is not in use anymore !
220 */
221 void
xmlDictCleanup(void)222 xmlDictCleanup(void) {
223 if (!xmlDictInitialized)
224 return;
225
226 xmlFreeRMutex(xmlDictMutex);
227
228 xmlDictInitialized = 0;
229 }
230
231 /*
232 * xmlDictAddString:
233 * @dict: the dictionary
234 * @name: the name of the userdata
235 * @len: the length of the name
236 *
237 * Add the string to the array[s]
238 *
239 * Returns the pointer of the local string, or NULL in case of error.
240 */
241 static const xmlChar *
xmlDictAddString(xmlDictPtr dict,const xmlChar * name,unsigned int namelen)242 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
243 xmlDictStringsPtr pool;
244 const xmlChar *ret;
245 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
246 size_t limit = 0;
247
248 #ifdef DICT_DEBUG_PATTERNS
249 fprintf(stderr, "-");
250 #endif
251 pool = dict->strings;
252 while (pool != NULL) {
253 if ((size_t)(pool->end - pool->free) > namelen)
254 goto found_pool;
255 if (pool->size > size) size = pool->size;
256 limit += pool->size;
257 pool = pool->next;
258 }
259 /*
260 * Not found, need to allocate
261 */
262 if (pool == NULL) {
263 if ((dict->limit > 0) && (limit > dict->limit)) {
264 return(NULL);
265 }
266
267 if (size == 0) size = 1000;
268 else size *= 4; /* exponential growth */
269 if (size < 4 * namelen)
270 size = 4 * namelen; /* just in case ! */
271 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
272 if (pool == NULL)
273 return(NULL);
274 pool->size = size;
275 pool->nbStrings = 0;
276 pool->free = &pool->array[0];
277 pool->end = &pool->array[size];
278 pool->next = dict->strings;
279 dict->strings = pool;
280 #ifdef DICT_DEBUG_PATTERNS
281 fprintf(stderr, "+");
282 #endif
283 }
284 found_pool:
285 ret = pool->free;
286 memcpy(pool->free, name, namelen);
287 pool->free += namelen;
288 *(pool->free++) = 0;
289 pool->nbStrings++;
290 return(ret);
291 }
292
293 /*
294 * xmlDictAddQString:
295 * @dict: the dictionary
296 * @prefix: the prefix of the userdata
297 * @plen: the prefix length
298 * @name: the name of the userdata
299 * @len: the length of the name
300 *
301 * Add the QName to the array[s]
302 *
303 * Returns the pointer of the local string, or NULL in case of error.
304 */
305 static const xmlChar *
xmlDictAddQString(xmlDictPtr dict,const xmlChar * prefix,unsigned int plen,const xmlChar * name,unsigned int namelen)306 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
307 const xmlChar *name, unsigned int namelen)
308 {
309 xmlDictStringsPtr pool;
310 const xmlChar *ret;
311 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
312 size_t limit = 0;
313
314 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
315
316 #ifdef DICT_DEBUG_PATTERNS
317 fprintf(stderr, "=");
318 #endif
319 pool = dict->strings;
320 while (pool != NULL) {
321 if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
322 goto found_pool;
323 if (pool->size > size) size = pool->size;
324 limit += pool->size;
325 pool = pool->next;
326 }
327 /*
328 * Not found, need to allocate
329 */
330 if (pool == NULL) {
331 if ((dict->limit > 0) && (limit > dict->limit)) {
332 return(NULL);
333 }
334
335 if (size == 0) size = 1000;
336 else size *= 4; /* exponential growth */
337 if (size < 4 * (namelen + plen + 1))
338 size = 4 * (namelen + plen + 1); /* just in case ! */
339 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
340 if (pool == NULL)
341 return(NULL);
342 pool->size = size;
343 pool->nbStrings = 0;
344 pool->free = &pool->array[0];
345 pool->end = &pool->array[size];
346 pool->next = dict->strings;
347 dict->strings = pool;
348 #ifdef DICT_DEBUG_PATTERNS
349 fprintf(stderr, "+");
350 #endif
351 }
352 found_pool:
353 ret = pool->free;
354 memcpy(pool->free, prefix, plen);
355 pool->free += plen;
356 *(pool->free++) = ':';
357 memcpy(pool->free, name, namelen);
358 pool->free += namelen;
359 *(pool->free++) = 0;
360 pool->nbStrings++;
361 return(ret);
362 }
363
364 #ifdef WITH_BIG_KEY
365 /*
366 * xmlDictComputeBigKey:
367 *
368 * Calculate a hash key using a good hash function that works well for
369 * larger hash table sizes.
370 *
371 * Hash function by "One-at-a-Time Hash" see
372 * http://burtleburtle.net/bob/hash/doobs.html
373 */
374
375 #ifdef __clang__
376 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
377 #endif
378 static uint32_t
xmlDictComputeBigKey(const xmlChar * data,int namelen,int seed)379 xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
380 uint32_t hash;
381 int i;
382
383 if (namelen <= 0 || data == NULL) return(0);
384
385 hash = seed;
386
387 for (i = 0;i < namelen; i++) {
388 hash += data[i];
389 hash += (hash << 10);
390 hash ^= (hash >> 6);
391 }
392 hash += (hash << 3);
393 hash ^= (hash >> 11);
394 hash += (hash << 15);
395
396 return hash;
397 }
398
399 /*
400 * xmlDictComputeBigQKey:
401 *
402 * Calculate a hash key for two strings using a good hash function
403 * that works well for larger hash table sizes.
404 *
405 * Hash function by "One-at-a-Time Hash" see
406 * http://burtleburtle.net/bob/hash/doobs.html
407 *
408 * Neither of the two strings must be NULL.
409 */
410 #ifdef __clang__
411 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
412 #endif
413 static unsigned long
xmlDictComputeBigQKey(const xmlChar * prefix,int plen,const xmlChar * name,int len,int seed)414 xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
415 const xmlChar *name, int len, int seed)
416 {
417 uint32_t hash;
418 int i;
419
420 hash = seed;
421
422 for (i = 0;i < plen; i++) {
423 hash += prefix[i];
424 hash += (hash << 10);
425 hash ^= (hash >> 6);
426 }
427 hash += ':';
428 hash += (hash << 10);
429 hash ^= (hash >> 6);
430
431 for (i = 0;i < len; i++) {
432 hash += name[i];
433 hash += (hash << 10);
434 hash ^= (hash >> 6);
435 }
436 hash += (hash << 3);
437 hash ^= (hash >> 11);
438 hash += (hash << 15);
439
440 return hash;
441 }
442 #endif /* WITH_BIG_KEY */
443
444 /*
445 * xmlDictComputeFastKey:
446 *
447 * Calculate a hash key using a fast hash function that works well
448 * for low hash table fill.
449 */
450 static unsigned long
xmlDictComputeFastKey(const xmlChar * name,int namelen,int seed)451 xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
452 unsigned long value = seed;
453
454 if ((name == NULL) || (namelen <= 0))
455 return(value);
456 value += *name;
457 value <<= 5;
458 if (namelen > 10) {
459 value += name[namelen - 1];
460 namelen = 10;
461 }
462 switch (namelen) {
463 case 10: value += name[9];
464 /* Falls through. */
465 case 9: value += name[8];
466 /* Falls through. */
467 case 8: value += name[7];
468 /* Falls through. */
469 case 7: value += name[6];
470 /* Falls through. */
471 case 6: value += name[5];
472 /* Falls through. */
473 case 5: value += name[4];
474 /* Falls through. */
475 case 4: value += name[3];
476 /* Falls through. */
477 case 3: value += name[2];
478 /* Falls through. */
479 case 2: value += name[1];
480 /* Falls through. */
481 default: break;
482 }
483 return(value);
484 }
485
486 /*
487 * xmlDictComputeFastQKey:
488 *
489 * Calculate a hash key for two strings using a fast hash function
490 * that works well for low hash table fill.
491 *
492 * Neither of the two strings must be NULL.
493 */
494 static unsigned long
xmlDictComputeFastQKey(const xmlChar * prefix,int plen,const xmlChar * name,int len,int seed)495 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
496 const xmlChar *name, int len, int seed)
497 {
498 unsigned long value = (unsigned long) seed;
499
500 if (plen == 0)
501 value += 30 * (unsigned long) ':';
502 else
503 value += 30 * (*prefix);
504
505 if (len > 10) {
506 int offset = len - (plen + 1 + 1);
507 if (offset < 0)
508 offset = len - (10 + 1);
509 value += name[offset];
510 len = 10;
511 if (plen > 10)
512 plen = 10;
513 }
514 switch (plen) {
515 case 10: value += prefix[9];
516 /* Falls through. */
517 case 9: value += prefix[8];
518 /* Falls through. */
519 case 8: value += prefix[7];
520 /* Falls through. */
521 case 7: value += prefix[6];
522 /* Falls through. */
523 case 6: value += prefix[5];
524 /* Falls through. */
525 case 5: value += prefix[4];
526 /* Falls through. */
527 case 4: value += prefix[3];
528 /* Falls through. */
529 case 3: value += prefix[2];
530 /* Falls through. */
531 case 2: value += prefix[1];
532 /* Falls through. */
533 case 1: value += prefix[0];
534 /* Falls through. */
535 default: break;
536 }
537 len -= plen;
538 if (len > 0) {
539 value += (unsigned long) ':';
540 len--;
541 }
542 switch (len) {
543 case 10: value += name[9];
544 /* Falls through. */
545 case 9: value += name[8];
546 /* Falls through. */
547 case 8: value += name[7];
548 /* Falls through. */
549 case 7: value += name[6];
550 /* Falls through. */
551 case 6: value += name[5];
552 /* Falls through. */
553 case 5: value += name[4];
554 /* Falls through. */
555 case 4: value += name[3];
556 /* Falls through. */
557 case 3: value += name[2];
558 /* Falls through. */
559 case 2: value += name[1];
560 /* Falls through. */
561 case 1: value += name[0];
562 /* Falls through. */
563 default: break;
564 }
565 return(value);
566 }
567
568 /**
569 * xmlDictCreate:
570 *
571 * Create a new dictionary
572 *
573 * Returns the newly created dictionary, or NULL if an error occurred.
574 */
575 xmlDictPtr
xmlDictCreate(void)576 xmlDictCreate(void) {
577 xmlDictPtr dict;
578
579 if (!xmlDictInitialized)
580 if (!__xmlInitializeDict())
581 return(NULL);
582
583 #ifdef DICT_DEBUG_PATTERNS
584 fprintf(stderr, "C");
585 #endif
586
587 dict = xmlMalloc(sizeof(xmlDict));
588 if (dict) {
589 dict->ref_counter = 1;
590 dict->limit = 0;
591
592 dict->size = MIN_DICT_SIZE;
593 dict->nbElems = 0;
594 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
595 dict->strings = NULL;
596 dict->subdict = NULL;
597 if (dict->dict) {
598 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
599 #ifdef DICT_RANDOMIZATION
600 dict->seed = __xmlRandom();
601 #else
602 dict->seed = 0;
603 #endif
604 return(dict);
605 }
606 xmlFree(dict);
607 }
608 return(NULL);
609 }
610
611 /**
612 * xmlDictCreateSub:
613 * @sub: an existing dictionary
614 *
615 * Create a new dictionary, inheriting strings from the read-only
616 * dictionary @sub. On lookup, strings are first searched in the
617 * new dictionary, then in @sub, and if not found are created in the
618 * new dictionary.
619 *
620 * Returns the newly created dictionary, or NULL if an error occurred.
621 */
622 xmlDictPtr
xmlDictCreateSub(xmlDictPtr sub)623 xmlDictCreateSub(xmlDictPtr sub) {
624 xmlDictPtr dict = xmlDictCreate();
625
626 if ((dict != NULL) && (sub != NULL)) {
627 #ifdef DICT_DEBUG_PATTERNS
628 fprintf(stderr, "R");
629 #endif
630 dict->seed = sub->seed;
631 dict->subdict = sub;
632 xmlDictReference(dict->subdict);
633 }
634 return(dict);
635 }
636
637 /**
638 * xmlDictReference:
639 * @dict: the dictionary
640 *
641 * Increment the reference counter of a dictionary
642 *
643 * Returns 0 in case of success and -1 in case of error
644 */
645 int
xmlDictReference(xmlDictPtr dict)646 xmlDictReference(xmlDictPtr dict) {
647 if (!xmlDictInitialized)
648 if (!__xmlInitializeDict())
649 return(-1);
650
651 if (dict == NULL) return -1;
652 xmlRMutexLock(xmlDictMutex);
653 dict->ref_counter++;
654 xmlRMutexUnlock(xmlDictMutex);
655 return(0);
656 }
657
658 /**
659 * xmlDictGrow:
660 * @dict: the dictionary
661 * @size: the new size of the dictionary
662 *
663 * resize the dictionary
664 *
665 * Returns 0 in case of success, -1 in case of failure
666 */
667 static int
xmlDictGrow(xmlDictPtr dict,size_t size)668 xmlDictGrow(xmlDictPtr dict, size_t size) {
669 unsigned long key, okey;
670 size_t oldsize, i;
671 xmlDictEntryPtr iter, next;
672 struct _xmlDictEntry *olddict;
673 #ifdef DEBUG_GROW
674 unsigned long nbElem = 0;
675 #endif
676 int ret = 0;
677 int keep_keys = 1;
678
679 if (dict == NULL)
680 return(-1);
681 if (size < 8)
682 return(-1);
683 if (size > 8 * 2048)
684 return(-1);
685
686 #ifdef DICT_DEBUG_PATTERNS
687 fprintf(stderr, "*");
688 #endif
689
690 oldsize = dict->size;
691 olddict = dict->dict;
692 if (olddict == NULL)
693 return(-1);
694 if (oldsize == MIN_DICT_SIZE)
695 keep_keys = 0;
696
697 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
698 if (dict->dict == NULL) {
699 dict->dict = olddict;
700 return(-1);
701 }
702 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
703 dict->size = size;
704
705 /* If the two loops are merged, there would be situations where
706 a new entry needs to allocated and data copied into it from
707 the main dict. It is nicer to run through the array twice, first
708 copying all the elements in the main array (less probability of
709 allocate) and then the rest, so we only free in the second loop.
710 */
711 for (i = 0; i < oldsize; i++) {
712 if (olddict[i].valid == 0)
713 continue;
714
715 if (keep_keys)
716 okey = olddict[i].okey;
717 else
718 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
719 key = okey % dict->size;
720
721 if (dict->dict[key].valid == 0) {
722 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
723 dict->dict[key].next = NULL;
724 dict->dict[key].okey = okey;
725 } else {
726 xmlDictEntryPtr entry;
727
728 entry = xmlMalloc(sizeof(xmlDictEntry));
729 if (entry != NULL) {
730 entry->name = olddict[i].name;
731 entry->len = olddict[i].len;
732 entry->okey = okey;
733 entry->next = dict->dict[key].next;
734 entry->valid = 1;
735 dict->dict[key].next = entry;
736 } else {
737 /*
738 * we don't have much ways to alert from here
739 * result is losing an entry and unicity guarantee
740 */
741 ret = -1;
742 }
743 }
744 #ifdef DEBUG_GROW
745 nbElem++;
746 #endif
747 }
748
749 for (i = 0; i < oldsize; i++) {
750 iter = olddict[i].next;
751 while (iter) {
752 next = iter->next;
753
754 /*
755 * put back the entry in the new dict
756 */
757
758 if (keep_keys)
759 okey = iter->okey;
760 else
761 okey = xmlDictComputeKey(dict, iter->name, iter->len);
762 key = okey % dict->size;
763 if (dict->dict[key].valid == 0) {
764 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
765 dict->dict[key].next = NULL;
766 dict->dict[key].valid = 1;
767 dict->dict[key].okey = okey;
768 xmlFree(iter);
769 } else {
770 iter->next = dict->dict[key].next;
771 iter->okey = okey;
772 dict->dict[key].next = iter;
773 }
774
775 #ifdef DEBUG_GROW
776 nbElem++;
777 #endif
778
779 iter = next;
780 }
781 }
782
783 xmlFree(olddict);
784
785 #ifdef DEBUG_GROW
786 xmlGenericError(xmlGenericErrorContext,
787 "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
788 #endif
789
790 return(ret);
791 }
792
793 /**
794 * xmlDictFree:
795 * @dict: the dictionary
796 *
797 * Free the hash @dict and its contents. The userdata is
798 * deallocated with @f if provided.
799 */
800 void
xmlDictFree(xmlDictPtr dict)801 xmlDictFree(xmlDictPtr dict) {
802 size_t i;
803 xmlDictEntryPtr iter;
804 xmlDictEntryPtr next;
805 int inside_dict = 0;
806 xmlDictStringsPtr pool, nextp;
807
808 if (dict == NULL)
809 return;
810
811 if (!xmlDictInitialized)
812 if (!__xmlInitializeDict())
813 return;
814
815 /* decrement the counter, it may be shared by a parser and docs */
816 xmlRMutexLock(xmlDictMutex);
817 dict->ref_counter--;
818 if (dict->ref_counter > 0) {
819 xmlRMutexUnlock(xmlDictMutex);
820 return;
821 }
822
823 xmlRMutexUnlock(xmlDictMutex);
824
825 if (dict->subdict != NULL) {
826 xmlDictFree(dict->subdict);
827 }
828
829 if (dict->dict) {
830 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
831 iter = &(dict->dict[i]);
832 if (iter->valid == 0)
833 continue;
834 inside_dict = 1;
835 while (iter) {
836 next = iter->next;
837 if (!inside_dict)
838 xmlFree(iter);
839 dict->nbElems--;
840 inside_dict = 0;
841 iter = next;
842 }
843 }
844 xmlFree(dict->dict);
845 }
846 pool = dict->strings;
847 while (pool != NULL) {
848 nextp = pool->next;
849 xmlFree(pool);
850 pool = nextp;
851 }
852 xmlFree(dict);
853 }
854
855 /**
856 * xmlDictLookup:
857 * @dict: the dictionary
858 * @name: the name of the userdata
859 * @len: the length of the name, if -1 it is recomputed
860 *
861 * Add the @name to the dictionary @dict if not present.
862 *
863 * Returns the internal copy of the name or NULL in case of internal error
864 */
865 const xmlChar *
xmlDictLookup(xmlDictPtr dict,const xmlChar * name,int len)866 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
867 unsigned long key, okey, nbi = 0;
868 xmlDictEntryPtr entry;
869 xmlDictEntryPtr insert;
870 const xmlChar *ret;
871 unsigned int l;
872
873 if ((dict == NULL) || (name == NULL))
874 return(NULL);
875
876 if (len < 0)
877 l = strlen((const char *) name);
878 else
879 l = len;
880
881 if (((dict->limit > 0) && (l >= dict->limit)) ||
882 (l > INT_MAX / 2))
883 return(NULL);
884
885 /*
886 * Check for duplicate and insertion location.
887 */
888 okey = xmlDictComputeKey(dict, name, l);
889 key = okey % dict->size;
890 if (dict->dict[key].valid == 0) {
891 insert = NULL;
892 } else {
893 for (insert = &(dict->dict[key]); insert->next != NULL;
894 insert = insert->next) {
895 #ifdef __GNUC__
896 if ((insert->okey == okey) && (insert->len == l)) {
897 if (!memcmp(insert->name, name, l))
898 return(insert->name);
899 }
900 #else
901 if ((insert->okey == okey) && (insert->len == l) &&
902 (!xmlStrncmp(insert->name, name, l)))
903 return(insert->name);
904 #endif
905 nbi++;
906 }
907 #ifdef __GNUC__
908 if ((insert->okey == okey) && (insert->len == l)) {
909 if (!memcmp(insert->name, name, l))
910 return(insert->name);
911 }
912 #else
913 if ((insert->okey == okey) && (insert->len == l) &&
914 (!xmlStrncmp(insert->name, name, l)))
915 return(insert->name);
916 #endif
917 }
918
919 if (dict->subdict) {
920 unsigned long skey;
921
922 /* we cannot always reuse the same okey for the subdict */
923 if (((dict->size == MIN_DICT_SIZE) &&
924 (dict->subdict->size != MIN_DICT_SIZE)) ||
925 ((dict->size != MIN_DICT_SIZE) &&
926 (dict->subdict->size == MIN_DICT_SIZE)))
927 skey = xmlDictComputeKey(dict->subdict, name, l);
928 else
929 skey = okey;
930
931 key = skey % dict->subdict->size;
932 if (dict->subdict->dict[key].valid != 0) {
933 xmlDictEntryPtr tmp;
934
935 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
936 tmp = tmp->next) {
937 #ifdef __GNUC__
938 if ((tmp->okey == skey) && (tmp->len == l)) {
939 if (!memcmp(tmp->name, name, l))
940 return(tmp->name);
941 }
942 #else
943 if ((tmp->okey == skey) && (tmp->len == l) &&
944 (!xmlStrncmp(tmp->name, name, l)))
945 return(tmp->name);
946 #endif
947 nbi++;
948 }
949 #ifdef __GNUC__
950 if ((tmp->okey == skey) && (tmp->len == l)) {
951 if (!memcmp(tmp->name, name, l))
952 return(tmp->name);
953 }
954 #else
955 if ((tmp->okey == skey) && (tmp->len == l) &&
956 (!xmlStrncmp(tmp->name, name, l)))
957 return(tmp->name);
958 #endif
959 }
960 key = okey % dict->size;
961 }
962
963 ret = xmlDictAddString(dict, name, l);
964 if (ret == NULL)
965 return(NULL);
966 if (insert == NULL) {
967 entry = &(dict->dict[key]);
968 } else {
969 entry = xmlMalloc(sizeof(xmlDictEntry));
970 if (entry == NULL)
971 return(NULL);
972 }
973 entry->name = ret;
974 entry->len = l;
975 entry->next = NULL;
976 entry->valid = 1;
977 entry->okey = okey;
978
979
980 if (insert != NULL)
981 insert->next = entry;
982
983 dict->nbElems++;
984
985 if ((nbi > MAX_HASH_LEN) &&
986 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
987 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
988 return(NULL);
989 }
990 /* Note that entry may have been freed at this point by xmlDictGrow */
991
992 return(ret);
993 }
994
995 /**
996 * xmlDictExists:
997 * @dict: the dictionary
998 * @name: the name of the userdata
999 * @len: the length of the name, if -1 it is recomputed
1000 *
1001 * Check if the @name exists in the dictionary @dict.
1002 *
1003 * Returns the internal copy of the name or NULL if not found.
1004 */
1005 const xmlChar *
xmlDictExists(xmlDictPtr dict,const xmlChar * name,int len)1006 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
1007 unsigned long key, okey, nbi = 0;
1008 xmlDictEntryPtr insert;
1009 unsigned int l;
1010
1011 if ((dict == NULL) || (name == NULL))
1012 return(NULL);
1013
1014 if (len < 0)
1015 l = strlen((const char *) name);
1016 else
1017 l = len;
1018 if (((dict->limit > 0) && (l >= dict->limit)) ||
1019 (l > INT_MAX / 2))
1020 return(NULL);
1021
1022 /*
1023 * Check for duplicate and insertion location.
1024 */
1025 okey = xmlDictComputeKey(dict, name, l);
1026 key = okey % dict->size;
1027 if (dict->dict[key].valid == 0) {
1028 insert = NULL;
1029 } else {
1030 for (insert = &(dict->dict[key]); insert->next != NULL;
1031 insert = insert->next) {
1032 #ifdef __GNUC__
1033 if ((insert->okey == okey) && (insert->len == l)) {
1034 if (!memcmp(insert->name, name, l))
1035 return(insert->name);
1036 }
1037 #else
1038 if ((insert->okey == okey) && (insert->len == l) &&
1039 (!xmlStrncmp(insert->name, name, l)))
1040 return(insert->name);
1041 #endif
1042 nbi++;
1043 }
1044 #ifdef __GNUC__
1045 if ((insert->okey == okey) && (insert->len == l)) {
1046 if (!memcmp(insert->name, name, l))
1047 return(insert->name);
1048 }
1049 #else
1050 if ((insert->okey == okey) && (insert->len == l) &&
1051 (!xmlStrncmp(insert->name, name, l)))
1052 return(insert->name);
1053 #endif
1054 }
1055
1056 if (dict->subdict) {
1057 unsigned long skey;
1058
1059 /* we cannot always reuse the same okey for the subdict */
1060 if (((dict->size == MIN_DICT_SIZE) &&
1061 (dict->subdict->size != MIN_DICT_SIZE)) ||
1062 ((dict->size != MIN_DICT_SIZE) &&
1063 (dict->subdict->size == MIN_DICT_SIZE)))
1064 skey = xmlDictComputeKey(dict->subdict, name, l);
1065 else
1066 skey = okey;
1067
1068 key = skey % dict->subdict->size;
1069 if (dict->subdict->dict[key].valid != 0) {
1070 xmlDictEntryPtr tmp;
1071
1072 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1073 tmp = tmp->next) {
1074 #ifdef __GNUC__
1075 if ((tmp->okey == skey) && (tmp->len == l)) {
1076 if (!memcmp(tmp->name, name, l))
1077 return(tmp->name);
1078 }
1079 #else
1080 if ((tmp->okey == skey) && (tmp->len == l) &&
1081 (!xmlStrncmp(tmp->name, name, l)))
1082 return(tmp->name);
1083 #endif
1084 nbi++;
1085 }
1086 #ifdef __GNUC__
1087 if ((tmp->okey == skey) && (tmp->len == l)) {
1088 if (!memcmp(tmp->name, name, l))
1089 return(tmp->name);
1090 }
1091 #else
1092 if ((tmp->okey == skey) && (tmp->len == l) &&
1093 (!xmlStrncmp(tmp->name, name, l)))
1094 return(tmp->name);
1095 #endif
1096 }
1097 }
1098
1099 /* not found */
1100 return(NULL);
1101 }
1102
1103 /**
1104 * xmlDictQLookup:
1105 * @dict: the dictionary
1106 * @prefix: the prefix
1107 * @name: the name
1108 *
1109 * Add the QName @prefix:@name to the hash @dict if not present.
1110 *
1111 * Returns the internal copy of the QName or NULL in case of internal error
1112 */
1113 const xmlChar *
xmlDictQLookup(xmlDictPtr dict,const xmlChar * prefix,const xmlChar * name)1114 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1115 unsigned long okey, key, nbi = 0;
1116 xmlDictEntryPtr entry;
1117 xmlDictEntryPtr insert;
1118 const xmlChar *ret;
1119 unsigned int len, plen, l;
1120
1121 if ((dict == NULL) || (name == NULL))
1122 return(NULL);
1123 if (prefix == NULL)
1124 return(xmlDictLookup(dict, name, -1));
1125
1126 l = len = strlen((const char *) name);
1127 plen = strlen((const char *) prefix);
1128 len += 1 + plen;
1129
1130 /*
1131 * Check for duplicate and insertion location.
1132 */
1133 okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1134 key = okey % dict->size;
1135 if (dict->dict[key].valid == 0) {
1136 insert = NULL;
1137 } else {
1138 for (insert = &(dict->dict[key]); insert->next != NULL;
1139 insert = insert->next) {
1140 if ((insert->okey == okey) && (insert->len == len) &&
1141 (xmlStrQEqual(prefix, name, insert->name)))
1142 return(insert->name);
1143 nbi++;
1144 }
1145 if ((insert->okey == okey) && (insert->len == len) &&
1146 (xmlStrQEqual(prefix, name, insert->name)))
1147 return(insert->name);
1148 }
1149
1150 if (dict->subdict) {
1151 unsigned long skey;
1152
1153 /* we cannot always reuse the same okey for the subdict */
1154 if (((dict->size == MIN_DICT_SIZE) &&
1155 (dict->subdict->size != MIN_DICT_SIZE)) ||
1156 ((dict->size != MIN_DICT_SIZE) &&
1157 (dict->subdict->size == MIN_DICT_SIZE)))
1158 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1159 else
1160 skey = okey;
1161
1162 key = skey % dict->subdict->size;
1163 if (dict->subdict->dict[key].valid != 0) {
1164 xmlDictEntryPtr tmp;
1165 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1166 tmp = tmp->next) {
1167 if ((tmp->okey == skey) && (tmp->len == len) &&
1168 (xmlStrQEqual(prefix, name, tmp->name)))
1169 return(tmp->name);
1170 nbi++;
1171 }
1172 if ((tmp->okey == skey) && (tmp->len == len) &&
1173 (xmlStrQEqual(prefix, name, tmp->name)))
1174 return(tmp->name);
1175 }
1176 key = okey % dict->size;
1177 }
1178
1179 ret = xmlDictAddQString(dict, prefix, plen, name, l);
1180 if (ret == NULL)
1181 return(NULL);
1182 if (insert == NULL) {
1183 entry = &(dict->dict[key]);
1184 } else {
1185 entry = xmlMalloc(sizeof(xmlDictEntry));
1186 if (entry == NULL)
1187 return(NULL);
1188 }
1189 entry->name = ret;
1190 entry->len = len;
1191 entry->next = NULL;
1192 entry->valid = 1;
1193 entry->okey = okey;
1194
1195 if (insert != NULL)
1196 insert->next = entry;
1197
1198 dict->nbElems++;
1199
1200 if ((nbi > MAX_HASH_LEN) &&
1201 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1202 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1203 /* Note that entry may have been freed at this point by xmlDictGrow */
1204
1205 return(ret);
1206 }
1207
1208 /**
1209 * xmlDictOwns:
1210 * @dict: the dictionary
1211 * @str: the string
1212 *
1213 * check if a string is owned by the dictionary
1214 *
1215 * Returns 1 if true, 0 if false and -1 in case of error
1216 * -1 in case of error
1217 */
1218 int
xmlDictOwns(xmlDictPtr dict,const xmlChar * str)1219 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1220 xmlDictStringsPtr pool;
1221
1222 if ((dict == NULL) || (str == NULL))
1223 return(-1);
1224 pool = dict->strings;
1225 while (pool != NULL) {
1226 if ((str >= &pool->array[0]) && (str <= pool->free))
1227 return(1);
1228 pool = pool->next;
1229 }
1230 if (dict->subdict)
1231 return(xmlDictOwns(dict->subdict, str));
1232 return(0);
1233 }
1234
1235 /**
1236 * xmlDictSize:
1237 * @dict: the dictionary
1238 *
1239 * Query the number of elements installed in the hash @dict.
1240 *
1241 * Returns the number of elements in the dictionary or
1242 * -1 in case of error
1243 */
1244 int
xmlDictSize(xmlDictPtr dict)1245 xmlDictSize(xmlDictPtr dict) {
1246 if (dict == NULL)
1247 return(-1);
1248 if (dict->subdict)
1249 return(dict->nbElems + dict->subdict->nbElems);
1250 return(dict->nbElems);
1251 }
1252
1253 /**
1254 * xmlDictSetLimit:
1255 * @dict: the dictionary
1256 * @limit: the limit in bytes
1257 *
1258 * Set a size limit for the dictionary
1259 * Added in 2.9.0
1260 *
1261 * Returns the previous limit of the dictionary or 0
1262 */
1263 size_t
xmlDictSetLimit(xmlDictPtr dict,size_t limit)1264 xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1265 size_t ret;
1266
1267 if (dict == NULL)
1268 return(0);
1269 ret = dict->limit;
1270 dict->limit = limit;
1271 return(ret);
1272 }
1273
1274 /**
1275 * xmlDictGetUsage:
1276 * @dict: the dictionary
1277 *
1278 * Get how much memory is used by a dictionary for strings
1279 * Added in 2.9.0
1280 *
1281 * Returns the amount of strings allocated
1282 */
1283 size_t
xmlDictGetUsage(xmlDictPtr dict)1284 xmlDictGetUsage(xmlDictPtr dict) {
1285 xmlDictStringsPtr pool;
1286 size_t limit = 0;
1287
1288 if (dict == NULL)
1289 return(0);
1290 pool = dict->strings;
1291 while (pool != NULL) {
1292 limit += pool->size;
1293 pool = pool->next;
1294 }
1295 return(limit);
1296 }
1297
1298 #define bottom_dict
1299 #include "elfgcchack.h"
1300