1 /*

     2  * libxml2_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  * Portion Copyright © 2009 Nokia Corporation and/or its subsidiary(-ies). All rights reserved. 

    19  */

    20 

    21 #define IN_LIBXML

    22 #include "xmlenglibxml.h"

    23 

    24 #include <string.h>

    25 #include <stdapis/libxml2/libxml2_globals.h>

    26 

    27 #define MAX_HASH_LEN 8

    28 

    29 /* #define DEBUG_GROW */

    30 

    31 /*

    32  * A single entry in the hash table

    33  */

    34 typedef struct _xmlHashEntry xmlHashEntry;

    35 typedef xmlHashEntry* xmlHashEntryPtr;

    36 struct _xmlHashEntry {

    37     struct _xmlHashEntry *next;

    38     xmlChar *name;

    39     xmlChar *name2;

    40     xmlChar *name3;

    41     void *payload;

    42     int valid;

    43 };

    44 

    45 /*

    46  * The entire hash table

    47  */

    48 struct _xmlHashTable {

    49     xmlHashEntryPtr table;

    50     int size;

    51     int nbElems;

    52 };

    53 

    54 /*

    55  * xmlHashComputeKey:

    56  * Calculate the hash key

    57  *

    58  * OOM: never

    59  */

    60 static unsigned long

    61 xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,

    62               const xmlChar *name2, const xmlChar *name3) {

    63     unsigned long value = 0L;

    64     char ch;

    65 

    66     if (name != NULL) {

    67     value += 30 * (*name);

    68     while ((ch = *name++) != 0) {

    69         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    70     }

    71     }

    72     if (name2 != NULL) {

    73     while ((ch = *name2++) != 0) {

    74         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    75     }

    76     }

    77     if (name3 != NULL) {

    78     while ((ch = *name3++) != 0) {

    79         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

    80     }

    81     }

    82     return (value % table->size);

    83 }

    84 

    85 static unsigned long

    86 xmlHashComputeQKey(xmlHashTablePtr table,

    87            const xmlChar *prefix, const xmlChar *name,

    88            const xmlChar *prefix2, const xmlChar *name2,

    89            const xmlChar *prefix3, const xmlChar *name3) {

    90     unsigned long value = 0L;

    91     char ch;

    92 

    93     if (prefix != NULL)

    94     value += 30 * (*prefix);

    95     else

    96     value += 30 * (*name);

    97 

    98     if (prefix != NULL) {

    99     while ((ch = *prefix++) != 0) {

   100         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

   101     }

   102     value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');

   103     }

   104     if (name != NULL) {

   105     while ((ch = *name++) != 0) {

   106         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

   107     }

   108     }

   109     if (prefix2 != NULL) {

   110     while ((ch = *prefix2++) != 0) {

   111         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

   112     }

   113     value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');

   114     }

   115     if (name2 != NULL) {

   116     while ((ch = *name2++) != 0) {

   117         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

   118     }

   119     }

   120     if (prefix3 != NULL) {

   121     while ((ch = *prefix3++) != 0) {

   122         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

   123     }

   124     value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');

   125     }

   126     if (name3 != NULL) {

   127     while ((ch = *name3++) != 0) {

   128         value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);

   129     }

   130     }

   131     return (value % table->size);

   132 }

   133 

   134 /**

   135  * xmlHashCreate:

   136  * @param size the size of the hash table

   137  *

   138  * Create a new xmlHashTablePtr.

   139  *

   140  * Returns the newly created object, or NULL if an error occured.

   141  *

   142  * OOM: possible --> returns NULL, OOM flag is set

   143  */

   144 XMLPUBFUNEXPORT xmlHashTablePtr

   145 xmlHashCreate(int size) {

   146     xmlHashTablePtr table;

   147 

   148     if (size <= 0)

   149         size = 256;

   150 

   151     table = (xmlHashTablePtr) xmlMalloc(sizeof(xmlHashTable));

   152     if (table) {

   153         table->size = size;

   154         table->nbElems = 0;

   155         table->table = (xmlHashEntryPtr)xmlMalloc(size * sizeof(xmlHashEntry)); // may set OOM flag

   156         if (table->table) {

   157             memset(table->table, 0, size * sizeof(xmlHashEntry));

   158             return(table);

   159         }

   160         xmlFree(table);

   161     }

   162     return(NULL);

   163 }

   164 

   165 /**

   166  * xmlHashGrow:

   167  * @param table the hash table

   168  * @param size the new size of the hash table

   169  *

   170  * resize the hash table

   171  *

   172  * Returns 0 in case of success, -1 in case of failure

   173  *

   174  * OOM: possible --> sets OOM flag when returns -1

   175  */

   176 static int

   177 xmlHashGrow(xmlHashTablePtr table, int size) {

   178     unsigned long key;

   179     int oldsize, i;

   180     xmlHashEntryPtr iter, next;

   181     struct _xmlHashEntry *oldtable;

   182 #ifdef DEBUG_GROW

   183     unsigned long nbElem = 0;

   184 #endif

   185 

   186     if (table == NULL)

   187         return(-1);

   188     if (size < 8)

   189         return(-1);

   190     if (size > 8 * 2048)

   191         return(-1);

   192 

   193     oldsize = table->size;

   194     oldtable = table->table;

   195     if (oldtable == NULL)

   196         return(-1);

   197 

   198     table->table = (xmlHashEntryPtr)xmlMalloc(size * sizeof(xmlHashEntry)); // may set OOM flag

   199     if (table->table == NULL) {

   200         table->table = oldtable;

   201         return(-1);

   202     }

   203     memset(table->table, 0, size * sizeof(xmlHashEntry));

   204     table->size = size;

   205 

   206     /*  If the two loops are merged, there would be situations where

   207     a new entry needs to allocated and data copied into it from

   208     the main table. So instead, we run through the array twice, first

   209     copying all the elements in the main array (where we can't get

   210     conflicts) and then the rest, so we only free (and don't allocate)

   211     */

   212     for (i = 0; i < oldsize; i++) {

   213         

   214         if (oldtable[i].valid == 0)

   215             continue;

   216         key = xmlHashComputeKey(

   217                     table,

   218                     oldtable[i].name,

   219                     oldtable[i].name2,

   220                     oldtable[i].name3);

   221         memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));

   222         table->table[key].next = NULL;

   223     }

   224 

   225     for (i = 0; i < oldsize; i++) {

   226         iter = oldtable[i].next;

   227         while (iter) {

   228             next = iter->next;

   229 

   230             /*

   231             * put back the entry in the new table

   232             */

   233 

   234             key = xmlHashComputeKey(

   235                     table,

   236                     iter->name,

   237                     iter->name2,

   238                     iter->name3);

   239             if (table->table[key].valid == 0) {

   240                 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));

   241                 table->table[key].next = NULL;

   242                 xmlFree(iter);

   243             } else {

   244                 iter->next = table->table[key].next;

   245                 table->table[key].next = iter;

   246             }

   247 

   248 #ifdef DEBUG_GROW

   249             nbElem++;

   250 #endif

   251             iter = next;

   252         }

   253     }

   254 

   255     xmlFree(oldtable);

   256 

   257 #ifdef DEBUG_GROW

   258     xmlGenericError(xmlGenericErrorContext,

   259         "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);

   260 #endif

   261     return(0);

   262 }

   263 

   264 /**

   265  * xmlHashFree:

   266  * @param table the hash table

   267  * @param f the deallocator function for items in the hash

   268  *

   269  * Free the hash table and its contents. The userdata is

   270  * deallocated with f if provided.

   271  *

   272  * OOM: never //  same as argument 'f' has when f!=NULL

   273  */

   274 XMLPUBFUNEXPORT void

   275 xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {

   276     int i;

   277     xmlHashEntryPtr iter;

   278     xmlHashEntryPtr next;

   279     int inside_table = 0;

   280     int nbElems;

   281 

   282     if (table == NULL)

   283         return;

   284     if (table->table) {

   285     nbElems = table->nbElems;

   286     for(i = 0; (i < table->size) && (nbElems > 0); i++) {

   287         iter = &(table->table[i]);

   288         if (iter->valid == 0)

   289         continue;

   290         inside_table = 1;

   291         while (iter) {

   292         next = iter->next;

   293         if ((f != NULL) && (iter->payload != NULL))

   294             f(iter->payload, iter->name);

   295         if (iter->name)

   296             xmlFree(iter->name);

   297         if (iter->name2)

   298             xmlFree(iter->name2);

   299         if (iter->name3)

   300             xmlFree(iter->name3);

   301         iter->payload = NULL;

   302         if (!inside_table)

   303             xmlFree(iter);

   304         nbElems--;

   305         inside_table = 0;

   306         iter = next;

   307         }

   308         inside_table = 0;

   309     }

   310     xmlFree(table->table);

   311     }

   312     xmlFree(table);

   313 }

   314 

   315 /**

   316  * xmlHashAddEntry:

   317  * @param table the hash table

   318  * @param name the name of the userdata

   319  * @param userdata a pointer to the userdata

   320  *

   321  * Add the userdata to the hash table. This can later be retrieved

   322  * by using the name. Duplicate names generate errors.

   323  *

   324  * Returns 0 the addition succeeded and -1 in case of error.

   325  *

   326  * OOM: iif returns -1 and flag is set

   327  */

   328 XMLPUBFUNEXPORT int

   329 xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {

   330     return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));

   331 }

   332 

   333 /**

   334  * xmlHashAddEntry2:

   335  * @param table the hash table

   336  * @param name the name of the userdata

   337  * @param name2 a second name of the userdata

   338  * @param userdata a pointer to the userdata

   339  *

   340  * Add the userdata to the hash table. This can later be retrieved

   341  * by using the (name, name2) tuple. Duplicate tuples generate errors.

   342  *

   343  * Returns 0 the addition succeeded and -1 in case of error.

   344  */

   345 XMLPUBFUNEXPORT int

   346 xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,

   347             const xmlChar *name2, void *userdata) {

   348     return(xmlHashAddEntry3(table, name, name2, NULL, userdata));

   349 }

   350 

   351 /**

   352  * xmlHashUpdateEntry:

   353  * @param table the hash table

   354  * @param name the name of the userdata

   355  * @param userdata a pointer to the userdata

   356  * @param f the deallocator function for replaced item (if any)

   357  *

   358  * Add the userdata to the hash table. This can later be retrieved

   359  * by using the name. Existing entry for this name will be removed

   360  * and freed with f if found.

   361  *

   362  * Returns 0 the addition succeeded and -1 in case of error.

   363  */

   364 XMLPUBFUNEXPORT int

   365 xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,

   366                void *userdata, xmlHashDeallocator f) {

   367     return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));

   368 }

   369 

   370 /**

   371  * xmlHashUpdateEntry2:

   372  * @param table the hash table

   373  * @param name the name of the userdata

   374  * @param name2 a second name of the userdata

   375  * @param userdata a pointer to the userdata

   376  * @param f the deallocator function for replaced item (if any)

   377  *

   378  * Add the userdata to the hash table. This can later be retrieved

   379  * by using the (name, name2) tuple. Existing entry for this tuple will

   380  * be removed and freed with f if found.

   381  *

   382  * Returns 0 the addition succeeded and -1 in case of error.

   383  */

   384 XMLPUBFUNEXPORT int

   385 xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,

   386                const xmlChar *name2, void *userdata,

   387            xmlHashDeallocator f) {

   388     return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));

   389 }

   390 

   391 /**

   392  * xmlHashLookup:

   393  * @param table the hash table

   394  * @param name the name of the userdata

   395  *

   396  * Find the userdata specified by the name.

   397  *

   398  * Returns the pointer to the userdata

   399  */

   400 XMLPUBFUNEXPORT void *

   401 xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {

   402     return(xmlHashLookup3(table, name, NULL, NULL));

   403 }

   404 

   405 /**

   406  * xmlHashLookup2:

   407  * @param table the hash table

   408  * @param name the name of the userdata

   409  * @param name2 a second name of the userdata

   410  *

   411  * Find the userdata specified by the (name, name2) tuple.

   412  *

   413  * Returns the pointer to the userdata

   414  *

   415  * OOM: never

   416  */

   417 XMLPUBFUNEXPORT void*

   418 xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,

   419           const xmlChar *name2) {

   420     return(xmlHashLookup3(table, name, name2, NULL));

   421 }

   422 

   423 #ifndef XMLENGINE_EXCLUDE_UNUSED

   424 /**

   425  * xmlHashQLookup:

   426  * @param table the hash table

   427  * @param prefix the prefix of the userdata

   428  * @param name the name of the userdata

   429  *

   430  * Find the userdata specified by the QName prefix:name/name.

   431  *

   432  * Returns the pointer to the userdata

   433  *

   434  * OOM: never

   435  */

   436 void*

   437 xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,

   438                const xmlChar *name) {

   439     return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));

   440 }

   441 #endif /* ifndef XMLENGINE_EXCLUDE_UNUSED */

   442 

   443 /**

   444  * xmlHashQLookup2:

   445  * @param table the hash table

   446  * @param prefix the prefix of the userdata

   447  * @param name the name of the userdata

   448  * @param prefix2 the second prefix of the userdata

   449  * @param name2 a second name of the userdata

   450  *

   451  * Find the userdata specified by the QNames tuple

   452  *

   453  * Returns the pointer to the userdata

   454  */

   455 XMLPUBFUNEXPORT void *

   456 xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,

   457                 const xmlChar *name, const xmlChar *prefix2,

   458             const xmlChar *name2) {

   459     return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));

   460 }

   461 

   462 /**

   463  * xmlHashAddEntry3:

   464  * @param table the hash table

   465  * @param name the name of the userdata

   466  * @param name2 a second name of the userdata

   467  * @param name3 a third name of the userdata

   468  * @param userdata a pointer to the userdata

   469  *

   470  * Add the userdata to the hash table. This can later be retrieved

   471  * by using the tuple (name, name2, name3). Duplicate entries generate

   472  * errors.

   473  *

   474  * Returns 0 the addition succeeded and -1 in case of error.

   475  *

   476  * OOM: iif returns -1 and flag is set

   477  */

   478 XMLPUBFUNEXPORT int

   479 xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,

   480              const xmlChar *name2, const xmlChar *name3,

   481          void *userdata) {

   482 	LOAD_GS_DIRECT         

   483     unsigned long key, len = 0;

   484     xmlHashEntryPtr entry;

   485     xmlHashEntryPtr insert;

   486     int res;

   487 

   488     if ((table == NULL) || name == NULL)

   489         return(-1);

   490 

   491     /*

   492      * Check for duplicate and insertion location.

   493      */

   494     key = xmlHashComputeKey(table, name, name2, name3);

   495     if (table->table[key].valid == 0) {

   496         insert = NULL;

   497     } else {

   498         for (insert = &(table->table[key]); insert->next != NULL;

   499             insert = insert->next) {

   500             if ((xmlStrEqual(insert->name, name)) &&

   501             (xmlStrEqual(insert->name2, name2)) &&

   502             (xmlStrEqual(insert->name3, name3)))

   503             return(-1);

   504             len++;

   505         }

   506         if ((xmlStrEqual(insert->name, name)) &&

   507             (xmlStrEqual(insert->name2, name2)) &&

   508             (xmlStrEqual(insert->name3, name3)))

   509             return(-1);

   510     }

   511 

   512     if (insert == NULL) {

   513         entry = &(table->table[key]);

   514     } else {

   515         entry = (xmlHashEntryPtr) xmlMalloc(sizeof(xmlHashEntry)); // may set OOM flag

   516         if (entry == NULL)

   517             return(-1);

   518     }

   519     // DONE: Check OOM                               // DONE: Try to avoid xmlStrdup(NULL)

   520     

   521     

   522     entry->name  = xmlStrdup(name); // name is never NULL here

   523     entry->name2 = name2 ? xmlStrdup(name2): (xmlChar*) name2 /* it's NULL here */;

   524     entry->name3 = name3 ? xmlStrdup(name3): (xmlChar*) name3 /* it's NULL here */;

   525     if(OOM_FLAG){

   526         if(entry->name)  xmlFree(entry->name);

   527         if(entry->name2) xmlFree(entry->name2);

   528         if(entry->name3) xmlFree(entry->name3);

   529         if(insert) xmlFree(entry);

   530         return -1;

   531     }

   532     entry->payload = userdata;

   533     entry->next = NULL;

   534     entry->valid = 1;

   535 

   536     if (insert != NULL)

   537         insert->next = entry;

   538 

   539     table->nbElems++;

   540 

   541     res = 0;

   542     if (len > MAX_HASH_LEN){

   543        res = xmlHashGrow(table, MAX_HASH_LEN * table->size); 

   544     }

   545 

   546     return(res);

   547 }

   548 

   549 /**

   550  * xmlHashUpdateEntry3:

   551  * @param table the hash table

   552  * @param name the name of the userdata

   553  * @param name2 a second name of the userdata

   554  * @param name3 a third name of the userdata

   555  * @param userdata a pointer to the userdata

   556  * @param f the deallocator function for replaced item (if any)

   557  *

   558  * Add the userdata to the hash table. This can later be retrieved

   559  * by using the tuple (name, name2, name3). Existing entry for this tuple

   560  * will be removed and freed with f if found.

   561  *

   562  * Returns 0 the addition succeeded and -1 in case of error.

   563  */

   564 XMLPUBFUNEXPORT int

   565 xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,

   566                const xmlChar *name2, const xmlChar *name3,

   567            void *userdata, xmlHashDeallocator f) {

   568 	LOAD_GS_DIRECT           

   569     unsigned long key;

   570     xmlHashEntryPtr entry;

   571     xmlHashEntryPtr insert;

   572 

   573     if ((table == NULL) || name == NULL)

   574         return(-1);

   575 

   576     /*

   577      * Check for duplicate and insertion location.

   578      */

   579     key = xmlHashComputeKey(table, name, name2, name3);

   580     if (table->table[key].valid == 0) {

   581     insert = NULL;

   582     } else {

   583     for (insert = &(table->table[key]); insert->next != NULL;

   584          insert = insert->next) {

   585         if ((xmlStrEqual(insert->name, name)) &&

   586         (xmlStrEqual(insert->name2, name2)) &&

   587         (xmlStrEqual(insert->name3, name3))) {

   588         if (f)

   589             f(insert->payload, insert->name);

   590         insert->payload = userdata;

   591         return(0);

   592         }

   593     }

   594     if ((xmlStrEqual(insert->name, name)) &&

   595         (xmlStrEqual(insert->name2, name2)) &&

   596         (xmlStrEqual(insert->name3, name3))) {

   597         if (f)

   598         f(insert->payload, insert->name);

   599         insert->payload = userdata;

   600         return(0);

   601     }

   602     }

   603 

   604     if (!insert) {

   605         entry =  &(table->table[key]);

   606     } else {

   607         entry = (xmlHashEntryPtr)xmlMalloc(sizeof(xmlHashEntry));

   608         if (entry == NULL)

   609             return(-1);

   610     }

   611     // DONE: Check OOM

   612     entry->name  = xmlStrdup(name); // name is never NULL here

   613     entry->name2 = name2 ? xmlStrdup(name2): NULL;

   614     entry->name3 = name3 ? xmlStrdup(name3): NULL;

   615     if(OOM_FLAG){

   616         if(entry->name)  xmlFree(entry->name);

   617         if(entry->name2) xmlFree(entry->name2);

   618         if(entry->name3) xmlFree(entry->name3);

   619         if(insert) xmlFree(entry);

   620         return -1;

   621     }

   622     entry->payload = userdata;

   623     entry->next = NULL;

   624     entry->valid = 1;

   625     table->nbElems++;

   626 

   627 

   628     if (insert) {

   629         insert->next = entry;

   630     }

   631     return(0);

   632 }

   633 

   634 /**

   635  * xmlHashLookup3:

   636  * @param table the hash table

   637  * @param name the name of the userdata

   638  * @param name2 a second name of the userdata

   639  * @param name3 a third name of the userdata

   640  *

   641  * Find the userdata specified by the (name, name2, name3) tuple.

   642  *

   643  * Returns the a pointer to the userdata

   644  *

   645  * OOM: never

   646  */

   647 XMLPUBFUNEXPORT void *

   648 xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,

   649            const xmlChar *name2, const xmlChar *name3)

   650 {

   651     unsigned long key;

   652     xmlHashEntryPtr entry;

   653 

   654     if (table == NULL)

   655         return(NULL);

   656     if (name == NULL)

   657         return(NULL);

   658     key = xmlHashComputeKey(table, name, name2, name3);

   659     if (table->table[key].valid == 0)

   660         return(NULL);

   661     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {

   662         if ((xmlStrEqual(entry->name, name)) &&

   663             (xmlStrEqual(entry->name2, name2)) &&

   664             (xmlStrEqual(entry->name3, name3)))

   665             return(entry->payload);

   666     }

   667     return(NULL);

   668 }

   669 

   670 /**

   671  * xmlHashQLookup3:

   672  * @param table the hash table

   673  * @param prefix the prefix of the userdata

   674  * @param name the name of the userdata

   675  * @param prefix2 the second prefix of the userdata

   676  * @param name2 a second name of the userdata

   677  * @param prefix3 the third prefix of the userdata

   678  * @param name3 a third name of the userdata

   679  *

   680  * Find the userdata specified by the (name, name2, name3) tuple.

   681  *

   682  * Returns the a pointer to the userdata

   683  */

   684 XMLPUBFUNEXPORT void *

   685 xmlHashQLookup3(xmlHashTablePtr table,

   686                 const xmlChar *prefix, const xmlChar *name,

   687         const xmlChar *prefix2, const xmlChar *name2,

   688         const xmlChar *prefix3, const xmlChar *name3) {

   689     unsigned long key;

   690     xmlHashEntryPtr entry;

   691 

   692     if (table == NULL)

   693     return(NULL);

   694     if (name == NULL)

   695     return(NULL);

   696     key = xmlHashComputeQKey(table, prefix, name, prefix2,

   697                              name2, prefix3, name3);

   698     if (table->table[key].valid == 0)

   699     return(NULL);

   700     for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {

   701     if ((xmlStrQEqual(prefix, name, entry->name)) &&

   702         (xmlStrQEqual(prefix2, name2, entry->name2)) &&

   703         (xmlStrQEqual(prefix3, name3, entry->name3)))

   704         return(entry->payload);

   705     }

   706     return(NULL);

   707 }

   708 

   709 typedef struct {

   710     xmlHashScanner hashscanner;

   711     void *data;

   712 } stubData;

   713 

   714 static void

   715 stubHashScannerFull (void *payload, void *data, const xmlChar *name,

   716                      const xmlChar *name2 ATTRIBUTE_UNUSED,

   717              const xmlChar *name3 ATTRIBUTE_UNUSED) {

   718     stubData *stubdata = (stubData *) data;

   719     stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);

   720 }

   721 

   722 /**

   723  * xmlHashScan:

   724  * @param table the hash table

   725  * @param f the scanner function for items in the hash

   726  * @param data extra data passed to f

   727  *

   728  * Scan the hash table and applied f to each value.

   729  */

   730 XMLPUBFUNEXPORT void

   731 xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {

   732     stubData stubdata;

   733     stubdata.data = data;

   734     stubdata.hashscanner = f;

   735     xmlHashScanFull (table, stubHashScannerFull, &stubdata);

   736 }

   737 

   738 /**

   739  * xmlHashScanFull:

   740  * @param table the hash table

   741  * @param f the scanner function for items in the hash

   742  * @param data extra data passed to f

   743  *

   744  * Scan the hash table and applied f to each value.

   745  */

   746 XMLPUBFUNEXPORT void

   747 xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {

   748     int i;

   749     xmlHashEntryPtr iter;

   750     xmlHashEntryPtr next;

   751 

   752     if (table == NULL)

   753     return;

   754     if (f == NULL)

   755     return;

   756 

   757     if (table->table) {

   758     for(i = 0; i < table->size; i++) {

   759         if (table->table[i].valid == 0)

   760         continue;

   761         iter = &(table->table[i]);

   762         while (iter) {

   763         next = iter->next;

   764         if ((f != NULL) && (iter->payload != NULL))

   765             f(iter->payload, data, iter->name,

   766               iter->name2, iter->name3);

   767         iter = next;

   768         }

   769     }

   770     }

   771 }

   772 

   773 /**

   774  * xmlHashScan3:

   775  * @param table the hash table

   776  * @param name the name of the userdata or NULL

   777  * @param name2 a second name of the userdata or NULL

   778  * @param name3 a third name of the userdata or NULL

   779  * @param f the scanner function for items in the hash

   780  * @param data extra data passed to f

   781  *

   782  * Scan the hash table and applied f to each value matching

   783  * (name, name2, name3) tuple. If one of the names is null,

   784  * the comparison is considered to match.

   785  */

   786 XMLPUBFUNEXPORT void

   787 xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,

   788          const xmlChar *name2, const xmlChar *name3,

   789          xmlHashScanner f, void *data) {

   790     xmlHashScanFull3 (table, name, name2, name3,

   791               (xmlHashScannerFull) f, data);

   792 }

   793 

   794 /**

   795  * xmlHashScanFull3:

   796  * @param table the hash table

   797  * @param name the name of the userdata or NULL

   798  * @param name2 a second name of the userdata or NULL

   799  * @param name3 a third name of the userdata or NULL

   800  * @param f the scanner function for items in the hash

   801  * @param data extra data passed to f

   802  *

   803  * Scan the hash table and applied f to each value matching

   804  * (name, name2, name3) tuple. If one of the names is null,

   805  * the comparison is considered to match.

   806  */

   807 XMLPUBFUNEXPORT void

   808 xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,

   809          const xmlChar *name2, const xmlChar *name3,

   810          xmlHashScannerFull f, void *data) {

   811     int i;

   812     xmlHashEntryPtr iter;

   813     xmlHashEntryPtr next;

   814 

   815     if (table == NULL)

   816     return;

   817     if (f == NULL)

   818     return;

   819 

   820     if (table->table) {

   821     for(i = 0; i < table->size; i++) {

   822         if (table->table[i].valid == 0)

   823         continue;

   824         iter = &(table->table[i]);

   825         while (iter) {

   826         next = iter->next;

   827         if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&

   828             ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&

   829             ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&

   830             (iter->payload != NULL)) {

   831             f(iter->payload, data, iter->name,

   832               iter->name2, iter->name3);

   833         }

   834         iter = next;

   835         }

   836     }

   837     }

   838 }

   839 

   840 /**

   841  * xmlHashCopy:

   842  * @param table the hash table

   843  * @param f the copier function for items in the hash

   844  *

   845  * Scan the hash table and applied f to each value.

   846  *

   847  * Returns the new table or NULL in case of error.

   848  *

   849  * OOM: possible --> returns NULL, OOM flag is set

   850  */

   851 XMLPUBFUNEXPORT xmlHashTablePtr

   852 xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f)

   853 {

   854 	LOAD_GS_DIRECT

   855     int i;

   856     xmlHashEntryPtr iter;

   857     xmlHashEntryPtr next;

   858     xmlHashTablePtr ret;

   859     //int res; 

   860     void* pCopy;

   861 

   862     if (table == NULL)

   863         return(NULL);

   864     if (f == NULL)

   865         return(NULL);

   866 

   867     ret = xmlHashCreate(table->size); // may set OOM flag

   868     if(!ret)

   869         return NULL; // OOM happened, the flag is set already

   870 

   871     if (table->table) {

   872         for(i = 0; i < table->size; i++)

   873         {

   874             if (table->table[i].valid == 0)

   875                 continue;

   876             iter = &(table->table[i]);

   877             while (iter)

   878             {

   879                 next = iter->next;

   880                 pCopy = f(iter->payload, iter->name);

   881                 if(OOM_FLAG)

   882                     goto oom;

   883                 //res = 

   884                 xmlHashAddEntry3(

   885                             ret,

   886                             iter->name,

   887                             iter->name2,

   888                             iter->name3,

   889                             pCopy);

   890                 if(OOM_FLAG)

   891                     goto oom;

   892                 iter = next;

   893             }

   894         }

   895     }

   896     ret->nbElems = table->nbElems;

   897     return(ret);

   898 oom:

   899     // OOM during copying entry in  f()

   900     xmlHashFree(ret, NULL); 

   901     return NULL;

   902 }

   903 

   904 #ifndef XMLENGINE_EXCLUDE_UNUSED

   905 /**

   906  * xmlHashSize:

   907  * @param table the hash table

   908  *

   909  * Query the number of elements installed in the hash table.

   910  *

   911  * Returns the number of elements in the hash table or

   912  * -1 in case of error

   913  */

   914 int

   915 xmlHashSize(xmlHashTablePtr table)

   916 {

   917     if (table == NULL)

   918         return(-1);

   919     return(table->nbElems);

   920 }

   921 #endif /* ifndef XMLENGINE_EXCLUDE_UNUSED */

   922 

   923 /**

   924  * xmlHashRemoveEntry:

   925  * @param table the hash table

   926  * @param name the name of the userdata

   927  * @param f the deallocator function for removed item (if any)

   928  *

   929  * Find the userdata specified by the name and remove

   930  * it from the hash table. Existing userdata for this tuple will be removed

   931  * and freed with f.

   932  *

   933  * Returns 0 if the removal succeeded and -1 in case of error or not found.

   934  *

   935  * OOM:  never / same as argument function 'f' has, if f!=NULL*

   936  */

   937 XMLPUBFUNEXPORT int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,

   938                xmlHashDeallocator f)

   939 {

   940     return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));

   941 }

   942 

   943 /**

   944  * xmlHashRemoveEntry2:

   945  * @param table the hash table

   946  * @param name the name of the userdata

   947  * @param name2 a second name of the userdata

   948  * @param f the deallocator function for removed item (if any)

   949  *

   950  * Find the userdata specified by the (name, name2) tuple and remove

   951  * it from the hash table. Existing userdata for this tuple will be removed

   952  * and freed with f.

   953  *

   954  * Returns 0 if the removal succeeded and -1 in case of error or not found.

   955  */

   956 XMLPUBFUNEXPORT int

   957 xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,

   958             const xmlChar *name2, xmlHashDeallocator f) {

   959     return(xmlHashRemoveEntry3(table, name, name2, NULL, f));

   960 }

   961 

   962 /**

   963  * xmlHashRemoveEntry3:

   964  * @param table the hash table

   965  * @param name the name of the userdata

   966  * @param name2 a second name of the userdata

   967  * @param name3 a third name of the userdata

   968  * @param f the deallocator function for removed item (if any)

   969  *

   970  * Find the userdata specified by the (name, name2, name3) tuple and remove

   971  * it from the hash table. Existing userdata for this tuple will be removed

   972  * and freed with f.

   973  *

   974  * Returns 0 if the removal succeeded and -1 in case of error or not found.

   975  *

   976  * OOM:  never / same as argument function 'f' has, if f!=NULL

   977  */

   978 XMLPUBFUNEXPORT int

   979 xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,

   980     const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f)

   981 {

   982     unsigned long key;

   983     xmlHashEntryPtr entry;

   984     xmlHashEntryPtr prev = NULL;

   985 

   986     if (table == NULL || name == NULL)

   987         return(-1);

   988 

   989     key = xmlHashComputeKey(table, name, name2, name3);

   990     if (table->table[key].valid == 0) {

   991         return(-1);

   992     } else {

   993         for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {

   994             if (xmlStrEqual(entry->name, name) &&

   995                     xmlStrEqual(entry->name2, name2) &&

   996                     xmlStrEqual(entry->name3, name3)) {

   997                 if ((f != NULL) && (entry->payload != NULL))

   998                     f(entry->payload, entry->name);

   999                 entry->payload = NULL;

  1000                 if(entry->name)

  1001                     xmlFree(entry->name);

  1002                 if(entry->name2)

  1003                     xmlFree(entry->name2);

  1004                 if(entry->name3)

  1005                     xmlFree(entry->name3);

  1006                 if(prev) {

  1007                     prev->next = entry->next;

  1008             xmlFree(entry);

  1009         } else {

  1010             if (entry->next == NULL) {

  1011             entry->valid = 0;

  1012             } else {

  1013             entry = entry->next;

  1014             memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));

  1015             xmlFree(entry);

  1016             }

  1017         }

  1018                 table->nbElems--;

  1019                 return(0);

  1020             }

  1021             prev = entry;

  1022         }

  1023         return(-1);

  1024     }

  1025 }