From 3473f88a7abdf4e585e267288fb77e898c580d2b Mon Sep 17 00:00:00 2001 From: Owen Taylor Date: Fri, 23 Feb 2001 17:55:21 +0000 Subject: Revert directory structure changes --- hash.c | 620 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 620 insertions(+) create mode 100644 hash.c (limited to 'hash.c') diff --git a/hash.c b/hash.c new file mode 100644 index 00000000..7881fc64 --- /dev/null +++ b/hash.c @@ -0,0 +1,620 @@ +/* + * 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: bjorn.reese@systematic.dk + */ + +#ifdef WIN32 +#include "win32config.h" +#else +#include "config.h" +#endif + +#include +#include +#include +#include + +/* + * 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; +}; + +/* + * The entire hash table + */ +struct _xmlHashTable { + struct _xmlHashEntry **table; + int size; + int nbElems; +}; + +/* + * xmlHashComputeKey: + * Calculate the hash key + */ +static unsigned long +xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *string) { + unsigned long value = 0L; + char ch; + + while ((ch = *string++) != 0) { + /* value *= 31; */ + value += (unsigned long)ch; + } + return (value % table->size); +} + +/** + * xmlHashCreate: + * @size: the size of the hash table + * + * Create a new xmlHashTablePtr. + * + * Returns the newly created object, or NULL if an error occured. + */ +xmlHashTablePtr +xmlHashCreate(int size) { + xmlHashTablePtr table; + + if (size <= 0) + size = 256; + + table = xmlMalloc(sizeof(xmlHashTable)); + if (table) { + table->size = size; + table->nbElems = 0; + table->table = xmlMalloc(size * sizeof(xmlHashEntry)); + if (table->table) { + memset(table->table, 0, size * sizeof(xmlHashEntry)); + return(table); + } + xmlFree(table); + } + return(NULL); +} + +/** + * xmlHashFree: + * @table: the hash table + * @f: the deallocator function for items in the hash + * + * Free the hash table and its contents. The userdata is + * deallocated with f if provided. + */ +void +xmlHashFree(xmlHashTablePtr table, xmlHashDeallocator f) { + int i; + xmlHashEntryPtr iter; + xmlHashEntryPtr next; + + if (table == NULL) + return; + if (table->table) { + for(i = 0; i < table->size; i++) { + iter = table->table[i]; + while (iter) { + next = iter->next; + if (iter->name) + xmlFree(iter->name); + if (iter->name2) + xmlFree(iter->name2); + if (iter->name3) + xmlFree(iter->name3); + if (f) + f(iter->payload, iter->name); + iter->payload = NULL; + xmlFree(iter); + iter = next; + } + table->table[i] = NULL; + } + xmlFree(table->table); + } + xmlFree(table); +} + +/** + * xmlHashAddEntry: + * @table: the hash table + * @name: the name of the userdata + * @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. + */ +int +xmlHashAddEntry(xmlHashTablePtr table, const xmlChar *name, void *userdata) { + return(xmlHashAddEntry3(table, name, NULL, NULL, userdata)); +} + +/** + * xmlHashAddEntry2: + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * @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. + */ +int +xmlHashAddEntry2(xmlHashTablePtr table, const xmlChar *name, + const xmlChar *name2, void *userdata) { + return(xmlHashAddEntry3(table, name, name2, NULL, userdata)); +} + +/** + * xmlHashUpdateEntry: + * @table: the hash table + * @name: the name of the userdata + * @userdata: a pointer to the userdata + * @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. + */ +int +xmlHashUpdateEntry(xmlHashTablePtr table, const xmlChar *name, + void *userdata, xmlHashDeallocator f) { + return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f)); +} + +/** + * xmlHashUpdateEntry2: + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * @userdata: a pointer to the userdata + * @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. + */ +int +xmlHashUpdateEntry2(xmlHashTablePtr table, const xmlChar *name, + const xmlChar *name2, void *userdata, + xmlHashDeallocator f) { + return(xmlHashUpdateEntry3(table, name, name2, NULL, userdata, f)); +} + +/** + * xmlHashLookup: + * @table: the hash table + * @name: the name of the userdata + * + * Find the userdata specified by the name. + * + * Returns the a pointer to the userdata + */ +void * +xmlHashLookup(xmlHashTablePtr table, const xmlChar *name) { + return(xmlHashLookup3(table, name, NULL, NULL)); +} + +/** + * xmlHashLookup2: + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * + * Find the userdata specified by the (name, name2) tuple. + * + * Returns the a pointer to the userdata + */ +void * +xmlHashLookup2(xmlHashTablePtr table, const xmlChar *name, + const xmlChar *name2) { + return(xmlHashLookup3(table, name, name2, NULL)); +} + +/** + * xmlHashAddEntry3: + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * @name3: a third name of the userdata + * @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. + */ +int +xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name, + const xmlChar *name2, const xmlChar *name3, + void *userdata) { + unsigned long key; + xmlHashEntryPtr entry; + xmlHashEntryPtr insert; + + if ((table == NULL) || name == NULL) + return(-1); + + /* + * Check for duplicate and insertion location. + */ + key = xmlHashComputeKey(table, name); + if (table->table[key] == NULL) { + 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); + } + if ((xmlStrEqual(insert->name, name)) && + (xmlStrEqual(insert->name2, name2)) && + (xmlStrEqual(insert->name3, name3))) + return(-1); + } + + entry = xmlMalloc(sizeof(xmlHashEntry)); + if (entry == NULL) + return(-1); + entry->name = xmlStrdup(name); + entry->name2 = xmlStrdup(name2); + entry->name3 = xmlStrdup(name3); + entry->payload = userdata; + entry->next = NULL; + + + if (insert == NULL) { + table->table[key] = entry; + } else { + insert->next = entry; + } + table->nbElems++; + return(0); +} + +/** + * xmlHashUpdateEntry3: + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * @name3: a third name of the userdata + * @userdata: a pointer to the userdata + * @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. + */ +int +xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name, + const xmlChar *name2, const xmlChar *name3, + void *userdata, xmlHashDeallocator f) { + unsigned long key; + xmlHashEntryPtr entry; + xmlHashEntryPtr insert; + + if ((table == NULL) || name == NULL) + return(-1); + + /* + * Check for duplicate and insertion location. + */ + key = xmlHashComputeKey(table, name); + if (table->table[key] == NULL) { + 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); + } + } + + entry = xmlMalloc(sizeof(xmlHashEntry)); + if (entry == NULL) + return(-1); + entry->name = xmlStrdup(name); + entry->name2 = xmlStrdup(name2); + entry->name3 = xmlStrdup(name3); + entry->payload = userdata; + entry->next = NULL; + table->nbElems++; + + + if (insert == NULL) { + table->table[key] = entry; + } else { + insert->next = entry; + } + return(0); +} + +/** + * xmlHashLookup: + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * @name3: a third name of the userdata + * + * Find the userdata specified by the (name, name2, name3) tuple. + * + * Returns the a pointer to the userdata + */ +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); + 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); +} + +/** + * xmlHashScan: + * @table: the hash table + * @f: the scanner function for items in the hash + * @data: extra data passed to f + * + * Scan the hash table and applied f to each value. + */ +void +xmlHashScan(xmlHashTablePtr table, xmlHashScanner 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++) { + iter = table->table[i]; + while (iter) { + next = iter->next; + if (f) + f(iter->payload, data, iter->name); + iter = next; + } + } + } +} + +/** + * xmlHashScan3: + * @table: the hash table + * @name: the name of the userdata or NULL + * @name2: a second name of the userdata or NULL + * @name3: a third name of the userdata or NULL + * @f: the scanner function for items in the hash + * @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. + */ +void +xmlHashScan3(xmlHashTablePtr table, const xmlChar *name, + const xmlChar *name2, const xmlChar *name3, + xmlHashScanner 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++) { + 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)))) { + f(iter->payload, data, iter->name); + } + iter = next; + } + } + } +} + +/** + * xmlHashCopy: + * @table: the hash table + * @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. + */ +xmlHashTablePtr +xmlHashCopy(xmlHashTablePtr table, xmlHashCopier f) { + int i; + xmlHashEntryPtr iter; + xmlHashEntryPtr next; + xmlHashTablePtr ret; + + if (table == NULL) + return(NULL); + if (f == NULL) + return(NULL); + + ret = xmlHashCreate(table->size); + if (table->table) { + for(i = 0; i < table->size; i++) { + iter = table->table[i]; + while (iter) { + next = iter->next; + xmlHashAddEntry3(ret, iter->name, iter->name2, + iter->name3, f(iter->payload, iter->name)); + iter = next; + } + } + } + ret->nbElems = table->nbElems; + return(ret); +} + +/** + * xmlHashSize: + * @table: 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); +} + +/** + * @table: the hash table + * @name: the name of the userdata + * @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. + */ +int xmlHashRemoveEntry(xmlHashTablePtr table, const xmlChar *name, + xmlHashDeallocator f) { + return(xmlHashRemoveEntry3(table, name, NULL, NULL, f)); +} + +/** + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * @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. + */ +int xmlHashRemoveEntry2(xmlHashTablePtr table, const xmlChar *name, + const xmlChar *name2, xmlHashDeallocator f) { + return(xmlHashRemoveEntry3(table, name, name2, NULL, f)); +} + +/** + * @table: the hash table + * @name: the name of the userdata + * @name2: a second name of the userdata + * @name3: a third name of the userdata + * @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. + */ +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); + if (table->table[key] == NULL) { + 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) + 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; + else + table->table[key] = entry->next; + xmlFree(entry); + table->nbElems--; + return(0); + } + prev = entry; + } + return(-1); + } +} \ No newline at end of file -- cgit v1.2.1