ReactOS 0.4.16-dev-199-g898cc56
hash.c File Reference
#include "libxml.h"
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <libxml/parser.h>
#include <libxml/hash.h>
#include <libxml/xmlmemory.h>
#include <libxml/xmlerror.h>
#include <libxml/globals.h>
Include dependency graph for hash.c:

Go to the source code of this file.

Classes

struct  _xmlHashEntry
 
struct  _xmlHashTable
 
struct  stubData
 

Macros

#define IN_LIBXML
 
#define HASH_RANDOMIZATION
 
#define MAX_HASH_LEN   8
 

Typedefs

typedef struct _xmlHashEntry xmlHashEntry
 
typedef xmlHashEntryxmlHashEntryPtr
 

Functions

static unsigned long xmlHashComputeKey (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3)
 
static unsigned long xmlHashComputeQKey (xmlHashTablePtr table, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3)
 
xmlHashTablePtr xmlHashCreate (int size)
 
xmlHashTablePtr xmlHashCreateDict (int size, xmlDictPtr dict)
 
static int xmlHashGrow (xmlHashTablePtr table, int size)
 
void xmlHashFree (xmlHashTablePtr table, xmlHashDeallocator f)
 
: the entry's name

xmlHashDefaultDeallocator: @entry: the hash table entry

Free a hash table entry with xmlFree.

void xmlHashDefaultDeallocator (void *entry, const xmlChar *name ATTRIBUTE_UNUSED)
 
. Duplicate names generate errors.

Returns 0 the addition succeeded and -1 in case of error.

int xmlHashAddEntry (xmlHashTablePtr table, const xmlChar *name, void *userdata)
 
, @name2) tuple. Duplicate tuples generate errors.

Returns 0 the addition succeeded and -1 in case of error.

int xmlHashAddEntry2 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, void *userdata)
 
. Existing entry for this @name will be removed

and freed with @f if found.

Returns 0 the addition succeeded and -1 in case of error.

int xmlHashUpdateEntry (xmlHashTablePtr table, const xmlChar *name, void *userdata, xmlHashDeallocator f)
 
, @name2) tuple. Existing entry for this tuple will

be removed and freed with @f if found.

Returns 0 the addition succeeded and -1 in case of error.

int xmlHashUpdateEntry2 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, void *userdata, xmlHashDeallocator f)
 
.

Returns the pointer to the userdata

voidxmlHashLookup (xmlHashTablePtr table, const xmlChar *name)
 
, @name2) tuple.

Returns the pointer to the userdata

voidxmlHashLookup2 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2)
 
/@name.

Returns the pointer to the userdata

voidxmlHashQLookup (xmlHashTablePtr table, const xmlChar *prefix, const xmlChar *name)
 
2: a second name of the userdata
voidxmlHashQLookup2 (xmlHashTablePtr table, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2)
 
, @name2, @name3). Duplicate entries generate

errors.

Returns 0 the addition succeeded and -1 in case of error.

int xmlHashAddEntry3 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, void *userdata)
 
, @name2, @name3). Existing entry for this tuple

will be removed and freed with @f if found.

Returns 0 the addition succeeded and -1 in case of error.

int xmlHashUpdateEntry3 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, void *userdata, xmlHashDeallocator f)
 
, @name2, @name3) tuple.

Returns the a pointer to the userdata

voidxmlHashLookup3 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3)
 
voidxmlHashQLookup3 (xmlHashTablePtr table, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3)
 
static void stubHashScannerFull (void *payload, void *data, const xmlChar *name, const xmlChar *name2 ATTRIBUTE_UNUSED, const xmlChar *name3 ATTRIBUTE_UNUSED)
 
void xmlHashScan (xmlHashTablePtr table, xmlHashScanner f, void *data)
 
void xmlHashScanFull (xmlHashTablePtr table, xmlHashScannerFull f, void *data)
 
, @name2, @name3) tuple. If one of the names is null,

the comparison is considered to match.

void xmlHashScan3 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, xmlHashScanner f, void *data)
 
void xmlHashScanFull3 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, xmlHashScannerFull f, void *data)
 
xmlHashTablePtr xmlHashCopy (xmlHashTablePtr table, xmlHashCopier f)
 
int xmlHashSize (xmlHashTablePtr table)
 
and remove

it from the hash @table. Existing userdata for this tuple will be removed and freed with @f.

Returns 0 if the removal succeeded and -1 in case of error or not found.

int xmlHashRemoveEntry (xmlHashTablePtr table, const xmlChar *name, xmlHashDeallocator f)
 
, @name2) tuple and remove

it from the hash @table. Existing userdata for this tuple will be removed and freed with @f.

Returns 0 if the removal succeeded and -1 in case of error or not found.

int xmlHashRemoveEntry2 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, xmlHashDeallocator f)
 
, @name2, @name3) tuple and remove

it from the hash @table. Existing userdata for this tuple will be removed and freed with @f.

Returns 0 if the removal succeeded and -1 in case of error or not found.

int xmlHashRemoveEntry3 (xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f)
 

Macro Definition Documentation

