dict.c

Go to the documentation of this file.

/*
 * dict.c: dictionary of reusable strings, just used to avoid allocation
 *         and freeing operations.
 *
 * Copyright (C) 2003 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
 * copyright notice and this permission notice appear in all copies.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
 *
 * Author: daniel@veillard.com
 */

#define IN_LIBXML
#include "libxml.h"

#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 DEBUG_GROW */
/* #define DICT_DEBUG_PATTERNS */

#define MAX_HASH_LEN 3
#define MIN_DICT_SIZE 128
#define MAX_DICT_HASH 8 * 2048
#define WITH_BIG_KEY

#ifdef WITH_BIG_KEY
#define xmlDictComputeKey(dict, name, len)          \
    (((dict)->size == MIN_DICT_SIZE) ?              \
     xmlDictComputeFastKey(name, len) :             \
     xmlDictComputeBigKey(name, len))

#define xmlDictComputeQKey(dict, prefix, plen, name, len)   \
    (((prefix) == NULL) ?                   \
      (xmlDictComputeKey(dict, name, len)) :            \
      (((dict)->size == MIN_DICT_SIZE) ?            \
       xmlDictComputeFastQKey(prefix, plen, name, len) :    \
       xmlDictComputeBigQKey(prefix, plen, name, len)))

#else /* !WITH_BIG_KEY */
#define xmlDictComputeKey(dict, name, len)          \
        xmlDictComputeFastKey(name, len)
#define xmlDictComputeQKey(dict, prefix, plen, name, len)   \
        xmlDictComputeFastQKey(prefix, plen, name, len)
#endif /* WITH_BIG_KEY */

/*
 * An entry in the dictionnary
 */
typedef struct _xmlDictEntry xmlDictEntry;
typedef xmlDictEntry *xmlDictEntryPtr;
struct _xmlDictEntry {
    struct _xmlDictEntry *next;
    const xmlChar *name;
    int len;
    int valid;
    unsigned long okey;
};

typedef struct _xmlDictStrings xmlDictStrings;
typedef xmlDictStrings *xmlDictStringsPtr;
struct _xmlDictStrings {
    xmlDictStringsPtr next;
    xmlChar *free;
    xmlChar *end;
    int size;
    int nbStrings;
    xmlChar array[1];
};
/*
 * The entire dictionnary
 */
struct _xmlDict {
    int ref_counter;

    struct _xmlDictEntry *dict;
    int size;
    int nbElems;
    xmlDictStringsPtr strings;

    struct _xmlDict *subdict;
};

/*
 * A mutex for modifying the reference counter for shared
 * dictionaries.
 */
static xmlRMutexPtr xmlDictMutex = NULL;

/*
 * Whether the dictionary mutex was initialized.
 */
static int xmlDictInitialized = 0;

static int xmlInitializeDict(void) {
    if (xmlDictInitialized)
        return(1);

    if ((xmlDictMutex = xmlNewRMutex()) == NULL)
        return(0);

    xmlDictInitialized = 1;
    return(1);
}

void
xmlDictCleanup(void) {
    if (!xmlDictInitialized)
        return;

    xmlFreeRMutex(xmlDictMutex);

    xmlDictInitialized = 0;
}

/*
 * xmlDictAddString:
 * @dict: the dictionnary
 * @name: the name of the userdata
 * @len: the length of the name, if -1 it is recomputed
 *
 * 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) {
    xmlDictStringsPtr pool;
    const xmlChar *ret;
    int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */

#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;
    pool = pool->next;
    }
    /*
     * Not found, need to allocate
     */
    if (pool == NULL) {
        if (size == 0) size = 1000;
    else size *= 4; /* exponential growth */
        if (size < 4 * namelen) 
        size = 4 * namelen; /* 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;
#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
 *
 * 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, int plen,
                 const xmlChar *name, int namelen)
{
    xmlDictStringsPtr pool;
    const xmlChar *ret;
    int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */

    if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));

