dict.c File Reference

#include "libxml.h"
#include <limits.h>
#include <string.h>
#include <time.h>
#include "private/dict.h"
#include "private/threads.h"
#include <libxml/parser.h>
#include <libxml/dict.h>
#include <libxml/xmlmemory.h>
#include <libxml/xmlstring.h>

Include dependency graph for dict.c:

Go to the source code of this file.

Classes
struct	_xmlDictStrings
struct	_xmlDict

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)
#define	HASH_ROL31(x, n)   ((x) << (n) | ((x) & 0x7FFFFFFF) >> (31 - (n)))

Typedefs
typedef struct _xmlDictStrings	xmlDictStrings
typedef xmlDictStrings *	xmlDictStringsPtr
typedef xmlHashedString	xmlDictEntry

Functions
int	xmlInitializeDict (void)
void	xmlInitDictInternal (void)
void	xmlDictCleanup (void)
void	xmlCleanupDictInternal (void)
static const xmlChar *	xmlDictAddString (xmlDictPtr dict, const xmlChar *name, unsigned int namelen)
static const xmlChar *	xmlDictAddQString (xmlDictPtr dict, const xmlChar *prefix, unsigned int plen, const xmlChar *name, unsigned int namelen)
xmlDictPtr	xmlDictCreate (void)
xmlDictPtr	xmlDictCreateSub (xmlDictPtr sub)
int	xmlDictReference (xmlDictPtr dict)
void	xmlDictFree (xmlDictPtr dict)
int	xmlDictOwns (xmlDictPtr dict, const xmlChar *str)
int	xmlDictSize (xmlDictPtr dict)
size_t	xmlDictSetLimit (xmlDictPtr dict, size_t limit)
size_t	xmlDictGetUsage (xmlDictPtr dict)
static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned	xmlDictHashName (unsigned seed, const xmlChar *data, size_t maxLen, size_t *plen)
static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned	xmlDictHashQName (unsigned seed, const xmlChar *prefix, const xmlChar *name, size_t *pplen, size_t *plen)
unsigned	xmlDictComputeHash (const xmlDict *dict, const xmlChar *string)
ATTRIBUTE_NO_SANITIZE_INTEGER unsigned	xmlDictCombineHash (unsigned v1, unsigned v2)
: string
xmlDictLookupInternal: @dict: dict @prefix: optional QName prefix @maybeLen: length of string or -1 if unknown @update: whether the string should be added Internal lookup and update function.
static ATTRIBUTE_NO_SANITIZE_INTEGER xmlDictEntry *	xmlDictFindEntry (const xmlDict *dict, const xmlChar *prefix, const xmlChar *name, int len, unsigned hashValue, int *pfound)
static int	xmlDictGrow (xmlDictPtr dict, unsigned size)
static ATTRIBUTE_NO_SANITIZE_INTEGER const xmlDictEntry *	xmlDictLookupInternal (xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name, int maybeLen, int update)
: string key
xmlDictLookupHashed: @dict: dictionary @len: length of the key, if -1 it is recomputed Lookup a dictionary entry and add the string to the dictionary if it wasn't found. Returns the dictionary entry.
const xmlChar *	xmlDictLookup (xmlDictPtr dict, const xmlChar *name, int len)
xmlHashedString	xmlDictLookupHashed (xmlDictPtr dict, const xmlChar *name, int len)
: the name of the userdata
xmlDictExists: @dict: the dictionary @len: the length of the name, if -1 it is recomputed Check if a string exists in the dictionary. Returns the internal copy of the name or NULL if not found.
const xmlChar *	xmlDictExists (xmlDictPtr dict, const xmlChar *name, int len)

Variables
static xmlMutex	xmlDictMutex

and add it to the dictionary if
it wasn't found. Returns the interned copy of the string or NULL if a memory allocation failed.
static xmlMutex	xmlRngMutex
static unsigned	globalRngState [2]
const xmlChar *	xmlDictQLookup (xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name)
ATTRIBUTE_NO_SANITIZE_INTEGER void	xmlInitRandom (void)
void	xmlCleanupRandom (void)
static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned	xoroshiro64ss (unsigned *s)
unsigned	xmlRandom (void)

