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