ReactOS 0.4.15-dev-7842-g558ab78
dict.c File Reference
#include "libxml.h"
#include <limits.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#include <stdint.h>
#include <libxml/tree.h>
#include <libxml/dict.h>
#include <libxml/xmlmemory.h>
#include <libxml/xmlerror.h>
#include <libxml/globals.h>
Include dependency graph for dict.c:

Go to the source code of this file.

Classes

struct  _xmlDictEntry
 
struct  _xmlDictStrings
 
struct  _xmlDict
 

Macros

#define IN_LIBXML
 
#define DICT_RANDOMIZATION
 
#define MAX_HASH_LEN   3
 
#define MIN_DICT_SIZE   128
 
#define MAX_DICT_HASH   8 * 2048
 
#define WITH_BIG_KEY
 
#define xmlDictComputeKey(dict, name, len)
 
#define xmlDictComputeQKey(dict, prefix, plen, name, len)
 

Typedefs

typedef struct _xmlDictEntry xmlDictEntry
 
typedef xmlDictEntryxmlDictEntryPtr
 
typedef struct _xmlDictStrings xmlDictStrings
 
typedef xmlDictStringsxmlDictStringsPtr
 

Functions

int xmlInitializeDict (void)
 
int __xmlInitializeDict (void)
 
int __xmlRandom (void)
 
void xmlDictCleanup (void)
 
static const xmlCharxmlDictAddString (xmlDictPtr dict, const xmlChar *name, unsigned int namelen)
 
static const xmlCharxmlDictAddQString (xmlDictPtr dict, const xmlChar *prefix, unsigned int plen, const xmlChar *name, unsigned int namelen)
 
static uint32_t xmlDictComputeBigKey (const xmlChar *data, int namelen, int seed)
 
static unsigned long xmlDictComputeBigQKey (const xmlChar *prefix, int plen, const xmlChar *name, int len, int seed)
 
static unsigned long xmlDictComputeFastKey (const xmlChar *name, int namelen, int seed)
 
static unsigned long xmlDictComputeFastQKey (const xmlChar *prefix, int plen, const xmlChar *name, int len, int seed)
 
xmlDictPtr xmlDictCreate (void)
 
xmlDictPtr xmlDictCreateSub (xmlDictPtr sub)
 
int xmlDictReference (xmlDictPtr dict)
 
static int xmlDictGrow (xmlDictPtr dict, size_t size)
 
void xmlDictFree (xmlDictPtr dict)
 
to the dictionary @dict if not present.

Returns the internal copy of the name or NULL in case of internal error

const xmlCharxmlDictLookup (xmlDictPtr dict, const xmlChar *name, int len)
 
exists in the dictionary @dict.

Returns the internal copy of the name or NULL if not found.

const xmlCharxmlDictExists (xmlDictPtr dict, const xmlChar *name, int len)
 
to the hash @dict if not present.

Returns the internal copy of the QName or NULL in case of internal error

const xmlCharxmlDictQLookup (xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name)
 
int xmlDictOwns (xmlDictPtr dict, const xmlChar *str)
 
int xmlDictSize (xmlDictPtr dict)
 
size_t xmlDictSetLimit (xmlDictPtr dict, size_t limit)
 
size_t xmlDictGetUsage (xmlDictPtr dict)
 

Variables

static xmlMutexPtr xmlDictMutex = NULL
 
static int xmlDictInitialized = 0
 

Macro Definition Documentation

◆ DICT_RANDOMIZATION

#define DICT_RANDOMIZATION

Definition at line 38 of file dict.c.

◆ IN_LIBXML

#define IN_LIBXML

Definition at line 19 of file dict.c.

◆ MAX_DICT_HASH

#define MAX_DICT_HASH   8 * 2048

Definition at line 62 of file dict.c.

◆ MAX_HASH_LEN

#define MAX_HASH_LEN   3

Definition at line 60 of file dict.c.

◆ MIN_DICT_SIZE

#define MIN_DICT_SIZE   128

Definition at line 61 of file dict.c.

◆ WITH_BIG_KEY

#define WITH_BIG_KEY

Definition at line 63 of file dict.c.

◆ xmlDictComputeKey

#define xmlDictComputeKey (   dict,
  name,
  len 
)
Value:
(((dict)->size == MIN_DICT_SIZE) ? \
xmlDictComputeFastKey(name, len, (dict)->seed) : \
xmlDictComputeBigKey(name, len, (dict)->seed))
GLsizeiptr size
Definition: glext.h:5919
GLenum GLsizei len
Definition: glext.h:6722
#define MIN_DICT_SIZE
Definition: dict.c:61
static uint32_t xmlDictComputeBigKey(const xmlChar *data, int namelen, int seed)
Definition: dict.c:381
Definition: name.c:39

Definition at line 66 of file dict.c.

◆ xmlDictComputeQKey

#define xmlDictComputeQKey (   dict,
  prefix,
  plen,
  name,
  len 
)
Value:
(((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)))
#define NULL
Definition: types.h:112
#define xmlDictComputeKey(dict, name, len)
Definition: dict.c:66
static unsigned long xmlDictComputeBigQKey(const xmlChar *prefix, int plen, const xmlChar *name, int len, int seed)
Definition: dict.c:416

Definition at line 71 of file dict.c.

Typedef Documentation

◆ xmlDictEntry

Definition at line 88 of file dict.c.

◆ xmlDictEntryPtr

Definition at line 89 of file dict.c.

◆ xmlDictStrings

Definition at line 98 of file dict.c.

