hash.c revision 5821806d5e7f356e8fa4b058a389a808ea183019
15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2001 September 22 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The author disclaims copyright to this source code. In place of 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** a legal notice, here is a blessing: 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you do good and not evil. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you find forgiveness for yourself and forgive others. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you share freely, never taking more than you give. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)************************************************************************* 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This is the implementation of generic hash-tables 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** used in SQLite. 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sqliteInt.h" 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <assert.h> 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Turn bulk memory into a hash table object by initializing the 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** fields of the Hash structure. 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** "pNew" is a pointer to the hash table that is to be initialized. 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void sqlite3HashInit(Hash *pNew){ 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pNew!=0 ); 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->first = 0; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->count = 0; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->htsize = 0; 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->ht = 0; 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Remove all entries from a hash table. Reclaim all memory. 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Call this routine to delete a hash table or to reset a hash table 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** to the empty state. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void sqlite3HashClear(Hash *pH){ 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *elem; /* For looping over all elements of the table */ 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pH!=0 ); 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem = pH->first; 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->first = 0; 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_free(pH->ht); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->ht = 0; 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->htsize = 0; 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( elem ){ 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *next_elem = elem->next; 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_free(elem); 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem = next_elem; 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->count = 0; 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The hashing function. 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static unsigned int strHash(const char *z, int nKey){ 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int h = 0; 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( nKey>=0 ); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( nKey > 0 ){ 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++]; 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) nKey--; 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return h; 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Link pNew element into the hash table pH. If pEntry!=0 then also 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** insert pNew into the pEntry hash bucket. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void insertElement( 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Hash *pH, /* The complete hash table */ 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct _ht *pEntry, /* The entry into which pNew is inserted */ 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *pNew /* The element to be inserted */ 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)){ 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *pHead; /* First element already in pEntry */ 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pEntry ){ 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pHead = pEntry->count ? pEntry->chain : 0; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry->count++; 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry->chain = pNew; 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pHead = 0; 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pHead ){ 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->next = pHead; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->prev = pHead->prev; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pHead->prev ){ pHead->prev->next = pNew; } 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) else { pH->first = pNew; } 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pHead->prev = pNew; 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->next = pH->first; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->first ){ pH->first->prev = pNew; } 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->prev = 0; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->first = pNew; 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Resize the hash table so that it cantains "new_size" buckets. 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The hash table might fail to resize if sqlite3_malloc() fails or 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** if the new size is the same as the prior size. 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return TRUE if the resize occurs and false if not. 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static int rehash(Hash *pH, unsigned int new_size){ 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct _ht *new_ht; /* The new hash table */ 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *elem, *next_elem; /* For looping over existing elements */ 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#if SQLITE_MALLOC_SOFT_LIMIT>0 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){ 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( new_size==pH->htsize ) return 0; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#endif 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) /* The inability to allocates space for a larger hash table is 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** a performance hit but it is not a fatal error. So mark the 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ** allocation as a benign. 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) */ 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3BeginBenignMalloc(); 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) ); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3EndBenignMalloc(); 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( new_ht==0 ) return 0; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_free(pH->ht); 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->ht = new_ht; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(new_ht, 0, new_size*sizeof(struct _ht)); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(elem=pH->first, pH->first=0; elem; elem = next_elem){ 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int h = strHash(elem->pKey, elem->nKey) % new_size; 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_elem = elem->next; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insertElement(pH, &new_ht[h], elem); 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* This function (for internal use only) locates an element in an 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** hash table that matches the given key. The hash for this key has 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** already been computed and is passed as the 4th parameter. 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static HashElem *findElementGivenHash( 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const Hash *pH, /* The pH to be searched */ 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const char *pKey, /* The key we are searching for */ 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int nKey, /* Bytes in key (not counting zero terminator) */ 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int h /* The hash for this key. */ 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)){ 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *elem; /* Used to loop thru the element list */ 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int count; /* Number of elements left to test */ 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->ht ){ 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct _ht *pEntry = &pH->ht[h]; 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem = pEntry->chain; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count = pEntry->count; 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem = pH->first; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count = pH->count; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( count-- && ALWAYS(elem) ){ 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( elem->nKey==nKey && sqlite3StrNICmp(elem->pKey,pKey,nKey)==0 ){ 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return elem; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem = elem->next; 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Remove a single entry from the hash table given a pointer to that 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** element and a hash on the element's key. 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void removeElementGivenHash( 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Hash *pH, /* The pH containing "elem" */ 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem* elem, /* The element to be removed from the pH */ 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int h /* Hash value for the element */ 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)){ 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct _ht *pEntry; 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( elem->prev ){ 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem->prev->next = elem->next; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->first = elem->next; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( elem->next ){ 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem->next->prev = elem->prev; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->ht ){ 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry = &pH->ht[h]; 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pEntry->chain==elem ){ 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry->chain = elem->next; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry->count--; 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pEntry->count>=0 ); 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3_free( elem ); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->count--; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->count<=0 ){ 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pH->first==0 ); 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pH->count==0 ); 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3HashClear(pH); 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Attempt to locate an element of the hash table pH with a key 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** that matches pKey,nKey. Return the data for this element if it is 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** found, or NULL if there is no match. 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void *sqlite3HashFind(const Hash *pH, const char *pKey, int nKey){ 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *elem; /* The element that matches key */ 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int h; /* A hash on key */ 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pH!=0 ); 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pKey!=0 ); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( nKey>=0 ); 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->ht ){ 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = strHash(pKey, nKey) % pH->htsize; 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = 0; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem = findElementGivenHash(pH, pKey, nKey, h); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return elem ? elem->data : 0; 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* Insert an element into the hash table pH. The key is pKey,nKey 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** and the data is "data". 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If no element exists with a matching key, then a new 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** element is created and NULL is returned. 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If another element already exists with the same key, then the 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** new data replaces the old data and the old data is returned. 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The key is not copied in this instance. If a malloc fails, then 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** the new data is returned and the hash table is unchanged. 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If the "data" parameter to this function is NULL, then the 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** element corresponding to "key" is removed from the hash table. 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void *sqlite3HashInsert(Hash *pH, const char *pKey, int nKey, void *data){ 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int h; /* the hash of the key modulo hash table size */ 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *elem; /* Used to loop thru the element list */ 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) HashElem *new_elem; /* New element added to the pH */ 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pH!=0 ); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pKey!=0 ); 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( nKey>=0 ); 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->htsize ){ 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = strHash(pKey, nKey) % pH->htsize; 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = 0; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem = findElementGivenHash(pH,pKey,nKey,h); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( elem ){ 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) void *old_data = elem->data; 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( data==0 ){ 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) removeElementGivenHash(pH,elem,h); 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem->data = data; 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) elem->pKey = pKey; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert(nKey==elem->nKey); 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return old_data; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( data==0 ) return 0; 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) ); 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( new_elem==0 ) return data; 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_elem->pKey = pKey; 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_elem->nKey = nKey; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) new_elem->data = data; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pH->count++; 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->count>=10 && pH->count > 2*pH->htsize ){ 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( rehash(pH, pH->count*2) ){ 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pH->htsize>0 ); 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) h = strHash(pKey, nKey) % pH->htsize; 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pH->ht ){ 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insertElement(pH, &pH->ht[h], new_elem); 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) insertElement(pH, 0, new_elem); 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 278