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 ((size_t)(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 ((size_t)(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         /* Falls through. */
 457         case 9: value += name[8];
 458         /* Falls through. */
 459         case 8: value += name[7];
 460         /* Falls through. */
 461         case 7: value += name[6];
 462         /* Falls through. */
 463         case 6: value += name[5];
 464         /* Falls through. */
 465         case 5: value += name[4];
 466         /* Falls through. */
 467         case 4: value += name[3];
 468         /* Falls through. */
 469         case 3: value += name[2];
 470         /* Falls through. */
 471         case 2: value += name[1];
 472         /* Falls through. */
 473         default: break;
 474     }
 475     return(value);
 476 }
 477
 478 /*
 479  * xmlDictComputeFastQKey:
 480  *
 481  * Calculate a hash key for two strings using a fast hash function
 482  * that works well for low hash table fill.
 483  *
 484  * Neither of the two strings must be NULL.
 485  */
 486 static unsigned long
 487 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
 488                        const xmlChar *name, int len, int seed)
 489 {
 490     unsigned long value = (unsigned long) seed;
 491
 492     if (plen == 0)
 493         value += 30 * (unsigned long) ':';
 494     else
 495         value += 30 * (*prefix);
 496
 497     if (len > 10) {
 498         int offset = len - (plen + 1 + 1);
 499         if (offset < 0)
 500             offset = len - (10 + 1);
 501         value += name[offset];
 502         len = 10;
 503         if (plen > 10)
 504             plen = 10;
 505     }
 506     switch (plen) {
 507         case 10: value += prefix[9];
 508         /* Falls through. */
 509         case 9: value += prefix[8];
 510         /* Falls through. */
 511         case 8: value += prefix[7];
 512         /* Falls through. */
 513         case 7: value += prefix[6];
 514         /* Falls through. */
 515         case 6: value += prefix[5];
 516         /* Falls through. */
 517         case 5: value += prefix[4];
 518         /* Falls through. */
 519         case 4: value += prefix[3];
 520         /* Falls through. */
 521         case 3: value += prefix[2];
 522         /* Falls through. */
 523         case 2: value += prefix[1];
 524         /* Falls through. */
 525         case 1: value += prefix[0];
 526         /* Falls through. */
 527         default: break;
 528     }
 529     len -= plen;
 530     if (len > 0) {
 531         value += (unsigned long) ':';
 532         len--;
 533     }
 534     switch (len) {
 535         case 10: value += name[9];
 536         /* Falls through. */
 537         case 9: value += name[8];
 538         /* Falls through. */
 539         case 8: value += name[7];
 540         /* Falls through. */
 541         case 7: value += name[6];
 542         /* Falls through. */
 543         case 6: value += name[5];
 544         /* Falls through. */
 545         case 5: value += name[4];
 546         /* Falls through. */
 547         case 4: value += name[3];
 548         /* Falls through. */
 549         case 3: value += name[2];
 550         /* Falls through. */
 551         case 2: value += name[1];
 552         /* Falls through. */
 553         case 1: value += name[0];
 554         /* Falls through. */
 555         default: break;
 556     }
 557     return(value);
 558 }
 559
 560 /**
 561  * xmlDictCreate:
 562  *
 563  * Create a new dictionary
 564  *
 565  * Returns the newly created dictionary, or NULL if an error occurred.
 566  */
 567 xmlDictPtr
 568 xmlDictCreate(void) {
 569     xmlDictPtr dict;
 570
 571     if (!xmlDictInitialized)
 572         if (!__xmlInitializeDict())
 573             return(NULL);
 574
 575 #ifdef DICT_DEBUG_PATTERNS
 576     fprintf(stderr, "C");
 577 #endif
 578
 579     dict = xmlMalloc(sizeof(xmlDict));
 580     if (dict) {
 581         dict->ref_counter = 1;
 582         dict->limit = 0;
 583
 584         dict->size = MIN_DICT_SIZE;
 585         dict->nbElems = 0;
 586         dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
 587         dict->strings = NULL;
 588         dict->subdict = NULL;
 589         if (dict->dict) {
 590             memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
 591 #ifdef DICT_RANDOMIZATION
 592             dict->seed = __xmlRandom();
 593 #else
 594             dict->seed = 0;
 595 #endif
 596             return(dict);
 597         }
 598         xmlFree(dict);
 599     }
 600     return(NULL);
 601 }
 602
 603 /**
 604  * xmlDictCreateSub:
 605  * @sub: an existing dictionary
 606  *
 607  * Create a new dictionary, inheriting strings from the read-only
 608  * dictionary @sub. On lookup, strings are first searched in the
 609  * new dictionary, then in @sub, and if not found are created in the
 610  * new dictionary.
 611  *
 612  * Returns the newly created dictionary, or NULL if an error occurred.
 613  */
 614 xmlDictPtr
 615 xmlDictCreateSub(xmlDictPtr sub) {
 616     xmlDictPtr dict = xmlDictCreate();
 617
 618     if ((dict != NULL) && (sub != NULL)) {
 619 #ifdef DICT_DEBUG_PATTERNS
 620         fprintf(stderr, "R");
 621 #endif
 622         dict->seed = sub->seed;
 623         dict->subdict = sub;
 624         xmlDictReference(dict->subdict);
 625     }
 626     return(dict);
 627 }
 628
 629 /**
 630  * xmlDictReference:
 631  * @dict: the dictionary
 632  *
 633  * Increment the reference counter of a dictionary
 634  *
 635  * Returns 0 in case of success and -1 in case of error
 636  */
 637 int
 638 xmlDictReference(xmlDictPtr dict) {
 639     if (!xmlDictInitialized)
 640         if (!__xmlInitializeDict())
 641             return(-1);
 642
 643     if (dict == NULL) return -1;
 644     xmlRMutexLock(xmlDictMutex);
 645     dict->ref_counter++;
 646     xmlRMutexUnlock(xmlDictMutex);
 647     return(0);
 648 }
 649
 650 /**
 651  * xmlDictGrow:
 652  * @dict: the dictionary
 653  * @size: the new size of the dictionary
 654  *
 655  * resize the dictionary
 656  *
 657  * Returns 0 in case of success, -1 in case of failure
 658  */
 659 static int
 660 xmlDictGrow(xmlDictPtr dict, size_t size) {
 661     unsigned long key, okey;
 662     size_t oldsize, i;
 663     xmlDictEntryPtr iter, next;
 664     struct _xmlDictEntry *olddict;
 665 #ifdef DEBUG_GROW
 666     unsigned long nbElem = 0;
 667 #endif
 668     int ret = 0;
 669     int keep_keys = 1;
 670
 671     if (dict == NULL)
 672         return(-1);
 673     if (size < 8)
 674         return(-1);
 675     if (size > 8 * 2048)
 676         return(-1);
 677
 678 #ifdef DICT_DEBUG_PATTERNS
 679     fprintf(stderr, "*");
 680 #endif
 681
 682     oldsize = dict->size;
 683     olddict = dict->dict;
 684     if (olddict == NULL)
 685         return(-1);
 686     if (oldsize == MIN_DICT_SIZE)
 687         keep_keys = 0;
 688
 689     dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
 690     if (dict->dict == NULL) {
 691         dict->dict = olddict;
 692         return(-1);
 693     }
 694     memset(dict->dict, 0, size * sizeof(xmlDictEntry));
 695     dict->size = size;
 696
 697     /*  If the two loops are merged, there would be situations where
 698         a new entry needs to allocated and data copied into it from
 699         the main dict. It is nicer to run through the array twice, first
 700         copying all the elements in the main array (less probability of
 701         allocate) and then the rest, so we only free in the second loop.
 702     */
 703     for (i = 0; i < oldsize; i++) {
 704         if (olddict[i].valid == 0)
 705             continue;
 706
 707         if (keep_keys)
 708             okey = olddict[i].okey;
 709         else
 710             okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
 711         key = okey % dict->size;
 712
 713         if (dict->dict[key].valid == 0) {
 714             memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
 715             dict->dict[key].next = NULL;
 716             dict->dict[key].okey = okey;
 717         } else {
 718             xmlDictEntryPtr entry;
 719
 720             entry = xmlMalloc(sizeof(xmlDictEntry));
 721             if (entry != NULL) {
 722                 entry->name = olddict[i].name;
 723                 entry->len = olddict[i].len;
 724                 entry->okey = okey;
 725                 entry->next = dict->dict[key].next;
 726                 entry->valid = 1;
 727                 dict->dict[key].next = entry;
 728             } else {
 729                 /*
 730                  * we don't have much ways to alert from herei
 731                  * result is losing an entry and unicity guarantee
 732                  */
 733                 ret = -1;
 734             }
 735         }
 736 #ifdef DEBUG_GROW
 737         nbElem++;
 738 #endif
 739     }
 740
 741     for (i = 0; i < oldsize; i++) {
 742         iter = olddict[i].next;
 743         while (iter) {
 744             next = iter->next;
 745
 746             /*
 747              * put back the entry in the new dict
 748              */
 749
 750             if (keep_keys)
 751                 okey = iter->okey;
 752             else
 753                 okey = xmlDictComputeKey(dict, iter->name, iter->len);
 754             key = okey % dict->size;
 755             if (dict->dict[key].valid == 0) {
 756                 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
 757                 dict->dict[key].next = NULL;
 758                 dict->dict[key].valid = 1;
 759                 dict->dict[key].okey = okey;
 760                 xmlFree(iter);
 761             } else {
 762                 iter->next = dict->dict[key].next;
 763                 iter->okey = okey;
 764                 dict->dict[key].next = iter;
 765             }
 766
 767 #ifdef DEBUG_GROW
 768             nbElem++;
 769 #endif
 770
 771             iter = next;
 772         }
 773     }
 774
 775     xmlFree(olddict);
 776
 777 #ifdef DEBUG_GROW
 778     xmlGenericError(xmlGenericErrorContext,
 779             "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
 780 #endif
 781
 782     return(ret);
 783 }
 784
 785 /**
 786  * xmlDictFree:
 787  * @dict: the dictionary
 788  *
 789  * Free the hash @dict and its contents. The userdata is
 790  * deallocated with @f if provided.
 791  */
 792 void
 793 xmlDictFree(xmlDictPtr dict) {
 794     size_t i;
 795     xmlDictEntryPtr iter;
 796     xmlDictEntryPtr next;
 797     int inside_dict = 0;
 798     xmlDictStringsPtr pool, nextp;
 799
 800     if (dict == NULL)
 801         return;
 802
 803     if (!xmlDictInitialized)
 804         if (!__xmlInitializeDict())
 805             return;
 806
 807     /* decrement the counter, it may be shared by a parser and docs */
 808     xmlRMutexLock(xmlDictMutex);
 809     dict->ref_counter--;
 810     if (dict->ref_counter > 0) {
 811         xmlRMutexUnlock(xmlDictMutex);
 812         return;
 813     }
 814
 815     xmlRMutexUnlock(xmlDictMutex);
 816
 817     if (dict->subdict != NULL) {
 818         xmlDictFree(dict->subdict);
 819     }
 820
 821     if (dict->dict) {
 822         for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
 823             iter = &(dict->dict[i]);
 824             if (iter->valid == 0)
 825                 continue;
 826             inside_dict = 1;
 827             while (iter) {
 828                 next = iter->next;
 829                 if (!inside_dict)
 830                     xmlFree(iter);
 831                 dict->nbElems--;
 832                 inside_dict = 0;
 833                 iter = next;
 834             }
 835         }
 836         xmlFree(dict->dict);
 837     }
 838     pool = dict->strings;
 839     while (pool != NULL) {
 840         nextp = pool->next;
 841         xmlFree(pool);
 842         pool = nextp;
 843     }
 844     xmlFree(dict);
 845 }
 846
 847 /**
 848  * xmlDictLookup:
 849  * @dict: the dictionary
 850  * @name: the name of the userdata
 851  * @len: the length of the name, if -1 it is recomputed
 852  *
 853  * Add the @name to the dictionary @dict if not present.
 854  *
 855  * Returns the internal copy of the name or NULL in case of internal error
 856  */
 857 const xmlChar *
 858 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
 859     unsigned long key, okey, nbi = 0;
 860     xmlDictEntryPtr entry;
 861     xmlDictEntryPtr insert;
 862     const xmlChar *ret;
 863     unsigned int l;
 864
 865     if ((dict == NULL) || (name == NULL))
 866         return(NULL);
 867
 868     if (len < 0)
 869         l = strlen((const char *) name);
 870     else
 871         l = len;
 872
 873     if (((dict->limit > 0) && (l >= dict->limit)) ||
 874         (l > INT_MAX / 2))
 875         return(NULL);
 876
 877     /*
 878      * Check for duplicate and insertion location.
 879      */
 880     okey = xmlDictComputeKey(dict, name, l);
 881     key = okey % dict->size;
 882     if (dict->dict[key].valid == 0) {
 883         insert = NULL;
 884     } else {
 885         for (insert = &(dict->dict[key]); insert->next != NULL;
 886              insert = insert->next) {
 887 #ifdef __GNUC__
 888             if ((insert->okey == okey) && (insert->len == l)) {
 889                 if (!memcmp(insert->name, name, l))
 890                     return(insert->name);
 891             }
 892 #else
 893             if ((insert->okey == okey) && (insert->len == l) &&
 894                 (!xmlStrncmp(insert->name, name, l)))
 895                 return(insert->name);
 896 #endif
 897             nbi++;
 898         }
 899 #ifdef __GNUC__
 900         if ((insert->okey == okey) && (insert->len == l)) {
 901             if (!memcmp(insert->name, name, l))
 902                 return(insert->name);
 903         }
 904 #else
 905         if ((insert->okey == okey) && (insert->len == l) &&
 906             (!xmlStrncmp(insert->name, name, l)))
 907             return(insert->name);
 908 #endif
 909     }
 910
 911     if (dict->subdict) {
 912         unsigned long skey;
 913
 914         /* we cannot always reuse the same okey for the subdict */
 915         if (((dict->size == MIN_DICT_SIZE) &&
 916              (dict->subdict->size != MIN_DICT_SIZE)) ||
 917             ((dict->size != MIN_DICT_SIZE) &&
 918              (dict->subdict->size == MIN_DICT_SIZE)))
 919             skey = xmlDictComputeKey(dict->subdict, name, l);
 920         else
 921             skey = okey;
 922
 923         key = skey % dict->subdict->size;
 924         if (dict->subdict->dict[key].valid != 0) {
 925             xmlDictEntryPtr tmp;
 926
 927             for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
 928                  tmp = tmp->next) {
 929 #ifdef __GNUC__
 930                 if ((tmp->okey == skey) && (tmp->len == l)) {
 931                     if (!memcmp(tmp->name, name, l))
 932                         return(tmp->name);
 933                 }
 934 #else
 935                 if ((tmp->okey == skey) && (tmp->len == l) &&
 936                     (!xmlStrncmp(tmp->name, name, l)))
 937                     return(tmp->name);
 938 #endif
 939                 nbi++;
 940             }
 941 #ifdef __GNUC__
 942             if ((tmp->okey == skey) && (tmp->len == l)) {
 943                 if (!memcmp(tmp->name, name, l))
 944                     return(tmp->name);
 945             }
 946 #else
 947             if ((tmp->okey == skey) && (tmp->len == l) &&
 948                 (!xmlStrncmp(tmp->name, name, l)))
 949                 return(tmp->name);
 950 #endif
 951         }
 952         key = okey % dict->size;
 953     }
 954
 955     ret = xmlDictAddString(dict, name, l);
 956     if (ret == NULL)
 957         return(NULL);
 958     if (insert == NULL) {
 959         entry = &(dict->dict[key]);
 960     } else {
 961         entry = xmlMalloc(sizeof(xmlDictEntry));
 962         if (entry == NULL)
 963              return(NULL);
 964     }
 965     entry->name = ret;
 966     entry->len = l;
 967     entry->next = NULL;
 968     entry->valid = 1;
 969     entry->okey = okey;
 970
 971
 972     if (insert != NULL)
 973         insert->next = entry;
 974
 975     dict->nbElems++;
 976
 977     if ((nbi > MAX_HASH_LEN) &&
 978         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
 979         if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
 980             return(NULL);
 981     }
 982     /* Note that entry may have been freed at this point by xmlDictGrow */
 983
 984     return(ret);
 985 }
 986
 987 /**
 988  * xmlDictExists:
 989  * @dict: the dictionary
 990  * @name: the name of the userdata
 991  * @len: the length of the name, if -1 it is recomputed
 992  *
 993  * Check if the @name exists in the dictionary @dict.
 994  *
 995  * Returns the internal copy of the name or NULL if not found.
 996  */
 997 const xmlChar *
 998 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
 999     unsigned long key, okey, nbi = 0;
