--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/xml/libxml2libs/src/libxml2/libxml2_hash.c Thu Dec 17 09:29:21 2009 +0200
@@ -0,0 +1,1025 @@
+/*
+ * libxml2_hash.c: chained hash tables
+ *
+ * Reference: Your favorite introductory book on algorithms
+ *
+ * Copyright (C) 2000 Bjorn Reese and Daniel Veillard.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
+ * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
+ * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
+ *
+ * Author: breese@users.sourceforge.net
+ * Portion Copyright © 2009 Nokia Corporation and/or its subsidiary(-ies). All rights reserved.
+ */
+
+#define IN_LIBXML
+#include "xmlenglibxml.h"
+
+#include <string.h>
+#include <stdapis/libxml2/libxml2_globals.h>
+
+#define MAX_HASH_LEN 8
+
+/* #define DEBUG_GROW */
+
+/*
+ * A single entry in the hash table
+ */
+typedef struct _xmlHashEntry xmlHashEntry;
+typedef xmlHashEntry* xmlHashEntryPtr;
+struct _xmlHashEntry {
+ struct _xmlHashEntry *next;
+ xmlChar *name;
+ xmlChar *name2;
+ xmlChar *name3;
+ void *payload;
+ int valid;
+};
+
+/*
+ * The entire hash table
+ */
+struct _xmlHashTable {
+ xmlHashEntryPtr table;
+ int size;
+ int nbElems;
+};
+
+/*
+ * xmlHashComputeKey:
+ * Calculate the hash key
+ *
+ * OOM: never
+ */
+static unsigned long
+xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, const xmlChar *name3) {
+ unsigned long value = 0L;
+ char ch;
+
+ if (name != NULL) {
+ value += 30 * (*name);
+ while ((ch = *name++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ }
+ if (name2 != NULL) {
+ while ((ch = *name2++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ }
+ if (name3 != NULL) {
+ while ((ch = *name3++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ }
+ return (value % table->size);
+}
+
+static unsigned long
+xmlHashComputeQKey(xmlHashTablePtr table,
+ const xmlChar *prefix, const xmlChar *name,
+ const xmlChar *prefix2, const xmlChar *name2,
+ const xmlChar *prefix3, const xmlChar *name3) {
+ unsigned long value = 0L;
+ char ch;
+
+ if (prefix != NULL)
+ value += 30 * (*prefix);
+ else
+ value += 30 * (*name);
+
+ if (prefix != NULL) {
+ while ((ch = *prefix++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
+ }
+ if (name != NULL) {
+ while ((ch = *name++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ }
+ if (prefix2 != NULL) {
+ while ((ch = *prefix2++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
+ }
+ if (name2 != NULL) {
+ while ((ch = *name2++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ }
+ if (prefix3 != NULL) {
+ while ((ch = *prefix3++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
+ }
+ if (name3 != NULL) {
+ while ((ch = *name3++) != 0) {
+ value = value ^ ((value << 5) + (value >> 3) + (unsigned long)ch);
+ }
+ }
+ return (value % table->size);
+}
+
+/**
+ * xmlHashCreate:
+ * @param size the size of the hash table
+ *
+ * Create a new xmlHashTablePtr.
+ *
+ * Returns the newly created object, or NULL if an error occured.
+ *
+ * OOM: possible --> returns NULL, OOM flag is set
+ */
+XMLPUBFUNEXPORT xmlHashTablePtr
+xmlHashCreate(int size) {
+ xmlHashTablePtr table;
+
+ if (size <= 0)
+ size = 256;
+
+ table = (xmlHashTablePtr) xmlMalloc(sizeof(xmlHashTable));
+ if (table) {
+ table->size = size;
+ table->nbElems = 0;
+ table->table = (xmlHashEntryPtr)xmlMalloc(size * sizeof(xmlHashEntry)); // may set OOM flag
+ if (table->table) {
+ memset(table->table, 0, size * sizeof(xmlHashEntry));
+ return(table);
+ }
+ xmlFree(table);
+ }
+ return(NULL);
+}
+
+/**
+ * xmlHashGrow:
+ * @param table the hash table
+ * @param size the new size of the hash table
+ *
+ * resize the hash table
+ *
+ * Returns 0 in case of success, -1 in case of failure
+ *
+ * OOM: possible --> sets OOM flag when returns -1
+ */
+static int
+xmlHashGrow(xmlHashTablePtr table, int size) {
+ unsigned long key;
+ int oldsize, i;
+ xmlHashEntryPtr iter, next;
+ struct _xmlHashEntry *oldtable;
+#ifdef DEBUG_GROW
+ unsigned long nbElem = 0;
+#endif
+
+ if (table == NULL)
+ return(-1);
+ if (size < 8)
+ return(-1);
+ if (size > 8 * 2048)
+ return(-1);
+
+ oldsize = table->size;
+ oldtable = table->table;
+ if (oldtable == NULL)
+ return(-1);
+
+ table->table = (xmlHashEntryPtr)xmlMalloc(size * sizeof(xmlHashEntry)); // may set OOM flag
+ if (table->table == NULL) {
+ table->table = oldtable;
+ return(-1);
+ }
+ memset(table->table, 0, size * sizeof(xmlHashEntry));
+ table->size = size;
+
+ /* If the two loops are merged, there would be situations where
+ a new entry needs to allocated and data copied into it from
+ the main table. So instead, we run through the array twice, first
+ copying all the elements in the main array (where we can't get
+ conflicts) and then the rest, so we only free (and don't allocate)
+ */
+ for (i = 0; i < oldsize; i++) {
+
+ if (oldtable[i].valid == 0)
+ continue;
+ key = xmlHashComputeKey(
+ table,
+ oldtable[i].name,
+ oldtable[i].name2,
+ oldtable[i].name3);
+ memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
+ table->table[key].next = NULL;
+ }
+
+ for (i = 0; i < oldsize; i++) {
+ iter = oldtable[i].next;
+ while (iter) {
+ next = iter->next;
+
+ /*
+ * put back the entry in the new table
+ */
+
+ key = xmlHashComputeKey(
+ table,
+ iter->name,
+ iter->name2,
+ iter->name3);
+ if (table->table[key].valid == 0) {
+ memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
+ table->table[key].next = NULL;
+ xmlFree(iter);
+ } else {
+ iter->next = table->table[key].next;
+ table->table[key].next = iter;
+ }
+
+#ifdef DEBUG_GROW
+ nbElem++;
+#endif
+ iter = next;
+ }
+ }
+
+ xmlFree(oldtable);
+
+#ifdef DEBUG_GROW
+ xmlGenericError(xmlGenericErrorContext,
+ "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
+#endif
+ return(0);
+}
+
+/**
+ * xmlHashFree:
+ * @param table the hash table
+ * @param f the deallocator function for items in the hash
+ *
+ * Free the hash table and its contents. The userdata is
+ * deallocated with f if provided.
+ *
+ * OOM: never // same as argument 'f' has when f!=NULL
+ */
+XMLPUBFUNEXPORT void
+xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) {
+ int i;
+ xmlHashEntryPtr iter;
+ xmlHashEntryPtr next;
+ int inside_table = 0;
+ int nbElems;
+
+ if (table == NULL)
+ return;
+ if (table->table) {
+ nbElems = table->nbElems;
+ for(i = 0; (i < table->size) && (nbElems > 0); i++) {
+ iter = &(table->table[i]);
+ if (iter->valid == 0)
+ continue;
+ inside_table = 1;
+ while (iter) {
+ next = iter->next;
+ if ((f != NULL) && (iter->payload != NULL))
+ f(iter->payload, iter->name);
+ if (iter->name)
+ xmlFree(iter->name);
+ if (iter->name2)
+ xmlFree(iter->name2);
+ if (iter->name3)
+ xmlFree(iter->name3);
+ iter->payload = NULL;
+ if (!inside_table)
+ xmlFree(iter);
+ nbElems--;
+ inside_table = 0;
+ iter = next;
+ }
+ inside_table = 0;
+ }
+ xmlFree(table->table);
+ }
+ xmlFree(table);
+}
+
+/**
+ * xmlHashAddEntry:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param userdata a pointer to the userdata
+ *
+ * Add the userdata to the hash table. This can later be retrieved
+ * by using the name. Duplicate names generate errors.
+ *
+ * Returns 0 the addition succeeded and -1 in case of error.
+ *
+ * OOM: iif returns -1 and flag is set
+ */
+XMLPUBFUNEXPORT int
+xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) {
+ return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
+}
+
+/**
+ * xmlHashAddEntry2:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ * @param userdata a pointer to the userdata
+ *
+ * Add the userdata to the hash table. This can later be retrieved
+ * by using the (name, name2) tuple. Duplicate tuples generate errors.
+ *
+ * Returns 0 the addition succeeded and -1 in case of error.
+ */
+XMLPUBFUNEXPORT int
+xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, void *userdata) {
+ return(xmlHashAddEntry3(table, name, name2, NULL, userdata));
+}
+
+/**
+ * xmlHashUpdateEntry:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param userdata a pointer to the userdata
+ * @param f the deallocator function for replaced item (if any)
+ *
+ * Add the userdata to the hash table. This can later be retrieved
+ * by using the name. Existing entry for this name will be removed
+ * and freed with f if found.
+ *
+ * Returns 0 the addition succeeded and -1 in case of error.
+ */
+XMLPUBFUNEXPORT int
+xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name,
+ void *userdata, xmlHashDeallocator f) {
+ return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
+}
+
+/**
+ * xmlHashUpdateEntry2:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ * @param userdata a pointer to the userdata
+ * @param f the deallocator function for replaced item (if any)
+ *
+ * Add the userdata to the hash table. This can later be retrieved
+ * by using the (name, name2) tuple. Existing entry for this tuple will
+ * be removed and freed with f if found.
+ *
+ * Returns 0 the addition succeeded and -1 in case of error.
+ */
+XMLPUBFUNEXPORT int
+xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, void *userdata,
+ xmlHashDeallocator f) {
+ return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f));
+}
+
+/**
+ * xmlHashLookup:
+ * @param table the hash table
+ * @param name the name of the userdata
+ *
+ * Find the userdata specified by the name.
+ *
+ * Returns the pointer to the userdata
+ */
+XMLPUBFUNEXPORT void *
+xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) {
+ return(xmlHashLookup3(table, name, NULL, NULL));
+}
+
+/**
+ * xmlHashLookup2:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ *
+ * Find the userdata specified by the (name, name2) tuple.
+ *
+ * Returns the pointer to the userdata
+ *
+ * OOM: never
+ */
+XMLPUBFUNEXPORT void*
+xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2) {
+ return(xmlHashLookup3(table, name, name2, NULL));
+}
+
+#ifndef XMLENGINE_EXCLUDE_UNUSED
+/**
+ * xmlHashQLookup:
+ * @param table the hash table
+ * @param prefix the prefix of the userdata
+ * @param name the name of the userdata
+ *
+ * Find the userdata specified by the QName prefix:name/name.
+ *
+ * Returns the pointer to the userdata
+ *
+ * OOM: never
+ */
+void*
+xmlHashQLookup(xmlHashTablePtr table, const xmlChar *prefix,
+ const xmlChar *name) {
+ return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
+}
+#endif /* ifndef XMLENGINE_EXCLUDE_UNUSED */
+
+/**
+ * xmlHashQLookup2:
+ * @param table the hash table
+ * @param prefix the prefix of the userdata
+ * @param name the name of the userdata
+ * @param prefix2 the second prefix of the userdata
+ * @param name2 a second name of the userdata
+ *
+ * Find the userdata specified by the QNames tuple
+ *
+ * Returns the pointer to the userdata
+ */
+XMLPUBFUNEXPORT void *
+xmlHashQLookup2(xmlHashTablePtr table, const xmlChar *prefix,
+ const xmlChar *name, const xmlChar *prefix2,
+ const xmlChar *name2) {
+ return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
+}
+
+/**
+ * xmlHashAddEntry3:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ * @param name3 a third name of the userdata
+ * @param userdata a pointer to the userdata
+ *
+ * Add the userdata to the hash table. This can later be retrieved
+ * by using the tuple (name, name2, name3). Duplicate entries generate
+ * errors.
+ *
+ * Returns 0 the addition succeeded and -1 in case of error.
+ *
+ * OOM: iif returns -1 and flag is set
+ */
+XMLPUBFUNEXPORT int
+xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, const xmlChar *name3,
+ void *userdata) {
+ LOAD_GS_DIRECT
+ unsigned long key, len = 0;
+ xmlHashEntryPtr entry;
+ xmlHashEntryPtr insert;
+ int res;
+
+ if ((table == NULL) || name == NULL)
+ return(-1);
+
+ /*
+ * Check for duplicate and insertion location.
+ */
+ key = xmlHashComputeKey(table, name, name2, name3);
+ if (table->table[key].valid == 0) {
+ insert = NULL;
+ } else {
+ for (insert = &(table->table[key]); insert->next != NULL;
+ insert = insert->next) {
+ if ((xmlStrEqual(insert->name, name)) &&
+ (xmlStrEqual(insert->name2, name2)) &&
+ (xmlStrEqual(insert->name3, name3)))
+ return(-1);
+ len++;
+ }
+ if ((xmlStrEqual(insert->name, name)) &&
+ (xmlStrEqual(insert->name2, name2)) &&
+ (xmlStrEqual(insert->name3, name3)))
+ return(-1);
+ }
+
+ if (insert == NULL) {
+ entry = &(table->table[key]);
+ } else {
+ entry = (xmlHashEntryPtr) xmlMalloc(sizeof(xmlHashEntry)); // may set OOM flag
+ if (entry == NULL)
+ return(-1);
+ }
+ // DONE: Check OOM // DONE: Try to avoid xmlStrdup(NULL)
+
+
+ entry->name = xmlStrdup(name); // name is never NULL here
+ entry->name2 = name2 ? xmlStrdup(name2): (xmlChar*) name2 /* it's NULL here */;
+ entry->name3 = name3 ? xmlStrdup(name3): (xmlChar*) name3 /* it's NULL here */;
+ if(OOM_FLAG){
+ if(entry->name) xmlFree(entry->name);
+ if(entry->name2) xmlFree(entry->name2);
+ if(entry->name3) xmlFree(entry->name3);
+ if(insert) xmlFree(entry);
+ return -1;
+ }
+ entry->payload = userdata;
+ entry->next = NULL;
+ entry->valid = 1;
+
+ if (insert != NULL)
+ insert->next = entry;
+
+ table->nbElems++;
+
+ res = 0;
+ if (len > MAX_HASH_LEN){
+ res = xmlHashGrow(table, MAX_HASH_LEN * table->size);
+ }
+
+ return(res);
+}
+
+/**
+ * xmlHashUpdateEntry3:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ * @param name3 a third name of the userdata
+ * @param userdata a pointer to the userdata
+ * @param f the deallocator function for replaced item (if any)
+ *
+ * Add the userdata to the hash table. This can later be retrieved
+ * by using the tuple (name, name2, name3). Existing entry for this tuple
+ * will be removed and freed with f if found.
+ *
+ * Returns 0 the addition succeeded and -1 in case of error.
+ */
+XMLPUBFUNEXPORT int
+xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, const xmlChar *name3,
+ void *userdata, xmlHashDeallocator f) {
+ LOAD_GS_DIRECT
+ unsigned long key;
+ xmlHashEntryPtr entry;
+ xmlHashEntryPtr insert;
+
+ if ((table == NULL) || name == NULL)
+ return(-1);
+
+ /*
+ * Check for duplicate and insertion location.
+ */
+ key = xmlHashComputeKey(table, name, name2, name3);
+ if (table->table[key].valid == 0) {
+ insert = NULL;
+ } else {
+ for (insert = &(table->table[key]); insert->next != NULL;
+ insert = insert->next) {
+ if ((xmlStrEqual(insert->name, name)) &&
+ (xmlStrEqual(insert->name2, name2)) &&
+ (xmlStrEqual(insert->name3, name3))) {
+ if (f)
+ f(insert->payload, insert->name);
+ insert->payload = userdata;
+ return(0);
+ }
+ }
+ if ((xmlStrEqual(insert->name, name)) &&
+ (xmlStrEqual(insert->name2, name2)) &&
+ (xmlStrEqual(insert->name3, name3))) {
+ if (f)
+ f(insert->payload, insert->name);
+ insert->payload = userdata;
+ return(0);
+ }
+ }
+
+ if (!insert) {
+ entry = &(table->table[key]);
+ } else {
+ entry = (xmlHashEntryPtr)xmlMalloc(sizeof(xmlHashEntry));
+ if (entry == NULL)
+ return(-1);
+ }
+ // DONE: Check OOM
+ entry->name = xmlStrdup(name); // name is never NULL here
+ entry->name2 = name2 ? xmlStrdup(name2): NULL;
+ entry->name3 = name3 ? xmlStrdup(name3): NULL;
+ if(OOM_FLAG){
+ if(entry->name) xmlFree(entry->name);
+ if(entry->name2) xmlFree(entry->name2);
+ if(entry->name3) xmlFree(entry->name3);
+ if(insert) xmlFree(entry);
+ return -1;
+ }
+ entry->payload = userdata;
+ entry->next = NULL;
+ entry->valid = 1;
+ table->nbElems++;
+
+
+ if (insert) {
+ insert->next = entry;
+ }
+ return(0);
+}
+
+/**
+ * xmlHashLookup3:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ * @param name3 a third name of the userdata
+ *
+ * Find the userdata specified by the (name, name2, name3) tuple.
+ *
+ * Returns the a pointer to the userdata
+ *
+ * OOM: never
+ */
+XMLPUBFUNEXPORT void *
+xmlHashLookup3(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, const xmlChar *name3)
+{
+ unsigned long key;
+ xmlHashEntryPtr entry;
+
+ if (table == NULL)
+ return(NULL);
+ if (name == NULL)
+ return(NULL);
+ key = xmlHashComputeKey(table, name, name2, name3);
+ if (table->table[key].valid == 0)
+ return(NULL);
+ for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
+ if ((xmlStrEqual(entry->name, name)) &&
+ (xmlStrEqual(entry->name2, name2)) &&
+ (xmlStrEqual(entry->name3, name3)))
+ return(entry->payload);
+ }
+ return(NULL);
+}
+
+/**
+ * xmlHashQLookup3:
+ * @param table the hash table
+ * @param prefix the prefix of the userdata
+ * @param name the name of the userdata
+ * @param prefix2 the second prefix of the userdata
+ * @param name2 a second name of the userdata
+ * @param prefix3 the third prefix of the userdata
+ * @param name3 a third name of the userdata
+ *
+ * Find the userdata specified by the (name, name2, name3) tuple.
+ *
+ * Returns the a pointer to the userdata
+ */
+XMLPUBFUNEXPORT void *
+xmlHashQLookup3(xmlHashTablePtr table,
+ const xmlChar *prefix, const xmlChar *name,
+ const xmlChar *prefix2, const xmlChar *name2,
+ const xmlChar *prefix3, const xmlChar *name3) {
+ unsigned long key;
+ xmlHashEntryPtr entry;
+
+ if (table == NULL)
+ return(NULL);
+ if (name == NULL)
+ return(NULL);
+ key = xmlHashComputeQKey(table, prefix, name, prefix2,
+ name2, prefix3, name3);
+ if (table->table[key].valid == 0)
+ return(NULL);
+ for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
+ if ((xmlStrQEqual(prefix, name, entry->name)) &&
+ (xmlStrQEqual(prefix2, name2, entry->name2)) &&
+ (xmlStrQEqual(prefix3, name3, entry->name3)))
+ return(entry->payload);
+ }
+ return(NULL);
+}
+
+typedef struct {
+ xmlHashScanner hashscanner;
+ void *data;
+} stubData;
+
+static void
+stubHashScannerFull (void *payload, void *data, const xmlChar *name,
+ const xmlChar *name2 ATTRIBUTE_UNUSED,
+ const xmlChar *name3 ATTRIBUTE_UNUSED) {
+ stubData *stubdata = (stubData *) data;
+ stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
+}
+
+/**
+ * xmlHashScan:
+ * @param table the hash table
+ * @param f the scanner function for items in the hash
+ * @param data extra data passed to f
+ *
+ * Scan the hash table and applied f to each value.
+ */
+XMLPUBFUNEXPORT void
+xmlHashScan(xmlHashTablePtr table, xmlHashScanner f, void *data) {
+ stubData stubdata;
+ stubdata.data = data;
+ stubdata.hashscanner = f;
+ xmlHashScanFull (table, stubHashScannerFull, &stubdata);
+}
+
+/**
+ * xmlHashScanFull:
+ * @param table the hash table
+ * @param f the scanner function for items in the hash
+ * @param data extra data passed to f
+ *
+ * Scan the hash table and applied f to each value.
+ */
+XMLPUBFUNEXPORT void
+xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data) {
+ int i;
+ xmlHashEntryPtr iter;
+ xmlHashEntryPtr next;
+
+ if (table == NULL)
+ return;
+ if (f == NULL)
+ return;
+
+ if (table->table) {
+ for(i = 0; i < table->size; i++) {
+ if (table->table[i].valid == 0)
+ continue;
+ iter = &(table->table[i]);
+ while (iter) {
+ next = iter->next;
+ if ((f != NULL) && (iter->payload != NULL))
+ f(iter->payload, data, iter->name,
+ iter->name2, iter->name3);
+ iter = next;
+ }
+ }
+ }
+}
+
+/**
+ * xmlHashScan3:
+ * @param table the hash table
+ * @param name the name of the userdata or NULL
+ * @param name2 a second name of the userdata or NULL
+ * @param name3 a third name of the userdata or NULL
+ * @param f the scanner function for items in the hash
+ * @param data extra data passed to f
+ *
+ * Scan the hash table and applied f to each value matching
+ * (name, name2, name3) tuple. If one of the names is null,
+ * the comparison is considered to match.
+ */
+XMLPUBFUNEXPORT void
+xmlHashScan3(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, const xmlChar *name3,
+ xmlHashScanner f, void *data) {
+ xmlHashScanFull3 (table, name, name2, name3,
+ (xmlHashScannerFull) f, data);
+}
+
+/**
+ * xmlHashScanFull3:
+ * @param table the hash table
+ * @param name the name of the userdata or NULL
+ * @param name2 a second name of the userdata or NULL
+ * @param name3 a third name of the userdata or NULL
+ * @param f the scanner function for items in the hash
+ * @param data extra data passed to f
+ *
+ * Scan the hash table and applied f to each value matching
+ * (name, name2, name3) tuple. If one of the names is null,
+ * the comparison is considered to match.
+ */
+XMLPUBFUNEXPORT void
+xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, const xmlChar *name3,
+ xmlHashScannerFull f, void *data) {
+ int i;
+ xmlHashEntryPtr iter;
+ xmlHashEntryPtr next;
+
+ if (table == NULL)
+ return;
+ if (f == NULL)
+ return;
+
+ if (table->table) {
+ for(i = 0; i < table->size; i++) {
+ if (table->table[i].valid == 0)
+ continue;
+ iter = &(table->table[i]);
+ while (iter) {
+ next = iter->next;
+ if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
+ ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
+ ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
+ (iter->payload != NULL)) {
+ f(iter->payload, data, iter->name,
+ iter->name2, iter->name3);
+ }
+ iter = next;
+ }
+ }
+ }
+}
+
+/**
+ * xmlHashCopy:
+ * @param table the hash table
+ * @param f the copier function for items in the hash
+ *
+ * Scan the hash table and applied f to each value.
+ *
+ * Returns the new table or NULL in case of error.
+ *
+ * OOM: possible --> returns NULL, OOM flag is set
+ */
+XMLPUBFUNEXPORT xmlHashTablePtr
+xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f)
+{
+ LOAD_GS_DIRECT
+ int i;
+ xmlHashEntryPtr iter;
+ xmlHashEntryPtr next;
+ xmlHashTablePtr ret;
+ //int res;
+ void* pCopy;
+
+ if (table == NULL)
+ return(NULL);
+ if (f == NULL)
+ return(NULL);
+
+ ret = xmlHashCreate(table->size); // may set OOM flag
+ if(!ret)
+ return NULL; // OOM happened, the flag is set already
+
+ if (table->table) {
+ for(i = 0; i < table->size; i++)
+ {
+ if (table->table[i].valid == 0)
+ continue;
+ iter = &(table->table[i]);
+ while (iter)
+ {
+ next = iter->next;
+ pCopy = f(iter->payload, iter->name);
+ if(OOM_FLAG)
+ goto oom;
+ //res =
+ xmlHashAddEntry3(
+ ret,
+ iter->name,
+ iter->name2,
+ iter->name3,
+ pCopy);
+ if(OOM_FLAG)
+ goto oom;
+ iter = next;
+ }
+ }
+ }
+ ret->nbElems = table->nbElems;
+ return(ret);
+oom:
+ // OOM during copying entry in f()
+ xmlHashFree(ret, NULL);
+ return NULL;
+}
+
+#ifndef XMLENGINE_EXCLUDE_UNUSED
+/**
+ * xmlHashSize:
+ * @param table the hash table
+ *
+ * Query the number of elements installed in the hash table.
+ *
+ * Returns the number of elements in the hash table or
+ * -1 in case of error
+ */
+int
+xmlHashSize(xmlHashTablePtr table)
+{
+ if (table == NULL)
+ return(-1);
+ return(table->nbElems);
+}
+#endif /* ifndef XMLENGINE_EXCLUDE_UNUSED */
+
+/**
+ * xmlHashRemoveEntry:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param f the deallocator function for removed item (if any)
+ *
+ * Find the userdata specified by the name and remove
+ * it from the hash table. Existing userdata for this tuple will be removed
+ * and freed with f.
+ *
+ * Returns 0 if the removal succeeded and -1 in case of error or not found.
+ *
+ * OOM: never / same as argument function 'f' has, if f!=NULL*
+ */
+XMLPUBFUNEXPORT int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name,
+ xmlHashDeallocator f)
+{
+ return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
+}
+
+/**
+ * xmlHashRemoveEntry2:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ * @param f the deallocator function for removed item (if any)
+ *
+ * Find the userdata specified by the (name, name2) tuple and remove
+ * it from the hash table. Existing userdata for this tuple will be removed
+ * and freed with f.
+ *
+ * Returns 0 if the removal succeeded and -1 in case of error or not found.
+ */
+XMLPUBFUNEXPORT int
+xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, xmlHashDeallocator f) {
+ return(xmlHashRemoveEntry3(table, name, name2, NULL, f));
+}
+
+/**
+ * xmlHashRemoveEntry3:
+ * @param table the hash table
+ * @param name the name of the userdata
+ * @param name2 a second name of the userdata
+ * @param name3 a third name of the userdata
+ * @param f the deallocator function for removed item (if any)
+ *
+ * Find the userdata specified by the (name, name2, name3) tuple and remove
+ * it from the hash table. Existing userdata for this tuple will be removed
+ * and freed with f.
+ *
+ * Returns 0 if the removal succeeded and -1 in case of error or not found.
+ *
+ * OOM: never / same as argument function 'f' has, if f!=NULL
+ */
+XMLPUBFUNEXPORT int
+xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name,
+ const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f)
+{
+ unsigned long key;
+ xmlHashEntryPtr entry;
+ xmlHashEntryPtr prev = NULL;
+
+ if (table == NULL || name == NULL)
+ return(-1);
+
+ key = xmlHashComputeKey(table, name, name2, name3);
+ if (table->table[key].valid == 0) {
+ return(-1);
+ } else {
+ for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
+ if (xmlStrEqual(entry->name, name) &&
+ xmlStrEqual(entry->name2, name2) &&
+ xmlStrEqual(entry->name3, name3)) {
+ if ((f != NULL) && (entry->payload != NULL))
+ f(entry->payload, entry->name);
+ entry->payload = NULL;
+ if(entry->name)
+ xmlFree(entry->name);
+ if(entry->name2)
+ xmlFree(entry->name2);
+ if(entry->name3)
+ xmlFree(entry->name3);
+ if(prev) {
+ prev->next = entry->next;
+ xmlFree(entry);
+ } else {
+ if (entry->next == NULL) {
+ entry->valid = 0;
+ } else {
+ entry = entry->next;
+ memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
+ xmlFree(entry);
+ }
+ }
+ table->nbElems--;
+ return(0);
+ }
+ prev = entry;
+ }
+ return(-1);
+ }
+}