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