◆ xmlDictStringsPtr

Definition at line 99 of file dict.c.

Function Documentation

◆ __xmlInitializeDict()

int __xmlInitializeDict ( void  )

__xmlInitializeDict:

This function is not public Do the dictionary mutex initialization. this function is not thread safe, initialization should 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

Definition at line 173 of file dict.c.

173 {
175 return(1);
176
177 if ((xmlDictMutex = xmlNewMutex()) == NULL)
178 return(0);
180
181#ifdef DICT_RANDOMIZATION
182#ifdef HAVE_RAND_R
183 rand_seed = time(NULL);
184 rand_r(& rand_seed);
185#else
186 srand(time(NULL));
187#endif
188#endif
191 return(1);
192}
void __cdecl srand(_In_ unsigned int _Seed)
__u16 time
Definition: mkdosfs.c:8
static xmlMutexPtr xmlDictMutex
Definition: dict.c:130
static int xmlDictInitialized
Definition: dict.c:135
XMLPUBFUN void XMLCALL xmlMutexUnlock(xmlMutexPtr tok)
Definition: threads.c:248
XMLPUBFUN xmlMutexPtr XMLCALL xmlNewMutex(void)
Definition: threads.c:168
XMLPUBFUN void XMLCALL xmlMutexLock(xmlMutexPtr tok)
Definition: threads.c:220

Referenced by __xmlRandom(), xmlDictCreate(), xmlDictFree(), and xmlDictReference().

◆ __xmlRandom()

int __xmlRandom ( void  )

Definition at line 195 of file dict.c.

195 {
196 int ret;
197
198 if (xmlDictInitialized == 0)
200
202#ifdef HAVE_RAND_R
203 ret = rand_r(& rand_seed);
204#else
205 ret = rand();
206#endif
208 return(ret);
209}
_Check_return_ int __cdecl rand(void)
Definition: rand.c:10
int __xmlInitializeDict(void)
Definition: dict.c:173
int ret

Referenced by xmlDictCreate(), and xmlHashCreate().

◆ xmlDictAddQString()

static const xmlChar * xmlDictAddQString ( xmlDictPtr  dict,
const xmlChar prefix,
unsigned int  plen,
const xmlChar name,
unsigned int  namelen 
)
static

Definition at line 308 of file dict.c.

310{
312 const xmlChar *ret;
313 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
314 size_t limit = 0;
315
316 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
317
318#ifdef DICT_DEBUG_PATTERNS
319 fprintf(stderr, "=");
320#endif
321 pool = dict->strings;
322 while (pool != NULL) {
323 if ((size_t)(pool->end - pool->free) > namelen + plen + 1)
324 goto found_pool;
325 if (pool->size > size) size = pool->size;
326 limit += pool->size;
327 pool = pool->next;
328 }
329 /*
330 * Not found, need to allocate
331 */
332 if (pool == NULL) {
333 if ((dict->limit > 0) && (limit > dict->limit)) {
334 return(NULL);
335 }
336
337 if (size == 0) size = 1000;
338 else size *= 4; /* exponential growth */
339 if (size < 4 * (namelen + plen + 1))
340 size = 4 * (namelen + plen + 1); /* just in case ! */
342 if (pool == NULL)
343 return(NULL);
344 pool->size = size;
345 pool->nbStrings = 0;
346 pool->free = &pool->array[0];
347 pool->end = &pool->array[size];
348 pool->next = dict->strings;
349 dict->strings = pool;
350#ifdef DICT_DEBUG_PATTERNS
351 fprintf(stderr, "+");
352#endif
353 }
354found_pool:
355 ret = pool->free;
356 memcpy(pool->free, prefix, plen);
357 pool->free += plen;
358 *(pool->free++) = ':';
359 memcpy(pool->free, name, namelen);
360 pool->free += namelen;
361 *(pool->free++) = 0;
362 pool->nbStrings++;
363 return(ret);
364}
GLint namelen
Definition: glext.h:7232
GLint limit
Definition: glext.h:10326
#define stderr
Definition: stdio.h:100
_Check_return_opt_ _CRTIMP int __cdecl fprintf(_Inout_ FILE *_File, _In_z_ _Printf_format_string_ const char *_Format,...)
#define memcpy(s1, s2, n)
Definition: mkisofs.h:878
XMLPUBVAR xmlMallocFunc xmlMalloc
Definition: globals.h:248
xmlDictStrings * xmlDictStringsPtr
Definition: dict.c:99
static const xmlChar * xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen)
Definition: dict.c:244
size_t limit
Definition: dict.c:123
xmlDictStringsPtr strings
Definition: dict.c:117
unsigned char xmlChar
Definition: xmlstring.h:28

Referenced by xmlDictQLookup().

◆ xmlDictAddString()

static const xmlChar * xmlDictAddString ( xmlDictPtr  dict,
const xmlChar name,
unsigned int  namelen 
)
static

Definition at line 244 of file dict.c.

