2 * dict.c: dictionary of reusable strings, just used to avoid allocation
3 * and freeing operations.
5 * Copyright (C) 2003-2012 Daniel Veillard.
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.
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.
16 * Author: daniel@veillard.com
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
37 #if !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION)
38 #define DICT_RANDOMIZATION
45 #ifdef HAVE_INTTYPES_H
48 typedef unsigned __int32
uint32_t;
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>
57 /* #define DEBUG_GROW */
58 /* #define DICT_DEBUG_PATTERNS */
60 #define MAX_HASH_LEN 3
61 #define MIN_DICT_SIZE 128
62 #define MAX_DICT_HASH 8 * 2048
66 #define xmlDictComputeKey(dict, name, len) \
67 (((dict)->size == MIN_DICT_SIZE) ? \
68 xmlDictComputeFastKey(name, len, (dict)->seed) : \
69 xmlDictComputeBigKey(name, len, (dict)->seed))
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)))
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 */
86 * An entry in the dictionary
88 typedef struct _xmlDictEntry xmlDictEntry
;
89 typedef xmlDictEntry
*xmlDictEntryPtr
;
90 struct _xmlDictEntry
{
91 struct _xmlDictEntry
*next
;
98 typedef struct _xmlDictStrings xmlDictStrings
;
99 typedef xmlDictStrings
*xmlDictStringsPtr
;
100 struct _xmlDictStrings
{
101 xmlDictStringsPtr next
;
109 * The entire dictionary
114 struct _xmlDictEntry
*dict
;
116 unsigned int nbElems
;
117 xmlDictStringsPtr strings
;
119 struct _xmlDict
*subdict
;
120 /* used for randomization */
122 /* used to impose a limit on size */
127 * A mutex for modifying the reference counter for shared
130 static xmlMutexPtr xmlDictMutex
= NULL
;
133 * Whether the dictionary mutex was initialized.
135 static int xmlDictInitialized
= 0;
137 #ifdef DICT_RANDOMIZATION
140 * Internal data for random function, protected by xmlDictMutex
142 static unsigned int rand_seed
= 0;
149 * DEPRECATED: This function will be made private. Call xmlInitParser to
150 * initialize the library.
152 * Do the dictionary mutex initialization.
154 * Returns 0 if initialization was already done, and 1 if that
155 * call led to the initialization
157 int xmlInitializeDict(void) {
162 * __xmlInitializeDict:
164 * This function is not public
165 * Do the dictionary mutex initialization.
166 * this function is not thread safe, initialization should
167 * normally be done once at setup when called from xmlOnceInit()
168 * we may also land in this code if thread support is not compiled in
170 * Returns 0 if initialization was already done, and 1 if that
171 * call led to the initialization
173 int __xmlInitializeDict(void) {
174 if (xmlDictInitialized
)
177 if ((xmlDictMutex
= xmlNewMutex()) == NULL
)
179 xmlMutexLock(xmlDictMutex
);
181 #ifdef DICT_RANDOMIZATION
183 rand_seed
= time(NULL
);
189 xmlDictInitialized
= 1;
190 xmlMutexUnlock(xmlDictMutex
);
194 #ifdef DICT_RANDOMIZATION
195 int __xmlRandom(void) {
198 if (xmlDictInitialized
== 0)
199 __xmlInitializeDict();
201 xmlMutexLock(xmlDictMutex
);
203 ret
= rand_r(& rand_seed
);
207 xmlMutexUnlock(xmlDictMutex
);
215 * DEPRECATED: This function will be made private. Call xmlCleanupParser
216 * to free global state but see the warnings there. xmlCleanupParser
217 * should be only called once at program exit. In most cases, you don't
218 * have call cleanup functions at all.
220 * Free the dictionary mutex. Do not call unless sure the library
221 * is not in use anymore !
224 xmlDictCleanup(void) {
225 if (!xmlDictInitialized
)
228 xmlFreeMutex(xmlDictMutex
);
230 xmlDictInitialized
= 0;
235 * @dict: the dictionary
236 * @name: the name of the userdata
237 * @len: the length of the name
239 * Add the string to the array[s]
241 * Returns the pointer of the local string, or NULL in case of error.
243 static const xmlChar
*
244 xmlDictAddString(xmlDictPtr dict
, const xmlChar
*name
, unsigned int namelen
) {
245 xmlDictStringsPtr pool
;
247 size_t size
= 0; /* + sizeof(_xmlDictStrings) == 1024 */
250 #ifdef DICT_DEBUG_PATTERNS
251 fprintf(stderr
, "-");
253 pool
= dict
->strings
;
254 while (pool
!= NULL
) {
255 if ((size_t)(pool
->end
- pool
->free
) > namelen
)
257 if (pool
->size
> size
) size
= pool
->size
;
262 * Not found, need to allocate
265 if ((dict
->limit
> 0) && (limit
> dict
->limit
)) {
269 if (size
== 0) size
= 1000;
270 else size
*= 4; /* exponential growth */
271 if (size
< 4 * namelen
)
272 size
= 4 * namelen
; /* just in case ! */
273 pool
= (xmlDictStringsPtr
) xmlMalloc(sizeof(xmlDictStrings
) + size
);
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
, "+");
288 memcpy(pool
->free
, name
, namelen
);
289 pool
->free
+= namelen
;
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
303 * Add the QName to the array[s]
305 * Returns the pointer of the local string, or NULL in case of error.
307 static const xmlChar
*
308 xmlDictAddQString(xmlDictPtr dict
, const xmlChar
*prefix
, unsigned int plen
,
309 const xmlChar
*name
, unsigned int namelen
)
311 xmlDictStringsPtr pool
;
313 size_t size
= 0; /* + sizeof(_xmlDictStrings) == 1024 */
316 if (prefix
== NULL
) return(xmlDictAddString(dict
, name
, namelen
));
318 #ifdef DICT_DEBUG_PATTERNS
319 fprintf(stderr
, "=");
321 pool
= dict
->strings
;
322 while (pool
!= NULL
) {
323 if ((size_t)(pool
->end
- pool
->free
) > namelen
+ plen
+ 1)
325 if (pool
->size
> size
) size
= pool
->size
;
330 * Not found, need to allocate
333 if ((dict
->limit
> 0) && (limit
> dict
->limit
)) {
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 ! */
341 pool
= (xmlDictStringsPtr
) xmlMalloc(sizeof(xmlDictStrings
) + size
);
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
, "+");
356 memcpy(pool
->free
, prefix
, plen
);
358 *(pool
->free
++) = ':';
359 memcpy(pool
->free
, name
, namelen
);
360 pool
->free
+= namelen
;
368 * xmlDictComputeBigKey:
370 * Calculate a hash key using a good hash function that works well for
371 * larger hash table sizes.
373 * Hash function by "One-at-a-Time Hash" see
374 * http://burtleburtle.net/bob/hash/doobs.html
378 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
381 xmlDictComputeBigKey(const xmlChar
* data
, int namelen
, int seed
) {
385 if (namelen
<= 0 || data
== NULL
) return(0);
389 for (i
= 0;i
< namelen
; i
++) {
391 hash
+= (hash
<< 10);
395 hash
^= (hash
>> 11);
396 hash
+= (hash
<< 15);
402 * xmlDictComputeBigQKey:
404 * Calculate a hash key for two strings using a good hash function
405 * that works well for larger hash table sizes.
407 * Hash function by "One-at-a-Time Hash" see
408 * http://burtleburtle.net/bob/hash/doobs.html
410 * Neither of the two strings must be NULL.
413 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
416 xmlDictComputeBigQKey(const xmlChar
*prefix
, int plen
,
417 const xmlChar
*name
, int len
, int seed
)
424 for (i
= 0;i
< plen
; i
++) {
426 hash
+= (hash
<< 10);
430 hash
+= (hash
<< 10);
433 for (i
= 0;i
< len
; i
++) {
435 hash
+= (hash
<< 10);
439 hash
^= (hash
>> 11);
440 hash
+= (hash
<< 15);
444 #endif /* WITH_BIG_KEY */
447 * xmlDictComputeFastKey:
449 * Calculate a hash key using a fast hash function that works well
450 * for low hash table fill.
453 xmlDictComputeFastKey(const xmlChar
*name
, int namelen
, int seed
) {
454 unsigned long value
= seed
;
456 if (name
== NULL
) return(0);
460 value
+= name
[namelen
- 1];
464 case 10: value
+= name
[9];
466 case 9: value
+= name
[8];
468 case 8: value
+= name
[7];
470 case 7: value
+= name
[6];
472 case 6: value
+= name
[5];
474 case 5: value
+= name
[4];
476 case 4: value
+= name
[3];
478 case 3: value
+= name
[2];
480 case 2: value
+= name
[1];
488 * xmlDictComputeFastQKey:
490 * Calculate a hash key for two strings using a fast hash function
491 * that works well for low hash table fill.
493 * Neither of the two strings must be NULL.
496 xmlDictComputeFastQKey(const xmlChar
*prefix
, int plen
,
497 const xmlChar
*name
, int len
, int seed
)
499 unsigned long value
= (unsigned long) seed
;
502 value
+= 30 * (unsigned long) ':';
504 value
+= 30 * (*prefix
);
507 int offset
= len
- (plen
+ 1 + 1);
509 offset
= len
- (10 + 1);
510 value
+= name
[offset
];
516 case 10: value
+= prefix
[9];
518 case 9: value
+= prefix
[8];
520 case 8: value
+= prefix
[7];
522 case 7: value
+= prefix
[6];
524 case 6: value
+= prefix
[5];
526 case 5: value
+= prefix
[4];
528 case 4: value
+= prefix
[3];
530 case 3: value
+= prefix
[2];
532 case 2: value
+= prefix
[1];
534 case 1: value
+= prefix
[0];
540 value
+= (unsigned long) ':';
544 case 10: value
+= name
[9];
546 case 9: value
+= name
[8];
548 case 8: value
+= name
[7];
550 case 7: value
+= name
[6];
552 case 6: value
+= name
[5];
554 case 5: value
+= name
[4];
556 case 4: value
+= name
[3];
558 case 3: value
+= name
[2];
560 case 2: value
+= name
[1];
562 case 1: value
+= name
[0];
572 * Create a new dictionary
574 * Returns the newly created dictionary, or NULL if an error occurred.
577 xmlDictCreate(void) {
580 if (!xmlDictInitialized
)
581 if (!__xmlInitializeDict())
584 #ifdef DICT_DEBUG_PATTERNS
585 fprintf(stderr
, "C");
588 dict
= xmlMalloc(sizeof(xmlDict
));
590 dict
->ref_counter
= 1;
593 dict
->size
= MIN_DICT_SIZE
;
595 dict
->dict
= xmlMalloc(MIN_DICT_SIZE
* sizeof(xmlDictEntry
));
596 dict
->strings
= NULL
;
597 dict
->subdict
= NULL
;
599 memset(dict
->dict
, 0, MIN_DICT_SIZE
* sizeof(xmlDictEntry
));
600 #ifdef DICT_RANDOMIZATION
601 dict
->seed
= __xmlRandom();
614 * @sub: an existing dictionary
616 * Create a new dictionary, inheriting strings from the read-only
617 * dictionary @sub. On lookup, strings are first searched in the
618 * new dictionary, then in @sub, and if not found are created in the
621 * Returns the newly created dictionary, or NULL if an error occurred.
624 xmlDictCreateSub(xmlDictPtr sub
) {
625 xmlDictPtr dict
= xmlDictCreate();
627 if ((dict
!= NULL
) && (sub
!= NULL
)) {
628 #ifdef DICT_DEBUG_PATTERNS
629 fprintf(stderr
, "R");
631 dict
->seed
= sub
->seed
;
633 xmlDictReference(dict
->subdict
);
640 * @dict: the dictionary
642 * Increment the reference counter of a dictionary
644 * Returns 0 in case of success and -1 in case of error
647 xmlDictReference(xmlDictPtr dict
) {
648 if (!xmlDictInitialized
)
649 if (!__xmlInitializeDict())
652 if (dict
== NULL
) return -1;
653 xmlMutexLock(xmlDictMutex
);
655 xmlMutexUnlock(xmlDictMutex
);
661 * @dict: the dictionary
662 * @size: the new size of the dictionary
664 * resize the dictionary
666 * Returns 0 in case of success, -1 in case of failure
669 xmlDictGrow(xmlDictPtr dict
, size_t size
) {
670 unsigned long key
, okey
;
672 xmlDictEntryPtr iter
, next
;
673 struct _xmlDictEntry
*olddict
;
675 unsigned long nbElem
= 0;
687 #ifdef DICT_DEBUG_PATTERNS
688 fprintf(stderr
, "*");
691 oldsize
= dict
->size
;
692 olddict
= dict
->dict
;
695 if (oldsize
== MIN_DICT_SIZE
)
698 dict
->dict
= xmlMalloc(size
* sizeof(xmlDictEntry
));
699 if (dict
->dict
== NULL
) {
700 dict
->dict
= olddict
;
703 memset(dict
->dict
, 0, size
* sizeof(xmlDictEntry
));
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.
712 for (i
= 0; i
< oldsize
; i
++) {
713 if (olddict
[i
].valid
== 0)
717 okey
= olddict
[i
].okey
;
719 okey
= xmlDictComputeKey(dict
, olddict
[i
].name
, olddict
[i
].len
);
720 key
= okey
% dict
->size
;
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
;
727 xmlDictEntryPtr entry
;
729 entry
= xmlMalloc(sizeof(xmlDictEntry
));
731 entry
->name
= olddict
[i
].name
;
732 entry
->len
= olddict
[i
].len
;
734 entry
->next
= dict
->dict
[key
].next
;
736 dict
->dict
[key
].next
= entry
;
739 * we don't have much ways to alert from here
740 * result is losing an entry and unicity guarantee
750 for (i
= 0; i
< oldsize
; i
++) {
751 iter
= olddict
[i
].next
;
756 * put back the entry in the new dict
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
;
771 iter
->next
= dict
->dict
[key
].next
;
773 dict
->dict
[key
].next
= iter
;
787 xmlGenericError(xmlGenericErrorContext
,
788 "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize
, size
, nbElem
);
796 * @dict: the dictionary
798 * Free the hash @dict and its contents. The userdata is
799 * deallocated with @f if provided.
802 xmlDictFree(xmlDictPtr dict
) {
804 xmlDictEntryPtr iter
;
805 xmlDictEntryPtr next
;
807 xmlDictStringsPtr pool
, nextp
;
812 if (!xmlDictInitialized
)
813 if (!__xmlInitializeDict())
816 /* decrement the counter, it may be shared by a parser and docs */
817 xmlMutexLock(xmlDictMutex
);
819 if (dict
->ref_counter
> 0) {
820 xmlMutexUnlock(xmlDictMutex
);
824 xmlMutexUnlock(xmlDictMutex
);
826 if (dict
->subdict
!= NULL
) {
827 xmlDictFree(dict
->subdict
);
831 for(i
= 0; ((i
< dict
->size
) && (dict
->nbElems
> 0)); i
++) {
832 iter
= &(dict
->dict
[i
]);
833 if (iter
->valid
== 0)
847 pool
= dict
->strings
;
848 while (pool
!= NULL
) {
858 * @dict: the dictionary
859 * @name: the name of the userdata
860 * @len: the length of the name, if -1 it is recomputed
862 * Add the @name to the dictionary @dict if not present.
864 * Returns the internal copy of the name or NULL in case of internal error
867 xmlDictLookup(xmlDictPtr dict
, const xmlChar
*name
, int len
) {
868 unsigned long key
, okey
, nbi
= 0;
869 xmlDictEntryPtr entry
;
870 xmlDictEntryPtr insert
;
874 if ((dict
== NULL
) || (name
== NULL
))
878 l
= strlen((const char *) name
);
882 if (((dict
->limit
> 0) && (l
>= dict
->limit
)) ||
887 * Check for duplicate and insertion location.
889 okey
= xmlDictComputeKey(dict
, name
, l
);
890 key
= okey
% dict
->size
;
891 if (dict
->dict
[key
].valid
== 0) {
894 for (insert
= &(dict
->dict
[key
]); insert
->next
!= NULL
;
895 insert
= insert
->next
) {
897 if ((insert
->okey
== okey
) && (insert
->len
== l
)) {
898 if (!memcmp(insert
->name
, name
, l
))
899 return(insert
->name
);
902 if ((insert
->okey
== okey
) && (insert
->len
== l
) &&
903 (!xmlStrncmp(insert
->name
, name
, l
)))
904 return(insert
->name
);
909 if ((insert
->okey
== okey
) && (insert
->len
== l
)) {
910 if (!memcmp(insert
->name
, name
, l
))
911 return(insert
->name
);
914 if ((insert
->okey
== okey
) && (insert
->len
== l
) &&
915 (!xmlStrncmp(insert
->name
, name
, l
)))
916 return(insert
->name
);
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
);
932 key
= skey
% dict
->subdict
->size
;
933 if (dict
->subdict
->dict
[key
].valid
!= 0) {
936 for (tmp
= &(dict
->subdict
->dict
[key
]); tmp
->next
!= NULL
;
939 if ((tmp
->okey
== skey
) && (tmp
->len
== l
)) {
940 if (!memcmp(tmp
->name
, name
, l
))
944 if ((tmp
->okey
== skey
) && (tmp
->len
== l
) &&
945 (!xmlStrncmp(tmp
->name
, name
, l
)))
951 if ((tmp
->okey
== skey
) && (tmp
->len
== l
)) {
952 if (!memcmp(tmp
->name
, name
, l
))
956 if ((tmp
->okey
== skey
) && (tmp
->len
== l
) &&
957 (!xmlStrncmp(tmp
->name
, name
, l
)))
961 key
= okey
% dict
->size
;
964 ret
= xmlDictAddString(dict
, name
, l
);
967 if (insert
== NULL
) {
968 entry
= &(dict
->dict
[key
]);
970 entry
= xmlMalloc(sizeof(xmlDictEntry
));
982 insert
->next
= entry
;
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)
991 /* Note that entry may have been freed at this point by xmlDictGrow */
998 * @dict: the dictionary
999 * @name: the name of the userdata
1000 * @len: the length of the name, if -1 it is recomputed
1002 * Check if the @name exists in the dictionary @dict.
1004 * Returns the internal copy of the name or NULL if not found.
1007 xmlDictExists(xmlDictPtr dict
, const xmlChar
*name
, int len
) {
1008 unsigned long key
, okey
, nbi
= 0;
1009 xmlDictEntryPtr insert
;
1012 if ((dict
== NULL
) || (name
== NULL
))
1016 l
= strlen((const char *) name
);
1019 if (((dict
->limit
> 0) && (l
>= dict
->limit
)) ||
1024 * Check for duplicate and insertion location.
1026 okey
= xmlDictComputeKey(dict
, name
, l
);
1027 key
= okey
% dict
->size
;
1028 if (dict
->dict
[key
].valid
== 0) {
1031 for (insert
= &(dict
->dict
[key
]); insert
->next
!= NULL
;
1032 insert
= insert
->next
) {
1034 if ((insert
->okey
== okey
) && (insert
->len
== l
)) {
1035 if (!memcmp(insert
->name
, name
, l
))
1036 return(insert
->name
);
1039 if ((insert
->okey
== okey
) && (insert
->len
== l
) &&
1040 (!xmlStrncmp(insert
->name
, name
, l
)))
1041 return(insert
->name
);
1046 if ((insert
->okey
== okey
) && (insert
->len
== l
)) {
1047 if (!memcmp(insert
->name
, name
, l
))
1048 return(insert
->name
);
1051 if ((insert
->okey
== okey
) && (insert
->len
== l
) &&
1052 (!xmlStrncmp(insert
->name
, name
, l
)))
1053 return(insert
->name
);
1057 if (dict
->subdict
) {
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
);
1069 key
= skey
% dict
->subdict
->size
;
1070 if (dict
->subdict
->dict
[key
].valid
!= 0) {
1071 xmlDictEntryPtr tmp
;
1073 for (tmp
= &(dict
->subdict
->dict
[key
]); tmp
->next
!= NULL
;
1076 if ((tmp
->okey
== skey
) && (tmp
->len
== l
)) {
1077 if (!memcmp(tmp
->name
, name
, l
))
1081 if ((tmp
->okey
== skey
) && (tmp
->len
== l
) &&
1082 (!xmlStrncmp(tmp
->name
, name
, l
)))
1088 if ((tmp
->okey
== skey
) && (tmp
->len
== l
)) {
1089 if (!memcmp(tmp
->name
, name
, l
))
1093 if ((tmp
->okey
== skey
) && (tmp
->len
== l
) &&
1094 (!xmlStrncmp(tmp
->name
, name
, l
)))
1106 * @dict: the dictionary
1107 * @prefix: the prefix
1110 * Add the QName @prefix:@name to the hash @dict if not present.
1112 * Returns the internal copy of the QName or NULL in case of internal error
1115 xmlDictQLookup(xmlDictPtr dict
, const xmlChar
*prefix
, const xmlChar
*name
) {
1116 unsigned long okey
, key
, nbi
= 0;
1117 xmlDictEntryPtr entry
;
1118 xmlDictEntryPtr insert
;
1120 unsigned int len
, plen
, l
;
1122 if ((dict
== NULL
) || (name
== NULL
))
1125 return(xmlDictLookup(dict
, name
, -1));
1127 l
= len
= strlen((const char *) name
);
1128 plen
= strlen((const char *) prefix
);
1132 * Check for duplicate and insertion location.
1134 okey
= xmlDictComputeQKey(dict
, prefix
, plen
, name
, l
);
1135 key
= okey
% dict
->size
;
1136 if (dict
->dict
[key
].valid
== 0) {
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
);
1146 if ((insert
->okey
== okey
) && (insert
->len
== len
) &&
1147 (xmlStrQEqual(prefix
, name
, insert
->name
)))
1148 return(insert
->name
);
1151 if (dict
->subdict
) {
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
);
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
;
1168 if ((tmp
->okey
== skey
) && (tmp
->len
== len
) &&
1169 (xmlStrQEqual(prefix
, name
, tmp
->name
)))
1173 if ((tmp
->okey
== skey
) && (tmp
->len
== len
) &&
1174 (xmlStrQEqual(prefix
, name
, tmp
->name
)))
1177 key
= okey
% dict
->size
;
1180 ret
= xmlDictAddQString(dict
, prefix
, plen
, name
, l
);
1183 if (insert
== NULL
) {
1184 entry
= &(dict
->dict
[key
]);
1186 entry
= xmlMalloc(sizeof(xmlDictEntry
));
1197 insert
->next
= entry
;
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 */
1211 * @dict: the dictionary
1214 * check if a string is owned by the dictionary
1216 * Returns 1 if true, 0 if false and -1 in case of error
1217 * -1 in case of error
1220 xmlDictOwns(xmlDictPtr dict
, const xmlChar
*str
) {
1221 xmlDictStringsPtr pool
;
1223 if ((dict
== NULL
) || (str
== NULL
))
1225 pool
= dict
->strings
;
1226 while (pool
!= NULL
) {
1227 if ((str
>= &pool
->array
[0]) && (str
<= pool
->free
))
1232 return(xmlDictOwns(dict
->subdict
, str
));
1238 * @dict: the dictionary
1240 * Query the number of elements installed in the hash @dict.
1242 * Returns the number of elements in the dictionary or
1243 * -1 in case of error
1246 xmlDictSize(xmlDictPtr dict
) {
1250 return(dict
->nbElems
+ dict
->subdict
->nbElems
);
1251 return(dict
->nbElems
);
1256 * @dict: the dictionary
1257 * @limit: the limit in bytes
1259 * Set a size limit for the dictionary
1262 * Returns the previous limit of the dictionary or 0
1265 xmlDictSetLimit(xmlDictPtr dict
, size_t limit
) {
1271 dict
->limit
= limit
;
1277 * @dict: the dictionary
1279 * Get how much memory is used by a dictionary for strings
1282 * Returns the amount of strings allocated
1285 xmlDictGetUsage(xmlDictPtr dict
) {
1286 xmlDictStringsPtr pool
;
1291 pool
= dict
->strings
;
1292 while (pool
!= NULL
) {
1293 limit
+= pool
->size
;