Macro Definition Documentation

HASH_ROL31

#define HASH_ROL31	(		x,
			n
	)		((x) << (n) | ((x) & 0x7FFFFFFF) >> (31 - (n)))

Definition at line 517 of file dict.c.

IN_LIBXML

#define IN_LIBXML

Definition at line 19 of file dict.c.

MAX_FILL_DENOM

#define MAX_FILL_DENOM   8

Definition at line 39 of file dict.c.

MAX_FILL_NUM

#define MAX_FILL_NUM   7

Definition at line 38 of file dict.c.

MAX_HASH_SIZE

#define MAX_HASH_SIZE   (1u << 31)

Definition at line 41 of file dict.c.

MIN_HASH_SIZE

#define MIN_HASH_SIZE   8

Definition at line 40 of file dict.c.

SIZE_MAX

#define SIZE_MAX   ((size_t) -1)

Definition at line 35 of file dict.c.

Typedef Documentation

xmlDictEntry

typedef xmlHashedString xmlDictEntry

Definition at line 54 of file dict.c.

xmlDictStrings

typedef struct _xmlDictStrings xmlDictStrings

Definition at line 43 of file dict.c.

xmlDictStringsPtr

typedef xmlDictStrings* xmlDictStringsPtr

Definition at line 44 of file dict.c.

Function Documentation

xmlCleanupDictInternal()

void xmlCleanupDictInternal

(

void

)

xmlCleanupDictInternal:

Free the dictionary mutex.

Definition at line 121 of file dict.c.

                             {
    xmlCleanupMutex(&xmlDictMutex);
}

Referenced by xmlCleanupParser().

xmlCleanupRandom()

void xmlCleanupRandom

(

void

)

Definition at line 932 of file dict.c.

                       {
    xmlCleanupMutex(&xmlRngMutex);
}

Referenced by xmlCleanupParser().

xmlDictAddQString()

static const xmlChar * xmlDictAddQString ( xmlDictPtr  dict, const xmlChar *  prefix, unsigned int  plen, const xmlChar *  name, unsigned int  namelen  )

static

Definition at line 204 of file dict.c.

{
    xmlDictStringsPtr pool;
    const xmlChar *ret;
    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
    size_t limit = 0;
 
    pool = dict->strings;
    while (pool != NULL) {
    if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
        goto found_pool;
    if (pool->size > size) size = pool->size;
        limit += pool->size;
    pool = pool->next;
    }
    /*
     * Not found, need to allocate
     */
    if (pool == NULL) {
        if ((dict->limit > 0) && (limit > dict->limit)) {
            return(NULL);
        }
 
        if (size == 0) size = 1000;
    else size *= 4; /* exponential growth */
        if (size < 4 * (namelen + plen + 1))
        size = 4 * (namelen + plen + 1); /* just in case ! */
    pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
    if (pool == NULL)
        return(NULL);
    pool->size = size;
    pool->nbStrings = 0;
    pool->free = &pool->array[0];
    pool->end = &pool->array[size];
    pool->next = dict->strings;
    dict->strings = pool;
    }
found_pool:
    ret = pool->free;
    memcpy(pool->free, prefix, plen);
    pool->free += plen;
    *(pool->free++) = ':';
    memcpy(pool->free, name, namelen);
    pool->free += namelen;
    *(pool->free++) = 0;
    pool->nbStrings++;
    return(ret);
}

Referenced by xmlDictLookupInternal().

xmlDictAddString()

static const xmlChar * xmlDictAddString ( xmlDictPtr  dict, const xmlChar *  name, unsigned int  namelen  )

static