244 {
246 const xmlChar *ret;
247 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
248 size_t limit = 0;
249
250#ifdef DICT_DEBUG_PATTERNS
251 fprintf(stderr, "-");
252#endif
253 pool = dict->strings;
254 while (pool != NULL) {
255 if ((size_t)(pool->end - pool->free) > namelen)
256 goto found_pool;
257 if (pool->size > size) size = pool->size;
258 limit += pool->size;
259 pool = pool->next;
260 }
261 /*
262 * Not found, need to allocate
263 */
264 if (pool == NULL) {
265 if ((dict->limit > 0) && (limit > dict->limit)) {
266 return(NULL);
267 }
268
269 if (size == 0) size = 1000;
270 else size *= 4; /* exponential growth */
271 if (size < 4 * namelen)
272 size = 4 * namelen; /* just in case ! */
274 if (pool == NULL)
275 return(NULL);
276 pool->size = size;
277 pool->nbStrings = 0;
278 pool->free = &pool->array[0];
279 pool->end = &pool->array[size];
280 pool->next = dict->strings;
281 dict->strings = pool;
282#ifdef DICT_DEBUG_PATTERNS
283 fprintf(stderr, "+");
284#endif
285 }
286found_pool:
287 ret = pool->free;
288 memcpy(pool->free, name, namelen);
289 pool->free += namelen;
290 *(pool->free++) = 0;
291 pool->nbStrings++;
292 return(ret);
293}

Referenced by xmlDictAddQString(), and xmlDictLookup().

◆ xmlDictCleanup()

void xmlDictCleanup ( void  )

xmlDictCleanup:

DEPRECATED: This function will be made private. Call xmlCleanupParser to free global state but see the warnings there. xmlCleanupParser should be only called once at program exit. In most cases, you don't have call cleanup functions at all.

Free the dictionary mutex. Do not call unless sure the library is not in use anymore !

Definition at line 224 of file dict.c.

224 {
226 return;
227
229
231}
XMLPUBFUN void XMLCALL xmlFreeMutex(xmlMutexPtr tok)
Definition: threads.c:197

Referenced by xmlCleanupParser().

◆ xmlDictComputeBigKey()

static uint32_t xmlDictComputeBigKey ( const xmlChar data,
int  namelen,
int  seed 
)
static

Definition at line 381 of file dict.c.

381 {
383 int i;
384
385 if (namelen <= 0 || data == NULL) return(0);
386
387 hash = seed;
388
389 for (i = 0;i < namelen; i++) {
390 hash += data[i];
391 hash += (hash << 10);
392 hash ^= (hash >> 6);
393 }
394 hash += (hash << 3);
395 hash ^= (hash >> 11);
396 hash += (hash << 15);
397
398 return hash;
399}
UINT32 uint32_t
Definition: types.h:75
GLint GLenum GLsizei GLsizei GLsizei GLint GLsizei const GLvoid * data
Definition: gl.h:1950
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
Definition: _hash_fun.h:40

◆ xmlDictComputeBigQKey()

static unsigned long xmlDictComputeBigQKey ( const xmlChar prefix,
int  plen,
const xmlChar name,
int  len,
int  seed 
)
static

Definition at line 416 of file dict.c.

418{
420 int i;
421
422 hash = seed;
423
424 for (i = 0;i < plen; i++) {
425 hash += prefix[i];
426 hash += (hash << 10);
427 hash ^= (hash >> 6);
428 }
429 hash += ':';
430 hash += (hash << 10);
431 hash ^= (hash >> 6);
432
433 for (i = 0;i < len; i++) {
434 hash += name[i];
435 hash += (hash << 10);
436 hash ^= (hash >> 6);
437 }
438 hash += (hash << 3);
439 hash ^= (hash >> 11);
440 hash += (hash << 15);
441
442 return hash;
443}

◆ xmlDictComputeFastKey()

static unsigned long xmlDictComputeFastKey ( const xmlChar name,
int  namelen,
int  seed 
)
static

Definition at line 453 of file dict.c.

453 {
454 unsigned long value = seed;
455
456 if (name == NULL) return(0);
457 value += *name;
458 value <<= 5;
459 if (namelen > 10) {
460 value += name[namelen - 1];
461 namelen = 10;
462 }
463 switch (namelen) {
464 case 10: value += name[9];
465 /* Falls through. */
466 case 9: value += name[8];
467 /* Falls through. */
468 case 8: value += name[7];
469 /* Falls through. */
470 case 7: value += name[6];
471 /* Falls through. */
472 case 6: value += name[5];
473 /* Falls through. */
474 case 5: value += name[4];
475 /* Falls through. */
476 case 4: value += name[3];
477 /* Falls through. */
478 case 3: value += name[2];
479 /* Falls through. */
480 case 2: value += name[1];
481 /* Falls through. */
482 default: break;
483 }
484 return(value);
485}
Definition: pdh_main.c:94

◆ xmlDictComputeFastQKey()

static unsigned long xmlDictComputeFastQKey ( const xmlChar prefix,
int  plen,
const xmlChar name,
int  len,
int  seed 
)
static

Definition at line 496 of file dict.c.