◆ HASH_RANDOMIZATION

#define HASH_RANDOMIZATION

Definition at line 33 of file hash.c.

◆ IN_LIBXML

#define IN_LIBXML

Definition at line 20 of file hash.c.

◆ MAX_HASH_LEN

#define MAX_HASH_LEN   8

Definition at line 42 of file hash.c.

Typedef Documentation

◆ xmlHashEntry

Definition at line 49 of file hash.c.

◆ xmlHashEntryPtr

Definition at line 50 of file hash.c.

Function Documentation

◆ stubHashScannerFull()

static void stubHashScannerFull ( void payload,
void data,
const xmlChar name,
const xmlChar *name2  ATTRIBUTE_UNUSED,
const xmlChar *name3  ATTRIBUTE_UNUSED 
)
static

Definition at line 843 of file hash.c.

845 {
846 stubData *stubdata = (stubData *) data;
847 stubdata->hashscanner (payload, stubdata->data, (xmlChar *) name);
848}
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
Definition: name.c:39
Definition: hash.c:837
xmlHashScanner hashscanner
Definition: hash.c:838
void * data
Definition: hash.c:839
unsigned char xmlChar
Definition: xmlstring.h:28

Referenced by xmlHashScan(), and xmlHashScan3().

◆ xmlHashAddEntry()

int xmlHashAddEntry ( xmlHashTablePtr  table,
const xmlChar name,
void userdata 
)

Definition at line 389 of file hash.c.

389 {
390 return(xmlHashAddEntry3(table, name, NULL, NULL, userdata));
391}
#define NULL
Definition: types.h:112
int xmlHashAddEntry3(xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, void *userdata)
Definition: hash.c:531

Referenced by xmlAddID(), xmlAddNotationDecl(), xmlAddRef(), xsltGetExtData(), xsltInitCtxtExt(), xsltInitCtxtKey(), xsltNamespaceAlias(), xsltRegisterExtModuleFull(), and xsltStyleInitializeStylesheetModule().

◆ xmlHashAddEntry2()

◆ xmlHashAddEntry3()

int xmlHashAddEntry3 ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
const xmlChar name3,
void userdata 
)

Definition at line 531 of file hash.c.

533 {
534 unsigned long key, len = 0;
537
538 if ((table == NULL) || (name == NULL))
539 return(-1);
540
541 /*
542 * If using a dict internalize if needed
543 */
544 if (table->dict) {
545 if (!xmlDictOwns(table->dict, name)) {
546 name = xmlDictLookup(table->dict, name, -1);
547 if (name == NULL)
548 return(-1);
549 }
550 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
551 name2 = xmlDictLookup(table->dict, name2, -1);
552 if (name2 == NULL)
553 return(-1);
554 }
555 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
556 name3 = xmlDictLookup(table->dict, name3, -1);
557 if (name3 == NULL)
558 return(-1);
559 }
560 }
561
562 /*
563 * Check for duplicate and insertion location.
564 */
566 if (table->table[key].valid == 0) {
567 insert = NULL;
568 } else {
569 if (table->dict) {
570 for (insert = &(table->table[key]); insert->next != NULL;
571 insert = insert->next) {
572 if ((insert->name == name) &&
573 (insert->name2 == name2) &&
574 (insert->name3 == name3))
575 return(-1);
576 len++;
577 }
578 if ((insert->name == name) &&
579 (insert->name2 == name2) &&
580 (insert->name3 == name3))
581 return(-1);
582 } else {
583 for (insert = &(table->table[key]); insert->next != NULL;
584 insert = insert->next) {
585 if ((xmlStrEqual(insert->name, name)) &&
586 (xmlStrEqual(insert->name2, name2)) &&
587 (xmlStrEqual(insert->name3, name3)))
588 return(-1);
589 len++;
590 }
591 if ((xmlStrEqual(insert->name, name)) &&
592 (xmlStrEqual(insert->name2, name2)) &&
593 (xmlStrEqual(insert->name3, name3)))
594 return(-1);
595 }
596 }
597
598 if (insert == NULL) {
599 entry = &(table->table[key]);
600 } else {
601 entry = xmlMalloc(sizeof(xmlHashEntry));
602 if (entry == NULL)
603 return(-1);
604 }
605
606 if (table->dict != NULL) {
607 entry->name = (xmlChar *) name;
608 entry->name2 = (xmlChar *) name2;
609 entry->name3 = (xmlChar *) name3;
610 } else {
611 entry->name = xmlStrdup(name);
612 entry->name2 = xmlStrdup(name2);
613 entry->name3 = xmlStrdup(name3);
614 }
615 entry->payload = userdata;
616 entry->next = NULL;
617 entry->valid = 1;
618
619
620 if (insert != NULL)
621 insert->next = entry;
622
623 table->nbElems++;
624
625 if (len > MAX_HASH_LEN)
627
628 return(0);
629}
static const WCHAR name3[]
Definition: db.c:2839
GLenum GLsizei len
Definition: glext.h:6722
uint32_t entry
Definition: isohybrid.c:63
XMLPUBFUN const xmlChar *XMLCALL xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len)
Definition: dict.c:867
XMLPUBFUN int XMLCALL xmlDictOwns(xmlDictPtr dict, const xmlChar *str)
Definition: dict.c:1220
XMLPUBVAR xmlMallocFunc xmlMalloc
Definition: globals.h:248
static int xmlHashGrow(xmlHashTablePtr table, int size)
Definition: hash.c:231
#define MAX_HASH_LEN
Definition: hash.c:42
static unsigned long xmlHashComputeKey(xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3)
Definition: hash.c:81
Definition: copy.c:22
static int insert
Definition: xmllint.c:138
XMLPUBFUN xmlChar *XMLCALL xmlStrdup(const xmlChar *cur)
Definition: xmlstring.c:67
XMLPUBFUN int XMLCALL xmlStrEqual(const xmlChar *str1, const xmlChar *str2)
Definition: xmlstring.c:160