Definition at line 136 of file dict.c.

                                                                             {
    xmlDictStringsPtr pool;
    const xmlChar *ret;
    size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
    size_t limit = 0;
 
    pool = dict->strings;
    while (pool != NULL) {
    if ((size_t)(pool->end - pool->free) > namelen)
        goto found_pool;
    if (pool->size > size) size = pool->size;
        limit += pool->size;
    pool = pool->next;
    }
    /*
     * Not found, need to allocate
     */
    if (pool == NULL) {
        if ((dict->limit > 0) && (limit > dict->limit)) {
            return(NULL);
        }
 
        if (size == 0) {
            size = 1000;
        } else {
            if (size < (SIZE_MAX - sizeof(xmlDictStrings)) / 4)
                size *= 4; /* exponential growth */
            else
                size = SIZE_MAX - sizeof(xmlDictStrings);
        }
        if (size / 4 < namelen) {
            if ((size_t) namelen + 0 < (SIZE_MAX - sizeof(xmlDictStrings)) / 4)
                size = 4 * (size_t) namelen; /* just in case ! */
            else
                return(NULL);
        }
    pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
    if (pool == NULL)
        return(NULL);
    pool->size = size;
    pool->nbStrings = 0;
    pool->free = &pool->array[0];
    pool->end = &pool->array[size];
    pool->next = dict->strings;
    dict->strings = pool;
    }
found_pool:
    ret = pool->free;
    memcpy(pool->free, name, namelen);
    pool->free += namelen;
    *(pool->free++) = 0;
    pool->nbStrings++;
    return(ret);
}

Referenced by xmlDictLookupInternal().

xmlDictCleanup()

void xmlDictCleanup

(

void

)

xmlDictCleanup:

DEPRECATED: This function is a no-op. Call xmlCleanupParser to free global state but see the warnings there. xmlCleanupParser should be only called once at program exit. In most cases, you don't have call cleanup functions at all.

Definition at line 112 of file dict.c.

                     {
}

xmlDictCombineHash()

ATTRIBUTE_NO_SANITIZE_INTEGER unsigned xmlDictCombineHash	(	unsigned	v1,
		unsigned	v2
	)

Definition at line 521 of file dict.c.

                                             {
    /*
     * The upper bit of hash values is always set, so we have to operate on
     * 31-bit hashes here.
     */
    v1 ^= v2;
    v1 += HASH_ROL31(v2, 5);
 
    return((v1 & 0xFFFFFFFF) | 0x80000000);
}

Referenced by xmlParseStartTag2().

xmlDictComputeHash()

unsigned xmlDictComputeHash	(	const xmlDict *	dict,
		const xmlChar *	string
	)

Definition at line 512 of file dict.c.

                                                               {
    size_t len;
    return(xmlDictHashName(dict->seed, string, SIZE_MAX, &len));
}

Referenced by xmlParserNsLookupSax(), and xmlParserNsUpdateSax().

xmlDictCreate()

xmlDictPtr xmlDictCreate

(

void

)

xmlDictCreate:

Create a new dictionary

Returns the newly created dictionary, or NULL if an error occurred.

Definition at line 262 of file dict.c.

                    {
    xmlDictPtr dict;
 
    xmlInitParser();
 
    dict = xmlMalloc(sizeof(xmlDict));
    if (dict == NULL)
        return(NULL);
    dict->ref_counter = 1;
    dict->limit = 0;
 
    dict->size = 0;
    dict->nbElems = 0;
    dict->table = NULL;
    dict->strings = NULL;
    dict->subdict = NULL;
    dict->seed = xmlRandom();
#ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
    dict->seed = 0;
#endif
    return(dict);
}

Referenced by xmlDictCreateSub(), xmlInitSAXParserCtxt(), and xsltNewStylesheetInternal().

xmlDictCreateSub()

xmlDictPtr xmlDictCreateSub

(

xmlDictPtr

sub

)

xmlDictCreateSub: @sub: an existing dictionary

Create a new dictionary, inheriting strings from the read-only dictionary @sub. On lookup, strings are first searched in the new dictionary, then in @sub, and if not found are created in the new dictionary.

Returns the newly created dictionary, or NULL if an error occurred.

Definition at line 297 of file dict.c.

                                 {
    xmlDictPtr dict = xmlDictCreate();
 
    if ((dict != NULL) && (sub != NULL)) {
        dict->seed = sub->seed;
        dict->subdict = sub;
    xmlDictReference(dict->subdict);
    }
    return(dict);
}