498{
499 unsigned long value = (unsigned long) seed;
500
501 if (plen == 0)
502 value += 30 * (unsigned long) ':';
503 else
504 value += 30 * (*prefix);
505
506 if (len > 10) {
507 int offset = len - (plen + 1 + 1);
508 if (offset < 0)
509 offset = len - (10 + 1);
510 value += name[offset];
511 len = 10;
512 if (plen > 10)
513 plen = 10;
514 }
515 switch (plen) {
516 case 10: value += prefix[9];
517 /* Falls through. */
518 case 9: value += prefix[8];
519 /* Falls through. */
520 case 8: value += prefix[7];
521 /* Falls through. */
522 case 7: value += prefix[6];
523 /* Falls through. */
524 case 6: value += prefix[5];
525 /* Falls through. */
526 case 5: value += prefix[4];
527 /* Falls through. */
528 case 4: value += prefix[3];
529 /* Falls through. */
530 case 3: value += prefix[2];
531 /* Falls through. */
532 case 2: value += prefix[1];
533 /* Falls through. */
534 case 1: value += prefix[0];
535 /* Falls through. */
536 default: break;
537 }
538 len -= plen;
539 if (len > 0) {
540 value += (unsigned long) ':';
541 len--;
542 }
543 switch (len) {
544 case 10: value += name[9];
545 /* Falls through. */
546 case 9: value += name[8];
547 /* Falls through. */
548 case 8: value += name[7];
549 /* Falls through. */
550 case 7: value += name[6];
551 /* Falls through. */
552 case 6: value += name[5];
553 /* Falls through. */
554 case 5: value += name[4];
555 /* Falls through. */
556 case 4: value += name[3];
557 /* Falls through. */
558 case 3: value += name[2];
559 /* Falls through. */
560 case 2: value += name[1];
561 /* Falls through. */
562 case 1: value += name[0];
563 /* Falls through. */
564 default: break;
565 }
566 return(value);
567}
GLintptr offset
Definition: glext.h:5920
#define long
Definition: qsort.c:33

◆ xmlDictCreate()

xmlDictPtr xmlDictCreate ( void  )

xmlDictCreate:

Create a new dictionary

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

Definition at line 577 of file dict.c.

577 {
578 xmlDictPtr dict;
579
581 if (!__xmlInitializeDict())
582 return(NULL);
583
584#ifdef DICT_DEBUG_PATTERNS
585 fprintf(stderr, "C");
586#endif
587
588 dict = xmlMalloc(sizeof(xmlDict));
589 if (dict) {
590 dict->ref_counter = 1;
591 dict->limit = 0;
592
593 dict->size = MIN_DICT_SIZE;
594 dict->nbElems = 0;
595 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
596 dict->strings = NULL;
597 dict->subdict = NULL;
598 if (dict->dict) {
599 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
600#ifdef DICT_RANDOMIZATION
601 dict->seed = __xmlRandom();
602#else
603 dict->seed = 0;
604#endif
605 return(dict);
606 }
607 xmlFree(dict);
608 }
609 return(NULL);
610}
XMLPUBVAR xmlFreeFunc xmlFree
Definition: globals.h:251
int __xmlRandom(void)
Definition: dict.c:195
#define memset(x, y, z)
Definition: compat.h:39
Definition: dict.c:111
struct _xmlDictEntry * dict
Definition: dict.c:114
struct _xmlDict * subdict
Definition: dict.c:119
int ref_counter
Definition: dict.c:112
unsigned int nbElems
Definition: dict.c:116
size_t size
Definition: dict.c:115
int seed
Definition: dict.c:121

Referenced by xmlDictCreateSub(), xmlInitParserCtxt(), and xsltNewStylesheetInternal().

◆ xmlDictCreateSub()

xmlDictPtr xmlDictCreateSub ( xmlDictPtr  sub)

xmlDictCreateSub: @sub: an existing dictionary

Create a new dictionary, inheriting strings from the read-only dictionary @sub. On lookup, strings are first searched in the new dictionary, then in @sub, and if not found are created in the new dictionary.

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

Definition at line 624 of file dict.c.

624 {
625 xmlDictPtr dict = xmlDictCreate();
626
627 if ((dict != NULL) && (sub != NULL)) {
628#ifdef DICT_DEBUG_PATTERNS
629 fprintf(stderr, "R");
630#endif
631 dict->seed = sub->seed;
632 dict->subdict = sub;
634 }
635 return(dict);
636}
int xmlDictReference(xmlDictPtr dict)
Definition: dict.c:647
xmlDictPtr xmlDictCreate(void)
Definition: dict.c:577

Referenced by xsltNewTransformContext().

◆ xmlDictExists()

const xmlChar * xmlDictExists ( xmlDictPtr  dict,
const xmlChar name,
int  len 
)

Definition at line 1007 of file dict.c.

