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)
52typedef 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 */
92typedef struct _xmlDictEntry xmlDictEntry;
93typedef xmlDictEntry *xmlDictEntryPtr;
94struct _xmlDictEntry {
95    struct _xmlDictEntry *next;
96    const xmlChar *name;
97    unsigned int len;
98    int valid;
99    unsigned long okey;
100};
101
102typedef struct _xmlDictStrings xmlDictStrings;
103typedef xmlDictStrings *xmlDictStringsPtr;
104struct _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 */
115struct _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 */
134static xmlRMutexPtr xmlDictMutex = NULL;
135
136/*
137 * Whether the dictionary mutex was initialized.
138 */
139static int xmlDictInitialized = 0;
140
141#ifdef DICT_RANDOMIZATION
142#ifdef HAVE_RAND_R
143/*
144 * Internal data for random function, protected by xmlDictMutex
145 */
146static 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 */
159int 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 */
175int __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
197int __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 */
220void
221xmlDictCleanup(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 */
240static const xmlChar *
241xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
242    xmlDictStringsPtr pool;
243    const xmlChar *ret;
244    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
245    size_t limit = 0;
246
247#ifdef DICT_DEBUG_PATTERNS
248    fprintf(stderr, "-");
249#endif
250    pool = dict->strings;
251    while (pool != NULL) {
252	if (pool->end - pool->free > namelen)
253	    goto found_pool;
254	if (pool->size > size) size = pool->size;
255        limit += pool->size;
256	pool = pool->next;
257    }
258    /*
259     * Not found, need to allocate
260     */
261    if (pool == NULL) {
262        if ((dict->limit > 0) && (limit > dict->limit)) {
263            return(NULL);
264        }
265
266        if (size == 0) size = 1000;
267	else size *= 4; /* exponential growth */
268        if (size < 4 * namelen)
269	    size = 4 * namelen; /* just in case ! */
270	pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
271	if (pool == NULL)
272	    return(NULL);
273	pool->size = size;
274	pool->nbStrings = 0;
275	pool->free = &pool->array[0];
276	pool->end = &pool->array[size];
277	pool->next = dict->strings;
278	dict->strings = pool;
279#ifdef DICT_DEBUG_PATTERNS
280        fprintf(stderr, "+");
281#endif
282    }
283found_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 */
304static const xmlChar *
305xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
306                 const xmlChar *name, unsigned int namelen)
307{
308    xmlDictStringsPtr pool;
309    const xmlChar *ret;
310    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
311    size_t limit = 0;
312
313    if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
314
315#ifdef DICT_DEBUG_PATTERNS
316    fprintf(stderr, "=");
317#endif
318    pool = dict->strings;
319    while (pool != NULL) {
320	if (pool->end - pool->free > namelen + plen + 1)
321	    goto found_pool;
322	if (pool->size > size) size = pool->size;
323        limit += pool->size;
324	pool = pool->next;
325    }
326    /*
327     * Not found, need to allocate
328     */
329    if (pool == NULL) {
330        if ((dict->limit > 0) && (limit > dict->limit)) {
331            return(NULL);
332        }
333
334        if (size == 0) size = 1000;
335	else size *= 4; /* exponential growth */
336        if (size < 4 * (namelen + plen + 1))
337	    size = 4 * (namelen + plen + 1); /* just in case ! */
338	pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
339	if (pool == NULL)
340	    return(NULL);
341	pool->size = size;
342	pool->nbStrings = 0;
343	pool->free = &pool->array[0];
344	pool->end = &pool->array[size];
345	pool->next = dict->strings;
346	dict->strings = pool;
347#ifdef DICT_DEBUG_PATTERNS
348        fprintf(stderr, "+");
349#endif
350    }
351found_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
374static uint32_t
375xmlDictComputeBigKey(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 */
406static unsigned long
407xmlDictComputeBigQKey(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 */
443static unsigned long
444xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
445    unsigned long value = seed;
446
447    if (name == NULL) return(0);
448    value = *name;
449    value <<= 5;
450    if (namelen > 10) {
451        value += name[namelen - 1];
452        namelen = 10;
453    }
454    switch (namelen) {
455        case 10: value += name[9];
456        case 9: value += name[8];
457        case 8: value += name[7];
458        case 7: value += name[6];
459        case 6: value += name[5];
460        case 5: value += name[4];
461        case 4: value += name[3];
462        case 3: value += name[2];
463        case 2: value += name[1];
464        default: break;
465    }
466    return(value);
467}
468
469/*
470 * xmlDictComputeFastQKey:
471 *
472 * Calculate a hash key for two strings using a fast hash function
473 * that works well for low hash table fill.
474 *
475 * Neither of the two strings must be NULL.
476 */
477static unsigned long
478xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
479                       const xmlChar *name, int len, int seed)
480{
481    unsigned long value = (unsigned long) seed;
482
483    if (plen == 0)
484	value += 30 * (unsigned long) ':';
485    else
486	value += 30 * (*prefix);
487
488    if (len > 10) {
489        int offset = len - (plen + 1 + 1);
490	if (offset < 0)
491	    offset = len - (10 + 1);
492	value += name[offset];
493        len = 10;
494	if (plen > 10)
495	    plen = 10;
496    }
497    switch (plen) {
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];
508        default: break;
509    }
510    len -= plen;
511    if (len > 0) {
512        value += (unsigned long) ':';
513	len--;
514    }
515    switch (len) {
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];
526        default: break;
527    }
528    return(value);
529}
530
531/**
532 * xmlDictCreate:
533 *
534 * Create a new dictionary
535 *
536 * Returns the newly created dictionary, or NULL if an error occured.
537 */
538xmlDictPtr
539xmlDictCreate(void) {
540    xmlDictPtr dict;
541
542    if (!xmlDictInitialized)
543        if (!__xmlInitializeDict())
544            return(NULL);
545
546#ifdef DICT_DEBUG_PATTERNS
547    fprintf(stderr, "C");
548#endif
549
550    dict = xmlMalloc(sizeof(xmlDict));
551    if (dict) {
552        dict->ref_counter = 1;
553        dict->limit = 0;
554
555        dict->size = MIN_DICT_SIZE;
556	dict->nbElems = 0;
557        dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
558	dict->strings = NULL;
559	dict->subdict = NULL;
560        if (dict->dict) {
561	    memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
562#ifdef DICT_RANDOMIZATION
563            dict->seed = __xmlRandom();
564#else
565            dict->seed = 0;
566#endif
567	    return(dict);
568        }
569        xmlFree(dict);
570    }
571    return(NULL);
572}
573
574/**
575 * xmlDictCreateSub:
576 * @sub: an existing dictionary
577 *
578 * Create a new dictionary, inheriting strings from the read-only
579 * dictionary @sub. On lookup, strings are first searched in the
580 * new dictionary, then in @sub, and if not found are created in the
581 * new dictionary.
582 *
583 * Returns the newly created dictionary, or NULL if an error occured.
584 */
585xmlDictPtr
586xmlDictCreateSub(xmlDictPtr sub) {
587    xmlDictPtr dict = xmlDictCreate();
588
589    if ((dict != NULL) && (sub != NULL)) {
590#ifdef DICT_DEBUG_PATTERNS
591        fprintf(stderr, "R");
592#endif
593        dict->seed = sub->seed;
594        dict->subdict = sub;
595	xmlDictReference(dict->subdict);
596    }
597    return(dict);
598}
599
600/**
601 * xmlDictReference:
602 * @dict: the dictionary
603 *
604 * Increment the reference counter of a dictionary
605 *
606 * Returns 0 in case of success and -1 in case of error
607 */
608int
609xmlDictReference(xmlDictPtr dict) {
610    if (!xmlDictInitialized)
611        if (!__xmlInitializeDict())
612            return(-1);
613
614    if (dict == NULL) return -1;
615    xmlRMutexLock(xmlDictMutex);
616    dict->ref_counter++;
617    xmlRMutexUnlock(xmlDictMutex);
618    return(0);
619}
620
621/**
622 * xmlDictGrow:
623 * @dict: the dictionary
624 * @size: the new size of the dictionary
625 *
626 * resize the dictionary
627 *
628 * Returns 0 in case of success, -1 in case of failure
629 */
630static int
631xmlDictGrow(xmlDictPtr dict, size_t size) {
632    unsigned long key, okey;
633    size_t oldsize, i;
634    xmlDictEntryPtr iter, next;
635    struct _xmlDictEntry *olddict;
636#ifdef DEBUG_GROW
637    unsigned long nbElem = 0;
638#endif
639    int ret = 0;
640    int keep_keys = 1;
641
642    if (dict == NULL)
643	return(-1);
644    if (size < 8)
645        return(-1);
646    if (size > 8 * 2048)
647	return(-1);
648
649#ifdef DICT_DEBUG_PATTERNS
650    fprintf(stderr, "*");
651#endif
652
653    oldsize = dict->size;
654    olddict = dict->dict;
655    if (olddict == NULL)
656        return(-1);
657    if (oldsize == MIN_DICT_SIZE)
658        keep_keys = 0;
659
660    dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
661    if (dict->dict == NULL) {
662	dict->dict = olddict;
663	return(-1);
664    }
665    memset(dict->dict, 0, size * sizeof(xmlDictEntry));
666    dict->size = size;
667
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.
673    */
674    for (i = 0; i < oldsize; i++) {
675	if (olddict[i].valid == 0)
676	    continue;
677
678	if (keep_keys)
679	    okey = olddict[i].okey;
680	else
681	    okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
682	key = okey % dict->size;
683
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;
688	} else {
689	    xmlDictEntryPtr entry;
690
691	    entry = xmlMalloc(sizeof(xmlDictEntry));
692	    if (entry != NULL) {
693		entry->name = olddict[i].name;
694		entry->len = olddict[i].len;
695		entry->okey = okey;
696		entry->next = dict->dict[key].next;
697		entry->valid = 1;
698		dict->dict[key].next = entry;
699	    } else {
700	        /*
701		 * we don't have much ways to alert from herei
702		 * result is loosing an entry and unicity garantee
703		 */
704	        ret = -1;
705	    }
706	}
707#ifdef DEBUG_GROW
708	nbElem++;
709#endif
710    }
711
712    for (i = 0; i < oldsize; i++) {
713	iter = olddict[i].next;
714	while (iter) {
715	    next = iter->next;
716
717	    /*
718	     * put back the entry in the new dict
719	     */
720
721	    if (keep_keys)
722		okey = iter->okey;
723	    else
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;
731		xmlFree(iter);
732	    } else {
733		iter->next = dict->dict[key].next;
734		iter->okey = okey;
735		dict->dict[key].next = iter;
736	    }
737
738#ifdef DEBUG_GROW
739	    nbElem++;
740#endif
741
742	    iter = next;
743	}
744    }
745
746    xmlFree(olddict);
747
748#ifdef DEBUG_GROW
749    xmlGenericError(xmlGenericErrorContext,
750	    "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
751#endif
752
753    return(ret);
754}
755
756/**
757 * xmlDictFree:
758 * @dict: the dictionary
759 *
760 * Free the hash @dict and its contents. The userdata is
761 * deallocated with @f if provided.
762 */
763void
764xmlDictFree(xmlDictPtr dict) {
765    size_t i;
766    xmlDictEntryPtr iter;
767    xmlDictEntryPtr next;
768    int inside_dict = 0;
769    xmlDictStringsPtr pool, nextp;
770
771    if (dict == NULL)
772	return;
773
774    if (!xmlDictInitialized)
775        if (!__xmlInitializeDict())
776            return;
777
778    /* decrement the counter, it may be shared by a parser and docs */
779    xmlRMutexLock(xmlDictMutex);
780    dict->ref_counter--;
781    if (dict->ref_counter > 0) {
782        xmlRMutexUnlock(xmlDictMutex);
783        return;
784    }
785
786    xmlRMutexUnlock(xmlDictMutex);
787
788    if (dict->subdict != NULL) {
789        xmlDictFree(dict->subdict);
790    }
791
792    if (dict->dict) {
793	for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
794	    iter = &(dict->dict[i]);
795	    if (iter->valid == 0)
796		continue;
797	    inside_dict = 1;
798	    while (iter) {
799		next = iter->next;
800		if (!inside_dict)
801		    xmlFree(iter);
802		dict->nbElems--;
803		inside_dict = 0;
804		iter = next;
805	    }
806	}
807	xmlFree(dict->dict);
808    }
809    pool = dict->strings;
810    while (pool != NULL) {
811        nextp = pool->next;
812	xmlFree(pool);
813	pool = nextp;
814    }
815    xmlFree(dict);
816}
817
818/**
819 * xmlDictLookup:
820 * @dict: the dictionary
821 * @name: the name of the userdata
822 * @len: the length of the name, if -1 it is recomputed
823 *
824 * Add the @name to the dictionary @dict if not present.
825 *
826 * Returns the internal copy of the name or NULL in case of internal error
827 */
828const xmlChar *
829xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
830    unsigned long key, okey, nbi = 0;
831    xmlDictEntryPtr entry;
832    xmlDictEntryPtr insert;
833    const xmlChar *ret;
834    unsigned int l;
835
836    if ((dict == NULL) || (name == NULL))
837	return(NULL);
838
839    if (len < 0)
840        l = strlen((const char *) name);
841    else
842        l = len;
843
844    if (((dict->limit > 0) && (l >= dict->limit)) ||
845        (l > INT_MAX / 2))
846        return(NULL);
847
848    /*
849     * Check for duplicate and insertion location.
850     */
851    okey = xmlDictComputeKey(dict, name, l);
852    key = okey % dict->size;
853    if (dict->dict[key].valid == 0) {
854	insert = NULL;
855    } else {
856	for (insert = &(dict->dict[key]); insert->next != NULL;
857	     insert = insert->next) {
858#ifdef __GNUC__
859	    if ((insert->okey == okey) && (insert->len == l)) {
860		if (!memcmp(insert->name, name, l))
861		    return(insert->name);
862	    }
863#else
864	    if ((insert->okey == okey) && (insert->len == l) &&
865	        (!xmlStrncmp(insert->name, name, l)))
866		return(insert->name);
867#endif
868	    nbi++;
869	}
870#ifdef __GNUC__
871	if ((insert->okey == okey) && (insert->len == l)) {
872	    if (!memcmp(insert->name, name, l))
873		return(insert->name);
874	}
875#else
876	if ((insert->okey == okey) && (insert->len == l) &&
877	    (!xmlStrncmp(insert->name, name, l)))
878	    return(insert->name);
879#endif
880    }
881
882    if (dict->subdict) {
883        unsigned long skey;
884
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);
891	else
892	    skey = okey;
893
894	key = skey % dict->subdict->size;
895	if (dict->subdict->dict[key].valid != 0) {
896	    xmlDictEntryPtr tmp;
897
898	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
899		 tmp = tmp->next) {
900#ifdef __GNUC__
901		if ((tmp->okey == skey) && (tmp->len == l)) {
902		    if (!memcmp(tmp->name, name, l))
903			return(tmp->name);
904		}
905#else
906		if ((tmp->okey == skey) && (tmp->len == l) &&
907		    (!xmlStrncmp(tmp->name, name, l)))
908		    return(tmp->name);
909#endif
910		nbi++;
911	    }
912#ifdef __GNUC__
913	    if ((tmp->okey == skey) && (tmp->len == l)) {
914		if (!memcmp(tmp->name, name, l))
915		    return(tmp->name);
916	    }
917#else
918	    if ((tmp->okey == skey) && (tmp->len == l) &&
919		(!xmlStrncmp(tmp->name, name, l)))
920		return(tmp->name);
921#endif
922	}
923	key = okey % dict->size;
924    }
925
926    ret = xmlDictAddString(dict, name, l);
927    if (ret == NULL)
928        return(NULL);
929    if (insert == NULL) {
930	entry = &(dict->dict[key]);
931    } else {
932	entry = xmlMalloc(sizeof(xmlDictEntry));
933	if (entry == NULL)
934	     return(NULL);
935    }
936    entry->name = ret;
937    entry->len = l;
938    entry->next = NULL;
939    entry->valid = 1;
940    entry->okey = okey;
941
942
943    if (insert != NULL)
944	insert->next = entry;
945
946    dict->nbElems++;
947
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)
951	    return(NULL);
952    }
953    /* Note that entry may have been freed at this point by xmlDictGrow */
954
955    return(ret);
956}
957
958/**
959 * xmlDictExists:
960 * @dict: the dictionary
961 * @name: the name of the userdata
962 * @len: the length of the name, if -1 it is recomputed
963 *
964 * Check if the @name exists in the dictionary @dict.
965 *
966 * Returns the internal copy of the name or NULL if not found.
967 */
968const xmlChar *
969xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
970    unsigned long key, okey, nbi = 0;
971    xmlDictEntryPtr insert;
972    unsigned int l;
973
974    if ((dict == NULL) || (name == NULL))
975	return(NULL);
976
977    if (len < 0)
978        l = strlen((const char *) name);
979    else
980        l = len;
981    if (((dict->limit > 0) && (l >= dict->limit)) ||
982        (l > INT_MAX / 2))
983        return(NULL);
984
985    /*
986     * Check for duplicate and insertion location.
987     */
988    okey = xmlDictComputeKey(dict, name, l);
989    key = okey % dict->size;
990    if (dict->dict[key].valid == 0) {
991	insert = NULL;
992    } else {
993	for (insert = &(dict->dict[key]); insert->next != NULL;
994	     insert = insert->next) {
995#ifdef __GNUC__
996	    if ((insert->okey == okey) && (insert->len == l)) {
997		if (!memcmp(insert->name, name, l))
998		    return(insert->name);
999	    }
1000#else
1001	    if ((insert->okey == okey) && (insert->len == l) &&
1002	        (!xmlStrncmp(insert->name, name, l)))
1003		return(insert->name);
1004#endif
1005	    nbi++;
1006	}
1007#ifdef __GNUC__
1008	if ((insert->okey == okey) && (insert->len == l)) {
1009	    if (!memcmp(insert->name, name, l))
1010		return(insert->name);
1011	}
1012#else
1013	if ((insert->okey == okey) && (insert->len == l) &&
1014	    (!xmlStrncmp(insert->name, name, l)))
1015	    return(insert->name);
1016#endif
1017    }
1018
1019    if (dict->subdict) {
1020        unsigned long skey;
1021
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);
1028	else
1029	    skey = okey;
1030
1031	key = skey % dict->subdict->size;
1032	if (dict->subdict->dict[key].valid != 0) {
1033	    xmlDictEntryPtr tmp;
1034
1035	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1036		 tmp = tmp->next) {
1037#ifdef __GNUC__
1038		if ((tmp->okey == skey) && (tmp->len == l)) {
1039		    if (!memcmp(tmp->name, name, l))
1040			return(tmp->name);
1041		}
1042#else
1043		if ((tmp->okey == skey) && (tmp->len == l) &&
1044		    (!xmlStrncmp(tmp->name, name, l)))
1045		    return(tmp->name);
1046#endif
1047		nbi++;
1048	    }
1049#ifdef __GNUC__
1050	    if ((tmp->okey == skey) && (tmp->len == l)) {
1051		if (!memcmp(tmp->name, name, l))
1052		    return(tmp->name);
1053	    }
1054#else
1055	    if ((tmp->okey == skey) && (tmp->len == l) &&
1056		(!xmlStrncmp(tmp->name, name, l)))
1057		return(tmp->name);
1058#endif
1059	}
1060    }
1061
1062    /* not found */
1063    return(NULL);
1064}
1065
1066/**
1067 * xmlDictQLookup:
1068 * @dict: the dictionary
1069 * @prefix: the prefix
1070 * @name: the name
1071 *
1072 * Add the QName @prefix:@name to the hash @dict if not present.
1073 *
1074 * Returns the internal copy of the QName or NULL in case of internal error
1075 */
1076const xmlChar *
1077xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1078    unsigned long okey, key, nbi = 0;
1079    xmlDictEntryPtr entry;
1080    xmlDictEntryPtr insert;
1081    const xmlChar *ret;
1082    unsigned int len, plen, l;
1083
1084    if ((dict == NULL) || (name == NULL))
1085	return(NULL);
1086    if (prefix == NULL)
1087        return(xmlDictLookup(dict, name, -1));
1088
1089    l = len = strlen((const char *) name);
1090    plen = strlen((const char *) prefix);
1091    len += 1 + plen;
1092
1093    /*
1094     * Check for duplicate and insertion location.
1095     */
1096    okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1097    key = okey % dict->size;
1098    if (dict->dict[key].valid == 0) {
1099	insert = NULL;
1100    } else {
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);
1106	    nbi++;
1107	}
1108	if ((insert->okey == okey) && (insert->len == len) &&
1109	    (xmlStrQEqual(prefix, name, insert->name)))
1110	    return(insert->name);
1111    }
1112
1113    if (dict->subdict) {
1114        unsigned long skey;
1115
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);
1122	else
1123	    skey = okey;
1124
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;
1129		 tmp = tmp->next) {
1130		if ((tmp->okey == skey) && (tmp->len == len) &&
1131		    (xmlStrQEqual(prefix, name, tmp->name)))
1132		    return(tmp->name);
1133		nbi++;
1134	    }
1135	    if ((tmp->okey == skey) && (tmp->len == len) &&
1136		(xmlStrQEqual(prefix, name, tmp->name)))
1137		return(tmp->name);
1138	}
1139	key = okey % dict->size;
1140    }
1141
1142    ret = xmlDictAddQString(dict, prefix, plen, name, l);
1143    if (ret == NULL)
1144        return(NULL);
1145    if (insert == NULL) {
1146	entry = &(dict->dict[key]);
1147    } else {
1148	entry = xmlMalloc(sizeof(xmlDictEntry));
1149	if (entry == NULL)
1150	     return(NULL);
1151    }
1152    entry->name = ret;
1153    entry->len = len;
1154    entry->next = NULL;
1155    entry->valid = 1;
1156    entry->okey = okey;
1157
1158    if (insert != NULL)
1159	insert->next = entry;
1160
1161    dict->nbElems++;
1162
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 */
1167
1168    return(ret);
1169}
1170
1171/**
1172 * xmlDictOwns:
1173 * @dict: the dictionary
1174 * @str: the string
1175 *
1176 * check if a string is owned by the disctionary
1177 *
1178 * Returns 1 if true, 0 if false and -1 in case of error
1179 * -1 in case of error
1180 */
1181int
1182xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1183    xmlDictStringsPtr pool;
1184
1185    if ((dict == NULL) || (str == NULL))
1186	return(-1);
1187    pool = dict->strings;
1188    while (pool != NULL) {
1189        if ((str >= &pool->array[0]) && (str <= pool->free))
1190	    return(1);
1191	pool = pool->next;
1192    }
1193    if (dict->subdict)
1194        return(xmlDictOwns(dict->subdict, str));
1195    return(0);
1196}
1197
1198/**
1199 * xmlDictSize:
1200 * @dict: the dictionary
1201 *
1202 * Query the number of elements installed in the hash @dict.
1203 *
1204 * Returns the number of elements in the dictionary or
1205 * -1 in case of error
1206 */
1207int
1208xmlDictSize(xmlDictPtr dict) {
1209    if (dict == NULL)
1210	return(-1);
1211    if (dict->subdict)
1212        return(dict->nbElems + dict->subdict->nbElems);
1213    return(dict->nbElems);
1214}
1215
1216/**
1217 * xmlDictSetLimit:
1218 * @dict: the dictionary
1219 * @limit: the limit in bytes
1220 *
1221 * Set a size limit for the dictionary
1222 * Added in 2.9.0
1223 *
1224 * Returns the previous limit of the dictionary or 0
1225 */
1226size_t
1227xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1228    size_t ret;
1229
1230    if (dict == NULL)
1231	return(0);
1232    ret = dict->limit;
1233    dict->limit = limit;
1234    return(ret);
1235}
1236
1237/**
1238 * xmlDictGetUsage:
1239 * @dict: the dictionary
1240 *
1241 * Get how much memory is used by a dictionary for strings
1242 * Added in 2.9.0
1243 *
1244 * Returns the amount of strings allocated
1245 */
1246size_t
1247xmlDictGetUsage(xmlDictPtr dict) {
1248    xmlDictStringsPtr pool;
1249    size_t limit = 0;
1250
1251    if (dict == NULL)
1252	return(0);
1253    pool = dict->strings;
1254    while (pool != NULL) {
1255        limit += pool->size;
1256	pool = pool->next;
1257    }
1258    return(limit);
1259}
1260
1261#define bottom_dict
1262#include "elfgcchack.h"
1263