Referenced by xsltNewTransformContext().

xmlDictExists()

const xmlChar * xmlDictExists	(	xmlDictPtr	dict,
		const xmlChar *	name,
		int	len
	)

Definition at line 872 of file dict.c.

                                                             {
    const xmlDictEntry *entry;
 
    entry = xmlDictLookupInternal(dict, NULL, name, len, 0);
    if (entry == NULL)
        return(NULL);
    return(entry->name);
}

xmlDictFindEntry()

static ATTRIBUTE_NO_SANITIZE_INTEGER xmlDictEntry * xmlDictFindEntry ( const xmlDict *  dict, const xmlChar *  prefix, const xmlChar *  name, int  len, unsigned  hashValue, int *  pfound  )

static

Definition at line 547 of file dict.c.

                              {
    xmlDictEntry *entry;
    unsigned mask, pos, displ;
    int found = 0;
 
    mask = dict->size - 1;
    pos = hashValue & mask;
    entry = &dict->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;
 
        do {
            if (entry->hashValue == hashValue) {
                if (prefix == NULL) {
                    /*
                     * name is not necessarily null-terminated.
                     */
                    if ((strncmp((const char *) entry->name,
                                 (const char *) name, len) == 0) &&
                        (entry->name[len] == 0)) {
                        found = 1;
                        break;
                    }
                } else {
                    if (xmlStrQEqual(prefix, name, entry->name)) {
                        found = 1;
                        break;
                    }
                }
            }
 
            displ++;
            pos++;
            entry++;
            if ((pos & mask) == 0)
                entry = dict->table;
        } while ((entry->hashValue != 0) &&
                 (((pos - entry->hashValue) & mask) >= displ));
    }
 
    *pfound = found;
    return(entry);
}

Referenced by xmlDictLookupInternal().

xmlDictFree()

void xmlDictFree

(

xmlDictPtr

dict

)

xmlDictFree: @dict: the dictionary

Free the hash @dict and its contents. The userdata is deallocated with @f if provided.

Definition at line 333 of file dict.c.

                             {
    xmlDictStringsPtr pool, nextp;
 
    if (dict == NULL)
    return;
 
    /* decrement the counter, it may be shared by a parser and docs */
    xmlMutexLock(&xmlDictMutex);
    dict->ref_counter--;
    if (dict->ref_counter > 0) {
        xmlMutexUnlock(&xmlDictMutex);
        return;
    }
 
    xmlMutexUnlock(&xmlDictMutex);
 
    if (dict->subdict != NULL) {
        xmlDictFree(dict->subdict);
    }
 
    if (dict->table) {
    xmlFree(dict->table);
    }
    pool = dict->strings;
    while (pool != NULL) {
        nextp = pool->next;
    xmlFree(pool);
    pool = nextp;
    }
    xmlFree(dict);
}

Referenced by xmlDictFree(), xmlFreeParserCtxt(), xmlHashFree(), xmlParseBalancedChunkMemoryInternal(), xmlParseExternalEntityPrivate(), xmlParseInNodeContext(), xslt_doc_default_loader(), xsltDocDefaultLoaderFunc(), xsltFreeStylesheet(), xsltFreeTransformContext(), and xsltParseStylesheetUser().

xmlDictGetUsage()

size_t xmlDictGetUsage

(

xmlDictPtr

dict

)

xmlDictGetUsage: @dict: the dictionary

Get how much memory is used by a dictionary for strings Added in 2.9.0

Returns the amount of strings allocated

Definition at line 441 of file dict.c.

                                 {
    xmlDictStringsPtr pool;
    size_t limit = 0;
 
    if (dict == NULL)
    return(0);
    pool = dict->strings;
    while (pool != NULL) {
        limit += pool->size;
    pool = pool->next;
    }
    return(limit);
}

xmlDictGrow()

static int xmlDictGrow ( xmlDictPtr  dict, unsigned  size  )

static

xmlDictGrow: @dict: dictionary @size: new size of the dictionary

Resize the dictionary hash table.

