hash.c File Reference

#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"

Include dependency graph for hash.c:

Go to the source code of this file.

Classes
struct	xmlHashEntry
struct	_xmlHashTable
struct	stubData

Macros
#define	IN_LIBXML
#define	SIZE_MAX   ((size_t) -1)
#define	MAX_FILL_NUM   7
#define	MAX_FILL_DENOM   8
#define	MIN_HASH_SIZE   8
#define	MAX_HASH_SIZE   (1u << 31)

Functions
static int	xmlHashGrow (xmlHashTablePtr hash, unsigned size)
static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned	xmlHashValue (unsigned seed, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, size_t *lengths)
static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned	xmlHashQNameValue (unsigned seed, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3)
xmlHashTablePtr	xmlHashCreate (int size)
xmlHashTablePtr	xmlHashCreateDict (int size, xmlDictPtr dict)
void	xmlHashFree (xmlHashTablePtr hash, xmlHashDeallocator dealloc)
static int	xmlFastStrEqual (const xmlChar *s1, const xmlChar *s2)
static ATTRIBUTE_NO_SANITIZE_INTEGER xmlHashEntry *	xmlHashFindEntry (const xmlHashTable *hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, unsigned hashValue, int *pfound)
static ATTRIBUTE_NO_SANITIZE_INTEGER int	xmlHashUpdateInternal (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, void *payload, xmlHashDeallocator dealloc, int update)
void	xmlHashDefaultDeallocator (void *entry, const xmlChar *key ATTRIBUTE_UNUSED)
int	xmlHashAddEntry (xmlHashTablePtr hash, const xmlChar *key, void *payload)
int	xmlHashAddEntry2 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, void *payload)
int	xmlHashAddEntry3 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, void *payload)
int	xmlHashUpdateEntry (xmlHashTablePtr hash, const xmlChar *key, void *payload, xmlHashDeallocator dealloc)
int	xmlHashUpdateEntry2 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, void *payload, xmlHashDeallocator dealloc)
int	xmlHashUpdateEntry3 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, void *payload, xmlHashDeallocator dealloc)
void *	xmlHashLookup (xmlHashTablePtr hash, const xmlChar *key)
void *	xmlHashLookup2 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2)
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)
2: second local name
@prefix3: third prefix
void *	xmlHashQLookup2 (xmlHashTablePtr hash, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2)
void *	xmlHashLookup3 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3)
3: 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_INTEGER void *	xmlHashQLookup3 (xmlHashTablePtr hash, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3)
static void	stubHashScannerFull (void *payload, void *data, const xmlChar *key, const xmlChar *key2 ATTRIBUTE_UNUSED, const xmlChar *key3 ATTRIBUTE_UNUSED)
void	xmlHashScan (xmlHashTablePtr hash, xmlHashScanner scan, void *data)
void	xmlHashScanFull (xmlHashTablePtr hash, xmlHashScannerFull scan, void *data)
void	xmlHashScan3 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, xmlHashScanner scan, void *data)
void	xmlHashScanFull3 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, xmlHashScannerFull scan, void *data)
xmlHashTablePtr	xmlHashCopy (xmlHashTablePtr hash, xmlHashCopier copy)
int	xmlHashSize (xmlHashTablePtr hash)
int	xmlHashRemoveEntry (xmlHashTablePtr hash, const xmlChar *key, xmlHashDeallocator dealloc)
int	xmlHashRemoveEntry2 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, xmlHashDeallocator dealloc)
ATTRIBUTE_NO_SANITIZE_INTEGER int	xmlHashRemoveEntry3 (xmlHashTablePtr hash, const xmlChar *key, const xmlChar *key2, const xmlChar *key3, xmlHashDeallocator dealloc)

Macro Definition Documentation

IN_LIBXML

#define IN_LIBXML

Definition at line 10 of file hash.c.

MAX_FILL_DENOM

#define MAX_FILL_DENOM   8

Definition at line 29 of file hash.c.

MAX_FILL_NUM

#define MAX_FILL_NUM   7

Definition at line 28 of file hash.c.

MAX_HASH_SIZE

#define MAX_HASH_SIZE   (1u << 31)

Definition at line 31 of file hash.c.

MIN_HASH_SIZE

#define MIN_HASH_SIZE   8

Definition at line 30 of file hash.c.

SIZE_MAX

