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