dict.c

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