Returns 0 in case of success, -1 if a memory allocation failed.

Definition at line 609 of file dict.c.

                                            {
    const xmlDictEntry *oldentry, *oldend, *end;
    xmlDictEntry *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 = dict->size;
    if (oldsize == 0)
        goto done;
 
    oldend = &dict->table[oldsize];
    end = &table[size];
 
    /*
     * Robin Hood sorting order is maintained if we
     *
     * - compute dict indices with modulo
     * - resize by an integer factor
     * - start to copy from the beginning of a probe sequence
     */
    oldentry = dict->table;
    while (oldentry->hashValue != 0) {
        if (++oldentry >= oldend)
            oldentry = dict->table;
    }
 
    for (i = 0; i < oldsize; i++) {
        if (oldentry->hashValue != 0) {
            xmlDictEntry *entry = &table[oldentry->hashValue & (size - 1)];
 
            while (entry->hashValue != 0) {
                if (++entry >= end)
                    entry = table;
            }
            *entry = *oldentry;
        }
 
        if (++oldentry >= oldend)
            oldentry = dict->table;
    }
 
    xmlFree(dict->table);
 
done:
    dict->table = table;
    dict->size = size;
 
    return(0);
}

Referenced by xmlDictLookupInternal().

xmlDictHashName()

static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned xmlDictHashName ( unsigned  seed, const xmlChar *  data, size_t  maxLen, size_t *  plen  )

static

Definition at line 464 of file dict.c.

                              {
    unsigned h1, h2;
    size_t i;
 
    HASH_INIT(h1, h2, seed);
 
    for (i = 0; i < maxLen && data[i]; i++) {
        HASH_UPDATE(h1, h2, data[i]);
    }
 
    HASH_FINISH(h1, h2);
 
    *plen = i;
    return(h2 | MAX_HASH_SIZE);
}

Referenced by xmlDictComputeHash(), and xmlDictLookupInternal().

xmlDictHashQName()

static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned xmlDictHashQName ( unsigned  seed, const xmlChar *  prefix, const xmlChar *  name, size_t *  pplen, size_t *  plen  )

static

Definition at line 483 of file dict.c.

                                              {
    unsigned h1, h2;
    size_t i;
 
    HASH_INIT(h1, h2, seed);
 
    for (i = 0; prefix[i] != 0; i++) {
        HASH_UPDATE(h1, h2, prefix[i]);
    }
    *pplen = i;
 
    HASH_UPDATE(h1, h2, ':');
 
    for (i = 0; name[i] != 0; i++) {
        HASH_UPDATE(h1, h2, name[i]);
    }
    *plen = i;
 
    HASH_FINISH(h1, h2);
 
    /*
     * Always set the upper bit of hash values since 0 means an unoccupied
     * bucket.
     */
    return(h2 | MAX_HASH_SIZE);
}

Referenced by xmlDictLookupInternal().

xmlDictLookup()

const xmlChar * xmlDictLookup	(	xmlDictPtr	dict,
		const xmlChar *	name,
		int	len
	)

Definition at line 824 of file dict.c.

                                                             {
    const xmlDictEntry *entry;
 
    entry = xmlDictLookupInternal(dict, NULL, name, len, 1);
    if (entry == NULL)
        return(NULL);
    return(entry->name);
}

Referenced by xmlAddAttributeDecl(), xmlAddID(), xmlCopyDocElementContent(), xmlDetectSAX2(), xmlHashUpdateInternal(), xmlNewDocElementContent(), xmlParseBalancedChunkMemoryInternal(), xmlParseExternalEntityPrivate(), xmlParseName(), xmlParseNameComplex(), xmlParseReference(), xmlSAX2TextNode(), xsltAddTemplate(), xsltApplyAttributeSet(), xsltApplyStylesheetInternal(), xsltAttribute(), xsltAttributeComp(), xsltAttrListTemplateProcess(), xsltAttrTemplateProcess(), xsltElement(), xsltElementComp(), xsltEvalStaticAttrValueTemplate(), xsltGetCNsProp(), xsltGetQNameProperty(), xsltGetQNameURI2(), xsltNumberComp(), xsltParseStylesheetAttributeSet(), xsltParseStylesheetTemplate(), xsltParseTemplateContent(), xsltPreprocessStylesheet(), xsltProcessUserParamInternal(), xsltRegisterGlobalVariable(), xsltShallowCopyAttr(), xsltSortComp(), xsltSplitQName(), xsltStackLookup(), and xsltXPathVariableLookup().

