dict.c

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