1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/sql/SQLite364/hash.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,303 @@
1.4 +/*
1.5 +** 2001 September 22
1.6 +**
1.7 +** The author disclaims copyright to this source code. In place of
1.8 +** a legal notice, here is a blessing:
1.9 +**
1.10 +** May you do good and not evil.
1.11 +** May you find forgiveness for yourself and forgive others.
1.12 +** May you share freely, never taking more than you give.
1.13 +**
1.14 +*************************************************************************
1.15 +** This is the implementation of generic hash-tables
1.16 +** used in SQLite.
1.17 +**
1.18 +** $Id: hash.c,v 1.31 2008/10/10 17:41:29 drh Exp $
1.19 +*/
1.20 +#include "sqliteInt.h"
1.21 +#include <assert.h>
1.22 +
1.23 +/* Turn bulk memory into a hash table object by initializing the
1.24 +** fields of the Hash structure.
1.25 +**
1.26 +** "pNew" is a pointer to the hash table that is to be initialized.
1.27 +** "copyKey" is true if the hash table should make its own private
1.28 +** copy of keys and false if it should just use the supplied pointer.
1.29 +*/
1.30 +void sqlite3HashInit(Hash *pNew, int copyKey){
1.31 + assert( pNew!=0 );
1.32 + pNew->copyKey = copyKey!=0;
1.33 + pNew->first = 0;
1.34 + pNew->count = 0;
1.35 + pNew->htsize = 0;
1.36 + pNew->ht = 0;
1.37 +}
1.38 +
1.39 +/* Remove all entries from a hash table. Reclaim all memory.
1.40 +** Call this routine to delete a hash table or to reset a hash table
1.41 +** to the empty state.
1.42 +*/
1.43 +void sqlite3HashClear(Hash *pH){
1.44 + HashElem *elem; /* For looping over all elements of the table */
1.45 +
1.46 + assert( pH!=0 );
1.47 + elem = pH->first;
1.48 + pH->first = 0;
1.49 + sqlite3_free(pH->ht);
1.50 + pH->ht = 0;
1.51 + pH->htsize = 0;
1.52 + while( elem ){
1.53 + HashElem *next_elem = elem->next;
1.54 + if( pH->copyKey && elem->pKey ){
1.55 + sqlite3_free(elem->pKey);
1.56 + }
1.57 + sqlite3_free(elem);
1.58 + elem = next_elem;
1.59 + }
1.60 + pH->count = 0;
1.61 +}
1.62 +
1.63 +/*
1.64 +** Hash and comparison functions when the mode is SQLITE_HASH_STRING
1.65 +*/
1.66 +static int strHash(const void *pKey, int nKey){
1.67 + const char *z = (const char *)pKey;
1.68 + int h = 0;
1.69 + if( nKey<=0 ) nKey = strlen(z);
1.70 + while( nKey > 0 ){
1.71 + h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
1.72 + nKey--;
1.73 + }
1.74 + return h & 0x7fffffff;
1.75 +}
1.76 +static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){
1.77 + if( n1!=n2 ) return 1;
1.78 + return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1);
1.79 +}
1.80 +
1.81 +
1.82 +/* Link an element into the hash table
1.83 +*/
1.84 +static void insertElement(
1.85 + Hash *pH, /* The complete hash table */
1.86 + struct _ht *pEntry, /* The entry into which pNew is inserted */
1.87 + HashElem *pNew /* The element to be inserted */
1.88 +){
1.89 + HashElem *pHead; /* First element already in pEntry */
1.90 + pHead = pEntry->chain;
1.91 + if( pHead ){
1.92 + pNew->next = pHead;
1.93 + pNew->prev = pHead->prev;
1.94 + if( pHead->prev ){ pHead->prev->next = pNew; }
1.95 + else { pH->first = pNew; }
1.96 + pHead->prev = pNew;
1.97 + }else{
1.98 + pNew->next = pH->first;
1.99 + if( pH->first ){ pH->first->prev = pNew; }
1.100 + pNew->prev = 0;
1.101 + pH->first = pNew;
1.102 + }
1.103 + pEntry->count++;
1.104 + pEntry->chain = pNew;
1.105 +}
1.106 +
1.107 +
1.108 +/* Resize the hash table so that it cantains "new_size" buckets.
1.109 +** "new_size" must be a power of 2. The hash table might fail
1.110 +** to resize if sqlite3_malloc() fails.
1.111 +*/
1.112 +static void rehash(Hash *pH, int new_size){
1.113 + struct _ht *new_ht; /* The new hash table */
1.114 + HashElem *elem, *next_elem; /* For looping over existing elements */
1.115 +
1.116 +#ifdef SQLITE_MALLOC_SOFT_LIMIT
1.117 + if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){
1.118 + new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht);
1.119 + }
1.120 + if( new_size==pH->htsize ) return;
1.121 +#endif
1.122 +
1.123 + /* There is a call to sqlite3_malloc() inside rehash(). If there is
1.124 + ** already an allocation at pH->ht, then if this malloc() fails it
1.125 + ** is benign (since failing to resize a hash table is a performance
1.126 + ** hit only, not a fatal error).
1.127 + */
1.128 + if( pH->htsize>0 ) sqlite3BeginBenignMalloc();
1.129 + new_ht = (struct _ht *)sqlite3MallocZero( new_size*sizeof(struct _ht) );
1.130 + if( pH->htsize>0 ) sqlite3EndBenignMalloc();
1.131 +
1.132 + if( new_ht==0 ) return;
1.133 + sqlite3_free(pH->ht);
1.134 + pH->ht = new_ht;
1.135 + pH->htsize = new_size;
1.136 + for(elem=pH->first, pH->first=0; elem; elem = next_elem){
1.137 + int h = strHash(elem->pKey, elem->nKey) & (new_size-1);
1.138 + next_elem = elem->next;
1.139 + insertElement(pH, &new_ht[h], elem);
1.140 + }
1.141 +}
1.142 +
1.143 +/* This function (for internal use only) locates an element in an
1.144 +** hash table that matches the given key. The hash for this key has
1.145 +** already been computed and is passed as the 4th parameter.
1.146 +*/
1.147 +static HashElem *findElementGivenHash(
1.148 + const Hash *pH, /* The pH to be searched */
1.149 + const void *pKey, /* The key we are searching for */
1.150 + int nKey,
1.151 + int h /* The hash for this key. */
1.152 +){
1.153 + HashElem *elem; /* Used to loop thru the element list */
1.154 + int count; /* Number of elements left to test */
1.155 +
1.156 + if( pH->ht ){
1.157 + struct _ht *pEntry = &pH->ht[h];
1.158 + elem = pEntry->chain;
1.159 + count = pEntry->count;
1.160 + while( count-- && elem ){
1.161 + if( strCompare(elem->pKey,elem->nKey,pKey,nKey)==0 ){
1.162 + return elem;
1.163 + }
1.164 + elem = elem->next;
1.165 + }
1.166 + }
1.167 + return 0;
1.168 +}
1.169 +
1.170 +/* Remove a single entry from the hash table given a pointer to that
1.171 +** element and a hash on the element's key.
1.172 +*/
1.173 +static void removeElementGivenHash(
1.174 + Hash *pH, /* The pH containing "elem" */
1.175 + HashElem* elem, /* The element to be removed from the pH */
1.176 + int h /* Hash value for the element */
1.177 +){
1.178 + struct _ht *pEntry;
1.179 + if( elem->prev ){
1.180 + elem->prev->next = elem->next;
1.181 + }else{
1.182 + pH->first = elem->next;
1.183 + }
1.184 + if( elem->next ){
1.185 + elem->next->prev = elem->prev;
1.186 + }
1.187 + pEntry = &pH->ht[h];
1.188 + if( pEntry->chain==elem ){
1.189 + pEntry->chain = elem->next;
1.190 + }
1.191 + pEntry->count--;
1.192 + if( pEntry->count<=0 ){
1.193 + pEntry->chain = 0;
1.194 + }
1.195 + if( pH->copyKey ){
1.196 + sqlite3_free(elem->pKey);
1.197 + }
1.198 + sqlite3_free( elem );
1.199 + pH->count--;
1.200 + if( pH->count<=0 ){
1.201 + assert( pH->first==0 );
1.202 + assert( pH->count==0 );
1.203 + sqlite3HashClear(pH);
1.204 + }
1.205 +}
1.206 +
1.207 +/* Attempt to locate an element of the hash table pH with a key
1.208 +** that matches pKey,nKey. Return a pointer to the corresponding
1.209 +** HashElem structure for this element if it is found, or NULL
1.210 +** otherwise.
1.211 +*/
1.212 +HashElem *sqlite3HashFindElem(const Hash *pH, const void *pKey, int nKey){
1.213 + int h; /* A hash on key */
1.214 + HashElem *elem; /* The element that matches key */
1.215 +
1.216 + if( pH==0 || pH->ht==0 ) return 0;
1.217 + h = strHash(pKey,nKey);
1.218 + elem = findElementGivenHash(pH,pKey,nKey, h % pH->htsize);
1.219 + return elem;
1.220 +}
1.221 +
1.222 +/* Attempt to locate an element of the hash table pH with a key
1.223 +** that matches pKey,nKey. Return the data for this element if it is
1.224 +** found, or NULL if there is no match.
1.225 +*/
1.226 +void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){
1.227 + HashElem *elem; /* The element that matches key */
1.228 + elem = sqlite3HashFindElem(pH, pKey, nKey);
1.229 + return elem ? elem->data : 0;
1.230 +}
1.231 +
1.232 +/* Insert an element into the hash table pH. The key is pKey,nKey
1.233 +** and the data is "data".
1.234 +**
1.235 +** If no element exists with a matching key, then a new
1.236 +** element is created. A copy of the key is made if the copyKey
1.237 +** flag is set. NULL is returned.
1.238 +**
1.239 +** If another element already exists with the same key, then the
1.240 +** new data replaces the old data and the old data is returned.
1.241 +** The key is not copied in this instance. If a malloc fails, then
1.242 +** the new data is returned and the hash table is unchanged.
1.243 +**
1.244 +** If the "data" parameter to this function is NULL, then the
1.245 +** element corresponding to "key" is removed from the hash table.
1.246 +*/
1.247 +void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){
1.248 + int hraw; /* Raw hash value of the key */
1.249 + int h; /* the hash of the key modulo hash table size */
1.250 + HashElem *elem; /* Used to loop thru the element list */
1.251 + HashElem *new_elem; /* New element added to the pH */
1.252 +
1.253 + assert( pH!=0 );
1.254 + hraw = strHash(pKey, nKey);
1.255 + if( pH->htsize ){
1.256 + h = hraw % pH->htsize;
1.257 + elem = findElementGivenHash(pH,pKey,nKey,h);
1.258 + if( elem ){
1.259 + void *old_data = elem->data;
1.260 + if( data==0 ){
1.261 + removeElementGivenHash(pH,elem,h);
1.262 + }else{
1.263 + elem->data = data;
1.264 + if( !pH->copyKey ){
1.265 + elem->pKey = (void *)pKey;
1.266 + }
1.267 + assert(nKey==elem->nKey);
1.268 + }
1.269 + return old_data;
1.270 + }
1.271 + }
1.272 + if( data==0 ) return 0;
1.273 + new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
1.274 + if( new_elem==0 ) return data;
1.275 + if( pH->copyKey && pKey!=0 ){
1.276 + new_elem->pKey = sqlite3Malloc( nKey );
1.277 + if( new_elem->pKey==0 ){
1.278 + sqlite3_free(new_elem);
1.279 + return data;
1.280 + }
1.281 + memcpy((void*)new_elem->pKey, pKey, nKey);
1.282 + }else{
1.283 + new_elem->pKey = (void*)pKey;
1.284 + }
1.285 + new_elem->nKey = nKey;
1.286 + pH->count++;
1.287 + if( pH->htsize==0 ){
1.288 + rehash(pH, 128/sizeof(pH->ht[0]));
1.289 + if( pH->htsize==0 ){
1.290 + pH->count = 0;
1.291 + if( pH->copyKey ){
1.292 + sqlite3_free(new_elem->pKey);
1.293 + }
1.294 + sqlite3_free(new_elem);
1.295 + return data;
1.296 + }
1.297 + }
1.298 + if( pH->count > pH->htsize ){
1.299 + rehash(pH,pH->htsize*2);
1.300 + }
1.301 + assert( pH->htsize>0 );
1.302 + h = hraw % pH->htsize;
1.303 + insertElement(pH, &pH->ht[h], new_elem);
1.304 + new_elem->data = data;
1.305 + return 0;
1.306 +}