1007 {
1008 unsigned long key, okey, nbi = 0;
1010 unsigned int l;
1011
1012 if ((dict == NULL) || (name == NULL))
1013 return(NULL);
1014
1015 if (len < 0)
1016 l = strlen((const char *) name);
1017 else
1018 l = len;
1019 if (((dict->limit > 0) && (l >= dict->limit)) ||
1020 (l > INT_MAX / 2))
1021 return(NULL);
1022
1023 /*
1024 * Check for duplicate and insertion location.
1025 */
1026 okey = xmlDictComputeKey(dict, name, l);
1027 key = okey % dict->size;
1028 if (dict->dict[key].valid == 0) {
1029 insert = NULL;
1030 } else {
1031 for (insert = &(dict->dict[key]); insert->next != NULL;
1032 insert = insert->next) {
1033#ifdef __GNUC__
1034 if ((insert->okey == okey) && (insert->len == l)) {
1035 if (!memcmp(insert->name, name, l))
1036 return(insert->name);
1037 }
1038#else
1039 if ((insert->okey == okey) && (insert->len == l) &&
1040 (!xmlStrncmp(insert->name, name, l)))
1041 return(insert->name);
1042#endif
1043 nbi++;
1044 }
1045#ifdef __GNUC__
1046 if ((insert->okey == okey) && (insert->len == l)) {
1047 if (!memcmp(insert->name, name, l))
1048 return(insert->name);
1049 }
1050#else
1051 if ((insert->okey == okey) && (insert->len == l) &&
1052 (!xmlStrncmp(insert->name, name, l)))
1053 return(insert->name);
1054#endif
1055 }
1056
1057 if (dict->subdict) {
1058 unsigned long skey;
1059
1060 /* we cannot always reuse the same okey for the subdict */
1061 if (((dict->size == MIN_DICT_SIZE) &&
1062 (dict->subdict->size != MIN_DICT_SIZE)) ||
1063 ((dict->size != MIN_DICT_SIZE) &&
1064 (dict->subdict->size == MIN_DICT_SIZE)))
1065 skey = xmlDictComputeKey(dict->subdict, name, l);
1066 else
1067 skey = okey;
1068
1069 key = skey % dict->subdict->size;
1070 if (dict->subdict->dict[key].valid != 0) {
1071 xmlDictEntryPtr tmp;
1072
1073 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1074 tmp = tmp->next) {
1075#ifdef __GNUC__
1076 if ((tmp->okey == skey) && (tmp->len == l)) {
1077 if (!memcmp(tmp->name, name, l))
1078 return(tmp->name);
1079 }
1080#else
1081 if ((tmp->okey == skey) && (tmp->len == l) &&
1082 (!xmlStrncmp(tmp->name, name, l)))
1083 return(tmp->name);
1084#endif
1085 nbi++;
1086 }
1087#ifdef __GNUC__
1088 if ((tmp->okey == skey) && (tmp->len == l)) {
1089 if (!memcmp(tmp->name, name, l))
1090 return(tmp->name);
1091 }
1092#else
1093 if ((tmp->okey == skey) && (tmp->len == l) &&
1094 (!xmlStrncmp(tmp->name, name, l)))
1095 return(tmp->name);
1096#endif
1097 }
1098 }
1099
1100 /* not found */
1101 return(NULL);
1102}
int memcmp(void *Buffer1, void *Buffer2, ACPI_SIZE Count)
Definition: utclib.c:112
ACPI_SIZE strlen(const char *String)
Definition: utclib.c:269
r l[0]
Definition: byte_order.h:168
#define INT_MAX
Definition: limits.h:40
const xmlChar * name
Definition: dict.c:92
unsigned int len
Definition: dict.c:93
struct _xmlDictEntry * next
Definition: dict.c:91
unsigned long okey
Definition: dict.c:95
Definition: copy.c:22
static int insert
Definition: xmllint.c:138
XMLPUBFUN int XMLCALL xmlStrncmp(const xmlChar *str1, const xmlChar *str2, int len)
Definition: xmlstring.c:213

◆ xmlDictFree()

void xmlDictFree ( xmlDictPtr  dict)

xmlDictFree: @dict: the dictionary

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

Definition at line 802 of file dict.c.

802 {
803 size_t i;
804 xmlDictEntryPtr iter;
806 int inside_dict = 0;
807 xmlDictStringsPtr pool, nextp;
808
809 if (dict == NULL)
810 return;
811
813 if (!__xmlInitializeDict())
814 return;
815
816 /* decrement the counter, it may be shared by a parser and docs */
818 dict->ref_counter--;
819 if (dict->ref_counter > 0) {
821 return;
822 }
823
825
826 if (dict->subdict != NULL) {
827 xmlDictFree(dict->subdict);
828 }
829
830 if (dict->dict) {
831 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
832 iter = &(dict->dict[i]);
833 if (iter->valid == 0)
834 continue;
835 inside_dict = 1;
836 while (iter) {
837 next = iter->next;
838 if (!inside_dict)
839 xmlFree(iter);
840 dict->nbElems--;
841 inside_dict = 0;
842 iter = next;
843 }
844 }
845 xmlFree(dict->dict);
846 }
847 pool = dict->strings;
848 while (pool != NULL) {
849 nextp = pool->next;
850 xmlFree(pool);
851 pool = nextp;
852 }
853 xmlFree(dict);
854}
static unsigned __int64 next
Definition: rand_nt.c:6
void xmlDictFree(xmlDictPtr dict)
Definition: dict.c:802
int valid
Definition: dict.c:94

Referenced by xmlDictFree(), xmlFreeParserCtxt(), xmlHashFree(), xmlParseBalancedChunkMemoryInternal(), xmlParseExternalEntityPrivate(), xmlParseInNodeContext(), xsltDocDefaultLoaderFunc(), xsltFreeStylesheet(), xsltFreeTransformContext(), and xsltParseStylesheetUser().

◆ xmlDictGetUsage()

size_t xmlDictGetUsage ( xmlDictPtr  dict)

xmlDictGetUsage: @dict: the dictionary

Get how much memory is used by a dictionary for strings Added in 2.9.0

Returns the amount of strings allocated

Definition at line 1285 of file dict.c.

1285 {
1287 size_t limit = 0;
1288
1289 if (dict == NULL)
1290 return(0);
1291 pool = dict->strings;
1292 while (pool != NULL) {
1293 limit += pool->size;
1294 pool = pool->next;
1295 }
1296 return(limit);
1297}

◆ xmlDictGrow()

static int xmlDictGrow ( xmlDictPtr  dict,
size_t  size 
)
static

xmlDictGrow: @dict: the dictionary @size: the new size of the dictionary

resize the dictionary

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

Definition at line 669 of file dict.c.