Referenced by xmlAddAttributeDecl(), xmlHashAddEntry(), xmlHashAddEntry2(), xmlHashCopy(), and xsltAddTemplate().

◆ xmlHashComputeKey()

static unsigned long xmlHashComputeKey ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
const xmlChar name3 
)
static

Definition at line 81 of file hash.c.

82 {
83 unsigned long value = 0L;
84 unsigned long ch;
85
86#ifdef HASH_RANDOMIZATION
87 value = table->random_seed;
88#endif
89 if (name != NULL) {
90 value += 30 * (*name);
91 while ((ch = *name++) != 0) {
92 value = value ^ ((value << 5) + (value >> 3) + ch);
93 }
94 }
95 value = value ^ ((value << 5) + (value >> 3));
96 if (name2 != NULL) {
97 while ((ch = *name2++) != 0) {
98 value = value ^ ((value << 5) + (value >> 3) + ch);
99 }
100 }
101 value = value ^ ((value << 5) + (value >> 3));
102 if (name3 != NULL) {
103 while ((ch = *name3++) != 0) {
104 value = value ^ ((value << 5) + (value >> 3) + ch);
105 }
106 }
107 return (value % table->size);
108}
#define L(x)
Definition: ntvdm.h:50
Definition: pdh_main.c:94

Referenced by xmlHashAddEntry3(), xmlHashGrow(), xmlHashLookup3(), xmlHashRemoveEntry3(), and xmlHashUpdateEntry3().

◆ xmlHashComputeQKey()

static unsigned long xmlHashComputeQKey ( xmlHashTablePtr  table,
const xmlChar prefix,
const xmlChar name,
const xmlChar prefix2,
const xmlChar name2,
const xmlChar prefix3,
const xmlChar name3 
)
static

Definition at line 114 of file hash.c.

117 {
118 unsigned long value = 0L;
119 unsigned long ch;
120
121#ifdef HASH_RANDOMIZATION
122 value = table->random_seed;
123#endif
124 if (prefix != NULL)
125 value += 30 * (*prefix);
126 else
127 value += 30 * (*name);
128
129 if (prefix != NULL) {
130 while ((ch = *prefix++) != 0) {
131 value = value ^ ((value << 5) + (value >> 3) + ch);
132 }
133 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
134 }
135 if (name != NULL) {
136 while ((ch = *name++) != 0) {
137 value = value ^ ((value << 5) + (value >> 3) + ch);
138 }
139 }
140 value = value ^ ((value << 5) + (value >> 3));
141 if (prefix2 != NULL) {
142 while ((ch = *prefix2++) != 0) {
143 value = value ^ ((value << 5) + (value >> 3) + ch);
144 }
145 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
146 }
147 if (name2 != NULL) {
148 while ((ch = *name2++) != 0) {
149 value = value ^ ((value << 5) + (value >> 3) + ch);
150 }
151 }
152 value = value ^ ((value << 5) + (value >> 3));
153 if (prefix3 != NULL) {
154 while ((ch = *prefix3++) != 0) {
155 value = value ^ ((value << 5) + (value >> 3) + ch);
156 }
157 value = value ^ ((value << 5) + (value >> 3) + (unsigned long)':');
158 }
159 if (name3 != NULL) {
160 while ((ch = *name3++) != 0) {
161 value = value ^ ((value << 5) + (value >> 3) + ch);
162 }
163 }
164 return (value % table->size);
165}
#define long
Definition: qsort.c:33

Referenced by xmlHashQLookup3().

◆ xmlHashCopy()

xmlHashTablePtr xmlHashCopy ( xmlHashTablePtr  table,
xmlHashCopier  f 
)

xmlHashCopy: @table: the hash table @f: the copier function for items in the hash

Scan the hash @table and applied @f to each value.

Returns the new table or NULL in case of error.

Definition at line 992 of file hash.c.