xmlDictLookupHashed()

xmlHashedString xmlDictLookupHashed	(	xmlDictPtr	dict,
		const xmlChar *	name,
		int	len
	)

Definition at line 845 of file dict.c.

                                                                   {
    const xmlDictEntry *entry;
    xmlHashedString ret;
 
    entry = xmlDictLookupInternal(dict, NULL, name, len, 1);
 
    if (entry == NULL) {
        ret.name = NULL;
        ret.hashValue = 0;
    } else {
        ret = *entry;
    }
 
    return(ret);
}

Referenced by xmlAddDefAttrs(), xmlParseInNodeContext(), xmlParseNCName(), xmlParseNCNameComplex(), xmlParseQNameHashed(), and xmlParseStartTag2().

xmlDictLookupInternal()

static ATTRIBUTE_NO_SANITIZE_INTEGER const xmlDictEntry * xmlDictLookupInternal ( xmlDictPtr  dict, const xmlChar *  prefix, const xmlChar *  name, int  maybeLen, int  update  )

static

Definition at line 678 of file dict.c.

                                                                     {
    xmlDictEntry *entry = NULL;
    const xmlChar *ret;
    unsigned hashValue;
    size_t maxLen, len, plen, klen;
    int found = 0;
 
    if ((dict == NULL) || (name == NULL))
    return(NULL);
 
    maxLen = (maybeLen < 0) ? SIZE_MAX : (size_t) maybeLen;
 
    if (prefix == NULL) {
        hashValue = xmlDictHashName(dict->seed, name, maxLen, &len);
        if (len > INT_MAX / 2)
            return(NULL);
        klen = len;
    } else {
        hashValue = xmlDictHashQName(dict->seed, prefix, name, &plen, &len);
        if ((len > INT_MAX / 2) || (plen >= INT_MAX / 2 - len))
            return(NULL);
        klen = plen + 1 + len;
    }
 
    if ((dict->limit > 0) && (klen >= dict->limit))
        return(NULL);
 
    /*
     * Check for an existing entry
     */
    if (dict->size > 0)
        entry = xmlDictFindEntry(dict, prefix, name, klen, hashValue, &found);
    if (found)
        return(entry);
 
    if ((dict->subdict != NULL) && (dict->subdict->size > 0)) {
        xmlDictEntry *subEntry;
        unsigned subHashValue;
 
        if (prefix == NULL)
            subHashValue = xmlDictHashName(dict->subdict->seed, name, len,
                                           &len);
        else
            subHashValue = xmlDictHashQName(dict->subdict->seed, prefix, name,
                                            &plen, &len);
        subEntry = xmlDictFindEntry(dict->subdict, prefix, name, klen,
                                    subHashValue, &found);
        if (found)
            return(subEntry);
    }
 
    if (!update)
        return(NULL);
 
    /*
     * Grow the hash table if needed
     */
    if (dict->nbElems + 1 > dict->size / MAX_FILL_DENOM * MAX_FILL_NUM) {
        unsigned newSize, mask, displ, pos;
 
        if (dict->size == 0) {
            newSize = MIN_HASH_SIZE;
        } else {
            if (dict->size >= MAX_HASH_SIZE)
                return(NULL);
            newSize = dict->size * 2;
        }
        if (xmlDictGrow(dict, newSize) != 0)
            return(NULL);
 
        /*
         * Find new entry
         */
        mask = dict->size - 1;
        displ = 0;
        pos = hashValue & mask;
        entry = &dict->table[pos];
 
        while ((entry->hashValue != 0) &&
               ((pos - entry->hashValue) & mask) >= displ) {
            displ++;
            pos++;
            entry++;
            if ((pos & mask) == 0)
                entry = dict->table;
        }
    }
 
    if (prefix == NULL)
        ret = xmlDictAddString(dict, name, len);
    else
        ret = xmlDictAddQString(dict, prefix, plen, name, len);
    if (ret == NULL)
        return(NULL);
 
    /*
     * Shift the remainder of the probe sequence to the right
     */
    if (entry->hashValue != 0) {
        const xmlDictEntry *end = &dict->table[dict->size];
        const xmlDictEntry *cur = entry;
 
        do {
            cur++;
            if (cur >= end)
                cur = dict->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(&dict->table[1], dict->table,
                    (char *) cur - (char *) dict->table);
            cur = end - 1;
            dict->table[0] = *cur;
        }
 
        memmove(&entry[1], entry, (char *) cur - (char *) entry);
    }
 
    /*
     * Populate entry
     */
    entry->hashValue = hashValue;
    entry->name = ret;
 
    dict->nbElems++;
 
    return(entry);
}

