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