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 value += name[len - (plen + 1 + 1)];
490 len = 10;
491 if (plen > 10)
492 plen = 10;
493 }
494 switch (plen) {
495 case 10: value += prefix[9];
496 case 9: value += prefix[8];
497 case 8: value += prefix[7];
498 case 7: value += prefix[6];
499 case 6: value += prefix[5];
500 case 5: value += prefix[4];
501 case 4: value += prefix[3];
502 case 3: value += prefix[2];
503 case 2: value += prefix[1];
504 case 1: value += prefix[0];
505 default: break;
506 }
507 len -= plen;
508 if (len > 0) {
509 value += (unsigned long) ':';
510 len--;
511 }
512 switch (len) {
513 case 10: value += name[9];
514 case 9: value += name[8];
515 case 8: value += name[7];
516 case 7: value += name[6];
517 case 6: value += name[5];
518 case 5: value += name[4];
519 case 4: value += name[3];
520 case 3: value += name[2];
521 case 2: value += name[1];
522 case 1: value += name[0];
523 default: break;
524 }
525 return(value);
526 }
527
528 /**
529 * xmlDictCreate:
530 *
531 * Create a new dictionary
532 *
533 * Returns the newly created dictionnary, or NULL if an error occured.
534 */
535 xmlDictPtr
xmlDictCreate(void)536 xmlDictCreate(void) {
537 xmlDictPtr dict;
538
539 if (!xmlDictInitialized)
540 if (!__xmlInitializeDict())
541 return(NULL);
542
543 #ifdef DICT_DEBUG_PATTERNS
544 fprintf(stderr, "C");
545 #endif
546
547 dict = xmlMalloc(sizeof(xmlDict));
548 if (dict) {
549 dict->ref_counter = 1;
550 dict->limit = 0;
551
552 dict->size = MIN_DICT_SIZE;
553 dict->nbElems = 0;
554 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
555 dict->strings = NULL;
556 dict->subdict = NULL;
557 if (dict->dict) {
558 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
559 #ifdef DICT_RANDOMIZATION
560 dict->seed = __xmlRandom();
561 #else
562 dict->seed = 0;
563 #endif
564 return(dict);
565 }
566 xmlFree(dict);
567 }
568 return(NULL);
569 }
570
571 /**
572 * xmlDictCreateSub:
573 * @sub: an existing dictionnary
574 *
575 * Create a new dictionary, inheriting strings from the read-only
576 * dictionnary @sub. On lookup, strings are first searched in the
577 * new dictionnary, then in @sub, and if not found are created in the
578 * new dictionnary.
579 *
580 * Returns the newly created dictionnary, or NULL if an error occured.
581 */
582 xmlDictPtr
xmlDictCreateSub(xmlDictPtr sub)583 xmlDictCreateSub(xmlDictPtr sub) {
584 xmlDictPtr dict = xmlDictCreate();
585
586 if ((dict != NULL) && (sub != NULL)) {
587 #ifdef DICT_DEBUG_PATTERNS
588 fprintf(stderr, "R");
589 #endif
590 dict->seed = sub->seed;
591 dict->subdict = sub;
592 xmlDictReference(dict->subdict);
593 }
594 return(dict);
595 }
596
597 /**
598 * xmlDictReference:
599 * @dict: the dictionnary
600 *
601 * Increment the reference counter of a dictionary
602 *
603 * Returns 0 in case of success and -1 in case of error
604 */
605 int
xmlDictReference(xmlDictPtr dict)606 xmlDictReference(xmlDictPtr dict) {
607 if (!xmlDictInitialized)
608 if (!__xmlInitializeDict())
609 return(-1);
610
611 if (dict == NULL) return -1;
612 xmlRMutexLock(xmlDictMutex);
613 dict->ref_counter++;
614 xmlRMutexUnlock(xmlDictMutex);
615 return(0);
616 }
617
618 /**
619 * xmlDictGrow:
620 * @dict: the dictionnary
621 * @size: the new size of the dictionnary
622 *
623 * resize the dictionnary
624 *
625 * Returns 0 in case of success, -1 in case of failure
626 */
627 static int
xmlDictGrow(xmlDictPtr dict,size_t size)628 xmlDictGrow(xmlDictPtr dict, size_t size) {
629 unsigned long key, okey;
630 size_t oldsize, i;
631 xmlDictEntryPtr iter, next;
632 struct _xmlDictEntry *olddict;
633 #ifdef DEBUG_GROW
634 unsigned long nbElem = 0;
635 #endif
636 int ret = 0;
637 int keep_keys = 1;
638
639 if (dict == NULL)
640 return(-1);
641 if (size < 8)
642 return(-1);
643 if (size > 8 * 2048)
644 return(-1);
645
646 #ifdef DICT_DEBUG_PATTERNS
647 fprintf(stderr, "*");
648 #endif
649
650 oldsize = dict->size;
651 olddict = dict->dict;
652 if (olddict == NULL)
653 return(-1);
654 if (oldsize == MIN_DICT_SIZE)
655 keep_keys = 0;
656
657 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
658 if (dict->dict == NULL) {
659 dict->dict = olddict;
660 return(-1);
661 }
662 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
663 dict->size = size;
664
665 /* If the two loops are merged, there would be situations where
666 a new entry needs to allocated and data copied into it from
667 the main dict. It is nicer to run through the array twice, first
668 copying all the elements in the main array (less probability of
669 allocate) and then the rest, so we only free in the second loop.
670 */
671 for (i = 0; i < oldsize; i++) {
672 if (olddict[i].valid == 0)
673 continue;
674
675 if (keep_keys)
676 okey = olddict[i].okey;
677 else
678 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
679 key = okey % dict->size;
680
681 if (dict->dict[key].valid == 0) {
682 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
683 dict->dict[key].next = NULL;
684 dict->dict[key].okey = okey;
685 } else {
686 xmlDictEntryPtr entry;
687
688 entry = xmlMalloc(sizeof(xmlDictEntry));
689 if (entry != NULL) {
690 entry->name = olddict[i].name;
691 entry->len = olddict[i].len;
692 entry->okey = okey;
693 entry->next = dict->dict[key].next;
694 entry->valid = 1;
695 dict->dict[key].next = entry;
696 } else {
697 /*
698 * we don't have much ways to alert from herei
699 * result is loosing an entry and unicity garantee
700 */
701 ret = -1;
702 }
703 }
704 #ifdef DEBUG_GROW
705 nbElem++;
706 #endif
707 }
708
709 for (i = 0; i < oldsize; i++) {
710 iter = olddict[i].next;
711 while (iter) {
712 next = iter->next;
713
714 /*
715 * put back the entry in the new dict
716 */
717
718 if (keep_keys)
719 okey = iter->okey;
720 else
721 okey = xmlDictComputeKey(dict, iter->name, iter->len);
722 key = okey % dict->size;
723 if (dict->dict[key].valid == 0) {
724 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
725 dict->dict[key].next = NULL;
726 dict->dict[key].valid = 1;
727 dict->dict[key].okey = okey;
728 xmlFree(iter);
729 } else {
730 iter->next = dict->dict[key].next;
731 iter->okey = okey;
732 dict->dict[key].next = iter;
733 }
734
735 #ifdef DEBUG_GROW
736 nbElem++;
737 #endif
738
739 iter = next;
740 }
741 }
742
743 xmlFree(olddict);
744
745 #ifdef DEBUG_GROW
746 xmlGenericError(xmlGenericErrorContext,
747 "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
748 #endif
749
750 return(ret);
751 }
752
753 /**
754 * xmlDictFree:
755 * @dict: the dictionnary
756 *
757 * Free the hash @dict and its contents. The userdata is
758 * deallocated with @f if provided.
759 */
760 void
xmlDictFree(xmlDictPtr dict)761 xmlDictFree(xmlDictPtr dict) {
762 size_t i;
763 xmlDictEntryPtr iter;
764 xmlDictEntryPtr next;
765 int inside_dict = 0;
766 xmlDictStringsPtr pool, nextp;
767
768 if (dict == NULL)
769 return;
770
771 if (!xmlDictInitialized)
772 if (!__xmlInitializeDict())
773 return;
774
775 /* decrement the counter, it may be shared by a parser and docs */
776 xmlRMutexLock(xmlDictMutex);
777 dict->ref_counter--;
778 if (dict->ref_counter > 0) {
779 xmlRMutexUnlock(xmlDictMutex);
780 return;
781 }
782
783 xmlRMutexUnlock(xmlDictMutex);
784
785 if (dict->subdict != NULL) {
786 xmlDictFree(dict->subdict);
787 }
788
789 if (dict->dict) {
790 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
791 iter = &(dict->dict[i]);
792 if (iter->valid == 0)
793 continue;
794 inside_dict = 1;
795 while (iter) {
796 next = iter->next;
797 if (!inside_dict)
798 xmlFree(iter);
799 dict->nbElems--;
800 inside_dict = 0;
801 iter = next;
802 }
803 }
804 xmlFree(dict->dict);
805 }
806 pool = dict->strings;
807 while (pool != NULL) {
808 nextp = pool->next;
809 xmlFree(pool);
810 pool = nextp;
811 }
812 xmlFree(dict);
813 }
814
815 /**
816 * xmlDictLookup:
817 * @dict: the dictionnary
818 * @name: the name of the userdata
819 * @len: the length of the name, if -1 it is recomputed
820 *
821 * Add the @name to the dictionnary @dict if not present.
822 *
823 * Returns the internal copy of the name or NULL in case of internal error
824 */
825 const xmlChar *
xmlDictLookup(xmlDictPtr dict,const xmlChar * name,int len)826 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
827 unsigned long key, okey, nbi = 0;
828 xmlDictEntryPtr entry;
829 xmlDictEntryPtr insert;
830 const xmlChar *ret;
831 unsigned int l;
832
833 if ((dict == NULL) || (name == NULL))
834 return(NULL);
835
836 if (len < 0)
837 l = strlen((const char *) name);
838 else
839 l = len;
840
841 if (((dict->limit > 0) && (l >= dict->limit)) ||
842 (l > INT_MAX / 2))
843 return(NULL);
844
845 /*
846 * Check for duplicate and insertion location.
847 */
848 okey = xmlDictComputeKey(dict, name, l);
849 key = okey % dict->size;
850 if (dict->dict[key].valid == 0) {
851 insert = NULL;
852 } else {
853 for (insert = &(dict->dict[key]); insert->next != NULL;
854 insert = insert->next) {
855 #ifdef __GNUC__
856 if ((insert->okey == okey) && (insert->len == l)) {
857 if (!memcmp(insert->name, name, l))
858 return(insert->name);
859 }
860 #else
861 if ((insert->okey == okey) && (insert->len == l) &&
862 (!xmlStrncmp(insert->name, name, l)))
863 return(insert->name);
864 #endif
865 nbi++;
866 }
867 #ifdef __GNUC__
868 if ((insert->okey == okey) && (insert->len == l)) {
869 if (!memcmp(insert->name, name, l))
870 return(insert->name);
871 }
872 #else
873 if ((insert->okey == okey) && (insert->len == l) &&
874 (!xmlStrncmp(insert->name, name, l)))
875 return(insert->name);
876 #endif
877 }
878
879 if (dict->subdict) {
880 unsigned long skey;
881
882 /* we cannot always reuse the same okey for the subdict */
883 if (((dict->size == MIN_DICT_SIZE) &&
884 (dict->subdict->size != MIN_DICT_SIZE)) ||
885 ((dict->size != MIN_DICT_SIZE) &&
886 (dict->subdict->size == MIN_DICT_SIZE)))
887 skey = xmlDictComputeKey(dict->subdict, name, l);
888 else
889 skey = okey;
890
891 key = skey % dict->subdict->size;
892 if (dict->subdict->dict[key].valid != 0) {
893 xmlDictEntryPtr tmp;
894
895 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
896 tmp = tmp->next) {
897 #ifdef __GNUC__
898 if ((tmp->okey == skey) && (tmp->len == l)) {
899 if (!memcmp(tmp->name, name, l))
900 return(tmp->name);
901 }
902 #else
903 if ((tmp->okey == skey) && (tmp->len == l) &&
904 (!xmlStrncmp(tmp->name, name, l)))
905 return(tmp->name);
906 #endif
907 nbi++;
908 }
909 #ifdef __GNUC__
910 if ((tmp->okey == skey) && (tmp->len == l)) {
911 if (!memcmp(tmp->name, name, l))
912 return(tmp->name);
913 }
914 #else
915 if ((tmp->okey == skey) && (tmp->len == l) &&
916 (!xmlStrncmp(tmp->name, name, l)))
917 return(tmp->name);
918 #endif
919 }
920 key = okey % dict->size;
921 }
922
923 ret = xmlDictAddString(dict, name, l);
924 if (ret == NULL)
925 return(NULL);
926 if (insert == NULL) {
927 entry = &(dict->dict[key]);
928 } else {
929 entry = xmlMalloc(sizeof(xmlDictEntry));
930 if (entry == NULL)
931 return(NULL);
932 }
933 entry->name = ret;
934 entry->len = l;
935 entry->next = NULL;
936 entry->valid = 1;
937 entry->okey = okey;
938
939
940 if (insert != NULL)
941 insert->next = entry;
942
943 dict->nbElems++;
944
945 if ((nbi > MAX_HASH_LEN) &&
946 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
947 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
948 return(NULL);
949 }
950 /* Note that entry may have been freed at this point by xmlDictGrow */
951
952 return(ret);
953 }
954
955 /**
956 * xmlDictExists:
957 * @dict: the dictionnary
958 * @name: the name of the userdata
959 * @len: the length of the name, if -1 it is recomputed
960 *
961 * Check if the @name exists in the dictionnary @dict.
962 *
963 * Returns the internal copy of the name or NULL if not found.
964 */
965 const xmlChar *
xmlDictExists(xmlDictPtr dict,const xmlChar * name,int len)966 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
967 unsigned long key, okey, nbi = 0;
968 xmlDictEntryPtr insert;
969 unsigned int l;
970
971 if ((dict == NULL) || (name == NULL))
972 return(NULL);
973
974 if (len < 0)
975 l = strlen((const char *) name);
976 else
977 l = len;
978 if (((dict->limit > 0) && (l >= dict->limit)) ||
979 (l > INT_MAX / 2))
980 return(NULL);
981
982 /*
983 * Check for duplicate and insertion location.
984 */
985 okey = xmlDictComputeKey(dict, name, l);
986 key = okey % dict->size;
987 if (dict->dict[key].valid == 0) {
988 insert = NULL;
989 } else {
990 for (insert = &(dict->dict[key]); insert->next != NULL;
991 insert = insert->next) {
992 #ifdef __GNUC__
993 if ((insert->okey == okey) && (insert->len == l)) {
994 if (!memcmp(insert->name, name, l))
995 return(insert->name);
996 }
997 #else
998 if ((insert->okey == okey) && (insert->len == l) &&
999 (!xmlStrncmp(insert->name, name, l)))
1000 return(insert->name);
1001 #endif
1002 nbi++;
1003 }
1004 #ifdef __GNUC__
1005 if ((insert->okey == okey) && (insert->len == l)) {
1006 if (!memcmp(insert->name, name, l))
1007 return(insert->name);
1008 }
1009 #else
1010 if ((insert->okey == okey) && (insert->len == l) &&
1011 (!xmlStrncmp(insert->name, name, l)))
1012 return(insert->name);
1013 #endif
1014 }
1015
1016 if (dict->subdict) {
1017 unsigned long skey;
1018
1019 /* we cannot always reuse the same okey for the subdict */
1020 if (((dict->size == MIN_DICT_SIZE) &&
1021 (dict->subdict->size != MIN_DICT_SIZE)) ||
1022 ((dict->size != MIN_DICT_SIZE) &&
1023 (dict->subdict->size == MIN_DICT_SIZE)))
1024 skey = xmlDictComputeKey(dict->subdict, name, l);
1025 else
1026 skey = okey;
1027
1028 key = skey % dict->subdict->size;
1029 if (dict->subdict->dict[key].valid != 0) {
1030 xmlDictEntryPtr tmp;
1031
1032 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1033 tmp = tmp->next) {
1034 #ifdef __GNUC__
1035 if ((tmp->okey == skey) && (tmp->len == l)) {
1036 if (!memcmp(tmp->name, name, l))
1037 return(tmp->name);
1038 }
1039 #else
1040 if ((tmp->okey == skey) && (tmp->len == l) &&
1041 (!xmlStrncmp(tmp->name, name, l)))
1042 return(tmp->name);
1043 #endif
1044 nbi++;
1045 }
1046 #ifdef __GNUC__
1047 if ((tmp->okey == skey) && (tmp->len == l)) {
1048 if (!memcmp(tmp->name, name, l))
1049 return(tmp->name);
1050 }
1051 #else
1052 if ((tmp->okey == skey) && (tmp->len == l) &&
1053 (!xmlStrncmp(tmp->name, name, l)))
1054 return(tmp->name);
1055 #endif
1056 }
1057 }
1058
1059 /* not found */
1060 return(NULL);
1061 }
1062
1063 /**
1064 * xmlDictQLookup:
1065 * @dict: the dictionnary
1066 * @prefix: the prefix
1067 * @name: the name
1068 *
1069 * Add the QName @prefix:@name to the hash @dict if not present.
1070 *
1071 * Returns the internal copy of the QName or NULL in case of internal error
1072 */
1073 const xmlChar *
xmlDictQLookup(xmlDictPtr dict,const xmlChar * prefix,const xmlChar * name)1074 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1075 unsigned long okey, key, nbi = 0;
1076 xmlDictEntryPtr entry;
1077 xmlDictEntryPtr insert;
1078 const xmlChar *ret;
1079 unsigned int len, plen, l;
1080
1081 if ((dict == NULL) || (name == NULL))
1082 return(NULL);
1083 if (prefix == NULL)
1084 return(xmlDictLookup(dict, name, -1));
1085
1086 l = len = strlen((const char *) name);
1087 plen = strlen((const char *) prefix);
1088 len += 1 + plen;
1089
1090 /*
1091 * Check for duplicate and insertion location.
1092 */
1093 okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1094 key = okey % dict->size;
1095 if (dict->dict[key].valid == 0) {
1096 insert = NULL;
1097 } else {
1098 for (insert = &(dict->dict[key]); insert->next != NULL;
1099 insert = insert->next) {
1100 if ((insert->okey == okey) && (insert->len == len) &&
1101 (xmlStrQEqual(prefix, name, insert->name)))
1102 return(insert->name);
1103 nbi++;
1104 }
1105 if ((insert->okey == okey) && (insert->len == len) &&
1106 (xmlStrQEqual(prefix, name, insert->name)))
1107 return(insert->name);
1108 }
1109
1110 if (dict->subdict) {
1111 unsigned long skey;
1112
1113 /* we cannot always reuse the same okey for the subdict */
1114 if (((dict->size == MIN_DICT_SIZE) &&
1115 (dict->subdict->size != MIN_DICT_SIZE)) ||
1116 ((dict->size != MIN_DICT_SIZE) &&
1117 (dict->subdict->size == MIN_DICT_SIZE)))
1118 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1119 else
1120 skey = okey;
1121
1122 key = skey % dict->subdict->size;
1123 if (dict->subdict->dict[key].valid != 0) {
1124 xmlDictEntryPtr tmp;
1125 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1126 tmp = tmp->next) {
1127 if ((tmp->okey == skey) && (tmp->len == len) &&
1128 (xmlStrQEqual(prefix, name, tmp->name)))
1129 return(tmp->name);
1130 nbi++;
1131 }
1132 if ((tmp->okey == skey) && (tmp->len == len) &&
1133 (xmlStrQEqual(prefix, name, tmp->name)))
1134 return(tmp->name);
1135 }
1136 key = okey % dict->size;
1137 }
1138
1139 ret = xmlDictAddQString(dict, prefix, plen, name, l);
1140 if (ret == NULL)
1141 return(NULL);
1142 if (insert == NULL) {
1143 entry = &(dict->dict[key]);
1144 } else {
1145 entry = xmlMalloc(sizeof(xmlDictEntry));
1146 if (entry == NULL)
1147 return(NULL);
1148 }
1149 entry->name = ret;
1150 entry->len = len;
1151 entry->next = NULL;
1152 entry->valid = 1;
1153 entry->okey = okey;
1154
1155 if (insert != NULL)
1156 insert->next = entry;
1157
1158 dict->nbElems++;
1159
1160 if ((nbi > MAX_HASH_LEN) &&
1161 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1162 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1163 /* Note that entry may have been freed at this point by xmlDictGrow */
1164
1165 return(ret);
1166 }
1167
1168 /**
1169 * xmlDictOwns:
1170 * @dict: the dictionnary
1171 * @str: the string
1172 *
1173 * check if a string is owned by the disctionary
1174 *
1175 * Returns 1 if true, 0 if false and -1 in case of error
1176 * -1 in case of error
1177 */
1178 int
xmlDictOwns(xmlDictPtr dict,const xmlChar * str)1179 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1180 xmlDictStringsPtr pool;
1181
1182 if ((dict == NULL) || (str == NULL))
1183 return(-1);
1184 pool = dict->strings;
1185 while (pool != NULL) {
1186 if ((str >= &pool->array[0]) && (str <= pool->free))
1187 return(1);
1188 pool = pool->next;
1189 }
1190 if (dict->subdict)
1191 return(xmlDictOwns(dict->subdict, str));
1192 return(0);
1193 }
1194
1195 /**
1196 * xmlDictSize:
1197 * @dict: the dictionnary
1198 *
1199 * Query the number of elements installed in the hash @dict.
1200 *
1201 * Returns the number of elements in the dictionnary or
1202 * -1 in case of error
1203 */
1204 int
xmlDictSize(xmlDictPtr dict)1205 xmlDictSize(xmlDictPtr dict) {
1206 if (dict == NULL)
1207 return(-1);
1208 if (dict->subdict)
1209 return(dict->nbElems + dict->subdict->nbElems);
1210 return(dict->nbElems);
1211 }
1212
1213 /**
1214 * xmlDictSetLimit:
1215 * @dict: the dictionnary
1216 * @limit: the limit in bytes
1217 *
1218 * Set a size limit for the dictionary
1219 * Added in 2.9.0
1220 *
1221 * Returns the previous limit of the dictionary or 0
1222 */
1223 size_t
xmlDictSetLimit(xmlDictPtr dict,size_t limit)1224 xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1225 size_t ret;
1226
1227 if (dict == NULL)
1228 return(0);
1229 ret = dict->limit;
1230 dict->limit = limit;
1231 return(ret);
1232 }
1233
1234 /**
1235 * xmlDictGetUsage:
1236 * @dict: the dictionnary
1237 *
1238 * Get how much memory is used by a dictionary for strings
1239 * Added in 2.9.0
1240 *
1241 * Returns the amount of strings allocated
1242 */
1243 size_t
xmlDictGetUsage(xmlDictPtr dict)1244 xmlDictGetUsage(xmlDictPtr dict) {
1245 xmlDictStringsPtr pool;
1246 size_t limit = 0;
1247
1248 if (dict == NULL)
1249 return(0);
1250 pool = dict->strings;
1251 while (pool != NULL) {
1252 limit += pool->size;
1253 pool = pool->next;
1254 }
1255 return(limit);
1256 }
1257
1258 #define bottom_dict
1259 #include "elfgcchack.h"
1260