Referenced by xmlDictExists(), xmlDictLookup(), xmlDictLookupHashed(), and xmlDictQLookup().

xmlDictOwns()

int xmlDictOwns	(	xmlDictPtr	dict,
		const xmlChar *	str
	)

xmlDictOwns: @dict: the dictionary @str: the string

check if a string is owned by the dictionary

Returns 1 if true, 0 if false and -1 in case of error -1 in case of error

Definition at line 376 of file dict.c.

                                                 {
    xmlDictStringsPtr pool;
 
    if ((dict == NULL) || (str == NULL))
    return(-1);
    pool = dict->strings;
    while (pool != NULL) {
        if ((str >= &pool->array[0]) && (str <= pool->free))
        return(1);
    pool = pool->next;
    }
    if (dict->subdict)
        return(xmlDictOwns(dict->subdict, str));
    return(0);
}

Referenced by xmlDictOwns(), xmlFreeAttribute(), xmlFreeDocElementContent(), xmlHashUpdateInternal(), xmlParseEnumerationType(), xmlParseNotationType(), xmlSAX2ExternalSubset(), xmlSAX2Text(), xsltAttrListTemplateProcess(), xsltAttrTemplateProcess(), xsltCopyText(), xsltParseTemplateContent(), and xsltPreprocessStylesheet().

xmlDictQLookup()

const xmlChar * xmlDictQLookup	(	xmlDictPtr	dict,
		const xmlChar *	prefix,
		const xmlChar *	name
	)

Definition at line 894 of file dict.c.

                                                                            {
    const xmlDictEntry *entry;
 
    entry = xmlDictLookupInternal(dict, prefix, name, -1, 1);
    if (entry == NULL)
        return(NULL);
    return(entry->name);
}

Referenced by xmlSAX2StartElementNs(), xsltApplyStylesheetInternal(), and xsltDocumentElem().

xmlDictReference()

int xmlDictReference

(

xmlDictPtr

dict

)

xmlDictReference: @dict: the dictionary

Increment the reference counter of a dictionary

Returns 0 in case of success and -1 in case of error

Definition at line 317 of file dict.c.

                                  {
    if (dict == NULL) return -1;
    xmlMutexLock(&xmlDictMutex);
    dict->ref_counter++;
    xmlMutexUnlock(&xmlDictMutex);
    return(0);
}

Referenced by xmlDictCreateSub(), xmlHashCreateDict(), xmlParseBalancedChunkMemoryInternal(), xmlParseExternalEntityPrivate(), xmlSAX2StartDocument(), xslt_doc_default_loader(), xsltApplyStylesheetInternal(), xsltCreateRVT(), xsltDocDefaultLoaderFunc(), xsltDocumentElem(), xsltLoadStylesheetPI(), and xsltParseStylesheetUser().

xmlDictSetLimit()

size_t xmlDictSetLimit	(	xmlDictPtr	dict,
		size_t	limit
	)

xmlDictSetLimit: @dict: the dictionary @limit: the limit in bytes

Set a size limit for the dictionary Added in 2.9.0

Returns the previous limit of the dictionary or 0

