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