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