992 {
993 int i;
994 xmlHashEntryPtr iter;
997
998 if (table == NULL)
999 return(NULL);
1000 if (f == NULL)
1001 return(NULL);
1002
1003 ret = xmlHashCreate(table->size);
1004 if (ret == NULL)
1005 return(NULL);
1006
1007 if (table->table) {
1008 for(i = 0; i < table->size; i++) {
1009 if (table->table[i].valid == 0)
1010 continue;
1011 iter = &(table->table[i]);
1012 while (iter) {
1013 next = iter->next;
1014 xmlHashAddEntry3(ret, iter->name, iter->name2,
1015 iter->name3, f(iter->payload, iter->name));
1016 iter = next;
1017 }
1018 }
1019 }
1020 ret->nbElems = table->nbElems;
1021 return(ret);
1022}
GLfloat f
Definition: glext.h:7540
GLsizei GLenum const GLvoid GLsizei GLenum GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLint GLint GLint GLshort GLshort GLshort GLubyte GLubyte GLubyte GLuint GLuint GLuint GLushort GLushort GLushort GLbyte GLbyte GLbyte GLbyte GLdouble GLdouble GLdouble GLdouble GLfloat GLfloat GLfloat GLfloat GLint GLint GLint GLint GLshort GLshort GLshort GLshort GLubyte GLubyte GLubyte GLubyte GLuint GLuint GLuint GLuint GLushort GLushort GLushort GLushort GLboolean const GLdouble const GLfloat const GLint const GLshort const GLbyte const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLdouble const GLfloat const GLfloat const GLint const GLint const GLshort const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort const GLdouble const GLfloat const GLint const GLshort GLenum GLenum GLenum GLfloat GLenum GLint GLenum GLenum GLenum GLfloat GLenum GLenum GLint GLenum GLfloat GLenum GLint GLint GLushort GLenum GLenum GLfloat GLenum GLenum GLint GLfloat const GLubyte GLenum GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLint GLint GLsizei GLsizei GLint GLenum GLenum const GLvoid GLenum GLenum const GLfloat GLenum GLenum const GLint GLenum GLenum const GLdouble GLenum GLenum const GLfloat GLenum GLenum const GLint GLsizei GLuint GLfloat GLuint GLbitfield GLfloat GLint GLuint GLboolean GLenum GLfloat GLenum GLbitfield GLenum GLfloat GLfloat GLint GLint const GLfloat GLenum GLfloat GLfloat GLint GLint GLfloat GLfloat GLint GLint const GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat GLint GLfloat GLfloat const GLdouble const GLfloat const GLdouble const GLfloat GLint i
Definition: glfuncs.h:248
static unsigned __int64 next
Definition: rand_nt.c:6
xmlHashTablePtr xmlHashCreate(int size)
Definition: hash.c:176
xmlChar * name2
Definition: hash.c:54
xmlChar * name
Definition: hash.c:53
struct _xmlHashEntry * next
Definition: hash.c:52
void * payload
Definition: hash.c:56
xmlChar * name3
Definition: hash.c:55
int ret

◆ xmlHashCreate()

xmlHashTablePtr xmlHashCreate ( int  size)

xmlHashCreate: @size: the size of the hash table

Create a new xmlHashTablePtr.

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

Definition at line 176 of file hash.c.

176 {
178
179 if (size <= 0)
180 size = 256;
181
182 table = xmlMalloc(sizeof(xmlHashTable));
183 if (table) {
184 table->dict = NULL;
185 table->size = size;
186 table->nbElems = 0;
187 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
188 if (table->table) {
189 memset(table->table, 0, size * sizeof(xmlHashEntry));
190#ifdef HASH_RANDOMIZATION
191 table->random_seed = __xmlRandom();
192#endif
193 return(table);
194 }
195 xmlFree(table);
196 }
197 return(NULL);
198}
GLsizeiptr size
Definition: glext.h:5919
XMLPUBVAR xmlFreeFunc xmlFree
Definition: globals.h:251
int __xmlRandom(void)
Definition: dict.c:195
#define memset(x, y, z)
Definition: compat.h:39

Referenced by xmlHashCopy(), xmlHashCreateDict(), xsltAddTemplate(), xsltApplyStylesheetInternal(), xsltDocumentElem(), xsltGatherNamespaces(), xsltGetExtData(), xsltInitCtxtExt(), xsltNamespaceAlias(), xsltNewKeyTable(), xsltParseStylesheetAttributeSet(), xsltParseStylesheetOutput(), xsltParseStylesheetPreserveSpace(), xsltParseStylesheetStripSpace(), xsltProcessUserParamInternal(), xsltRegisterExtElement(), xsltRegisterExtFunction(), xsltRegisterExtModuleElement(), xsltRegisterExtModuleFull(), xsltRegisterExtModuleFunction(), xsltRegisterExtModuleTopLevel(), xsltResolveStylesheetAttributeSet(), and xsltStyleInitializeStylesheetModule().

◆ xmlHashCreateDict()

xmlHashTablePtr xmlHashCreateDict ( int  size,
xmlDictPtr  dict 
)

xmlHashCreateDict: @size: the size of the hash table @dict: a dictionary to use for the hash

Create a new xmlHashTablePtr which will use @dict as the internal dictionary

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

Definition at line 210 of file hash.c.