#define SIZE_MAX   ((size_t) -1)

Definition at line 25 of file hash.c.

Function Documentation

stubHashScannerFull()

static void stubHashScannerFull ( void *  payload, void *  data, const xmlChar *  key, const xmlChar *key2  ATTRIBUTE_UNUSED, const xmlChar *key3  ATTRIBUTE_UNUSED  )

static

Definition at line 882 of file hash.c.

                                                          {
    stubData *sdata = (stubData *) data;
    sdata->scan(payload, sdata->data, key);
}

Referenced by xmlHashScan(), and xmlHashScan3().

xmlFastStrEqual()

static int xmlFastStrEqual ( const xmlChar *  s1, const xmlChar *  s2  )

static

xmlFastStrEqual: @s1: string @s2: string

Compare two strings for equality, allowing NULL values.

Definition at line 269 of file hash.c.

                                                      {
    if (s1 == NULL)
        return(s2 == NULL);
    else
        return((s2 != NULL) &&
               (strcmp((const char *) s1, (const char *) s2) == 0));
}

Referenced by xmlHashFindEntry(), and xmlHashScanFull3().

xmlHashAddEntry()

int xmlHashAddEntry	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		void *	payload
	)

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.

Definition at line 621 of file hash.c.

                                                                         {
    return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload, NULL, 0));
}

Referenced by cache_add_entry(), xmlAddID(), xmlAddNotationDecl(), xmlAddRef(), xsltGetExtData(), xsltInitCtxtExt(), xsltInitCtxtKey(), xsltNamespaceAlias(), xsltRegisterExtModuleFull(), and xsltStyleInitializeStylesheetModule().

xmlHashAddEntry2()

int xmlHashAddEntry2	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		void *	payload
	)

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.

Definition at line 639 of file hash.c.

                                                     {
    return(xmlHashUpdateInternal(hash, key, key2, NULL, payload, NULL, 0));
}

Referenced by xmlAddElementDecl(), xmlAddSpecialAttr(), xmlGetDtdElementDesc2(), xsltAddTemplate(), xsltDocumentElem(), xsltEvalGlobalVariables(), xsltParseStylesheetAttributeSet(), xsltParseStylesheetOutput(), xsltParseStylesheetPreserveSpace(), xsltParseStylesheetStripSpace(), xsltProcessUserParamInternal(), xsltRegisterExtElement(), xsltRegisterExtFunction(), and xsltResolveSASCallback().

xmlHashAddEntry3()

int xmlHashAddEntry3	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		const xmlChar *	key3,
		void *	payload
	)

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.

Definition at line 659 of file hash.c.

                                {
    return(xmlHashUpdateInternal(hash, key, key2, key3, payload, NULL, 0));
}

Referenced by xmlAddAttributeDecl(), xmlHashCopy(), and xsltAddTemplate().

xmlHashCopy()

xmlHashTablePtr xmlHashCopy	(	xmlHashTablePtr	hash,
		xmlHashCopier	copy
	)

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.

Definition at line 1050 of file hash.c.

                                                      {
    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);
}

xmlHashCreate()

xmlHashTablePtr xmlHashCreate

(

int

size

)

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.

Definition at line 160 of file hash.c.

                        {
    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);
}

Referenced by SchemaCache_create(), xmlHashCopy(), xmlHashCreateDict(), xsltAddTemplate(), xsltApplyStylesheetInternal(), xsltDocumentElem(), xsltGatherNamespaces(), xsltGetExtData(), xsltInitCtxtExt(), xsltNamespaceAlias(), xsltNewKeyTable(), xsltParseStylesheetAttributeSet(), xsltParseStylesheetOutput(), xsltParseStylesheetPreserveSpace(), xsltParseStylesheetStripSpace(), xsltProcessUserParamInternal(), xsltRegisterExtElement(), xsltRegisterExtFunction(), xsltRegisterExtModuleElement(), xsltRegisterExtModuleFull(), xsltRegisterExtModuleFunction(), xsltRegisterExtModuleTopLevel(), xsltResolveStylesheetAttributeSet(), and xsltStyleInitializeStylesheetModule().

xmlHashCreateDict()

xmlHashTablePtr xmlHashCreateDict	(	int	size,
		xmlDictPtr	dict
	)

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.