Definition at line 421 of file dict.c.

                                               {
    size_t ret;
 
    if (dict == NULL)
    return(0);
    ret = dict->limit;
    dict->limit = limit;
    return(ret);
}

Referenced by xmlCtxtUseOptionsInternal(), and xmlInitSAXParserCtxt().

xmlDictSize()

int xmlDictSize

(

xmlDictPtr

dict

)

xmlDictSize: @dict: the dictionary

Query the number of elements installed in the hash @dict.

Returns the number of elements in the dictionary or -1 in case of error

Definition at line 402 of file dict.c.

                             {
    if (dict == NULL)
    return(-1);
    if (dict->subdict)
        return(dict->nbElems + dict->subdict->nbElems);
    return(dict->nbElems);
}

xmlInitDictInternal()

void xmlInitDictInternal

(

void

)

xmlInitDictInternal:

Initialize mutex.

Definition at line 99 of file dict.c.

                          {
    xmlInitMutex(&xmlDictMutex);
}

Referenced by xmlInitParser().

xmlInitializeDict()

int xmlInitializeDict

(

void

)

xmlInitializeDict:

DEPRECATED: Alias for xmlInitParser.

Returns 0.

Definition at line 88 of file dict.c.

                        {
    xmlInitParser();
    return(0);
}

xmlInitRandom()

ATTRIBUTE_NO_SANITIZE_INTEGER void xmlInitRandom

(

void

)

Definition at line 918 of file dict.c.

                    {
    int var;
 
    xmlInitMutex(&xmlRngMutex);
 
    /* TODO: Get seed values from system PRNG */
 
    globalRngState[0] = (unsigned) time(NULL) ^
                        HASH_ROL((unsigned) (size_t) &xmlInitRandom, 8);
    globalRngState[1] = HASH_ROL((unsigned) (size_t) &xmlRngMutex, 16) ^
                        HASH_ROL((unsigned) (size_t) &var, 24);
}

Referenced by xmlInitParser(), and xmlInitRandom().

xmlRandom()

unsigned xmlRandom

(

void

)

Definition at line 951 of file dict.c.

                {
#ifdef XML_THREAD_LOCAL
    if (!localRngInitialized) {
        xmlMutexLock(&xmlRngMutex);
        localRngState[0] = xoroshiro64ss(globalRngState);
        localRngState[1] = xoroshiro64ss(globalRngState);
        localRngInitialized = 1;
        xmlMutexUnlock(&xmlRngMutex);
    }
 
    return(xoroshiro64ss(localRngState));
#else
    unsigned ret;
 
    xmlMutexLock(&xmlRngMutex);
    ret = xoroshiro64ss(globalRngState);
    xmlMutexUnlock(&xmlRngMutex);
 
    return(ret);
#endif
}

Referenced by xmlDictCreate(), and xmlHashCreate().

xoroshiro64ss()

static ATTRIBUTE_NO_SANITIZE_INTEGER unsigned xoroshiro64ss ( unsigned *  s )

static

Definition at line 938 of file dict.c.

                           {
    unsigned s0 = s[0];
    unsigned s1 = s[1];
    unsigned result = HASH_ROL(s0 * 0x9E3779BB, 5) * 5;
 
    s1 ^= s0;
    s[0] = HASH_ROL(s0, 26) ^ s1 ^ (s1 << 9);
    s[1] = HASH_ROL(s1, 13);
 
    return(result & 0xFFFFFFFF);
}

Referenced by xmlRandom().

Variable Documentation

globalRngState

unsigned globalRngState[2]

static

Definition at line 909 of file dict.c.

Referenced by xmlInitRandom(), and xmlRandom().

xmlDictMutex

xmlMutex xmlDictMutex

static

Definition at line 78 of file dict.c.

Referenced by xmlCleanupDictInternal(), xmlDictFree(), xmlDictReference(), and xmlInitDictInternal().

xmlRngMutex

xmlMutex xmlRngMutex

static

Definition at line 907 of file dict.c.

Referenced by xmlCleanupRandom(), xmlInitRandom(), and xmlRandom().