#ifdef DICT_DEBUG_PATTERNS
    fprintf(stderr, "=");
#endif
    pool = dict->strings;
    while (pool != NULL) {
    if (pool->end - pool->free > namelen + plen + 1)
        goto found_pool;
    if (pool->size > size) size = pool->size;
    pool = pool->next;
    }
    /*
     * Not found, need to allocate
     */
    if (pool == 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;
#ifdef DICT_DEBUG_PATTERNS
        fprintf(stderr, "+");
#endif
    }
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);
}

#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) {
    uint32_t hash;
    int i;

    if (namelen <= 0 || data == NULL) return(0);

    hash = 0;

    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)
{
    uint32_t hash;
    int i;

    hash = 0;

    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 */

/*
 * xmlDictComputeFastKey:
 *
 * Calculate a hash key using a fast hash function that works well
 * for low hash table fill.
 */
static unsigned long
xmlDictComputeFastKey(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);
}

/*
 * 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
xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
                       const xmlChar *name, int len)
{
    unsigned long value = 0L;

    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;

    if (!xmlDictInitialized)
        if (!xmlInitializeDict())
            return(NULL);

#ifdef DICT_DEBUG_PATTERNS
    fprintf(stderr, "C");
#endif

    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)) {
#ifdef DICT_DEBUG_PATTERNS
        fprintf(stderr, "R");
#endif
        dict->subdict = sub;
    xmlDictReference(dict->subdict);
    }
    return(dict);
}

int
xmlDictReference(xmlDictPtr dict) {
    if (!xmlDictInitialized)
        if (!xmlInitializeDict())
            return(-1);

    if (dict == NULL) return -1;
    xmlRMutexLock(xmlDictMutex);
    dict->ref_counter++;
    xmlRMutexUnlock(xmlDictMutex);
    return(0);
}

static int
xmlDictGrow(xmlDictPtr dict, int size) {
    unsigned long key, okey;
    int 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)
        return(-1);
    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;
    return(-1);
    }
    memset(dict->dict, 0, size * sizeof(xmlDictEntry));
    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. 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)
        continue;

    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
    }

    for (i = 0; i < oldsize; i++) {
    iter = olddict[i].next;
    while (iter) {
        next = iter->next;

        /*
         * put back the entry in the new dict
         */

        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;
        iter->okey = okey;
        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(ret);
}

void
xmlDictFree(xmlDictPtr dict) {
    int i;
    xmlDictEntryPtr iter;
    xmlDictEntryPtr next;
    int inside_dict = 0;
    xmlDictStringsPtr pool, nextp;

    if (dict == NULL)
    return;

    if (!xmlDictInitialized)
        if (!xmlInitializeDict())
            return;

    /* decrement the counter, it may be shared by a parser and docs */
    xmlRMutexLock(xmlDictMutex);
    dict->ref_counter--;
    if (dict->ref_counter > 0) {
        xmlRMutexUnlock(xmlDictMutex);
        return;
    }

    xmlRMutexUnlock(xmlDictMutex);

    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;
        }
    }
    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 = strlen((const char *) name);

    /*
     * Check for duplicate and insertion location.
     */
    okey = xmlDictComputeKey(dict, 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->okey == okey) && (insert->len == len)) {
        if (!memcmp(insert->name, name, len))
            return(insert->name);
        }
#else
        if ((insert->okey == okey) && (insert->len == len) &&
            (!xmlStrncmp(insert->name, name, len)))
        return(insert->name);
#endif
        nbi++;
    }
#ifdef __GNUC__
    if ((insert->okey == okey) && (insert->len == len)) {
        if (!memcmp(insert->name, name, len))
        return(insert->name);
    }
#else
    if ((insert->okey == okey) && (insert->len == len) &&
        (!xmlStrncmp(insert->name, name, len)))
        return(insert->name);