Definition at line 209 of file hash.c.

                                             {
    xmlHashTablePtr hash;
 
    hash = xmlHashCreate(size);
    if (hash != NULL) {
        hash->dict = dict;
        xmlDictReference(dict);
    }
    return(hash);
}

Referenced by xmlAddAttributeDecl(), xmlAddDefAttrs(), xmlAddElementDecl(), xmlAddID(), xmlAddNotationDecl(), xmlAddRef(), xmlAddSpecialAttr(), and xmlGetDtdElementDesc2().

xmlHashDefaultDeallocator()

void xmlHashDefaultDeallocator	(	void *	entry,
		const xmlChar *key	ATTRIBUTE_UNUSED
	)

xmlHashDefaultDeallocator: @entry: hash table entry @key: the entry's string key

Free a hash table entry with xmlFree.

Definition at line 603 of file hash.c.

                                                                            {
    xmlFree(entry);
}

Referenced by xmlCtxtReset(), and xmlFreeParserCtxt().

xmlHashFindEntry()

static ATTRIBUTE_NO_SANITIZE_INTEGER xmlHashEntry * xmlHashFindEntry ( const xmlHashTable *  hash, const xmlChar *  key, const xmlChar *  key2, const xmlChar *  key3, unsigned  hashValue, int *  pfound  )

static

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.

Definition at line 292 of file hash.c.

                                                  {
    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);
}

Referenced by xmlHashLookup3(), xmlHashRemoveEntry3(), and xmlHashUpdateInternal().

xmlHashFree()

void xmlHashFree	(	xmlHashTablePtr	hash,
		xmlHashDeallocator	dealloc
	)

xmlHashFree: @hash: hash table @dealloc: deallocator function or NULL

Free the hash and its contents. The payload is deallocated with @dealloc if provided.

Definition at line 229 of file hash.c.

                                                              {
    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);
}

Referenced by schema_cache_Release(), xmlCleanSpecialAttr(), xmlCtxtReset(), xmlFreeAttributeTable(), xmlFreeElementTable(), xmlFreeIDTable(), xmlFreeNotationTable(), xmlFreeParserCtxt(), xmlFreeRefTable(), xsltCleanupGlobals(), xsltFreeAttributeSetsHashes(), xsltFreeCtxtExts(), xsltFreeGlobalVariables(), xsltFreeKeyTable(), xsltFreeNamespaceAliasHashes(), xsltFreeStylesheet(), xsltFreeTemplateHashes(), xsltResolveStylesheetAttributeSet(), xsltShutdownCtxtExts(), xsltShutdownExts(), xsltUnregisterAllExtModuleElement(), xsltUnregisterAllExtModuleFunction(), xsltUnregisterAllExtModules(), and xsltUnregisterAllExtModuleTopLevel().

xmlHashGrow()

static int xmlHashGrow ( xmlHashTablePtr  hash, unsigned  size  )

static

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.

Definition at line 354 of file hash.c.

                                                 {
    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);
}

Referenced by xmlHashCreate(), and xmlHashUpdateInternal().

xmlHashLookup()

void * xmlHashLookup	(	xmlHashTablePtr	hash,
		const xmlChar *	key
	)

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.

Definition at line 739 of file hash.c.

                                                        {
    return(xmlHashLookup3(hash, key, NULL, NULL));
}

Referenced by cache_copy(), get_entry(), lookup_schema_elemDecl(), schema_cache_get(), xmlAddRef(), xmlGetDtdNotationDesc(), xmlGetID(), xmlGetRefs(), xmlRemoveID(), xmlRemoveRef(), xsltApplySequenceConstructor(), xsltCheckInstructionElement(), xsltCheckParentElement(), xsltCopyNamespaceList(), xsltGatherNamespaces(), xsltGetExtData(), xsltGetExtInfo(), xsltGetKey(), xsltGetNamespace(), xsltInitCtxtExt(), xsltInitCtxtKey(), xsltRegisterExtModuleFull(), xsltRegisterExtPrefix(), xsltStyleGetExtData(), and xsltStyleInitializeStylesheetModule().

xmlHashLookup2()

void * xmlHashLookup2	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2
	)

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.

Definition at line 754 of file hash.c.

                                   {
    return(xmlHashLookup3(hash, key, key2, NULL));
}

