1ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 2ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * dict.c: dictionary of reusable strings, just used to avoid allocation 3ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * and freeing operations. 4ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 5df143a5041f03a22808b59c76698770b74692815Selim Gurun * Copyright (C) 2003-2012 Daniel Veillard. 6ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 7ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Permission to use, copy, modify, and distribute this software for any 8ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * purpose with or without fee is hereby granted, provided that the above 9ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * copyright notice and this permission notice appear in all copies. 10ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 11ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED 12ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF 13ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE AUTHORS AND 14ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * CONTRIBUTORS ACCEPT NO RESPONSIBILITY IN ANY CONCEIVABLE MANNER. 15ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 16ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Author: daniel@veillard.com 17ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 18ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 19ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#define IN_LIBXML 20ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include "libxml.h" 21ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 2294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#include <limits.h> 23df143a5041f03a22808b59c76698770b74692815Selim Gurun#ifdef HAVE_STDLIB_H 24df143a5041f03a22808b59c76698770b74692815Selim Gurun#include <stdlib.h> 25df143a5041f03a22808b59c76698770b74692815Selim Gurun#endif 26df143a5041f03a22808b59c76698770b74692815Selim Gurun#ifdef HAVE_TIME_H 27df143a5041f03a22808b59c76698770b74692815Selim Gurun#include <time.h> 28df143a5041f03a22808b59c76698770b74692815Selim Gurun#endif 29df143a5041f03a22808b59c76698770b74692815Selim Gurun 30df143a5041f03a22808b59c76698770b74692815Selim Gurun/* 31df143a5041f03a22808b59c76698770b74692815Selim Gurun * Following http://www.ocert.org/advisories/ocert-2011-003.html 32df143a5041f03a22808b59c76698770b74692815Selim Gurun * it seems that having hash randomization might be a good idea 33df143a5041f03a22808b59c76698770b74692815Selim Gurun * when using XML with untrusted data 34df143a5041f03a22808b59c76698770b74692815Selim Gurun * Note1: that it works correctly only if compiled with WITH_BIG_KEY 35df143a5041f03a22808b59c76698770b74692815Selim Gurun * which is the default. 36df143a5041f03a22808b59c76698770b74692815Selim Gurun * Note2: the fast function used for a small dict won't protect very 37df143a5041f03a22808b59c76698770b74692815Selim Gurun * well but since the attack is based on growing a very big hash 38df143a5041f03a22808b59c76698770b74692815Selim Gurun * list we will use the BigKey algo as soon as the hash size grows 39df143a5041f03a22808b59c76698770b74692815Selim Gurun * over MIN_DICT_SIZE so this actually works 40df143a5041f03a22808b59c76698770b74692815Selim Gurun */ 41df143a5041f03a22808b59c76698770b74692815Selim Gurun#if defined(HAVE_RAND) && defined(HAVE_SRAND) && defined(HAVE_TIME) 42df143a5041f03a22808b59c76698770b74692815Selim Gurun#define DICT_RANDOMIZATION 43df143a5041f03a22808b59c76698770b74692815Selim Gurun#endif 44df143a5041f03a22808b59c76698770b74692815Selim Gurun 45ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include <string.h> 4660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef HAVE_STDINT_H 4760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#include <stdint.h> 4860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#else 4960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef HAVE_INTTYPES_H 5060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#include <inttypes.h> 5160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#elif defined(WIN32) 5260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scotttypedef unsigned __int32 uint32_t; 5360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 5460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 55ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include <libxml/tree.h> 56ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include <libxml/dict.h> 57ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include <libxml/xmlmemory.h> 58ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include <libxml/xmlerror.h> 59ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include <libxml/globals.h> 60ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 6160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott/* #define DEBUG_GROW */ 6260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott/* #define DICT_DEBUG_PATTERNS */ 6360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 6460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#define MAX_HASH_LEN 3 65ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#define MIN_DICT_SIZE 128 66ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#define MAX_DICT_HASH 8 * 2048 6760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#define WITH_BIG_KEY 6860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 6960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef WITH_BIG_KEY 70df143a5041f03a22808b59c76698770b74692815Selim Gurun#define xmlDictComputeKey(dict, name, len) \ 71df143a5041f03a22808b59c76698770b74692815Selim Gurun (((dict)->size == MIN_DICT_SIZE) ? \ 72df143a5041f03a22808b59c76698770b74692815Selim Gurun xmlDictComputeFastKey(name, len, (dict)->seed) : \ 73df143a5041f03a22808b59c76698770b74692815Selim Gurun xmlDictComputeBigKey(name, len, (dict)->seed)) 74df143a5041f03a22808b59c76698770b74692815Selim Gurun 75df143a5041f03a22808b59c76698770b74692815Selim Gurun#define xmlDictComputeQKey(dict, prefix, plen, name, len) \ 76df143a5041f03a22808b59c76698770b74692815Selim Gurun (((prefix) == NULL) ? \ 77df143a5041f03a22808b59c76698770b74692815Selim Gurun (xmlDictComputeKey(dict, name, len)) : \ 78df143a5041f03a22808b59c76698770b74692815Selim Gurun (((dict)->size == MIN_DICT_SIZE) ? \ 79df143a5041f03a22808b59c76698770b74692815Selim Gurun xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) : \ 80df143a5041f03a22808b59c76698770b74692815Selim Gurun xmlDictComputeBigQKey(prefix, plen, name, len, (dict)->seed))) 8160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 8260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#else /* !WITH_BIG_KEY */ 83df143a5041f03a22808b59c76698770b74692815Selim Gurun#define xmlDictComputeKey(dict, name, len) \ 84df143a5041f03a22808b59c76698770b74692815Selim Gurun xmlDictComputeFastKey(name, len, (dict)->seed) 85df143a5041f03a22808b59c76698770b74692815Selim Gurun#define xmlDictComputeQKey(dict, prefix, plen, name, len) \ 86df143a5041f03a22808b59c76698770b74692815Selim Gurun xmlDictComputeFastQKey(prefix, plen, name, len, (dict)->seed) 8760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif /* WITH_BIG_KEY */ 88ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 89ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 90ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * An entry in the dictionnary 91ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 92ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projecttypedef struct _xmlDictEntry xmlDictEntry; 93ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projecttypedef xmlDictEntry *xmlDictEntryPtr; 94ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstruct _xmlDictEntry { 95ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project struct _xmlDictEntry *next; 96ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project const xmlChar *name; 9794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun unsigned int len; 98ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project int valid; 9960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott unsigned long okey; 100ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project}; 101ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 102ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projecttypedef struct _xmlDictStrings xmlDictStrings; 103ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projecttypedef xmlDictStrings *xmlDictStringsPtr; 104ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstruct _xmlDictStrings { 105ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictStringsPtr next; 106ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlChar *free; 107ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlChar *end; 10894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t size; 10994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t nbStrings; 110ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlChar array[1]; 111ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project}; 112ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 113ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * The entire dictionnary 114ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 115ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstruct _xmlDict { 116ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project int ref_counter; 117ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 118ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project struct _xmlDictEntry *dict; 11994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t size; 12094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun unsigned int nbElems; 121ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictStringsPtr strings; 122ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 123ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project struct _xmlDict *subdict; 124df143a5041f03a22808b59c76698770b74692815Selim Gurun /* used for randomization */ 125df143a5041f03a22808b59c76698770b74692815Selim Gurun int seed; 12694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun /* used to impose a limit on size */ 12794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t limit; 128ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project}; 129ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 130ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 131ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * A mutex for modifying the reference counter for shared 132ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * dictionaries. 133ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 134ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstatic xmlRMutexPtr xmlDictMutex = NULL; 135ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 136ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 137ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Whether the dictionary mutex was initialized. 138ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 139ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstatic int xmlDictInitialized = 0; 140ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 14194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#ifdef DICT_RANDOMIZATION 14294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#ifdef HAVE_RAND_R 14394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun/* 14494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Internal data for random function, protected by xmlDictMutex 14594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun */ 14694442ad4107000e6d49f9b85a46a591495a57632Selim Gurunstatic unsigned int rand_seed = 0; 14794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#endif 14894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#endif 14994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 150ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 151ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlInitializeDict: 152ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 153ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Do the dictionary mutex initialization. 15494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * this function is deprecated 15594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * 15694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Returns 0 if initialization was already done, and 1 if that 15794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * call led to the initialization 15894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun */ 15994442ad4107000e6d49f9b85a46a591495a57632Selim Gurunint xmlInitializeDict(void) { 16094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(0); 16194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun} 16294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 16394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun/** 16494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * __xmlInitializeDict: 16594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * 16694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * This function is not public 16794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Do the dictionary mutex initialization. 168ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * this function is not thread safe, initialization should 16994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * normally be done once at setup when called from xmlOnceInit() 17094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * we may also land in this code if thread support is not compiled in 17194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * 17294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Returns 0 if initialization was already done, and 1 if that 17394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * call led to the initialization 174ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 17594442ad4107000e6d49f9b85a46a591495a57632Selim Gurunint __xmlInitializeDict(void) { 176ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (xmlDictInitialized) 177ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(1); 178ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 179ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((xmlDictMutex = xmlNewRMutex()) == NULL) 180ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(0); 18194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun xmlRMutexLock(xmlDictMutex); 182ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 183df143a5041f03a22808b59c76698770b74692815Selim Gurun#ifdef DICT_RANDOMIZATION 18494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#ifdef HAVE_RAND_R 18594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun rand_seed = time(NULL); 18694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun rand_r(& rand_seed); 18794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#else 188df143a5041f03a22808b59c76698770b74692815Selim Gurun srand(time(NULL)); 189df143a5041f03a22808b59c76698770b74692815Selim Gurun#endif 19094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#endif 191ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictInitialized = 1; 19294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun xmlRMutexUnlock(xmlDictMutex); 193ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(1); 194ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 195ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 19694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#ifdef DICT_RANDOMIZATION 19794442ad4107000e6d49f9b85a46a591495a57632Selim Gurunint __xmlRandom(void) { 19894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun int ret; 19994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 20094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (xmlDictInitialized == 0) 20194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun __xmlInitializeDict(); 20294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 20394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun xmlRMutexLock(xmlDictMutex); 20494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#ifdef HAVE_RAND_R 20594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun ret = rand_r(& rand_seed); 20694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#else 20794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun ret = rand(); 20894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#endif 20994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun xmlRMutexUnlock(xmlDictMutex); 21094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(ret); 21194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun} 21294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun#endif 21394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 214ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 215ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictCleanup: 216ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 21794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Free the dictionary mutex. Do not call unless sure the library 21894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * is not in use anymore ! 219ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 220ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectvoid 221ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictCleanup(void) { 222ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (!xmlDictInitialized) 223ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return; 224ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 225ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFreeRMutex(xmlDictMutex); 226ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 227ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictInitialized = 0; 228ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 229ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 230ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 231ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictAddString: 232ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 233ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @name: the name of the userdata 23494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * @len: the length of the name 235ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 236ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Add the string to the array[s] 237ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 238ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the pointer of the local string, or NULL in case of error. 239ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 240ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstatic const xmlChar * 24194442ad4107000e6d49f9b85a46a591495a57632Selim GurunxmlDictAddString(xmlDictPtr dict, const xmlChar *name, unsigned int namelen) { 242ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictStringsPtr pool; 243ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project const xmlChar *ret; 24494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */ 24594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t limit = 0; 246ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 24760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef DICT_DEBUG_PATTERNS 24860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott fprintf(stderr, "-"); 24960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 250ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = dict->strings; 251ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project while (pool != NULL) { 252ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (pool->end - pool->free > namelen) 253ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project goto found_pool; 254ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (pool->size > size) size = pool->size; 25594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun limit += pool->size; 256ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = pool->next; 257ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 258ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* 259ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Not found, need to allocate 260ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 261ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (pool == NULL) { 26294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((dict->limit > 0) && (limit > dict->limit)) { 26394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(NULL); 26494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun } 26594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 266ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (size == 0) size = 1000; 267ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project else size *= 4; /* exponential growth */ 26894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (size < 4 * namelen) 269ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project size = 4 * namelen; /* just in case ! */ 270ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size); 271ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (pool == NULL) 272ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 273ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->size = size; 274ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->nbStrings = 0; 275ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->free = &pool->array[0]; 276ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->end = &pool->array[size]; 277ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->next = dict->strings; 278ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->strings = pool; 27960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef DICT_DEBUG_PATTERNS 28060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott fprintf(stderr, "+"); 28160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 282ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 283ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectfound_pool: 284ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project ret = pool->free; 285ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project memcpy(pool->free, name, namelen); 286ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->free += namelen; 287ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project *(pool->free++) = 0; 28860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott pool->nbStrings++; 289ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(ret); 290ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 291ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 292ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 293ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictAddQString: 294ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 295ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @prefix: the prefix of the userdata 29660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * @plen: the prefix length 297ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @name: the name of the userdata 29894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * @len: the length of the name 299ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 300ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Add the QName to the array[s] 301ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 302ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the pointer of the local string, or NULL in case of error. 303ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 304ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstatic const xmlChar * 30594442ad4107000e6d49f9b85a46a591495a57632Selim GurunxmlDictAddQString(xmlDictPtr dict, const xmlChar *prefix, unsigned int plen, 30694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun const xmlChar *name, unsigned int namelen) 307ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project{ 308ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictStringsPtr pool; 309ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project const xmlChar *ret; 31094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t size = 0; /* + sizeof(_xmlDictStrings) == 1024 */ 31194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t limit = 0; 312ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 313ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (prefix == NULL) return(xmlDictAddString(dict, name, namelen)); 314ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 31560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef DICT_DEBUG_PATTERNS 31660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott fprintf(stderr, "="); 31760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 318ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = dict->strings; 319ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project while (pool != NULL) { 32060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (pool->end - pool->free > namelen + plen + 1) 321ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project goto found_pool; 322ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (pool->size > size) size = pool->size; 32394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun limit += pool->size; 324ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = pool->next; 325ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 326ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* 327ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Not found, need to allocate 328ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 329ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (pool == NULL) { 33094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((dict->limit > 0) && (limit > dict->limit)) { 33194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(NULL); 33294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun } 33394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 334ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (size == 0) size = 1000; 335ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project else size *= 4; /* exponential growth */ 33660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (size < 4 * (namelen + plen + 1)) 33760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott size = 4 * (namelen + plen + 1); /* just in case ! */ 338ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = (xmlDictStringsPtr) xmlMalloc(sizeof(xmlDictStrings) + size); 339ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (pool == NULL) 340ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 341ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->size = size; 342ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->nbStrings = 0; 343ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->free = &pool->array[0]; 344ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->end = &pool->array[size]; 345ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->next = dict->strings; 346ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->strings = pool; 34760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef DICT_DEBUG_PATTERNS 34860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott fprintf(stderr, "+"); 34960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 350ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 351ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectfound_pool: 352ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project ret = pool->free; 353ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project memcpy(pool->free, prefix, plen); 354ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->free += plen; 355ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project *(pool->free++) = ':'; 356ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project memcpy(pool->free, name, namelen); 357ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool->free += namelen; 358ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project *(pool->free++) = 0; 35960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott pool->nbStrings++; 360ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(ret); 361ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 362ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 36360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef WITH_BIG_KEY 36460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott/* 36560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * xmlDictComputeBigKey: 36660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 36760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Calculate a hash key using a good hash function that works well for 36860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * larger hash table sizes. 36960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 37060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Hash function by "One-at-a-Time Hash" see 37160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * http://burtleburtle.net/bob/hash/doobs.html 37260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott */ 37360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 37460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scottstatic uint32_t 375df143a5041f03a22808b59c76698770b74692815Selim GurunxmlDictComputeBigKey(const xmlChar* data, int namelen, int seed) { 37660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott uint32_t hash; 37760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott int i; 37860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 37960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (namelen <= 0 || data == NULL) return(0); 38060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 381df143a5041f03a22808b59c76698770b74692815Selim Gurun hash = seed; 38260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 38360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott for (i = 0;i < namelen; i++) { 38460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += data[i]; 38560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 10); 38660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash ^= (hash >> 6); 38760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } 38860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 3); 38960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash ^= (hash >> 11); 39060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 15); 39160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 39260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott return hash; 39360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott} 39460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 39560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott/* 39660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * xmlDictComputeBigQKey: 39760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 39860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Calculate a hash key for two strings using a good hash function 39960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * that works well for larger hash table sizes. 40060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 40160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Hash function by "One-at-a-Time Hash" see 40260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * http://burtleburtle.net/bob/hash/doobs.html 40360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 40460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Neither of the two strings must be NULL. 40560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott */ 40660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scottstatic unsigned long 40760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick ScottxmlDictComputeBigQKey(const xmlChar *prefix, int plen, 408df143a5041f03a22808b59c76698770b74692815Selim Gurun const xmlChar *name, int len, int seed) 40960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott{ 41060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott uint32_t hash; 41160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott int i; 41260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 413df143a5041f03a22808b59c76698770b74692815Selim Gurun hash = seed; 41460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 41560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott for (i = 0;i < plen; i++) { 41660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += prefix[i]; 41760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 10); 41860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash ^= (hash >> 6); 41960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } 42060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += ':'; 42160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 10); 42260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash ^= (hash >> 6); 42360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 42460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott for (i = 0;i < len; i++) { 42560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += name[i]; 42660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 10); 42760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash ^= (hash >> 6); 42860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } 42960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 3); 43060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash ^= (hash >> 11); 43160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott hash += (hash << 15); 43260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 43360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott return hash; 43460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott} 43560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif /* WITH_BIG_KEY */ 43660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 437ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 43860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * xmlDictComputeFastKey: 43960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 44060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Calculate a hash key using a fast hash function that works well 44160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * for low hash table fill. 442ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 443ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstatic unsigned long 444df143a5041f03a22808b59c76698770b74692815Selim GurunxmlDictComputeFastKey(const xmlChar *name, int namelen, int seed) { 445df143a5041f03a22808b59c76698770b74692815Selim Gurun unsigned long value = seed; 44660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 447ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (name == NULL) return(0); 448ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project value = *name; 449ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project value <<= 5; 450ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (namelen > 10) { 451ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project value += name[namelen - 1]; 452ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project namelen = 10; 453ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 454ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project switch (namelen) { 455ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 10: value += name[9]; 456ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 9: value += name[8]; 457ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 8: value += name[7]; 458ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 7: value += name[6]; 459ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 6: value += name[5]; 460ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 5: value += name[4]; 461ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 4: value += name[3]; 462ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 3: value += name[2]; 463ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 2: value += name[1]; 464ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project default: break; 465ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 466ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(value); 467ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 468ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 469ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/* 47060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * xmlDictComputeFastQKey: 47160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 47260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Calculate a hash key for two strings using a fast hash function 47360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * that works well for low hash table fill. 47460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * 47560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * Neither of the two strings must be NULL. 476ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 477ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstatic unsigned long 47860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick ScottxmlDictComputeFastQKey(const xmlChar *prefix, int plen, 479df143a5041f03a22808b59c76698770b74692815Selim Gurun const xmlChar *name, int len, int seed) 480ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project{ 481df143a5041f03a22808b59c76698770b74692815Selim Gurun unsigned long value = (unsigned long) seed; 482ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 483ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (plen == 0) 484ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project value += 30 * (unsigned long) ':'; 485ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project else 486ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project value += 30 * (*prefix); 48760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 488ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (len > 10) { 489ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project value += name[len - (plen + 1 + 1)]; 490ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project len = 10; 491ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (plen > 10) 492ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project plen = 10; 493ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 494ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project switch (plen) { 495ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 10: value += prefix[9]; 496ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 9: value += prefix[8]; 497ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 8: value += prefix[7]; 498ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 7: value += prefix[6]; 499ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 6: value += prefix[5]; 500ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 5: value += prefix[4]; 501ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 4: value += prefix[3]; 502ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 3: value += prefix[2]; 503ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 2: value += prefix[1]; 504ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 1: value += prefix[0]; 505ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project default: break; 506ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 507ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project len -= plen; 508ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (len > 0) { 509ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project value += (unsigned long) ':'; 510ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project len--; 511ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 512ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project switch (len) { 513ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 10: value += name[9]; 514ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 9: value += name[8]; 515ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 8: value += name[7]; 516ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 7: value += name[6]; 517ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 6: value += name[5]; 518ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 5: value += name[4]; 519ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 4: value += name[3]; 520ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 3: value += name[2]; 521ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 2: value += name[1]; 522ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project case 1: value += name[0]; 523ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project default: break; 524ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 525ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(value); 526ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 527ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 528ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 529ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictCreate: 530ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 531ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Create a new dictionary 532ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 533ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the newly created dictionnary, or NULL if an error occured. 534ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 535ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictPtr 536ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictCreate(void) { 537ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictPtr dict; 538ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 539ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (!xmlDictInitialized) 54094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!__xmlInitializeDict()) 541ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 54260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 54360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef DICT_DEBUG_PATTERNS 54460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott fprintf(stderr, "C"); 54560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 54660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 547ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict = xmlMalloc(sizeof(xmlDict)); 548ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict) { 549ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->ref_counter = 1; 55094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun dict->limit = 0; 551ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 552ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->size = MIN_DICT_SIZE; 553ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->nbElems = 0; 554ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->dict = xmlMalloc(MIN_DICT_SIZE * sizeof(xmlDictEntry)); 555ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->strings = NULL; 556ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->subdict = NULL; 557ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->dict) { 55860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott memset(dict->dict, 0, MIN_DICT_SIZE * sizeof(xmlDictEntry)); 559df143a5041f03a22808b59c76698770b74692815Selim Gurun#ifdef DICT_RANDOMIZATION 56094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun dict->seed = __xmlRandom(); 561df143a5041f03a22808b59c76698770b74692815Selim Gurun#else 562df143a5041f03a22808b59c76698770b74692815Selim Gurun dict->seed = 0; 563df143a5041f03a22808b59c76698770b74692815Selim Gurun#endif 56460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott return(dict); 565ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 566ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFree(dict); 567ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 568ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 569ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 570ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 571ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 572ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictCreateSub: 573ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @sub: an existing dictionnary 574ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 575ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Create a new dictionary, inheriting strings from the read-only 576ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * dictionnary @sub. On lookup, strings are first searched in the 577ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * new dictionnary, then in @sub, and if not found are created in the 578ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * new dictionnary. 579ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 580ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the newly created dictionnary, or NULL if an error occured. 581ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 582ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictPtr 583ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictCreateSub(xmlDictPtr sub) { 584ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictPtr dict = xmlDictCreate(); 58560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 586ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((dict != NULL) && (sub != NULL)) { 58760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef DICT_DEBUG_PATTERNS 58860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott fprintf(stderr, "R"); 58960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 590df143a5041f03a22808b59c76698770b74692815Selim Gurun dict->seed = sub->seed; 591ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->subdict = sub; 592ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictReference(dict->subdict); 593ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 594ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(dict); 595ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 596ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 597ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 598ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictReference: 599ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 600ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 601ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Increment the reference counter of a dictionary 602ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 603ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns 0 in case of success and -1 in case of error 604ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 605ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectint 606ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictReference(xmlDictPtr dict) { 607ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (!xmlDictInitialized) 60894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!__xmlInitializeDict()) 609ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 610ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 611ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict == NULL) return -1; 612ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlRMutexLock(xmlDictMutex); 613ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->ref_counter++; 614ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlRMutexUnlock(xmlDictMutex); 615ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(0); 616ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 617ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 618ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 619ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictGrow: 620ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 621ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @size: the new size of the dictionnary 622ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 623ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * resize the dictionnary 624ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 625ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns 0 in case of success, -1 in case of failure 626ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 627ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectstatic int 62894442ad4107000e6d49f9b85a46a591495a57632Selim GurunxmlDictGrow(xmlDictPtr dict, size_t size) { 62960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott unsigned long key, okey; 63094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t oldsize, i; 631ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr iter, next; 632ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project struct _xmlDictEntry *olddict; 633ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef DEBUG_GROW 634ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project unsigned long nbElem = 0; 635ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 63660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott int ret = 0; 63760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott int keep_keys = 1; 63860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 639ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict == NULL) 640ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 641ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (size < 8) 642ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 643ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (size > 8 * 2048) 644ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 645ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 64660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#ifdef DICT_DEBUG_PATTERNS 64760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott fprintf(stderr, "*"); 64860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott#endif 64960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 650ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project oldsize = dict->size; 651ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project olddict = dict->dict; 652ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (olddict == NULL) 653ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 65460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (oldsize == MIN_DICT_SIZE) 65560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott keep_keys = 0; 65660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 657ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->dict = xmlMalloc(size * sizeof(xmlDictEntry)); 658ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->dict == NULL) { 659ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->dict = olddict; 660ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 661ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 662ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project memset(dict->dict, 0, size * sizeof(xmlDictEntry)); 663ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->size = size; 664ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 665ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* If the two loops are merged, there would be situations where 66660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott a new entry needs to allocated and data copied into it from 66760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott the main dict. It is nicer to run through the array twice, first 66860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott copying all the elements in the main array (less probability of 66960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott allocate) and then the rest, so we only free in the second loop. 670ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 671ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (i = 0; i < oldsize; i++) { 67260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (olddict[i].valid == 0) 673ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project continue; 67460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 67560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (keep_keys) 67660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott okey = olddict[i].okey; 67760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott else 67860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott okey = xmlDictComputeKey(dict, olddict[i].name, olddict[i].len); 67960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott key = okey % dict->size; 68060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 68160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (dict->dict[key].valid == 0) { 68260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott memcpy(&(dict->dict[key]), &(olddict[i]), sizeof(xmlDictEntry)); 68360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott dict->dict[key].next = NULL; 68460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott dict->dict[key].okey = okey; 68560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } else { 68660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott xmlDictEntryPtr entry; 68760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 68860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry = xmlMalloc(sizeof(xmlDictEntry)); 68960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (entry != NULL) { 69060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry->name = olddict[i].name; 69160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry->len = olddict[i].len; 69260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry->okey = okey; 69360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry->next = dict->dict[key].next; 69460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry->valid = 1; 69560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott dict->dict[key].next = entry; 69660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } else { 69760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott /* 69860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * we don't have much ways to alert from herei 69960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * result is loosing an entry and unicity garantee 70060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott */ 70160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott ret = -1; 70260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } 70360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } 704ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef DEBUG_GROW 705ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbElem++; 706ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 707ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 708ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 709ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (i = 0; i < oldsize; i++) { 710ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project iter = olddict[i].next; 711ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project while (iter) { 712ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project next = iter->next; 713ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 714ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* 715ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * put back the entry in the new dict 716ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 717ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 71860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (keep_keys) 71960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott okey = iter->okey; 72060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott else 72160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott okey = xmlDictComputeKey(dict, iter->name, iter->len); 72260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott key = okey % dict->size; 723ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->dict[key].valid == 0) { 724ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project memcpy(&(dict->dict[key]), iter, sizeof(xmlDictEntry)); 725ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->dict[key].next = NULL; 726ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->dict[key].valid = 1; 72760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott dict->dict[key].okey = okey; 728ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFree(iter); 729ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } else { 73060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott iter->next = dict->dict[key].next; 73160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott iter->okey = okey; 73260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott dict->dict[key].next = iter; 733ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 734ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 735ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef DEBUG_GROW 736ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbElem++; 737ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 738ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 739ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project iter = next; 740ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 741ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 742ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 743ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFree(olddict); 744ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 745ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef DEBUG_GROW 746ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlGenericError(xmlGenericErrorContext, 74794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun "xmlDictGrow : from %lu to %lu, %u elems\n", oldsize, size, nbElem); 748ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 749ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 75060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott return(ret); 751ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 752ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 753ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 754ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictFree: 755ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 756ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 757ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Free the hash @dict and its contents. The userdata is 758ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * deallocated with @f if provided. 759ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 760ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectvoid 761ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictFree(xmlDictPtr dict) { 76294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t i; 763ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr iter; 764ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr next; 765ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project int inside_dict = 0; 766ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictStringsPtr pool, nextp; 767ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 768ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict == NULL) 769ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return; 770ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 771ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (!xmlDictInitialized) 77294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!__xmlInitializeDict()) 773ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return; 774ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 775ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* decrement the counter, it may be shared by a parser and docs */ 776ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlRMutexLock(xmlDictMutex); 777ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->ref_counter--; 778ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->ref_counter > 0) { 779ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlRMutexUnlock(xmlDictMutex); 780ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return; 781ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 782ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 783ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlRMutexUnlock(xmlDictMutex); 784ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 785ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict != NULL) { 786ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictFree(dict->subdict); 787ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 788ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 789ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->dict) { 790ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for(i = 0; ((i < dict->size) && (dict->nbElems > 0)); i++) { 791ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project iter = &(dict->dict[i]); 792ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (iter->valid == 0) 793ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project continue; 794ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project inside_dict = 1; 795ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project while (iter) { 796ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project next = iter->next; 797ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (!inside_dict) 798ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFree(iter); 799ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->nbElems--; 800ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project inside_dict = 0; 801ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project iter = next; 802ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 803ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 804ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFree(dict->dict); 805ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 806ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = dict->strings; 807ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project while (pool != NULL) { 808ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nextp = pool->next; 809ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFree(pool); 810ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = nextp; 811ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 812ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlFree(dict); 813ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 814ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 815ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 816ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictLookup: 817ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 818ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @name: the name of the userdata 819ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @len: the length of the name, if -1 it is recomputed 820ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 821ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Add the @name to the dictionnary @dict if not present. 822ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 823ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the internal copy of the name or NULL in case of internal error 824ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 825ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectconst xmlChar * 826ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictLookup(xmlDictPtr dict, const xmlChar *name, int len) { 827ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project unsigned long key, okey, nbi = 0; 828ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr entry; 829ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr insert; 830ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project const xmlChar *ret; 83194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun unsigned int l; 832ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 833ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((dict == NULL) || (name == NULL)) 834ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 835ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 836ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (len < 0) 83794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun l = strlen((const char *) name); 83894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun else 83994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun l = len; 84094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 84194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (((dict->limit > 0) && (l >= dict->limit)) || 84294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (l > INT_MAX / 2)) 84394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(NULL); 844ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 845ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* 846ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Check for duplicate and insertion location. 847ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 84894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun okey = xmlDictComputeKey(dict, name, l); 849ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project key = okey % dict->size; 850ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->dict[key].valid == 0) { 851ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert = NULL; 852ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } else { 853ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (insert = &(dict->dict[key]); insert->next != NULL; 854ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert = insert->next) { 855ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 85694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l)) { 85794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(insert->name, name, l)) 858ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 859ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 860ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 86194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l) && 86294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(insert->name, name, l))) 863ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 864ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 865ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbi++; 866ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 867ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 86894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l)) { 86994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(insert->name, name, l)) 870ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 871ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 872ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 87394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l) && 87494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(insert->name, name, l))) 875ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 876ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 877ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 878ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 879ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict) { 88060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott unsigned long skey; 88160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 88260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott /* we cannot always reuse the same okey for the subdict */ 88360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (((dict->size == MIN_DICT_SIZE) && 88460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott (dict->subdict->size != MIN_DICT_SIZE)) || 88560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott ((dict->size != MIN_DICT_SIZE) && 88660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott (dict->subdict->size == MIN_DICT_SIZE))) 88794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun skey = xmlDictComputeKey(dict->subdict, name, l); 88860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott else 88960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott skey = okey; 89060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 89160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott key = skey % dict->subdict->size; 892ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict->dict[key].valid != 0) { 893ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr tmp; 894ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 895ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; 896ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project tmp = tmp->next) { 897ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 89894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l)) { 89994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(tmp->name, name, l)) 900ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 901ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 902ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 90394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l) && 90494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(tmp->name, name, l))) 905ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 906ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 907ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbi++; 908ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 909ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 91094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l)) { 91194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(tmp->name, name, l)) 912ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 913ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 914ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 91594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l) && 91694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(tmp->name, name, l))) 917ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 918ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 919ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 920ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project key = okey % dict->size; 921ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 922ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 92394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun ret = xmlDictAddString(dict, name, l); 924ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (ret == NULL) 925ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 926ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (insert == NULL) { 927ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry = &(dict->dict[key]); 928ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } else { 929ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry = xmlMalloc(sizeof(xmlDictEntry)); 930ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (entry == NULL) 931ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 932ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 933ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry->name = ret; 93494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun entry->len = l; 935ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry->next = NULL; 936ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry->valid = 1; 93760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry->okey = okey; 938ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 939ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 94094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (insert != NULL) 941ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert->next = entry; 942ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 943ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->nbElems++; 944ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 945ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((nbi > MAX_HASH_LEN) && 94660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) { 94760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size) != 0) 94860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott return(NULL); 94960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott } 950ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* Note that entry may have been freed at this point by xmlDictGrow */ 951ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 952ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(ret); 953ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 954ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 955ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 956ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictExists: 957ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 958ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @name: the name of the userdata 959ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @len: the length of the name, if -1 it is recomputed 960ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 961ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Check if the @name exists in the dictionnary @dict. 962ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 963ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the internal copy of the name or NULL if not found. 964ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 965ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectconst xmlChar * 966ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictExists(xmlDictPtr dict, const xmlChar *name, int len) { 967ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project unsigned long key, okey, nbi = 0; 968ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr insert; 96994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun unsigned int l; 970ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 971ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((dict == NULL) || (name == NULL)) 972ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 973ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 974ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (len < 0) 97594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun l = strlen((const char *) name); 97694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun else 97794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun l = len; 97894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (((dict->limit > 0) && (l >= dict->limit)) || 97994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (l > INT_MAX / 2)) 98094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(NULL); 981ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 982ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* 983ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Check for duplicate and insertion location. 984ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 98594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun okey = xmlDictComputeKey(dict, name, l); 986ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project key = okey % dict->size; 987ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->dict[key].valid == 0) { 988ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert = NULL; 989ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } else { 990ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (insert = &(dict->dict[key]); insert->next != NULL; 991ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert = insert->next) { 992ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 99394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l)) { 99494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(insert->name, name, l)) 995ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 996ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 997ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 99894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l) && 99994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(insert->name, name, l))) 1000ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 1001ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 1002ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbi++; 1003ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1004ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 100594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l)) { 100694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(insert->name, name, l)) 1007ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 1008ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1009ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 101094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((insert->okey == okey) && (insert->len == l) && 101194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(insert->name, name, l))) 1012ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 1013ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 1014ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1015ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1016ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict) { 101760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott unsigned long skey; 101860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 101960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott /* we cannot always reuse the same okey for the subdict */ 102060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (((dict->size == MIN_DICT_SIZE) && 102160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott (dict->subdict->size != MIN_DICT_SIZE)) || 102260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott ((dict->size != MIN_DICT_SIZE) && 102360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott (dict->subdict->size == MIN_DICT_SIZE))) 102494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun skey = xmlDictComputeKey(dict->subdict, name, l); 102560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott else 102660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott skey = okey; 102760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 102860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott key = skey % dict->subdict->size; 1029ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict->dict[key].valid != 0) { 1030ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr tmp; 1031ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1032ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; 1033ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project tmp = tmp->next) { 1034ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 103594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l)) { 103694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(tmp->name, name, l)) 1037ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 1038ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1039ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 104094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l) && 104194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(tmp->name, name, l))) 1042ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 1043ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 1044ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbi++; 1045ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1046ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#ifdef __GNUC__ 104794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l)) { 104894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (!memcmp(tmp->name, name, l)) 1049ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 1050ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1051ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#else 105294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if ((tmp->okey == skey) && (tmp->len == l) && 105394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun (!xmlStrncmp(tmp->name, name, l))) 1054ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 1055ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#endif 1056ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1057ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1058ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1059ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* not found */ 1060ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 1061ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 1062ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1063ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 1064ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictQLookup: 1065ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 106660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott * @prefix: the prefix 1067ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @name: the name 1068ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 1069ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Add the QName @prefix:@name to the hash @dict if not present. 1070ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 1071ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the internal copy of the QName or NULL in case of internal error 1072ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 1073ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectconst xmlChar * 1074ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictQLookup(xmlDictPtr dict, const xmlChar *prefix, const xmlChar *name) { 1075ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project unsigned long okey, key, nbi = 0; 1076ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr entry; 1077ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr insert; 1078ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project const xmlChar *ret; 107994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun unsigned int len, plen, l; 1080ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1081ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((dict == NULL) || (name == NULL)) 1082ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 108360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (prefix == NULL) 108460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott return(xmlDictLookup(dict, name, -1)); 1085ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 108660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott l = len = strlen((const char *) name); 108760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott plen = strlen((const char *) prefix); 108860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott len += 1 + plen; 1089ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1090ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* 1091ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Check for duplicate and insertion location. 1092ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 109360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott okey = xmlDictComputeQKey(dict, prefix, plen, name, l); 1094ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project key = okey % dict->size; 1095ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->dict[key].valid == 0) { 1096ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert = NULL; 1097ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } else { 1098ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (insert = &(dict->dict[key]); insert->next != NULL; 1099ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert = insert->next) { 110060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if ((insert->okey == okey) && (insert->len == len) && 1101ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project (xmlStrQEqual(prefix, name, insert->name))) 1102ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 1103ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbi++; 1104ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 110560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if ((insert->okey == okey) && (insert->len == len) && 1106ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project (xmlStrQEqual(prefix, name, insert->name))) 1107ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(insert->name); 1108ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1109ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1110ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict) { 111160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott unsigned long skey; 111260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 111360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott /* we cannot always reuse the same okey for the subdict */ 111460a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if (((dict->size == MIN_DICT_SIZE) && 111560a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott (dict->subdict->size != MIN_DICT_SIZE)) || 111660a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott ((dict->size != MIN_DICT_SIZE) && 111760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott (dict->subdict->size == MIN_DICT_SIZE))) 111860a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott skey = xmlDictComputeQKey(dict->subdict, prefix, plen, name, l); 111960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott else 112060a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott skey = okey; 112160a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott 112260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott key = skey % dict->subdict->size; 1123ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict->dict[key].valid != 0) { 1124ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictEntryPtr tmp; 1125ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project for (tmp = &(dict->subdict->dict[key]); tmp->next != NULL; 1126ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project tmp = tmp->next) { 112760a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if ((tmp->okey == skey) && (tmp->len == len) && 1128ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project (xmlStrQEqual(prefix, name, tmp->name))) 1129ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 1130ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project nbi++; 1131ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 113260a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott if ((tmp->okey == skey) && (tmp->len == len) && 1133ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project (xmlStrQEqual(prefix, name, tmp->name))) 1134ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(tmp->name); 1135ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1136ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project key = okey % dict->size; 1137ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1138ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 113960a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott ret = xmlDictAddQString(dict, prefix, plen, name, l); 1140ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (ret == NULL) 1141ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 1142ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (insert == NULL) { 1143ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry = &(dict->dict[key]); 1144ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } else { 1145ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry = xmlMalloc(sizeof(xmlDictEntry)); 1146ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (entry == NULL) 1147ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(NULL); 1148ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1149ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry->name = ret; 1150ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry->len = len; 1151ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry->next = NULL; 1152ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project entry->valid = 1; 115360a4c356ee9ce5e9ccb23347c0381f0436192691Patrick Scott entry->okey = okey; 1154ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 115594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (insert != NULL) 1156ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project insert->next = entry; 1157ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1158ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project dict->nbElems++; 1159ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1160ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((nbi > MAX_HASH_LEN) && 1161ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project (dict->size <= ((MAX_DICT_HASH / 2) / MAX_HASH_LEN))) 1162ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictGrow(dict, MAX_HASH_LEN * 2 * dict->size); 1163ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project /* Note that entry may have been freed at this point by xmlDictGrow */ 1164ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1165ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(ret); 1166ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 1167ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1168ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 1169ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictOwns: 1170ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 1171ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @str: the string 1172ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 1173ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * check if a string is owned by the disctionary 1174ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 1175ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns 1 if true, 0 if false and -1 in case of error 1176ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * -1 in case of error 1177ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 1178ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectint 1179ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictOwns(xmlDictPtr dict, const xmlChar *str) { 1180ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project xmlDictStringsPtr pool; 1181ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1182ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((dict == NULL) || (str == NULL)) 1183ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 1184ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = dict->strings; 1185ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project while (pool != NULL) { 1186ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if ((str >= &pool->array[0]) && (str <= pool->free)) 1187ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(1); 1188ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project pool = pool->next; 1189ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project } 1190ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict) 1191ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(xmlDictOwns(dict->subdict, str)); 1192ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(0); 1193ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 1194ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1195ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project/** 1196ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * xmlDictSize: 1197ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * @dict: the dictionnary 1198ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 1199ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Query the number of elements installed in the hash @dict. 1200ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * 1201ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * Returns the number of elements in the dictionnary or 1202ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project * -1 in case of error 1203ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project */ 1204ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Projectint 1205ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source ProjectxmlDictSize(xmlDictPtr dict) { 1206ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict == NULL) 1207ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(-1); 1208ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project if (dict->subdict) 1209ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(dict->nbElems + dict->subdict->nbElems); 1210ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project return(dict->nbElems); 1211ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project} 1212ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 121394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun/** 121494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * xmlDictSetLimit: 121594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * @dict: the dictionnary 121694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * @limit: the limit in bytes 121794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * 121894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Set a size limit for the dictionary 121994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Added in 2.9.0 122094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * 122194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Returns the previous limit of the dictionary or 0 122294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun */ 122394442ad4107000e6d49f9b85a46a591495a57632Selim Gurunsize_t 122494442ad4107000e6d49f9b85a46a591495a57632Selim GurunxmlDictSetLimit(xmlDictPtr dict, size_t limit) { 122594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t ret; 122694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 122794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (dict == NULL) 122894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(0); 122994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun ret = dict->limit; 123094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun dict->limit = limit; 123194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(ret); 123294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun} 123394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 123494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun/** 123594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * xmlDictGetUsage: 123694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * @dict: the dictionnary 123794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * 123894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Get how much memory is used by a dictionary for strings 123994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Added in 2.9.0 124094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * 124194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun * Returns the amount of strings allocated 124294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun */ 124394442ad4107000e6d49f9b85a46a591495a57632Selim Gurunsize_t 124494442ad4107000e6d49f9b85a46a591495a57632Selim GurunxmlDictGetUsage(xmlDictPtr dict) { 124594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun xmlDictStringsPtr pool; 124694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun size_t limit = 0; 124794442ad4107000e6d49f9b85a46a591495a57632Selim Gurun 124894442ad4107000e6d49f9b85a46a591495a57632Selim Gurun if (dict == NULL) 124994442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(0); 125094442ad4107000e6d49f9b85a46a591495a57632Selim Gurun pool = dict->strings; 125194442ad4107000e6d49f9b85a46a591495a57632Selim Gurun while (pool != NULL) { 125294442ad4107000e6d49f9b85a46a591495a57632Selim Gurun limit += pool->size; 125394442ad4107000e6d49f9b85a46a591495a57632Selim Gurun pool = pool->next; 125494442ad4107000e6d49f9b85a46a591495a57632Selim Gurun } 125594442ad4107000e6d49f9b85a46a591495a57632Selim Gurun return(limit); 125694442ad4107000e6d49f9b85a46a591495a57632Selim Gurun} 1257ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project 1258ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#define bottom_dict 1259ab4e2e90f63db6b1cd8bb2e453cac899ef43d42bThe Android Open Source Project#include "elfgcchack.h" 1260