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	}
702	xmlFree(dict->dict);
703    }
704    pool = dict->strings;
705    while (pool != NULL) {
706        nextp = pool->next;
707	xmlFree(pool);
708	pool = nextp;
709    }
710    xmlFree(dict);
711}
712
713/**
714 * xmlDictLookup:
715 * @dict: the dictionnary
716 * @name: the name of the userdata
717 * @len: the length of the name, if -1 it is recomputed
718 *
719 * Add the @name to the dictionnary @dict if not present.
720 *
721 * Returns the internal copy of the name or NULL in case of internal error
722 */
723const xmlChar *
724xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
725    unsigned long key, okey, nbi = 0;
726    xmlDictEntryPtr entry;
727    xmlDictEntryPtr insert;
728    const xmlChar *ret;
729
730    if ((dict == NULL) || (name == NULL))
731	return(NULL);
732
733    if (len < 0)
734        len = strlen((const char *) name);
735
736    /*
737     * Check for duplicate and insertion location.
738     */
739    okey = xmlDictComputeKey(dict, name, len);
740    key = okey % dict->size;
741    if (dict->dict[key].valid == 0) {
742	insert = NULL;
743    } else {
744	for (insert = &(dict->dict[key]); insert->next != NULL;
745	     insert = insert->next) {
746#ifdef __GNUC__
747	    if ((insert->okey == okey) && (insert->len == len)) {
748		if (!memcmp(insert->name, name, len))
749		    return(insert->name);
750	    }
751#else
752	    if ((insert->okey == okey) && (insert->len == len) &&
753	        (!xmlStrncmp(insert->name, name, len)))
754		return(insert->name);
755#endif
756	    nbi++;
757	}
758#ifdef __GNUC__
759	if ((insert->okey == okey) && (insert->len == len)) {
760	    if (!memcmp(insert->name, name, len))
761		return(insert->name);
762	}
763#else
764	if ((insert->okey == okey) && (insert->len == len) &&
765	    (!xmlStrncmp(insert->name, name, len)))
766	    return(insert->name);
767#endif
768    }
769
770    if (dict->subdict) {
771        unsigned long skey;
772
773        /* we cannot always reuse the same okey for the subdict */
774        if (((dict->size == MIN_DICT_SIZE) &&
775	     (dict->subdict->size != MIN_DICT_SIZE)) ||
776            ((dict->size != MIN_DICT_SIZE) &&
777	     (dict->subdict->size == MIN_DICT_SIZE)))
778	    skey = xmlDictComputeKey(dict->subdict, name, len);
779	else
780	    skey = okey;
781
782	key = skey % dict->subdict->size;
783	if (dict->subdict->dict[key].valid != 0) {
784	    xmlDictEntryPtr tmp;
785
786	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
787		 tmp = tmp->next) {
788#ifdef __GNUC__
789		if ((tmp->okey == skey) && (tmp->len == len)) {
790		    if (!memcmp(tmp->name, name, len))
791			return(tmp->name);
792		}
793#else
794		if ((tmp->okey == skey) && (tmp->len == len) &&
795		    (!xmlStrncmp(tmp->name, name, len)))
796		    return(tmp->name);
797#endif
798		nbi++;
799	    }
800#ifdef __GNUC__
801	    if ((tmp->okey == skey) && (tmp->len == len)) {
802		if (!memcmp(tmp->name, name, len))
803		    return(tmp->name);
804	    }
805#else
806	    if ((tmp->okey == skey) && (tmp->len == len) &&
807		(!xmlStrncmp(tmp->name, name, len)))
808		return(tmp->name);
809#endif
810	}
811	key = okey % dict->size;
812    }
813
814    ret = xmlDictAddString(dict, name, len);
815    if (ret == NULL)
816        return(NULL);
817    if (insert == NULL) {
818	entry = &(dict->dict[key]);
819    } else {
820	entry = xmlMalloc(sizeof(xmlDictEntry));
821	if (entry == NULL)
822	     return(NULL);
823    }
824    entry->name = ret;
825    entry->len = len;
826    entry->next = NULL;
827    entry->valid = 1;
828    entry->okey = okey;
829
830
831    if (insert != NULL)
832	insert->next = entry;
833
834    dict->nbElems++;
835
836    if ((nbi > MAX_HASH_LEN) &&
837        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
838	if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
839	    return(NULL);
840    }
841    /* Note that entry may have been freed at this point by xmlDictGrow */
842
843    return(ret);
844}
845
846/**
847 * xmlDictExists:
848 * @dict: the dictionnary
849 * @name: the name of the userdata
850 * @len: the length of the name, if -1 it is recomputed
851 *
852 * Check if the @name exists in the dictionnary @dict.
853 *
854 * Returns the internal copy of the name or NULL if not found.
855 */
856const xmlChar *
857xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
858    unsigned long key, okey, nbi = 0;
859    xmlDictEntryPtr insert;
860
861    if ((dict == NULL) || (name == NULL))
862	return(NULL);
863
864    if (len < 0)
865        len = strlen((const char *) name);
866
867    /*
868     * Check for duplicate and insertion location.
869     */
870    okey = xmlDictComputeKey(dict, name, len);
871    key = okey % dict->size;
872    if (dict->dict[key].valid == 0) {
873	insert = NULL;
874    } else {
875	for (insert = &(dict->dict[key]); insert->next != NULL;
876	     insert = insert->next) {
877#ifdef __GNUC__
878	    if ((insert->okey == okey) && (insert->len == len)) {
879		if (!memcmp(insert->name, name, len))
880		    return(insert->name);
881	    }
882#else
883	    if ((insert->okey == okey) && (insert->len == len) &&
884	        (!xmlStrncmp(insert->name, name, len)))
885		return(insert->name);
886#endif
887	    nbi++;
888	}
889#ifdef __GNUC__
890	if ((insert->okey == okey) && (insert->len == len)) {
891	    if (!memcmp(insert->name, name, len))
892		return(insert->name);
893	}
894#else
895	if ((insert->okey == okey) && (insert->len == len) &&
896	    (!xmlStrncmp(insert->name, name, len)))
897	    return(insert->name);
898#endif
899    }
900
901    if (dict->subdict) {
902        unsigned long skey;
903
904        /* we cannot always reuse the same okey for the subdict */
905        if (((dict->size == MIN_DICT_SIZE) &&
906	     (dict->subdict->size != MIN_DICT_SIZE)) ||
907            ((dict->size != MIN_DICT_SIZE) &&
908	     (dict->subdict->size == MIN_DICT_SIZE)))
909	    skey = xmlDictComputeKey(dict->subdict, name, len);
910	else
911	    skey = okey;
912
913	key = skey % dict->subdict->size;
914	if (dict->subdict->dict[key].valid != 0) {
915	    xmlDictEntryPtr tmp;
916
917	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
918		 tmp = tmp->next) {
919#ifdef __GNUC__
920		if ((tmp->okey == skey) && (tmp->len == len)) {
921		    if (!memcmp(tmp->name, name, len))
922			return(tmp->name);
923		}
924#else
925		if ((tmp->okey == skey) && (tmp->len == len) &&
926		    (!xmlStrncmp(tmp->name, name, len)))
927		    return(tmp->name);
928#endif
929		nbi++;
930	    }
931#ifdef __GNUC__
932	    if ((tmp->okey == skey) && (tmp->len == len)) {
933		if (!memcmp(tmp->name, name, len))
934		    return(tmp->name);
935	    }
936#else
937	    if ((tmp->okey == skey) && (tmp->len == len) &&
938		(!xmlStrncmp(tmp->name, name, len)))
939		return(tmp->name);
940#endif
941	}
942    }
943
944    /* not found */
945    return(NULL);
946}
947
948/**
949 * xmlDictQLookup:
950 * @dict: the dictionnary
951 * @prefix: the prefix
952 * @name: the name
953 *
954 * Add the QName @prefix:@name to the hash @dict if not present.
955 *
956 * Returns the internal copy of the QName or NULL in case of internal error
957 */
958const xmlChar *
959xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
960    unsigned long okey, key, nbi = 0;
961    xmlDictEntryPtr entry;
962    xmlDictEntryPtr insert;
963    const xmlChar *ret;
964    int len, plen, l;
965
966    if ((dict == NULL) || (name == NULL))
967	return(NULL);
968    if (prefix == NULL)
969        return(xmlDictLookup(dict, name, -1));
970
971    l = len = strlen((const char *) name);
972    plen = strlen((const char *) prefix);
973    len += 1 + plen;
974
975    /*
976     * Check for duplicate and insertion location.
977     */
978    okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
979    key = okey % dict->size;
980    if (dict->dict[key].valid == 0) {
981	insert = NULL;
982    } else {
983	for (insert = &(dict->dict[key]); insert->next != NULL;
984	     insert = insert->next) {
985	    if ((insert->okey == okey) && (insert->len == len) &&
986	        (xmlStrQEqual(prefix, name, insert->name)))
987		return(insert->name);
988	    nbi++;
989	}
990	if ((insert->okey == okey) && (insert->len == len) &&
991	    (xmlStrQEqual(prefix, name, insert->name)))
992	    return(insert->name);
993    }
994
995    if (dict->subdict) {
996        unsigned long skey;
997
998        /* we cannot always reuse the same okey for the subdict */
999        if (((dict->size == MIN_DICT_SIZE) &&
1000	     (dict->subdict->size != MIN_DICT_SIZE)) ||
1001            ((dict->size != MIN_DICT_SIZE) &&
1002	     (dict->subdict->size == MIN_DICT_SIZE)))
1003	    skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1004	else
1005	    skey = okey;
1006
1007	key = skey % dict->subdict->size;
1008	if (dict->subdict->dict[key].valid != 0) {
1009	    xmlDictEntryPtr tmp;
1010	    for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1011		 tmp = tmp->next) {
1012		if ((tmp->okey == skey) && (tmp->len == len) &&
1013		    (xmlStrQEqual(prefix, name, tmp->name)))
1014		    return(tmp->name);
1015		nbi++;
1016	    }
1017	    if ((tmp->okey == skey) && (tmp->len == len) &&
1018		(xmlStrQEqual(prefix, name, tmp->name)))
1019		return(tmp->name);
1020	}
1021	key = okey % dict->size;
1022    }
1023
1024    ret = xmlDictAddQString(dict, prefix, plen, name, l);
1025    if (ret == NULL)
1026        return(NULL);
1027    if (insert == NULL) {
1028	entry = &(dict->dict[key]);
1029    } else {
1030	entry = xmlMalloc(sizeof(xmlDictEntry));
1031	if (entry == NULL)
1032	     return(NULL);
1033    }
1034    entry->name = ret;
1035    entry->len = len;
1036    entry->next = NULL;
1037    entry->valid = 1;
1038    entry->okey = okey;
1039
1040    if (insert != NULL)
1041	insert->next = entry;
1042
1043    dict->nbElems++;
1044
1045    if ((nbi > MAX_HASH_LEN) &&
1046        (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1047	xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1048    /* Note that entry may have been freed at this point by xmlDictGrow */
1049
1050    return(ret);
1051}
1052
1053/**
1054 * xmlDictOwns:
1055 * @dict: the dictionnary
1056 * @str: the string
1057 *
1058 * check if a string is owned by the disctionary
1059 *
1060 * Returns 1 if true, 0 if false and -1 in case of error
1061 * -1 in case of error
1062 */
1063int
1064xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1065    xmlDictStringsPtr pool;
1066
1067    if ((dict == NULL) || (str == NULL))
1068	return(-1);
1069    pool = dict->strings;
1070    while (pool != NULL) {
1071        if ((str >= &pool->array[0]) && (str <= pool->free))
1072	    return(1);
1073	pool = pool->next;
1074    }
1075    if (dict->subdict)
1076        return(xmlDictOwns(dict->subdict, str));
1077    return(0);
1078}
1079
1080/**
1081 * xmlDictSize:
1082 * @dict: the dictionnary
1083 *
1084 * Query the number of elements installed in the hash @dict.
1085 *
1086 * Returns the number of elements in the dictionnary or
1087 * -1 in case of error
1088 */
1089int
1090xmlDictSize(xmlDictPtr dict) {
1091    if (dict == NULL)
1092	return(-1);
1093    if (dict->subdict)
1094        return(dict->nbElems + dict->subdict->nbElems);
1095    return(dict->nbElems);
1096}
1097
1098
1099#define bottom_dict
1100#include "elfgcchack.h"
1101