#endif
    }

    if (dict->subdict) {
        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, len);
    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->okey == skey) && (tmp->len == len)) {
            if (!memcmp(tmp->name, name, len))
            return(tmp->name);
        }
#else
        if ((tmp->okey == skey) && (tmp->len == len) &&
            (!xmlStrncmp(tmp->name, name, len)))
            return(tmp->name);
#endif
        nbi++;
        }
#ifdef __GNUC__
        if ((tmp->okey == skey) && (tmp->len == len)) {
        if (!memcmp(tmp->name, name, len))
            return(tmp->name);
        }
#else
        if ((tmp->okey == skey) && (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;
    entry->okey = okey;


    if (insert != NULL) 
    insert->next = entry;

    dict->nbElems++;

    if ((nbi > MAX_HASH_LEN) &&
        (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);
}

const xmlChar *
xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
    unsigned long key, okey, nbi = 0;
    xmlDictEntryPtr insert;

    if ((dict == NULL) || (name == NULL))
    return(NULL);

    if (len < 0)
        len = strlen((const char *) name);

    /*
     * Check for duplicate and insertion location.
     */
    okey = xmlDictComputeKey(dict, 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->okey == okey) && (insert->len == len)) {
        if (!memcmp(insert->name, name, len))
            return(insert->name);
        }
#else
        if ((insert->okey == okey) && (insert->len == len) &&
            (!xmlStrncmp(insert->name, name, len)))
        return(insert->name);
#endif
        nbi++;
    }
#ifdef __GNUC__
    if ((insert->okey == okey) && (insert->len == len)) {
        if (!memcmp(insert->name, name, len))
        return(insert->name);
    }
#else
    if ((insert->okey == okey) && (insert->len == len) &&
        (!xmlStrncmp(insert->name, name, len)))
        return(insert->name);
#endif
    }

    if (dict->subdict) {
        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, len);
    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->okey == skey) && (tmp->len == len)) {
            if (!memcmp(tmp->name, name, len))
            return(tmp->name);
        }
#else
        if ((tmp->okey == skey) && (tmp->len == len) &&
            (!xmlStrncmp(tmp->name, name, len)))
            return(tmp->name);
#endif
        nbi++;
        }
#ifdef __GNUC__
        if ((tmp->okey == skey) && (tmp->len == len)) {
        if (!memcmp(tmp->name, name, len))
            return(tmp->name);
        }
#else
        if ((tmp->okey == skey) && (tmp->len == len) &&
        (!xmlStrncmp(tmp->name, name, len)))
        return(tmp->name);
#endif
    }
    }

    /* not found */
    return(NULL);
}

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, plen, l;

    if ((dict == NULL) || (name == NULL))
    return(NULL);
    if (prefix == NULL)
        return(xmlDictLookup(dict, name, -1));

    l = len = strlen((const char *) name);
    plen = strlen((const char *) prefix);
    len += 1 + plen;

    /*
     * Check for duplicate and insertion location.
     */
    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->okey == okey) && (insert->len == len) &&
            (xmlStrQEqual(prefix, name, insert->name)))
        return(insert->name);
        nbi++;
    }
    if ((insert->okey == okey) && (insert->len == len) &&
        (xmlStrQEqual(prefix, name, insert->name)))
        return(insert->name);
    }

    if (dict->subdict) {
        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->okey == skey) && (tmp->len == len) &&
            (xmlStrQEqual(prefix, name, tmp->name)))
            return(tmp->name);
        nbi++;
        }
        if ((tmp->okey == skey) && (tmp->len == len) &&
        (xmlStrQEqual(prefix, name, tmp->name)))
        return(tmp->name);
    }
    key = okey % dict->size;
    }

    ret = xmlDictAddQString(dict, prefix, plen, name, l);
    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;
    entry->okey = okey;

    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);
    /* Note that entry may have been freed at this point by xmlDictGrow */

    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[0]) && (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);
}


#define bottom_dict
#include "elfgcchack.h"