1000     xmlDictEntryPtr insert;
1001     unsigned int l;
1002
1003     if ((dict == NULL) || (name == NULL))
1004         return(NULL);
1005
1006     if (len < 0)
1007         l = strlen((const char *) name);
1008     else
1009         l = len;
1010     if (((dict->limit > 0) && (l >= dict->limit)) ||
1011         (l > INT_MAX / 2))
1012         return(NULL);
1013
1014     /*
1015      * Check for duplicate and insertion location.
1016      */
1017     okey = xmlDictComputeKey(dict, name, l);
1018     key = okey % dict->size;
1019     if (dict->dict[key].valid == 0) {
1020         insert = NULL;
1021     } else {
1022         for (insert = &(dict->dict[key]); insert->next != NULL;
1023              insert = insert->next) {
1024 #ifdef __GNUC__
1025             if ((insert->okey == okey) && (insert->len == l)) {
1026                 if (!memcmp(insert->name, name, l))
1027                     return(insert->name);
1028             }
1029 #else
1030             if ((insert->okey == okey) && (insert->len == l) &&
1031                 (!xmlStrncmp(insert->name, name, l)))
1032                 return(insert->name);
1033 #endif
1034             nbi++;
1035         }
1036 #ifdef __GNUC__
1037         if ((insert->okey == okey) && (insert->len == l)) {
1038             if (!memcmp(insert->name, name, l))
1039                 return(insert->name);
1040         }
1041 #else
1042         if ((insert->okey == okey) && (insert->len == l) &&
1043             (!xmlStrncmp(insert->name, name, l)))
1044             return(insert->name);
1045 #endif
1046     }
1047
1048     if (dict->subdict) {
1049         unsigned long skey;
1050
1051         /* we cannot always reuse the same okey for the subdict */
1052         if (((dict->size == MIN_DICT_SIZE) &&
1053              (dict->subdict->size != MIN_DICT_SIZE)) ||
1054             ((dict->size != MIN_DICT_SIZE) &&
1055              (dict->subdict->size == MIN_DICT_SIZE)))
1056             skey = xmlDictComputeKey(dict->subdict, name, l);
1057         else
1058             skey = okey;
1059
1060         key = skey % dict->subdict->size;
1061         if (dict->subdict->dict[key].valid != 0) {
1062             xmlDictEntryPtr tmp;
1063
1064             for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1065                  tmp = tmp->next) {
1066 #ifdef __GNUC__
1067                 if ((tmp->okey == skey) && (tmp->len == l)) {
1068                     if (!memcmp(tmp->name, name, l))
1069                         return(tmp->name);
1070                 }
1071 #else
1072                 if ((tmp->okey == skey) && (tmp->len == l) &&
1073                     (!xmlStrncmp(tmp->name, name, l)))
1074                     return(tmp->name);
1075 #endif
1076                 nbi++;
1077             }
1078 #ifdef __GNUC__
1079             if ((tmp->okey == skey) && (tmp->len == l)) {
1080                 if (!memcmp(tmp->name, name, l))
1081                     return(tmp->name);
1082             }
1083 #else
1084             if ((tmp->okey == skey) && (tmp->len == l) &&
1085                 (!xmlStrncmp(tmp->name, name, l)))
1086                 return(tmp->name);
1087 #endif
1088         }
1089     }
1090
1091     /* not found */
1092     return(NULL);
1093 }
1094
1095 /**
1096  * xmlDictQLookup:
1097  * @dict: the dictionary
1098  * @prefix: the prefix
1099  * @name: the name
1100  *
1101  * Add the QName @prefix:@name to the hash @dict if not present.
1102  *
1103  * Returns the internal copy of the QName or NULL in case of internal error
1104  */
1105 const xmlChar *
1106 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
1107     unsigned long okey, key, nbi = 0;
1108     xmlDictEntryPtr entry;
1109     xmlDictEntryPtr insert;
1110     const xmlChar *ret;
1111     unsigned int len, plen, l;
1112
1113     if ((dict == NULL) || (name == NULL))
1114         return(NULL);
1115     if (prefix == NULL)
1116         return(xmlDictLookup(dict, name, -1));
1117
1118     l = len = strlen((const char *) name);
1119     plen = strlen((const char *) prefix);
1120     len += 1 + plen;
1121
1122     /*
1123      * Check for duplicate and insertion location.
1124      */
1125     okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1126     key = okey % dict->size;
1127     if (dict->dict[key].valid == 0) {
1128         insert = NULL;
1129     } else {
1130         for (insert = &(dict->dict[key]); insert->next != NULL;
1131              insert = insert->next) {
1132             if ((insert->okey == okey) && (insert->len == len) &&
1133                 (xmlStrQEqual(prefix, name, insert->name)))
1134                 return(insert->name);
1135             nbi++;
1136         }
1137         if ((insert->okey == okey) && (insert->len == len) &&
1138             (xmlStrQEqual(prefix, name, insert->name)))
1139             return(insert->name);
1140     }
1141
1142     if (dict->subdict) {
1143         unsigned long skey;
1144
1145         /* we cannot always reuse the same okey for the subdict */
1146         if (((dict->size == MIN_DICT_SIZE) &&
1147              (dict->subdict->size != MIN_DICT_SIZE)) ||
1148             ((dict->size != MIN_DICT_SIZE) &&
1149              (dict->subdict->size == MIN_DICT_SIZE)))
1150             skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1151         else
1152             skey = okey;
1153
1154         key = skey % dict->subdict->size;
1155         if (dict->subdict->dict[key].valid != 0) {
1156             xmlDictEntryPtr tmp;
1157             for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1158                  tmp = tmp->next) {
1159                 if ((tmp->okey == skey) && (tmp->len == len) &&
1160                     (xmlStrQEqual(prefix, name, tmp->name)))
1161                     return(tmp->name);
1162                 nbi++;
1163             }
1164             if ((tmp->okey == skey) && (tmp->len == len) &&
1165                 (xmlStrQEqual(prefix, name, tmp->name)))
1166                 return(tmp->name);
1167         }
1168         key = okey % dict->size;
1169     }
1170
1171     ret = xmlDictAddQString(dict, prefix, plen, name, l);
1172     if (ret == NULL)
1173         return(NULL);
1174     if (insert == NULL) {
1175         entry = &(dict->dict[key]);
1176     } else {
1177         entry = xmlMalloc(sizeof(xmlDictEntry));
1178         if (entry == NULL)
1179              return(NULL);
1180     }
1181     entry->name = ret;
1182     entry->len = len;
1183     entry->next = NULL;
1184     entry->valid = 1;
1185     entry->okey = okey;
1186
1187     if (insert != NULL)
1188         insert->next = entry;
1189
1190     dict->nbElems++;
1191
1192     if ((nbi > MAX_HASH_LEN) &&
1193         (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1194         xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1195     /* Note that entry may have been freed at this point by xmlDictGrow */
1196
1197     return(ret);
1198 }
1199
1200 /**
1201  * xmlDictOwns:
1202  * @dict: the dictionary
1203  * @str: the string
1204  *
1205  * check if a string is owned by the disctionary
1206  *
1207  * Returns 1 if true, 0 if false and -1 in case of error
1208  * -1 in case of error
1209  */
1210 int
1211 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1212     xmlDictStringsPtr pool;
1213
1214     if ((dict == NULL) || (str == NULL))
1215         return(-1);
1216     pool = dict->strings;
1217     while (pool != NULL) {
1218         if ((str >= &pool->array[0]) && (str <= pool->free))
1219             return(1);
1220         pool = pool->next;
1221     }
1222     if (dict->subdict)
1223         return(xmlDictOwns(dict->subdict, str));
1224     return(0);
1225 }
1226
1227 /**
1228  * xmlDictSize:
1229  * @dict: the dictionary
1230  *
1231  * Query the number of elements installed in the hash @dict.
1232  *
1233  * Returns the number of elements in the dictionary or
1234  * -1 in case of error
1235  */
1236 int
1237 xmlDictSize(xmlDictPtr dict) {
1238     if (dict == NULL)
1239         return(-1);
1240     if (dict->subdict)
1241         return(dict->nbElems + dict->subdict->nbElems);
1242     return(dict->nbElems);
1243 }
1244
1245 /**
1246  * xmlDictSetLimit:
1247  * @dict: the dictionary
1248  * @limit: the limit in bytes
1249  *
1250  * Set a size limit for the dictionary
1251  * Added in 2.9.0
1252  *
1253  * Returns the previous limit of the dictionary or 0
1254  */
1255 size_t
1256 xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1257     size_t ret;
1258
1259     if (dict == NULL)
1260         return(0);
1261     ret = dict->limit;
1262     dict->limit = limit;
1263     return(ret);
1264 }
1265
1266 /**
1267  * xmlDictGetUsage:
1268  * @dict: the dictionary
1269  *
1270  * Get how much memory is used by a dictionary for strings
1271  * Added in 2.9.0
1272  *
1273  * Returns the amount of strings allocated
1274  */
1275 size_t
1276 xmlDictGetUsage(xmlDictPtr dict) {
1277     xmlDictStringsPtr pool;
1278     size_t limit = 0;
1279
1280     if (dict == NULL)
1281         return(0);
1282     pool = dict->strings;
1283     while (pool != NULL) {
1284         limit += pool->size;
1285         pool = pool->next;
1286     }
1287     return(limit);
1288 }
1289
1290 #define bottom_dict
1291 #include "elfgcchack.h"