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