1 /* 2 ** 2001 September 22 3 ** 4 ** The author disclaims copyright to this source code. In place of 5 ** a legal notice, here is a blessing: 6 ** 7 ** May you do good and not evil. 8 ** May you find forgiveness for yourself and forgive others. 9 ** May you share freely, never taking more than you give. 10 ** 11 ************************************************************************* 12 ** This is the implementation of generic hash-tables 13 ** used in SQLite. 14 ** 15 ** $Id: hash.c,v 1.36 2009/04/28 17:33:16 drh Exp $ 16 */ 17 #include "sqliteInt.h" 18 #include <assert.h> 19 20 /* Turn bulk memory into a hash table object by initializing the 21 ** fields of the Hash structure. 22 ** 23 ** "pNew" is a pointer to the hash table that is to be initialized. 24 ** "copyKey" is true if the hash table should make its own private 25 ** copy of keys and false if it should just use the supplied pointer. 26 */ 27 void sqlite3HashInit(Hash *pNew, int copyKey){ 28 assert( pNew!=0 ); 29 pNew->copyKey = copyKey!=0; 30 pNew->first = 0; 31 pNew->count = 0; 32 pNew->htsize = 0; 33 pNew->ht = 0; 34 } 35 36 /* Remove all entries from a hash table. Reclaim all memory. 37 ** Call this routine to delete a hash table or to reset a hash table 38 ** to the empty state. 39 */ 40 void sqlite3HashClear(Hash *pH){ 41 HashElem *elem; /* For looping over all elements of the table */ 42 43 assert( pH!=0 ); 44 elem = pH->first; 45 pH->first = 0; 46 sqlite3_free(pH->ht); 47 pH->ht = 0; 48 pH->htsize = 0; 49 while( elem ){ 50 HashElem *next_elem = elem->next; 51 if( pH->copyKey ){ 52 sqlite3_free(elem->pKey); 53 } 54 sqlite3_free(elem); 55 elem = next_elem; 56 } 57 pH->count = 0; 58 } 59 60 /* 61 ** Hash and comparison functions when the mode is SQLITE_HASH_STRING 62 */ 63 static unsigned int strHash(const void *pKey, int nKey){ 64 const char *z = (const char *)pKey; 65 int h = 0; 66 assert( nKey>=0 ); 67 while( nKey > 0 ){ 68 h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++]; 69 nKey--; 70 } 71 return h; 72 } 73 static int strCompare(const void *pKey1, int n1, const void *pKey2, int n2){ 74 if( n1!=n2 ) return 1; 75 return sqlite3StrNICmp((const char*)pKey1,(const char*)pKey2,n1); 76 } 77 78 79 /* Link pNew element into the hash table pH. If pEntry!=0 then also 80 ** insert pNew into the pEntry hash bucket. 81 */ 82 static void insertElement( 83 Hash *pH, /* The complete hash table */ 84 struct _ht *pEntry, /* The entry into which pNew is inserted */ 85 HashElem *pNew /* The element to be inserted */ 86 ){ 87 HashElem *pHead; /* First element already in pEntry */ 88 if( pEntry ){ 89 pHead = pEntry->count ? pEntry->chain : 0; 90 pEntry->count++; 91 pEntry->chain = pNew; 92 }else{ 93 pHead = 0; 94 } 95 if( pHead ){ 96 pNew->next = pHead; 97 pNew->prev = pHead->prev; 98 if( pHead->prev ){ pHead->prev->next = pNew; } 99 else { pH->first = pNew; } 100 pHead->prev = pNew; 101 }else{ 102 pNew->next = pH->first; 103 if( pH->first ){ pH->first->prev = pNew; } 104 pNew->prev = 0; 105 pH->first = pNew; 106 } 107 } 108 109 110 /* Resize the hash table so that it cantains "new_size" buckets. 111 ** 112 ** The hash table might fail to resize if sqlite3_malloc() fails or 113 ** if the new size is the same as the prior size. 114 ** Return TRUE if the resize occurs and false if not. 115 */ 116 static int rehash(Hash *pH, unsigned int new_size){ 117 struct _ht *new_ht; /* The new hash table */ 118 HashElem *elem, *next_elem; /* For looping over existing elements */ 119 120 #if SQLITE_MALLOC_SOFT_LIMIT>0 121 if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){ 122 new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht); 123 } 124 if( new_size==pH->htsize ) return 0; 125 #endif 126 127 /* The inability to allocates space for a larger hash table is 128 ** a performance hit but it is not a fatal error. So mark the 129 ** allocation as a benign. 130 */ 131 sqlite3BeginBenignMalloc(); 132 new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) ); 133 sqlite3EndBenignMalloc(); 134 135 if( new_ht==0 ) return 0; 136 sqlite3_free(pH->ht); 137 pH->ht = new_ht; 138 pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht); 139 memset(new_ht, 0, new_size*sizeof(struct _ht)); 140 for(elem=pH->first, pH->first=0; elem; elem = next_elem){ 141 unsigned int h = strHash(elem->pKey, elem->nKey) % new_size; 142 next_elem = elem->next; 143 insertElement(pH, &new_ht[h], elem); 144 } 145 return 1; 146 } 147 148 /* This function (for internal use only) locates an element in an 149 ** hash table that matches the given key. The hash for this key has 150 ** already been computed and is passed as the 4th parameter. 151 */ 152 static HashElem *findElementGivenHash( 153 const Hash *pH, /* The pH to be searched */ 154 const void *pKey, /* The key we are searching for */ 155 int nKey, /* Bytes in key (not counting zero terminator) */ 156 unsigned int h /* The hash for this key. */ 157 ){ 158 HashElem *elem; /* Used to loop thru the element list */ 159 int count; /* Number of elements left to test */ 160 161 if( pH->ht ){ 162 struct _ht *pEntry = &pH->ht[h]; 163 elem = pEntry->chain; 164 count = pEntry->count; 165 }else{ 166 elem = pH->first; 167 count = pH->count; 168 } 169 while( count-- && ALWAYS(elem) ){ 170 if( strCompare(elem->pKey,elem->nKey,pKey,nKey)==0 ){ 171 return elem; 172 } 173 elem = elem->next; 174 } 175 return 0; 176 } 177 178 /* Remove a single entry from the hash table given a pointer to that 179 ** element and a hash on the element's key. 180 */ 181 static void removeElementGivenHash( 182 Hash *pH, /* The pH containing "elem" */ 183 HashElem* elem, /* The element to be removed from the pH */ 184 unsigned int h /* Hash value for the element */ 185 ){ 186 struct _ht *pEntry; 187 if( elem->prev ){ 188 elem->prev->next = elem->next; 189 }else{ 190 pH->first = elem->next; 191 } 192 if( elem->next ){ 193 elem->next->prev = elem->prev; 194 } 195 if( pH->ht ){ 196 pEntry = &pH->ht[h]; 197 if( pEntry->chain==elem ){ 198 pEntry->chain = elem->next; 199 } 200 pEntry->count--; 201 assert( pEntry->count>=0 ); 202 } 203 if( pH->copyKey ){ 204 sqlite3_free(elem->pKey); 205 } 206 sqlite3_free( elem ); 207 pH->count--; 208 if( pH->count<=0 ){ 209 assert( pH->first==0 ); 210 assert( pH->count==0 ); 211 sqlite3HashClear(pH); 212 } 213 } 214 215 /* Attempt to locate an element of the hash table pH with a key 216 ** that matches pKey,nKey. Return the data for this element if it is 217 ** found, or NULL if there is no match. 218 */ 219 void *sqlite3HashFind(const Hash *pH, const void *pKey, int nKey){ 220 HashElem *elem; /* The element that matches key */ 221 unsigned int h; /* A hash on key */ 222 223 assert( pH!=0 ); 224 assert( pKey!=0 ); 225 assert( nKey>=0 ); 226 if( pH->ht ){ 227 h = strHash(pKey, nKey) % pH->htsize; 228 }else{ 229 h = 0; 230 } 231 elem = findElementGivenHash(pH, pKey, nKey, h); 232 return elem ? elem->data : 0; 233 } 234 235 /* Insert an element into the hash table pH. The key is pKey,nKey 236 ** and the data is "data". 237 ** 238 ** If no element exists with a matching key, then a new 239 ** element is created. A copy of the key is made if the copyKey 240 ** flag is set. NULL is returned. 241 ** 242 ** If another element already exists with the same key, then the 243 ** new data replaces the old data and the old data is returned. 244 ** The key is not copied in this instance. If a malloc fails, then 245 ** the new data is returned and the hash table is unchanged. 246 ** 247 ** If the "data" parameter to this function is NULL, then the 248 ** element corresponding to "key" is removed from the hash table. 249 */ 250 void *sqlite3HashInsert(Hash *pH, const void *pKey, int nKey, void *data){ 251 unsigned int h; /* the hash of the key modulo hash table size */ 252 HashElem *elem; /* Used to loop thru the element list */ 253 HashElem *new_elem; /* New element added to the pH */ 254 255 assert( pH!=0 ); 256 assert( pKey!=0 ); 257 assert( nKey>=0 ); 258 if( pH->htsize ){ 259 h = strHash(pKey, nKey) % pH->htsize; 260 }else{ 261 h = 0; 262 } 263 elem = findElementGivenHash(pH,pKey,nKey,h); 264 if( elem ){ 265 void *old_data = elem->data; 266 if( data==0 ){ 267 removeElementGivenHash(pH,elem,h); 268 }else{ 269 elem->data = data; 270 if( !pH->copyKey ){ 271 elem->pKey = (void *)pKey; 272 } 273 assert(nKey==elem->nKey); 274 } 275 return old_data; 276 } 277 if( data==0 ) return 0; 278 new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) ); 279 if( new_elem==0 ) return data; 280 if( pH->copyKey ){ 281 new_elem->pKey = sqlite3Malloc( nKey ); 282 if( new_elem->pKey==0 ){ 283 sqlite3_free(new_elem); 284 return data; 285 } 286 memcpy((void*)new_elem->pKey, pKey, nKey); 287 }else{ 288 new_elem->pKey = (void*)pKey; 289 } 290 new_elem->nKey = nKey; 291 new_elem->data = data; 292 pH->count++; 293 if( pH->count>=10 && pH->count > 2*pH->htsize ){ 294 if( rehash(pH, pH->count*2) && pH->htsize ){ 295 h = strHash(pKey, nKey) % pH->htsize; 296 } 297 } 298 if( pH->ht ){ 299 insertElement(pH, &pH->ht[h], new_elem); 300 }else{ 301 insertElement(pH, 0, new_elem); 302 } 303 return 0; 304 } 305