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