210 {
212
214 if (table != NULL) {
215 table->dict = dict;
216 xmlDictReference(dict);
217 }
218 return(table);
219}
XMLPUBFUN int XMLCALL xmlDictReference(xmlDictPtr dict)
Definition: dict.c:647

Referenced by xmlAddAttributeDecl(), xmlAddDefAttrs(), xmlAddElementDecl(), xmlAddID(), xmlAddNotationDecl(), xmlAddRef(), xmlAddSpecialAttr(), and xmlGetDtdElementDesc2().

◆ xmlHashDefaultDeallocator()

void xmlHashDefaultDeallocator ( void entry,
const xmlChar *name  ATTRIBUTE_UNUSED 
)

Definition at line 373 of file hash.c.

373 {
374 xmlFree(entry);
375}

◆ xmlHashFree()

void xmlHashFree ( xmlHashTablePtr  table,
xmlHashDeallocator  f 
)

xmlHashFree: @table: the hash table @f: the deallocator function for items in the hash

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

Definition at line 322 of file hash.c.

322 {
323 int i;
324 xmlHashEntryPtr iter;
326 int inside_table = 0;
327 int nbElems;
328
329 if (table == NULL)
330 return;
331 if (table->table) {
332 nbElems = table->nbElems;
333 for(i = 0; (i < table->size) && (nbElems > 0); i++) {
334 iter = &(table->table[i]);
335 if (iter->valid == 0)
336 continue;
337 inside_table = 1;
338 while (iter) {
339 next = iter->next;
340 if ((f != NULL) && (iter->payload != NULL))
341 f(iter->payload, iter->name);
342 if (table->dict == NULL) {
343 if (iter->name)
344 xmlFree(iter->name);
345 if (iter->name2)
346 xmlFree(iter->name2);
347 if (iter->name3)
348 xmlFree(iter->name3);
349 }
350 iter->payload = NULL;
351 if (!inside_table)
352 xmlFree(iter);
353 nbElems--;
354 inside_table = 0;
355 iter = next;
356 }
357 }
358 xmlFree(table->table);
359 }
360 if (table->dict)
361 xmlDictFree(table->dict);
362 xmlFree(table);
363}
#define f
Definition: ke_i.h:83
XMLPUBFUN void XMLCALL xmlDictFree(xmlDictPtr dict)
Definition: dict.c:802
int valid
Definition: hash.c:57

Referenced by xmlCleanSpecialAttr(), xmlCtxtReset(), xmlFreeAttributeTable(), xmlFreeElementTable(), xmlFreeIDTable(), xmlFreeNotationTable(), xmlFreeParserCtxt(), xmlFreeRefTable(), xsltCleanupGlobals(), xsltFreeAttributeSetsHashes(), xsltFreeCtxtExts(), xsltFreeGlobalVariables(), xsltFreeKeyTable(), xsltFreeNamespaceAliasHashes(), xsltFreeStylesheet(), xsltFreeTemplateHashes(), xsltResolveStylesheetAttributeSet(), xsltShutdownCtxtExts(), xsltShutdownExts(), xsltUnregisterAllExtModuleElement(), xsltUnregisterAllExtModuleFunction(), xsltUnregisterAllExtModules(), and xsltUnregisterAllExtModuleTopLevel().

◆ xmlHashGrow()

static int xmlHashGrow ( xmlHashTablePtr  table,
int  size 
)
static

xmlHashGrow: @table: the hash table @size: the new size of the hash table

resize the hash table

Returns 0 in case of success, -1 in case of failure

Definition at line 231 of file hash.c.

231 {
232 unsigned long key;
233 int oldsize, i;
234 xmlHashEntryPtr iter, next;
235 struct _xmlHashEntry *oldtable;
236#ifdef DEBUG_GROW
237 unsigned long nbElem = 0;
238#endif
239
240 if (table == NULL)
241 return(-1);
242 if (size < 8)
243 return(-1);
244 if (size > 8 * 2048)
245 return(-1);
246
247 oldsize = table->size;
248 oldtable = table->table;
249 if (oldtable == NULL)
250 return(-1);
251
252 table->table = xmlMalloc(size * sizeof(xmlHashEntry));
253 if (table->table == NULL) {
254 table->table = oldtable;
255 return(-1);
256 }
257 memset(table->table, 0, size * sizeof(xmlHashEntry));
258 table->size = size;
259
260 /* If the two loops are merged, there would be situations where
261 a new entry needs to allocated and data copied into it from
262 the main table. So instead, we run through the array twice, first
263 copying all the elements in the main array (where we can't get
264 conflicts) and then the rest, so we only free (and don't allocate)
265 */
266 for (i = 0; i < oldsize; i++) {
267 if (oldtable[i].valid == 0)
268 continue;
269 key = xmlHashComputeKey(table, oldtable[i].name, oldtable[i].name2,
270 oldtable[i].name3);
271 memcpy(&(table->table[key]), &(oldtable[i]), sizeof(xmlHashEntry));
272 table->table[key].next = NULL;
273 }
274
275 for (i = 0; i < oldsize; i++) {
276 iter = oldtable[i].next;
277 while (iter) {
278 next = iter->next;
279
280 /*
281 * put back the entry in the new table
282 */
283
284 key = xmlHashComputeKey(table, iter->name, iter->name2,
285 iter->name3);
286 if (table->table[key].valid == 0) {
287 memcpy(&(table->table[key]), iter, sizeof(xmlHashEntry));
288 table->table[key].next = NULL;
289 xmlFree(iter);
290 } else {
291 iter->next = table->table[key].next;
292 table->table[key].next = iter;
293 }
294
295#ifdef DEBUG_GROW
296 nbElem++;
297#endif
298
299 iter = next;
300 }
301 }
302
303 xmlFree(oldtable);
304
305#ifdef DEBUG_GROW
307 "xmlHashGrow : from %d to %d, %d elems\n", oldsize, size, nbElem);
308#endif
309
310 return(0);
311}
BOOLEAN valid
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:353
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:337

