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