dict.c revision d46ee884c41b808b239563b1978468aae12e33a2
/*
* 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>
#include <libxml/xmlmemory.h>
#include <libxml/xmlerror.h>
#define MAX_HASH_LEN 4
#define MIN_DICT_SIZE 128
/* #define ALLOW_REMOVAL */
/* #define DEBUG_GROW */
/*
* An entry in the dictionnary
*/
typedef struct _xmlDictEntry xmlDictEntry;
typedef xmlDictEntry *xmlDictEntryPtr;
struct _xmlDictEntry {
struct _xmlDictEntry *next;
int len;
int valid;
};
typedef struct _xmlDictStrings xmlDictStrings;
typedef xmlDictStrings *xmlDictStringsPtr;
struct _xmlDictStrings {
int size;
int nbStrings;
};
/*
* The entire dictionnary
*/
struct _xmlDict {
int ref_counter;
struct _xmlDictEntry *dict;
int size;
int nbElems;
};
/*
* A mutex for modifying the reference counter for shared
* dictionaries.
*/
/*
* Whether the dictionary mutex was initialized.
*/
static int xmlDictInitialized = 0;
/**
* xmlInitializeDict:
*
* Do the dictionary mutex initialization.
* this function is not thread safe, initialization should
* preferably be done once at startup
*/
static int xmlInitializeDict(void) {
if (xmlDictInitialized)
return(1);
return(0);
xmlDictInitialized = 1;
return(1);
}
/**
* xmlDictCleanup:
*
* Free the dictionary mutex.
*/
void
xmlDictCleanup(void) {
if (!xmlDictInitialized)
return;
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 *
int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
goto found_pool;
}
/*
* Not found, need to allocate
*/
return(NULL);
}
return(ret);
}
/*
* xmlDictAddQString:
* @dict: the dictionnary
* @prefix: the prefix of the userdata
* @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 *
{
int size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
int plen;
goto found_pool;
}
/*
* Not found, need to allocate
*/
return(NULL);
}
return(ret);
}
/*
* xmlDictComputeKey:
* Calculate the hash key
*/
static unsigned long
unsigned long value = 0L;
value <<= 5;
if (namelen > 10) {
namelen = 10;
}
switch (namelen) {
default: break;
}
return(value);
}
/*
* xmlDictComputeQKey:
* Calculate the hash key
*/
static unsigned long
{
unsigned long value = 0L;
int plen;
if (plen == 0)
else
if (len > 10) {
len = 10;
if (plen > 10)
plen = 10;
}
switch (plen) {
default: break;
}
if (len > 0) {
value += (unsigned long) ':';
len--;
}
switch (len) {
default: break;
}
return(value);
}
/**
* xmlDictCreate:
*
* Create a new dictionary
*
* Returns the newly created dictionnary, or NULL if an error occured.
*/
xmlDictCreate(void) {
if (!xmlDictInitialized)
if (!xmlInitializeDict())
return(NULL);
if (dict) {
return(dict);
}
}
}
return(NULL);
}
/**
* xmlDictCreateSub:
* @sub: an existing dictionnary
*
* Create a new dictionary, inheriting strings from the read-only
* dictionnary @sub. On lookup, strings are first searched in the
* new dictionnary, then in @sub, and if not found are created in the
* new dictionnary.
*
* Returns the newly created dictionnary, or NULL if an error occured.
*/
}
return(dict);
}
/**
* xmlDictReference:
* @dict: the dictionnary
*
* Increment the reference counter of a dictionary
*
* Returns 0 in case of success and -1 in case of error
*/
int
if (!xmlDictInitialized)
if (!xmlInitializeDict())
return(-1);
dict->ref_counter++;
return(0);
}
/**
* xmlDictGrow:
* @dict: the dictionnary
* @size: the new size of the dictionnary
*
* resize the dictionnary
*
* Returns 0 in case of success, -1 in case of failure
*/
static int
unsigned long key;
int oldsize, i;
struct _xmlDictEntry *olddict;
#ifdef DEBUG_GROW
unsigned long nbElem = 0;
#endif
return(-1);
if (size < 8)
return(-1);
return(-1);
return(-1);
return(-1);
}
/* 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)
*/
for (i = 0; i < oldsize; i++) {
continue;
#ifdef DEBUG_GROW
nbElem++;
#endif
}
for (i = 0; i < oldsize; i++) {
while (iter) {
/*
* put back the entry in the new dict
*/
} else {
}
#ifdef DEBUG_GROW
nbElem++;
#endif
}
}
#ifdef DEBUG_GROW
#endif
return(0);
}
/**
* xmlDictFree:
* @dict: the dictionnary
*
* Free the hash @dict and its contents. The userdata is
* deallocated with @f if provided.
*/
void
int i;
int inside_dict = 0;
return;
if (!xmlDictInitialized)
if (!xmlInitializeDict())
return;
/* decrement the counter, it may be shared by a parser and docs */
dict->ref_counter--;
if (dict->ref_counter > 0) {
return;
}
}
continue;
inside_dict = 1;
while (iter) {
if (!inside_dict)
inside_dict = 0;
}
inside_dict = 0;
}
}
}
}
/**
* xmlDictLookup:
* @dict: the dictionnary
* @name: the name of the userdata
* @len: the length of the name, if -1 it is recomputed
*
* Add the @name to the dictionnary @dict if not present.
*
* Returns the internal copy of the name or NULL in case of internal error
*/
const xmlChar *
return(NULL);
if (len < 0)
/*
* Check for duplicate and insertion location.
*/
} else {
#ifdef __GNUC__
}
#else
#endif
nbi++;
}
#ifdef __GNUC__
}
#else
#endif
}
#ifdef __GNUC__
}
#else
#endif
nbi++;
}
#ifdef __GNUC__
}
#else
#endif
}
}
return(NULL);
} else {
return(NULL);
}
if ((nbi > MAX_HASH_LEN) &&
/* Note that entry may have been freed at this point by xmlDictGrow */
return(ret);
}
/**
* xmlDictExists:
* @dict: the dictionnary
* @name: the name of the userdata
* @len: the length of the name, if -1 it is recomputed
*
* Check if the @name exists in the dictionnary @dict.
*
* Returns the internal copy of the name or NULL if not found.
*/
const xmlChar *
return(NULL);
if (len < 0)
/*
* Check for duplicate and insertion location.
*/
} else {
#ifdef __GNUC__
}
#else
#endif
nbi++;
}
#ifdef __GNUC__
}
#else
#endif
}
#ifdef __GNUC__
}
#else
#endif
nbi++;
}
#ifdef __GNUC__
}
#else
#endif
}
}
/* not found */
return(NULL);
}
/**
* xmlDictQLookup:
* @dict: the dictionnary
* @prefix: the prefix
* @name: the name
*
* Add the QName @prefix:@name to the hash @dict if not present.
*
* Returns the internal copy of the QName or NULL in case of internal error
*/
const xmlChar *
int len;
return(NULL);
/*
* Check for duplicate and insertion location.
*/
} else {
nbi++;
}
}
nbi++;
}
}
}
return(NULL);
} else {
return(NULL);
}
if ((nbi > MAX_HASH_LEN) &&
/* Note that entry may have been freed at this point by xmlDictGrow */
return(ret);
}
/**
* xmlDictOwns:
* @dict: the dictionnary
* @str: the string
*
* check if a string is owned by the disctionary
*
* Returns 1 if true, 0 if false and -1 in case of error
* -1 in case of error
*/
int
return(-1);
return(1);
}
return(0);
}
/**
* xmlDictSize:
* @dict: the dictionnary
*
* Query the number of elements installed in the hash @dict.
*
* Returns the number of elements in the dictionnary or
* -1 in case of error
*/
int
return(-1);
}
#define bottom_dict
#include "elfgcchack.h"