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