669 {
670 unsigned long key, okey;
671 size_t oldsize, i;
672 xmlDictEntryPtr iter, next;
673 struct _xmlDictEntry *olddict;
674#ifdef DEBUG_GROW
675 unsigned long nbElem = 0;
676#endif
677 int ret = 0;
678 int keep_keys = 1;
679
680 if (dict == NULL)
681 return(-1);
682 if (size < 8)
683 return(-1);
684 if (size > 8 * 2048)
685 return(-1);
686
687#ifdef DICT_DEBUG_PATTERNS
688 fprintf(stderr, "*");
689#endif
690
691 oldsize = dict->size;
692 olddict = dict->dict;
693 if (olddict == NULL)
694 return(-1);
695 if (oldsize == MIN_DICT_SIZE)
696 keep_keys = 0;
697
698 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
699 if (dict->dict == NULL) {
700 dict->dict = olddict;
701 return(-1);
702 }
703 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
704 dict->size = size;
705
706 /* If the two loops are merged, there would be situations where
707 a new entry needs to allocated and data copied into it from
708 the main dict. It is nicer to run through the array twice, first
709 copying all the elements in the main array (less probability of
710 allocate) and then the rest, so we only free in the second loop.
711 */
712 for (i = 0; i < oldsize; i++) {
713 if (olddict[i].valid == 0)
714 continue;
715
716 if (keep_keys)
717 okey = olddict[i].okey;
718 else
719 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
720 key = okey % dict->size;
721
722 if (dict->dict[key].valid == 0) {
723 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
724 dict->dict[key].next = NULL;
725 dict->dict[key].okey = okey;
726 } else {
728
729 entry = xmlMalloc(sizeof(xmlDictEntry));
730 if (entry != NULL) {
731 entry->name = olddict[i].name;
732 entry->len = olddict[i].len;
733 entry->okey = okey;
734 entry->next = dict->dict[key].next;
735 entry->valid = 1;
736 dict->dict[key].next = entry;
737 } else {
738 /*
739 * we don't have much ways to alert from here
740 * result is losing an entry and unicity guarantee
741 */
742 ret = -1;
743 }
744 }
745#ifdef DEBUG_GROW
746 nbElem++;
747#endif
748 }
749
750 for (i = 0; i < oldsize; i++) {
751 iter = olddict[i].next;
752 while (iter) {
753 next = iter->next;
754
755 /*
756 * put back the entry in the new dict
757 */
758
759 if (keep_keys)
760 okey = iter->okey;
761 else
762 okey = xmlDictComputeKey(dict, iter->name, iter->len);
763 key = okey % dict->size;
764 if (dict->dict[key].valid == 0) {
765 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
766 dict->dict[key].next = NULL;
767 dict->dict[key].valid = 1;
768 dict->dict[key].okey = okey;
769 xmlFree(iter);
770 } else {
771 iter->next = dict->dict[key].next;
772 iter->okey = okey;
773 dict->dict[key].next = iter;
774 }
775
776#ifdef DEBUG_GROW
777 nbElem++;
778#endif
779
780 iter = next;
781 }
782 }
783
784 xmlFree(olddict);
785
786#ifdef DEBUG_GROW
788 "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
789#endif
790
791 return(ret);
792}
BOOLEAN valid
uint32_t entry
Definition: isohybrid.c:63
XMLPUBVAR void * xmlGenericErrorContext
Definition: globals.h:353
XMLPUBVAR xmlGenericErrorFunc xmlGenericError
Definition: globals.h:337

Referenced by xmlDictLookup(), and xmlDictQLookup().

◆ xmlDictLookup()

const xmlChar * xmlDictLookup ( xmlDictPtr  dict,
const xmlChar name,
int  len 
)

Definition at line 867 of file dict.c.

867 {
868 unsigned long key, okey, nbi = 0;
871 const xmlChar *ret;
872 unsigned int l;
873
874 if ((dict == NULL) || (name == NULL))
875 return(NULL);
876
877 if (len < 0)
878 l = strlen((const char *) name);
879 else
880 l = len;
881
882 if (((dict->limit > 0) && (l >= dict->limit)) ||
883 (l > INT_MAX / 2))
884 return(NULL);
885
886 /*
887 * Check for duplicate and insertion location.
888 */
889 okey = xmlDictComputeKey(dict, name, l);
890 key = okey % dict->size;
891 if (dict->dict[key].valid == 0) {
892 insert = NULL;
893 } else {
894 for (insert = &(dict->dict[key]); insert->next != NULL;
895 insert = insert->next) {
896#ifdef __GNUC__
897 if ((insert->okey == okey) && (insert->len == l)) {
898 if (!memcmp(insert->name, name, l))
899 return(insert->name);
900 }
901#else
902 if ((insert->okey == okey) && (insert->len == l) &&
903 (!xmlStrncmp(insert->name, name, l)))
904 return(insert->name);
905#endif
906 nbi++;
907 }
908#ifdef __GNUC__
909 if ((insert->okey == okey) && (insert->len == l)) {
910 if (!memcmp(insert->name, name, l))
911 return(insert->name);
912 }
913#else
914 if ((insert->okey == okey) && (insert->len == l) &&
915 (!xmlStrncmp(insert->name, name, l)))
916 return(insert->name);
917#endif
918 }
919
920 if (dict->subdict) {
921 unsigned long skey;
922
923 /* we cannot always reuse the same okey for the subdict */
924 if (((dict->size == MIN_DICT_SIZE) &&
925 (dict->subdict->size != MIN_DICT_SIZE)) ||
926 ((dict->size != MIN_DICT_SIZE) &&
927 (dict->subdict->size == MIN_DICT_SIZE)))
928 skey = xmlDictComputeKey(dict->subdict, name, l);
929 else
930 skey = okey;
931
932 key = skey % dict->subdict->size;
933 if (dict->subdict->dict[key].valid != 0) {
934 xmlDictEntryPtr tmp;
935
936 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
937 tmp = tmp->next) {
938#ifdef __GNUC__
939 if ((tmp->okey == skey) && (tmp->len == l)) {
940 if (!memcmp(tmp->name, name, l))
941 return(tmp->name);
942 }
943#else
944 if ((tmp->okey == skey) && (tmp->len == l) &&
945 (!xmlStrncmp(tmp->name, name, l)))
946 return(tmp->name);
947#endif
948 nbi++;
949 }
950#ifdef __GNUC__
951 if ((tmp->okey == skey) && (tmp->len == l)) {
952 if (!memcmp(tmp->name, name, l))
953 return(tmp->name);
954 }
955#else
956 if ((tmp->okey == skey) && (tmp->len == l) &&
957 (!xmlStrncmp(tmp->name, name, l)))
958 return(tmp->name);
959#endif
960 }
961 key = okey % dict->size;
962 }
963
964 ret = xmlDictAddString(dict, name, l);
965 if (ret == NULL)
966 return(NULL);
967 if (insert == NULL) {
968 entry = &(dict->dict[key]);
969 } else {
970 entry = xmlMalloc(sizeof(xmlDictEntry));
971 if (entry == NULL)
972 return(NULL);
973 }
974 entry->name = ret;
975 entry->len = l;
976 entry->next = NULL;
977 entry->valid = 1;
978 entry->okey = okey;
979
980
981 if (insert != NULL)
982 insert->next = entry;
983
984 dict->nbElems++;
985
986 if ((nbi > MAX_HASH_LEN) &&
987 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
988 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
989 return(NULL);
990 }
991 /* Note that entry may have been freed at this point by xmlDictGrow */
992
993 return(ret);
994}
#define MAX_DICT_HASH
Definition: dict.c:62
#define MAX_HASH_LEN
Definition: dict.c:60
static int xmlDictGrow(xmlDictPtr dict, size_t size)
Definition: dict.c:669

