Something went wrong. Try again.
Reactos
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215/* * hash.c: hash tables * * Hash table with open addressing, linear probing and * Robin Hood reordering. * * See Copyright for the status of this software. */
#define IN_LIBXML#include "libxml.h"
#include <string.h>#include <limits.h>
#include <libxml/parser.h>#include <libxml/hash.h>#include <libxml/dict.h>#include <libxml/xmlmemory.h>#include <libxml/xmlstring.h>
#include "private/dict.h"
#ifndef SIZE_MAX #define SIZE_MAX ((size_t) -1)#endif
#define MAX_FILL_NUM 7#define MAX_FILL_DENOM 8#define MIN_HASH_SIZE 8#define MAX_HASH_SIZE (1u << 31)
/* * A single entry in the hash table */typedef struct { unsigned hashValue; /* 0 means unoccupied, occupied entries have the * MAX_HASH_SIZE bit set to 1 */ xmlChar *key; xmlChar *key2; /* TODO: Don't allocate possibly empty keys */ xmlChar *key3; void *payload;} xmlHashEntry;
/* * The entire hash table */struct _xmlHashTable { xmlHashEntry *table; unsigned size; /* power of two */ unsigned nbElems; xmlDictPtr dict; unsigned randomSeed;};
static intxmlHashGrow(xmlHashTablePtr hash, unsigned size);
ATTRIBUTE_NO_SANITIZE_INTEGERstatic unsignedxmlHashValue(unsigned seed, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, size_t *lengths) { unsigned h1, h2; size_t i;
HASH_INIT(h1, h2, seed);
for (i = 0; key[i] != 0; i++) { HASH_UPDATE(h1, h2, key[i]); } if (lengths) lengths[0] = i;
HASH_UPDATE(h1, h2, 0);
if (key2 != NULL) { for (i = 0; key2[i] != 0; i++) { HASH_UPDATE(h1, h2, key2[i]); } if (lengths) lengths[1] = i; }
HASH_UPDATE(h1, h2, 0);
if (key3 != NULL) { for (i = 0; key3[i] != 0; i++) { HASH_UPDATE(h1, h2, key3[i]); } if (lengths) lengths[2] = i; }
HASH_FINISH(h1, h2);
return(h2);}
ATTRIBUTE_NO_SANITIZE_INTEGERstatic unsignedxmlHashQNameValue(unsigned seed, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3) { unsigned h1, h2, ch;
HASH_INIT(h1, h2, seed);
if (prefix != NULL) { while ((ch = *prefix++) != 0) { HASH_UPDATE(h1, h2, ch); } HASH_UPDATE(h1, h2, ':'); } if (name != NULL) { while ((ch = *name++) != 0) { HASH_UPDATE(h1, h2, ch); } } HASH_UPDATE(h1, h2, 0); if (prefix2 != NULL) { while ((ch = *prefix2++) != 0) { HASH_UPDATE(h1, h2, ch); } HASH_UPDATE(h1, h2, ':'); } if (name2 != NULL) { while ((ch = *name2++) != 0) { HASH_UPDATE(h1, h2, ch); } } HASH_UPDATE(h1, h2, 0); if (prefix3 != NULL) { while ((ch = *prefix3++) != 0) { HASH_UPDATE(h1, h2, ch); } HASH_UPDATE(h1, h2, ':'); } if (name3 != NULL) { while ((ch = *name3++) != 0) { HASH_UPDATE(h1, h2, ch); } }
HASH_FINISH(h1, h2);
return(h2);}
/** * xmlHashCreate: * @size: initial size of the hash table * * Create a new hash table. Set size to zero if the number of entries * can't be estimated. * * Returns the newly created object, or NULL if a memory allocation failed. */xmlHashTablePtrxmlHashCreate(int size) { xmlHashTablePtr hash;
xmlInitParser();
hash = xmlMalloc(sizeof(*hash)); if (hash == NULL) return(NULL); hash->dict = NULL; hash->size = 0; hash->table = NULL; hash->nbElems = 0; hash->randomSeed = xmlRandom();#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION hash->randomSeed = 0;#endif
/* * Unless a larger size is passed, the backing table is created * lazily with MIN_HASH_SIZE capacity. In practice, there are many * hash tables which are never filled. */ if (size > MIN_HASH_SIZE) { unsigned newSize = MIN_HASH_SIZE * 2;
while ((newSize < (unsigned) size) && (newSize < MAX_HASH_SIZE)) newSize *= 2;
if (xmlHashGrow(hash, newSize) != 0) { xmlFree(hash); return(NULL); } }
return(hash);}
/** * xmlHashCreateDict: * @size: the size of the hash table * @dict: a dictionary to use for the hash * * Create a new hash table backed by a dictionary. This can reduce * resource usage considerably if most keys passed to API functions * originate from this dictionary. * * Returns the newly created object, or NULL if a memory allocation failed. */xmlHashTablePtrxmlHashCreateDict(int size, xmlDictPtr dict) { xmlHashTablePtr hash;
hash = xmlHashCreate(size); if (hash != NULL) { hash->dict = dict; xmlDictReference(dict); } return(hash);}
/** * xmlHashFree: * @hash: hash table * @dealloc: deallocator function or NULL * * Free the hash and its contents. The payload is deallocated with * @dealloc if provided. */voidxmlHashFree(xmlHashTablePtr hash, xmlHashDeallocator dealloc) { if (hash == NULL) return;
if (hash->table) { const xmlHashEntry *end = &hash->table[hash->size]; const xmlHashEntry *entry;
for (entry = hash->table; entry < end; entry++) { if (entry->hashValue == 0) continue; if ((dealloc != NULL) && (entry->payload != NULL)) dealloc(entry->payload, entry->key); if (hash->dict == NULL) { if (entry->key) xmlFree(entry->key); if (entry->key2) xmlFree(entry->key2); if (entry->key3) xmlFree(entry->key3); } }
xmlFree(hash->table); }
if (hash->dict) xmlDictFree(hash->dict);
xmlFree(hash);}
/** * xmlFastStrEqual: * @s1: string * @s2: string * * Compare two strings for equality, allowing NULL values. */static intxmlFastStrEqual(const xmlChar *s1, const xmlChar *s2) { if (s1 == NULL) return(s2 == NULL); else return((s2 != NULL) && (strcmp((const char *) s1, (const char *) s2) == 0));}
/** * xmlHashFindEntry: * @hash: hash table, non-NULL, size > 0 * @key: first string key, non-NULL * @key2: second string key * @key3: third string key * @hashValue: valid hash value of keys * @pfound: result of search * * Try to find a matching hash table entry. If an entry was found, set * @found to 1 and return the entry. Otherwise, set @found to 0 and return * the location where a new entry should be inserted. */ATTRIBUTE_NO_SANITIZE_INTEGERstatic xmlHashEntry *xmlHashFindEntry(const xmlHashTable *hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, unsigned hashValue, int *pfound) { xmlHashEntry *entry; unsigned mask, pos, displ; int found = 0;
mask = hash->size - 1; pos = hashValue & mask; entry = &hash->table[pos];
if (entry->hashValue != 0) { /* * Robin hood hashing: abort if the displacement of the entry * is smaller than the displacement of the key we look for. * This also stops at the correct position when inserting. */ displ = 0; hashValue |= MAX_HASH_SIZE;
do { if (entry->hashValue == hashValue) { if (hash->dict) { if ((entry->key == key) && (entry->key2 == key2) && (entry->key3 == key3)) { found = 1; break; } } if ((strcmp((const char *) entry->key, (const char *) key) == 0) && (xmlFastStrEqual(entry->key2, key2)) && (xmlFastStrEqual(entry->key3, key3))) { found = 1; break; } }
displ++; pos++; entry++; if ((pos & mask) == 0) entry = hash->table; } while ((entry->hashValue != 0) && (((pos - entry->hashValue) & mask) >= displ)); }
*pfound = found; return(entry);}
/** * xmlHashGrow: * @hash: hash table * @size: new size of the hash table * * Resize the hash table. * * Returns 0 in case of success, -1 if a memory allocation failed. */static intxmlHashGrow(xmlHashTablePtr hash, unsigned size) { const xmlHashEntry *oldentry, *oldend, *end; xmlHashEntry *table; unsigned oldsize, i;
/* Add 0 to avoid spurious -Wtype-limits warning on 64-bit GCC */ if ((size_t) size + 0 > SIZE_MAX / sizeof(table[0])) return(-1); table = xmlMalloc(size * sizeof(table[0])); if (table == NULL) return(-1); memset(table, 0, size * sizeof(table[0]));
oldsize = hash->size; if (oldsize == 0) goto done;
oldend = &hash->table[oldsize]; end = &table[size];
/* * Robin Hood sorting order is maintained if we * * - compute hash indices with modulo * - resize by an integer factor * - start to copy from the beginning of a probe sequence */ oldentry = hash->table; while (oldentry->hashValue != 0) { if (++oldentry >= oldend) oldentry = hash->table; }
for (i = 0; i < oldsize; i++) { if (oldentry->hashValue != 0) { xmlHashEntry *entry = &table[oldentry->hashValue & (size - 1)];
while (entry->hashValue != 0) { if (++entry >= end) entry = table; } *entry = *oldentry; }
if (++oldentry >= oldend) oldentry = hash->table; }
xmlFree(hash->table);
done: hash->table = table; hash->size = size;
return(0);}
/** * xmlHashUpdateInternal: * @hash: hash table * @key: first string key * @key2: second string key * @key3: third string key * @payload: pointer to the payload * @dealloc: deallocator function for replaced item or NULL * @update: whether existing entries should be updated * * Internal function to add or update hash entries. */ATTRIBUTE_NO_SANITIZE_INTEGERstatic intxmlHashUpdateInternal(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, void *payload, xmlHashDeallocator dealloc, int update) { xmlChar *copy, *copy2, *copy3; xmlHashEntry *entry = NULL; size_t lengths[3]; unsigned hashValue; int found = 0;
if ((hash == NULL) || (key == NULL)) return(-1);
/* * Check for an existing entry */ hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, lengths); if (hash->size > 0) entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); if (found) { if (update) { if (dealloc) dealloc(entry->payload, entry->key); entry->payload = payload; return(0); } else { /* * xmlHashAddEntry found an existing entry. * * TODO: We should return a different error code here to * distinguish from malloc failures. */ return(-1); } }
/* * Grow the hash table if needed */ if (hash->nbElems + 1 > hash->size / MAX_FILL_DENOM * MAX_FILL_NUM) { unsigned newSize, mask, displ, pos;
if (hash->size == 0) { newSize = MIN_HASH_SIZE; } else { /* This guarantees that nbElems < INT_MAX */ if (hash->size >= MAX_HASH_SIZE) return(-1); newSize = hash->size * 2; } if (xmlHashGrow(hash, newSize) != 0) return(-1);
/* * Find new entry */ mask = hash->size - 1; displ = 0; pos = hashValue & mask; entry = &hash->table[pos];
if (entry->hashValue != 0) { do { displ++; pos++; entry++; if ((pos & mask) == 0) entry = hash->table; } while ((entry->hashValue != 0) && ((pos - entry->hashValue) & mask) >= displ); } }
/* * Copy keys */ if (hash->dict != NULL) { if (xmlDictOwns(hash->dict, key)) { copy = (xmlChar *) key; } else { copy = (xmlChar *) xmlDictLookup(hash->dict, key, -1); if (copy == NULL) return(-1); }
if ((key2 == NULL) || (xmlDictOwns(hash->dict, key2))) { copy2 = (xmlChar *) key2; } else { copy2 = (xmlChar *) xmlDictLookup(hash->dict, key2, -1); if (copy2 == NULL) return(-1); } if ((key3 == NULL) || (xmlDictOwns(hash->dict, key3))) { copy3 = (xmlChar *) key3; } else { copy3 = (xmlChar *) xmlDictLookup(hash->dict, key3, -1); if (copy3 == NULL) return(-1); } } else { copy = xmlMalloc(lengths[0] + 1); if (copy == NULL) return(-1); memcpy(copy, key, lengths[0] + 1);
if (key2 != NULL) { copy2 = xmlMalloc(lengths[1] + 1); if (copy2 == NULL) { xmlFree(copy); return(-1); } memcpy(copy2, key2, lengths[1] + 1); } else { copy2 = NULL; }
if (key3 != NULL) { copy3 = xmlMalloc(lengths[2] + 1); if (copy3 == NULL) { xmlFree(copy); xmlFree(copy2); return(-1); } memcpy(copy3, key3, lengths[2] + 1); } else { copy3 = NULL; } }
/* * Shift the remainder of the probe sequence to the right */ if (entry->hashValue != 0) { const xmlHashEntry *end = &hash->table[hash->size]; const xmlHashEntry *cur = entry;
do { cur++; if (cur >= end) cur = hash->table; } while (cur->hashValue != 0);
if (cur < entry) { /* * If we traversed the end of the buffer, handle the part * at the start of the buffer. */ memmove(&hash->table[1], hash->table, (char *) cur - (char *) hash->table); cur = end - 1; hash->table[0] = *cur; }
memmove(&entry[1], entry, (char *) cur - (char *) entry); }
/* * Populate entry */ entry->key = copy; entry->key2 = copy2; entry->key3 = copy3; entry->payload = payload; /* OR with MAX_HASH_SIZE to make sure that the value is non-zero */ entry->hashValue = hashValue | MAX_HASH_SIZE;
hash->nbElems++;
return(0);}
/** * xmlHashDefaultDeallocator: * @entry: hash table entry * @key: the entry's string key * * Free a hash table entry with xmlFree. */voidxmlHashDefaultDeallocator(void *entry, const xmlChar *key ATTRIBUTE_UNUSED) { xmlFree(entry);}
/** * xmlHashAddEntry: * @hash: hash table * @key: string key * @payload: pointer to the payload * * Add a hash table entry. If an entry with this key already exists, * payload will not be updated and -1 is returned. This return value * can't be distinguished from out-of-memory errors, so this function * should be used with care. * * Returns 0 on success and -1 in case of error. */intxmlHashAddEntry(xmlHashTablePtr hash, const xmlChar *key, void *payload) { return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0));}
/** * xmlHashAddEntry2: * @hash: hash table * @key: first string key * @key2: second string key * @payload: pointer to the payload * * Add a hash table entry with two strings as key. * * See xmlHashAddEntry. * * Returns 0 on success and -1 in case of error. */intxmlHashAddEntry2(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, void *payload) { return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0));}
/** * xmlHashAddEntry3: * @hash: hash table * @key: first string key * @key2: second string key * @key3: third string key * @payload: pointer to the payload * * Add a hash table entry with three strings as key. * * See xmlHashAddEntry. * * Returns 0 on success and -1 in case of error. */intxmlHashAddEntry3(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, void *payload) { return(xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0));}
/** * xmlHashUpdateEntry: * @hash: hash table * @key: string key * @payload: pointer to the payload * @dealloc: deallocator function for replaced item or NULL * * Add a hash table entry. If an entry with this key already exists, * the old payload will be freed and updated with the new value. * * Returns 0 in case of success, -1 if a memory allocation failed. */intxmlHashUpdateEntry(xmlHashTablePtr hash, const xmlChar *key, void *payload, xmlHashDeallocator dealloc) { return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, dealloc, 1));}
/** * xmlHashUpdateEntry2: * @hash: hash table * @key: first string key * @key2: second string key * @payload: pointer to the payload * @dealloc: deallocator function for replaced item or NULL * * Add a hash table entry with two strings as key. * * See xmlHashUpdateEntry. * * Returns 0 on success and -1 in case of error. */intxmlHashUpdateEntry2(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, void *payload, xmlHashDeallocator dealloc) { return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, dealloc, 1));}
/** * xmlHashUpdateEntry3: * @hash: hash table * @key: first string key * @key2: second string key * @key3: third string key * @payload: pointer to the payload * @dealloc: deallocator function for replaced item or NULL * * Add a hash table entry with three strings as key. * * See xmlHashUpdateEntry. * * Returns 0 on success and -1 in case of error. */intxmlHashUpdateEntry3(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, void *payload, xmlHashDeallocator dealloc) { return(xmlHashUpdateInternal(hash, key, key2, key3, payload, dealloc, 1));}
/** * xmlHashLookup: * @hash: hash table * @key: string key * * Find the entry specified by @key. * * Returns a pointer to the payload or NULL if no entry was found. */void *xmlHashLookup(xmlHashTablePtr hash, const xmlChar *key) { return(xmlHashLookup3(hash, key, NULL, NULL));}
/** * xmlHashLookup2: * @hash: hash table * @key: first string key * @key2: second string key * * Find the payload specified by the (@key, @key2) tuple. * * Returns a pointer to the payload or NULL if no entry was found. */void *xmlHashLookup2(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2) { return(xmlHashLookup3(hash, key, key2, NULL));}
/** * xmlHashQLookup: * @hash: hash table * @prefix: prefix of the string key * @name: local name of the string key * * Find the payload specified by the QName @prefix:@name or @name. * * Returns a pointer to the payload or NULL if no entry was found. */void *xmlHashQLookup(xmlHashTablePtr hash, const xmlChar *prefix, const xmlChar *name) { return(xmlHashQLookup3(hash, prefix, name, NULL, NULL, NULL, NULL));}
/** * xmlHashQLookup2: * @hash: hash table * @prefix: first prefix * @name: first local name * @prefix2: second prefix * @name2: second local name * * Find the payload specified by the QNames tuple. * * Returns a pointer to the payload or NULL if no entry was found. */void *xmlHashQLookup2(xmlHashTablePtr hash, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2) { return(xmlHashQLookup3(hash, prefix, name, prefix2, name2, NULL, NULL));}
/** * xmlHashLookup3: * @hash: hash table * @key: first string key * @key2: second string key * @key3: third string key * * Find the payload specified by the (@key, @key2, @key3) tuple. * * Returns a pointer to the payload or NULL if no entry was found. */void *xmlHashLookup3(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3) { const xmlHashEntry *entry; unsigned hashValue; int found;
if ((hash == NULL) || (hash->size == 0) || (key == NULL)) return(NULL); hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); if (found) return(entry->payload); return(NULL);}
/** * xmlHashQLookup3: * @hash: hash table * @prefix: first prefix * @name: first local name * @prefix2: second prefix * @name2: second local name * @prefix3: third prefix * @name3: third local name * * Find the payload specified by the QNames tuple. * * Returns a pointer to the payload or NULL if no entry was found. */ATTRIBUTE_NO_SANITIZE_INTEGERvoid *xmlHashQLookup3(xmlHashTablePtr hash, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3) { const xmlHashEntry *entry; unsigned hashValue, mask, pos, displ;
if ((hash == NULL) || (hash->size == 0) || (name == NULL)) return(NULL);
hashValue = xmlHashQNameValue(hash->randomSeed, prefix, name, prefix2, name2, prefix3, name3); mask = hash->size - 1; pos = hashValue & mask; entry = &hash->table[pos];
if (entry->hashValue != 0) { displ = 0; hashValue |= MAX_HASH_SIZE;
do { if ((hashValue == entry->hashValue) && (xmlStrQEqual(prefix, name, entry->key)) && (xmlStrQEqual(prefix2, name2, entry->key2)) && (xmlStrQEqual(prefix3, name3, entry->key3))) return(entry->payload);
displ++; pos++; entry++; if ((pos & mask) == 0) entry = hash->table; } while ((entry->hashValue != 0) && (((pos - entry->hashValue) & mask) >= displ)); }
return(NULL);}
typedef struct { xmlHashScanner scan; void *data;} stubData;
static voidstubHashScannerFull(void *payload, void *data, const xmlChar *key, const xmlChar *key2 ATTRIBUTE_UNUSED, const xmlChar *key3 ATTRIBUTE_UNUSED) { stubData *sdata = (stubData *) data; sdata->scan(payload, sdata->data, key);}
/** * xmlHashScan: * @hash: hash table * @scan: scanner function for items in the hash * @data: extra data passed to @scan * * Scan the hash @table and apply @scan to each value. */voidxmlHashScan(xmlHashTablePtr hash, xmlHashScanner scan, void *data) { stubData sdata; sdata.data = data; sdata.scan = scan; xmlHashScanFull(hash, stubHashScannerFull, &sdata);}
/** * xmlHashScanFull: * @hash: hash table * @scan: scanner function for items in the hash * @data: extra data passed to @scan * * Scan the hash @table and apply @scan to each value. */voidxmlHashScanFull(xmlHashTablePtr hash, xmlHashScannerFull scan, void *data) { const xmlHashEntry *entry, *end; xmlHashEntry old; unsigned i;
if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) return;
/* * We must handle the case that a scanned entry is removed when executing * the callback (xmlCleanSpecialAttr and possibly other places). * * Find the start of a probe sequence to avoid scanning entries twice if * a deletion happens. */ entry = hash->table; end = &hash->table[hash->size]; while (entry->hashValue != 0) { if (++entry >= end) entry = hash->table; }
for (i = 0; i < hash->size; i++) { if ((entry->hashValue != 0) && (entry->payload != NULL)) { /* * Make sure to rescan after a possible deletion. */ do { old = *entry; scan(entry->payload, data, entry->key, entry->key2, entry->key3); } while ((entry->hashValue != 0) && (entry->payload != NULL) && ((entry->key != old.key) || (entry->key2 != old.key2) || (entry->key3 != old.key3))); } if (++entry >= end) entry = hash->table; }}
/** * xmlHashScan3: * @hash: hash table * @key: first string key or NULL * @key2: second string key or NULL * @key3: third string key or NULL * @scan: scanner function for items in the hash * @data: extra data passed to @scan * * Scan the hash @table and apply @scan to each value matching * (@key, @key2, @key3) tuple. If one of the keys is null, * the comparison is considered to match. */voidxmlHashScan3(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, xmlHashScanner scan, void *data) { stubData sdata; sdata.data = data; sdata.scan = scan; xmlHashScanFull3(hash, key, key2, key3, stubHashScannerFull, &sdata);}
/** * xmlHashScanFull3: * @hash: hash table * @key: first string key or NULL * @key2: second string key or NULL * @key3: third string key or NULL * @scan: scanner function for items in the hash * @data: extra data passed to @scan * * Scan the hash @table and apply @scan to each value matching * (@key, @key2, @key3) tuple. If one of the keys is null, * the comparison is considered to match. */voidxmlHashScanFull3(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, xmlHashScannerFull scan, void *data) { const xmlHashEntry *entry, *end; xmlHashEntry old; unsigned i;
if ((hash == NULL) || (hash->size == 0) || (scan == NULL)) return;
/* * We must handle the case that a scanned entry is removed when executing * the callback (xmlCleanSpecialAttr and possibly other places). * * Find the start of a probe sequence to avoid scanning entries twice if * a deletion happens. */ entry = hash->table; end = &hash->table[hash->size]; while (entry->hashValue != 0) { if (++entry >= end) entry = hash->table; }
for (i = 0; i < hash->size; i++) { if ((entry->hashValue != 0) && (entry->payload != NULL)) { /* * Make sure to rescan after a possible deletion. */ do { if (((key != NULL) && (strcmp((const char *) key, (const char *) entry->key) != 0)) || ((key2 != NULL) && (!xmlFastStrEqual(key2, entry->key2))) || ((key3 != NULL) && (!xmlFastStrEqual(key3, entry->key3)))) break; old = *entry; scan(entry->payload, data, entry->key, entry->key2, entry->key3); } while ((entry->hashValue != 0) && (entry->payload != NULL) && ((entry->key != old.key) || (entry->key2 != old.key2) || (entry->key3 != old.key3))); } if (++entry >= end) entry = hash->table; }}
/** * xmlHashCopy: * @hash: hash table * @copy: copier function for items in the hash * * Copy the hash @table using @copy to copy payloads. * * Returns the new table or NULL if a memory allocation failed. */xmlHashTablePtrxmlHashCopy(xmlHashTablePtr hash, xmlHashCopier copy) { const xmlHashEntry *entry, *end; xmlHashTablePtr ret;
if ((hash == NULL) || (copy == NULL)) return(NULL);
ret = xmlHashCreate(hash->size); if (ret == NULL) return(NULL);
if (hash->size == 0) return(ret);
end = &hash->table[hash->size];
for (entry = hash->table; entry < end; entry++) { if (entry->hashValue != 0) xmlHashAddEntry3(ret, entry->key, entry->key2, entry->key3, copy(entry->payload, entry->key)); }
return(ret);}
/** * xmlHashSize: * @hash: hash table * * Query the number of elements in the hash table. * * Returns the number of elements in the hash table or * -1 in case of error. */intxmlHashSize(xmlHashTablePtr hash) { if (hash == NULL) return(-1); return(hash->nbElems);}
/** * xmlHashRemoveEntry: * @hash: hash table * @key: string key * @dealloc: deallocator function for removed item or NULL * * Find the entry specified by the @key and remove it from the hash table. * Payload will be freed with @dealloc. * * Returns 0 on success and -1 if no entry was found. */int xmlHashRemoveEntry(xmlHashTablePtr hash, const xmlChar *key, xmlHashDeallocator dealloc) { return(xmlHashRemoveEntry3(hash, key, NULL, NULL, dealloc));}
/** * xmlHashRemoveEntry2: * @hash: hash table * @key: first string key * @key2: second string key * @dealloc: deallocator function for removed item or NULL * * Remove an entry with two strings as key. * * See xmlHashRemoveEntry. * * Returns 0 on success and -1 in case of error. */intxmlHashRemoveEntry2(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, xmlHashDeallocator dealloc) { return(xmlHashRemoveEntry3(hash, key, key2, NULL, dealloc));}
/** * xmlHashRemoveEntry3: * @hash: hash table * @key: first string key * @key2: second string key * @key3: third string key * @dealloc: deallocator function for removed item or NULL * * Remove an entry with three strings as key. * * See xmlHashRemoveEntry. * * Returns 0 on success and -1 in case of error. */ATTRIBUTE_NO_SANITIZE_INTEGERintxmlHashRemoveEntry3(xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, xmlHashDeallocator dealloc) { xmlHashEntry *entry, *cur, *next; unsigned hashValue, mask, pos, nextpos; int found;
if ((hash == NULL) || (hash->size == 0) || (key == NULL)) return(-1);
hashValue = xmlHashValue(hash->randomSeed, key, key2, key3, NULL); entry = xmlHashFindEntry(hash, key, key2, key3, hashValue, &found); if (!found) return(-1);
if ((dealloc != NULL) && (entry->payload != NULL)) dealloc(entry->payload, entry->key); if (hash->dict == NULL) { if (entry->key) xmlFree(entry->key); if (entry->key2) xmlFree(entry->key2); if (entry->key3) xmlFree(entry->key3); }
/* * Find end of probe sequence. Entries at their initial probe * position start a new sequence. */ mask = hash->size - 1; pos = entry - hash->table; cur = entry;
while (1) { nextpos = pos + 1; next = cur + 1; if ((nextpos & mask) == 0) next = hash->table;
if ((next->hashValue == 0) || (((next->hashValue - nextpos) & mask) == 0)) break;
cur = next; pos = nextpos; }
/* * Backward shift */ next = entry + 1;
if (cur < entry) { xmlHashEntry *end = &hash->table[hash->size];
memmove(entry, next, (char *) end - (char *) next); entry = hash->table; end[-1] = *entry; next = entry + 1; }
memmove(entry, next, (char *) cur - (char *) entry);
/* * Update entry */ cur->hashValue = 0;
hash->nbElems--;
return(0);}