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 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
14 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
16 * Author: daniel@veillard.com
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
41 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
42 #define DICT_RANDOMIZATION
49 #ifdef HAVE_INTTYPES_H
52 typedef unsigned __int32 uint32_t;
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>
61 /* #define DEBUG_GROW */
62 /* #define DICT_DEBUG_PATTERNS */
64 #define MAX_HASH_LEN 3
65 #define MIN_DICT_SIZE 128
66 #define MAX_DICT_HASH 8 * 2048
70 #define xmlDictComputeKey(dict, name, len) \
71 (((dict)->size == MIN_DICT_SIZE) ? \
72 xmlDictComputeFastKey(name, len, (dict)->seed) : \
73 xmlDictComputeBigKey(name, len, (dict)->seed))
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)))
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 */
90 * An entry in the dictionnary
92 typedef struct _xmlDictEntry xmlDictEntry;
93 typedef xmlDictEntry *xmlDictEntryPtr;
94 struct _xmlDictEntry {
95 struct _xmlDictEntry *next;
102 typedef struct _xmlDictStrings xmlDictStrings;
103 typedef xmlDictStrings *xmlDictStringsPtr;
104 struct _xmlDictStrings {
105 xmlDictStringsPtr next;
113 * The entire dictionnary
118 struct _xmlDictEntry *dict;
120 unsigned int nbElems;
121 xmlDictStringsPtr strings;
123 struct _xmlDict *subdict;
124 /* used for randomization */
126 /* used to impose a limit on size */
131 * A mutex for modifying the reference counter for shared
134 static xmlRMutexPtr xmlDictMutex = NULL;
137 * Whether the dictionary mutex was initialized.
139 static int xmlDictInitialized = 0;
141 #ifdef DICT_RANDOMIZATION
144 * Internal data for random function, protected by xmlDictMutex
146 static unsigned int rand_seed = 0;
153 * Do the dictionary mutex initialization.
154 * this function is deprecated
156 * Returns 0 if initialization was already done, and 1 if that
157 * call led to the initialization
159 int xmlInitializeDict(void) {
164 * __xmlInitializeDict:
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
172 * Returns 0 if initialization was already done, and 1 if that
173 * call led to the initialization
175 int __xmlInitializeDict(void) {
176 if (xmlDictInitialized)
179 if ((xmlDictMutex = xmlNewRMutex()) == NULL)
181 xmlRMutexLock(xmlDictMutex);
183 #ifdef DICT_RANDOMIZATION
185 rand_seed = time(NULL);
191 xmlDictInitialized = 1;
192 xmlRMutexUnlock(xmlDictMutex);
196 #ifdef DICT_RANDOMIZATION
197 int __xmlRandom(void) {
200 if (xmlDictInitialized == 0)
201 __xmlInitializeDict();
203 xmlRMutexLock(xmlDictMutex);
205 ret = rand_r(& rand_seed);
209 xmlRMutexUnlock(xmlDictMutex);
217 * Free the dictionary mutex. Do not call unless sure the library
218 * is not in use anymore !
221 xmlDictCleanup(void) {
222 if (!xmlDictInitialized)
225 xmlFreeRMutex(xmlDictMutex);
227 xmlDictInitialized = 0;
232 * @dict: the dictionnary
233 * @name: the name of the userdata
234 * @len: the length of the name
236 * Add the string to the array[s]
238 * Returns the pointer of the local string, or NULL in case of error.
240 static const xmlChar *
241 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
242 xmlDictStringsPtr pool;
244 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
247 #ifdef DICT_DEBUG_PATTERNS
248 fprintf(stderr, "-");
250 pool = dict->strings;
251 while (pool != NULL) {
252 if (pool->end - pool->free > namelen)
254 if (pool->size > size) size = pool->size;
259 * Not found, need to allocate
262 if ((dict->limit > 0) && (limit > dict->limit)) {
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);
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, "+");
285 memcpy(pool->free, name, namelen);
286 pool->free += namelen;
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
300 * Add the QName to the array[s]
302 * Returns the pointer of the local string, or NULL in case of error.
304 static const xmlChar *
305 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
306 const xmlChar *name, unsigned int namelen)
308 xmlDictStringsPtr pool;
310 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
313 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
315 #ifdef DICT_DEBUG_PATTERNS
316 fprintf(stderr, "=");
318 pool = dict->strings;
319 while (pool != NULL) {
320 if (pool->end - pool->free > namelen + plen + 1)
322 if (pool->size > size) size = pool->size;
327 * Not found, need to allocate
330 if ((dict->limit > 0) && (limit > dict->limit)) {
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);
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, "+");
353 memcpy(pool->free, prefix, plen);
355 *(pool->free++) = ':';
356 memcpy(pool->free, name, namelen);
357 pool->free += namelen;
365 * xmlDictComputeBigKey:
367 * Calculate a hash key using a good hash function that works well for
368 * larger hash table sizes.
370 * Hash function by "One-at-a-Time Hash" see
371 * http://burtleburtle.net/bob/hash/doobs.html
375 xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
379 if (namelen <= 0 || data == NULL) return(0);
383 for (i = 0;i < namelen; i++) {
385 hash += (hash << 10);
389 hash ^= (hash >> 11);
390 hash += (hash << 15);
396 * xmlDictComputeBigQKey:
398 * Calculate a hash key for two strings using a good hash function
399 * that works well for larger hash table sizes.
401 * Hash function by "One-at-a-Time Hash" see
402 * http://burtleburtle.net/bob/hash/doobs.html
404 * Neither of the two strings must be NULL.
407 xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
408 const xmlChar *name, int len, int seed)
415 for (i = 0;i < plen; i++) {
417 hash += (hash << 10);
421 hash += (hash << 10);
424 for (i = 0;i < len; i++) {
426 hash += (hash << 10);
430 hash ^= (hash >> 11);
431 hash += (hash << 15);
435 #endif /* WITH_BIG_KEY */
438 * xmlDictComputeFastKey:
440 * Calculate a hash key using a fast hash function that works well
441 * for low hash table fill.
444 xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
445 unsigned long value = seed;
447 if (name == NULL) return(0);
451 value += name[namelen - 1];
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];
470 * xmlDictComputeFastQKey:
472 * Calculate a hash key for two strings using a fast hash function
473 * that works well for low hash table fill.
475 * Neither of the two strings must be NULL.
478 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
479 const xmlChar *name, int len, int seed)
481 unsigned long value = (unsigned long) seed;
484 value += 30 * (unsigned long) ':';
486 value += 30 * (*prefix);
489 int offset = len - (plen + 1 + 1);
491 offset = len - (10 + 1);
492 value += name[offset];
498 case 10: value += prefix[9];
499 case 9: value += prefix[8];
500 case 8: value += prefix[7];
501 case 7: value += prefix[6];
502 case 6: value += prefix[5];
503 case 5: value += prefix[4];
504 case 4: value += prefix[3];
505 case 3: value += prefix[2];
506 case 2: value += prefix[1];
507 case 1: value += prefix[0];
512 value += (unsigned long) ':';
516 case 10: value += name[9];
517 case 9: value += name[8];
518 case 8: value += name[7];
519 case 7: value += name[6];
520 case 6: value += name[5];
521 case 5: value += name[4];
522 case 4: value += name[3];
523 case 3: value += name[2];
524 case 2: value += name[1];
525 case 1: value += name[0];
534 * Create a new dictionary
536 * Returns the newly created dictionnary, or NULL if an error occured.
539 xmlDictCreate(void) {
542 if (!xmlDictInitialized)
543 if (!__xmlInitializeDict())
546 #ifdef DICT_DEBUG_PATTERNS
547 fprintf(stderr, "C");
550 dict = xmlMalloc(sizeof(xmlDict));
552 dict->ref_counter = 1;
555 dict->size = MIN_DICT_SIZE;
557 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
558 dict->strings = NULL;
559 dict->subdict = NULL;
561 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
562 #ifdef DICT_RANDOMIZATION
563 dict->seed = __xmlRandom();
576 * @sub: an existing dictionnary
578 * Create a new dictionary, inheriting strings from the read-only
579 * dictionnary @sub. On lookup, strings are first searched in the
580 * new dictionnary, then in @sub, and if not found are created in the
583 * Returns the newly created dictionnary, or NULL if an error occured.
586 xmlDictCreateSub(xmlDictPtr sub) {
587 xmlDictPtr dict = xmlDictCreate();
589 if ((dict != NULL) && (sub != NULL)) {
590 #ifdef DICT_DEBUG_PATTERNS
591 fprintf(stderr, "R");
593 dict->seed = sub->seed;
595 xmlDictReference(dict->subdict);
602 * @dict: the dictionnary
604 * Increment the reference counter of a dictionary
606 * Returns 0 in case of success and -1 in case of error
609 xmlDictReference(xmlDictPtr dict) {
610 if (!xmlDictInitialized)
611 if (!__xmlInitializeDict())
614 if (dict == NULL) return -1;
615 xmlRMutexLock(xmlDictMutex);
617 xmlRMutexUnlock(xmlDictMutex);
623 * @dict: the dictionnary
624 * @size: the new size of the dictionnary
626 * resize the dictionnary
628 * Returns 0 in case of success, -1 in case of failure
631 xmlDictGrow(xmlDictPtr dict, size_t size) {
632 unsigned long key, okey;
634 xmlDictEntryPtr iter, next;
635 struct _xmlDictEntry *olddict;
637 unsigned long nbElem = 0;
649 #ifdef DICT_DEBUG_PATTERNS
650 fprintf(stderr, "*");
653 oldsize = dict->size;
654 olddict = dict->dict;
657 if (oldsize == MIN_DICT_SIZE)
660 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
661 if (dict->dict == NULL) {
662 dict->dict = olddict;
665 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
668 /* If the two loops are merged, there would be situations where
669 a new entry needs to allocated and data copied into it from
670 the main dict. It is nicer to run through the array twice, first
671 copying all the elements in the main array (less probability of
672 allocate) and then the rest, so we only free in the second loop.
674 for (i = 0; i < oldsize; i++) {
675 if (olddict[i].valid == 0)
679 okey = olddict[i].okey;
681 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
682 key = okey % dict->size;
684 if (dict->dict[key].valid == 0) {
685 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
686 dict->dict[key].next = NULL;
687 dict->dict[key].okey = okey;
689 xmlDictEntryPtr entry;
691 entry = xmlMalloc(sizeof(xmlDictEntry));
693 entry->name = olddict[i].name;
694 entry->len = olddict[i].len;
696 entry->next = dict->dict[key].next;
698 dict->dict[key].next = entry;
701 * we don't have much ways to alert from herei
702 * result is loosing an entry and unicity garantee
712 for (i = 0; i < oldsize; i++) {
713 iter = olddict[i].next;
718 * put back the entry in the new dict
724 okey = xmlDictComputeKey(dict, iter->name, iter->len);
725 key = okey % dict->size;
726 if (dict->dict[key].valid == 0) {
727 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
728 dict->dict[key].next = NULL;
729 dict->dict[key].valid = 1;
730 dict->dict[key].okey = okey;
733 iter->next = dict->dict[key].next;
735 dict->dict[key].next = iter;
749 xmlGenericError(xmlGenericErrorContext,
750 "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
758 * @dict: the dictionnary
760 * Free the hash @dict and its contents. The userdata is
761 * deallocated with @f if provided.
764 xmlDictFree(xmlDictPtr dict) {
766 xmlDictEntryPtr iter;
767 xmlDictEntryPtr next;
769 xmlDictStringsPtr pool, nextp;
774 if (!xmlDictInitialized)
775 if (!__xmlInitializeDict())
778 /* decrement the counter, it may be shared by a parser and docs */
779 xmlRMutexLock(xmlDictMutex);
781 if (dict->ref_counter > 0) {
782 xmlRMutexUnlock(xmlDictMutex);
786 xmlRMutexUnlock(xmlDictMutex);
788 if (dict->subdict != NULL) {
789 xmlDictFree(dict->subdict);
793 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
794 iter = &(dict->dict[i]);
795 if (iter->valid == 0)
809 pool = dict->strings;
810 while (pool != NULL) {
820 * @dict: the dictionnary
821 * @name: the name of the userdata
822 * @len: the length of the name, if -1 it is recomputed
824 * Add the @name to the dictionnary @dict if not present.
826 * Returns the internal copy of the name or NULL in case of internal error
829 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
830 unsigned long key, okey, nbi = 0;
831 xmlDictEntryPtr entry;
832 xmlDictEntryPtr insert;
836 if ((dict == NULL) || (name == NULL))
840 l = strlen((const char *) name);
844 if (((dict->limit > 0) && (l >= dict->limit)) ||
849 * Check for duplicate and insertion location.
851 okey = xmlDictComputeKey(dict, name, l);
852 key = okey % dict->size;
853 if (dict->dict[key].valid == 0) {
856 for (insert = &(dict->dict[key]); insert->next != NULL;
857 insert = insert->next) {
859 if ((insert->okey == okey) && (insert->len == l)) {
860 if (!memcmp(insert->name, name, l))
861 return(insert->name);
864 if ((insert->okey == okey) && (insert->len == l) &&
865 (!xmlStrncmp(insert->name, name, l)))
866 return(insert->name);
871 if ((insert->okey == okey) && (insert->len == l)) {
872 if (!memcmp(insert->name, name, l))
873 return(insert->name);
876 if ((insert->okey == okey) && (insert->len == l) &&
877 (!xmlStrncmp(insert->name, name, l)))
878 return(insert->name);
885 /* we cannot always reuse the same okey for the subdict */
886 if (((dict->size == MIN_DICT_SIZE) &&
887 (dict->subdict->size != MIN_DICT_SIZE)) ||
888 ((dict->size != MIN_DICT_SIZE) &&
889 (dict->subdict->size == MIN_DICT_SIZE)))
890 skey = xmlDictComputeKey(dict->subdict, name, l);
894 key = skey % dict->subdict->size;
895 if (dict->subdict->dict[key].valid != 0) {
898 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
901 if ((tmp->okey == skey) && (tmp->len == l)) {
902 if (!memcmp(tmp->name, name, l))
906 if ((tmp->okey == skey) && (tmp->len == l) &&
907 (!xmlStrncmp(tmp->name, name, l)))
913 if ((tmp->okey == skey) && (tmp->len == l)) {
914 if (!memcmp(tmp->name, name, l))
918 if ((tmp->okey == skey) && (tmp->len == l) &&
919 (!xmlStrncmp(tmp->name, name, l)))
923 key = okey % dict->size;
926 ret = xmlDictAddString(dict, name, l);
929 if (insert == NULL) {
930 entry = &(dict->dict[key]);
932 entry = xmlMalloc(sizeof(xmlDictEntry));
944 insert->next = entry;
948 if ((nbi > MAX_HASH_LEN) &&
949 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
950 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
953 /* Note that entry may have been freed at this point by xmlDictGrow */
960 * @dict: the dictionnary
961 * @name: the name of the userdata
962 * @len: the length of the name, if -1 it is recomputed
964 * Check if the @name exists in the dictionnary @dict.
966 * Returns the internal copy of the name or NULL if not found.
969 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
970 unsigned long key, okey, nbi = 0;
971 xmlDictEntryPtr insert;
974 if ((dict == NULL) || (name == NULL))
978 l = strlen((const char *) name);
981 if (((dict->limit > 0) && (l >= dict->limit)) ||
986 * Check for duplicate and insertion location.
988 okey = xmlDictComputeKey(dict, name, l);
989 key = okey % dict->size;
990 if (dict->dict[key].valid == 0) {
993 for (insert = &(dict->dict[key]); insert->next != NULL;
994 insert = insert->next) {
996 if ((insert->okey == okey) && (insert->len == l)) {
997 if (!memcmp(insert->name, name, l))
998 return(insert->name);
1001 if ((insert->okey == okey) && (insert->len == l) &&
1002 (!xmlStrncmp(insert->name, name, l)))
1003 return(insert->name);
1008 if ((insert->okey == okey) && (insert->len == l)) {
1009 if (!memcmp(insert->name, name, l))
1010 return(insert->name);
1013 if ((insert->okey == okey) && (insert->len == l) &&
1014 (!xmlStrncmp(insert->name, name, l)))
1015 return(insert->name);
1019 if (dict->subdict) {
1022 /* we cannot always reuse the same okey for the subdict */
1023 if (((dict->size == MIN_DICT_SIZE) &&
1024 (dict->subdict->size != MIN_DICT_SIZE)) ||
1025 ((dict->size != MIN_DICT_SIZE) &&
1026 (dict->subdict->size == MIN_DICT_SIZE)))
1027 skey = xmlDictComputeKey(dict->subdict, name, l);
1031 key = skey % dict->subdict->size;
1032 if (dict->subdict->dict[key].valid != 0) {
1033 xmlDictEntryPtr tmp;
1035 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1038 if ((tmp->okey == skey) && (tmp->len == l)) {
1039 if (!memcmp(tmp->name, name, l))
1043 if ((tmp->okey == skey) && (tmp->len == l) &&
1044 (!xmlStrncmp(tmp->name, name, l)))
1050 if ((tmp->okey == skey) && (tmp->len == l)) {
1051 if (!memcmp(tmp->name, name, l))
1055 if ((tmp->okey == skey) && (tmp->len == l) &&
1056 (!xmlStrncmp(tmp->name, name, l)))
1068 * @dict: the dictionnary
1069 * @prefix: the prefix
1072 * Add the QName @prefix:@name to the hash @dict if not present.
1074 * Returns the internal copy of the QName or NULL in case of internal error
1077 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1078 unsigned long okey, key, nbi = 0;
1079 xmlDictEntryPtr entry;
1080 xmlDictEntryPtr insert;
1082 unsigned int len, plen, l;
1084 if ((dict == NULL) || (name == NULL))
1087 return(xmlDictLookup(dict, name, -1));
1089 l = len = strlen((const char *) name);
1090 plen = strlen((const char *) prefix);
1094 * Check for duplicate and insertion location.
1096 okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1097 key = okey % dict->size;
1098 if (dict->dict[key].valid == 0) {
1101 for (insert = &(dict->dict[key]); insert->next != NULL;
1102 insert = insert->next) {
1103 if ((insert->okey == okey) && (insert->len == len) &&
1104 (xmlStrQEqual(prefix, name, insert->name)))
1105 return(insert->name);
1108 if ((insert->okey == okey) && (insert->len == len) &&
1109 (xmlStrQEqual(prefix, name, insert->name)))
1110 return(insert->name);
1113 if (dict->subdict) {
1116 /* we cannot always reuse the same okey for the subdict */
1117 if (((dict->size == MIN_DICT_SIZE) &&
1118 (dict->subdict->size != MIN_DICT_SIZE)) ||
1119 ((dict->size != MIN_DICT_SIZE) &&
1120 (dict->subdict->size == MIN_DICT_SIZE)))
1121 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1125 key = skey % dict->subdict->size;
1126 if (dict->subdict->dict[key].valid != 0) {
1127 xmlDictEntryPtr tmp;
1128 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1130 if ((tmp->okey == skey) && (tmp->len == len) &&
1131 (xmlStrQEqual(prefix, name, tmp->name)))
1135 if ((tmp->okey == skey) && (tmp->len == len) &&
1136 (xmlStrQEqual(prefix, name, tmp->name)))
1139 key = okey % dict->size;
1142 ret = xmlDictAddQString(dict, prefix, plen, name, l);
1145 if (insert == NULL) {
1146 entry = &(dict->dict[key]);
1148 entry = xmlMalloc(sizeof(xmlDictEntry));
1159 insert->next = entry;
1163 if ((nbi > MAX_HASH_LEN) &&
1164 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1165 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1166 /* Note that entry may have been freed at this point by xmlDictGrow */
1173 * @dict: the dictionnary
1176 * check if a string is owned by the disctionary
1178 * Returns 1 if true, 0 if false and -1 in case of error
1179 * -1 in case of error
1182 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1183 xmlDictStringsPtr pool;
1185 if ((dict == NULL) || (str == NULL))
1187 pool = dict->strings;
1188 while (pool != NULL) {
1189 if ((str >= &pool->array[0]) && (str <= pool->free))
1194 return(xmlDictOwns(dict->subdict, str));
1200 * @dict: the dictionnary
1202 * Query the number of elements installed in the hash @dict.
1204 * Returns the number of elements in the dictionnary or
1205 * -1 in case of error
1208 xmlDictSize(xmlDictPtr dict) {
1212 return(dict->nbElems + dict->subdict->nbElems);
1213 return(dict->nbElems);
1218 * @dict: the dictionnary
1219 * @limit: the limit in bytes
1221 * Set a size limit for the dictionary
1224 * Returns the previous limit of the dictionary or 0
1227 xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1233 dict->limit = limit;
1239 * @dict: the dictionnary
1241 * Get how much memory is used by a dictionary for strings
1244 * Returns the amount of strings allocated
1247 xmlDictGetUsage(xmlDictPtr dict) {
1248 xmlDictStringsPtr pool;
1253 pool = dict->strings;
1254 while (pool != NULL) {
1255 limit += pool->size;
1262 #include "elfgcchack.h"