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