Referenced by xmlAddDefAttrs(), xmlAddElementDecl(), xmlAddSpecialAttr(), xmlGetDtdElementDesc(), xmlGetDtdElementDesc2(), xmlGetDtdQElementDesc(), xmlParseStartTag2(), xsltAddTemplate(), xsltApplyAttributeSet(), xsltCopyText(), xsltCopyTextString(), xsltEvalGlobalVariables(), xsltExtElementLookup(), xsltExtModuleElementLookup(), xsltExtModuleElementPreComputeLookup(), xsltExtModuleFunctionLookup(), xsltExtModuleTopLevelLookup(), xsltFindElemSpaceHandling(), xsltFindTemplate(), xsltGlobalVariableLookup(), xsltParseStylesheetAttributeSet(), xsltPreComputeExtModuleElement(), xsltProcessUserParamInternal(), xsltResolveAttrSet(), xsltResolveUseAttrSets(), and xsltXPathFunctionLookup().

xmlHashLookup3()

void * xmlHashLookup3	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		const xmlChar *	key3
	)

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.

Definition at line 806 of file hash.c.

                                                         {
    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);
}

Referenced by xmlAddAttributeDecl(), xmlGetDtdAttrDesc(), xmlGetDtdQAttrDesc(), xmlHashLookup(), xmlHashLookup2(), xsltAddTemplate(), and xsltGetTemplate().

xmlHashQLookup()

void * xmlHashQLookup	(	xmlHashTablePtr	hash,
		const xmlChar *	prefix,
		const xmlChar *	name
	)

Definition at line 770 of file hash.c.

                                    {
    return(xmlHashQLookup3(hash, prefix, name, NULL, NULL, NULL, NULL));
}

xmlHashQLookup2()

void * xmlHashQLookup2	(	xmlHashTablePtr	hash,
		const xmlChar *	prefix,
		const xmlChar *	name,
		const xmlChar *	prefix2,
		const xmlChar *	name2
	)

Definition at line 788 of file hash.c.

                                      {
    return(xmlHashQLookup3(hash, prefix, name, prefix2, name2, NULL, NULL));
}

Referenced by xmlParseAttribute2().

xmlHashQLookup3()

ATTRIBUTE_NO_SANITIZE_INTEGER void * xmlHashQLookup3	(	xmlHashTablePtr	hash,
		const xmlChar *	prefix,
		const xmlChar *	name,
		const xmlChar *	prefix2,
		const xmlChar *	name2,
		const xmlChar *	prefix3,
		const xmlChar *	name3
	)

Definition at line 837 of file hash.c.

                                                              {
    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);
}

Referenced by xmlHashQLookup(), and xmlHashQLookup2().

xmlHashQNameValue()

static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned xmlHashQNameValue ( unsigned  seed, const xmlChar *  prefix, const xmlChar *  name, const xmlChar *  prefix2, const xmlChar *  name2, const xmlChar *  prefix3, const xmlChar *  name3  )

static

Definition at line 101 of file hash.c.

                                                                {
    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);
}

Referenced by xmlHashQLookup3().

xmlHashRemoveEntry()

int xmlHashRemoveEntry	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		xmlHashDeallocator	dealloc
	)

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.

Definition at line 1102 of file hash.c.

                                                   {
    return(xmlHashRemoveEntry3(hash, key, NULL, NULL, dealloc));
}

Referenced by cache_add_entry(), cache_remove_entry(), xmlRemoveID(), and xsltUnregisterExtModule().

xmlHashRemoveEntry2()

int xmlHashRemoveEntry2	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		xmlHashDeallocator	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.

Definition at line 1121 of file hash.c.

                                                                     {
    return(xmlHashRemoveEntry3(hash, key, key2, NULL, dealloc));
}

Referenced by xmlAddElementDecl(), xmlCleanSpecialAttrCallback(), xsltResolveAttrSet(), xsltUnregisterExtModuleElement(), xsltUnregisterExtModuleFunction(), and xsltUnregisterExtModuleTopLevel().

xmlHashRemoveEntry3()

ATTRIBUTE_NO_SANITIZE_INTEGER int xmlHashRemoveEntry3	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		const xmlChar *	key3,
		xmlHashDeallocator	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.

Definition at line 1142 of file hash.c.

                                                {
    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);
}

Referenced by xmlHashRemoveEntry(), and xmlHashRemoveEntry2().

xmlHashScan()

void xmlHashScan	(	xmlHashTablePtr	hash,
		xmlHashScanner	scan,
		void *	data
	)

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.

