libs/xml2/hash.c

   1 /*
   2  * hash.c: chained hash tables
   3  *
   4  * Reference: Your favorite introductory book on algorithms
   5  *
   6  * Copyright (C) 2000,2012 Bjorn Reese and Daniel Veillard.
   7  *
   8  * Permission to use, copy, modify, and distribute this software for any
   9  * purpose with or without fee is hereby granted, provided that the above
  10  * copyright notice and this permission notice appear in all copies.
  11  *
  12  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  13  * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  14  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
  15  * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
  16  *
  17  * Author: breese@users.sourceforge.net
  18  */
  19
  20 #define IN_LIBXML
  21 #include "libxml.h"
  22
  23 #include <string.h>
  24 #ifdef HAVE_STDLIB_H
  25 #include <stdlib.h>
  26 #endif
  27 #ifdef HAVE_TIME_H
  28 #include <time.h>
  29 #endif
  30
  31 /*
  32  * Following http://www.ocert.org/advisories/ocert-2011-003.html
  33  * it seems that having hash randomization might be a good idea
  34  * when using XML with untrusted data
  35  */
  36 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME) && \
  37     !defined(FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION)
  38 #define HASH_RANDOMIZATION
  39 #endif
  40
  41 #include <libxml/parser.h>
  42 #include <libxml/hash.h>
  43 #include <libxml/xmlmemory.h>
  44 #include <libxml/xmlerror.h>
  45 #include <libxml/globals.h>
  46
  47 #define MAX_HASH_LEN 8
  48
  49 /* #define DEBUG_GROW */
  50
  51 /*
  52  * A single entry in the hash table
  53  */
  54 typedef struct _xmlHashEntry xmlHashEntry;
  55 typedef xmlHashEntry *xmlHashEntryPtr;
  56 struct _xmlHashEntry {
  57     struct _xmlHashEntry *next;
  58     xmlChar *name;
  59     xmlChar *name2;
  60     xmlChar *name3;
  61     void *payload;
  62     int valid;
  63 };
  64
  65 /*
  66  * The entire hash table
  67  */
  68 struct _xmlHashTable {
  69     struct _xmlHashEntry *table;
  70     int size;
  71     int nbElems;
  72     xmlDictPtr dict;
  73 #ifdef HASH_RANDOMIZATION
  74     int random_seed;
  75 #endif
  76 };
  77
  78 /*
  79  * xmlHashComputeKey:
  80  * Calculate the hash key
  81  */
  82 #ifdef __clang__
  83 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
  84 #endif
  85 static unsigned long
  86 xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
  87                   const xmlChar *name2, const xmlChar *name3) {
  88     unsigned long value = 0L;
  89     char ch;
  90
  91 #ifdef HASH_RANDOMIZATION
  92     value = table->random_seed;
  93 #endif
  94     if (name != NULL) {
  95         value += 30 * (*name);
  96         while ((ch = *name++) != 0) {
  97             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
  98         }
  99     }
 100     value = value ^ ((value << 5) + (value >> 3));
 101     if (name2 != NULL) {
 102         while ((ch = *name2++) != 0) {
 103             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 104         }
 105     }
 106     value = value ^ ((value << 5) + (value >> 3));
 107     if (name3 != NULL) {
 108         while ((ch = *name3++) != 0) {
 109             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 110         }
 111     }
 112     return (value % table->size);
 113 }
 114
 115 #ifdef __clang__
 116 ATTRIBUTE_NO_SANITIZE("unsigned-integer-overflow")
 117 #endif
 118 static unsigned long
 119 xmlHashComputeQKey(xmlHashTablePtr table,
 120                    const xmlChar *prefix, const xmlChar *name,
 121                    const xmlChar *prefix2, const xmlChar *name2,
 122                    const xmlChar *prefix3, const xmlChar *name3) {
 123     unsigned long value = 0L;
 124     char ch;
 125
 126 #ifdef HASH_RANDOMIZATION
 127     value = table->random_seed;
 128 #endif
 129     if (prefix != NULL)
 130         value += 30 * (*prefix);
 131     else
 132         value += 30 * (*name);
 133
 134     if (prefix != NULL) {
 135         while ((ch = *prefix++) != 0) {
 136             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 137         }
 138         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
 139     }
 140     if (name != NULL) {
 141         while ((ch = *name++) != 0) {
 142             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 143         }
 144     }
 145     value = value ^ ((value << 5) + (value >> 3));
 146     if (prefix2 != NULL) {
 147         while ((ch = *prefix2++) != 0) {
 148             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 149         }
 150         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
 151     }
 152     if (name2 != NULL) {
 153         while ((ch = *name2++) != 0) {
 154             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 155         }
 156     }
 157     value = value ^ ((value << 5) + (value >> 3));
 158     if (prefix3 != NULL) {
 159         while ((ch = *prefix3++) != 0) {
 160             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 161         }
 162         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
 163     }
 164     if (name3 != NULL) {
 165         while ((ch = *name3++) != 0) {
 166             value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
 167         }
 168     }
 169     return (value % table->size);
 170 }
 171
 172 /**
 173  * xmlHashCreate:
 174  * @size: the size of the hash table
 175  *
 176  * Create a new xmlHashTablePtr.
 177  *
 178  * Returns the newly created object, or NULL if an error occurred.
 179  */
 180 xmlHashTablePtr
 181 xmlHashCreate(int size) {
 182     xmlHashTablePtr table;
 183
 184     if (size <= 0)
 185         size = 256;
 186
 187     table = xmlMalloc(sizeof(xmlHashTable));
 188     if (table) {
 189         table->dict = NULL;
 190         table->size = size;
 191         table->nbElems = 0;
 192         table->table = xmlMalloc(size * sizeof(xmlHashEntry));
 193         if (table->table) {
 194             memset(table->table, 0, size * sizeof(xmlHashEntry));
 195 #ifdef HASH_RANDOMIZATION
 196             table->random_seed = __xmlRandom();
 197 #endif
 198             return(table);
 199         }
 200         xmlFree(table);
 201     }
 202     return(NULL);
 203 }
 204
 205 /**
 206  * xmlHashCreateDict:
 207  * @size: the size of the hash table
 208  * @dict: a dictionary to use for the hash
 209  *
 210  * Create a new xmlHashTablePtr which will use @dict as the internal dictionary
 211  *
 212  * Returns the newly created object, or NULL if an error occurred.
 213  */
 214 xmlHashTablePtr
 215 xmlHashCreateDict(int size, xmlDictPtr dict) {
 216     xmlHashTablePtr table;
 217
 218     table = xmlHashCreate(size);
 219     if (table != NULL) {
 220         table->dict = dict;
 221         xmlDictReference(dict);
 222     }
 223     return(table);
 224 }
 225
 226 /**
 227  * xmlHashGrow:
 228  * @table: the hash table
 229  * @size: the new size of the hash table
 230  *
 231  * resize the hash table
 232  *
 233  * Returns 0 in case of success, -1 in case of failure
 234  */
 235 static int
 236 xmlHashGrow(xmlHashTablePtr table, int size) {
 237     unsigned long key;
 238     int oldsize, i;
 239     xmlHashEntryPtr iter, next;
 240     struct _xmlHashEntry *oldtable;
 241 #ifdef DEBUG_GROW
 242     unsigned long nbElem = 0;
 243 #endif
 244
 245     if (table == NULL)
 246         return(-1);
 247     if (size < 8)
 248         return(-1);
 249     if (size > 8 * 2048)
 250         return(-1);
 251
 252     oldsize = table->size;
 253     oldtable = table->table;
 254     if (oldtable == NULL)
 255         return(-1);
 256
 257     table->table = xmlMalloc(size * sizeof(xmlHashEntry));
 258     if (table->table == NULL) {
 259         table->table = oldtable;
 260         return(-1);
 261     }
 262     memset(table->table, 0, size * sizeof(xmlHashEntry));
 263     table->size = size;
 264
 265     /*  If the two loops are merged, there would be situations where
 266         a new entry needs to allocated and data copied into it from
 267         the main table. So instead, we run through the array twice, first
 268         copying all the elements in the main array (where we can't get
 269         conflicts) and then the rest, so we only free (and don't allocate)
 270     */
 271     for (i = 0; i < oldsize; i++) {
 272         if (oldtable[i].valid == 0)
 273             continue;
 274         key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
 275                                 oldtable[i].name3);
 276         memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
 277         table->table[key].next = NULL;
 278     }
 279
 280     for (i = 0; i < oldsize; i++) {
 281         iter = oldtable[i].next;
 282         while (iter) {
 283             next = iter->next;
 284
 285             /*
 286              * put back the entry in the new table
 287              */
 288
 289             key = xmlHashComputeKey(table, iter->name, iter->name2,
 290                                     iter->name3);
 291             if (table->table[key].valid == 0) {
 292                 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
 293                 table->table[key].next = NULL;
 294                 xmlFree(iter);
 295             } else {
 296                 iter->next = table->table[key].next;
 297                 table->table[key].next = iter;
 298             }
 299
 300 #ifdef DEBUG_GROW
 301             nbElem++;
 302 #endif
 303
 304             iter = next;
 305         }
 306     }
 307
 308     xmlFree(oldtable);
 309
 310 #ifdef DEBUG_GROW
 311     xmlGenericError(xmlGenericErrorContext,
 312             "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
 313 #endif
 314
 315     return(0);
 316 }
 317
 318 /**
 319  * xmlHashFree:
 320  * @table: the hash table
 321  * @f:  the deallocator function for items in the hash
 322  *
 323  * Free the hash @table and its contents. The userdata is
 324  * deallocated with @f if provided.
 325  */
 326 void
 327 xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
 328     int i;
 329     xmlHashEntryPtr iter;
 330     xmlHashEntryPtr next;
 331     int inside_table = 0;
 332     int nbElems;
 333
 334     if (table == NULL)
 335         return;
 336     if (table->table) {
 337         nbElems = table->nbElems;
 338         for(i = 0; (i < table->size) && (nbElems > 0); i++) {
 339             iter = &(table->table[i]);
 340             if (iter->valid == 0)
 341                 continue;
 342             inside_table = 1;
 343             while (iter) {
 344                 next = iter->next;
 345                 if ((f != NULL) && (iter->payload != NULL))
 346                     f(iter->payload, iter->name);
 347                 if (table->dict == NULL) {
 348                     if (iter->name)
 349                         xmlFree(iter->name);
 350                     if (iter->name2)
 351                         xmlFree(iter->name2);
 352                     if (iter->name3)
 353                         xmlFree(iter->name3);
 354                 }
 355                 iter->payload = NULL;
 356                 if (!inside_table)
 357                     xmlFree(iter);
 358                 nbElems--;
 359                 inside_table = 0;
 360                 iter = next;
 361             }
 362         }
 363         xmlFree(table->table);
 364     }
 365     if (table->dict)
 366         xmlDictFree(table->dict);
 367     xmlFree(table);
 368 }
 369
 370 /**
 371  * xmlHashDefaultDeallocator:
 372  * @entry: the hash table entry
 373  * @name: the entry's name
 374  *
 375  * Free a hash table entry with xmlFree.
 376  */
 377 void
 378 xmlHashDefaultDeallocator(void *entry, const xmlChar *name ATTRIBUTE_UNUSED) {
 379     xmlFree(entry);
 380 }
 381
 382 /**
 383  * xmlHashAddEntry:
 384  * @table: the hash table
 385  * @name: the name of the userdata
 386  * @userdata: a pointer to the userdata
 387  *
 388  * Add the @userdata to the hash @table. This can later be retrieved
 389  * by using the @name. Duplicate names generate errors.
 390  *
 391  * Returns 0 the addition succeeded and -1 in case of error.
 392  */
 393 int
 394 xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
 395     return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
 396 }
 397
 398 /**
 399  * xmlHashAddEntry2:
 400  * @table: the hash table
 401  * @name: the name of the userdata
 402  * @name2: a second name of the userdata
 403  * @userdata: a pointer to the userdata
 404  *
 405  * Add the @userdata to the hash @table. This can later be retrieved
 406  * by using the (@name, @name2) tuple. Duplicate tuples generate errors.
 407  *
 408  * Returns 0 the addition succeeded and -1 in case of error.
 409  */
 410 int
 411 xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
 412                 const xmlChar *name2, void *userdata) {
 413     return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
 414 }
 415
 416 /**
 417  * xmlHashUpdateEntry:
 418  * @table: the hash table
 419  * @name: the name of the userdata
 420  * @userdata: a pointer to the userdata
 421  * @f: the deallocator function for replaced item (if any)
 422  *
 423  * Add the @userdata to the hash @table. This can later be retrieved
 424  * by using the @name. Existing entry for this @name will be removed
 425  * and freed with @f if found.
 426  *
 427  * Returns 0 the addition succeeded and -1 in case of error.
 428  */
 429 int
 430 xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
 431                    void *userdata, xmlHashDeallocator f) {
 432     return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
 433 }
 434
 435 /**
 436  * xmlHashUpdateEntry2:
 437  * @table: the hash table
 438  * @name: the name of the userdata
 439  * @name2: a second name of the userdata
 440  * @userdata: a pointer to the userdata
 441  * @f: the deallocator function for replaced item (if any)
 442  *
 443  * Add the @userdata to the hash @table. This can later be retrieved
 444  * by using the (@name, @name2) tuple. Existing entry for this tuple will
 445  * be removed and freed with @f if found.
 446  *
 447  * Returns 0 the addition succeeded and -1 in case of error.
 448  */
 449 int
 450 xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
 451                    const xmlChar *name2, void *userdata,
 452                    xmlHashDeallocator f) {
 453     return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
 454 }
 455
 456 /**
 457  * xmlHashLookup:
 458  * @table: the hash table
 459  * @name: the name of the userdata
 460  *
 461  * Find the userdata specified by the @name.
 462  *
 463  * Returns the pointer to the userdata
 464  */
 465 void *
 466 xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
 467     return(xmlHashLookup3(table, name, NULL, NULL));
 468 }
 469
 470 /**
 471  * xmlHashLookup2:
 472  * @table: the hash table
 473  * @name: the name of the userdata
 474  * @name2: a second name of the userdata
 475  *
 476  * Find the userdata specified by the (@name, @name2) tuple.
 477  *
 478  * Returns the pointer to the userdata
 479  */
 480 void *
 481 xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
 482               const xmlChar *name2) {
 483     return(xmlHashLookup3(table, name, name2, NULL));
 484 }
 485
 486 /**
 487  * xmlHashQLookup:
 488  * @table: the hash table
 489  * @prefix: the prefix of the userdata
 490  * @name: the name of the userdata
 491  *
 492  * Find the userdata specified by the QName @prefix:@name/@name.
 493  *
 494  * Returns the pointer to the userdata
 495  */
 496 void *
 497 xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
 498                const xmlChar *name) {
 499     return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
 500 }
 501
 502 /**
 503  * xmlHashQLookup2:
 504  * @table: the hash table
 505  * @prefix: the prefix of the userdata
 506  * @name: the name of the userdata
 507  * @prefix2: the second prefix of the userdata
 508  * @name2: a second name of the userdata
 509  *
 510  * Find the userdata specified by the QNames tuple
 511  *
 512  * Returns the pointer to the userdata
 513  */
 514 void *
 515 xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
 516                 const xmlChar *name, const xmlChar *prefix2,
 517                 const xmlChar *name2) {
 518     return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
 519 }
 520
 521 /**
 522  * xmlHashAddEntry3:
 523  * @table: the hash table
 524  * @name: the name of the userdata
 525  * @name2: a second name of the userdata
 526  * @name3: a third name of the userdata
 527  * @userdata: a pointer to the userdata
 528  *
 529  * Add the @userdata to the hash @table. This can later be retrieved
 530  * by using the tuple (@name, @name2, @name3). Duplicate entries generate
 531  * errors.
 532  *
 533  * Returns 0 the addition succeeded and -1 in case of error.
 534  */
 535 int
 536 xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
 537                  const xmlChar *name2, const xmlChar *name3,
 538                  void *userdata) {
 539     unsigned long key, len = 0;
 540     xmlHashEntryPtr entry;
 541     xmlHashEntryPtr insert;
 542
 543     if ((table == NULL) || (name == NULL))
 544         return(-1);
 545
 546     /*
 547      * If using a dict internalize if needed
 548      */
 549     if (table->dict) {
 550         if (!xmlDictOwns(table->dict, name)) {
 551             name = xmlDictLookup(table->dict, name, -1);
 552             if (name == NULL)
 553                 return(-1);
 554         }
 555         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
 556             name2 = xmlDictLookup(table->dict, name2, -1);
 557             if (name2 == NULL)
 558                 return(-1);
 559         }
 560         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
 561             name3 = xmlDictLookup(table->dict, name3, -1);
 562             if (name3 == NULL)
 563                 return(-1);
 564         }
 565     }
 566
 567     /*
 568      * Check for duplicate and insertion location.
 569      */
 570     key = xmlHashComputeKey(table, name, name2, name3);
 571     if (table->table[key].valid == 0) {
 572         insert = NULL;
 573     } else {
 574         if (table->dict) {
 575             for (insert = &(table->table[key]); insert->next != NULL;
 576                  insert = insert->next) {
 577                 if ((insert->name == name) &&
 578                     (insert->name2 == name2) &&
 579                     (insert->name3 == name3))
 580                     return(-1);
 581                 len++;
 582             }
 583             if ((insert->name == name) &&
 584                 (insert->name2 == name2) &&
 585                 (insert->name3 == name3))
 586                 return(-1);
 587         } else {
 588             for (insert = &(table->table[key]); insert->next != NULL;
 589                  insert = insert->next) {
 590                 if ((xmlStrEqual(insert->name, name)) &&
 591                     (xmlStrEqual(insert->name2, name2)) &&
 592                     (xmlStrEqual(insert->name3, name3)))
 593                     return(-1);
 594                 len++;
 595             }
 596             if ((xmlStrEqual(insert->name, name)) &&
 597                 (xmlStrEqual(insert->name2, name2)) &&
 598                 (xmlStrEqual(insert->name3, name3)))
 599                 return(-1);
 600         }
 601     }
 602
 603     if (insert == NULL) {
 604         entry = &(table->table[key]);
 605     } else {
 606         entry = xmlMalloc(sizeof(xmlHashEntry));
 607         if (entry == NULL)
 608              return(-1);
 609     }
 610
 611     if (table->dict != NULL) {
 612         entry->name = (xmlChar *) name;
 613         entry->name2 = (xmlChar *) name2;
 614         entry->name3 = (xmlChar *) name3;
 615     } else {
 616         entry->name = xmlStrdup(name);
 617         entry->name2 = xmlStrdup(name2);
 618         entry->name3 = xmlStrdup(name3);
 619     }
 620     entry->payload = userdata;
 621     entry->next = NULL;
 622     entry->valid = 1;
 623
 624
 625     if (insert != NULL)
 626         insert->next = entry;
 627
 628     table->nbElems++;
 629
 630     if (len > MAX_HASH_LEN)
 631         xmlHashGrow(table, MAX_HASH_LEN * table->size);
 632
 633     return(0);
 634 }
 635
 636 /**
 637  * xmlHashUpdateEntry3:
 638  * @table: the hash table
 639  * @name: the name of the userdata
 640  * @name2: a second name of the userdata
 641  * @name3: a third name of the userdata
 642  * @userdata: a pointer to the userdata
 643  * @f: the deallocator function for replaced item (if any)
 644  *
 645  * Add the @userdata to the hash @table. This can later be retrieved
 646  * by using the tuple (@name, @name2, @name3). Existing entry for this tuple
 647  * will be removed and freed with @f if found.
 648  *
 649  * Returns 0 the addition succeeded and -1 in case of error.
 650  */
 651 int
 652 xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
 653                    const xmlChar *name2, const xmlChar *name3,
 654                    void *userdata, xmlHashDeallocator f) {
 655     unsigned long key;
 656     xmlHashEntryPtr entry;
 657     xmlHashEntryPtr insert;
 658
 659     if ((table == NULL) || name == NULL)
 660         return(-1);
 661
 662     /*
 663      * If using a dict internalize if needed
 664      */
 665     if (table->dict) {
 666         if (!xmlDictOwns(table->dict, name)) {
 667             name = xmlDictLookup(table->dict, name, -1);
 668             if (name == NULL)
 669                 return(-1);
 670         }
 671         if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
 672             name2 = xmlDictLookup(table->dict, name2, -1);
 673             if (name2 == NULL)
 674                 return(-1);
 675         }
 676         if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
 677             name3 = xmlDictLookup(table->dict, name3, -1);
 678             if (name3 == NULL)
 679                 return(-1);
 680         }
 681     }
 682
 683     /*
 684      * Check for duplicate and insertion location.
 685      */
 686     key = xmlHashComputeKey(table, name, name2, name3);
 687     if (table->table[key].valid == 0) {
 688         insert = NULL;
 689     } else {
 690         if (table ->dict) {
 691             for (insert = &(table->table[key]); insert->next != NULL;
 692                  insert = insert->next) {
 693                 if ((insert->name == name) &&
 694                     (insert->name2 == name2) &&
 695                     (insert->name3 == name3)) {
 696                     if (f)
 697                         f(insert->payload, insert->name);
 698                     insert->payload = userdata;
 699                     return(0);
 700                 }
 701             }
 702             if ((insert->name == name) &&
 703                 (insert->name2 == name2) &&
 704                 (insert->name3 == name3)) {
 705                 if (f)
 706                     f(insert->payload, insert->name);
 707                 insert->payload = userdata;
 708                 return(0);
 709             }
 710         } else {
 711             for (insert = &(table->table[key]); insert->next != NULL;
 712                  insert = insert->next) {
 713                 if ((xmlStrEqual(insert->name, name)) &&
 714                     (xmlStrEqual(insert->name2, name2)) &&
 715                     (xmlStrEqual(insert->name3, name3))) {
 716                     if (f)
 717                         f(insert->payload, insert->name);
 718                     insert->payload = userdata;
 719                     return(0);
 720                 }
 721             }
 722             if ((xmlStrEqual(insert->name, name)) &&
 723                 (xmlStrEqual(insert->name2, name2)) &&
 724                 (xmlStrEqual(insert->name3, name3))) {
 725                 if (f)
 726                     f(insert->payload, insert->name);
 727                 insert->payload = userdata;
 728                 return(0);
 729             }
 730         }
 731     }
 732
 733     if (insert == NULL) {
 734         entry =  &(table->table[key]);
 735     } else {
 736         entry = xmlMalloc(sizeof(xmlHashEntry));
 737         if (entry == NULL)
 738              return(-1);
 739     }
 740
 741     if (table->dict != NULL) {
 742         entry->name = (xmlChar *) name;
 743         entry->name2 = (xmlChar *) name2;
 744         entry->name3 = (xmlChar *) name3;
 745     } else {
 746         entry->name = xmlStrdup(name);
 747         entry->name2 = xmlStrdup(name2);
 748         entry->name3 = xmlStrdup(name3);
 749     }
 750     entry->payload = userdata;
 751     entry->next = NULL;
 752     entry->valid = 1;
 753     table->nbElems++;
 754
 755
 756     if (insert != NULL) {
 757         insert->next = entry;
 758     }
 759     return(0);
 760 }
 761
 762 /**
 763  * xmlHashLookup3:
 764  * @table: the hash table
 765  * @name: the name of the userdata
 766  * @name2: a second name of the userdata
 767  * @name3: a third name of the userdata
 768  *
 769  * Find the userdata specified by the (@name, @name2, @name3) tuple.
 770  *
 771  * Returns the a pointer to the userdata
 772  */
 773 void *
 774 xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
 775                const xmlChar *name2, const xmlChar *name3) {
 776     unsigned long key;
 777     xmlHashEntryPtr entry;
 778
 779     if (table == NULL)
 780         return(NULL);
 781     if (name == NULL)
 782         return(NULL);
 783     key = xmlHashComputeKey(table, name, name2, name3);
 784     if (table->table[key].valid == 0)
 785         return(NULL);
 786     if (table->dict) {
 787         for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 788             if ((entry->name == name) &&
 789                 (entry->name2 == name2) &&
 790                 (entry->name3 == name3))
 791                 return(entry->payload);
 792         }
 793     }
 794     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 795         if ((xmlStrEqual(entry->name, name)) &&
 796             (xmlStrEqual(entry->name2, name2)) &&
 797             (xmlStrEqual(entry->name3, name3)))
 798             return(entry->payload);
 799     }
 800     return(NULL);
 801 }
 802
 803 /**
 804  * xmlHashQLookup3:
 805  * @table: the hash table
 806  * @prefix: the prefix of the userdata
 807  * @name: the name of the userdata
 808  * @prefix2: the second prefix of the userdata
 809  * @name2: a second name of the userdata
 810  * @prefix3: the third prefix of the userdata
 811  * @name3: a third name of the userdata
 812  *
 813  * Find the userdata specified by the (@name, @name2, @name3) tuple.
 814  *
 815  * Returns the a pointer to the userdata
 816  */
 817 void *
 818 xmlHashQLookup3(xmlHashTablePtr table,
 819                 const xmlChar *prefix, const xmlChar *name,
 820                 const xmlChar *prefix2, const xmlChar *name2,
 821                 const xmlChar *prefix3, const xmlChar *name3) {
 822     unsigned long key;
 823     xmlHashEntryPtr entry;
 824
 825     if (table == NULL)
 826         return(NULL);
 827     if (name == NULL)
 828         return(NULL);
 829     key = xmlHashComputeQKey(table, prefix, name, prefix2,
 830                              name2, prefix3, name3);
 831     if (table->table[key].valid == 0)
 832         return(NULL);
 833     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
 834         if ((xmlStrQEqual(prefix, name, entry->name)) &&
 835             (xmlStrQEqual(prefix2, name2, entry->name2)) &&
 836             (xmlStrQEqual(prefix3, name3, entry->name3)))
 837             return(entry->payload);
 838     }
 839     return(NULL);
 840 }
 841
 842 typedef struct {
 843     xmlHashScanner hashscanner;
 844     void *data;
 845 } stubData;
 846
 847 static void
 848 stubHashScannerFull (void *payload, void *data, const xmlChar *name,
 849                      const xmlChar *name2 ATTRIBUTE_UNUSED,
 850                      const xmlChar *name3 ATTRIBUTE_UNUSED) {
 851     stubData *stubdata = (stubData *) data;
 852     stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
 853 }
 854
 855 /**
 856  * xmlHashScan:
 857  * @table: the hash table
 858  * @f:  the scanner function for items in the hash
 859  * @data:  extra data passed to f
 860  *
 861  * Scan the hash @table and applied @f to each value.
 862  */
 863 void
 864 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
 865     stubData stubdata;
 866     stubdata.data = data;
 867     stubdata.hashscanner = f;
 868     xmlHashScanFull (table, stubHashScannerFull, &stubdata);
 869 }
 870
 871 /**
 872  * xmlHashScanFull:
 873  * @table: the hash table
 874  * @f:  the scanner function for items in the hash
 875  * @data:  extra data passed to f
 876  *
 877  * Scan the hash @table and applied @f to each value.
 878  */
 879 void
 880 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
 881     int i, nb;
 882     xmlHashEntryPtr iter;
 883     xmlHashEntryPtr next;
 884
 885     if (table == NULL)
 886         return;
 887     if (f == NULL)
 888         return;
 889
 890     if (table->table) {
 891         for(i = 0; i < table->size; i++) {
 892             if (table->table[i].valid == 0)
 893                 continue;
 894             iter = &(table->table[i]);
 895             while (iter) {
 896                 next = iter->next;
 897                 nb = table->nbElems;
 898                 if ((f != NULL) && (iter->payload != NULL))
 899                     f(iter->payload, data, iter->name,
 900                       iter->name2, iter->name3);
 901                 if (nb != table->nbElems) {
 902                     /* table was modified by the callback, be careful */
 903                     if (iter == &(table->table[i])) {
 904                         if (table->table[i].valid == 0)
 905                             iter = NULL;
 906                         if (table->table[i].next != next)
 907                             iter = &(table->table[i]);
 908                     } else
 909                         iter = next;
 910                 } else
 911                     iter = next;
 912             }
 913         }
 914     }
 915 }
 916
 917 /**
 918  * xmlHashScan3:
 919  * @table: the hash table
 920  * @name: the name of the userdata or NULL
 921  * @name2: a second name of the userdata or NULL
 922  * @name3: a third name of the userdata or NULL
 923  * @f:  the scanner function for items in the hash
 924  * @data:  extra data passed to f
 925  *
 926  * Scan the hash @table and applied @f to each value matching
 927  * (@name, @name2, @name3) tuple. If one of the names is null,
 928  * the comparison is considered to match.
 929  */
 930 void
 931 xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
 932              const xmlChar *name2, const xmlChar *name3,
 933              xmlHashScanner f, void *data) {
 934     stubData stubdata;
 935     stubdata.data = data;
 936     stubdata.hashscanner = f;
 937     xmlHashScanFull3(table, name, name2, name3, stubHashScannerFull,
 938                      &stubdata);
 939 }
 940
 941 /**
 942  * xmlHashScanFull3:
 943  * @table: the hash table
 944  * @name: the name of the userdata or NULL
 945  * @name2: a second name of the userdata or NULL
 946  * @name3: a third name of the userdata or NULL
 947  * @f:  the scanner function for items in the hash
 948  * @data:  extra data passed to f
 949  *
 950  * Scan the hash @table and applied @f to each value matching
 951  * (@name, @name2, @name3) tuple. If one of the names is null,
 952  * the comparison is considered to match.
 953  */
 954 void
 955 xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
 956                  const xmlChar *name2, const xmlChar *name3,
 957                  xmlHashScannerFull f, void *data) {
 958     int i;
 959     xmlHashEntryPtr iter;
 960     xmlHashEntryPtr next;
 961
 962     if (table == NULL)
 963         return;
 964     if (f == NULL)
 965         return;
 966
 967     if (table->table) {
 968         for(i = 0; i < table->size; i++) {
 969             if (table->table[i].valid == 0)
 970                 continue;
 971             iter = &(table->table[i]);
 972             while (iter) {
 973                 next = iter->next;
 974                 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
 975                     ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
 976                     ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
 977                     (iter->payload != NULL)) {
 978                     f(iter->payload, data, iter->name,
 979                       iter->name2, iter->name3);
 980                 }
 981                 iter = next;
 982             }
 983         }
 984     }
 985 }
 986
 987 /**
 988  * xmlHashCopy:
 989  * @table: the hash table
 990  * @f:  the copier function for items in the hash
 991  *
 992  * Scan the hash @table and applied @f to each value.
 993  *
 994  * Returns the new table or NULL in case of error.
 995  */
 996 xmlHashTablePtr
 997 xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) {
 998     int i;
 999     xmlHashEntryPtr iter;
1000     xmlHashEntryPtr next;
1001     xmlHashTablePtr ret;
1002
1003     if (table == NULL)
1004         return(NULL);
1005     if (f == NULL)
1006         return(NULL);
1007
1008     ret = xmlHashCreate(table->size);
1009     if (ret == NULL)
1010         return(NULL);
1011
1012     if (table->table) {
1013         for(i = 0; i < table->size; i++) {
1014             if (table->table[i].valid == 0)
1015                 continue;
1016             iter = &(table->table[i]);
1017             while (iter) {
1018                 next = iter->next;
1019                 xmlHashAddEntry3(ret, iter->name, iter->name2,
1020                                  iter->name3, f(iter->payload, iter->name));
1021                 iter = next;
1022             }
1023         }
1024     }
1025     ret->nbElems = table->nbElems;
1026     return(ret);
1027 }
1028
1029 /**
1030  * xmlHashSize:
1031  * @table: the hash table
1032  *
1033  * Query the number of elements installed in the hash @table.
1034  *
1035  * Returns the number of elements in the hash table or
1036  * -1 in case of error
1037  */
1038 int
1039 xmlHashSize(xmlHashTablePtr table) {
1040     if (table == NULL)
1041         return(-1);
1042     return(table->nbElems);
1043 }
1044
1045 /**
1046  * xmlHashRemoveEntry:
1047  * @table: the hash table
1048  * @name: the name of the userdata
1049  * @f: the deallocator function for removed item (if any)
1050  *
1051  * Find the userdata specified by the @name and remove
1052  * it from the hash @table. Existing userdata for this tuple will be removed
1053  * and freed with @f.
1054  *
1055  * Returns 0 if the removal succeeded and -1 in case of error or not found.
1056  */
1057 int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
1058                        xmlHashDeallocator f) {
1059     return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
1060 }
1061
1062 /**
1063  * xmlHashRemoveEntry2:
1064  * @table: the hash table
1065  * @name: the name of the userdata
1066  * @name2: a second name of the userdata
1067  * @f: the deallocator function for removed item (if any)
1068  *
1069  * Find the userdata specified by the (@name, @name2) tuple and remove
1070  * it from the hash @table. Existing userdata for this tuple will be removed
1071  * and freed with @f.
1072  *
1073  * Returns 0 if the removal succeeded and -1 in case of error or not found.
1074  */
1075 int
1076 xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
1077                         const xmlChar *name2, xmlHashDeallocator f) {
1078     return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
1079 }
1080
1081 /**
1082  * xmlHashRemoveEntry3:
1083  * @table: the hash table
1084  * @name: the name of the userdata
1085  * @name2: a second name of the userdata
1086  * @name3: a third name of the userdata
1087  * @f: the deallocator function for removed item (if any)
1088  *
1089  * Find the userdata specified by the (@name, @name2, @name3) tuple and remove
1090  * it from the hash @table. Existing userdata for this tuple will be removed
1091  * and freed with @f.
1092  *
1093  * Returns 0 if the removal succeeded and -1 in case of error or not found.
1094  */
1095 int
1096 xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
1097     const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f) {
1098     unsigned long key;
1099     xmlHashEntryPtr entry;
1100     xmlHashEntryPtr prev = NULL;
1101
1102     if (table == NULL || name == NULL)
1103         return(-1);
1104
1105     key = xmlHashComputeKey(table, name, name2, name3);
1106     if (table->table[key].valid == 0) {
1107         return(-1);
1108     } else {
1109         for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
1110             if (xmlStrEqual(entry->name, name) &&
1111                     xmlStrEqual(entry->name2, name2) &&
1112                     xmlStrEqual(entry->name3, name3)) {
1113                 if ((f != NULL) && (entry->payload != NULL))
1114                     f(entry->payload, entry->name);
1115                 entry->payload = NULL;
1116                 if (table->dict == NULL) {
1117                     if(entry->name)
1118                         xmlFree(entry->name);
1119                     if(entry->name2)
1120                         xmlFree(entry->name2);
1121                     if(entry->name3)
1122                         xmlFree(entry->name3);
1123                 }
1124                 if(prev) {
1125                     prev->next = entry->next;
1126                     xmlFree(entry);
1127                 } else {
1128                     if (entry->next == NULL) {
1129                         entry->valid = 0;
1130                     } else {
1131                         entry = entry->next;
1132                         memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
1133                         xmlFree(entry);
1134                     }
1135                 }
1136                 table->nbElems--;
1137                 return(0);
1138             }
1139             prev = entry;
1140         }
1141         return(-1);
1142     }
1143 }
1144
1145 #define bottom_hash
1146 #include "elfgcchack.h"