Referenced by xmlHashAddEntry3().

◆ xmlHashLookup()

◆ xmlHashLookup2()

◆ xmlHashLookup3()

void * xmlHashLookup3 ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
const xmlChar name3 
)

Definition at line 769 of file hash.c.

770 {
771 unsigned long key;
773
774 if (table == NULL)
775 return(NULL);
776 if (name == NULL)
777 return(NULL);
779 if (table->table[key].valid == 0)
780 return(NULL);
781 if (table->dict) {
782 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
783 if ((entry->name == name) &&
784 (entry->name2 == name2) &&
785 (entry->name3 == name3))
786 return(entry->payload);
787 }
788 }
789 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
790 if ((xmlStrEqual(entry->name, name)) &&
791 (xmlStrEqual(entry->name2, name2)) &&
792 (xmlStrEqual(entry->name3, name3)))
793 return(entry->payload);
794 }
795 return(NULL);
796}

Referenced by xmlAddAttributeDecl(), xmlGetDtdAttrDesc(), xmlGetDtdQAttrDesc(), xmlHashLookup(), xmlHashLookup2(), xsltAddTemplate(), and xsltGetTemplate().

◆ xmlHashQLookup()

void * xmlHashQLookup ( xmlHashTablePtr  table,
const xmlChar prefix,
const xmlChar name 
)

Definition at line 492 of file hash.c.

493 {
494 return(xmlHashQLookup3(table, prefix, name, NULL, NULL, NULL, NULL));
495}
void * xmlHashQLookup3(xmlHashTablePtr table, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3)
Definition: hash.c:813

◆ xmlHashQLookup2()

void * xmlHashQLookup2 ( xmlHashTablePtr  table,
const xmlChar prefix,
const xmlChar name,
const xmlChar prefix2,
const xmlChar name2 
)

Definition at line 510 of file hash.c.

512 {
513 return(xmlHashQLookup3(table, prefix, name, prefix2, name2, NULL, NULL));
514}

Referenced by xmlParseAttribute2().

◆ xmlHashQLookup3()

void * xmlHashQLookup3 ( xmlHashTablePtr  table,
const xmlChar prefix,
const xmlChar name,
const xmlChar prefix2,
const xmlChar name2,
const xmlChar prefix3,
const xmlChar name3 
)

Definition at line 813 of file hash.c.

816 {
817 unsigned long key;
819
820 if (table == NULL)
821 return(NULL);
822 if (name == NULL)
823 return(NULL);
824 key = xmlHashComputeQKey(table, prefix, name, prefix2,
825 name2, prefix3, name3);
826 if (table->table[key].valid == 0)
827 return(NULL);
828 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
829 if ((xmlStrQEqual(prefix, name, entry->name)) &&
830 (xmlStrQEqual(prefix2, name2, entry->name2)) &&
831 (xmlStrQEqual(prefix3, name3, entry->name3)))
832 return(entry->payload);
833 }
834 return(NULL);
835}
static unsigned long xmlHashComputeQKey(xmlHashTablePtr table, const xmlChar *prefix, const xmlChar *name, const xmlChar *prefix2, const xmlChar *name2, const xmlChar *prefix3, const xmlChar *name3)
Definition: hash.c:114
XMLPUBFUN int XMLCALL xmlStrQEqual(const xmlChar *pref, const xmlChar *name, const xmlChar *str)
Definition: xmlstring.c:186

Referenced by xmlHashQLookup(), and xmlHashQLookup2().

◆ xmlHashRemoveEntry()

int xmlHashRemoveEntry ( xmlHashTablePtr  table,
const xmlChar name,
xmlHashDeallocator  f 
)

Definition at line 1052 of file hash.c.

1053 {
1054 return(xmlHashRemoveEntry3(table, name, NULL, NULL, f));
1055}
int xmlHashRemoveEntry3(xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, xmlHashDeallocator f)
Definition: hash.c:1091

Referenced by xmlRemoveID(), and xsltUnregisterExtModule().

◆ xmlHashRemoveEntry2()

◆ xmlHashRemoveEntry3()

int xmlHashRemoveEntry3 ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
const xmlChar name3,
xmlHashDeallocator  f 
)

Definition at line 1091 of file hash.c.

