dict.c

00001 /*
00002  * dict.c: dictionary of reusable strings, just used to avoid allocation
00003  *         and freeing operations.
00004  *
00005  * Copyright (C) 2003-2012 Daniel Veillard.
00006  *
00007  * Permission to use, copy, modify, and distribute this software for any
00008  * purpose with or without fee is hereby granted, provided that the above
00009  * copyright notice and this permission notice appear in all copies.
00010  *
00011  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
00012  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
00013  * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
00014  * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
00015  *
00016  * Author: daniel@veillard.com
00017  */
00018 
00019 #define IN_LIBXML
00020 #include "libxml.h"
00021 
00022 #include <limits.h>
00023 #ifdef HAVE_STDLIB_H
00024 #include <stdlib.h>
00025 #endif
00026 #ifdef HAVE_TIME_H
00027 #include <time.h>
00028 #endif
00029 
00030 /*
00031  * Following http://www.ocert.org/advisories/ocert-2011-003.html
00032  * it seems that having hash randomization might be a good idea
00033  * when using XML with untrusted data
00034  * Note1: that it works correctly only if compiled with WITH_BIG_KEY
00035  *  which is the default.
00036  * Note2: the fast function used for a small dict won't protect very
00037  *  well but since the attack is based on growing a very big hash
00038  *  list we will use the BigKey algo as soon as the hash size grows
00039  *  over MIN_DICT_SIZE so this actually works
00040  */
00041 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
00042 #define DICT_RANDOMIZATION
00043 #endif
00044 
00045 #include <string.h>
00046 #ifdef HAVE_STDINT_H
00047 #include <stdint.h>
00048 #else
00049 #ifdef HAVE_INTTYPES_H
00050 #include <inttypes.h>
00051 #elif defined(WIN32)
00052 typedef unsigned __int32 uint32_t;
00053 #endif
00054 #endif
00055 #include <libxml/tree.h>
00056 #include <libxml/dict.h>
00057 #include <libxml/xmlmemory.h>
00058 #include <libxml/xmlerror.h>
00059 #include <libxml/globals.h>
00060 
00061 /* #define DEBUG_GROW */
00062 /* #define DICT_DEBUG_PATTERNS */
00063 
00064 #define MAX_HASH_LEN 3
00065 #define MIN_DICT_SIZE 128
00066 #define MAX_DICT_HASH 8 * 2048
00067 #define WITH_BIG_KEY
00068 
00069 #ifdef WITH_BIG_KEY
00070 #define xmlDictComputeKey(dict, name, len)                              \
00071     (((dict)->size == MIN_DICT_SIZE) ?                                  \
00072      xmlDictComputeFastKey(name, len, (dict)->seed) :                   \
00073      xmlDictComputeBigKey(name, len, (dict)->seed))
00074 
00075 #define xmlDictComputeQKey(dict, prefix, plen, name, len)               \
00076     (((prefix) == NULL) ?                                               \
00077       (xmlDictComputeKey(dict, name, len)) :                             \
00078       (((dict)->size == MIN_DICT_SIZE) ?                                \
00079        xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) :  \
00080        xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
00081 
00082 #else /* !WITH_BIG_KEY */
00083 #define xmlDictComputeKey(dict, name, len)                              \
00084         xmlDictComputeFastKey(name, len, (dict)->seed)
00085 #define xmlDictComputeQKey(dict, prefix, plen, name, len)               \
00086         xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
00087 #endif /* WITH_BIG_KEY */
00088 
00089 /*
00090  * An entry in the dictionnary
00091  */
00092 typedef struct _xmlDictEntry xmlDictEntry;
00093 typedef xmlDictEntry *xmlDictEntryPtr;
00094 struct _xmlDictEntry {
00095     struct _xmlDictEntry *next;
00096     const xmlChar *name;
00097     unsigned int len;
00098     int valid;
00099     unsigned long okey;
00100 };
00101 
00102 typedef struct _xmlDictStrings xmlDictStrings;
00103 typedef xmlDictStrings *xmlDictStringsPtr;
00104 struct _xmlDictStrings {
00105     xmlDictStringsPtr next;
00106     xmlChar *free;
00107     xmlChar *end;
00108     size_t size;
00109     size_t nbStrings;
00110     xmlChar array[1];
00111 };
00112 /*
00113  * The entire dictionnary
00114  */
00115 struct _xmlDict {
00116     int ref_counter;
00117 
00118     struct _xmlDictEntry *dict;
00119     size_t size;
00120     unsigned int nbElems;
00121     xmlDictStringsPtr strings;
00122 
00123     struct _xmlDict *subdict;
00124     /* used for randomization */
00125     int seed;
00126     /* used to impose a limit on size */
00127     size_t limit;
00128 };
00129 
00130 /*
00131  * A mutex for modifying the reference counter for shared
00132  * dictionaries.
00133  */
00134 static xmlRMutexPtr xmlDictMutex = NULL;
00135 
00136 /*
00137  * Whether the dictionary mutex was initialized.
00138  */
00139 static int xmlDictInitialized = 0;
00140 
00141 #ifdef DICT_RANDOMIZATION
00142 #ifdef HAVE_RAND_R
00143 /*
00144  * Internal data for random function, protected by xmlDictMutex
00145  */
00146 static unsigned int rand_seed = 0;
00147 #endif
00148 #endif
00149 
00150 /**
00151  * xmlInitializeDict:
00152  *
00153  * Do the dictionary mutex initialization.
00154  * this function is deprecated
00155  *
00156  * Returns 0 if initialization was already done, and 1 if that
00157  * call led to the initialization
00158  */
00159 int xmlInitializeDict(void) {
00160     return(0);
00161 }
00162 
00163 /**
00164  * __xmlInitializeDict:
00165  *
00166  * This function is not public
00167  * Do the dictionary mutex initialization.
00168  * this function is not thread safe, initialization should
00169  * normally be done once at setup when called from xmlOnceInit()
00170  * we may also land in this code if thread support is not compiled in
00171  *
00172  * Returns 0 if initialization was already done, and 1 if that
00173  * call led to the initialization
00174  */
00175 int __xmlInitializeDict(void) {
00176     if (xmlDictInitialized)
00177         return(1);
00178 
00179     if ((xmlDictMutex = xmlNewRMutex()) == NULL)
00180         return(0);
00181     xmlRMutexLock(xmlDictMutex);
00182 
00183 #ifdef DICT_RANDOMIZATION
00184 #ifdef HAVE_RAND_R
00185     rand_seed = time(NULL);
00186     rand_r(& rand_seed);
00187 #else
00188     srand(time(NULL));
00189 #endif
00190 #endif
00191     xmlDictInitialized = 1;
00192     xmlRMutexUnlock(xmlDictMutex);
00193     return(1);
00194 }
00195 
00196 #ifdef DICT_RANDOMIZATION
00197 int __xmlRandom(void) {
00198     int ret;
00199 
00200     if (xmlDictInitialized == 0)
00201         __xmlInitializeDict();
00202 
00203     xmlRMutexLock(xmlDictMutex);
00204 #ifdef HAVE_RAND_R
00205     ret = rand_r(& rand_seed);
00206 #else
00207     ret = rand();
00208 #endif
00209     xmlRMutexUnlock(xmlDictMutex);
00210     return(ret);
00211 }
00212 #endif
00213 
00214 /**
00215  * xmlDictCleanup:
00216  *
00217  * Free the dictionary mutex. Do not call unless sure the library
00218  * is not in use anymore !
00219  */
00220 void
00221 xmlDictCleanup(void) {
00222     if (!xmlDictInitialized)
00223         return;
00224 
00225     xmlFreeRMutex(xmlDictMutex);
00226 
00227     xmlDictInitialized = 0;
00228 }
00229 
00230 /*
00231  * xmlDictAddString:
00232  * @dict: the dictionnary
00233  * @name: the name of the userdata
00234  * @len: the length of the name
00235  *
00236  * Add the string to the array[s]
00237  *
00238  * Returns the pointer of the local string, or NULL in case of error.
00239  */
00240 static const xmlChar *
00241 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
00242     xmlDictStringsPtr pool;
00243     const xmlChar *ret;
00244     size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
00245     size_t limit = 0;
00246 
00247 #ifdef DICT_DEBUG_PATTERNS
00248     fprintf(stderr, "-");
00249 #endif
00250     pool = dict->strings;
00251     while (pool != NULL) {
00252     if (pool->end - pool->free > namelen)
00253         goto found_pool;
00254     if (pool->size > size) size = pool->size;
00255         limit += pool->size;
00256     pool = pool->next;
00257     }
00258     /*
00259      * Not found, need to allocate
00260      */
00261     if (pool == NULL) {
00262         if ((dict->limit > 0) && (limit > dict->limit)) {
00263             return(NULL);
00264         }
00265 
00266         if (size == 0) size = 1000;
00267     else size *= 4; /* exponential growth */
00268         if (size < 4 * namelen)
00269         size = 4 * namelen; /* just in case ! */
00270     pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
00271     if (pool == NULL)
00272         return(NULL);
00273     pool->size = size;
00274     pool->nbStrings = 0;
00275     pool->free = &pool->array[0];
00276     pool->end = &pool->array[size];
00277     pool->next = dict->strings;
00278     dict->strings = pool;
00279 #ifdef DICT_DEBUG_PATTERNS
00280         fprintf(stderr, "+");
00281 #endif
00282     }
00283 found_pool:
00284     ret = pool->free;
00285     memcpy(pool->free, name, namelen);
00286     pool->free += namelen;
00287     *(pool->free++) = 0;
00288     pool->nbStrings++;
00289     return(ret);
00290 }
00291 
00292 /*
00293  * xmlDictAddQString:
00294  * @dict: the dictionnary
00295  * @prefix: the prefix of the userdata
00296  * @plen: the prefix length
00297  * @name: the name of the userdata
00298  * @len: the length of the name
00299  *
00300  * Add the QName to the array[s]
00301  *
00302  * Returns the pointer of the local string, or NULL in case of error.
00303  */
00304 static const xmlChar *
00305 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
00306                  const xmlChar *name, unsigned int namelen)
00307 {
00308     xmlDictStringsPtr pool;
00309     const xmlChar *ret;
00310     size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
00311     size_t limit = 0;
00312 
00313     if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
00314 
00315 #ifdef DICT_DEBUG_PATTERNS
00316     fprintf(stderr, "=");
00317 #endif
00318     pool = dict->strings;
00319     while (pool != NULL) {
00320     if (pool->end - pool->free > namelen + plen + 1)
00321         goto found_pool;
00322     if (pool->size > size) size = pool->size;
00323         limit += pool->size;
00324     pool = pool->next;
00325     }
00326     /*
00327      * Not found, need to allocate
00328      */
00329     if (pool == NULL) {
00330         if ((dict->limit > 0) && (limit > dict->limit)) {
00331             return(NULL);
00332         }
00333 
00334         if (size == 0) size = 1000;
00335     else size *= 4; /* exponential growth */
00336         if (size < 4 * (namelen + plen + 1))
00337         size = 4 * (namelen + plen + 1); /* just in case ! */
00338     pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
00339     if (pool == NULL)
00340         return(NULL);
00341     pool->size = size;
00342     pool->nbStrings = 0;
00343     pool->free = &pool->array[0];
00344     pool->end = &pool->array[size];
00345     pool->next = dict->strings;
00346     dict->strings = pool;
00347 #ifdef DICT_DEBUG_PATTERNS
00348         fprintf(stderr, "+");
00349 #endif
00350     }
00351 found_pool:
00352     ret = pool->free;
00353     memcpy(pool->free, prefix, plen);
00354     pool->free += plen;
00355     *(pool->free++) = ':';
00356     memcpy(pool->free, name, namelen);
00357     pool->free += namelen;
00358     *(pool->free++) = 0;
00359     pool->nbStrings++;
00360     return(ret);
00361 }
00362 
00363 #ifdef WITH_BIG_KEY
00364 /*
00365  * xmlDictComputeBigKey:
00366  *
00367  * Calculate a hash key using a good hash function that works well for
00368  * larger hash table sizes.
00369  *
00370  * Hash function by "One-at-a-Time Hash" see
00371  * http://burtleburtle.net/bob/hash/doobs.html
00372  */
00373 
00374 static uint32_t
00375 xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
00376     uint32_t hash;
00377     int i;
00378 
00379     if (namelen <= 0 || data == NULL) return(0);
00380 
00381     hash = seed;
00382 
00383     for (i = 0;i < namelen; i++) {
00384         hash += data[i];
00385     hash += (hash << 10);
00386     hash ^= (hash >> 6);
00387     }
00388     hash += (hash << 3);
00389     hash ^= (hash >> 11);
00390     hash += (hash << 15);
00391 
00392     return hash;
00393 }
00394 
00395 /*
00396  * xmlDictComputeBigQKey:
00397  *
00398  * Calculate a hash key for two strings using a good hash function
00399  * that works well for larger hash table sizes.
00400  *
00401  * Hash function by "One-at-a-Time Hash" see
00402  * http://burtleburtle.net/bob/hash/doobs.html
00403  *
00404  * Neither of the two strings must be NULL.
00405  */
00406 static unsigned long
00407 xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
00408                       const xmlChar *name, int len, int seed)
00409 {
00410     uint32_t hash;
00411     int i;
00412 
00413     hash = seed;
00414 
00415     for (i = 0;i < plen; i++) {
00416         hash += prefix[i];
00417     hash += (hash << 10);
00418     hash ^= (hash >> 6);
00419     }
00420     hash += ':';
00421     hash += (hash << 10);
00422     hash ^= (hash >> 6);
00423 
00424     for (i = 0;i < len; i++) {
00425         hash += name[i];
00426     hash += (hash << 10);
00427     hash ^= (hash >> 6);
00428     }
00429     hash += (hash << 3);
00430     hash ^= (hash >> 11);
00431     hash += (hash << 15);
00432 
00433     return hash;
00434 }
00435 #endif /* WITH_BIG_KEY */
00436 
00437 /*
00438  * xmlDictComputeFastKey:
00439  *
00440  * Calculate a hash key using a fast hash function that works well
00441  * for low hash table fill.
00442  */
00443 static unsigned long
00444 xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
00445     unsigned long value = seed;
00446 
00447     if (name == NULL) return(0);
00448     value = *name;
00449     value <<= 5;
00450     if (namelen > 10) {
00451         value += name[namelen - 1];
00452         namelen = 10;
00453     }
00454     switch (namelen) {
00455         case 10: value += name[9];
00456         case 9: value += name[8];
00457         case 8: value += name[7];
00458         case 7: value += name[6];
00459         case 6: value += name[5];
00460         case 5: value += name[4];
00461         case 4: value += name[3];
00462         case 3: value += name[2];
00463         case 2: value += name[1];
00464         default: break;
00465     }
00466     return(value);
00467 }
00468 
00469 /*
00470  * xmlDictComputeFastQKey:
00471  *
00472  * Calculate a hash key for two strings using a fast hash function
00473  * that works well for low hash table fill.
00474  *
00475  * Neither of the two strings must be NULL.
00476  */
00477 static unsigned long
00478 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
00479                        const xmlChar *name, int len, int seed)
00480 {
00481     unsigned long value = (unsigned long) seed;
00482 
00483     if (plen == 0)
00484     value += 30 * (unsigned long) ':';
00485     else
00486     value += 30 * (*prefix);
00487 
00488     if (len > 10) {
00489         int offset = len - (plen + 1 + 1);
00490     if (offset < 0)
00491         offset = len - (10 + 1);
00492     value += name[offset];
00493         len = 10;
00494     if (plen > 10)
00495         plen = 10;
00496     }
00497     switch (plen) {
00498         case 10: value += prefix[9];
00499         case 9: value += prefix[8];
00500         case 8: value += prefix[7];
00501         case 7: value += prefix[6];
00502         case 6: value += prefix[5];
00503         case 5: value += prefix[4];
00504         case 4: value += prefix[3];
00505         case 3: value += prefix[2];
00506         case 2: value += prefix[1];
00507         case 1: value += prefix[0];
00508         default: break;
00509     }
00510     len -= plen;
00511     if (len > 0) {
00512         value += (unsigned long) ':';
00513     len--;
00514     }
00515     switch (len) {
00516         case 10: value += name[9];
00517         case 9: value += name[8];
00518         case 8: value += name[7];
00519         case 7: value += name[6];
00520         case 6: value += name[5];
00521         case 5: value += name[4];
00522         case 4: value += name[3];
00523         case 3: value += name[2];
00524         case 2: value += name[1];
00525         case 1: value += name[0];
00526         default: break;
00527     }
00528     return(value);
00529 }
00530 
00531 /**
00532  * xmlDictCreate:
00533  *
00534  * Create a new dictionary
00535  *
00536  * Returns the newly created dictionnary, or NULL if an error occured.
00537  */
00538 xmlDictPtr
00539 xmlDictCreate(void) {
00540     xmlDictPtr dict;
00541 
00542     if (!xmlDictInitialized)
00543         if (!__xmlInitializeDict())
00544             return(NULL);
00545 
00546 #ifdef DICT_DEBUG_PATTERNS
00547     fprintf(stderr, "C");
00548 #endif
00549 
00550     dict = xmlMalloc(sizeof(xmlDict));
00551     if (dict) {
00552         dict->ref_counter = 1;
00553         dict->limit = 0;
00554 
00555         dict->size = MIN_DICT_SIZE;
00556     dict->nbElems = 0;
00557         dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
00558     dict->strings = NULL;
00559     dict->subdict = NULL;
00560         if (dict->dict) {
00561         memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
00562 #ifdef DICT_RANDOMIZATION
00563             dict->seed = __xmlRandom();
00564 #else
00565             dict->seed = 0;
00566 #endif
00567         return(dict);
00568         }
00569         xmlFree(dict);
00570     }
00571     return(NULL);
00572 }
00573 
00574 /**
00575  * xmlDictCreateSub:
00576  * @sub: an existing dictionnary
00577  *
00578  * Create a new dictionary, inheriting strings from the read-only
00579  * dictionnary @sub. On lookup, strings are first searched in the
00580  * new dictionnary, then in @sub, and if not found are created in the
00581  * new dictionnary.
00582  *
00583  * Returns the newly created dictionnary, or NULL if an error occured.
00584  */
00585 xmlDictPtr
00586 xmlDictCreateSub(xmlDictPtr sub) {
00587     xmlDictPtr dict = xmlDictCreate();
00588 
00589     if ((dict != NULL) && (sub != NULL)) {
00590 #ifdef DICT_DEBUG_PATTERNS
00591         fprintf(stderr, "R");
00592 #endif
00593         dict->seed = sub->seed;
00594         dict->subdict = sub;
00595     xmlDictReference(dict->subdict);
00596     }
00597     return(dict);
00598 }
00599 
00600 /**
00601  * xmlDictReference:
00602  * @dict: the dictionnary
00603  *
00604  * Increment the reference counter of a dictionary
00605  *
00606  * Returns 0 in case of success and -1 in case of error
00607  */
00608 int
00609 xmlDictReference(xmlDictPtr dict) {
00610     if (!xmlDictInitialized)
00611         if (!__xmlInitializeDict())
00612             return(-1);
00613 
00614     if (dict == NULL) return -1;
00615     xmlRMutexLock(xmlDictMutex);
00616     dict->ref_counter++;
00617     xmlRMutexUnlock(xmlDictMutex);
00618     return(0);
00619 }
00620 
00621 /**
00622  * xmlDictGrow:
00623  * @dict: the dictionnary
00624  * @size: the new size of the dictionnary
00625  *
00626  * resize the dictionnary
00627  *
00628  * Returns 0 in case of success, -1 in case of failure
00629  */
00630 static int
00631 xmlDictGrow(xmlDictPtr dict, size_t size) {
00632     unsigned long key, okey;
00633     size_t oldsize, i;
00634     xmlDictEntryPtr iter, next;
00635     struct _xmlDictEntry *olddict;
00636 #ifdef DEBUG_GROW
00637     unsigned long nbElem = 0;
00638 #endif
00639     int ret = 0;
00640     int keep_keys = 1;
00641 
00642     if (dict == NULL)
00643     return(-1);
00644     if (size < 8)
00645         return(-1);
00646     if (size > 8 * 2048)
00647     return(-1);
00648 
00649 #ifdef DICT_DEBUG_PATTERNS
00650     fprintf(stderr, "*");
00651 #endif
00652 
00653     oldsize = dict->size;
00654     olddict = dict->dict;
00655     if (olddict == NULL)
00656         return(-1);
00657     if (oldsize == MIN_DICT_SIZE)
00658         keep_keys = 0;
00659 
00660     dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
00661     if (dict->dict == NULL) {
00662     dict->dict = olddict;
00663     return(-1);
00664     }
00665     memset(dict->dict, 0, size * sizeof(xmlDictEntry));
00666     dict->size = size;
00667 
00668     /*  If the two loops are merged, there would be situations where
00669     a new entry needs to allocated and data copied into it from
00670     the main dict. It is nicer to run through the array twice, first
00671     copying all the elements in the main array (less probability of
00672     allocate) and then the rest, so we only free in the second loop.
00673     */
00674     for (i = 0; i < oldsize; i++) {
00675     if (olddict[i].valid == 0)
00676         continue;
00677 
00678     if (keep_keys)
00679         okey = olddict[i].okey;
00680     else
00681         okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
00682     key = okey % dict->size;
00683 
00684     if (dict->dict[key].valid == 0) {
00685         memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
00686         dict->dict[key].next = NULL;
00687         dict->dict[key].okey = okey;
00688     } else {
00689         xmlDictEntryPtr entry;
00690 
00691         entry = xmlMalloc(sizeof(xmlDictEntry));
00692         if (entry != NULL) {
00693         entry->name = olddict[i].name;
00694         entry->len = olddict[i].len;
00695         entry->okey = okey;
00696         entry->next = dict->dict[key].next;
00697         entry->valid = 1;
00698         dict->dict[key].next = entry;
00699         } else {
00700             /*
00701          * we don't have much ways to alert from herei
00702          * result is loosing an entry and unicity garantee
00703          */
00704             ret = -1;
00705         }
00706     }
00707 #ifdef DEBUG_GROW
00708     nbElem++;
00709 #endif
00710     }
00711 
00712     for (i = 0; i < oldsize; i++) {
00713     iter = olddict[i].next;
00714     while (iter) {
00715         next = iter->next;
00716 
00717         /*
00718          * put back the entry in the new dict
00719          */
00720 
00721         if (keep_keys)
00722         okey = iter->okey;
00723         else
00724         okey = xmlDictComputeKey(dict, iter->name, iter->len);
00725         key = okey % dict->size;
00726         if (dict->dict[key].valid == 0) {
00727         memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
00728         dict->dict[key].next = NULL;
00729         dict->dict[key].valid = 1;
00730         dict->dict[key].okey = okey;
00731         xmlFree(iter);
00732         } else {
00733         iter->next = dict->dict[key].next;
00734         iter->okey = okey;
00735         dict->dict[key].next = iter;
00736         }
00737 
00738 #ifdef DEBUG_GROW
00739         nbElem++;
00740 #endif
00741 
00742         iter = next;
00743     }
00744     }
00745 
00746     xmlFree(olddict);
00747 
00748 #ifdef DEBUG_GROW
00749     xmlGenericError(xmlGenericErrorContext,
00750         "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
00751 #endif
00752 
00753     return(ret);
00754 }
00755 
00756 /**
00757  * xmlDictFree:
00758  * @dict: the dictionnary
00759  *
00760  * Free the hash @dict and its contents. The userdata is
00761  * deallocated with @f if provided.
00762  */
00763 void
00764 xmlDictFree(xmlDictPtr dict) {
00765     size_t i;
00766     xmlDictEntryPtr iter;
00767     xmlDictEntryPtr next;
00768     int inside_dict = 0;
00769     xmlDictStringsPtr pool, nextp;
00770 
00771     if (dict == NULL)
00772     return;
00773 
00774     if (!xmlDictInitialized)
00775         if (!__xmlInitializeDict())
00776             return;
00777 
00778     /* decrement the counter, it may be shared by a parser and docs */
00779     xmlRMutexLock(xmlDictMutex);
00780     dict->ref_counter--;
00781     if (dict->ref_counter > 0) {
00782         xmlRMutexUnlock(xmlDictMutex);
00783         return;
00784     }
00785 
00786     xmlRMutexUnlock(xmlDictMutex);
00787 
00788     if (dict->subdict != NULL) {
00789         xmlDictFree(dict->subdict);
00790     }
00791 
00792     if (dict->dict) {
00793     for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
00794         iter = &(dict->dict[i]);
00795         if (iter->valid == 0)
00796         continue;
00797         inside_dict = 1;
00798         while (iter) {
00799         next = iter->next;
00800         if (!inside_dict)
00801             xmlFree(iter);
00802         dict->nbElems--;
00803         inside_dict = 0;
00804         iter = next;
00805         }
00806     }
00807     xmlFree(dict->dict);
00808     }
00809     pool = dict->strings;
00810     while (pool != NULL) {
00811         nextp = pool->next;
00812     xmlFree(pool);
00813     pool = nextp;
00814     }
00815     xmlFree(dict);
00816 }
00817 
00818 /**
00819  * xmlDictLookup:
00820  * @dict: the dictionnary
00821  * @name: the name of the userdata
00822  * @len: the length of the name, if -1 it is recomputed
00823  *
00824  * Add the @name to the dictionnary @dict if not present.
00825  *
00826  * Returns the internal copy of the name or NULL in case of internal error
00827  */
00828 const xmlChar *
00829 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
00830     unsigned long key, okey, nbi = 0;
00831     xmlDictEntryPtr entry;
00832     xmlDictEntryPtr insert;
00833     const xmlChar *ret;
00834     unsigned int l;
00835 
00836     if ((dict == NULL) || (name == NULL))
00837     return(NULL);
00838 
00839     if (len < 0)
00840         l = strlen((const char *) name);
00841     else
00842         l = len;
00843 
00844     if (((dict->limit > 0) && (l >= dict->limit)) ||
00845         (l > INT_MAX / 2))
00846         return(NULL);
00847 
00848     /*
00849      * Check for duplicate and insertion location.
00850      */
00851     okey = xmlDictComputeKey(dict, name, l);
00852     key = okey % dict->size;
00853     if (dict->dict[key].valid == 0) {
00854     insert = NULL;
00855     } else {
00856     for (insert = &(dict->dict[key]); insert->next != NULL;
00857          insert = insert->next) {
00858 #ifdef __GNUC__
00859         if ((insert->okey == okey) && (insert->len == l)) {
00860         if (!memcmp(insert->name, name, l))
00861             return(insert->name);
00862         }
00863 #else
00864         if ((insert->okey == okey) && (insert->len == l) &&
00865             (!xmlStrncmp(insert->name, name, l)))
00866         return(insert->name);
00867 #endif
00868         nbi++;
00869     }
00870 #ifdef __GNUC__
00871     if ((insert->okey == okey) && (insert->len == l)) {
00872         if (!memcmp(insert->name, name, l))
00873         return(insert->name);
00874     }
00875 #else
00876     if ((insert->okey == okey) && (insert->len == l) &&
00877         (!xmlStrncmp(insert->name, name, l)))
00878         return(insert->name);
00879 #endif
00880     }
00881 
00882     if (dict->subdict) {
00883         unsigned long skey;
00884 
00885         /* we cannot always reuse the same okey for the subdict */
00886         if (((dict->size == MIN_DICT_SIZE) &&
00887          (dict->subdict->size != MIN_DICT_SIZE)) ||
00888             ((dict->size != MIN_DICT_SIZE) &&
00889          (dict->subdict->size == MIN_DICT_SIZE)))
00890         skey = xmlDictComputeKey(dict->subdict, name, l);
00891     else
00892         skey = okey;
00893 
00894     key = skey % dict->subdict->size;
00895     if (dict->subdict->dict[key].valid != 0) {
00896         xmlDictEntryPtr tmp;
00897 
00898         for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
00899          tmp = tmp->next) {
00900 #ifdef __GNUC__
00901         if ((tmp->okey == skey) && (tmp->len == l)) {
00902             if (!memcmp(tmp->name, name, l))
00903             return(tmp->name);
00904         }
00905 #else
00906         if ((tmp->okey == skey) && (tmp->len == l) &&
00907             (!xmlStrncmp(tmp->name, name, l)))
00908             return(tmp->name);
00909 #endif
00910         nbi++;
00911         }
00912 #ifdef __GNUC__
00913         if ((tmp->okey == skey) && (tmp->len == l)) {
00914         if (!memcmp(tmp->name, name, l))
00915             return(tmp->name);
00916         }
00917 #else
00918         if ((tmp->okey == skey) && (tmp->len == l) &&
00919         (!xmlStrncmp(tmp->name, name, l)))
00920         return(tmp->name);
00921 #endif
00922     }
00923     key = okey % dict->size;
00924     }
00925 
00926     ret = xmlDictAddString(dict, name, l);
00927     if (ret == NULL)
00928         return(NULL);
00929     if (insert == NULL) {
00930     entry = &(dict->dict[key]);
00931     } else {
00932     entry = xmlMalloc(sizeof(xmlDictEntry));
00933     if (entry == NULL)
00934          return(NULL);
00935     }
00936     entry->name = ret;
00937     entry->len = l;
00938     entry->next = NULL;
00939     entry->valid = 1;
00940     entry->okey = okey;
00941 
00942 
00943     if (insert != NULL)
00944     insert->next = entry;
00945 
00946     dict->nbElems++;
00947 
00948     if ((nbi > MAX_HASH_LEN) &&
00949         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
00950     if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
00951         return(NULL);
00952     }
00953     /* Note that entry may have been freed at this point by xmlDictGrow */
00954 
00955     return(ret);
00956 }
00957 
00958 /**
00959  * xmlDictExists:
00960  * @dict: the dictionnary
00961  * @name: the name of the userdata
00962  * @len: the length of the name, if -1 it is recomputed
00963  *
00964  * Check if the @name exists in the dictionnary @dict.
00965  *
00966  * Returns the internal copy of the name or NULL if not found.
00967  */
00968 const xmlChar *
00969 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
00970     unsigned long key, okey, nbi = 0;
00971     xmlDictEntryPtr insert;
00972     unsigned int l;
00973 
00974     if ((dict == NULL) || (name == NULL))
00975     return(NULL);
00976 
00977     if (len < 0)
00978         l = strlen((const char *) name);
00979     else
00980         l = len;
00981     if (((dict->limit > 0) && (l >= dict->limit)) ||
00982         (l > INT_MAX / 2))
00983         return(NULL);
00984 
00985     /*
00986      * Check for duplicate and insertion location.
00987      */
00988     okey = xmlDictComputeKey(dict, name, l);
00989     key = okey % dict->size;
00990     if (dict->dict[key].valid == 0) {
00991     insert = NULL;
00992     } else {
00993     for (insert = &(dict->dict[key]); insert->next != NULL;
00994          insert = insert->next) {
00995 #ifdef __GNUC__
00996         if ((insert->okey == okey) && (insert->len == l)) {
00997         if (!memcmp(insert->name, name, l))
00998             return(insert->name);
00999         }
01000 #else
01001         if ((insert->okey == okey) && (insert->len == l) &&
01002             (!xmlStrncmp(insert->name, name, l)))
01003         return(insert->name);
01004 #endif
01005         nbi++;
01006     }
01007 #ifdef __GNUC__
01008     if ((insert->okey == okey) && (insert->len == l)) {
01009         if (!memcmp(insert->name, name, l))
01010         return(insert->name);
01011     }
01012 #else
01013     if ((insert->okey == okey) && (insert->len == l) &&
01014         (!xmlStrncmp(insert->name, name, l)))
01015         return(insert->name);
01016 #endif
01017     }
01018 
01019     if (dict->subdict) {
01020         unsigned long skey;
01021 
01022         /* we cannot always reuse the same okey for the subdict */
01023         if (((dict->size == MIN_DICT_SIZE) &&
01024          (dict->subdict->size != MIN_DICT_SIZE)) ||
01025             ((dict->size != MIN_DICT_SIZE) &&
01026          (dict->subdict->size == MIN_DICT_SIZE)))
01027         skey = xmlDictComputeKey(dict->subdict, name, l);
01028     else
01029         skey = okey;
01030 
01031     key = skey % dict->subdict->size;
01032     if (dict->subdict->dict[key].valid != 0) {
01033         xmlDictEntryPtr tmp;
01034 
01035         for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
01036          tmp = tmp->next) {
01037 #ifdef __GNUC__
01038         if ((tmp->okey == skey) && (tmp->len == l)) {
01039             if (!memcmp(tmp->name, name, l))
01040             return(tmp->name);
01041         }
01042 #else
01043         if ((tmp->okey == skey) && (tmp->len == l) &&
01044             (!xmlStrncmp(tmp->name, name, l)))
01045             return(tmp->name);
01046 #endif
01047         nbi++;
01048         }
01049 #ifdef __GNUC__
01050         if ((tmp->okey == skey) && (tmp->len == l)) {
01051         if (!memcmp(tmp->name, name, l))
01052             return(tmp->name);
01053         }
01054 #else
01055         if ((tmp->okey == skey) && (tmp->len == l) &&
01056         (!xmlStrncmp(tmp->name, name, l)))
01057         return(tmp->name);
01058 #endif
01059     }
01060     }
01061 
01062     /* not found */
01063     return(NULL);
01064 }
01065 
01066 /**
01067  * xmlDictQLookup:
01068  * @dict: the dictionnary
01069  * @prefix: the prefix
01070  * @name: the name
01071  *
01072  * Add the QName @prefix:@name to the hash @dict if not present.
01073  *
01074  * Returns the internal copy of the QName or NULL in case of internal error
01075  */
01076 const xmlChar *
01077 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
01078     unsigned long okey, key, nbi = 0;
01079     xmlDictEntryPtr entry;
01080     xmlDictEntryPtr insert;
01081     const xmlChar *ret;
01082     unsigned int len, plen, l;
01083 
01084     if ((dict == NULL) || (name == NULL))
01085     return(NULL);
01086     if (prefix == NULL)
01087         return(xmlDictLookup(dict, name, -1));
01088 
01089     l = len = strlen((const char *) name);
01090     plen = strlen((const char *) prefix);
01091     len += 1 + plen;
01092 
01093     /*
01094      * Check for duplicate and insertion location.
01095      */
01096     okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
01097     key = okey % dict->size;
01098     if (dict->dict[key].valid == 0) {
01099     insert = NULL;
01100     } else {
01101     for (insert = &(dict->dict[key]); insert->next != NULL;
01102          insert = insert->next) {
01103         if ((insert->okey == okey) && (insert->len == len) &&
01104             (xmlStrQEqual(prefix, name, insert->name)))
01105         return(insert->name);
01106         nbi++;
01107     }
01108     if ((insert->okey == okey) && (insert->len == len) &&
01109         (xmlStrQEqual(prefix, name, insert->name)))
01110         return(insert->name);
01111     }
01112 
01113     if (dict->subdict) {
01114         unsigned long skey;
01115 
01116         /* we cannot always reuse the same okey for the subdict */
01117         if (((dict->size == MIN_DICT_SIZE) &&
01118          (dict->subdict->size != MIN_DICT_SIZE)) ||
01119             ((dict->size != MIN_DICT_SIZE) &&
01120          (dict->subdict->size == MIN_DICT_SIZE)))
01121         skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
01122     else
01123         skey = okey;
01124 
01125     key = skey % dict->subdict->size;
01126     if (dict->subdict->dict[key].valid != 0) {
01127         xmlDictEntryPtr tmp;
01128         for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
01129          tmp = tmp->next) {
01130         if ((tmp->okey == skey) && (tmp->len == len) &&
01131             (xmlStrQEqual(prefix, name, tmp->name)))
01132             return(tmp->name);
01133         nbi++;
01134         }
01135         if ((tmp->okey == skey) && (tmp->len == len) &&
01136         (xmlStrQEqual(prefix, name, tmp->name)))
01137         return(tmp->name);
01138     }
01139     key = okey % dict->size;
01140     }
01141 
01142     ret = xmlDictAddQString(dict, prefix, plen, name, l);
01143     if (ret == NULL)
01144         return(NULL);
01145     if (insert == NULL) {
01146     entry = &(dict->dict[key]);
01147     } else {
01148     entry = xmlMalloc(sizeof(xmlDictEntry));
01149     if (entry == NULL)
01150          return(NULL);
01151     }
01152     entry->name = ret;
01153     entry->len = len;
01154     entry->next = NULL;
01155     entry->valid = 1;
01156     entry->okey = okey;
01157 
01158     if (insert != NULL)
01159     insert->next = entry;
01160 
01161     dict->nbElems++;
01162 
01163     if ((nbi > MAX_HASH_LEN) &&
01164         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
01165     xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
01166     /* Note that entry may have been freed at this point by xmlDictGrow */
01167 
01168     return(ret);
01169 }
01170 
01171 /**
01172  * xmlDictOwns:
01173  * @dict: the dictionnary
01174  * @str: the string
01175  *
01176  * check if a string is owned by the disctionary
01177  *
01178  * Returns 1 if true, 0 if false and -1 in case of error
01179  * -1 in case of error
01180  */
01181 int
01182 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
01183     xmlDictStringsPtr pool;
01184 
01185     if ((dict == NULL) || (str == NULL))
01186     return(-1);
01187     pool = dict->strings;
01188     while (pool != NULL) {
01189         if ((str >= &pool->array[0]) && (str <= pool->free))
01190         return(1);
01191     pool = pool->next;
01192     }
01193     if (dict->subdict)
01194         return(xmlDictOwns(dict->subdict, str));
01195     return(0);
01196 }
01197 
01198 /**
01199  * xmlDictSize:
01200  * @dict: the dictionnary
01201  *
01202  * Query the number of elements installed in the hash @dict.
01203  *
01204  * Returns the number of elements in the dictionnary or
01205  * -1 in case of error
01206  */
01207 int
01208 xmlDictSize(xmlDictPtr dict) {
01209     if (dict == NULL)
01210     return(-1);
01211     if (dict->subdict)
01212         return(dict->nbElems + dict->subdict->nbElems);
01213     return(dict->nbElems);
01214 }
01215 
01216 /**
01217  * xmlDictSetLimit:
01218  * @dict: the dictionnary
01219  * @limit: the limit in bytes
01220  *
01221  * Set a size limit for the dictionary
01222  * Added in 2.9.0
01223  *
01224  * Returns the previous limit of the dictionary or 0
01225  */
01226 size_t
01227 xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
01228     size_t ret;
01229 
01230     if (dict == NULL)
01231     return(0);
01232     ret = dict->limit;
01233     dict->limit = limit;
01234     return(ret);
01235 }
01236 
01237 /**
01238  * xmlDictGetUsage:
01239  * @dict: the dictionnary
01240  *
01241  * Get how much memory is used by a dictionary for strings
01242  * Added in 2.9.0
01243  *
01244  * Returns the amount of strings allocated
01245  */
01246 size_t
01247 xmlDictGetUsage(xmlDictPtr dict) {
01248     xmlDictStringsPtr pool;
01249     size_t limit = 0;
01250 
01251     if (dict == NULL)
01252     return(0);
01253     pool = dict->strings;
01254     while (pool != NULL) {
01255         limit += pool->size;
01256     pool = pool->next;
01257     }
01258     return(limit);
01259 }
01260 
01261 #define bottom_dict
01262 #include "elfgcchack.h"
01263