1/*
2 * dict.c: dictionary of reusable strings, just used to avoid allocation
3 *         and freeing operations.
4 *
5 * Copyright (C) 2003 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 <string.h>
23#ifdef HAVE_STDINT_H
24#include <stdint.h>
25#else
26#ifdef HAVE_INTTYPES_H
27#include <inttypes.h>
28#elif defined(WIN32)
29typedef unsigned __int32 uint32_t;
30#endif
31#endif
32#include <libxml/tree.h>
33#include <libxml/dict.h>
34#include <libxml/xmlmemory.h>
35#include <libxml/xmlerror.h>
36#include <libxml/globals.h>
37
38/* #define DEBUG_GROW */
39/* #define DICT_DEBUG_PATTERNS */
40
41#define MAX_HASH_LEN 3
42#define MIN_DICT_SIZE 128
43#define MAX_DICT_HASH 8 * 2048
44#define WITH_BIG_KEY
45
46#ifdef WITH_BIG_KEY
47#define xmlDictComputeKey(dict, name, len)			\
48    (((dict)->size == MIN_DICT_SIZE) ?				\
49     xmlDictComputeFastKey(name, len) :				\
50     xmlDictComputeBigKey(name, len))
51
52#define xmlDictComputeQKey(dict, prefix, plen, name, len)	\
53    (((prefix) == NULL) ?					\
54      (xmlDictComputeKey(dict, name, len)) :			\
55      (((dict)->size == MIN_DICT_SIZE) ?			\
56       xmlDictComputeFastQKey(prefix, plen, name, len) :	\
57       xmlDictComputeBigQKey(prefix, plen, name, len)))
58
59#else /* !WITH_BIG_KEY */
60#define xmlDictComputeKey(dict, name, len)			\
61        xmlDictComputeFastKey(name, len)
62#define xmlDictComputeQKey(dict, prefix, plen, name, len)	\
63        xmlDictComputeFastQKey(prefix, plen, name, len)
64#endif /* WITH_BIG_KEY */
65
66/*
67 * An entry in the dictionnary
68 */
69typedef struct _xmlDictEntry xmlDictEntry;
70typedef xmlDictEntry *xmlDictEntryPtr;
71struct _xmlDictEntry {
72    struct _xmlDictEntry *next;
73    const xmlChar *name;
74    int len;
75    int valid;
76    unsigned long okey;
77};
78
79typedef struct _xmlDictStrings xmlDictStrings;
80typedef xmlDictStrings *xmlDictStringsPtr;
81struct _xmlDictStrings {
82    xmlDictStringsPtr next;
83    xmlChar *free;
84    xmlChar *end;
85    int size;
86    int nbStrings;
87    xmlChar array[1];
88};
89/*
90 * The entire dictionnary
91 */
92struct _xmlDict {
93    int ref_counter;
94
95    struct _xmlDictEntry *dict;
96    int size;
97    int nbElems;
98    xmlDictStringsPtr strings;
99
100    struct _xmlDict *subdict;
101};
102
103/*
104 * A mutex for modifying the reference counter for shared
105 * dictionaries.
106 */
107static xmlRMutexPtr xmlDictMutex = NULL;
108
109/*
110 * Whether the dictionary mutex was initialized.
111 */
112static int xmlDictInitialized = 0;
113
114/**
115 * xmlInitializeDict:
116 *
117 * Do the dictionary mutex initialization.
118 * this function is not thread safe, initialization should
119 * preferably be done once at startup
120 */
121static int xmlInitializeDict(void) {
122    if (xmlDictInitialized)
123        return(1);
124
125    if ((xmlDictMutex = xmlNewRMutex()) == NULL)
126        return(0);
127
128    xmlDictInitialized = 1;
129    return(1);
130}
131
132/**
133 * xmlDictCleanup:
134 *
135 * Free the dictionary mutex.
136 */
137void
138xmlDictCleanup(void) {
139    if (!xmlDictInitialized)
140        return;
141
142    xmlFreeRMutex(xmlDictMutex);
143
144    xmlDictInitialized = 0;
145}
146
147/*
148 * xmlDictAddString:
149 * @dict: the dictionnary
150 * @name: the name of the userdata
151 * @len: the length of the name, if -1 it is recomputed
152 *
153 * Add the string to the array[s]
154 *
155 * Returns the pointer of the local string, or NULL in case of error.
156 */
157static const xmlChar *
158xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) {
159    xmlDictStringsPtr pool;
160    const xmlChar *ret;
161    int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
162
163#ifdef DICT_DEBUG_PATTERNS
164    fprintf(stderr, "-");
165#endif
166    pool = dict->strings;
167    while (pool != NULL) {
168	if (pool->end - pool->free > namelen)
169	    goto found_pool;
170	if (pool->size > size) size = pool->size;
171	pool = pool->next;
172    }
173    /*
174     * Not found, need to allocate
175     */
176    if (pool == NULL) {
177        if (size == 0) size = 1000;
178	else size *= 4; /* exponential growth */
179        if (size < 4 * namelen)
180	    size = 4 * namelen; /* just in case ! */
181	pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
182	if (pool == NULL)
183	    return(NULL);
184	pool->size = size;
185	pool->nbStrings = 0;
186	pool->free = &pool->array[0];
187	pool->end = &pool->array[size];
188	pool->next = dict->strings;
189	dict->strings = pool;
190#ifdef DICT_DEBUG_PATTERNS
191        fprintf(stderr, "+");
192#endif
193    }
194found_pool:
195    ret = pool->free;
196    memcpy(pool->free, name, namelen);
197    pool->free += namelen;
198    *(pool->free++) = 0;
199    pool->nbStrings++;
200    return(ret);
201}
202
203/*
204 * xmlDictAddQString:
205 * @dict: the dictionnary
206 * @prefix: the prefix of the userdata
207 * @plen: the prefix length
208 * @name: the name of the userdata
209 * @len: the length of the name, if -1 it is recomputed
210 *
211 * Add the QName to the array[s]
212 *
213 * Returns the pointer of the local string, or NULL in case of error.
214 */
215static const xmlChar *
216xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, int plen,
217                 const xmlChar *name, int namelen)
218{
219    xmlDictStringsPtr pool;
220    const xmlChar *ret;
221    int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
222
223    if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
224
225#ifdef DICT_DEBUG_PATTERNS
226    fprintf(stderr, "=");
227#endif
228    pool = dict->strings;
229    while (pool != NULL) {
230	if (pool->end - pool->free > namelen + plen + 1)
231	    goto found_pool;
232	if (pool->size > size) size = pool->size;
233	pool = pool->next;
234    }
235    /*
236     * Not found, need to allocate
237     */
238    if (pool == NULL) {
239        if (size == 0) size = 1000;
240	else size *= 4; /* exponential growth */
241        if (size < 4 * (namelen + plen + 1))
242	    size = 4 * (namelen + plen + 1); /* just in case ! */
243	pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
244	if (pool == NULL)
245	    return(NULL);
246	pool->size = size;
247	pool->nbStrings = 0;
248	pool->free = &pool->array[0];
249	pool->end = &pool->array[size];
250	pool->next = dict->strings;
251	dict->strings = pool;
252#ifdef DICT_DEBUG_PATTERNS
253        fprintf(stderr, "+");
254#endif
255    }
256found_pool:
257    ret = pool->free;
258    memcpy(pool->free, prefix, plen);
259    pool->free += plen;
260    *(pool->free++) = ':';
261    memcpy(pool->free, name, namelen);
262    pool->free += namelen;
263    *(pool->free++) = 0;
264    pool->nbStrings++;
265    return(ret);
266}
267
268#ifdef WITH_BIG_KEY
269/*
270 * xmlDictComputeBigKey:
271 *
272 * Calculate a hash key using a good hash function that works well for
273 * larger hash table sizes.
274 *
275 * Hash function by "One-at-a-Time Hash" see
276 * http://burtleburtle.net/bob/hash/doobs.html
277 */
278
279static uint32_t
280xmlDictComputeBigKey(const xmlChar* data, int namelen) {
281    uint32_t hash;
282    int i;
283
284    if (namelen <= 0 || data == NULL) return(0);
285
286    hash = 0;
287
288    for (i = 0;i < namelen; i++) {
289        hash += data[i];
290	hash += (hash << 10);
291	hash ^= (hash >> 6);
292    }
293    hash += (hash << 3);
294    hash ^= (hash >> 11);
295    hash += (hash << 15);
296
297    return hash;
298}
299
300/*
301 * xmlDictComputeBigQKey:
302 *
303 * Calculate a hash key for two strings using a good hash function
304 * that works well for larger hash table sizes.
305 *
306 * Hash function by "One-at-a-Time Hash" see
307 * http://burtleburtle.net/bob/hash/doobs.html
308 *
309 * Neither of the two strings must be NULL.
310 */
311static unsigned long
312xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
313                      const xmlChar *name, int len)
314{
315    uint32_t hash;
316    int i;
317
318    hash = 0;
319
320    for (i = 0;i < plen; i++) {
321        hash += prefix[i];
322	hash += (hash << 10);
323	hash ^= (hash >> 6);
324    }
325    hash += ':';
326    hash += (hash << 10);
327    hash ^= (hash >> 6);
328
329    for (i = 0;i < len; i++) {
330        hash += name[i];
331	hash += (hash << 10);
332	hash ^= (hash >> 6);
333    }
334    hash += (hash << 3);
335    hash ^= (hash >> 11);
336    hash += (hash << 15);
337
338    return hash;
339}
340#endif /* WITH_BIG_KEY */
341
342/*
343 * xmlDictComputeFastKey:
344 *
345 * Calculate a hash key using a fast hash function that works well
346 * for low hash table fill.
347 */
348static unsigned long
349xmlDictComputeFastKey(const xmlChar *name, int namelen) {
350    unsigned long value = 0L;
351
352    if (name == NULL) return(0);
353    value = *name;
354    value <<= 5;
355    if (namelen > 10) {
356        value += name[namelen - 1];
357        namelen = 10;
358    }
359    switch (namelen) {
360        case 10: value += name[9];
361        case 9: value += name[8];
362        case 8: value += name[7];
363        case 7: value += name[6];
364        case 6: value += name[5];
365        case 5: value += name[4];
366        case 4: value += name[3];
367        case 3: value += name[2];
368        case 2: value += name[1];
369        default: break;
370    }
371    return(value);
372}
373
374/*
375 * xmlDictComputeFastQKey:
376 *
377 * Calculate a hash key for two strings using a fast hash function
378 * that works well for low hash table fill.
379 *
380 * Neither of the two strings must be NULL.
381 */
382static unsigned long
383xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
384                       const xmlChar *name, int len)
385{
386    unsigned long value = 0L;
387
388    if (plen == 0)
389	value += 30 * (unsigned long) ':';
390    else
391	value += 30 * (*prefix);
392
393    if (len > 10) {
394        value += name[len - (plen + 1 + 1)];
395        len = 10;
396	if (plen > 10)
397	    plen = 10;
398    }
399    switch (plen) {
400        case 10: value += prefix[9];
401        case 9: value += prefix[8];
402        case 8: value += prefix[7];
403        case 7: value += prefix[6];
404        case 6: value += prefix[5];
405        case 5: value += prefix[4];
406        case 4: value += prefix[3];
407        case 3: value += prefix[2];
408        case 2: value += prefix[1];
409        case 1: value += prefix[0];
410        default: break;
411    }
412    len -= plen;
413    if (len > 0) {
414        value += (unsigned long) ':';
415	len--;
416    }
417    switch (len) {
418        case 10: value += name[9];
419        case 9: value += name[8];
420        case 8: value += name[7];
421        case 7: value += name[6];
422        case 6: value += name[5];
423        case 5: value += name[4];
424        case 4: value += name[3];
425        case 3: value += name[2];
426        case 2: value += name[1];
427        case 1: value += name[0];
428        default: break;
429    }
430    return(value);
431}
432
433/**
434 * xmlDictCreate:
435 *
436 * Create a new dictionary
437 *
438 * Returns the newly created dictionnary, or NULL if an error occured.
439 */
440xmlDictPtr
441xmlDictCreate(void) {
442    xmlDictPtr dict;
443
444    if (!xmlDictInitialized)
445        if (!xmlInitializeDict())
446            return(NULL);
447
448#ifdef DICT_DEBUG_PATTERNS
449    fprintf(stderr, "C");
450#endif
451
452    dict = xmlMalloc(sizeof(xmlDict));
453    if (dict) {
454        dict->ref_counter = 1;
455
456        dict->size = MIN_DICT_SIZE;
457	dict->nbElems = 0;
458        dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
459	dict->strings = NULL;
460	dict->subdict = NULL;
461        if (dict->dict) {
462	    memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
463	    return(dict);
464        }
465        xmlFree(dict);
466    }
467    return(NULL);
468}
469
470/**
471 * xmlDictCreateSub:
472 * @sub: an existing dictionnary
473 *
474 * Create a new dictionary, inheriting strings from the read-only
475 * dictionnary @sub. On lookup, strings are first searched in the
476 * new dictionnary, then in @sub, and if not found are created in the
477 * new dictionnary.
478 *
479 * Returns the newly created dictionnary, or NULL if an error occured.
480 */
481xmlDictPtr
482xmlDictCreateSub(xmlDictPtr sub) {
483    xmlDictPtr dict = xmlDictCreate();
484
485    if ((dict != NULL) && (sub != NULL)) {
486#ifdef DICT_DEBUG_PATTERNS
487        fprintf(stderr, "R");
488#endif
489        dict->subdict = sub;
490	xmlDictReference(dict->subdict);
491    }
492    return(dict);
493}
494
495/**
496 * xmlDictReference:
497 * @dict: the dictionnary
498 *
499 * Increment the reference counter of a dictionary
500 *
501 * Returns 0 in case of success and -1 in case of error
502 */
503int
504xmlDictReference(xmlDictPtr dict) {
505    if (!xmlDictInitialized)
506        if (!xmlInitializeDict())
507            return(-1);
508
509    if (dict == NULL) return -1;
510    xmlRMutexLock(xmlDictMutex);
511    dict->ref_counter++;
512    xmlRMutexUnlock(xmlDictMutex);
513    return(0);
514}
515
516/**
517 * xmlDictGrow:
518 * @dict: the dictionnary
519 * @size: the new size of the dictionnary
520 *
521 * resize the dictionnary
522 *
523 * Returns 0 in case of success, -1 in case of failure
524 */
525static int
526xmlDictGrow(xmlDictPtr dict, int size) {
527    unsigned long key, okey;
528    int oldsize, i;
529    xmlDictEntryPtr iter, next;
530    struct _xmlDictEntry *olddict;
531#ifdef DEBUG_GROW
532    unsigned long nbElem = 0;
533#endif
534    int ret = 0;
535    int keep_keys = 1;
536
537    if (dict == NULL)
538	return(-1);
539    if (size < 8)
540        return(-1);
541    if (size > 8 * 2048)
542	return(-1);
543
544#ifdef DICT_DEBUG_PATTERNS
545    fprintf(stderr, "*");
546#endif
547
548    oldsize = dict->size;
549    olddict = dict->dict;
550    if (olddict == NULL)
551        return(-1);
552    if (oldsize == MIN_DICT_SIZE)
553        keep_keys = 0;
554
555    dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
556    if (dict->dict == NULL) {
557	dict->dict = olddict;
558	return(-1);
559    }
560    memset(dict->dict, 0, size * sizeof(xmlDictEntry));
561    dict->size = size;
562
563    /*	If the two loops are merged, there would be situations where
564	a new entry needs to allocated and data copied into it from
565	the main dict. It is nicer to run through the array twice, first
566	copying all the elements in the main array (less probability of
567	allocate) and then the rest, so we only free in the second loop.
568    */
569    for (i = 0; i < oldsize; i++) {
570	if (olddict[i].valid == 0)
571	    continue;
572
573	if (keep_keys)
574	    okey = olddict[i].okey;
575	else
576	    okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
577	key = okey % dict->size;
578
579	if (dict->dict[key].valid == 0) {
580	    memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
581	    dict->dict[key].next = NULL;
582	    dict->dict[key].okey = okey;
583	} else {
584	    xmlDictEntryPtr entry;
585
586	    entry = xmlMalloc(sizeof(xmlDictEntry));
587	    if (entry != NULL) {
588		entry->name = olddict[i].name;
589		entry->len = olddict[i].len;
590		entry->okey = okey;
591		entry->next = dict->dict[key].next;
592		entry->valid = 1;
593		dict->dict[key].next = entry;
594	    } else {
595	        /*
596		 * we don't have much ways to alert from herei
597		 * result is loosing an entry and unicity garantee
598		 */
599	        ret = -1;
600	    }
601	}
602#ifdef DEBUG_GROW
603	nbElem++;
604#endif
605    }
606
607    for (i = 0; i < oldsize; i++) {
608	iter = olddict[i].next;
609	while (iter) {
610	    next = iter->next;
611
612	    /*
613	     * put back the entry in the new dict
614	     */
615
616	    if (keep_keys)
617		okey = iter->okey;
618	    else
619		okey = xmlDictComputeKey(dict, iter->name, iter->len);
620	    key = okey % dict->size;
621	    if (dict->dict[key].valid == 0) {
622		memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
623		dict->dict[key].next = NULL;
624		dict->dict[key].valid = 1;
625		dict->dict[key].okey = okey;
626		xmlFree(iter);
627	    } else {
628		iter->next = dict->dict[key].next;
629		iter->okey = okey;
630		dict->dict[key].next = iter;
631	    }
632
633#ifdef DEBUG_GROW
634	    nbElem++;
635#endif
636
637	    iter = next;
638	}
639    }
640
641    xmlFree(olddict);
642
643#ifdef DEBUG_GROW
644    xmlGenericError(xmlGenericErrorContext,
645	    "xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
646#endif
647
648    return(ret);
649}
650
651/**
652 * xmlDictFree:
653 * @dict: the dictionnary
654 *
655 * Free the hash @dict and its contents. The userdata is
656 * deallocated with @f if provided.
657 */
658void
659xmlDictFree(xmlDictPtr dict) {
660    int i;
661    xmlDictEntryPtr iter;
662    xmlDictEntryPtr next;
663    int inside_dict = 0;
664    xmlDictStringsPtr pool, nextp;
665
666    if (dict == NULL)
667	return;
668
669    if (!xmlDictInitialized)
670        if (!xmlInitializeDict())
671            return;
672
673    /* decrement the counter, it may be shared by a parser and docs */
674    xmlRMutexLock(xmlDictMutex);
675    dict->ref_counter--;
676    if (dict->ref_counter > 0) {
677        xmlRMutexUnlock(xmlDictMutex);
678        return;
679    }
680
681    xmlRMutexUnlock(xmlDictMutex);
682
683    if (dict->subdict != NULL) {
684        xmlDictFree(dict->subdict);
685    }
686
687    if (dict->dict) {
688	for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
689	    iter = &(dict->dict[i]);
690	    if (iter->valid == 0)
691		continue;
692	    inside_dict = 1;
693	    while (iter) {
694		next = iter->next;
695		if (!inside_dict)
696		    xmlFree(iter);
697		dict->nbElems--;
698		inside_dict = 0;
699		iter = next;
700	    }
701	    inside_dict = 0;
702	}
703	xmlFree(dict->dict);
704    }
705    pool = dict->strings;
706    while (pool != NULL) {
707        nextp = pool->next;
708	xmlFree(pool);
709	pool = nextp;
710    }
711    xmlFree(dict);
712}
713
714/**
715 * xmlDictLookup:
716 * @dict: the dictionnary
717 * @name: the name of the userdata
718 * @len: the length of the name, if -1 it is recomputed
719 *
720 * Add the @name to the dictionnary @dict if not present.
721 *
722 * Returns the internal copy of the name or NULL in case of internal error
723 */
724const xmlChar *
725xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
726    unsigned long key, okey, nbi = 0;
727    xmlDictEntryPtr entry;
728    xmlDictEntryPtr insert;
729    const xmlChar *ret;
730
731    if ((dict == NULL) || (name == NULL))
732	return(NULL);
733
734    if (len < 0)
735        len = strlen((const char *) name);
736
737    /*
738     * Check for duplicate and insertion location.
739     */
740    okey = xmlDictComputeKey(dict, name, len);
741    key = okey % dict->size;
742    if (dict->dict[key].valid == 0) {
743	insert = NULL;
744    } else {
745	for (insert = &(dict->dict[key]); insert->next != NULL;
746	     insert = insert->next) {
747#ifdef __GNUC__
748	    if ((insert->okey == okey) && (insert->len == len)) {
749		if (!memcmp(insert->name, name, len))
750		    return(insert->name);
751	    }
752#else
753	    if ((insert->okey == okey) && (insert->len == len) &&
754	        (!xmlStrncmp(insert->name, name, len)))
755		return(insert->name);
756#endif
757	    nbi++;
758	}
759#ifdef __GNUC__
760	if ((insert->okey == okey) && (insert->len == len)) {
761	    if (!memcmp(insert->name, name, len))
762		return(insert->name);
763	}
764#else
765	if ((insert->okey == okey) && (insert->len == len) &&
766	    (!xmlStrncmp(insert->name, name, len)))
767	    return(insert->name);
768#endif
769    }
770
771    if (dict->subdict) {
772        unsigned long skey;
773
774        /* we cannot always reuse the same okey for the subdict */
775        if (((dict->size == MIN_DICT_SIZE) &&
776	     (dict->subdict->size != MIN_DICT_SIZE)) ||
777            ((dict->size != MIN_DICT_SIZE) &&
778	     (dict->subdict->size == MIN_DICT_SIZE)))
779	    skey = xmlDictComputeKey(dict->subdict, name, len);
780	else
781	    skey = okey;
782
783	key = skey % dict->subdict->size;
784	if (dict->subdict->dict[key].valid != 0) {
785	    xmlDictEntryPtr tmp;
786
787	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
788		 tmp = tmp->next) {
789#ifdef __GNUC__
790		if ((tmp->okey == skey) && (tmp->len == len)) {
791		    if (!memcmp(tmp->name, name, len))
792			return(tmp->name);
793		}
794#else
795		if ((tmp->okey == skey) && (tmp->len == len) &&
796		    (!xmlStrncmp(tmp->name, name, len)))
797		    return(tmp->name);
798#endif
799		nbi++;
800	    }
801#ifdef __GNUC__
802	    if ((tmp->okey == skey) && (tmp->len == len)) {
803		if (!memcmp(tmp->name, name, len))
804		    return(tmp->name);
805	    }
806#else
807	    if ((tmp->okey == skey) && (tmp->len == len) &&
808		(!xmlStrncmp(tmp->name, name, len)))
809		return(tmp->name);
810#endif
811	}
812	key = okey % dict->size;
813    }
814
815    ret = xmlDictAddString(dict, name, len);
816    if (ret == NULL)
817        return(NULL);
818    if (insert == NULL) {
819	entry = &(dict->dict[key]);
820    } else {
821	entry = xmlMalloc(sizeof(xmlDictEntry));
822	if (entry == NULL)
823	     return(NULL);
824    }
825    entry->name = ret;
826    entry->len = len;
827    entry->next = NULL;
828    entry->valid = 1;
829    entry->okey = okey;
830
831
832    if (insert != NULL)
833	insert->next = entry;
834
835    dict->nbElems++;
836
837    if ((nbi > MAX_HASH_LEN) &&
838        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
839	if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
840	    return(NULL);
841    }
842    /* Note that entry may have been freed at this point by xmlDictGrow */
843
844    return(ret);
845}
846
847/**
848 * xmlDictExists:
849 * @dict: the dictionnary
850 * @name: the name of the userdata
851 * @len: the length of the name, if -1 it is recomputed
852 *
853 * Check if the @name exists in the dictionnary @dict.
854 *
855 * Returns the internal copy of the name or NULL if not found.
856 */
857const xmlChar *
858xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
859    unsigned long key, okey, nbi = 0;
860    xmlDictEntryPtr insert;
861
862    if ((dict == NULL) || (name == NULL))
863	return(NULL);
864
865    if (len < 0)
866        len = strlen((const char *) name);
867
868    /*
869     * Check for duplicate and insertion location.
870     */
871    okey = xmlDictComputeKey(dict, name, len);
872    key = okey % dict->size;
873    if (dict->dict[key].valid == 0) {
874	insert = NULL;
875    } else {
876	for (insert = &(dict->dict[key]); insert->next != NULL;
877	     insert = insert->next) {
878#ifdef __GNUC__
879	    if ((insert->okey == okey) && (insert->len == len)) {
880		if (!memcmp(insert->name, name, len))
881		    return(insert->name);
882	    }
883#else
884	    if ((insert->okey == okey) && (insert->len == len) &&
885	        (!xmlStrncmp(insert->name, name, len)))
886		return(insert->name);
887#endif
888	    nbi++;
889	}
890#ifdef __GNUC__
891	if ((insert->okey == okey) && (insert->len == len)) {
892	    if (!memcmp(insert->name, name, len))
893		return(insert->name);
894	}
895#else
896	if ((insert->okey == okey) && (insert->len == len) &&
897	    (!xmlStrncmp(insert->name, name, len)))
898	    return(insert->name);
899#endif
900    }
901
902    if (dict->subdict) {
903        unsigned long skey;
904
905        /* we cannot always reuse the same okey for the subdict */
906        if (((dict->size == MIN_DICT_SIZE) &&
907	     (dict->subdict->size != MIN_DICT_SIZE)) ||
908            ((dict->size != MIN_DICT_SIZE) &&
909	     (dict->subdict->size == MIN_DICT_SIZE)))
910	    skey = xmlDictComputeKey(dict->subdict, name, len);
911	else
912	    skey = okey;
913
914	key = skey % dict->subdict->size;
915	if (dict->subdict->dict[key].valid != 0) {
916	    xmlDictEntryPtr tmp;
917
918	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
919		 tmp = tmp->next) {
920#ifdef __GNUC__
921		if ((tmp->okey == skey) && (tmp->len == len)) {
922		    if (!memcmp(tmp->name, name, len))
923			return(tmp->name);
924		}
925#else
926		if ((tmp->okey == skey) && (tmp->len == len) &&
927		    (!xmlStrncmp(tmp->name, name, len)))
928		    return(tmp->name);
929#endif
930		nbi++;
931	    }
932#ifdef __GNUC__
933	    if ((tmp->okey == skey) && (tmp->len == len)) {
934		if (!memcmp(tmp->name, name, len))
935		    return(tmp->name);
936	    }
937#else
938	    if ((tmp->okey == skey) && (tmp->len == len) &&
939		(!xmlStrncmp(tmp->name, name, len)))
940		return(tmp->name);
941#endif
942	}
943    }
944
945    /* not found */
946    return(NULL);
947}
948
949/**
950 * xmlDictQLookup:
951 * @dict: the dictionnary
952 * @prefix: the prefix
953 * @name: the name
954 *
955 * Add the QName @prefix:@name to the hash @dict if not present.
956 *
957 * Returns the internal copy of the QName or NULL in case of internal error
958 */
959const xmlChar *
960xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
961    unsigned long okey, key, nbi = 0;
962    xmlDictEntryPtr entry;
963    xmlDictEntryPtr insert;
964    const xmlChar *ret;
965    int len, plen, l;
966
967    if ((dict == NULL) || (name == NULL))
968	return(NULL);
969    if (prefix == NULL)
970        return(xmlDictLookup(dict, name, -1));
971
972    l = len = strlen((const char *) name);
973    plen = strlen((const char *) prefix);
974    len += 1 + plen;
975
976    /*
977     * Check for duplicate and insertion location.
978     */
979    okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
980    key = okey % dict->size;
981    if (dict->dict[key].valid == 0) {
982	insert = NULL;
983    } else {
984	for (insert = &(dict->dict[key]); insert->next != NULL;
985	     insert = insert->next) {
986	    if ((insert->okey == okey) && (insert->len == len) &&
987	        (xmlStrQEqual(prefix, name, insert->name)))
988		return(insert->name);
989	    nbi++;
990	}
991	if ((insert->okey == okey) && (insert->len == len) &&
992	    (xmlStrQEqual(prefix, name, insert->name)))
993	    return(insert->name);
994    }
995
996    if (dict->subdict) {
997        unsigned long skey;
998
999        /* we cannot always reuse the same okey for the subdict */
1000        if (((dict->size == MIN_DICT_SIZE) &&
1001	     (dict->subdict->size != MIN_DICT_SIZE)) ||
1002            ((dict->size != MIN_DICT_SIZE) &&
1003	     (dict->subdict->size == MIN_DICT_SIZE)))
1004	    skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1005	else
1006	    skey = okey;
1007
1008	key = skey % dict->subdict->size;
1009	if (dict->subdict->dict[key].valid != 0) {
1010	    xmlDictEntryPtr tmp;
1011	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1012		 tmp = tmp->next) {
1013		if ((tmp->okey == skey) && (tmp->len == len) &&
1014		    (xmlStrQEqual(prefix, name, tmp->name)))
1015		    return(tmp->name);
1016		nbi++;
1017	    }
1018	    if ((tmp->okey == skey) && (tmp->len == len) &&
1019		(xmlStrQEqual(prefix, name, tmp->name)))
1020		return(tmp->name);
1021	}
1022	key = okey % dict->size;
1023    }
1024
1025    ret = xmlDictAddQString(dict, prefix, plen, name, l);
1026    if (ret == NULL)
1027        return(NULL);
1028    if (insert == NULL) {
1029	entry = &(dict->dict[key]);
1030    } else {
1031	entry = xmlMalloc(sizeof(xmlDictEntry));
1032	if (entry == NULL)
1033	     return(NULL);
1034    }
1035    entry->name = ret;
1036    entry->len = len;
1037    entry->next = NULL;
1038    entry->valid = 1;
1039    entry->okey = okey;
1040
1041    if (insert != NULL)
1042	insert->next = entry;
1043
1044    dict->nbElems++;
1045
1046    if ((nbi > MAX_HASH_LEN) &&
1047        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1048	xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1049    /* Note that entry may have been freed at this point by xmlDictGrow */
1050
1051    return(ret);
1052}
1053
1054/**
1055 * xmlDictOwns:
1056 * @dict: the dictionnary
1057 * @str: the string
1058 *
1059 * check if a string is owned by the disctionary
1060 *
1061 * Returns 1 if true, 0 if false and -1 in case of error
1062 * -1 in case of error
1063 */
1064int
1065xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1066    xmlDictStringsPtr pool;
1067
1068    if ((dict == NULL) || (str == NULL))
1069	return(-1);
1070    pool = dict->strings;
1071    while (pool != NULL) {
1072        if ((str >= &pool->array[0]) && (str <= pool->free))
1073	    return(1);
1074	pool = pool->next;
1075    }
1076    if (dict->subdict)
1077        return(xmlDictOwns(dict->subdict, str));
1078    return(0);
1079}
1080
1081/**
1082 * xmlDictSize:
1083 * @dict: the dictionnary
1084 *
1085 * Query the number of elements installed in the hash @dict.
1086 *
1087 * Returns the number of elements in the dictionnary or
1088 * -1 in case of error
1089 */
1090int
1091xmlDictSize(xmlDictPtr dict) {
1092    if (dict == NULL)
1093	return(-1);
1094    if (dict->subdict)
1095        return(dict->nbElems + dict->subdict->nbElems);
1096    return(dict->nbElems);
1097}
1098
1099
1100#define bottom_dict
1101#include "elfgcchack.h"
1102