1092 {
1093 unsigned long key;
1095 xmlHashEntryPtr prev = NULL;
1096
1097 if (table == NULL || name == NULL)
1098 return(-1);
1099
1101 if (table->table[key].valid == 0) {
1102 return(-1);
1103 } else {
1104 for (entry = &(table->table[key]); entry != NULL; entry = entry->next) {
1105 if (xmlStrEqual(entry->name, name) &&
1106 xmlStrEqual(entry->name2, name2) &&
1107 xmlStrEqual(entry->name3, name3)) {
1108 if ((f != NULL) && (entry->payload != NULL))
1109 f(entry->payload, entry->name);
1110 entry->payload = NULL;
1111 if (table->dict == NULL) {
1112 if(entry->name)
1113 xmlFree(entry->name);
1114 if(entry->name2)
1115 xmlFree(entry->name2);
1116 if(entry->name3)
1117 xmlFree(entry->name3);
1118 }
1119 if(prev) {
1120 prev->next = entry->next;
1121 xmlFree(entry);
1122 } else {
1123 if (entry->next == NULL) {
1124 entry->valid = 0;
1125 } else {
1126 entry = entry->next;
1127 memcpy(&(table->table[key]), entry, sizeof(xmlHashEntry));
1128 xmlFree(entry);
1129 }
1130 }
1131 table->nbElems--;
1132 return(0);
1133 }
1134 prev = entry;
1135 }
1136 return(-1);
1137 }
1138}

Referenced by xmlHashRemoveEntry(), and xmlHashRemoveEntry2().

◆ xmlHashScan()

void xmlHashScan ( xmlHashTablePtr  table,
xmlHashScanner  f,
void data 
)

xmlHashScan: @table: the hash table @f: the scanner function for items in the hash @data: extra data passed to f

Scan the hash @table and applied @f to each value.

Definition at line 859 of file hash.c.

859 {
860 stubData stubdata;
861 stubdata.data = data;
862 stubdata.hashscanner = f;
864}
static void stubHashScannerFull(void *payload, void *data, const xmlChar *name, const xmlChar *name2 ATTRIBUTE_UNUSED, const xmlChar *name3 ATTRIBUTE_UNUSED)
Definition: hash.c:843
void xmlHashScanFull(xmlHashTablePtr table, xmlHashScannerFull f, void *data)
Definition: hash.c:875

Referenced by xsltCleanupGlobals(), xsltEvalGlobalVariables(), xsltFixImportedCompSteps(), xsltInitCtxtExts(), xsltShutdownCtxtExts(), and xsltShutdownExts().

◆ xmlHashScan3()

void xmlHashScan3 ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
const xmlChar name3,
xmlHashScanner  f,
void data 
)

Definition at line 926 of file hash.c.

928 {
929 stubData stubdata;
930 stubdata.data = data;
931 stubdata.hashscanner = f;
933 &stubdata);
934}
void xmlHashScanFull3(xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, xmlHashScannerFull f, void *data)
Definition: hash.c:950

◆ xmlHashScanFull()

void xmlHashScanFull ( xmlHashTablePtr  table,
xmlHashScannerFull  f,
void data 
)

xmlHashScanFull: @table: the hash table @f: the scanner function for items in the hash @data: extra data passed to f

Scan the hash @table and applied @f to each value.

Definition at line 875 of file hash.c.

875 {
876 int i, nb;
877 xmlHashEntryPtr iter;
879
880 if (table == NULL)
881 return;
882 if (f == NULL)
883 return;
884
885 if (table->table) {
886 for(i = 0; i < table->size; i++) {
887 if (table->table[i].valid == 0)
888 continue;
889 iter = &(table->table[i]);
890 while (iter) {
891 next = iter->next;
892 nb = table->nbElems;
893 if ((f != NULL) && (iter->payload != NULL))
894 f(iter->payload, data, iter->name,
895 iter->name2, iter->name3);
896 if (nb != table->nbElems) {
897 /* table was modified by the callback, be careful */
898 if (iter == &(table->table[i])) {
899 if (table->table[i].valid == 0)
900 iter = NULL;
901 if (table->table[i].next != next)
902 iter = &(table->table[i]);
903 } else
904 iter = next;
905 } else
906 iter = next;
907 }
908 }
909 }
910}

Referenced by xmlCleanSpecialAttr(), xmlHashScan(), xsltDebugDumpExtensions(), and xsltResolveStylesheetAttributeSet().

◆ xmlHashScanFull3()

void xmlHashScanFull3 ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
const xmlChar name3,
xmlHashScannerFull  f,
void data 
)

Definition at line 950 of file hash.c.

952 {
953 int i;
954 xmlHashEntryPtr iter;
956
957 if (table == NULL)
958 return;
959 if (f == NULL)
960 return;
961
962 if (table->table) {
963 for(i = 0; i < table->size; i++) {
964 if (table->table[i].valid == 0)
965 continue;
966 iter = &(table->table[i]);
967 while (iter) {
968 next = iter->next;
969 if (((name == NULL) || (xmlStrEqual(name, iter->name))) &&
970 ((name2 == NULL) || (xmlStrEqual(name2, iter->name2))) &&
971 ((name3 == NULL) || (xmlStrEqual(name3, iter->name3))) &&
972 (iter->payload != NULL)) {
973 f(iter->payload, data, iter->name,
974 iter->name2, iter->name3);
975 }
976 iter = next;
977 }
978 }
979 }
980}