Referenced by xmlAddAttributeDecl(), xmlAddDefAttrs(), xmlAddID(), xmlCopyDocElementContent(), xmlDetectSAX2(), xmlDictQLookup(), xmlHashAddEntry3(), xmlHashUpdateEntry3(), xmlNewDocElementContent(), xmlParseBalancedChunkMemoryInternal(), xmlParseExternalEntityPrivate(), xmlParseInNodeContext(), xmlParseName(), xmlParseNameComplex(), xmlParseNCName(), xmlParseNCNameComplex(), xmlParseQName(), xmlParseReference(), xmlParseStartTag2(), xmlSAX2TextNode(), xsltAddTemplate(), xsltApplyAttributeSet(), xsltApplyStylesheetInternal(), xsltAttribute(), xsltAttributeComp(), xsltAttrListTemplateProcess(), xsltAttrTemplateProcess(), xsltElement(), xsltElementComp(), xsltEvalStaticAttrValueTemplate(), xsltGetCNsProp(), xsltGetQNameProperty(), xsltGetQNameURI2(), xsltNumberComp(), xsltParseStylesheetAttributeSet(), xsltParseStylesheetTemplate(), xsltParseTemplateContent(), xsltPreprocessStylesheet(), xsltProcessUserParamInternal(), xsltRegisterGlobalVariable(), xsltShallowCopyAttr(), xsltSortComp(), xsltSplitQName(), xsltStackLookup(), and xsltXPathVariableLookup().

◆ xmlDictOwns()

int xmlDictOwns ( xmlDictPtr  dict,
const xmlChar str 
)

xmlDictOwns: @dict: the dictionary @str: the string

check if a string is owned by the dictionary

Returns 1 if true, 0 if false and -1 in case of error -1 in case of error

Definition at line 1220 of file dict.c.

1220 {
1222
1223 if ((dict == NULL) || (str == NULL))
1224 return(-1);
1225 pool = dict->strings;
1226 while (pool != NULL) {
1227 if ((str >= &pool->array[0]) && (str <= pool->free))
1228 return(1);
1229 pool = pool->next;
1230 }
1231 if (dict->subdict)
1232 return(xmlDictOwns(dict->subdict, str));
1233 return(0);
1234}
#define free
Definition: debug_ros.c:5
const WCHAR * str
int xmlDictOwns(xmlDictPtr dict, const xmlChar *str)
Definition: dict.c:1220

Referenced by xmlDictOwns(), xmlFreeAttribute(), xmlFreeDocElementContent(), xmlHashAddEntry3(), xmlHashUpdateEntry3(), xmlParseEnumerationType(), xmlParseNotationType(), xmlSAX2ExternalSubset(), xmlSAX2Text(), xsltAttrListTemplateProcess(), xsltAttrTemplateProcess(), xsltCopyText(), xsltParseTemplateContent(), and xsltPreprocessStylesheet().

◆ xmlDictQLookup()

const xmlChar * xmlDictQLookup ( xmlDictPtr  dict,
const xmlChar prefix,
const xmlChar name 
)

Definition at line 1115 of file dict.c.

