* dict.c: dictionary of reusable strings, just used to avoid allocation
* and freeing operations.
*
- * Copyright (C) 2003 Daniel Veillard.
+ * Copyright (C) 2003-2012 Daniel Veillard.
*
* Permission to use, copy, modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
#define IN_LIBXML
#include "libxml.h"
+#include <limits.h>
+#ifdef HAVE_STDLIB_H
+#include <stdlib.h>
+#endif
+#ifdef HAVE_TIME_H
+#include <time.h>
+#endif
+
+/*
+ * Following http://www.ocert.org/advisories/ocert-2011-003.html
+ * it seems that having hash randomization might be a good idea
+ * when using XML with untrusted data
+ * Note1: that it works correctly only if compiled with WITH_BIG_KEY
+ * which is the default.
+ * Note2: the fast function used for a small dict won't protect very
+ * well but since the attack is based on growing a very big hash
+ * list we will use the BigKey algo as soon as the hash size grows
+ * over MIN_DICT_SIZE so this actually works
+ */
+#if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
+#define DICT_RANDOMIZATION
+#endif
+
#include <string.h>
+#ifdef HAVE_STDINT_H
+#include <stdint.h>
+#else
+#ifdef HAVE_INTTYPES_H
+#include <inttypes.h>
+#elif defined(WIN32)
+typedef unsigned __int32 uint32_t;
+#endif
+#endif
#include <libxml/tree.h>
#include <libxml/dict.h>
#include <libxml/xmlmemory.h>
#include <libxml/xmlerror.h>
#include <libxml/globals.h>
-#define MAX_HASH_LEN 4
+/* #define DEBUG_GROW */
+/* #define DICT_DEBUG_PATTERNS */
+
+#define MAX_HASH_LEN 3
#define MIN_DICT_SIZE 128
#define MAX_DICT_HASH 8 * 2048
-
-/* #define ALLOW_REMOVAL */
-/* #define DEBUG_GROW */
+#define WITH_BIG_KEY
+
+#ifdef WITH_BIG_KEY
+#define xmlDictComputeKey(dict, name, len) \
+ (((dict)->size == MIN_DICT_SIZE) ? \
+ xmlDictComputeFastKey(name, len, (dict)->seed) : \
+ xmlDictComputeBigKey(name, len, (dict)->seed))
+
+#define xmlDictComputeQKey(dict, prefix, plen, name, len) \
+ (((prefix) == NULL) ? \
+ (xmlDictComputeKey(dict, name, len)) : \
+ (((dict)->size == MIN_DICT_SIZE) ? \
+ xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \
+ xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
+
+#else /* !WITH_BIG_KEY */
+#define xmlDictComputeKey(dict, name, len) \
+ xmlDictComputeFastKey(name, len, (dict)->seed)
+#define xmlDictComputeQKey(dict, prefix, plen, name, len) \
+ xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
+#endif /* WITH_BIG_KEY */
/*
* An entry in the dictionnary
struct _xmlDictEntry {
struct _xmlDictEntry *next;
const xmlChar *name;
- int len;
+ unsigned int len;
int valid;
+ unsigned long okey;
};
typedef struct _xmlDictStrings xmlDictStrings;
xmlDictStringsPtr next;
xmlChar *free;
xmlChar *end;
- int size;
- int nbStrings;
+ size_t size;
+ size_t nbStrings;
xmlChar array[1];
};
/*
*/
struct _xmlDict {
int ref_counter;
- xmlRMutexPtr mutex;
struct _xmlDictEntry *dict;
- int size;
- int nbElems;
+ size_t size;
+ unsigned int nbElems;
xmlDictStringsPtr strings;
struct _xmlDict *subdict;
+ /* used for randomization */
+ int seed;
+ /* used to impose a limit on size */
+ size_t limit;
};
/*
*/
static int xmlDictInitialized = 0;
+#ifdef DICT_RANDOMIZATION
+#ifdef HAVE_RAND_R
+/*
+ * Internal data for random function, protected by xmlDictMutex
+ */
+static unsigned int rand_seed = 0;
+#endif
+#endif
+
/**
* xmlInitializeDict:
*
* Do the dictionary mutex initialization.
+ * this function is deprecated
+ *
+ * Returns 0 if initialization was already done, and 1 if that
+ * call led to the initialization
+ */
+int xmlInitializeDict(void) {
+ return(0);
+}
+
+/**
+ * __xmlInitializeDict:
+ *
+ * This function is not public
+ * Do the dictionary mutex initialization.
* this function is not thread safe, initialization should
- * preferably be done once at startup
+ * normally be done once at setup when called from xmlOnceInit()
+ * we may also land in this code if thread support is not compiled in
+ *
+ * Returns 0 if initialization was already done, and 1 if that
+ * call led to the initialization
*/
-static int xmlInitializeDict(void) {
+int __xmlInitializeDict(void) {
if (xmlDictInitialized)
return(1);
if ((xmlDictMutex = xmlNewRMutex()) == NULL)
return(0);
+ xmlRMutexLock(xmlDictMutex);
+#ifdef DICT_RANDOMIZATION
+#ifdef HAVE_RAND_R
+ rand_seed = time(NULL);
+ rand_r(& rand_seed);
+#else
+ srand(time(NULL));
+#endif
+#endif
xmlDictInitialized = 1;
+ xmlRMutexUnlock(xmlDictMutex);
return(1);
}
+#ifdef DICT_RANDOMIZATION
+int __xmlRandom(void) {
+ int ret;
+
+ if (xmlDictInitialized == 0)
+ __xmlInitializeDict();
+
+ xmlRMutexLock(xmlDictMutex);
+#ifdef HAVE_RAND_R
+ ret = rand_r(& rand_seed);
+#else
+ ret = rand();
+#endif
+ xmlRMutexUnlock(xmlDictMutex);
+ return(ret);
+}
+#endif
+
/**
* xmlDictCleanup:
*
- * Free the dictionary mutex.
+ * Free the dictionary mutex. Do not call unless sure the library
+ * is not in use anymore !
*/
void
xmlDictCleanup(void) {
* xmlDictAddString:
* @dict: the dictionnary
* @name: the name of the userdata
- * @len: the length of the name, if -1 it is recomputed
+ * @len: the length of the name
*
* Add the string to the array[s]
*
* Returns the pointer of the local string, or NULL in case of error.
*/
static const xmlChar *
-xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) {
+xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
xmlDictStringsPtr pool;
const xmlChar *ret;
- int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
+ size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
+ size_t limit = 0;
+#ifdef DICT_DEBUG_PATTERNS
+ fprintf(stderr, "-");
+#endif
pool = dict->strings;
while (pool != NULL) {
if (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 size *= 4; /* exponential growth */
- if (size < 4 * namelen)
+ if (size < 4 * namelen)
size = 4 * namelen; /* just in case ! */
pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
if (pool == NULL)
pool->end = &pool->array[size];
pool->next = dict->strings;
dict->strings = pool;
+#ifdef DICT_DEBUG_PATTERNS
+ fprintf(stderr, "+");
+#endif
}
found_pool:
ret = pool->free;
memcpy(pool->free, name, namelen);
pool->free += namelen;
*(pool->free++) = 0;
+ pool->nbStrings++;
return(ret);
}
* xmlDictAddQString:
* @dict: the dictionnary
* @prefix: the prefix of the userdata
+ * @plen: the prefix length
* @name: the name of the userdata
- * @len: the length of the name, if -1 it is recomputed
+ * @len: the length of the name
*
* Add the QName to the array[s]
*
* Returns the pointer of the local string, or NULL in case of error.
*/
static const xmlChar *
-xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix,
- const xmlChar *name, int namelen)
+xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
+ const xmlChar *name, unsigned int namelen)
{
xmlDictStringsPtr pool;
const xmlChar *ret;
- int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
- int plen;
+ size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
+ size_t limit = 0;
if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
- plen = xmlStrlen(prefix);
+#ifdef DICT_DEBUG_PATTERNS
+ fprintf(stderr, "=");
+#endif
pool = dict->strings;
while (pool != NULL) {
- if (pool->end - pool->free > namelen)
+ if (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)
- size = 4 * namelen; /* just in case ! */
+ 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->end = &pool->array[size];
pool->next = dict->strings;
dict->strings = pool;
+#ifdef DICT_DEBUG_PATTERNS
+ fprintf(stderr, "+");
+#endif
}
found_pool:
ret = pool->free;
memcpy(pool->free, prefix, plen);
pool->free += plen;
*(pool->free++) = ':';
- namelen -= plen + 1;
memcpy(pool->free, name, namelen);
pool->free += namelen;
*(pool->free++) = 0;
+ pool->nbStrings++;
return(ret);
}
+#ifdef WITH_BIG_KEY
+/*
+ * xmlDictComputeBigKey:
+ *
+ * Calculate a hash key using a good hash function that works well for
+ * larger hash table sizes.
+ *
+ * Hash function by "One-at-a-Time Hash" see
+ * http://burtleburtle.net/bob/hash/doobs.html
+ */
+
+static uint32_t
+xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
+ uint32_t hash;
+ int i;
+
+ if (namelen <= 0 || data == NULL) return(0);
+
+ hash = seed;
+
+ for (i = 0;i < namelen; i++) {
+ hash += data[i];
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+
+ return hash;
+}
+
+/*
+ * xmlDictComputeBigQKey:
+ *
+ * Calculate a hash key for two strings using a good hash function
+ * that works well for larger hash table sizes.
+ *
+ * Hash function by "One-at-a-Time Hash" see
+ * http://burtleburtle.net/bob/hash/doobs.html
+ *
+ * Neither of the two strings must be NULL.
+ */
+static unsigned long
+xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
+ const xmlChar *name, int len, int seed)
+{
+ uint32_t hash;
+ int i;
+
+ hash = seed;
+
+ for (i = 0;i < plen; i++) {
+ hash += prefix[i];
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ hash += ':';
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+
+ for (i = 0;i < len; i++) {
+ hash += name[i];
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+
+ return hash;
+}
+#endif /* WITH_BIG_KEY */
+
/*
- * xmlDictComputeKey:
- * Calculate the hash key
+ * xmlDictComputeFastKey:
+ *
+ * Calculate a hash key using a fast hash function that works well
+ * for low hash table fill.
*/
static unsigned long
-xmlDictComputeKey(const xmlChar *name, int namelen) {
- unsigned long value = 0L;
-
+xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
+ unsigned long value = seed;
+
if (name == NULL) return(0);
value = *name;
value <<= 5;
}
/*
- * xmlDictComputeQKey:
- * Calculate the hash key
+ * xmlDictComputeFastQKey:
+ *
+ * Calculate a hash key for two strings using a fast hash function
+ * that works well for low hash table fill.
+ *
+ * Neither of the two strings must be NULL.
*/
static unsigned long
-xmlDictComputeQKey(const xmlChar *prefix, const xmlChar *name, int len)
+xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
+ const xmlChar *name, int len, int seed)
{
- unsigned long value = 0L;
- int plen;
-
- if (prefix == NULL)
- return(xmlDictComputeKey(name, len));
+ unsigned long value = (unsigned long) seed;
- plen = xmlStrlen(prefix);
if (plen == 0)
value += 30 * (unsigned long) ':';
else
value += 30 * (*prefix);
-
+
if (len > 10) {
- value += name[len - (plen + 1 + 1)];
+ int offset = len - (plen + 1 + 1);
+ if (offset < 0)
+ offset = len - (10 + 1);
+ value += name[offset];
len = 10;
if (plen > 10)
plen = 10;
xmlDictPtr dict;
if (!xmlDictInitialized)
- if (!xmlInitializeDict())
+ if (!__xmlInitializeDict())
return(NULL);
-
+
+#ifdef DICT_DEBUG_PATTERNS
+ fprintf(stderr, "C");
+#endif
+
dict = xmlMalloc(sizeof(xmlDict));
if (dict) {
dict->ref_counter = 1;
+ dict->limit = 0;
dict->size = MIN_DICT_SIZE;
dict->nbElems = 0;
dict->strings = NULL;
dict->subdict = NULL;
if (dict->dict) {
- if ((dict->mutex = xmlNewRMutex()) != NULL) {
- memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
- return(dict);
- }
- xmlFree(dict->dict);
+ memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
+#ifdef DICT_RANDOMIZATION
+ dict->seed = __xmlRandom();
+#else
+ dict->seed = 0;
+#endif
+ return(dict);
}
xmlFree(dict);
}
xmlDictPtr
xmlDictCreateSub(xmlDictPtr sub) {
xmlDictPtr dict = xmlDictCreate();
-
+
if ((dict != NULL) && (sub != NULL)) {
+#ifdef DICT_DEBUG_PATTERNS
+ fprintf(stderr, "R");
+#endif
+ dict->seed = sub->seed;
dict->subdict = sub;
xmlDictReference(dict->subdict);
}
int
xmlDictReference(xmlDictPtr dict) {
if (!xmlDictInitialized)
- if (!xmlInitializeDict())
+ if (!__xmlInitializeDict())
return(-1);
if (dict == NULL) return -1;
* Returns 0 in case of success, -1 in case of failure
*/
static int
-xmlDictGrow(xmlDictPtr dict, int size) {
- unsigned long key;
- int oldsize, i;
+xmlDictGrow(xmlDictPtr dict, size_t size) {
+ unsigned long key, okey;
+ size_t oldsize, i;
xmlDictEntryPtr iter, next;
struct _xmlDictEntry *olddict;
#ifdef DEBUG_GROW
unsigned long nbElem = 0;
#endif
-
+ int ret = 0;
+ int keep_keys = 1;
+
if (dict == NULL)
return(-1);
if (size < 8)
if (size > 8 * 2048)
return(-1);
+#ifdef DICT_DEBUG_PATTERNS
+ fprintf(stderr, "*");
+#endif
+
oldsize = dict->size;
olddict = dict->dict;
if (olddict == NULL)
return(-1);
-
+ if (oldsize == MIN_DICT_SIZE)
+ keep_keys = 0;
+
dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
if (dict->dict == NULL) {
dict->dict = olddict;
dict->size = size;
/* If the two loops are merged, there would be situations where
- a new entry needs to allocated and data copied into it from
- the main dict. So instead, we run through the array twice, first
- copying all the elements in the main array (where we can't get
- conflicts) and then the rest, so we only free (and don't allocate)
+ a new entry needs to allocated and data copied into it from
+ the main dict. It is nicer to run through the array twice, first
+ copying all the elements in the main array (less probability of
+ allocate) and then the rest, so we only free in the second loop.
*/
for (i = 0; i < oldsize; i++) {
- if (olddict[i].valid == 0)
+ if (olddict[i].valid == 0)
continue;
- key = xmlDictComputeKey(olddict[i].name, olddict[i].len) % dict->size;
- memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
- dict->dict[key].next = NULL;
+
+ if (keep_keys)
+ okey = olddict[i].okey;
+ else
+ okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
+ key = okey % dict->size;
+
+ if (dict->dict[key].valid == 0) {
+ memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
+ dict->dict[key].next = NULL;
+ dict->dict[key].okey = okey;
+ } else {
+ xmlDictEntryPtr entry;
+
+ entry = xmlMalloc(sizeof(xmlDictEntry));
+ if (entry != NULL) {
+ entry->name = olddict[i].name;
+ entry->len = olddict[i].len;
+ entry->okey = okey;
+ entry->next = dict->dict[key].next;
+ entry->valid = 1;
+ dict->dict[key].next = entry;
+ } else {
+ /*
+ * we don't have much ways to alert from herei
+ * result is loosing an entry and unicity garantee
+ */
+ ret = -1;
+ }
+ }
#ifdef DEBUG_GROW
nbElem++;
#endif
* put back the entry in the new dict
*/
- key = xmlDictComputeKey(iter->name, iter->len) % dict->size;
+ if (keep_keys)
+ okey = iter->okey;
+ else
+ okey = xmlDictComputeKey(dict, iter->name, iter->len);
+ key = okey % dict->size;
if (dict->dict[key].valid == 0) {
memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
dict->dict[key].next = NULL;
dict->dict[key].valid = 1;
+ dict->dict[key].okey = okey;
xmlFree(iter);
} else {
- iter->next = dict->dict[key].next;
- dict->dict[key].next = iter;
+ iter->next = dict->dict[key].next;
+ iter->okey = okey;
+ dict->dict[key].next = iter;
}
#ifdef DEBUG_GROW
#ifdef DEBUG_GROW
xmlGenericError(xmlGenericErrorContext,
- "xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
+ "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
#endif
- return(0);
+ return(ret);
}
/**
*/
void
xmlDictFree(xmlDictPtr dict) {
- int i;
+ size_t i;
xmlDictEntryPtr iter;
xmlDictEntryPtr next;
int inside_dict = 0;
return;
if (!xmlDictInitialized)
- if (!xmlInitializeDict())
+ if (!__xmlInitializeDict())
return;
/* decrement the counter, it may be shared by a parser and docs */
inside_dict = 0;
iter = next;
}
- inside_dict = 0;
}
xmlFree(dict->dict);
}
xmlFree(pool);
pool = nextp;
}
- xmlFreeRMutex(dict->mutex);
xmlFree(dict);
}
xmlDictEntryPtr entry;
xmlDictEntryPtr insert;
const xmlChar *ret;
+ unsigned int l;
if ((dict == NULL) || (name == NULL))
return(NULL);
if (len < 0)
- len = xmlStrlen(name);
+ l = strlen((const char *) name);
+ else
+ l = len;
+
+ if (((dict->limit > 0) && (l >= dict->limit)) ||
+ (l > INT_MAX / 2))
+ return(NULL);
/*
* Check for duplicate and insertion location.
*/
- okey = xmlDictComputeKey(name, len);
+ okey = xmlDictComputeKey(dict, name, l);
key = okey % dict->size;
if (dict->dict[key].valid == 0) {
insert = NULL;
for (insert = &(dict->dict[key]); insert->next != NULL;
insert = insert->next) {
#ifdef __GNUC__
- if (insert->len == len) {
- if (!memcmp(insert->name, name, len))
+ if ((insert->okey == okey) && (insert->len == l)) {
+ if (!memcmp(insert->name, name, l))
return(insert->name);
}
#else
- if ((insert->len == len) &&
- (!xmlStrncmp(insert->name, name, len)))
+ if ((insert->okey == okey) && (insert->len == l) &&
+ (!xmlStrncmp(insert->name, name, l)))
return(insert->name);
#endif
nbi++;
}
#ifdef __GNUC__
- if (insert->len == len) {
- if (!memcmp(insert->name, name, len))
+ if ((insert->okey == okey) && (insert->len == l)) {
+ if (!memcmp(insert->name, name, l))
return(insert->name);
}
#else
- if ((insert->len == len) &&
- (!xmlStrncmp(insert->name, name, len)))
+ if ((insert->okey == okey) && (insert->len == l) &&
+ (!xmlStrncmp(insert->name, name, l)))
return(insert->name);
#endif
}
if (dict->subdict) {
- key = okey % dict->subdict->size;
+ unsigned long skey;
+
+ /* we cannot always reuse the same okey for the subdict */
+ if (((dict->size == MIN_DICT_SIZE) &&
+ (dict->subdict->size != MIN_DICT_SIZE)) ||
+ ((dict->size != MIN_DICT_SIZE) &&
+ (dict->subdict->size == MIN_DICT_SIZE)))
+ skey = xmlDictComputeKey(dict->subdict, name, l);
+ else
+ skey = okey;
+
+ key = skey % dict->subdict->size;
if (dict->subdict->dict[key].valid != 0) {
xmlDictEntryPtr tmp;
for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
tmp = tmp->next) {
#ifdef __GNUC__
- if (tmp->len == len) {
- if (!memcmp(tmp->name, name, len))
+ if ((tmp->okey == skey) && (tmp->len == l)) {
+ if (!memcmp(tmp->name, name, l))
return(tmp->name);
}
#else
- if ((tmp->len == len) &&
- (!xmlStrncmp(tmp->name, name, len)))
+ if ((tmp->okey == skey) && (tmp->len == l) &&
+ (!xmlStrncmp(tmp->name, name, l)))
return(tmp->name);
#endif
nbi++;
}
#ifdef __GNUC__
- if (tmp->len == len) {
- if (!memcmp(tmp->name, name, len))
+ if ((tmp->okey == skey) && (tmp->len == l)) {
+ if (!memcmp(tmp->name, name, l))
return(tmp->name);
}
#else
- if ((tmp->len == len) &&
- (!xmlStrncmp(tmp->name, name, len)))
+ if ((tmp->okey == skey) && (tmp->len == l) &&
+ (!xmlStrncmp(tmp->name, name, l)))
return(tmp->name);
#endif
}
key = okey % dict->size;
}
- ret = xmlDictAddString(dict, name, len);
+ ret = xmlDictAddString(dict, name, l);
if (ret == NULL)
return(NULL);
if (insert == NULL) {
return(NULL);
}
entry->name = ret;
- entry->len = len;
+ entry->len = l;
entry->next = NULL;
entry->valid = 1;
+ entry->okey = okey;
- if (insert != NULL)
+ if (insert != NULL)
insert->next = entry;
dict->nbElems++;
if ((nbi > MAX_HASH_LEN) &&
- (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
- xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
+ (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
+ if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
+ return(NULL);
+ }
/* Note that entry may have been freed at this point by xmlDictGrow */
return(ret);
xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
unsigned long key, okey, nbi = 0;
xmlDictEntryPtr insert;
+ unsigned int l;
if ((dict == NULL) || (name == NULL))
return(NULL);
if (len < 0)
- len = xmlStrlen(name);
+ l = strlen((const char *) name);
+ else
+ l = len;
+ if (((dict->limit > 0) && (l >= dict->limit)) ||
+ (l > INT_MAX / 2))
+ return(NULL);
/*
* Check for duplicate and insertion location.
*/
- okey = xmlDictComputeKey(name, len);
+ okey = xmlDictComputeKey(dict, name, l);
key = okey % dict->size;
if (dict->dict[key].valid == 0) {
insert = NULL;
for (insert = &(dict->dict[key]); insert->next != NULL;
insert = insert->next) {
#ifdef __GNUC__
- if (insert->len == len) {
- if (!memcmp(insert->name, name, len))
+ if ((insert->okey == okey) && (insert->len == l)) {
+ if (!memcmp(insert->name, name, l))
return(insert->name);
}
#else
- if ((insert->len == len) &&
- (!xmlStrncmp(insert->name, name, len)))
+ if ((insert->okey == okey) && (insert->len == l) &&
+ (!xmlStrncmp(insert->name, name, l)))
return(insert->name);
#endif
nbi++;
}
#ifdef __GNUC__
- if (insert->len == len) {
- if (!memcmp(insert->name, name, len))
+ if ((insert->okey == okey) && (insert->len == l)) {
+ if (!memcmp(insert->name, name, l))
return(insert->name);
}
#else
- if ((insert->len == len) &&
- (!xmlStrncmp(insert->name, name, len)))
+ if ((insert->okey == okey) && (insert->len == l) &&
+ (!xmlStrncmp(insert->name, name, l)))
return(insert->name);
#endif
}
if (dict->subdict) {
- key = okey % dict->subdict->size;
+ unsigned long skey;
+
+ /* we cannot always reuse the same okey for the subdict */
+ if (((dict->size == MIN_DICT_SIZE) &&
+ (dict->subdict->size != MIN_DICT_SIZE)) ||
+ ((dict->size != MIN_DICT_SIZE) &&
+ (dict->subdict->size == MIN_DICT_SIZE)))
+ skey = xmlDictComputeKey(dict->subdict, name, l);
+ else
+ skey = okey;
+
+ key = skey % dict->subdict->size;
if (dict->subdict->dict[key].valid != 0) {
xmlDictEntryPtr tmp;
for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
tmp = tmp->next) {
#ifdef __GNUC__
- if (tmp->len == len) {
- if (!memcmp(tmp->name, name, len))
+ if ((tmp->okey == skey) && (tmp->len == l)) {
+ if (!memcmp(tmp->name, name, l))
return(tmp->name);
}
#else
- if ((tmp->len == len) &&
- (!xmlStrncmp(tmp->name, name, len)))
+ if ((tmp->okey == skey) && (tmp->len == l) &&
+ (!xmlStrncmp(tmp->name, name, l)))
return(tmp->name);
#endif
nbi++;
}
#ifdef __GNUC__
- if (tmp->len == len) {
- if (!memcmp(tmp->name, name, len))
+ if ((tmp->okey == skey) && (tmp->len == l)) {
+ if (!memcmp(tmp->name, name, l))
return(tmp->name);
}
#else
- if ((tmp->len == len) &&
- (!xmlStrncmp(tmp->name, name, len)))
+ if ((tmp->okey == skey) && (tmp->len == l) &&
+ (!xmlStrncmp(tmp->name, name, l)))
return(tmp->name);
#endif
}
- key = okey % dict->size;
}
/* not found */
/**
* xmlDictQLookup:
* @dict: the dictionnary
- * @prefix: the prefix
+ * @prefix: the prefix
* @name: the name
*
* Add the QName @prefix:@name to the hash @dict if not present.
xmlDictEntryPtr entry;
xmlDictEntryPtr insert;
const xmlChar *ret;
- int len;
+ unsigned int len, plen, l;
if ((dict == NULL) || (name == NULL))
return(NULL);
+ if (prefix == NULL)
+ return(xmlDictLookup(dict, name, -1));
- len = xmlStrlen(name);
- if (prefix != NULL)
- len += 1 + xmlStrlen(prefix);
+ l = len = strlen((const char *) name);
+ plen = strlen((const char *) prefix);
+ len += 1 + plen;
/*
* Check for duplicate and insertion location.
*/
- okey = xmlDictComputeQKey(prefix, name, len);
+ okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
key = okey % dict->size;
if (dict->dict[key].valid == 0) {
insert = NULL;
} else {
for (insert = &(dict->dict[key]); insert->next != NULL;
insert = insert->next) {
- if ((insert->len == len) &&
+ if ((insert->okey == okey) && (insert->len == len) &&
(xmlStrQEqual(prefix, name, insert->name)))
return(insert->name);
nbi++;
}
- if ((insert->len == len) &&
+ if ((insert->okey == okey) && (insert->len == len) &&
(xmlStrQEqual(prefix, name, insert->name)))
return(insert->name);
}
if (dict->subdict) {
- key = okey % dict->subdict->size;
+ unsigned long skey;
+
+ /* we cannot always reuse the same okey for the subdict */
+ if (((dict->size == MIN_DICT_SIZE) &&
+ (dict->subdict->size != MIN_DICT_SIZE)) ||
+ ((dict->size != MIN_DICT_SIZE) &&
+ (dict->subdict->size == MIN_DICT_SIZE)))
+ skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
+ else
+ skey = okey;
+
+ key = skey % dict->subdict->size;
if (dict->subdict->dict[key].valid != 0) {
xmlDictEntryPtr tmp;
for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
tmp = tmp->next) {
- if ((tmp->len == len) &&
+ if ((tmp->okey == skey) && (tmp->len == len) &&
(xmlStrQEqual(prefix, name, tmp->name)))
return(tmp->name);
nbi++;
}
- if ((tmp->len == len) &&
+ if ((tmp->okey == skey) && (tmp->len == len) &&
(xmlStrQEqual(prefix, name, tmp->name)))
return(tmp->name);
}
key = okey % dict->size;
}
- ret = xmlDictAddQString(dict, prefix, name, len);
+ ret = xmlDictAddQString(dict, prefix, plen, name, l);
if (ret == NULL)
return(NULL);
if (insert == NULL) {
entry->len = len;
entry->next = NULL;
entry->valid = 1;
+ entry->okey = okey;
- if (insert != NULL)
+ if (insert != NULL)
insert->next = entry;
dict->nbElems++;
return(dict->nbElems);
}
+/**
+ * xmlDictSetLimit:
+ * @dict: the dictionnary
+ * @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
+ */
+size_t
+xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
+ size_t ret;
+
+ if (dict == NULL)
+ return(0);
+ ret = dict->limit;
+ dict->limit = limit;
+ return(ret);
+}
+
+/**
+ * xmlDictGetUsage:
+ * @dict: the dictionnary
+ *
+ * Get how much memory is used by a dictionary for strings
+ * Added in 2.9.0
+ *
+ * Returns the amount of strings allocated
+ */
+size_t
+xmlDictGetUsage(xmlDictPtr dict) {
+ 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);
+}
#define bottom_dict
#include "elfgcchack.h"
projects / platform / upstream / gettext.git / blobdiff