#define IN_LIBXML
#include "libxml.h"
#include <string.h>
#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 MIN_DICT_SIZE 128
#define MAX_DICT_HASH 8 * 2048
typedef struct _xmlDictEntry xmlDictEntry;
typedef xmlDictEntry *xmlDictEntryPtr;
struct _xmlDictEntry {
struct _xmlDictEntry *next;
const xmlChar *name;
int len;
int valid;
};
typedef struct _xmlDictStrings xmlDictStrings;
typedef xmlDictStrings *xmlDictStringsPtr;
struct _xmlDictStrings {
xmlDictStringsPtr next;
xmlChar *free;
xmlChar *end;
int size;
int nbStrings;
xmlChar array[1];
};
struct _xmlDict {
int ref_counter;
struct _xmlDictEntry *dict;
int size;
int nbElems;
xmlDictStringsPtr strings;
struct _xmlDict *subdict;
};
static const xmlChar *
xmlDictAddString(xmlDictPtr dict, const xmlChar *name, int namelen) {
xmlDictStringsPtr pool;
const xmlChar *ret;
int size = 0;
pool = dict->strings;
while (pool != NULL) {
if (pool->end - pool->free > namelen)
goto found_pool;
if (pool->size > size) size = pool->size;
pool = pool->next;
}
if (pool == NULL) {
if (size == 0) size = 1000;
else size *= 4;
if (size < 4 * namelen)
size = 4 * namelen;
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;
return(ret);
}
static const xmlChar *
xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix,
const xmlChar *name, int namelen)
{
xmlDictStringsPtr pool;
const xmlChar *ret;
int size = 0;
int plen;
if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
plen = xmlStrlen(prefix);
pool = dict->strings;
while (pool != NULL) {
if (pool->end - pool->free > namelen)
goto found_pool;
if (pool->size > size) size = pool->size;
pool = pool->next;
}
if (pool == NULL) {
if (size == 0) size = 1000;
else size *= 4;
if (size < 4 * namelen)
size = 4 * namelen;
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++) = ':';
namelen -= plen + 1;
memcpy(pool->free, name, namelen);
pool->free += namelen;
*(pool->free++) = 0;
return(ret);
}
static unsigned long
xmlDictComputeKey(const xmlChar *name, int namelen) {
unsigned long value = 0L;
if (name == NULL) return(0);
value = *name;
value <<= 5;
if (namelen > 10) {
value += name[namelen - 1];
namelen = 10;
}
switch (namelen) {
case 10: value += name[9];
case 9: value += name[8];
case 8: value += name[7];
case 7: value += name[6];
case 6: value += name[5];
case 5: value += name[4];
case 4: value += name[3];
case 3: value += name[2];
case 2: value += name[1];
default: break;
}
return(value);
}
static unsigned long
xmlDictComputeQKey(const xmlChar *prefix, const xmlChar *name, int len)
{
unsigned long value = 0L;
int plen;
if (prefix == NULL)
return(xmlDictComputeKey(name, len));
plen = xmlStrlen(prefix);
if (plen == 0)
value += 30 * (unsigned long) ':';
else
value += 30 * (*prefix);
if (len > 10) {
value += name[len - (plen + 1 + 1)];
len = 10;
if (plen > 10)
plen = 10;
}
switch (plen) {
case 10: value += prefix[9];
case 9: value += prefix[8];
case 8: value += prefix[7];
case 7: value += prefix[6];
case 6: value += prefix[5];
case 5: value += prefix[4];
case 4: value += prefix[3];
case 3: value += prefix[2];
case 2: value += prefix[1];
case 1: value += prefix[0];
default: break;
}
len -= plen;
if (len > 0) {
value += (unsigned long) ':';
len--;
}
switch (len) {
case 10: value += name[9];
case 9: value += name[8];
case 8: value += name[7];
case 7: value += name[6];
case 6: value += name[5];
case 5: value += name[4];
case 4: value += name[3];
case 3: value += name[2];
case 2: value += name[1];
case 1: value += name[0];
default: break;
}
return(value);
}
xmlDictPtr
xmlDictCreate(void) {
xmlDictPtr dict;
dict = xmlMalloc(sizeof(xmlDict));
if (dict) {
dict->ref_counter = 1;
dict->size = MIN_DICT_SIZE;
dict->nbElems = 0;
dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
dict->strings = NULL;
dict->subdict = NULL;
if (dict->dict) {
memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
return(dict);
}
xmlFree(dict);
}
return(NULL);
}
xmlDictPtr
xmlDictCreateSub(xmlDictPtr sub) {
xmlDictPtr dict = xmlDictCreate();
if ((dict != NULL) && (sub != NULL)) {
dict->subdict = sub;
xmlDictReference(dict->subdict);
}
return(dict);
}
int
xmlDictReference(xmlDictPtr dict) {
if (dict == NULL) return -1;
dict->ref_counter++;
return(0);
}
static int
xmlDictGrow(xmlDictPtr dict, int size) {
unsigned long key;
int oldsize, i;
xmlDictEntryPtr iter, next;
struct _xmlDictEntry *olddict;
#ifdef DEBUG_GROW
unsigned long nbElem = 0;
#endif
if (dict == NULL)
return(-1);
if (size < 8)
return(-1);
if (size > 8 * 2048)
return(-1);
oldsize = dict->size;
olddict = dict->dict;
if (olddict == NULL)
return(-1);
dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
if (dict->dict == NULL) {
dict->dict = olddict;
return(-1);
}
memset(dict->dict, 0, size * sizeof(xmlDictEntry));
dict->size = size;
for (i = 0; i < oldsize; i++) {
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;
#ifdef DEBUG_GROW
nbElem++;
#endif
}
for (i = 0; i < oldsize; i++) {
iter = olddict[i].next;
while (iter) {
next = iter->next;
key = xmlDictComputeKey(iter->name, iter->len) % 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;
xmlFree(iter);
} else {
iter->next = dict->dict[key].next;
dict->dict[key].next = iter;
}
#ifdef DEBUG_GROW
nbElem++;
#endif
iter = next;
}
}
xmlFree(olddict);
#ifdef DEBUG_GROW
xmlGenericError(xmlGenericErrorContext,
"xmlDictGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
#endif
return(0);
}
void
xmlDictFree(xmlDictPtr dict) {
int i;
xmlDictEntryPtr iter;
xmlDictEntryPtr next;
int inside_dict = 0;
xmlDictStringsPtr pool, nextp;
if (dict == NULL)
return;
dict->ref_counter--;
if (dict->ref_counter > 0) return;
if (dict->subdict != NULL) {
xmlDictFree(dict->subdict);
}
if (dict->dict) {
for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
iter = &(dict->dict[i]);
if (iter->valid == 0)
continue;
inside_dict = 1;
while (iter) {
next = iter->next;
if (!inside_dict)
xmlFree(iter);
dict->nbElems--;
inside_dict = 0;
iter = next;
}
inside_dict = 0;
}
xmlFree(dict->dict);
}
pool = dict->strings;
while (pool != NULL) {
nextp = pool->next;
xmlFree(pool);
pool = nextp;
}
xmlFree(dict);
}
const xmlChar *
xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
unsigned long key, okey, nbi = 0;
xmlDictEntryPtr entry;
xmlDictEntryPtr insert;
const xmlChar *ret;
if ((dict == NULL) || (name == NULL))
return(NULL);
if (len < 0)
len = xmlStrlen(name);
okey = xmlDictComputeKey(name, len);
key = okey % dict->size;
if (dict->dict[key].valid == 0) {
insert = NULL;
} else {
for (insert = &(dict->dict[key]); insert->next != NULL;
insert = insert->next) {
#ifdef __GNUC__
if (insert->len == len) {
if (!memcmp(insert->name, name, len))
return(insert->name);
}
#else
if ((insert->len == len) &&
(!xmlStrncmp(insert->name, name, len)))
return(insert->name);
#endif
nbi++;
}
#ifdef __GNUC__
if (insert->len == len) {
if (!memcmp(insert->name, name, len))
return(insert->name);
}
#else
if ((insert->len == len) &&
(!xmlStrncmp(insert->name, name, len)))
return(insert->name);
#endif
}
if (dict->subdict) {
key = okey % 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))
return(tmp->name);
}
#else
if ((tmp->len == len) &&
(!xmlStrncmp(tmp->name, name, len)))
return(tmp->name);
#endif
nbi++;
}
#ifdef __GNUC__
if (tmp->len == len) {
if (!memcmp(tmp->name, name, len))
return(tmp->name);
}
#else
if ((tmp->len == len) &&
(!xmlStrncmp(tmp->name, name, len)))
return(tmp->name);
#endif
}
key = okey % dict->size;
}
ret = xmlDictAddString(dict, name, len);
if (ret == NULL)
return(NULL);
if (insert == NULL) {
entry = &(dict->dict[key]);
} else {
entry = xmlMalloc(sizeof(xmlDictEntry));
if (entry == NULL)
return(NULL);
}
entry->name = ret;
entry->len = len;
entry->next = NULL;
entry->valid = 1;
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);
return(ret);
}
const xmlChar *
xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
unsigned long okey, key, nbi = 0;
xmlDictEntryPtr entry;
xmlDictEntryPtr insert;
const xmlChar *ret;
int len;
if ((dict == NULL) || (name == NULL))
return(NULL);
len = xmlStrlen(name);
if (prefix != NULL)
len += 1 + xmlStrlen(prefix);
okey = xmlDictComputeQKey(prefix, name, len);
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) &&
(xmlStrQEqual(prefix, name, insert->name)))
return(insert->name);
nbi++;
}
if ((insert->len == len) &&
(xmlStrQEqual(prefix, name, insert->name)))
return(insert->name);
}
if (dict->subdict) {
key = okey % 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) &&
(xmlStrQEqual(prefix, name, tmp->name)))
return(tmp->name);
nbi++;
}
if ((tmp->len == len) &&
(xmlStrQEqual(prefix, name, tmp->name)))
return(tmp->name);
}
key = okey % dict->size;
}
ret = xmlDictAddQString(dict, prefix, name, len);
if (ret == NULL)
return(NULL);
if (insert == NULL) {
entry = &(dict->dict[key]);
} else {
entry = xmlMalloc(sizeof(xmlDictEntry));
if (entry == NULL)
return(NULL);
}
entry->name = ret;
entry->len = len;
entry->next = NULL;
entry->valid = 1;
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);
return(ret);
}
int
xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
xmlDictStringsPtr pool;
if ((dict == NULL) || (str == NULL))
return(-1);
pool = dict->strings;
while (pool != NULL) {
if ((str >= pool->array) && (str <= pool->free))
return(1);
pool = pool->next;
}
if (dict->subdict)
return(xmlDictOwns(dict->subdict, str));
return(0);
}
int
xmlDictSize(xmlDictPtr dict) {
if (dict == NULL)
return(-1);
if (dict->subdict)
return(dict->nbElems + dict->subdict->nbElems);
return(dict->nbElems);
}