Paul Cercueil / libxml2

Important changes to repositories hosted on mbed.com

Mbed hosted mercurial repositories are deprecated and are due to be permanently deleted in July 2026.

To keep a copy of this software download the repository Zip archive or clone locally using Mercurial.

It is also possible to export all your personal repositories from the account settings page.

Dependents:   libiio

dict.c@1:26f20484cbdc, 2016-08-25 (annotated)

Committer:
pcercuei
Date:
Thu Aug 25 10:07:34 2016 +0000
Revision:
1:26f20484cbdc
Parent:
0:03b5121a232e 
Add config.h and dummy.c containing empty functions

Who changed what in which revision?

UserRevisionLine numberNew contents of line
pcercuei 0:03b5121a232e 1 /*
pcercuei 0:03b5121a232e 2 * dict.c: dictionary of reusable strings, just used to avoid allocation
pcercuei 0:03b5121a232e 3 * and freeing operations.
pcercuei 0:03b5121a232e 4 *
pcercuei 0:03b5121a232e 5 * Copyright (C) 2003-2012 Daniel Veillard.
pcercuei 0:03b5121a232e 6 *
pcercuei 0:03b5121a232e 7 * Permission to use, copy, modify, and distribute this software for any
pcercuei 0:03b5121a232e 8 * purpose with or without fee is hereby granted, provided that the above
pcercuei 0:03b5121a232e 9 * copyright notice and this permission notice appear in all copies.
pcercuei 0:03b5121a232e 10 *
pcercuei 0:03b5121a232e 11 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
pcercuei 0:03b5121a232e 12 * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
pcercuei 0:03b5121a232e 13 * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND
pcercuei 0:03b5121a232e 14 * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER.
pcercuei 0:03b5121a232e 15 *
pcercuei 0:03b5121a232e 16 * Author: daniel@veillard.com
pcercuei 0:03b5121a232e 17 */
pcercuei 0:03b5121a232e 18
pcercuei 0:03b5121a232e 19 #define IN_LIBXML
pcercuei 0:03b5121a232e 20 #include "libxml.h"
pcercuei 0:03b5121a232e 21
pcercuei 0:03b5121a232e 22 #include <limits.h>
pcercuei 0:03b5121a232e 23 #ifdef HAVE_STDLIB_H
pcercuei 0:03b5121a232e 24 #include <stdlib.h>
pcercuei 0:03b5121a232e 25 #endif
pcercuei 0:03b5121a232e 26 #ifdef HAVE_TIME_H
pcercuei 0:03b5121a232e 27 #include <time.h>
pcercuei 0:03b5121a232e 28 #endif
pcercuei 0:03b5121a232e 29
pcercuei 0:03b5121a232e 30 /*
pcercuei 0:03b5121a232e 31 * Following http://www.ocert.org/advisories/ocert-2011-003.html
pcercuei 0:03b5121a232e 32 * it seems that having hash randomization might be a good idea
pcercuei 0:03b5121a232e 33 * when using XML with untrusted data
pcercuei 0:03b5121a232e 34 * Note1: that it works correctly only if compiled with WITH_BIG_KEY
pcercuei 0:03b5121a232e 35 * which is the default.
pcercuei 0:03b5121a232e 36 * Note2: the fast function used for a small dict won't protect very
pcercuei 0:03b5121a232e 37 * well but since the attack is based on growing a very big hash
pcercuei 0:03b5121a232e 38 * list we will use the BigKey algo as soon as the hash size grows
pcercuei 0:03b5121a232e 39 * over MIN_DICT_SIZE so this actually works
pcercuei 0:03b5121a232e 40 */
pcercuei 0:03b5121a232e 41 #if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME)
pcercuei 0:03b5121a232e 42 #define DICT_RANDOMIZATION
pcercuei 0:03b5121a232e 43 #endif
pcercuei 0:03b5121a232e 44
pcercuei 0:03b5121a232e 45 #include <string.h>
pcercuei 0:03b5121a232e 46 #ifdef HAVE_STDINT_H
pcercuei 0:03b5121a232e 47 #include <stdint.h>
pcercuei 0:03b5121a232e 48 #else
pcercuei 0:03b5121a232e 49 #ifdef HAVE_INTTYPES_H
pcercuei 0:03b5121a232e 50 #include <inttypes.h>
pcercuei 0:03b5121a232e 51 #elif defined(WIN32)
pcercuei 0:03b5121a232e 52 typedef unsigned __int32 uint32_t;
pcercuei 0:03b5121a232e 53 #endif
pcercuei 0:03b5121a232e 54 #endif
pcercuei 0:03b5121a232e 55 #include <libxml/tree.h>
pcercuei 0:03b5121a232e 56 #include <libxml/dict.h>
pcercuei 0:03b5121a232e 57 #include <libxml/xmlmemory.h>
pcercuei 0:03b5121a232e 58 #include <libxml/xmlerror.h>
pcercuei 0:03b5121a232e 59 #include <libxml/globals.h>
pcercuei 0:03b5121a232e 60
pcercuei 0:03b5121a232e 61 /* #define DEBUG_GROW */
pcercuei 0:03b5121a232e 62 /* #define DICT_DEBUG_PATTERNS */
pcercuei 0:03b5121a232e 63
pcercuei 0:03b5121a232e 64 #define MAX_HASH_LEN 3
pcercuei 0:03b5121a232e 65 #define MIN_DICT_SIZE 128
pcercuei 0:03b5121a232e 66 #define MAX_DICT_HASH 8 * 2048
pcercuei 0:03b5121a232e 67 #define WITH_BIG_KEY
pcercuei 0:03b5121a232e 68
pcercuei 0:03b5121a232e 69 #ifdef WITH_BIG_KEY
pcercuei 0:03b5121a232e 70 #define xmlDictComputeKey(dict, name, len) \
pcercuei 0:03b5121a232e 71 (((dict)->size == MIN_DICT_SIZE) ? \
pcercuei 0:03b5121a232e 72 xmlDictComputeFastKey(name, len, (dict)->seed) : \
pcercuei 0:03b5121a232e 73 xmlDictComputeBigKey(name, len, (dict)->seed))
pcercuei 0:03b5121a232e 74
pcercuei 0:03b5121a232e 75 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
pcercuei 0:03b5121a232e 76 (((prefix) == NULL) ? \
pcercuei 0:03b5121a232e 77 (xmlDictComputeKey(dict, name, len)) : \
pcercuei 0:03b5121a232e 78 (((dict)->size == MIN_DICT_SIZE) ? \
pcercuei 0:03b5121a232e 79 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \
pcercuei 0:03b5121a232e 80 xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed)))
pcercuei 0:03b5121a232e 81
pcercuei 0:03b5121a232e 82 #else /* !WITH_BIG_KEY */
pcercuei 0:03b5121a232e 83 #define xmlDictComputeKey(dict, name, len) \
pcercuei 0:03b5121a232e 84 xmlDictComputeFastKey(name, len, (dict)->seed)
pcercuei 0:03b5121a232e 85 #define xmlDictComputeQKey(dict, prefix, plen, name, len) \
pcercuei 0:03b5121a232e 86 xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed)
pcercuei 0:03b5121a232e 87 #endif /* WITH_BIG_KEY */
pcercuei 0:03b5121a232e 88
pcercuei 0:03b5121a232e 89 /*
pcercuei 0:03b5121a232e 90 * An entry in the dictionnary
pcercuei 0:03b5121a232e 91 */
pcercuei 0:03b5121a232e 92 typedef struct _xmlDictEntry xmlDictEntry;
pcercuei 0:03b5121a232e 93 typedef xmlDictEntry *xmlDictEntryPtr;
pcercuei 0:03b5121a232e 94 struct _xmlDictEntry {
pcercuei 0:03b5121a232e 95 struct _xmlDictEntry *next;
pcercuei 0:03b5121a232e 96 const xmlChar *name;
pcercuei 0:03b5121a232e 97 unsigned int len;
pcercuei 0:03b5121a232e 98 int valid;
pcercuei 0:03b5121a232e 99 unsigned long okey;
pcercuei 0:03b5121a232e 100 };
pcercuei 0:03b5121a232e 101
pcercuei 0:03b5121a232e 102 typedef struct _xmlDictStrings xmlDictStrings;
pcercuei 0:03b5121a232e 103 typedef xmlDictStrings *xmlDictStringsPtr;
pcercuei 0:03b5121a232e 104 struct _xmlDictStrings {
pcercuei 0:03b5121a232e 105 xmlDictStringsPtr next;
pcercuei 0:03b5121a232e 106 xmlChar *free;
pcercuei 0:03b5121a232e 107 xmlChar *end;
pcercuei 0:03b5121a232e 108 size_t size;
pcercuei 0:03b5121a232e 109 size_t nbStrings;
pcercuei 0:03b5121a232e 110 xmlChar array[1];
pcercuei 0:03b5121a232e 111 };
pcercuei 0:03b5121a232e 112 /*
pcercuei 0:03b5121a232e 113 * The entire dictionnary
pcercuei 0:03b5121a232e 114 */
pcercuei 0:03b5121a232e 115 struct _xmlDict {
pcercuei 0:03b5121a232e 116 int ref_counter;
pcercuei 0:03b5121a232e 117
pcercuei 0:03b5121a232e 118 struct _xmlDictEntry *dict;
pcercuei 0:03b5121a232e 119 size_t size;
pcercuei 0:03b5121a232e 120 unsigned int nbElems;
pcercuei 0:03b5121a232e 121 xmlDictStringsPtr strings;
pcercuei 0:03b5121a232e 122
pcercuei 0:03b5121a232e 123 struct _xmlDict *subdict;
pcercuei 0:03b5121a232e 124 /* used for randomization */
pcercuei 0:03b5121a232e 125 int seed;
pcercuei 0:03b5121a232e 126 /* used to impose a limit on size */
pcercuei 0:03b5121a232e 127 size_t limit;
pcercuei 0:03b5121a232e 128 };
pcercuei 0:03b5121a232e 129
pcercuei 0:03b5121a232e 130 /*
pcercuei 0:03b5121a232e 131 * A mutex for modifying the reference counter for shared
pcercuei 0:03b5121a232e 132 * dictionaries.
pcercuei 0:03b5121a232e 133 */
pcercuei 0:03b5121a232e 134 static xmlRMutexPtr xmlDictMutex = NULL;
pcercuei 0:03b5121a232e 135
pcercuei 0:03b5121a232e 136 /*
pcercuei 0:03b5121a232e 137 * Whether the dictionary mutex was initialized.
pcercuei 0:03b5121a232e 138 */
pcercuei 0:03b5121a232e 139 static int xmlDictInitialized = 0;
pcercuei 0:03b5121a232e 140
pcercuei 0:03b5121a232e 141 #ifdef DICT_RANDOMIZATION
pcercuei 0:03b5121a232e 142 #ifdef HAVE_RAND_R
pcercuei 0:03b5121a232e 143 /*
pcercuei 0:03b5121a232e 144 * Internal data for random function, protected by xmlDictMutex
pcercuei 0:03b5121a232e 145 */
pcercuei 0:03b5121a232e 146 static unsigned int rand_seed = 0;
pcercuei 0:03b5121a232e 147 #endif
pcercuei 0:03b5121a232e 148 #endif
pcercuei 0:03b5121a232e 149
pcercuei 0:03b5121a232e 150 /**
pcercuei 0:03b5121a232e 151 * xmlInitializeDict:
pcercuei 0:03b5121a232e 152 *
pcercuei 0:03b5121a232e 153 * Do the dictionary mutex initialization.
pcercuei 0:03b5121a232e 154 * this function is deprecated
pcercuei 0:03b5121a232e 155 *
pcercuei 0:03b5121a232e 156 * Returns 0 if initialization was already done, and 1 if that
pcercuei 0:03b5121a232e 157 * call led to the initialization
pcercuei 0:03b5121a232e 158 */
pcercuei 0:03b5121a232e 159 int xmlInitializeDict(void) {
pcercuei 0:03b5121a232e 160 return(0);
pcercuei 0:03b5121a232e 161 }
pcercuei 0:03b5121a232e 162
pcercuei 0:03b5121a232e 163 /**
pcercuei 0:03b5121a232e 164 * __xmlInitializeDict:
pcercuei 0:03b5121a232e 165 *
pcercuei 0:03b5121a232e 166 * This function is not public
pcercuei 0:03b5121a232e 167 * Do the dictionary mutex initialization.
pcercuei 0:03b5121a232e 168 * this function is not thread safe, initialization should
pcercuei 0:03b5121a232e 169 * normally be done once at setup when called from xmlOnceInit()
pcercuei 0:03b5121a232e 170 * we may also land in this code if thread support is not compiled in
pcercuei 0:03b5121a232e 171 *
pcercuei 0:03b5121a232e 172 * Returns 0 if initialization was already done, and 1 if that
pcercuei 0:03b5121a232e 173 * call led to the initialization
pcercuei 0:03b5121a232e 174 */
pcercuei 0:03b5121a232e 175 int __xmlInitializeDict(void) {
pcercuei 0:03b5121a232e 176 if (xmlDictInitialized)
pcercuei 0:03b5121a232e 177 return(1);
pcercuei 0:03b5121a232e 178
pcercuei 0:03b5121a232e 179 if ((xmlDictMutex = xmlNewRMutex()) == NULL)
pcercuei 0:03b5121a232e 180 return(0);
pcercuei 0:03b5121a232e 181 xmlRMutexLock(xmlDictMutex);
pcercuei 0:03b5121a232e 182
pcercuei 0:03b5121a232e 183 #ifdef DICT_RANDOMIZATION
pcercuei 0:03b5121a232e 184 #ifdef HAVE_RAND_R
pcercuei 0:03b5121a232e 185 rand_seed = time(NULL);
pcercuei 0:03b5121a232e 186 rand_r(& rand_seed);
pcercuei 0:03b5121a232e 187 #else
pcercuei 0:03b5121a232e 188 srand(time(NULL));
pcercuei 0:03b5121a232e 189 #endif
pcercuei 0:03b5121a232e 190 #endif
pcercuei 0:03b5121a232e 191 xmlDictInitialized = 1;
pcercuei 0:03b5121a232e 192 xmlRMutexUnlock(xmlDictMutex);
pcercuei 0:03b5121a232e 193 return(1);
pcercuei 0:03b5121a232e 194 }
pcercuei 0:03b5121a232e 195
pcercuei 0:03b5121a232e 196 #ifdef DICT_RANDOMIZATION
pcercuei 0:03b5121a232e 197 int __xmlRandom(void) {
pcercuei 0:03b5121a232e 198 int ret;
pcercuei 0:03b5121a232e 199
pcercuei 0:03b5121a232e 200 if (xmlDictInitialized == 0)
pcercuei 0:03b5121a232e 201 __xmlInitializeDict();
pcercuei 0:03b5121a232e 202
pcercuei 0:03b5121a232e 203 xmlRMutexLock(xmlDictMutex);
pcercuei 0:03b5121a232e 204 #ifdef HAVE_RAND_R
pcercuei 0:03b5121a232e 205 ret = rand_r(& rand_seed);
pcercuei 0:03b5121a232e 206 #else
pcercuei 0:03b5121a232e 207 ret = rand();
pcercuei 0:03b5121a232e 208 #endif
pcercuei 0:03b5121a232e 209 xmlRMutexUnlock(xmlDictMutex);
pcercuei 0:03b5121a232e 210 return(ret);
pcercuei 0:03b5121a232e 211 }
pcercuei 0:03b5121a232e 212 #endif
pcercuei 0:03b5121a232e 213
pcercuei 0:03b5121a232e 214 /**
pcercuei 0:03b5121a232e 215 * xmlDictCleanup:
pcercuei 0:03b5121a232e 216 *
pcercuei 0:03b5121a232e 217 * Free the dictionary mutex. Do not call unless sure the library
pcercuei 0:03b5121a232e 218 * is not in use anymore !
pcercuei 0:03b5121a232e 219 */
pcercuei 0:03b5121a232e 220 void
pcercuei 0:03b5121a232e 221 xmlDictCleanup(void) {
pcercuei 0:03b5121a232e 222 if (!xmlDictInitialized)
pcercuei 0:03b5121a232e 223 return;
pcercuei 0:03b5121a232e 224
pcercuei 0:03b5121a232e 225 xmlFreeRMutex(xmlDictMutex);
pcercuei 0:03b5121a232e 226
pcercuei 0:03b5121a232e 227 xmlDictInitialized = 0;
pcercuei 0:03b5121a232e 228 }
pcercuei 0:03b5121a232e 229
pcercuei 0:03b5121a232e 230 /*
pcercuei 0:03b5121a232e 231 * xmlDictAddString:
pcercuei 0:03b5121a232e 232 * @dict: the dictionnary
pcercuei 0:03b5121a232e 233 * @name: the name of the userdata
pcercuei 0:03b5121a232e 234 * @len: the length of the name
pcercuei 0:03b5121a232e 235 *
pcercuei 0:03b5121a232e 236 * Add the string to the array[s]
pcercuei 0:03b5121a232e 237 *
pcercuei 0:03b5121a232e 238 * Returns the pointer of the local string, or NULL in case of error.
pcercuei 0:03b5121a232e 239 */
pcercuei 0:03b5121a232e 240 static const xmlChar *
pcercuei 0:03b5121a232e 241 xmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) {
pcercuei 0:03b5121a232e 242 xmlDictStringsPtr pool;
pcercuei 0:03b5121a232e 243 const xmlChar *ret;
pcercuei 0:03b5121a232e 244 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
pcercuei 0:03b5121a232e 245 size_t limit = 0;
pcercuei 0:03b5121a232e 246
pcercuei 0:03b5121a232e 247 #ifdef DICT_DEBUG_PATTERNS
pcercuei 0:03b5121a232e 248 fprintf(stderr, "-");
pcercuei 0:03b5121a232e 249 #endif
pcercuei 0:03b5121a232e 250 pool = dict->strings;
pcercuei 0:03b5121a232e 251 while (pool != NULL) {
pcercuei 0:03b5121a232e 252 if (pool->end - pool->free > namelen)
pcercuei 0:03b5121a232e 253 goto found_pool;
pcercuei 0:03b5121a232e 254 if (pool->size > size) size = pool->size;
pcercuei 0:03b5121a232e 255 limit += pool->size;
pcercuei 0:03b5121a232e 256 pool = pool->next;
pcercuei 0:03b5121a232e 257 }
pcercuei 0:03b5121a232e 258 /*
pcercuei 0:03b5121a232e 259 * Not found, need to allocate
pcercuei 0:03b5121a232e 260 */
pcercuei 0:03b5121a232e 261 if (pool == NULL) {
pcercuei 0:03b5121a232e 262 if ((dict->limit > 0) && (limit > dict->limit)) {
pcercuei 0:03b5121a232e 263 return(NULL);
pcercuei 0:03b5121a232e 264 }
pcercuei 0:03b5121a232e 265
pcercuei 0:03b5121a232e 266 if (size == 0) size = 1000;
pcercuei 0:03b5121a232e 267 else size *= 4; /* exponential growth */
pcercuei 0:03b5121a232e 268 if (size < 4 * namelen)
pcercuei 0:03b5121a232e 269 size = 4 * namelen; /* just in case ! */
pcercuei 0:03b5121a232e 270 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
pcercuei 0:03b5121a232e 271 if (pool == NULL)
pcercuei 0:03b5121a232e 272 return(NULL);
pcercuei 0:03b5121a232e 273 pool->size = size;
pcercuei 0:03b5121a232e 274 pool->nbStrings = 0;
pcercuei 0:03b5121a232e 275 pool->free = &pool->array[0];
pcercuei 0:03b5121a232e 276 pool->end = &pool->array[size];
pcercuei 0:03b5121a232e 277 pool->next = dict->strings;
pcercuei 0:03b5121a232e 278 dict->strings = pool;
pcercuei 0:03b5121a232e 279 #ifdef DICT_DEBUG_PATTERNS
pcercuei 0:03b5121a232e 280 fprintf(stderr, "+");
pcercuei 0:03b5121a232e 281 #endif
pcercuei 0:03b5121a232e 282 }
pcercuei 0:03b5121a232e 283 found_pool:
pcercuei 0:03b5121a232e 284 ret = pool->free;
pcercuei 0:03b5121a232e 285 memcpy(pool->free, name, namelen);
pcercuei 0:03b5121a232e 286 pool->free += namelen;
pcercuei 0:03b5121a232e 287 *(pool->free++) = 0;
pcercuei 0:03b5121a232e 288 pool->nbStrings++;
pcercuei 0:03b5121a232e 289 return(ret);
pcercuei 0:03b5121a232e 290 }
pcercuei 0:03b5121a232e 291
pcercuei 0:03b5121a232e 292 /*
pcercuei 0:03b5121a232e 293 * xmlDictAddQString:
pcercuei 0:03b5121a232e 294 * @dict: the dictionnary
pcercuei 0:03b5121a232e 295 * @prefix: the prefix of the userdata
pcercuei 0:03b5121a232e 296 * @plen: the prefix length
pcercuei 0:03b5121a232e 297 * @name: the name of the userdata
pcercuei 0:03b5121a232e 298 * @len: the length of the name
pcercuei 0:03b5121a232e 299 *
pcercuei 0:03b5121a232e 300 * Add the QName to the array[s]
pcercuei 0:03b5121a232e 301 *
pcercuei 0:03b5121a232e 302 * Returns the pointer of the local string, or NULL in case of error.
pcercuei 0:03b5121a232e 303 */
pcercuei 0:03b5121a232e 304 static const xmlChar *
pcercuei 0:03b5121a232e 305 xmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen,
pcercuei 0:03b5121a232e 306 const xmlChar *name, unsigned int namelen)
pcercuei 0:03b5121a232e 307 {
pcercuei 0:03b5121a232e 308 xmlDictStringsPtr pool;
pcercuei 0:03b5121a232e 309 const xmlChar *ret;
pcercuei 0:03b5121a232e 310 size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */
pcercuei 0:03b5121a232e 311 size_t limit = 0;
pcercuei 0:03b5121a232e 312
pcercuei 0:03b5121a232e 313 if (prefix == NULL) return(xmlDictAddString(dict, name, namelen));
pcercuei 0:03b5121a232e 314
pcercuei 0:03b5121a232e 315 #ifdef DICT_DEBUG_PATTERNS
pcercuei 0:03b5121a232e 316 fprintf(stderr, "=");
pcercuei 0:03b5121a232e 317 #endif
pcercuei 0:03b5121a232e 318 pool = dict->strings;
pcercuei 0:03b5121a232e 319 while (pool != NULL) {
pcercuei 0:03b5121a232e 320 if (pool->end - pool->free > namelen + plen + 1)
pcercuei 0:03b5121a232e 321 goto found_pool;
pcercuei 0:03b5121a232e 322 if (pool->size > size) size = pool->size;
pcercuei 0:03b5121a232e 323 limit += pool->size;
pcercuei 0:03b5121a232e 324 pool = pool->next;
pcercuei 0:03b5121a232e 325 }
pcercuei 0:03b5121a232e 326 /*
pcercuei 0:03b5121a232e 327 * Not found, need to allocate
pcercuei 0:03b5121a232e 328 */
pcercuei 0:03b5121a232e 329 if (pool == NULL) {
pcercuei 0:03b5121a232e 330 if ((dict->limit > 0) && (limit > dict->limit)) {
pcercuei 0:03b5121a232e 331 return(NULL);
pcercuei 0:03b5121a232e 332 }
pcercuei 0:03b5121a232e 333
pcercuei 0:03b5121a232e 334 if (size == 0) size = 1000;
pcercuei 0:03b5121a232e 335 else size *= 4; /* exponential growth */
pcercuei 0:03b5121a232e 336 if (size < 4 * (namelen + plen + 1))
pcercuei 0:03b5121a232e 337 size = 4 * (namelen + plen + 1); /* just in case ! */
pcercuei 0:03b5121a232e 338 pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size);
pcercuei 0:03b5121a232e 339 if (pool == NULL)
pcercuei 0:03b5121a232e 340 return(NULL);
pcercuei 0:03b5121a232e 341 pool->size = size;
pcercuei 0:03b5121a232e 342 pool->nbStrings = 0;
pcercuei 0:03b5121a232e 343 pool->free = &pool->array[0];
pcercuei 0:03b5121a232e 344 pool->end = &pool->array[size];
pcercuei 0:03b5121a232e 345 pool->next = dict->strings;
pcercuei 0:03b5121a232e 346 dict->strings = pool;
pcercuei 0:03b5121a232e 347 #ifdef DICT_DEBUG_PATTERNS
pcercuei 0:03b5121a232e 348 fprintf(stderr, "+");
pcercuei 0:03b5121a232e 349 #endif
pcercuei 0:03b5121a232e 350 }
pcercuei 0:03b5121a232e 351 found_pool:
pcercuei 0:03b5121a232e 352 ret = pool->free;
pcercuei 0:03b5121a232e 353 memcpy(pool->free, prefix, plen);
pcercuei 0:03b5121a232e 354 pool->free += plen;
pcercuei 0:03b5121a232e 355 *(pool->free++) = ':';
pcercuei 0:03b5121a232e 356 memcpy(pool->free, name, namelen);
pcercuei 0:03b5121a232e 357 pool->free += namelen;
pcercuei 0:03b5121a232e 358 *(pool->free++) = 0;
pcercuei 0:03b5121a232e 359 pool->nbStrings++;
pcercuei 0:03b5121a232e 360 return(ret);
pcercuei 0:03b5121a232e 361 }
pcercuei 0:03b5121a232e 362
pcercuei 0:03b5121a232e 363 #ifdef WITH_BIG_KEY
pcercuei 0:03b5121a232e 364 /*
pcercuei 0:03b5121a232e 365 * xmlDictComputeBigKey:
pcercuei 0:03b5121a232e 366 *
pcercuei 0:03b5121a232e 367 * Calculate a hash key using a good hash function that works well for
pcercuei 0:03b5121a232e 368 * larger hash table sizes.
pcercuei 0:03b5121a232e 369 *
pcercuei 0:03b5121a232e 370 * Hash function by "One-at-a-Time Hash" see
pcercuei 0:03b5121a232e 371 * http://burtleburtle.net/bob/hash/doobs.html
pcercuei 0:03b5121a232e 372 */
pcercuei 0:03b5121a232e 373
pcercuei 0:03b5121a232e 374 static uint32_t
pcercuei 0:03b5121a232e 375 xmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) {
pcercuei 0:03b5121a232e 376 uint32_t hash;
pcercuei 0:03b5121a232e 377 int i;
pcercuei 0:03b5121a232e 378
pcercuei 0:03b5121a232e 379 if (namelen <= 0 || data == NULL) return(0);
pcercuei 0:03b5121a232e 380
pcercuei 0:03b5121a232e 381 hash = seed;
pcercuei 0:03b5121a232e 382
pcercuei 0:03b5121a232e 383 for (i = 0;i < namelen; i++) {
pcercuei 0:03b5121a232e 384 hash += data[i];
pcercuei 0:03b5121a232e 385 hash += (hash << 10);
pcercuei 0:03b5121a232e 386 hash ^= (hash >> 6);
pcercuei 0:03b5121a232e 387 }
pcercuei 0:03b5121a232e 388 hash += (hash << 3);
pcercuei 0:03b5121a232e 389 hash ^= (hash >> 11);
pcercuei 0:03b5121a232e 390 hash += (hash << 15);
pcercuei 0:03b5121a232e 391
pcercuei 0:03b5121a232e 392 return hash;
pcercuei 0:03b5121a232e 393 }
pcercuei 0:03b5121a232e 394
pcercuei 0:03b5121a232e 395 /*
pcercuei 0:03b5121a232e 396 * xmlDictComputeBigQKey:
pcercuei 0:03b5121a232e 397 *
pcercuei 0:03b5121a232e 398 * Calculate a hash key for two strings using a good hash function
pcercuei 0:03b5121a232e 399 * that works well for larger hash table sizes.
pcercuei 0:03b5121a232e 400 *
pcercuei 0:03b5121a232e 401 * Hash function by "One-at-a-Time Hash" see
pcercuei 0:03b5121a232e 402 * http://burtleburtle.net/bob/hash/doobs.html
pcercuei 0:03b5121a232e 403 *
pcercuei 0:03b5121a232e 404 * Neither of the two strings must be NULL.
pcercuei 0:03b5121a232e 405 */
pcercuei 0:03b5121a232e 406 static unsigned long
pcercuei 0:03b5121a232e 407 xmlDictComputeBigQKey(const xmlChar *prefix, int plen,
pcercuei 0:03b5121a232e 408 const xmlChar *name, int len, int seed)
pcercuei 0:03b5121a232e 409 {
pcercuei 0:03b5121a232e 410 uint32_t hash;
pcercuei 0:03b5121a232e 411 int i;
pcercuei 0:03b5121a232e 412
pcercuei 0:03b5121a232e 413 hash = seed;
pcercuei 0:03b5121a232e 414
pcercuei 0:03b5121a232e 415 for (i = 0;i < plen; i++) {
pcercuei 0:03b5121a232e 416 hash += prefix[i];
pcercuei 0:03b5121a232e 417 hash += (hash << 10);
pcercuei 0:03b5121a232e 418 hash ^= (hash >> 6);
pcercuei 0:03b5121a232e 419 }
pcercuei 0:03b5121a232e 420 hash += ':';
pcercuei 0:03b5121a232e 421 hash += (hash << 10);
pcercuei 0:03b5121a232e 422 hash ^= (hash >> 6);
pcercuei 0:03b5121a232e 423
pcercuei 0:03b5121a232e 424 for (i = 0;i < len; i++) {
pcercuei 0:03b5121a232e 425 hash += name[i];
pcercuei 0:03b5121a232e 426 hash += (hash << 10);
pcercuei 0:03b5121a232e 427 hash ^= (hash >> 6);
pcercuei 0:03b5121a232e 428 }
pcercuei 0:03b5121a232e 429 hash += (hash << 3);
pcercuei 0:03b5121a232e 430 hash ^= (hash >> 11);
pcercuei 0:03b5121a232e 431 hash += (hash << 15);
pcercuei 0:03b5121a232e 432
pcercuei 0:03b5121a232e 433 return hash;
pcercuei 0:03b5121a232e 434 }
pcercuei 0:03b5121a232e 435 #endif /* WITH_BIG_KEY */
pcercuei 0:03b5121a232e 436
pcercuei 0:03b5121a232e 437 /*
pcercuei 0:03b5121a232e 438 * xmlDictComputeFastKey:
pcercuei 0:03b5121a232e 439 *
pcercuei 0:03b5121a232e 440 * Calculate a hash key using a fast hash function that works well
pcercuei 0:03b5121a232e 441 * for low hash table fill.
pcercuei 0:03b5121a232e 442 */
pcercuei 0:03b5121a232e 443 static unsigned long
pcercuei 0:03b5121a232e 444 xmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) {
pcercuei 0:03b5121a232e 445 unsigned long value = seed;
pcercuei 0:03b5121a232e 446
pcercuei 0:03b5121a232e 447 if (name == NULL) return(0);
pcercuei 0:03b5121a232e 448 value = *name;
pcercuei 0:03b5121a232e 449 value <<= 5;
pcercuei 0:03b5121a232e 450 if (namelen > 10) {
pcercuei 0:03b5121a232e 451 value += name[namelen - 1];
pcercuei 0:03b5121a232e 452 namelen = 10;
pcercuei 0:03b5121a232e 453 }
pcercuei 0:03b5121a232e 454 switch (namelen) {
pcercuei 0:03b5121a232e 455 case 10: value += name[9];
pcercuei 0:03b5121a232e 456 case 9: value += name[8];
pcercuei 0:03b5121a232e 457 case 8: value += name[7];
pcercuei 0:03b5121a232e 458 case 7: value += name[6];
pcercuei 0:03b5121a232e 459 case 6: value += name[5];
pcercuei 0:03b5121a232e 460 case 5: value += name[4];
pcercuei 0:03b5121a232e 461 case 4: value += name[3];
pcercuei 0:03b5121a232e 462 case 3: value += name[2];
pcercuei 0:03b5121a232e 463 case 2: value += name[1];
pcercuei 0:03b5121a232e 464 default: break;
pcercuei 0:03b5121a232e 465 }
pcercuei 0:03b5121a232e 466 return(value);
pcercuei 0:03b5121a232e 467 }
pcercuei 0:03b5121a232e 468
pcercuei 0:03b5121a232e 469 /*
pcercuei 0:03b5121a232e 470 * xmlDictComputeFastQKey:
pcercuei 0:03b5121a232e 471 *
pcercuei 0:03b5121a232e 472 * Calculate a hash key for two strings using a fast hash function
pcercuei 0:03b5121a232e 473 * that works well for low hash table fill.
pcercuei 0:03b5121a232e 474 *
pcercuei 0:03b5121a232e 475 * Neither of the two strings must be NULL.
pcercuei 0:03b5121a232e 476 */
pcercuei 0:03b5121a232e 477 static unsigned long
pcercuei 0:03b5121a232e 478 xmlDictComputeFastQKey(const xmlChar *prefix, int plen,
pcercuei 0:03b5121a232e 479 const xmlChar *name, int len, int seed)
pcercuei 0:03b5121a232e 480 {
pcercuei 0:03b5121a232e 481 unsigned long value = (unsigned long) seed;
pcercuei 0:03b5121a232e 482
pcercuei 0:03b5121a232e 483 if (plen == 0)
pcercuei 0:03b5121a232e 484 value += 30 * (unsigned long) ':';
pcercuei 0:03b5121a232e 485 else
pcercuei 0:03b5121a232e 486 value += 30 * (*prefix);
pcercuei 0:03b5121a232e 487
pcercuei 0:03b5121a232e 488 if (len > 10) {
pcercuei 0:03b5121a232e 489 int offset = len - (plen + 1 + 1);
pcercuei 0:03b5121a232e 490 if (offset < 0)
pcercuei 0:03b5121a232e 491 offset = len - (10 + 1);
pcercuei 0:03b5121a232e 492 value += name[offset];
pcercuei 0:03b5121a232e 493 len = 10;
pcercuei 0:03b5121a232e 494 if (plen > 10)
pcercuei 0:03b5121a232e 495 plen = 10;
pcercuei 0:03b5121a232e 496 }
pcercuei 0:03b5121a232e 497 switch (plen) {
pcercuei 0:03b5121a232e 498 case 10: value += prefix[9];
pcercuei 0:03b5121a232e 499 case 9: value += prefix[8];
pcercuei 0:03b5121a232e 500 case 8: value += prefix[7];
pcercuei 0:03b5121a232e 501 case 7: value += prefix[6];
pcercuei 0:03b5121a232e 502 case 6: value += prefix[5];
pcercuei 0:03b5121a232e 503 case 5: value += prefix[4];
pcercuei 0:03b5121a232e 504 case 4: value += prefix[3];
pcercuei 0:03b5121a232e 505 case 3: value += prefix[2];
pcercuei 0:03b5121a232e 506 case 2: value += prefix[1];
pcercuei 0:03b5121a232e 507 case 1: value += prefix[0];
pcercuei 0:03b5121a232e 508 default: break;
pcercuei 0:03b5121a232e 509 }
pcercuei 0:03b5121a232e 510 len -= plen;
pcercuei 0:03b5121a232e 511 if (len > 0) {
pcercuei 0:03b5121a232e 512 value += (unsigned long) ':';
pcercuei 0:03b5121a232e 513 len--;
pcercuei 0:03b5121a232e 514 }
pcercuei 0:03b5121a232e 515 switch (len) {
pcercuei 0:03b5121a232e 516 case 10: value += name[9];
pcercuei 0:03b5121a232e 517 case 9: value += name[8];
pcercuei 0:03b5121a232e 518 case 8: value += name[7];
pcercuei 0:03b5121a232e 519 case 7: value += name[6];
pcercuei 0:03b5121a232e 520 case 6: value += name[5];
pcercuei 0:03b5121a232e 521 case 5: value += name[4];
pcercuei 0:03b5121a232e 522 case 4: value += name[3];
pcercuei 0:03b5121a232e 523 case 3: value += name[2];
pcercuei 0:03b5121a232e 524 case 2: value += name[1];
pcercuei 0:03b5121a232e 525 case 1: value += name[0];
pcercuei 0:03b5121a232e 526 default: break;
pcercuei 0:03b5121a232e 527 }
pcercuei 0:03b5121a232e 528 return(value);
pcercuei 0:03b5121a232e 529 }
pcercuei 0:03b5121a232e 530
pcercuei 0:03b5121a232e 531 /**
pcercuei 0:03b5121a232e 532 * xmlDictCreate:
pcercuei 0:03b5121a232e 533 *
pcercuei 0:03b5121a232e 534 * Create a new dictionary
pcercuei 0:03b5121a232e 535 *
pcercuei 0:03b5121a232e 536 * Returns the newly created dictionnary, or NULL if an error occured.
pcercuei 0:03b5121a232e 537 */
pcercuei 0:03b5121a232e 538 xmlDictPtr
pcercuei 0:03b5121a232e 539 xmlDictCreate(void) {
pcercuei 0:03b5121a232e 540 xmlDictPtr dict;
pcercuei 0:03b5121a232e 541
pcercuei 0:03b5121a232e 542 if (!xmlDictInitialized)
pcercuei 0:03b5121a232e 543 if (!__xmlInitializeDict())
pcercuei 0:03b5121a232e 544 return(NULL);
pcercuei 0:03b5121a232e 545
pcercuei 0:03b5121a232e 546 #ifdef DICT_DEBUG_PATTERNS
pcercuei 0:03b5121a232e 547 fprintf(stderr, "C");
pcercuei 0:03b5121a232e 548 #endif
pcercuei 0:03b5121a232e 549
pcercuei 0:03b5121a232e 550 dict = xmlMalloc(sizeof(xmlDict));
pcercuei 0:03b5121a232e 551 if (dict) {
pcercuei 0:03b5121a232e 552 dict->ref_counter = 1;
pcercuei 0:03b5121a232e 553 dict->limit = 0;
pcercuei 0:03b5121a232e 554
pcercuei 0:03b5121a232e 555 dict->size = MIN_DICT_SIZE;
pcercuei 0:03b5121a232e 556 dict->nbElems = 0;
pcercuei 0:03b5121a232e 557 dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 558 dict->strings = NULL;
pcercuei 0:03b5121a232e 559 dict->subdict = NULL;
pcercuei 0:03b5121a232e 560 if (dict->dict) {
pcercuei 0:03b5121a232e 561 memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 562 #ifdef DICT_RANDOMIZATION
pcercuei 0:03b5121a232e 563 dict->seed = __xmlRandom();
pcercuei 0:03b5121a232e 564 #else
pcercuei 0:03b5121a232e 565 dict->seed = 0;
pcercuei 0:03b5121a232e 566 #endif
pcercuei 0:03b5121a232e 567 return(dict);
pcercuei 0:03b5121a232e 568 }
pcercuei 0:03b5121a232e 569 xmlFree(dict);
pcercuei 0:03b5121a232e 570 }
pcercuei 0:03b5121a232e 571 return(NULL);
pcercuei 0:03b5121a232e 572 }
pcercuei 0:03b5121a232e 573
pcercuei 0:03b5121a232e 574 /**
pcercuei 0:03b5121a232e 575 * xmlDictCreateSub:
pcercuei 0:03b5121a232e 576 * @sub: an existing dictionnary
pcercuei 0:03b5121a232e 577 *
pcercuei 0:03b5121a232e 578 * Create a new dictionary, inheriting strings from the read-only
pcercuei 0:03b5121a232e 579 * dictionnary @sub. On lookup, strings are first searched in the
pcercuei 0:03b5121a232e 580 * new dictionnary, then in @sub, and if not found are created in the
pcercuei 0:03b5121a232e 581 * new dictionnary.
pcercuei 0:03b5121a232e 582 *
pcercuei 0:03b5121a232e 583 * Returns the newly created dictionnary, or NULL if an error occured.
pcercuei 0:03b5121a232e 584 */
pcercuei 0:03b5121a232e 585 xmlDictPtr
pcercuei 0:03b5121a232e 586 xmlDictCreateSub(xmlDictPtr sub) {
pcercuei 0:03b5121a232e 587 xmlDictPtr dict = xmlDictCreate();
pcercuei 0:03b5121a232e 588
pcercuei 0:03b5121a232e 589 if ((dict != NULL) && (sub != NULL)) {
pcercuei 0:03b5121a232e 590 #ifdef DICT_DEBUG_PATTERNS
pcercuei 0:03b5121a232e 591 fprintf(stderr, "R");
pcercuei 0:03b5121a232e 592 #endif
pcercuei 0:03b5121a232e 593 dict->seed = sub->seed;
pcercuei 0:03b5121a232e 594 dict->subdict = sub;
pcercuei 0:03b5121a232e 595 xmlDictReference(dict->subdict);
pcercuei 0:03b5121a232e 596 }
pcercuei 0:03b5121a232e 597 return(dict);
pcercuei 0:03b5121a232e 598 }
pcercuei 0:03b5121a232e 599
pcercuei 0:03b5121a232e 600 /**
pcercuei 0:03b5121a232e 601 * xmlDictReference:
pcercuei 0:03b5121a232e 602 * @dict: the dictionnary
pcercuei 0:03b5121a232e 603 *
pcercuei 0:03b5121a232e 604 * Increment the reference counter of a dictionary
pcercuei 0:03b5121a232e 605 *
pcercuei 0:03b5121a232e 606 * Returns 0 in case of success and -1 in case of error
pcercuei 0:03b5121a232e 607 */
pcercuei 0:03b5121a232e 608 int
pcercuei 0:03b5121a232e 609 xmlDictReference(xmlDictPtr dict) {
pcercuei 0:03b5121a232e 610 if (!xmlDictInitialized)
pcercuei 0:03b5121a232e 611 if (!__xmlInitializeDict())
pcercuei 0:03b5121a232e 612 return(-1);
pcercuei 0:03b5121a232e 613
pcercuei 0:03b5121a232e 614 if (dict == NULL) return -1;
pcercuei 0:03b5121a232e 615 xmlRMutexLock(xmlDictMutex);
pcercuei 0:03b5121a232e 616 dict->ref_counter++;
pcercuei 0:03b5121a232e 617 xmlRMutexUnlock(xmlDictMutex);
pcercuei 0:03b5121a232e 618 return(0);
pcercuei 0:03b5121a232e 619 }
pcercuei 0:03b5121a232e 620
pcercuei 0:03b5121a232e 621 /**
pcercuei 0:03b5121a232e 622 * xmlDictGrow:
pcercuei 0:03b5121a232e 623 * @dict: the dictionnary
pcercuei 0:03b5121a232e 624 * @size: the new size of the dictionnary
pcercuei 0:03b5121a232e 625 *
pcercuei 0:03b5121a232e 626 * resize the dictionnary
pcercuei 0:03b5121a232e 627 *
pcercuei 0:03b5121a232e 628 * Returns 0 in case of success, -1 in case of failure
pcercuei 0:03b5121a232e 629 */
pcercuei 0:03b5121a232e 630 static int
pcercuei 0:03b5121a232e 631 xmlDictGrow(xmlDictPtr dict, size_t size) {
pcercuei 0:03b5121a232e 632 unsigned long key, okey;
pcercuei 0:03b5121a232e 633 size_t oldsize, i;
pcercuei 0:03b5121a232e 634 xmlDictEntryPtr iter, next;
pcercuei 0:03b5121a232e 635 struct _xmlDictEntry *olddict;
pcercuei 0:03b5121a232e 636 #ifdef DEBUG_GROW
pcercuei 0:03b5121a232e 637 unsigned long nbElem = 0;
pcercuei 0:03b5121a232e 638 #endif
pcercuei 0:03b5121a232e 639 int ret = 0;
pcercuei 0:03b5121a232e 640 int keep_keys = 1;
pcercuei 0:03b5121a232e 641
pcercuei 0:03b5121a232e 642 if (dict == NULL)
pcercuei 0:03b5121a232e 643 return(-1);
pcercuei 0:03b5121a232e 644 if (size < 8)
pcercuei 0:03b5121a232e 645 return(-1);
pcercuei 0:03b5121a232e 646 if (size > 8 * 2048)
pcercuei 0:03b5121a232e 647 return(-1);
pcercuei 0:03b5121a232e 648
pcercuei 0:03b5121a232e 649 #ifdef DICT_DEBUG_PATTERNS
pcercuei 0:03b5121a232e 650 fprintf(stderr, "*");
pcercuei 0:03b5121a232e 651 #endif
pcercuei 0:03b5121a232e 652
pcercuei 0:03b5121a232e 653 oldsize = dict->size;
pcercuei 0:03b5121a232e 654 olddict = dict->dict;
pcercuei 0:03b5121a232e 655 if (olddict == NULL)
pcercuei 0:03b5121a232e 656 return(-1);
pcercuei 0:03b5121a232e 657 if (oldsize == MIN_DICT_SIZE)
pcercuei 0:03b5121a232e 658 keep_keys = 0;
pcercuei 0:03b5121a232e 659
pcercuei 0:03b5121a232e 660 dict->dict = xmlMalloc(size * sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 661 if (dict->dict == NULL) {
pcercuei 0:03b5121a232e 662 dict->dict = olddict;
pcercuei 0:03b5121a232e 663 return(-1);
pcercuei 0:03b5121a232e 664 }
pcercuei 0:03b5121a232e 665 memset(dict->dict, 0, size * sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 666 dict->size = size;
pcercuei 0:03b5121a232e 667
pcercuei 0:03b5121a232e 668 /* If the two loops are merged, there would be situations where
pcercuei 0:03b5121a232e 669 a new entry needs to allocated and data copied into it from
pcercuei 0:03b5121a232e 670 the main dict. It is nicer to run through the array twice, first
pcercuei 0:03b5121a232e 671 copying all the elements in the main array (less probability of
pcercuei 0:03b5121a232e 672 allocate) and then the rest, so we only free in the second loop.
pcercuei 0:03b5121a232e 673 */
pcercuei 0:03b5121a232e 674 for (i = 0; i < oldsize; i++) {
pcercuei 0:03b5121a232e 675 if (olddict[i].valid == 0)
pcercuei 0:03b5121a232e 676 continue;
pcercuei 0:03b5121a232e 677
pcercuei 0:03b5121a232e 678 if (keep_keys)
pcercuei 0:03b5121a232e 679 okey = olddict[i].okey;
pcercuei 0:03b5121a232e 680 else
pcercuei 0:03b5121a232e 681 okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len);
pcercuei 0:03b5121a232e 682 key = okey % dict->size;
pcercuei 0:03b5121a232e 683
pcercuei 0:03b5121a232e 684 if (dict->dict[key].valid == 0) {
pcercuei 0:03b5121a232e 685 memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 686 dict->dict[key].next = NULL;
pcercuei 0:03b5121a232e 687 dict->dict[key].okey = okey;
pcercuei 0:03b5121a232e 688 } else {
pcercuei 0:03b5121a232e 689 xmlDictEntryPtr entry;
pcercuei 0:03b5121a232e 690
pcercuei 0:03b5121a232e 691 entry = xmlMalloc(sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 692 if (entry != NULL) {
pcercuei 0:03b5121a232e 693 entry->name = olddict[i].name;
pcercuei 0:03b5121a232e 694 entry->len = olddict[i].len;
pcercuei 0:03b5121a232e 695 entry->okey = okey;
pcercuei 0:03b5121a232e 696 entry->next = dict->dict[key].next;
pcercuei 0:03b5121a232e 697 entry->valid = 1;
pcercuei 0:03b5121a232e 698 dict->dict[key].next = entry;
pcercuei 0:03b5121a232e 699 } else {
pcercuei 0:03b5121a232e 700 /*
pcercuei 0:03b5121a232e 701 * we don't have much ways to alert from herei
pcercuei 0:03b5121a232e 702 * result is loosing an entry and unicity garantee
pcercuei 0:03b5121a232e 703 */
pcercuei 0:03b5121a232e 704 ret = -1;
pcercuei 0:03b5121a232e 705 }
pcercuei 0:03b5121a232e 706 }
pcercuei 0:03b5121a232e 707 #ifdef DEBUG_GROW
pcercuei 0:03b5121a232e 708 nbElem++;
pcercuei 0:03b5121a232e 709 #endif
pcercuei 0:03b5121a232e 710 }
pcercuei 0:03b5121a232e 711
pcercuei 0:03b5121a232e 712 for (i = 0; i < oldsize; i++) {
pcercuei 0:03b5121a232e 713 iter = olddict[i].next;
pcercuei 0:03b5121a232e 714 while (iter) {
pcercuei 0:03b5121a232e 715 next = iter->next;
pcercuei 0:03b5121a232e 716
pcercuei 0:03b5121a232e 717 /*
pcercuei 0:03b5121a232e 718 * put back the entry in the new dict
pcercuei 0:03b5121a232e 719 */
pcercuei 0:03b5121a232e 720
pcercuei 0:03b5121a232e 721 if (keep_keys)
pcercuei 0:03b5121a232e 722 okey = iter->okey;
pcercuei 0:03b5121a232e 723 else
pcercuei 0:03b5121a232e 724 okey = xmlDictComputeKey(dict, iter->name, iter->len);
pcercuei 0:03b5121a232e 725 key = okey % dict->size;
pcercuei 0:03b5121a232e 726 if (dict->dict[key].valid == 0) {
pcercuei 0:03b5121a232e 727 memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 728 dict->dict[key].next = NULL;
pcercuei 0:03b5121a232e 729 dict->dict[key].valid = 1;
pcercuei 0:03b5121a232e 730 dict->dict[key].okey = okey;
pcercuei 0:03b5121a232e 731 xmlFree(iter);
pcercuei 0:03b5121a232e 732 } else {
pcercuei 0:03b5121a232e 733 iter->next = dict->dict[key].next;
pcercuei 0:03b5121a232e 734 iter->okey = okey;
pcercuei 0:03b5121a232e 735 dict->dict[key].next = iter;
pcercuei 0:03b5121a232e 736 }
pcercuei 0:03b5121a232e 737
pcercuei 0:03b5121a232e 738 #ifdef DEBUG_GROW
pcercuei 0:03b5121a232e 739 nbElem++;
pcercuei 0:03b5121a232e 740 #endif
pcercuei 0:03b5121a232e 741
pcercuei 0:03b5121a232e 742 iter = next;
pcercuei 0:03b5121a232e 743 }
pcercuei 0:03b5121a232e 744 }
pcercuei 0:03b5121a232e 745
pcercuei 0:03b5121a232e 746 xmlFree(olddict);
pcercuei 0:03b5121a232e 747
pcercuei 0:03b5121a232e 748 #ifdef DEBUG_GROW
pcercuei 0:03b5121a232e 749 xmlGenericError(xmlGenericErrorContext,
pcercuei 0:03b5121a232e 750 "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem);
pcercuei 0:03b5121a232e 751 #endif
pcercuei 0:03b5121a232e 752
pcercuei 0:03b5121a232e 753 return(ret);
pcercuei 0:03b5121a232e 754 }
pcercuei 0:03b5121a232e 755
pcercuei 0:03b5121a232e 756 /**
pcercuei 0:03b5121a232e 757 * xmlDictFree:
pcercuei 0:03b5121a232e 758 * @dict: the dictionnary
pcercuei 0:03b5121a232e 759 *
pcercuei 0:03b5121a232e 760 * Free the hash @dict and its contents. The userdata is
pcercuei 0:03b5121a232e 761 * deallocated with @f if provided.
pcercuei 0:03b5121a232e 762 */
pcercuei 0:03b5121a232e 763 void
pcercuei 0:03b5121a232e 764 xmlDictFree(xmlDictPtr dict) {
pcercuei 0:03b5121a232e 765 size_t i;
pcercuei 0:03b5121a232e 766 xmlDictEntryPtr iter;
pcercuei 0:03b5121a232e 767 xmlDictEntryPtr next;
pcercuei 0:03b5121a232e 768 int inside_dict = 0;
pcercuei 0:03b5121a232e 769 xmlDictStringsPtr pool, nextp;
pcercuei 0:03b5121a232e 770
pcercuei 0:03b5121a232e 771 if (dict == NULL)
pcercuei 0:03b5121a232e 772 return;
pcercuei 0:03b5121a232e 773
pcercuei 0:03b5121a232e 774 if (!xmlDictInitialized)
pcercuei 0:03b5121a232e 775 if (!__xmlInitializeDict())
pcercuei 0:03b5121a232e 776 return;
pcercuei 0:03b5121a232e 777
pcercuei 0:03b5121a232e 778 /* decrement the counter, it may be shared by a parser and docs */
pcercuei 0:03b5121a232e 779 xmlRMutexLock(xmlDictMutex);
pcercuei 0:03b5121a232e 780 dict->ref_counter--;
pcercuei 0:03b5121a232e 781 if (dict->ref_counter > 0) {
pcercuei 0:03b5121a232e 782 xmlRMutexUnlock(xmlDictMutex);
pcercuei 0:03b5121a232e 783 return;
pcercuei 0:03b5121a232e 784 }
pcercuei 0:03b5121a232e 785
pcercuei 0:03b5121a232e 786 xmlRMutexUnlock(xmlDictMutex);
pcercuei 0:03b5121a232e 787
pcercuei 0:03b5121a232e 788 if (dict->subdict != NULL) {
pcercuei 0:03b5121a232e 789 xmlDictFree(dict->subdict);
pcercuei 0:03b5121a232e 790 }
pcercuei 0:03b5121a232e 791
pcercuei 0:03b5121a232e 792 if (dict->dict) {
pcercuei 0:03b5121a232e 793 for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) {
pcercuei 0:03b5121a232e 794 iter = &(dict->dict[i]);
pcercuei 0:03b5121a232e 795 if (iter->valid == 0)
pcercuei 0:03b5121a232e 796 continue;
pcercuei 0:03b5121a232e 797 inside_dict = 1;
pcercuei 0:03b5121a232e 798 while (iter) {
pcercuei 0:03b5121a232e 799 next = iter->next;
pcercuei 0:03b5121a232e 800 if (!inside_dict)
pcercuei 0:03b5121a232e 801 xmlFree(iter);
pcercuei 0:03b5121a232e 802 dict->nbElems--;
pcercuei 0:03b5121a232e 803 inside_dict = 0;
pcercuei 0:03b5121a232e 804 iter = next;
pcercuei 0:03b5121a232e 805 }
pcercuei 0:03b5121a232e 806 }
pcercuei 0:03b5121a232e 807 xmlFree(dict->dict);
pcercuei 0:03b5121a232e 808 }
pcercuei 0:03b5121a232e 809 pool = dict->strings;
pcercuei 0:03b5121a232e 810 while (pool != NULL) {
pcercuei 0:03b5121a232e 811 nextp = pool->next;
pcercuei 0:03b5121a232e 812 xmlFree(pool);
pcercuei 0:03b5121a232e 813 pool = nextp;
pcercuei 0:03b5121a232e 814 }
pcercuei 0:03b5121a232e 815 xmlFree(dict);
pcercuei 0:03b5121a232e 816 }
pcercuei 0:03b5121a232e 817
pcercuei 0:03b5121a232e 818 /**
pcercuei 0:03b5121a232e 819 * xmlDictLookup:
pcercuei 0:03b5121a232e 820 * @dict: the dictionnary
pcercuei 0:03b5121a232e 821 * @name: the name of the userdata
pcercuei 0:03b5121a232e 822 * @len: the length of the name, if -1 it is recomputed
pcercuei 0:03b5121a232e 823 *
pcercuei 0:03b5121a232e 824 * Add the @name to the dictionnary @dict if not present.
pcercuei 0:03b5121a232e 825 *
pcercuei 0:03b5121a232e 826 * Returns the internal copy of the name or NULL in case of internal error
pcercuei 0:03b5121a232e 827 */
pcercuei 0:03b5121a232e 828 const xmlChar *
pcercuei 0:03b5121a232e 829 xmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) {
pcercuei 0:03b5121a232e 830 unsigned long key, okey, nbi = 0;
pcercuei 0:03b5121a232e 831 xmlDictEntryPtr entry;
pcercuei 0:03b5121a232e 832 xmlDictEntryPtr insert;
pcercuei 0:03b5121a232e 833 const xmlChar *ret;
pcercuei 0:03b5121a232e 834 unsigned int l;
pcercuei 0:03b5121a232e 835
pcercuei 0:03b5121a232e 836 if ((dict == NULL) || (name == NULL))
pcercuei 0:03b5121a232e 837 return(NULL);
pcercuei 0:03b5121a232e 838
pcercuei 0:03b5121a232e 839 if (len < 0)
pcercuei 0:03b5121a232e 840 l = strlen((const char *) name);
pcercuei 0:03b5121a232e 841 else
pcercuei 0:03b5121a232e 842 l = len;
pcercuei 0:03b5121a232e 843
pcercuei 0:03b5121a232e 844 if (((dict->limit > 0) && (l >= dict->limit)) ||
pcercuei 0:03b5121a232e 845 (l > INT_MAX / 2))
pcercuei 0:03b5121a232e 846 return(NULL);
pcercuei 0:03b5121a232e 847
pcercuei 0:03b5121a232e 848 /*
pcercuei 0:03b5121a232e 849 * Check for duplicate and insertion location.
pcercuei 0:03b5121a232e 850 */
pcercuei 0:03b5121a232e 851 okey = xmlDictComputeKey(dict, name, l);
pcercuei 0:03b5121a232e 852 key = okey % dict->size;
pcercuei 0:03b5121a232e 853 if (dict->dict[key].valid == 0) {
pcercuei 0:03b5121a232e 854 insert = NULL;
pcercuei 0:03b5121a232e 855 } else {
pcercuei 0:03b5121a232e 856 for (insert = &(dict->dict[key]); insert->next != NULL;
pcercuei 0:03b5121a232e 857 insert = insert->next) {
pcercuei 0:03b5121a232e 858 #ifdef __GNUC__
pcercuei 0:03b5121a232e 859 if ((insert->okey == okey) && (insert->len == l)) {
pcercuei 0:03b5121a232e 860 if (!memcmp(insert->name, name, l))
pcercuei 0:03b5121a232e 861 return(insert->name);
pcercuei 0:03b5121a232e 862 }
pcercuei 0:03b5121a232e 863 #else
pcercuei 0:03b5121a232e 864 if ((insert->okey == okey) && (insert->len == l) &&
pcercuei 0:03b5121a232e 865 (!xmlStrncmp(insert->name, name, l)))
pcercuei 0:03b5121a232e 866 return(insert->name);
pcercuei 0:03b5121a232e 867 #endif
pcercuei 0:03b5121a232e 868 nbi++;
pcercuei 0:03b5121a232e 869 }
pcercuei 0:03b5121a232e 870 #ifdef __GNUC__
pcercuei 0:03b5121a232e 871 if ((insert->okey == okey) && (insert->len == l)) {
pcercuei 0:03b5121a232e 872 if (!memcmp(insert->name, name, l))
pcercuei 0:03b5121a232e 873 return(insert->name);
pcercuei 0:03b5121a232e 874 }
pcercuei 0:03b5121a232e 875 #else
pcercuei 0:03b5121a232e 876 if ((insert->okey == okey) && (insert->len == l) &&
pcercuei 0:03b5121a232e 877 (!xmlStrncmp(insert->name, name, l)))
pcercuei 0:03b5121a232e 878 return(insert->name);
pcercuei 0:03b5121a232e 879 #endif
pcercuei 0:03b5121a232e 880 }
pcercuei 0:03b5121a232e 881
pcercuei 0:03b5121a232e 882 if (dict->subdict) {
pcercuei 0:03b5121a232e 883 unsigned long skey;
pcercuei 0:03b5121a232e 884
pcercuei 0:03b5121a232e 885 /* we cannot always reuse the same okey for the subdict */
pcercuei 0:03b5121a232e 886 if (((dict->size == MIN_DICT_SIZE) &&
pcercuei 0:03b5121a232e 887 (dict->subdict->size != MIN_DICT_SIZE)) ||
pcercuei 0:03b5121a232e 888 ((dict->size != MIN_DICT_SIZE) &&
pcercuei 0:03b5121a232e 889 (dict->subdict->size == MIN_DICT_SIZE)))
pcercuei 0:03b5121a232e 890 skey = xmlDictComputeKey(dict->subdict, name, l);
pcercuei 0:03b5121a232e 891 else
pcercuei 0:03b5121a232e 892 skey = okey;
pcercuei 0:03b5121a232e 893
pcercuei 0:03b5121a232e 894 key = skey % dict->subdict->size;
pcercuei 0:03b5121a232e 895 if (dict->subdict->dict[key].valid != 0) {
pcercuei 0:03b5121a232e 896 xmlDictEntryPtr tmp;
pcercuei 0:03b5121a232e 897
pcercuei 0:03b5121a232e 898 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
pcercuei 0:03b5121a232e 899 tmp = tmp->next) {
pcercuei 0:03b5121a232e 900 #ifdef __GNUC__
pcercuei 0:03b5121a232e 901 if ((tmp->okey == skey) && (tmp->len == l)) {
pcercuei 0:03b5121a232e 902 if (!memcmp(tmp->name, name, l))
pcercuei 0:03b5121a232e 903 return(tmp->name);
pcercuei 0:03b5121a232e 904 }
pcercuei 0:03b5121a232e 905 #else
pcercuei 0:03b5121a232e 906 if ((tmp->okey == skey) && (tmp->len == l) &&
pcercuei 0:03b5121a232e 907 (!xmlStrncmp(tmp->name, name, l)))
pcercuei 0:03b5121a232e 908 return(tmp->name);
pcercuei 0:03b5121a232e 909 #endif
pcercuei 0:03b5121a232e 910 nbi++;
pcercuei 0:03b5121a232e 911 }
pcercuei 0:03b5121a232e 912 #ifdef __GNUC__
pcercuei 0:03b5121a232e 913 if ((tmp->okey == skey) && (tmp->len == l)) {
pcercuei 0:03b5121a232e 914 if (!memcmp(tmp->name, name, l))
pcercuei 0:03b5121a232e 915 return(tmp->name);
pcercuei 0:03b5121a232e 916 }
pcercuei 0:03b5121a232e 917 #else
pcercuei 0:03b5121a232e 918 if ((tmp->okey == skey) && (tmp->len == l) &&
pcercuei 0:03b5121a232e 919 (!xmlStrncmp(tmp->name, name, l)))
pcercuei 0:03b5121a232e 920 return(tmp->name);
pcercuei 0:03b5121a232e 921 #endif
pcercuei 0:03b5121a232e 922 }
pcercuei 0:03b5121a232e 923 key = okey % dict->size;
pcercuei 0:03b5121a232e 924 }
pcercuei 0:03b5121a232e 925
pcercuei 0:03b5121a232e 926 ret = xmlDictAddString(dict, name, l);
pcercuei 0:03b5121a232e 927 if (ret == NULL)
pcercuei 0:03b5121a232e 928 return(NULL);
pcercuei 0:03b5121a232e 929 if (insert == NULL) {
pcercuei 0:03b5121a232e 930 entry = &(dict->dict[key]);
pcercuei 0:03b5121a232e 931 } else {
pcercuei 0:03b5121a232e 932 entry = xmlMalloc(sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 933 if (entry == NULL)
pcercuei 0:03b5121a232e 934 return(NULL);
pcercuei 0:03b5121a232e 935 }
pcercuei 0:03b5121a232e 936 entry->name = ret;
pcercuei 0:03b5121a232e 937 entry->len = l;
pcercuei 0:03b5121a232e 938 entry->next = NULL;
pcercuei 0:03b5121a232e 939 entry->valid = 1;
pcercuei 0:03b5121a232e 940 entry->okey = okey;
pcercuei 0:03b5121a232e 941
pcercuei 0:03b5121a232e 942
pcercuei 0:03b5121a232e 943 if (insert != NULL)
pcercuei 0:03b5121a232e 944 insert->next = entry;
pcercuei 0:03b5121a232e 945
pcercuei 0:03b5121a232e 946 dict->nbElems++;
pcercuei 0:03b5121a232e 947
pcercuei 0:03b5121a232e 948 if ((nbi > MAX_HASH_LEN) &&
pcercuei 0:03b5121a232e 949 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) {
pcercuei 0:03b5121a232e 950 if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0)
pcercuei 0:03b5121a232e 951 return(NULL);
pcercuei 0:03b5121a232e 952 }
pcercuei 0:03b5121a232e 953 /* Note that entry may have been freed at this point by xmlDictGrow */
pcercuei 0:03b5121a232e 954
pcercuei 0:03b5121a232e 955 return(ret);
pcercuei 0:03b5121a232e 956 }
pcercuei 0:03b5121a232e 957
pcercuei 0:03b5121a232e 958 /**
pcercuei 0:03b5121a232e 959 * xmlDictExists:
pcercuei 0:03b5121a232e 960 * @dict: the dictionnary
pcercuei 0:03b5121a232e 961 * @name: the name of the userdata
pcercuei 0:03b5121a232e 962 * @len: the length of the name, if -1 it is recomputed
pcercuei 0:03b5121a232e 963 *
pcercuei 0:03b5121a232e 964 * Check if the @name exists in the dictionnary @dict.
pcercuei 0:03b5121a232e 965 *
pcercuei 0:03b5121a232e 966 * Returns the internal copy of the name or NULL if not found.
pcercuei 0:03b5121a232e 967 */
pcercuei 0:03b5121a232e 968 const xmlChar *
pcercuei 0:03b5121a232e 969 xmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) {
pcercuei 0:03b5121a232e 970 unsigned long key, okey, nbi = 0;
pcercuei 0:03b5121a232e 971 xmlDictEntryPtr insert;
pcercuei 0:03b5121a232e 972 unsigned int l;
pcercuei 0:03b5121a232e 973
pcercuei 0:03b5121a232e 974 if ((dict == NULL) || (name == NULL))
pcercuei 0:03b5121a232e 975 return(NULL);
pcercuei 0:03b5121a232e 976
pcercuei 0:03b5121a232e 977 if (len < 0)
pcercuei 0:03b5121a232e 978 l = strlen((const char *) name);
pcercuei 0:03b5121a232e 979 else
pcercuei 0:03b5121a232e 980 l = len;
pcercuei 0:03b5121a232e 981 if (((dict->limit > 0) && (l >= dict->limit)) ||
pcercuei 0:03b5121a232e 982 (l > INT_MAX / 2))
pcercuei 0:03b5121a232e 983 return(NULL);
pcercuei 0:03b5121a232e 984
pcercuei 0:03b5121a232e 985 /*
pcercuei 0:03b5121a232e 986 * Check for duplicate and insertion location.
pcercuei 0:03b5121a232e 987 */
pcercuei 0:03b5121a232e 988 okey = xmlDictComputeKey(dict, name, l);
pcercuei 0:03b5121a232e 989 key = okey % dict->size;
pcercuei 0:03b5121a232e 990 if (dict->dict[key].valid == 0) {
pcercuei 0:03b5121a232e 991 insert = NULL;
pcercuei 0:03b5121a232e 992 } else {
pcercuei 0:03b5121a232e 993 for (insert = &(dict->dict[key]); insert->next != NULL;
pcercuei 0:03b5121a232e 994 insert = insert->next) {
pcercuei 0:03b5121a232e 995 #ifdef __GNUC__
pcercuei 0:03b5121a232e 996 if ((insert->okey == okey) && (insert->len == l)) {
pcercuei 0:03b5121a232e 997 if (!memcmp(insert->name, name, l))
pcercuei 0:03b5121a232e 998 return(insert->name);
pcercuei 0:03b5121a232e 999 }
pcercuei 0:03b5121a232e 1000 #else
pcercuei 0:03b5121a232e 1001 if ((insert->okey == okey) && (insert->len == l) &&
pcercuei 0:03b5121a232e 1002 (!xmlStrncmp(insert->name, name, l)))
pcercuei 0:03b5121a232e 1003 return(insert->name);
pcercuei 0:03b5121a232e 1004 #endif
pcercuei 0:03b5121a232e 1005 nbi++;
pcercuei 0:03b5121a232e 1006 }
pcercuei 0:03b5121a232e 1007 #ifdef __GNUC__
pcercuei 0:03b5121a232e 1008 if ((insert->okey == okey) && (insert->len == l)) {
pcercuei 0:03b5121a232e 1009 if (!memcmp(insert->name, name, l))
pcercuei 0:03b5121a232e 1010 return(insert->name);
pcercuei 0:03b5121a232e 1011 }
pcercuei 0:03b5121a232e 1012 #else
pcercuei 0:03b5121a232e 1013 if ((insert->okey == okey) && (insert->len == l) &&
pcercuei 0:03b5121a232e 1014 (!xmlStrncmp(insert->name, name, l)))
pcercuei 0:03b5121a232e 1015 return(insert->name);
pcercuei 0:03b5121a232e 1016 #endif
pcercuei 0:03b5121a232e 1017 }
pcercuei 0:03b5121a232e 1018
pcercuei 0:03b5121a232e 1019 if (dict->subdict) {
pcercuei 0:03b5121a232e 1020 unsigned long skey;
pcercuei 0:03b5121a232e 1021
pcercuei 0:03b5121a232e 1022 /* we cannot always reuse the same okey for the subdict */
pcercuei 0:03b5121a232e 1023 if (((dict->size == MIN_DICT_SIZE) &&
pcercuei 0:03b5121a232e 1024 (dict->subdict->size != MIN_DICT_SIZE)) ||
pcercuei 0:03b5121a232e 1025 ((dict->size != MIN_DICT_SIZE) &&
pcercuei 0:03b5121a232e 1026 (dict->subdict->size == MIN_DICT_SIZE)))
pcercuei 0:03b5121a232e 1027 skey = xmlDictComputeKey(dict->subdict, name, l);
pcercuei 0:03b5121a232e 1028 else
pcercuei 0:03b5121a232e 1029 skey = okey;
pcercuei 0:03b5121a232e 1030
pcercuei 0:03b5121a232e 1031 key = skey % dict->subdict->size;
pcercuei 0:03b5121a232e 1032 if (dict->subdict->dict[key].valid != 0) {
pcercuei 0:03b5121a232e 1033 xmlDictEntryPtr tmp;
pcercuei 0:03b5121a232e 1034
pcercuei 0:03b5121a232e 1035 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
pcercuei 0:03b5121a232e 1036 tmp = tmp->next) {
pcercuei 0:03b5121a232e 1037 #ifdef __GNUC__
pcercuei 0:03b5121a232e 1038 if ((tmp->okey == skey) && (tmp->len == l)) {
pcercuei 0:03b5121a232e 1039 if (!memcmp(tmp->name, name, l))
pcercuei 0:03b5121a232e 1040 return(tmp->name);
pcercuei 0:03b5121a232e 1041 }
pcercuei 0:03b5121a232e 1042 #else
pcercuei 0:03b5121a232e 1043 if ((tmp->okey == skey) && (tmp->len == l) &&
pcercuei 0:03b5121a232e 1044 (!xmlStrncmp(tmp->name, name, l)))
pcercuei 0:03b5121a232e 1045 return(tmp->name);
pcercuei 0:03b5121a232e 1046 #endif
pcercuei 0:03b5121a232e 1047 nbi++;
pcercuei 0:03b5121a232e 1048 }
pcercuei 0:03b5121a232e 1049 #ifdef __GNUC__
pcercuei 0:03b5121a232e 1050 if ((tmp->okey == skey) && (tmp->len == l)) {
pcercuei 0:03b5121a232e 1051 if (!memcmp(tmp->name, name, l))
pcercuei 0:03b5121a232e 1052 return(tmp->name);
pcercuei 0:03b5121a232e 1053 }
pcercuei 0:03b5121a232e 1054 #else
pcercuei 0:03b5121a232e 1055 if ((tmp->okey == skey) && (tmp->len == l) &&
pcercuei 0:03b5121a232e 1056 (!xmlStrncmp(tmp->name, name, l)))
pcercuei 0:03b5121a232e 1057 return(tmp->name);
pcercuei 0:03b5121a232e 1058 #endif
pcercuei 0:03b5121a232e 1059 }
pcercuei 0:03b5121a232e 1060 }
pcercuei 0:03b5121a232e 1061
pcercuei 0:03b5121a232e 1062 /* not found */
pcercuei 0:03b5121a232e 1063 return(NULL);
pcercuei 0:03b5121a232e 1064 }
pcercuei 0:03b5121a232e 1065
pcercuei 0:03b5121a232e 1066 /**
pcercuei 0:03b5121a232e 1067 * xmlDictQLookup:
pcercuei 0:03b5121a232e 1068 * @dict: the dictionnary
pcercuei 0:03b5121a232e 1069 * @prefix: the prefix
pcercuei 0:03b5121a232e 1070 * @name: the name
pcercuei 0:03b5121a232e 1071 *
pcercuei 0:03b5121a232e 1072 * Add the QName @prefix:@name to the hash @dict if not present.
pcercuei 0:03b5121a232e 1073 *
pcercuei 0:03b5121a232e 1074 * Returns the internal copy of the QName or NULL in case of internal error
pcercuei 0:03b5121a232e 1075 */
pcercuei 0:03b5121a232e 1076 const xmlChar *
pcercuei 0:03b5121a232e 1077 xmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) {
pcercuei 0:03b5121a232e 1078 unsigned long okey, key, nbi = 0;
pcercuei 0:03b5121a232e 1079 xmlDictEntryPtr entry;
pcercuei 0:03b5121a232e 1080 xmlDictEntryPtr insert;
pcercuei 0:03b5121a232e 1081 const xmlChar *ret;
pcercuei 0:03b5121a232e 1082 unsigned int len, plen, l;
pcercuei 0:03b5121a232e 1083
pcercuei 0:03b5121a232e 1084 if ((dict == NULL) || (name == NULL))
pcercuei 0:03b5121a232e 1085 return(NULL);
pcercuei 0:03b5121a232e 1086 if (prefix == NULL)
pcercuei 0:03b5121a232e 1087 return(xmlDictLookup(dict, name, -1));
pcercuei 0:03b5121a232e 1088
pcercuei 0:03b5121a232e 1089 l = len = strlen((const char *) name);
pcercuei 0:03b5121a232e 1090 plen = strlen((const char *) prefix);
pcercuei 0:03b5121a232e 1091 len += 1 + plen;
pcercuei 0:03b5121a232e 1092
pcercuei 0:03b5121a232e 1093 /*
pcercuei 0:03b5121a232e 1094 * Check for duplicate and insertion location.
pcercuei 0:03b5121a232e 1095 */
pcercuei 0:03b5121a232e 1096 okey = xmlDictComputeQKey(dict, prefix, plen, name, l);
pcercuei 0:03b5121a232e 1097 key = okey % dict->size;
pcercuei 0:03b5121a232e 1098 if (dict->dict[key].valid == 0) {
pcercuei 0:03b5121a232e 1099 insert = NULL;
pcercuei 0:03b5121a232e 1100 } else {
pcercuei 0:03b5121a232e 1101 for (insert = &(dict->dict[key]); insert->next != NULL;
pcercuei 0:03b5121a232e 1102 insert = insert->next) {
pcercuei 0:03b5121a232e 1103 if ((insert->okey == okey) && (insert->len == len) &&
pcercuei 0:03b5121a232e 1104 (xmlStrQEqual(prefix, name, insert->name)))
pcercuei 0:03b5121a232e 1105 return(insert->name);
pcercuei 0:03b5121a232e 1106 nbi++;
pcercuei 0:03b5121a232e 1107 }
pcercuei 0:03b5121a232e 1108 if ((insert->okey == okey) && (insert->len == len) &&
pcercuei 0:03b5121a232e 1109 (xmlStrQEqual(prefix, name, insert->name)))
pcercuei 0:03b5121a232e 1110 return(insert->name);
pcercuei 0:03b5121a232e 1111 }
pcercuei 0:03b5121a232e 1112
pcercuei 0:03b5121a232e 1113 if (dict->subdict) {
pcercuei 0:03b5121a232e 1114 unsigned long skey;
pcercuei 0:03b5121a232e 1115
pcercuei 0:03b5121a232e 1116 /* we cannot always reuse the same okey for the subdict */
pcercuei 0:03b5121a232e 1117 if (((dict->size == MIN_DICT_SIZE) &&
pcercuei 0:03b5121a232e 1118 (dict->subdict->size != MIN_DICT_SIZE)) ||
pcercuei 0:03b5121a232e 1119 ((dict->size != MIN_DICT_SIZE) &&
pcercuei 0:03b5121a232e 1120 (dict->subdict->size == MIN_DICT_SIZE)))
pcercuei 0:03b5121a232e 1121 skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l);
pcercuei 0:03b5121a232e 1122 else
pcercuei 0:03b5121a232e 1123 skey = okey;
pcercuei 0:03b5121a232e 1124
pcercuei 0:03b5121a232e 1125 key = skey % dict->subdict->size;
pcercuei 0:03b5121a232e 1126 if (dict->subdict->dict[key].valid != 0) {
pcercuei 0:03b5121a232e 1127 xmlDictEntryPtr tmp;
pcercuei 0:03b5121a232e 1128 for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL;
pcercuei 0:03b5121a232e 1129 tmp = tmp->next) {
pcercuei 0:03b5121a232e 1130 if ((tmp->okey == skey) && (tmp->len == len) &&
pcercuei 0:03b5121a232e 1131 (xmlStrQEqual(prefix, name, tmp->name)))
pcercuei 0:03b5121a232e 1132 return(tmp->name);
pcercuei 0:03b5121a232e 1133 nbi++;
pcercuei 0:03b5121a232e 1134 }
pcercuei 0:03b5121a232e 1135 if ((tmp->okey == skey) && (tmp->len == len) &&
pcercuei 0:03b5121a232e 1136 (xmlStrQEqual(prefix, name, tmp->name)))
pcercuei 0:03b5121a232e 1137 return(tmp->name);
pcercuei 0:03b5121a232e 1138 }
pcercuei 0:03b5121a232e 1139 key = okey % dict->size;
pcercuei 0:03b5121a232e 1140 }
pcercuei 0:03b5121a232e 1141
pcercuei 0:03b5121a232e 1142 ret = xmlDictAddQString(dict, prefix, plen, name, l);
pcercuei 0:03b5121a232e 1143 if (ret == NULL)
pcercuei 0:03b5121a232e 1144 return(NULL);
pcercuei 0:03b5121a232e 1145 if (insert == NULL) {
pcercuei 0:03b5121a232e 1146 entry = &(dict->dict[key]);
pcercuei 0:03b5121a232e 1147 } else {
pcercuei 0:03b5121a232e 1148 entry = xmlMalloc(sizeof(xmlDictEntry));
pcercuei 0:03b5121a232e 1149 if (entry == NULL)
pcercuei 0:03b5121a232e 1150 return(NULL);
pcercuei 0:03b5121a232e 1151 }
pcercuei 0:03b5121a232e 1152 entry->name = ret;
pcercuei 0:03b5121a232e 1153 entry->len = len;
pcercuei 0:03b5121a232e 1154 entry->next = NULL;
pcercuei 0:03b5121a232e 1155 entry->valid = 1;
pcercuei 0:03b5121a232e 1156 entry->okey = okey;
pcercuei 0:03b5121a232e 1157
pcercuei 0:03b5121a232e 1158 if (insert != NULL)
pcercuei 0:03b5121a232e 1159 insert->next = entry;
pcercuei 0:03b5121a232e 1160
pcercuei 0:03b5121a232e 1161 dict->nbElems++;
pcercuei 0:03b5121a232e 1162
pcercuei 0:03b5121a232e 1163 if ((nbi > MAX_HASH_LEN) &&
pcercuei 0:03b5121a232e 1164 (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN)))
pcercuei 0:03b5121a232e 1165 xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size);
pcercuei 0:03b5121a232e 1166 /* Note that entry may have been freed at this point by xmlDictGrow */
pcercuei 0:03b5121a232e 1167
pcercuei 0:03b5121a232e 1168 return(ret);
pcercuei 0:03b5121a232e 1169 }
pcercuei 0:03b5121a232e 1170
pcercuei 0:03b5121a232e 1171 /**
pcercuei 0:03b5121a232e 1172 * xmlDictOwns:
pcercuei 0:03b5121a232e 1173 * @dict: the dictionnary
pcercuei 0:03b5121a232e 1174 * @str: the string
pcercuei 0:03b5121a232e 1175 *
pcercuei 0:03b5121a232e 1176 * check if a string is owned by the disctionary
pcercuei 0:03b5121a232e 1177 *
pcercuei 0:03b5121a232e 1178 * Returns 1 if true, 0 if false and -1 in case of error
pcercuei 0:03b5121a232e 1179 * -1 in case of error
pcercuei 0:03b5121a232e 1180 */
pcercuei 0:03b5121a232e 1181 int
pcercuei 0:03b5121a232e 1182 xmlDictOwns(xmlDictPtr dict, const xmlChar *str) {
pcercuei 0:03b5121a232e 1183 xmlDictStringsPtr pool;
pcercuei 0:03b5121a232e 1184
pcercuei 0:03b5121a232e 1185 if ((dict == NULL) || (str == NULL))
pcercuei 0:03b5121a232e 1186 return(-1);
pcercuei 0:03b5121a232e 1187 pool = dict->strings;
pcercuei 0:03b5121a232e 1188 while (pool != NULL) {
pcercuei 0:03b5121a232e 1189 if ((str >= &pool->array[0]) && (str <= pool->free))
pcercuei 0:03b5121a232e 1190 return(1);
pcercuei 0:03b5121a232e 1191 pool = pool->next;
pcercuei 0:03b5121a232e 1192 }
pcercuei 0:03b5121a232e 1193 if (dict->subdict)
pcercuei 0:03b5121a232e 1194 return(xmlDictOwns(dict->subdict, str));
pcercuei 0:03b5121a232e 1195 return(0);
pcercuei 0:03b5121a232e 1196 }
pcercuei 0:03b5121a232e 1197
pcercuei 0:03b5121a232e 1198 /**
pcercuei 0:03b5121a232e 1199 * xmlDictSize:
pcercuei 0:03b5121a232e 1200 * @dict: the dictionnary
pcercuei 0:03b5121a232e 1201 *
pcercuei 0:03b5121a232e 1202 * Query the number of elements installed in the hash @dict.
pcercuei 0:03b5121a232e 1203 *
pcercuei 0:03b5121a232e 1204 * Returns the number of elements in the dictionnary or
pcercuei 0:03b5121a232e 1205 * -1 in case of error
pcercuei 0:03b5121a232e 1206 */
pcercuei 0:03b5121a232e 1207 int
pcercuei 0:03b5121a232e 1208 xmlDictSize(xmlDictPtr dict) {
pcercuei 0:03b5121a232e 1209 if (dict == NULL)
pcercuei 0:03b5121a232e 1210 return(-1);
pcercuei 0:03b5121a232e 1211 if (dict->subdict)
pcercuei 0:03b5121a232e 1212 return(dict->nbElems + dict->subdict->nbElems);
pcercuei 0:03b5121a232e 1213 return(dict->nbElems);
pcercuei 0:03b5121a232e 1214 }
pcercuei 0:03b5121a232e 1215
pcercuei 0:03b5121a232e 1216 /**
pcercuei 0:03b5121a232e 1217 * xmlDictSetLimit:
pcercuei 0:03b5121a232e 1218 * @dict: the dictionnary
pcercuei 0:03b5121a232e 1219 * @limit: the limit in bytes
pcercuei 0:03b5121a232e 1220 *
pcercuei 0:03b5121a232e 1221 * Set a size limit for the dictionary
pcercuei 0:03b5121a232e 1222 * Added in 2.9.0
pcercuei 0:03b5121a232e 1223 *
pcercuei 0:03b5121a232e 1224 * Returns the previous limit of the dictionary or 0
pcercuei 0:03b5121a232e 1225 */
pcercuei 0:03b5121a232e 1226 size_t
pcercuei 0:03b5121a232e 1227 xmlDictSetLimit(xmlDictPtr dict, size_t limit) {
pcercuei 0:03b5121a232e 1228 size_t ret;
pcercuei 0:03b5121a232e 1229
pcercuei 0:03b5121a232e 1230 if (dict == NULL)
pcercuei 0:03b5121a232e 1231 return(0);
pcercuei 0:03b5121a232e 1232 ret = dict->limit;
pcercuei 0:03b5121a232e 1233 dict->limit = limit;
pcercuei 0:03b5121a232e 1234 return(ret);
pcercuei 0:03b5121a232e 1235 }
pcercuei 0:03b5121a232e 1236
pcercuei 0:03b5121a232e 1237 /**
pcercuei 0:03b5121a232e 1238 * xmlDictGetUsage:
pcercuei 0:03b5121a232e 1239 * @dict: the dictionnary
pcercuei 0:03b5121a232e 1240 *
pcercuei 0:03b5121a232e 1241 * Get how much memory is used by a dictionary for strings
pcercuei 0:03b5121a232e 1242 * Added in 2.9.0
pcercuei 0:03b5121a232e 1243 *
pcercuei 0:03b5121a232e 1244 * Returns the amount of strings allocated
pcercuei 0:03b5121a232e 1245 */
pcercuei 0:03b5121a232e 1246 size_t
pcercuei 0:03b5121a232e 1247 xmlDictGetUsage(xmlDictPtr dict) {
pcercuei 0:03b5121a232e 1248 xmlDictStringsPtr pool;
pcercuei 0:03b5121a232e 1249 size_t limit = 0;
pcercuei 0:03b5121a232e 1250
pcercuei 0:03b5121a232e 1251 if (dict == NULL)
pcercuei 0:03b5121a232e 1252 return(0);
pcercuei 0:03b5121a232e 1253 pool = dict->strings;
pcercuei 0:03b5121a232e 1254 while (pool != NULL) {
pcercuei 0:03b5121a232e 1255 limit += pool->size;
pcercuei 0:03b5121a232e 1256 pool = pool->next;
pcercuei 0:03b5121a232e 1257 }
pcercuei 0:03b5121a232e 1258 return(limit);
pcercuei 0:03b5121a232e 1259 }
pcercuei 0:03b5121a232e 1260
pcercuei 0:03b5121a232e 1261 #define bottom_dict
pcercuei 0:03b5121a232e 1262 #include "elfgcchack.h"
pcercuei 0:03b5121a232e 1263