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