blob: c0585fe239633928036080cbede9ff3352eb64ab [file] [log] [blame]
Daniel Veillard2fdbd322003-08-18 12:15:38 +00001/*
2 * dict.c: dictionary of reusable strings, just used to avoid allocation
3 * and freeing operations.
4 *
Daniel Veillard8973d582012-02-04 19:07:44 +08005 * Copyright (C) 2003-2012 Daniel Veillard.
Daniel Veillard2fdbd322003-08-18 12:15:38 +00006 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
12 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
13 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
14 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
15 *
16 * Author: daniel@veillard.com
17 */
18
19#define IN_LIBXML
20#include "libxml.h"
21
Daniel Veillard7c693da2012-07-25 16:32:18 +080022#include <limits.h>
Daniel Veillard8973d582012-02-04 19:07:44 +080023#ifdef HAVE_STDLIB_H
24#include <stdlib.h>
25#endif
26#ifdef HAVE_TIME_H
27#include <time.h>
28#endif
29
30/*
31 * Following http://www.ocert.org/advisories/ocert-2011-003.html
32 * it seems that having hash randomization might be a good idea
33 * when using XML with untrusted data
34 * Note1: that it works correctly only if compiled with WITH_BIG_KEY
35 * which is the default.
36 * Note2: the fast function used for a small dict won't protect very
37 * well but since the attack is based on growing a very big hash
38 * list we will use the BigKey algo as soon as the hash size grows
39 * over MIN_DICT_SIZE so this actually works
40 */
41#if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
42#define DICT_RANDOMIZATION
43#endif
44
Daniel Veillard2fdbd322003-08-18 12:15:38 +000045#include <string.h>
Rob Richardsb6b2ee12008-05-03 12:34:25 +000046#ifdef HAVE_STDINT_H
Daniel Veillarde9100a52008-04-22 08:28:50 +000047#include <stdint.h>
Daniel Veillard7f4547c2008-10-03 07:58:23 +000048#else
49#ifdef HAVE_INTTYPES_H
50#include <inttypes.h>
Rob Richardsb6b2ee12008-05-03 12:34:25 +000051#elif defined(WIN32)
52typedef unsigned __int32 uint32_t;
Rob Richardsb6b2ee12008-05-03 12:34:25 +000053#endif
Daniel Veillard7f4547c2008-10-03 07:58:23 +000054#endif
Daniel Veillard2fdbd322003-08-18 12:15:38 +000055#include <libxml/tree.h>
56#include <libxml/dict.h>
57#include <libxml/xmlmemory.h>
58#include <libxml/xmlerror.h>
59#include <libxml/globals.h>
60
Daniel Veillard424785e2008-08-06 09:35:25 +000061/* #define DEBUG_GROW */
62/* #define DICT_DEBUG_PATTERNS */
63
Daniel Veillarde9100a52008-04-22 08:28:50 +000064#define MAX_HASH_LEN 3
Daniel Veillard2fdbd322003-08-18 12:15:38 +000065#define MIN_DICT_SIZE 128
66#define MAX_DICT_HASH 8 * 2048
Daniel Veillard424785e2008-08-06 09:35:25 +000067#define WITH_BIG_KEY
Daniel Veillard2fdbd322003-08-18 12:15:38 +000068
Daniel Veillard424785e2008-08-06 09:35:25 +000069#ifdef WITH_BIG_KEY
Daniel Veillard8973d582012-02-04 19:07:44 +080070#define xmlDictComputeKey(dict, name, len) \
71 (((dict)->size == MIN_DICT_SIZE) ? \
72 xmlDictComputeFastKey(name, len, (dict)->seed) : \
73 xmlDictComputeBigKey(name, len, (dict)->seed))
Daniel Veillarde9100a52008-04-22 08:28:50 +000074
Daniel Veillard8973d582012-02-04 19:07:44 +080075#define xmlDictComputeQKey(dict, prefix, plen, name, len) \
76 (((prefix) == NULL) ? \
77 (xmlDictComputeKey(dict, name, len)) : \
78 (((dict)->size == MIN_DICT_SIZE) ? \
79 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \
80 xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
Daniel Veillarde9100a52008-04-22 08:28:50 +000081
Daniel Veillard424785e2008-08-06 09:35:25 +000082#else /* !WITH_BIG_KEY */
Daniel Veillard8973d582012-02-04 19:07:44 +080083#define xmlDictComputeKey(dict, name, len) \
84 xmlDictComputeFastKey(name, len, (dict)->seed)
85#define xmlDictComputeQKey(dict, prefix, plen, name, len) \
86 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
Daniel Veillard424785e2008-08-06 09:35:25 +000087#endif /* WITH_BIG_KEY */
Daniel Veillard2fdbd322003-08-18 12:15:38 +000088
89/*
Jan Pokornýbb654fe2016-04-13 16:56:07 +020090 * An entry in the dictionary
Daniel Veillard2fdbd322003-08-18 12:15:38 +000091 */
92typedef struct _xmlDictEntry xmlDictEntry;
93typedef xmlDictEntry *xmlDictEntryPtr;
94struct _xmlDictEntry {
95 struct _xmlDictEntry *next;
Daniel Veillard81514ba2003-09-16 23:17:26 +000096 const xmlChar *name;
Daniel Veillard7c693da2012-07-25 16:32:18 +080097 unsigned int len;
Daniel Veillard2fdbd322003-08-18 12:15:38 +000098 int valid;
Daniel Veillardd68f8912008-08-08 10:09:19 +000099 unsigned long okey;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000100};
101
Daniel Veillard81514ba2003-09-16 23:17:26 +0000102typedef struct _xmlDictStrings xmlDictStrings;
103typedef xmlDictStrings *xmlDictStringsPtr;
104struct _xmlDictStrings {
105 xmlDictStringsPtr next;
106 xmlChar *free;
107 xmlChar *end;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800108 size_t size;
109 size_t nbStrings;
Daniel Veillard81514ba2003-09-16 23:17:26 +0000110 xmlChar array[1];
111};
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000112/*
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200113 * The entire dictionary
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000114 */
115struct _xmlDict {
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000116 int ref_counter;
117
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000118 struct _xmlDictEntry *dict;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800119 size_t size;
120 unsigned int nbElems;
Daniel Veillard81514ba2003-09-16 23:17:26 +0000121 xmlDictStringsPtr strings;
Daniel Veillard4773df22004-01-23 13:15:13 +0000122
123 struct _xmlDict *subdict;
Daniel Veillard8973d582012-02-04 19:07:44 +0800124 /* used for randomization */
125 int seed;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800126 /* used to impose a limit on size */
127 size_t limit;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000128};
129
130/*
Daniel Veillard14412512005-01-21 23:53:26 +0000131 * A mutex for modifying the reference counter for shared
132 * dictionaries.
133 */
134static xmlRMutexPtr xmlDictMutex = NULL;
135
136/*
137 * Whether the dictionary mutex was initialized.
138 */
139static int xmlDictInitialized = 0;
140
Daniel Veillard379ebc12012-05-18 15:41:31 +0800141#ifdef DICT_RANDOMIZATION
142#ifdef HAVE_RAND_R
143/*
144 * Internal data for random function, protected by xmlDictMutex
145 */
Wouter Van Rooye7715a52012-09-14 14:39:42 +0800146static unsigned int rand_seed = 0;
Daniel Veillard379ebc12012-05-18 15:41:31 +0800147#endif
148#endif
149
Daniel Veillard14412512005-01-21 23:53:26 +0000150/**
William M. Brack4e1c2db2005-02-11 10:58:55 +0000151 * xmlInitializeDict:
Daniel Veillard14412512005-01-21 23:53:26 +0000152 *
153 * Do the dictionary mutex initialization.
Daniel Veillard5fe9e9e2013-04-05 23:10:41 +0800154 * this function is deprecated
Daniel Veillardee8f1d42012-05-21 11:16:12 +0800155 *
156 * Returns 0 if initialization was already done, and 1 if that
157 * call led to the initialization
Daniel Veillard14412512005-01-21 23:53:26 +0000158 */
Daniel Veillard379ebc12012-05-18 15:41:31 +0800159int xmlInitializeDict(void) {
Daniel Veillard5fe9e9e2013-04-05 23:10:41 +0800160 return(0);
161}
162
163/**
164 * __xmlInitializeDict:
165 *
166 * This function is not public
167 * Do the dictionary mutex initialization.
168 * this function is not thread safe, initialization should
169 * normally be done once at setup when called from xmlOnceInit()
170 * we may also land in this code if thread support is not compiled in
171 *
172 * Returns 0 if initialization was already done, and 1 if that
173 * call led to the initialization
174 */
175int __xmlInitializeDict(void) {
Daniel Veillard14412512005-01-21 23:53:26 +0000176 if (xmlDictInitialized)
177 return(1);
178
179 if ((xmlDictMutex = xmlNewRMutex()) == NULL)
180 return(0);
Daniel Veillard379ebc12012-05-18 15:41:31 +0800181 xmlRMutexLock(xmlDictMutex);
Daniel Veillard14412512005-01-21 23:53:26 +0000182
Daniel Veillard8973d582012-02-04 19:07:44 +0800183#ifdef DICT_RANDOMIZATION
Daniel Veillard379ebc12012-05-18 15:41:31 +0800184#ifdef HAVE_RAND_R
185 rand_seed = time(NULL);
186 rand_r(& rand_seed);
187#else
Daniel Veillard8973d582012-02-04 19:07:44 +0800188 srand(time(NULL));
189#endif
Daniel Veillard379ebc12012-05-18 15:41:31 +0800190#endif
Daniel Veillard14412512005-01-21 23:53:26 +0000191 xmlDictInitialized = 1;
Daniel Veillard379ebc12012-05-18 15:41:31 +0800192 xmlRMutexUnlock(xmlDictMutex);
Daniel Veillard14412512005-01-21 23:53:26 +0000193 return(1);
194}
195
Daniel Veillard379ebc12012-05-18 15:41:31 +0800196#ifdef DICT_RANDOMIZATION
197int __xmlRandom(void) {
198 int ret;
199
200 if (xmlDictInitialized == 0)
Daniel Veillard5fe9e9e2013-04-05 23:10:41 +0800201 __xmlInitializeDict();
Daniel Veillard379ebc12012-05-18 15:41:31 +0800202
203 xmlRMutexLock(xmlDictMutex);
204#ifdef HAVE_RAND_R
205 ret = rand_r(& rand_seed);
206#else
207 ret = rand();
208#endif
209 xmlRMutexUnlock(xmlDictMutex);
210 return(ret);
211}
212#endif
213
Daniel Veillard14412512005-01-21 23:53:26 +0000214/**
Daniel Veillard2ae13382005-01-25 23:45:06 +0000215 * xmlDictCleanup:
Daniel Veillard14412512005-01-21 23:53:26 +0000216 *
Daniel Veillard379ebc12012-05-18 15:41:31 +0800217 * Free the dictionary mutex. Do not call unless sure the library
218 * is not in use anymore !
Daniel Veillard14412512005-01-21 23:53:26 +0000219 */
220void
221xmlDictCleanup(void) {
222 if (!xmlDictInitialized)
223 return;
224
225 xmlFreeRMutex(xmlDictMutex);
226
227 xmlDictInitialized = 0;
228}
229
230/*
Daniel Veillard81514ba2003-09-16 23:17:26 +0000231 * xmlDictAddString:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200232 * @dict: the dictionary
Daniel Veillard81514ba2003-09-16 23:17:26 +0000233 * @name: the name of the userdata
Daniel Veillard7c693da2012-07-25 16:32:18 +0800234 * @len: the length of the name
Daniel Veillard81514ba2003-09-16 23:17:26 +0000235 *
236 * Add the string to the array[s]
237 *
238 * Returns the pointer of the local string, or NULL in case of error.
239 */
240static const xmlChar *
Daniel Veillard7c693da2012-07-25 16:32:18 +0800241xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
Daniel Veillard81514ba2003-09-16 23:17:26 +0000242 xmlDictStringsPtr pool;
243 const xmlChar *ret;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800244 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
245 size_t limit = 0;
Daniel Veillard81514ba2003-09-16 23:17:26 +0000246
Daniel Veillard424785e2008-08-06 09:35:25 +0000247#ifdef DICT_DEBUG_PATTERNS
248 fprintf(stderr, "-");
249#endif
Daniel Veillard81514ba2003-09-16 23:17:26 +0000250 pool = dict->strings;
251 while (pool != NULL) {
252 if (pool->end - pool->free > namelen)
253 goto found_pool;
254 if (pool->size > size) size = pool->size;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800255 limit += pool->size;
Daniel Veillard81514ba2003-09-16 23:17:26 +0000256 pool = pool->next;
257 }
258 /*
259 * Not found, need to allocate
260 */
261 if (pool == NULL) {
Daniel Veillard7c693da2012-07-25 16:32:18 +0800262 if ((dict->limit > 0) && (limit > dict->limit)) {
263 return(NULL);
264 }
265
Daniel Veillard81514ba2003-09-16 23:17:26 +0000266 if (size == 0) size = 1000;
267 else size *= 4; /* exponential growth */
Daniel Veillard7c693da2012-07-25 16:32:18 +0800268 if (size < 4 * namelen)
Daniel Veillard81514ba2003-09-16 23:17:26 +0000269 size = 4 * namelen; /* just in case ! */
270 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
271 if (pool == NULL)
272 return(NULL);
273 pool->size = size;
274 pool->nbStrings = 0;
275 pool->free = &pool->array[0];
276 pool->end = &pool->array[size];
277 pool->next = dict->strings;
278 dict->strings = pool;
Daniel Veillard424785e2008-08-06 09:35:25 +0000279#ifdef DICT_DEBUG_PATTERNS
280 fprintf(stderr, "+");
281#endif
Daniel Veillard81514ba2003-09-16 23:17:26 +0000282 }
283found_pool:
284 ret = pool->free;
285 memcpy(pool->free, name, namelen);
286 pool->free += namelen;
287 *(pool->free++) = 0;
Daniel Veillard424785e2008-08-06 09:35:25 +0000288 pool->nbStrings++;
Daniel Veillard81514ba2003-09-16 23:17:26 +0000289 return(ret);
290}
291
292/*
Daniel Veillarde72c5082003-09-19 12:44:05 +0000293 * xmlDictAddQString:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200294 * @dict: the dictionary
Daniel Veillarde72c5082003-09-19 12:44:05 +0000295 * @prefix: the prefix of the userdata
Daniel Veillardffda65f2008-08-07 16:33:49 +0000296 * @plen: the prefix length
Daniel Veillarde72c5082003-09-19 12:44:05 +0000297 * @name: the name of the userdata
Daniel Veillard7c693da2012-07-25 16:32:18 +0800298 * @len: the length of the name
Daniel Veillarde72c5082003-09-19 12:44:05 +0000299 *
300 * Add the QName to the array[s]
301 *
302 * Returns the pointer of the local string, or NULL in case of error.
303 */
304static const xmlChar *
Daniel Veillard7c693da2012-07-25 16:32:18 +0800305xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
306 const xmlChar *name, unsigned int namelen)
Daniel Veillarde72c5082003-09-19 12:44:05 +0000307{
308 xmlDictStringsPtr pool;
309 const xmlChar *ret;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800310 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
311 size_t limit = 0;
Daniel Veillarde72c5082003-09-19 12:44:05 +0000312
313 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
Daniel Veillarde72c5082003-09-19 12:44:05 +0000314
Daniel Veillard424785e2008-08-06 09:35:25 +0000315#ifdef DICT_DEBUG_PATTERNS
316 fprintf(stderr, "=");
317#endif
Daniel Veillarde72c5082003-09-19 12:44:05 +0000318 pool = dict->strings;
319 while (pool != NULL) {
Daniel Veillardffda65f2008-08-07 16:33:49 +0000320 if (pool->end - pool->free > namelen + plen + 1)
Daniel Veillarde72c5082003-09-19 12:44:05 +0000321 goto found_pool;
322 if (pool->size > size) size = pool->size;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800323 limit += pool->size;
Daniel Veillarde72c5082003-09-19 12:44:05 +0000324 pool = pool->next;
325 }
326 /*
327 * Not found, need to allocate
328 */
329 if (pool == NULL) {
Daniel Veillard7c693da2012-07-25 16:32:18 +0800330 if ((dict->limit > 0) && (limit > dict->limit)) {
331 return(NULL);
332 }
333
Daniel Veillarde72c5082003-09-19 12:44:05 +0000334 if (size == 0) size = 1000;
335 else size *= 4; /* exponential growth */
Daniel Veillardffda65f2008-08-07 16:33:49 +0000336 if (size < 4 * (namelen + plen + 1))
337 size = 4 * (namelen + plen + 1); /* just in case ! */
Daniel Veillarde72c5082003-09-19 12:44:05 +0000338 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
339 if (pool == NULL)
340 return(NULL);
341 pool->size = size;
342 pool->nbStrings = 0;
343 pool->free = &pool->array[0];
344 pool->end = &pool->array[size];
345 pool->next = dict->strings;
346 dict->strings = pool;
Daniel Veillard424785e2008-08-06 09:35:25 +0000347#ifdef DICT_DEBUG_PATTERNS
348 fprintf(stderr, "+");
349#endif
Daniel Veillarde72c5082003-09-19 12:44:05 +0000350 }
351found_pool:
352 ret = pool->free;
353 memcpy(pool->free, prefix, plen);
354 pool->free += plen;
355 *(pool->free++) = ':';
Daniel Veillarde72c5082003-09-19 12:44:05 +0000356 memcpy(pool->free, name, namelen);
357 pool->free += namelen;
358 *(pool->free++) = 0;
Daniel Veillard424785e2008-08-06 09:35:25 +0000359 pool->nbStrings++;
Daniel Veillarde72c5082003-09-19 12:44:05 +0000360 return(ret);
361}
362
Daniel Veillard424785e2008-08-06 09:35:25 +0000363#ifdef WITH_BIG_KEY
Daniel Veillarde72c5082003-09-19 12:44:05 +0000364/*
Daniel Veillarde9100a52008-04-22 08:28:50 +0000365 * xmlDictComputeBigKey:
366 *
367 * Calculate a hash key using a good hash function that works well for
368 * larger hash table sizes.
369 *
Daniel Veillard424785e2008-08-06 09:35:25 +0000370 * Hash function by "One-at-a-Time Hash" see
Daniel Veillarde9100a52008-04-22 08:28:50 +0000371 * http://burtleburtle.net/bob/hash/doobs.html
372 */
Daniel Veillarde9100a52008-04-22 08:28:50 +0000373
374static uint32_t
Daniel Veillard8973d582012-02-04 19:07:44 +0800375xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
Daniel Veillard424785e2008-08-06 09:35:25 +0000376 uint32_t hash;
377 int i;
Daniel Veillarde9100a52008-04-22 08:28:50 +0000378
Daniel Veillard424785e2008-08-06 09:35:25 +0000379 if (namelen <= 0 || data == NULL) return(0);
Daniel Veillarde9100a52008-04-22 08:28:50 +0000380
Daniel Veillard8973d582012-02-04 19:07:44 +0800381 hash = seed;
Daniel Veillarde9100a52008-04-22 08:28:50 +0000382
Daniel Veillard424785e2008-08-06 09:35:25 +0000383 for (i = 0;i < namelen; i++) {
384 hash += data[i];
385 hash += (hash << 10);
386 hash ^= (hash >> 6);
Daniel Veillarde9100a52008-04-22 08:28:50 +0000387 }
Daniel Veillard424785e2008-08-06 09:35:25 +0000388 hash += (hash << 3);
389 hash ^= (hash >> 11);
390 hash += (hash << 15);
Daniel Veillarde9100a52008-04-22 08:28:50 +0000391
392 return hash;
393}
394
395/*
Daniel Veillard424785e2008-08-06 09:35:25 +0000396 * xmlDictComputeBigQKey:
397 *
398 * Calculate a hash key for two strings using a good hash function
399 * that works well for larger hash table sizes.
400 *
401 * Hash function by "One-at-a-Time Hash" see
402 * http://burtleburtle.net/bob/hash/doobs.html
403 *
404 * Neither of the two strings must be NULL.
405 */
406static unsigned long
Daniel Veillardffda65f2008-08-07 16:33:49 +0000407xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
Daniel Veillard8973d582012-02-04 19:07:44 +0800408 const xmlChar *name, int len, int seed)
Daniel Veillard424785e2008-08-06 09:35:25 +0000409{
410 uint32_t hash;
411 int i;
Daniel Veillard424785e2008-08-06 09:35:25 +0000412
Daniel Veillard8973d582012-02-04 19:07:44 +0800413 hash = seed;
Daniel Veillard424785e2008-08-06 09:35:25 +0000414
415 for (i = 0;i < plen; i++) {
416 hash += prefix[i];
417 hash += (hash << 10);
418 hash ^= (hash >> 6);
419 }
420 hash += ':';
421 hash += (hash << 10);
422 hash ^= (hash >> 6);
423
424 for (i = 0;i < len; i++) {
425 hash += name[i];
426 hash += (hash << 10);
427 hash ^= (hash >> 6);
428 }
429 hash += (hash << 3);
430 hash ^= (hash >> 11);
431 hash += (hash << 15);
432
433 return hash;
434}
435#endif /* WITH_BIG_KEY */
436
437/*
Daniel Veillarde9100a52008-04-22 08:28:50 +0000438 * xmlDictComputeFastKey:
439 *
440 * Calculate a hash key using a fast hash function that works well
441 * for low hash table fill.
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000442 */
443static unsigned long
Daniel Veillard8973d582012-02-04 19:07:44 +0800444xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
445 unsigned long value = seed;
Daniel Veillard424785e2008-08-06 09:35:25 +0000446
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000447 if (name == NULL) return(0);
Daniel Veillard4773df22004-01-23 13:15:13 +0000448 value = *name;
449 value <<= 5;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000450 if (namelen > 10) {
451 value += name[namelen - 1];
452 namelen = 10;
453 }
454 switch (namelen) {
455 case 10: value += name[9];
456 case 9: value += name[8];
457 case 8: value += name[7];
458 case 7: value += name[6];
459 case 6: value += name[5];
460 case 5: value += name[4];
461 case 4: value += name[3];
462 case 3: value += name[2];
463 case 2: value += name[1];
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000464 default: break;
465 }
Daniel Veillard4773df22004-01-23 13:15:13 +0000466 return(value);
Daniel Veillarde72c5082003-09-19 12:44:05 +0000467}
468
469/*
Daniel Veillarde9100a52008-04-22 08:28:50 +0000470 * xmlDictComputeFastQKey:
471 *
472 * Calculate a hash key for two strings using a fast hash function
473 * that works well for low hash table fill.
474 *
475 * Neither of the two strings must be NULL.
Daniel Veillarde72c5082003-09-19 12:44:05 +0000476 */
477static unsigned long
Daniel Veillardffda65f2008-08-07 16:33:49 +0000478xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
Daniel Veillard8973d582012-02-04 19:07:44 +0800479 const xmlChar *name, int len, int seed)
Daniel Veillarde72c5082003-09-19 12:44:05 +0000480{
Daniel Veillard8973d582012-02-04 19:07:44 +0800481 unsigned long value = (unsigned long) seed;
Daniel Veillarde72c5082003-09-19 12:44:05 +0000482
Daniel Veillarde72c5082003-09-19 12:44:05 +0000483 if (plen == 0)
484 value += 30 * (unsigned long) ':';
485 else
486 value += 30 * (*prefix);
Daniel Veillard424785e2008-08-06 09:35:25 +0000487
Daniel Veillarde72c5082003-09-19 12:44:05 +0000488 if (len > 10) {
David Drysdale6360a312015-11-20 10:47:12 +0800489 int offset = len - (plen + 1 + 1);
490 if (offset < 0)
491 offset = len - (10 + 1);
492 value += name[offset];
Daniel Veillarde72c5082003-09-19 12:44:05 +0000493 len = 10;
494 if (plen > 10)
495 plen = 10;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000496 }
Daniel Veillarde72c5082003-09-19 12:44:05 +0000497 switch (plen) {
498 case 10: value += prefix[9];
499 case 9: value += prefix[8];
500 case 8: value += prefix[7];
501 case 7: value += prefix[6];
502 case 6: value += prefix[5];
503 case 5: value += prefix[4];
504 case 4: value += prefix[3];
505 case 3: value += prefix[2];
506 case 2: value += prefix[1];
507 case 1: value += prefix[0];
508 default: break;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000509 }
Daniel Veillarde72c5082003-09-19 12:44:05 +0000510 len -= plen;
511 if (len > 0) {
512 value += (unsigned long) ':';
513 len--;
514 }
515 switch (len) {
516 case 10: value += name[9];
517 case 9: value += name[8];
518 case 8: value += name[7];
519 case 7: value += name[6];
520 case 6: value += name[5];
521 case 5: value += name[4];
522 case 4: value += name[3];
523 case 3: value += name[2];
524 case 2: value += name[1];
525 case 1: value += name[0];
526 default: break;
527 }
Daniel Veillard4773df22004-01-23 13:15:13 +0000528 return(value);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000529}
530
531/**
532 * xmlDictCreate:
533 *
534 * Create a new dictionary
535 *
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200536 * Returns the newly created dictionary, or NULL if an error occured.
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000537 */
538xmlDictPtr
539xmlDictCreate(void) {
540 xmlDictPtr dict;
Daniel Veillard14412512005-01-21 23:53:26 +0000541
542 if (!xmlDictInitialized)
Daniel Veillard5fe9e9e2013-04-05 23:10:41 +0800543 if (!__xmlInitializeDict())
Daniel Veillard14412512005-01-21 23:53:26 +0000544 return(NULL);
Daniel Veillard424785e2008-08-06 09:35:25 +0000545
546#ifdef DICT_DEBUG_PATTERNS
547 fprintf(stderr, "C");
548#endif
549
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000550 dict = xmlMalloc(sizeof(xmlDict));
551 if (dict) {
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000552 dict->ref_counter = 1;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800553 dict->limit = 0;
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000554
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000555 dict->size = MIN_DICT_SIZE;
556 dict->nbElems = 0;
557 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
Daniel Veillard81514ba2003-09-16 23:17:26 +0000558 dict->strings = NULL;
Daniel Veillard4773df22004-01-23 13:15:13 +0000559 dict->subdict = NULL;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000560 if (dict->dict) {
Daniel Veillardb242b082008-02-08 09:56:31 +0000561 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
Daniel Veillard8973d582012-02-04 19:07:44 +0800562#ifdef DICT_RANDOMIZATION
Daniel Veillard379ebc12012-05-18 15:41:31 +0800563 dict->seed = __xmlRandom();
Daniel Veillard8973d582012-02-04 19:07:44 +0800564#else
565 dict->seed = 0;
566#endif
Daniel Veillardb242b082008-02-08 09:56:31 +0000567 return(dict);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000568 }
569 xmlFree(dict);
570 }
571 return(NULL);
572}
573
574/**
Daniel Veillard4773df22004-01-23 13:15:13 +0000575 * xmlDictCreateSub:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200576 * @sub: an existing dictionary
Daniel Veillard4773df22004-01-23 13:15:13 +0000577 *
578 * Create a new dictionary, inheriting strings from the read-only
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200579 * dictionary @sub. On lookup, strings are first searched in the
580 * new dictionary, then in @sub, and if not found are created in the
581 * new dictionary.
Daniel Veillard4773df22004-01-23 13:15:13 +0000582 *
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200583 * Returns the newly created dictionary, or NULL if an error occured.
Daniel Veillard4773df22004-01-23 13:15:13 +0000584 */
585xmlDictPtr
586xmlDictCreateSub(xmlDictPtr sub) {
587 xmlDictPtr dict = xmlDictCreate();
Daniel Veillard424785e2008-08-06 09:35:25 +0000588
Daniel Veillard4773df22004-01-23 13:15:13 +0000589 if ((dict != NULL) && (sub != NULL)) {
Daniel Veillard424785e2008-08-06 09:35:25 +0000590#ifdef DICT_DEBUG_PATTERNS
591 fprintf(stderr, "R");
592#endif
Daniel Veillard8973d582012-02-04 19:07:44 +0800593 dict->seed = sub->seed;
Daniel Veillard4773df22004-01-23 13:15:13 +0000594 dict->subdict = sub;
595 xmlDictReference(dict->subdict);
596 }
597 return(dict);
598}
599
600/**
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000601 * xmlDictReference:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200602 * @dict: the dictionary
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000603 *
604 * Increment the reference counter of a dictionary
605 *
606 * Returns 0 in case of success and -1 in case of error
607 */
608int
609xmlDictReference(xmlDictPtr dict) {
Daniel Veillard14412512005-01-21 23:53:26 +0000610 if (!xmlDictInitialized)
Daniel Veillard5fe9e9e2013-04-05 23:10:41 +0800611 if (!__xmlInitializeDict())
Daniel Veillard14412512005-01-21 23:53:26 +0000612 return(-1);
613
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000614 if (dict == NULL) return -1;
Daniel Veillard14412512005-01-21 23:53:26 +0000615 xmlRMutexLock(xmlDictMutex);
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000616 dict->ref_counter++;
Daniel Veillard14412512005-01-21 23:53:26 +0000617 xmlRMutexUnlock(xmlDictMutex);
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000618 return(0);
619}
620
621/**
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000622 * xmlDictGrow:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200623 * @dict: the dictionary
624 * @size: the new size of the dictionary
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000625 *
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200626 * resize the dictionary
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000627 *
628 * Returns 0 in case of success, -1 in case of failure
629 */
630static int
Daniel Veillard7c693da2012-07-25 16:32:18 +0800631xmlDictGrow(xmlDictPtr dict, size_t size) {
Daniel Veillardd68f8912008-08-08 10:09:19 +0000632 unsigned long key, okey;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800633 size_t oldsize, i;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000634 xmlDictEntryPtr iter, next;
635 struct _xmlDictEntry *olddict;
636#ifdef DEBUG_GROW
637 unsigned long nbElem = 0;
638#endif
Daniel Veillardffda65f2008-08-07 16:33:49 +0000639 int ret = 0;
Daniel Veillardd68f8912008-08-08 10:09:19 +0000640 int keep_keys = 1;
Daniel Veillard424785e2008-08-06 09:35:25 +0000641
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000642 if (dict == NULL)
643 return(-1);
644 if (size < 8)
645 return(-1);
646 if (size > 8 * 2048)
647 return(-1);
648
Daniel Veillard424785e2008-08-06 09:35:25 +0000649#ifdef DICT_DEBUG_PATTERNS
650 fprintf(stderr, "*");
651#endif
652
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000653 oldsize = dict->size;
654 olddict = dict->dict;
655 if (olddict == NULL)
656 return(-1);
Daniel Veillardd68f8912008-08-08 10:09:19 +0000657 if (oldsize == MIN_DICT_SIZE)
658 keep_keys = 0;
Daniel Veillard424785e2008-08-06 09:35:25 +0000659
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000660 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
661 if (dict->dict == NULL) {
662 dict->dict = olddict;
663 return(-1);
664 }
665 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
666 dict->size = size;
667
668 /* If the two loops are merged, there would be situations where
Daniel Veillard424785e2008-08-06 09:35:25 +0000669 a new entry needs to allocated and data copied into it from
Daniel Veillardffda65f2008-08-07 16:33:49 +0000670 the main dict. It is nicer to run through the array twice, first
671 copying all the elements in the main array (less probability of
672 allocate) and then the rest, so we only free in the second loop.
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000673 */
674 for (i = 0; i < oldsize; i++) {
Daniel Veillard424785e2008-08-06 09:35:25 +0000675 if (olddict[i].valid == 0)
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000676 continue;
Daniel Veillardd68f8912008-08-08 10:09:19 +0000677
678 if (keep_keys)
679 okey = olddict[i].okey;
680 else
681 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
682 key = okey % dict->size;
683
Daniel Veillardffda65f2008-08-07 16:33:49 +0000684 if (dict->dict[key].valid == 0) {
685 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
686 dict->dict[key].next = NULL;
Daniel Veillardd68f8912008-08-08 10:09:19 +0000687 dict->dict[key].okey = okey;
Daniel Veillardffda65f2008-08-07 16:33:49 +0000688 } else {
689 xmlDictEntryPtr entry;
690
691 entry = xmlMalloc(sizeof(xmlDictEntry));
692 if (entry != NULL) {
693 entry->name = olddict[i].name;
694 entry->len = olddict[i].len;
Daniel Veillardd68f8912008-08-08 10:09:19 +0000695 entry->okey = okey;
Daniel Veillardffda65f2008-08-07 16:33:49 +0000696 entry->next = dict->dict[key].next;
697 entry->valid = 1;
698 dict->dict[key].next = entry;
699 } else {
Daniel Veillardd68f8912008-08-08 10:09:19 +0000700 /*
701 * we don't have much ways to alert from herei
702 * result is loosing an entry and unicity garantee
703 */
Daniel Veillardffda65f2008-08-07 16:33:49 +0000704 ret = -1;
705 }
706 }
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000707#ifdef DEBUG_GROW
708 nbElem++;
709#endif
710 }
711
712 for (i = 0; i < oldsize; i++) {
713 iter = olddict[i].next;
714 while (iter) {
715 next = iter->next;
716
717 /*
718 * put back the entry in the new dict
719 */
720
Daniel Veillardd68f8912008-08-08 10:09:19 +0000721 if (keep_keys)
722 okey = iter->okey;
723 else
724 okey = xmlDictComputeKey(dict, iter->name, iter->len);
725 key = okey % dict->size;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000726 if (dict->dict[key].valid == 0) {
727 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
728 dict->dict[key].next = NULL;
729 dict->dict[key].valid = 1;
Daniel Veillardd68f8912008-08-08 10:09:19 +0000730 dict->dict[key].okey = okey;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000731 xmlFree(iter);
732 } else {
Daniel Veillard424785e2008-08-06 09:35:25 +0000733 iter->next = dict->dict[key].next;
Daniel Veillardd68f8912008-08-08 10:09:19 +0000734 iter->okey = okey;
Daniel Veillard424785e2008-08-06 09:35:25 +0000735 dict->dict[key].next = iter;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000736 }
737
738#ifdef DEBUG_GROW
739 nbElem++;
740#endif
741
742 iter = next;
743 }
744 }
745
746 xmlFree(olddict);
747
748#ifdef DEBUG_GROW
749 xmlGenericError(xmlGenericErrorContext,
Daniel Veillard7c693da2012-07-25 16:32:18 +0800750 "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000751#endif
752
Daniel Veillardffda65f2008-08-07 16:33:49 +0000753 return(ret);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000754}
755
756/**
757 * xmlDictFree:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200758 * @dict: the dictionary
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000759 *
760 * Free the hash @dict and its contents. The userdata is
761 * deallocated with @f if provided.
762 */
763void
764xmlDictFree(xmlDictPtr dict) {
Daniel Veillard7c693da2012-07-25 16:32:18 +0800765 size_t i;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000766 xmlDictEntryPtr iter;
767 xmlDictEntryPtr next;
768 int inside_dict = 0;
Daniel Veillard81514ba2003-09-16 23:17:26 +0000769 xmlDictStringsPtr pool, nextp;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000770
771 if (dict == NULL)
772 return;
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000773
Daniel Veillard14412512005-01-21 23:53:26 +0000774 if (!xmlDictInitialized)
Daniel Veillard5fe9e9e2013-04-05 23:10:41 +0800775 if (!__xmlInitializeDict())
Daniel Veillard14412512005-01-21 23:53:26 +0000776 return;
777
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000778 /* decrement the counter, it may be shared by a parser and docs */
Daniel Veillard14412512005-01-21 23:53:26 +0000779 xmlRMutexLock(xmlDictMutex);
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000780 dict->ref_counter--;
Daniel Veillard1bb16a12005-01-21 16:55:41 +0000781 if (dict->ref_counter > 0) {
Daniel Veillard14412512005-01-21 23:53:26 +0000782 xmlRMutexUnlock(xmlDictMutex);
Daniel Veillard1bb16a12005-01-21 16:55:41 +0000783 return;
784 }
785
Daniel Veillard14412512005-01-21 23:53:26 +0000786 xmlRMutexUnlock(xmlDictMutex);
Daniel Veillarde96a2a42003-09-24 21:23:56 +0000787
Daniel Veillard4773df22004-01-23 13:15:13 +0000788 if (dict->subdict != NULL) {
789 xmlDictFree(dict->subdict);
790 }
791
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000792 if (dict->dict) {
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000793 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000794 iter = &(dict->dict[i]);
795 if (iter->valid == 0)
796 continue;
797 inside_dict = 1;
798 while (iter) {
799 next = iter->next;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000800 if (!inside_dict)
801 xmlFree(iter);
Daniel Veillard6155d8a2003-08-19 15:01:28 +0000802 dict->nbElems--;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000803 inside_dict = 0;
804 iter = next;
805 }
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000806 }
807 xmlFree(dict->dict);
808 }
Daniel Veillard81514ba2003-09-16 23:17:26 +0000809 pool = dict->strings;
810 while (pool != NULL) {
811 nextp = pool->next;
812 xmlFree(pool);
813 pool = nextp;
814 }
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000815 xmlFree(dict);
816}
817
818/**
819 * xmlDictLookup:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200820 * @dict: the dictionary
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000821 * @name: the name of the userdata
Daniel Veillard0fb18932003-09-07 09:14:37 +0000822 * @len: the length of the name, if -1 it is recomputed
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000823 *
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200824 * Add the @name to the dictionary @dict if not present.
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000825 *
826 * Returns the internal copy of the name or NULL in case of internal error
827 */
828const xmlChar *
829xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
Daniel Veillard4773df22004-01-23 13:15:13 +0000830 unsigned long key, okey, nbi = 0;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000831 xmlDictEntryPtr entry;
832 xmlDictEntryPtr insert;
833 const xmlChar *ret;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800834 unsigned int l;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000835
Daniel Veillard0fb18932003-09-07 09:14:37 +0000836 if ((dict == NULL) || (name == NULL))
837 return(NULL);
838
839 if (len < 0)
Daniel Veillard7c693da2012-07-25 16:32:18 +0800840 l = strlen((const char *) name);
841 else
842 l = len;
843
844 if (((dict->limit > 0) && (l >= dict->limit)) ||
845 (l > INT_MAX / 2))
846 return(NULL);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000847
848 /*
849 * Check for duplicate and insertion location.
850 */
Daniel Veillard7c693da2012-07-25 16:32:18 +0800851 okey = xmlDictComputeKey(dict, name, l);
Daniel Veillard4773df22004-01-23 13:15:13 +0000852 key = okey % dict->size;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000853 if (dict->dict[key].valid == 0) {
854 insert = NULL;
855 } else {
856 for (insert = &(dict->dict[key]); insert->next != NULL;
857 insert = insert->next) {
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000858#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +0800859 if ((insert->okey == okey) && (insert->len == l)) {
860 if (!memcmp(insert->name, name, l))
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000861 return(insert->name);
862 }
863#else
Patrick Ganstererfd4f6fd2012-08-13 17:54:20 +0800864 if ((insert->okey == okey) && (insert->len == l) &&
Daniel Veillard7c693da2012-07-25 16:32:18 +0800865 (!xmlStrncmp(insert->name, name, l)))
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000866 return(insert->name);
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000867#endif
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000868 nbi++;
869 }
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000870#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +0800871 if ((insert->okey == okey) && (insert->len == l)) {
872 if (!memcmp(insert->name, name, l))
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000873 return(insert->name);
874 }
875#else
Daniel Veillard7c693da2012-07-25 16:32:18 +0800876 if ((insert->okey == okey) && (insert->len == l) &&
877 (!xmlStrncmp(insert->name, name, l)))
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000878 return(insert->name);
Daniel Veillardc82c57e2004-01-12 16:24:34 +0000879#endif
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000880 }
881
Daniel Veillard4773df22004-01-23 13:15:13 +0000882 if (dict->subdict) {
Daniel Veillard424785e2008-08-06 09:35:25 +0000883 unsigned long skey;
884
885 /* we cannot always reuse the same okey for the subdict */
886 if (((dict->size == MIN_DICT_SIZE) &&
887 (dict->subdict->size != MIN_DICT_SIZE)) ||
888 ((dict->size != MIN_DICT_SIZE) &&
889 (dict->subdict->size == MIN_DICT_SIZE)))
Daniel Veillard7c693da2012-07-25 16:32:18 +0800890 skey = xmlDictComputeKey(dict->subdict, name, l);
Daniel Veillard424785e2008-08-06 09:35:25 +0000891 else
892 skey = okey;
893
894 key = skey % dict->subdict->size;
Daniel Veillard4773df22004-01-23 13:15:13 +0000895 if (dict->subdict->dict[key].valid != 0) {
896 xmlDictEntryPtr tmp;
897
898 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
899 tmp = tmp->next) {
900#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +0800901 if ((tmp->okey == skey) && (tmp->len == l)) {
902 if (!memcmp(tmp->name, name, l))
Daniel Veillard4773df22004-01-23 13:15:13 +0000903 return(tmp->name);
904 }
905#else
Daniel Veillard7c693da2012-07-25 16:32:18 +0800906 if ((tmp->okey == skey) && (tmp->len == l) &&
907 (!xmlStrncmp(tmp->name, name, l)))
Daniel Veillard4773df22004-01-23 13:15:13 +0000908 return(tmp->name);
909#endif
910 nbi++;
911 }
912#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +0800913 if ((tmp->okey == skey) && (tmp->len == l)) {
914 if (!memcmp(tmp->name, name, l))
Daniel Veillard4773df22004-01-23 13:15:13 +0000915 return(tmp->name);
916 }
917#else
Daniel Veillard7c693da2012-07-25 16:32:18 +0800918 if ((tmp->okey == skey) && (tmp->len == l) &&
919 (!xmlStrncmp(tmp->name, name, l)))
Daniel Veillard4773df22004-01-23 13:15:13 +0000920 return(tmp->name);
921#endif
922 }
923 key = okey % dict->size;
924 }
925
Daniel Veillard7c693da2012-07-25 16:32:18 +0800926 ret = xmlDictAddString(dict, name, l);
Daniel Veillard81514ba2003-09-16 23:17:26 +0000927 if (ret == NULL)
928 return(NULL);
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000929 if (insert == NULL) {
930 entry = &(dict->dict[key]);
931 } else {
932 entry = xmlMalloc(sizeof(xmlDictEntry));
933 if (entry == NULL)
934 return(NULL);
935 }
Daniel Veillard81514ba2003-09-16 23:17:26 +0000936 entry->name = ret;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800937 entry->len = l;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000938 entry->next = NULL;
939 entry->valid = 1;
Daniel Veillardd68f8912008-08-08 10:09:19 +0000940 entry->okey = okey;
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000941
942
Daniel Veillard7c693da2012-07-25 16:32:18 +0800943 if (insert != NULL)
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000944 insert->next = entry;
945
946 dict->nbElems++;
947
948 if ((nbi > MAX_HASH_LEN) &&
Daniel Veillardffda65f2008-08-07 16:33:49 +0000949 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
950 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
951 return(NULL);
952 }
Daniel Veillard2fdbd322003-08-18 12:15:38 +0000953 /* Note that entry may have been freed at this point by xmlDictGrow */
954
955 return(ret);
956}
957
958/**
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000959 * xmlDictExists:
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200960 * @dict: the dictionary
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000961 * @name: the name of the userdata
962 * @len: the length of the name, if -1 it is recomputed
963 *
Jan Pokornýbb654fe2016-04-13 16:56:07 +0200964 * Check if the @name exists in the dictionary @dict.
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000965 *
966 * Returns the internal copy of the name or NULL if not found.
967 */
968const xmlChar *
969xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
970 unsigned long key, okey, nbi = 0;
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000971 xmlDictEntryPtr insert;
Daniel Veillard7c693da2012-07-25 16:32:18 +0800972 unsigned int l;
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000973
974 if ((dict == NULL) || (name == NULL))
975 return(NULL);
976
977 if (len < 0)
Daniel Veillard7c693da2012-07-25 16:32:18 +0800978 l = strlen((const char *) name);
979 else
980 l = len;
981 if (((dict->limit > 0) && (l >= dict->limit)) ||
982 (l > INT_MAX / 2))
983 return(NULL);
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000984
985 /*
986 * Check for duplicate and insertion location.
987 */
Daniel Veillard7c693da2012-07-25 16:32:18 +0800988 okey = xmlDictComputeKey(dict, name, l);
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000989 key = okey % dict->size;
990 if (dict->dict[key].valid == 0) {
991 insert = NULL;
992 } else {
993 for (insert = &(dict->dict[key]); insert->next != NULL;
994 insert = insert->next) {
995#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +0800996 if ((insert->okey == okey) && (insert->len == l)) {
997 if (!memcmp(insert->name, name, l))
Daniel Veillard6bb3e862004-11-24 12:39:00 +0000998 return(insert->name);
999 }
1000#else
Daniel Veillard7c693da2012-07-25 16:32:18 +08001001 if ((insert->okey == okey) && (insert->len == l) &&
1002 (!xmlStrncmp(insert->name, name, l)))
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001003 return(insert->name);
1004#endif
1005 nbi++;
1006 }
1007#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +08001008 if ((insert->okey == okey) && (insert->len == l)) {
1009 if (!memcmp(insert->name, name, l))
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001010 return(insert->name);
1011 }
1012#else
Daniel Veillard7c693da2012-07-25 16:32:18 +08001013 if ((insert->okey == okey) && (insert->len == l) &&
1014 (!xmlStrncmp(insert->name, name, l)))
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001015 return(insert->name);
1016#endif
1017 }
1018
1019 if (dict->subdict) {
Daniel Veillard424785e2008-08-06 09:35:25 +00001020 unsigned long skey;
1021
1022 /* we cannot always reuse the same okey for the subdict */
1023 if (((dict->size == MIN_DICT_SIZE) &&
1024 (dict->subdict->size != MIN_DICT_SIZE)) ||
1025 ((dict->size != MIN_DICT_SIZE) &&
1026 (dict->subdict->size == MIN_DICT_SIZE)))
Daniel Veillard7c693da2012-07-25 16:32:18 +08001027 skey = xmlDictComputeKey(dict->subdict, name, l);
Daniel Veillard424785e2008-08-06 09:35:25 +00001028 else
1029 skey = okey;
1030
1031 key = skey % dict->subdict->size;
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001032 if (dict->subdict->dict[key].valid != 0) {
1033 xmlDictEntryPtr tmp;
1034
1035 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1036 tmp = tmp->next) {
1037#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +08001038 if ((tmp->okey == skey) && (tmp->len == l)) {
1039 if (!memcmp(tmp->name, name, l))
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001040 return(tmp->name);
1041 }
1042#else
Daniel Veillard7c693da2012-07-25 16:32:18 +08001043 if ((tmp->okey == skey) && (tmp->len == l) &&
1044 (!xmlStrncmp(tmp->name, name, l)))
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001045 return(tmp->name);
1046#endif
1047 nbi++;
1048 }
1049#ifdef __GNUC__
Daniel Veillard7c693da2012-07-25 16:32:18 +08001050 if ((tmp->okey == skey) && (tmp->len == l)) {
1051 if (!memcmp(tmp->name, name, l))
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001052 return(tmp->name);
1053 }
1054#else
Daniel Veillard7c693da2012-07-25 16:32:18 +08001055 if ((tmp->okey == skey) && (tmp->len == l) &&
1056 (!xmlStrncmp(tmp->name, name, l)))
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001057 return(tmp->name);
1058#endif
1059 }
Daniel Veillard6bb3e862004-11-24 12:39:00 +00001060 }
1061
1062 /* not found */
1063 return(NULL);
1064}
1065
1066/**
Daniel Veillarde72c5082003-09-19 12:44:05 +00001067 * xmlDictQLookup:
Jan Pokornýbb654fe2016-04-13 16:56:07 +02001068 * @dict: the dictionary
Daniel Veillardd68f8912008-08-08 10:09:19 +00001069 * @prefix: the prefix
Daniel Veillarde72c5082003-09-19 12:44:05 +00001070 * @name: the name
1071 *
1072 * Add the QName @prefix:@name to the hash @dict if not present.
1073 *
1074 * Returns the internal copy of the QName or NULL in case of internal error
1075 */
1076const xmlChar *
1077xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
Daniel Veillard4773df22004-01-23 13:15:13 +00001078 unsigned long okey, key, nbi = 0;
Daniel Veillarde72c5082003-09-19 12:44:05 +00001079 xmlDictEntryPtr entry;
1080 xmlDictEntryPtr insert;
1081 const xmlChar *ret;
Daniel Veillard7c693da2012-07-25 16:32:18 +08001082 unsigned int len, plen, l;
Daniel Veillarde72c5082003-09-19 12:44:05 +00001083
1084 if ((dict == NULL) || (name == NULL))
1085 return(NULL);
Daniel Veillardffda65f2008-08-07 16:33:49 +00001086 if (prefix == NULL)
1087 return(xmlDictLookup(dict, name, -1));
Daniel Veillarde72c5082003-09-19 12:44:05 +00001088
Daniel Veillardffda65f2008-08-07 16:33:49 +00001089 l = len = strlen((const char *) name);
1090 plen = strlen((const char *) prefix);
1091 len += 1 + plen;
Daniel Veillarde72c5082003-09-19 12:44:05 +00001092
1093 /*
1094 * Check for duplicate and insertion location.
1095 */
Daniel Veillardffda65f2008-08-07 16:33:49 +00001096 okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
Daniel Veillard4773df22004-01-23 13:15:13 +00001097 key = okey % dict->size;
Daniel Veillarde72c5082003-09-19 12:44:05 +00001098 if (dict->dict[key].valid == 0) {
1099 insert = NULL;
1100 } else {
1101 for (insert = &(dict->dict[key]); insert->next != NULL;
1102 insert = insert->next) {
Daniel Veillardd68f8912008-08-08 10:09:19 +00001103 if ((insert->okey == okey) && (insert->len == len) &&
Daniel Veillarde72c5082003-09-19 12:44:05 +00001104 (xmlStrQEqual(prefix, name, insert->name)))
1105 return(insert->name);
1106 nbi++;
1107 }
Daniel Veillardd68f8912008-08-08 10:09:19 +00001108 if ((insert->okey == okey) && (insert->len == len) &&
Daniel Veillarde72c5082003-09-19 12:44:05 +00001109 (xmlStrQEqual(prefix, name, insert->name)))
1110 return(insert->name);
1111 }
1112
Daniel Veillard4773df22004-01-23 13:15:13 +00001113 if (dict->subdict) {
Daniel Veillard424785e2008-08-06 09:35:25 +00001114 unsigned long skey;
1115
1116 /* we cannot always reuse the same okey for the subdict */
1117 if (((dict->size == MIN_DICT_SIZE) &&
1118 (dict->subdict->size != MIN_DICT_SIZE)) ||
1119 ((dict->size != MIN_DICT_SIZE) &&
1120 (dict->subdict->size == MIN_DICT_SIZE)))
Daniel Veillardffda65f2008-08-07 16:33:49 +00001121 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
Daniel Veillard424785e2008-08-06 09:35:25 +00001122 else
1123 skey = okey;
1124
1125 key = skey % dict->subdict->size;
Daniel Veillard4773df22004-01-23 13:15:13 +00001126 if (dict->subdict->dict[key].valid != 0) {
1127 xmlDictEntryPtr tmp;
1128 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
1129 tmp = tmp->next) {
Daniel Veillardd68f8912008-08-08 10:09:19 +00001130 if ((tmp->okey == skey) && (tmp->len == len) &&
Daniel Veillard4773df22004-01-23 13:15:13 +00001131 (xmlStrQEqual(prefix, name, tmp->name)))
1132 return(tmp->name);
1133 nbi++;
1134 }
Daniel Veillardd68f8912008-08-08 10:09:19 +00001135 if ((tmp->okey == skey) && (tmp->len == len) &&
Daniel Veillard4773df22004-01-23 13:15:13 +00001136 (xmlStrQEqual(prefix, name, tmp->name)))
1137 return(tmp->name);
1138 }
1139 key = okey % dict->size;
1140 }
1141
Daniel Veillardffda65f2008-08-07 16:33:49 +00001142 ret = xmlDictAddQString(dict, prefix, plen, name, l);
Daniel Veillarde72c5082003-09-19 12:44:05 +00001143 if (ret == NULL)
1144 return(NULL);
1145 if (insert == NULL) {
1146 entry = &(dict->dict[key]);
1147 } else {
1148 entry = xmlMalloc(sizeof(xmlDictEntry));
1149 if (entry == NULL)
1150 return(NULL);
1151 }
1152 entry->name = ret;
1153 entry->len = len;
1154 entry->next = NULL;
1155 entry->valid = 1;
Daniel Veillardd68f8912008-08-08 10:09:19 +00001156 entry->okey = okey;
Daniel Veillarde72c5082003-09-19 12:44:05 +00001157
Daniel Veillard7c693da2012-07-25 16:32:18 +08001158 if (insert != NULL)
Daniel Veillarde72c5082003-09-19 12:44:05 +00001159 insert->next = entry;
1160
1161 dict->nbElems++;
1162
1163 if ((nbi > MAX_HASH_LEN) &&
1164 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
1165 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
1166 /* Note that entry may have been freed at this point by xmlDictGrow */
1167
1168 return(ret);
1169}
1170
1171/**
Daniel Veillard81514ba2003-09-16 23:17:26 +00001172 * xmlDictOwns:
Jan Pokornýbb654fe2016-04-13 16:56:07 +02001173 * @dict: the dictionary
Daniel Veillard81514ba2003-09-16 23:17:26 +00001174 * @str: the string
1175 *
1176 * check if a string is owned by the disctionary
1177 *
1178 * Returns 1 if true, 0 if false and -1 in case of error
1179 * -1 in case of error
1180 */
1181int
1182xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
1183 xmlDictStringsPtr pool;
1184
1185 if ((dict == NULL) || (str == NULL))
1186 return(-1);
1187 pool = dict->strings;
1188 while (pool != NULL) {
William M. Brackbf5cf212004-08-31 06:47:17 +00001189 if ((str >= &pool->array[0]) && (str <= pool->free))
Daniel Veillard81514ba2003-09-16 23:17:26 +00001190 return(1);
1191 pool = pool->next;
1192 }
Daniel Veillard4773df22004-01-23 13:15:13 +00001193 if (dict->subdict)
1194 return(xmlDictOwns(dict->subdict, str));
Daniel Veillard81514ba2003-09-16 23:17:26 +00001195 return(0);
1196}
Daniel Veillarde96a2a42003-09-24 21:23:56 +00001197
Daniel Veillard81514ba2003-09-16 23:17:26 +00001198/**
Daniel Veillard2fdbd322003-08-18 12:15:38 +00001199 * xmlDictSize:
Jan Pokornýbb654fe2016-04-13 16:56:07 +02001200 * @dict: the dictionary
Daniel Veillard2fdbd322003-08-18 12:15:38 +00001201 *
1202 * Query the number of elements installed in the hash @dict.
1203 *
Jan Pokornýbb654fe2016-04-13 16:56:07 +02001204 * Returns the number of elements in the dictionary or
Daniel Veillard2fdbd322003-08-18 12:15:38 +00001205 * -1 in case of error
1206 */
1207int
1208xmlDictSize(xmlDictPtr dict) {
1209 if (dict == NULL)
1210 return(-1);
Daniel Veillard4773df22004-01-23 13:15:13 +00001211 if (dict->subdict)
1212 return(dict->nbElems + dict->subdict->nbElems);
Daniel Veillard2fdbd322003-08-18 12:15:38 +00001213 return(dict->nbElems);
1214}
1215
Daniel Veillard7c693da2012-07-25 16:32:18 +08001216/**
1217 * xmlDictSetLimit:
Jan Pokornýbb654fe2016-04-13 16:56:07 +02001218 * @dict: the dictionary
Daniel Veillard7c693da2012-07-25 16:32:18 +08001219 * @limit: the limit in bytes
1220 *
1221 * Set a size limit for the dictionary
1222 * Added in 2.9.0
1223 *
1224 * Returns the previous limit of the dictionary or 0
1225 */
1226size_t
1227xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
1228 size_t ret;
1229
1230 if (dict == NULL)
1231 return(0);
1232 ret = dict->limit;
1233 dict->limit = limit;
1234 return(ret);
1235}
1236
1237/**
1238 * xmlDictGetUsage:
Jan Pokornýbb654fe2016-04-13 16:56:07 +02001239 * @dict: the dictionary
Daniel Veillard7c693da2012-07-25 16:32:18 +08001240 *
1241 * Get how much memory is used by a dictionary for strings
1242 * Added in 2.9.0
1243 *
1244 * Returns the amount of strings allocated
1245 */
1246size_t
1247xmlDictGetUsage(xmlDictPtr dict) {
1248 xmlDictStringsPtr pool;
1249 size_t limit = 0;
1250
1251 if (dict == NULL)
1252 return(0);
1253 pool = dict->strings;
1254 while (pool != NULL) {
1255 limit += pool->size;
1256 pool = pool->next;
1257 }
1258 return(limit);
1259}
Daniel Veillard2fdbd322003-08-18 12:15:38 +00001260
Daniel Veillard5d4644e2005-04-01 13:11:58 +00001261#define bottom_dict
1262#include "elfgcchack.h"