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