1115 {
1116 unsigned long okey, key, nbi = 0;
1119 const xmlChar *ret;
1120 unsigned int len, plen, l;
1121
1122 if ((dict == NULL) || (name == NULL))
1123 return(NULL);
1124 if (prefix == NULL)
1125 return(xmlDictLookup(dict, name, -1));
1126
1127 l = len = strlen((const char *) name);
1128 plen = strlen((const char *) prefix);
1129 len += 1 + plen;
1130
1131 /*
1132 * Check for duplicate and insertion location.
1133 */
1134 okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
1135 key = okey % dict->size;
1136 if (dict->dict[key].valid == 0) {
1137 insert = NULL;
1138 } else {
1139 for (insert = &(dict->dict[key]); insert->next != NULL;
1140 insert = insert->next) {
1141 if ((insert->okey == okey) && (insert->len == len) &&
1142 (xmlStrQEqual(prefix, name, insert->name)))
1143 return(insert->name);
1144 nbi++;
1145 }
1146 if ((insert->okey == okey) && (insert->len == len) &&
1147 (xmlStrQEqual(prefix, name, insert->name)))
1148 return(insert->name);
1149 }
1150
1151 if (dict->subdict) {
1152 unsigned long skey;
1153
1154 /* we cannot always reuse the same okey for the subdict */
1155 if (((dict->size == MIN_DICT_SIZE) &&
1156 (dict->subdict->size != MIN_DICT_SIZE)) ||
1157 ((dict->size != MIN_DICT_SIZE) &&
1158 (dict->subdict->size == MIN_DICT_SIZE)))
1159 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
1160 else
1161 skey = okey;
1162
1163 key = skey % dict->subdict->size;
1164 if (dict->subdict->dict[key].valid != 0) {
1165 xmlDictEntryPtr tmp;
1166 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1167 tmp = tmp->next) {
1168 if ((tmp->okey == skey) && (tmp->len == len) &&
1169 (xmlStrQEqual(prefix, name, tmp->name)))
1170 return(tmp->name);
1171 nbi++;
1172 }
1173 if ((tmp->okey == skey) && (tmp->len == len) &&
1174 (xmlStrQEqual(prefix, name, tmp->name)))
1175 return(tmp->name);
1176 }
1177 key = okey % dict->size;
1178 }
1179
1180 ret = xmlDictAddQString(dict, prefix, plen, name, l);
1181 if (ret == NULL)
1182 return(NULL);
1183 if (insert == NULL) {
1184 entry = &(dict->dict[key]);
1185 } else {
1186 entry = xmlMalloc(sizeof(xmlDictEntry));
1187 if (entry == NULL)
1188 return(NULL);
1189 }
1190 entry->name = ret;
1191 entry->len = len;
1192 entry->next = NULL;
1193 entry->valid = 1;
1194 entry->okey = okey;
1195
1196 if (insert != NULL)
1197 insert->next = entry;
1198
1199 dict->nbElems++;
1200
1201 if ((nbi > MAX_HASH_LEN) &&
1202 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1203 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1204 /* Note that entry may have been freed at this point by xmlDictGrow */
1205
1206 return(ret);
1207}
static const xmlChar * xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen, const xmlChar *name, unsigned int namelen)
Definition: dict.c:308
#define xmlDictComputeQKey(dict, prefix, plen, name, len)
Definition: dict.c:71
const xmlChar * xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len)
Definition: dict.c:867
XMLPUBFUN int XMLCALL xmlStrQEqual(const xmlChar *pref, const xmlChar *name, const xmlChar *str)
Definition: xmlstring.c:186

Referenced by xmlSAX2StartElementNs(), xsltApplyStylesheetInternal(), and xsltDocumentElem().

◆ xmlDictReference()

int xmlDictReference ( xmlDictPtr  dict)

xmlDictReference: @dict: the dictionary

Increment the reference counter of a dictionary

Returns 0 in case of success and -1 in case of error

Definition at line 647 of file dict.c.

647 {
649 if (!__xmlInitializeDict())
650 return(-1);
651
652 if (dict == NULL) return -1;
654 dict->ref_counter++;
656 return(0);
657}

Referenced by xmlDictCreateSub(), xmlHashCreateDict(), xmlParseBalancedChunkMemoryInternal(), xmlParseExternalEntityPrivate(), xmlSAX2StartDocument(), xsltApplyStylesheetInternal(), xsltCreateRVT(), xsltDocDefaultLoaderFunc(), xsltDocumentElem(), xsltLoadStylesheetPI(), and xsltParseStylesheetUser().

◆ xmlDictSetLimit()

size_t xmlDictSetLimit ( xmlDictPtr  dict,
size_t  limit 
)

xmlDictSetLimit: @dict: the dictionary @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

Definition at line 1265 of file dict.c.

1265 {
1266 size_t ret;
1267
1268 if (dict == NULL)
1269 return(0);
1270 ret = dict->limit;
1271 dict->limit = limit;
1272 return(ret);
1273}

Referenced by xmlCtxtUseOptionsInternal(), and xmlInitParserCtxt().

◆ xmlDictSize()

int xmlDictSize ( xmlDictPtr  dict)

xmlDictSize: @dict: the dictionary

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

Returns the number of elements in the dictionary or -1 in case of error

Definition at line 1246 of file dict.c.

1246 {
1247 if (dict == NULL)
1248 return(-1);
1249 if (dict->subdict)
1250 return(dict->nbElems + dict->subdict->nbElems);
1251 return(dict->nbElems);
1252}

◆ xmlInitializeDict()

int xmlInitializeDict ( void  )

xmlInitializeDict:

DEPRECATED: This function will be made private. Call xmlInitParser to initialize the library.

Do the dictionary mutex initialization.

Returns 0 if initialization was already done, and 1 if that call led to the initialization

Definition at line 157 of file dict.c.

157 {
158 return(0);
159}

Referenced by xmlInitParser().

Variable Documentation

◆ xmlDictInitialized

int xmlDictInitialized = 0
static

◆ xmlDictMutex

xmlMutexPtr xmlDictMutex = NULL
static