Referenced by xmlHashScan3().

◆ xmlHashSize()

int xmlHashSize ( xmlHashTablePtr  table)

xmlHashSize: @table: the hash table

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

Returns the number of elements in the hash table or -1 in case of error

Definition at line 1034 of file hash.c.

1034 {
1035 if (table == NULL)
1036 return(-1);
1037 return(table->nbElems);
1038}

Referenced by xmlCleanSpecialAttr().

◆ xmlHashUpdateEntry()

int xmlHashUpdateEntry ( xmlHashTablePtr  table,
const xmlChar name,
void userdata,
xmlHashDeallocator  f 
)

Definition at line 425 of file hash.c.

426 {
427 return(xmlHashUpdateEntry3(table, name, NULL, NULL, userdata, f));
428}
int xmlHashUpdateEntry3(xmlHashTablePtr table, const xmlChar *name, const xmlChar *name2, const xmlChar *name3, void *userdata, xmlHashDeallocator f)
Definition: hash.c:647

Referenced by xmlRemoveRef(), and xsltGatherNamespaces().

◆ xmlHashUpdateEntry2()

int xmlHashUpdateEntry2 ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
void userdata,
xmlHashDeallocator  f 
)

◆ xmlHashUpdateEntry3()

int xmlHashUpdateEntry3 ( xmlHashTablePtr  table,
const xmlChar name,
const xmlChar name2,
const xmlChar name3,
void userdata,
xmlHashDeallocator  f 
)

Definition at line 647 of file hash.c.

649 {
650 unsigned long key;
653
654 if ((table == NULL) || name == NULL)
655 return(-1);
656
657 /*
658 * If using a dict internalize if needed
659 */
660 if (table->dict) {
661 if (!xmlDictOwns(table->dict, name)) {
662 name = xmlDictLookup(table->dict, name, -1);
663 if (name == NULL)
664 return(-1);
665 }
666 if ((name2 != NULL) && (!xmlDictOwns(table->dict, name2))) {
667 name2 = xmlDictLookup(table->dict, name2, -1);
668 if (name2 == NULL)
669 return(-1);
670 }
671 if ((name3 != NULL) && (!xmlDictOwns(table->dict, name3))) {
672 name3 = xmlDictLookup(table->dict, name3, -1);
673 if (name3 == NULL)
674 return(-1);
675 }
676 }
677
678 /*
679 * Check for duplicate and insertion location.
680 */
682 if (table->table[key].valid == 0) {
683 insert = NULL;
684 } else {
685 if (table ->dict) {
686 for (insert = &(table->table[key]); insert->next != NULL;
687 insert = insert->next) {
688 if ((insert->name == name) &&
689 (insert->name2 == name2) &&
690 (insert->name3 == name3)) {
691 if (f)
692 f(insert->payload, insert->name);
693 insert->payload = userdata;
694 return(0);
695 }
696 }
697 if ((insert->name == name) &&
698 (insert->name2 == name2) &&
699 (insert->name3 == name3)) {
700 if (f)
701 f(insert->payload, insert->name);
702 insert->payload = userdata;
703 return(0);
704 }
705 } else {
706 for (insert = &(table->table[key]); insert->next != NULL;
707 insert = insert->next) {
708 if ((xmlStrEqual(insert->name, name)) &&
709 (xmlStrEqual(insert->name2, name2)) &&
710 (xmlStrEqual(insert->name3, name3))) {
711 if (f)
712 f(insert->payload, insert->name);
713 insert->payload = userdata;
714 return(0);
715 }
716 }
717 if ((xmlStrEqual(insert->name, name)) &&
718 (xmlStrEqual(insert->name2, name2)) &&
719 (xmlStrEqual(insert->name3, name3))) {
720 if (f)
721 f(insert->payload, insert->name);
722 insert->payload = userdata;
723 return(0);
724 }
725 }
726 }
727
728 if (insert == NULL) {
729 entry = &(table->table[key]);
730 } else {
731 entry = xmlMalloc(sizeof(xmlHashEntry));
732 if (entry == NULL)
733 return(-1);
734 }
735
736 if (table->dict != NULL) {
737 entry->name = (xmlChar *) name;
738 entry->name2 = (xmlChar *) name2;
739 entry->name3 = (xmlChar *) name3;
740 } else {
741 entry->name = xmlStrdup(name);
742 entry->name2 = xmlStrdup(name2);
743 entry->name3 = xmlStrdup(name3);
744 }
745 entry->payload = userdata;
746 entry->next = NULL;
747 entry->valid = 1;
748 table->nbElems++;
749
750
751 if (insert != NULL) {
752 insert->next = entry;
753 }
754 return(0);
755}

Referenced by xmlHashUpdateEntry(), xmlHashUpdateEntry2(), and xsltAddTemplate().