Definition at line 898 of file hash.c.

                                                                   {
    stubData sdata;
    sdata.data = data;
    sdata.scan = scan;
    xmlHashScanFull(hash, stubHashScannerFull, &sdata);
}

Referenced by schema_cache_addCollection(), xsltCleanupGlobals(), xsltEvalGlobalVariables(), xsltFixImportedCompSteps(), xsltInitCtxtExts(), xsltShutdownCtxtExts(), and xsltShutdownExts().

xmlHashScan3()

void xmlHashScan3	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		const xmlChar *	key3,
		xmlHashScanner	scan,
		void *	data
	)

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.

Definition at line 969 of file hash.c.

                                              {
    stubData sdata;
    sdata.data = data;
    sdata.scan = scan;
    xmlHashScanFull3(hash, key, key2, key3, stubHashScannerFull, &sdata);
}

xmlHashScanFull()

void xmlHashScanFull	(	xmlHashTablePtr	hash,
		xmlHashScannerFull	scan,
		void *	data
	)

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.

Definition at line 914 of file hash.c.

                                                                           {
    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;
    }
}

Referenced by xmlCleanSpecialAttr(), xmlHashScan(), xsltDebugDumpExtensions(), and xsltResolveStylesheetAttributeSet().

xmlHashScanFull3()

void xmlHashScanFull3	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		const xmlChar *	key3,
		xmlHashScannerFull	scan,
		void *	data
	)

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.

Definition at line 992 of file hash.c.

                                                      {
    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;
    }
}

Referenced by xmlHashScan3().

xmlHashSize()

int xmlHashSize

(

xmlHashTablePtr

hash

)

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.

Definition at line 1085 of file hash.c.

                                  {
    if (hash == NULL)
        return(-1);
    return(hash->nbElems);
}

Referenced by lookup_schema_elemDecl(), and xmlCleanSpecialAttr().

xmlHashUpdateEntry()

int xmlHashUpdateEntry	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		void *	payload,
		xmlHashDeallocator	dealloc
	)

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.

Definition at line 678 of file hash.c.

                                                              {
    return(xmlHashUpdateInternal(hash, key, NULL, NULL, payload,
                                 dealloc, 1));
}

Referenced by xmlRemoveRef(), and xsltGatherNamespaces().

xmlHashUpdateEntry2()

int xmlHashUpdateEntry2	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		void *	payload,
		xmlHashDeallocator	dealloc
	)

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.

Definition at line 699 of file hash.c.

                                               {
    return(xmlHashUpdateInternal(hash, key, key2, NULL, payload,
                                 dealloc, 1));
}

Referenced by xmlAddDefAttrs(), xsltRegisterExtModuleElement(), xsltRegisterExtModuleFunction(), and xsltRegisterExtModuleTopLevel().

xmlHashUpdateEntry3()

int xmlHashUpdateEntry3	(	xmlHashTablePtr	hash,
		const xmlChar *	key,
		const xmlChar *	key2,
		const xmlChar *	key3,
		void *	payload,
		xmlHashDeallocator	dealloc
	)

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.

Definition at line 722 of file hash.c.

                                                              {
    return(xmlHashUpdateInternal(hash, key, key2, key3, payload,
                                 dealloc, 1));
}

Referenced by xsltAddTemplate().

xmlHashUpdateInternal()

static ATTRIBUTE_NO_SANITIZE_INTEGER int xmlHashUpdateInternal ( xmlHashTablePtr  hash, const xmlChar *  key, const xmlChar *  key2, const xmlChar *  key3, void *  payload, xmlHashDeallocator  dealloc, int  update  )

static

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.

Definition at line 425 of file hash.c.

                                                                             {
    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);
}

Referenced by xmlHashAddEntry(), xmlHashAddEntry2(), xmlHashAddEntry3(), xmlHashUpdateEntry(), xmlHashUpdateEntry2(), and xmlHashUpdateEntry3().

xmlHashValue()

static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned xmlHashValue ( unsigned  seed, const xmlChar *  key, const xmlChar *  key2, const xmlChar *  key3, size_t *  lengths  )

static

Definition at line 61 of file hash.c.

                                                   {
    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);
}

Referenced by xmlHashLookup3(), xmlHashRemoveEntry3(), and xmlHashUpdateInternal().