Annotation of embedaddon/sqlite3/src/hash.c, revision 1.1
1.1 ! misho 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: #include "sqliteInt.h"
! 16: #include <assert.h>
! 17:
! 18: /* Turn bulk memory into a hash table object by initializing the
! 19: ** fields of the Hash structure.
! 20: **
! 21: ** "pNew" is a pointer to the hash table that is to be initialized.
! 22: */
! 23: void sqlite3HashInit(Hash *pNew){
! 24: assert( pNew!=0 );
! 25: pNew->first = 0;
! 26: pNew->count = 0;
! 27: pNew->htsize = 0;
! 28: pNew->ht = 0;
! 29: }
! 30:
! 31: /* Remove all entries from a hash table. Reclaim all memory.
! 32: ** Call this routine to delete a hash table or to reset a hash table
! 33: ** to the empty state.
! 34: */
! 35: void sqlite3HashClear(Hash *pH){
! 36: HashElem *elem; /* For looping over all elements of the table */
! 37:
! 38: assert( pH!=0 );
! 39: elem = pH->first;
! 40: pH->first = 0;
! 41: sqlite3_free(pH->ht);
! 42: pH->ht = 0;
! 43: pH->htsize = 0;
! 44: while( elem ){
! 45: HashElem *next_elem = elem->next;
! 46: sqlite3_free(elem);
! 47: elem = next_elem;
! 48: }
! 49: pH->count = 0;
! 50: }
! 51:
! 52: /*
! 53: ** The hashing function.
! 54: */
! 55: static unsigned int strHash(const char *z, int nKey){
! 56: int h = 0;
! 57: assert( nKey>=0 );
! 58: while( nKey > 0 ){
! 59: h = (h<<3) ^ h ^ sqlite3UpperToLower[(unsigned char)*z++];
! 60: nKey--;
! 61: }
! 62: return h;
! 63: }
! 64:
! 65:
! 66: /* Link pNew element into the hash table pH. If pEntry!=0 then also
! 67: ** insert pNew into the pEntry hash bucket.
! 68: */
! 69: static void insertElement(
! 70: Hash *pH, /* The complete hash table */
! 71: struct _ht *pEntry, /* The entry into which pNew is inserted */
! 72: HashElem *pNew /* The element to be inserted */
! 73: ){
! 74: HashElem *pHead; /* First element already in pEntry */
! 75: if( pEntry ){
! 76: pHead = pEntry->count ? pEntry->chain : 0;
! 77: pEntry->count++;
! 78: pEntry->chain = pNew;
! 79: }else{
! 80: pHead = 0;
! 81: }
! 82: if( pHead ){
! 83: pNew->next = pHead;
! 84: pNew->prev = pHead->prev;
! 85: if( pHead->prev ){ pHead->prev->next = pNew; }
! 86: else { pH->first = pNew; }
! 87: pHead->prev = pNew;
! 88: }else{
! 89: pNew->next = pH->first;
! 90: if( pH->first ){ pH->first->prev = pNew; }
! 91: pNew->prev = 0;
! 92: pH->first = pNew;
! 93: }
! 94: }
! 95:
! 96:
! 97: /* Resize the hash table so that it cantains "new_size" buckets.
! 98: **
! 99: ** The hash table might fail to resize if sqlite3_malloc() fails or
! 100: ** if the new size is the same as the prior size.
! 101: ** Return TRUE if the resize occurs and false if not.
! 102: */
! 103: static int rehash(Hash *pH, unsigned int new_size){
! 104: struct _ht *new_ht; /* The new hash table */
! 105: HashElem *elem, *next_elem; /* For looping over existing elements */
! 106:
! 107: #if SQLITE_MALLOC_SOFT_LIMIT>0
! 108: if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){
! 109: new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht);
! 110: }
! 111: if( new_size==pH->htsize ) return 0;
! 112: #endif
! 113:
! 114: /* The inability to allocates space for a larger hash table is
! 115: ** a performance hit but it is not a fatal error. So mark the
! 116: ** allocation as a benign.
! 117: */
! 118: sqlite3BeginBenignMalloc();
! 119: new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) );
! 120: sqlite3EndBenignMalloc();
! 121:
! 122: if( new_ht==0 ) return 0;
! 123: sqlite3_free(pH->ht);
! 124: pH->ht = new_ht;
! 125: pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht);
! 126: memset(new_ht, 0, new_size*sizeof(struct _ht));
! 127: for(elem=pH->first, pH->first=0; elem; elem = next_elem){
! 128: unsigned int h = strHash(elem->pKey, elem->nKey) % new_size;
! 129: next_elem = elem->next;
! 130: insertElement(pH, &new_ht[h], elem);
! 131: }
! 132: return 1;
! 133: }
! 134:
! 135: /* This function (for internal use only) locates an element in an
! 136: ** hash table that matches the given key. The hash for this key has
! 137: ** already been computed and is passed as the 4th parameter.
! 138: */
! 139: static HashElem *findElementGivenHash(
! 140: const Hash *pH, /* The pH to be searched */
! 141: const char *pKey, /* The key we are searching for */
! 142: int nKey, /* Bytes in key (not counting zero terminator) */
! 143: unsigned int h /* The hash for this key. */
! 144: ){
! 145: HashElem *elem; /* Used to loop thru the element list */
! 146: int count; /* Number of elements left to test */
! 147:
! 148: if( pH->ht ){
! 149: struct _ht *pEntry = &pH->ht[h];
! 150: elem = pEntry->chain;
! 151: count = pEntry->count;
! 152: }else{
! 153: elem = pH->first;
! 154: count = pH->count;
! 155: }
! 156: while( count-- && ALWAYS(elem) ){
! 157: if( elem->nKey==nKey && sqlite3StrNICmp(elem->pKey,pKey,nKey)==0 ){
! 158: return elem;
! 159: }
! 160: elem = elem->next;
! 161: }
! 162: return 0;
! 163: }
! 164:
! 165: /* Remove a single entry from the hash table given a pointer to that
! 166: ** element and a hash on the element's key.
! 167: */
! 168: static void removeElementGivenHash(
! 169: Hash *pH, /* The pH containing "elem" */
! 170: HashElem* elem, /* The element to be removed from the pH */
! 171: unsigned int h /* Hash value for the element */
! 172: ){
! 173: struct _ht *pEntry;
! 174: if( elem->prev ){
! 175: elem->prev->next = elem->next;
! 176: }else{
! 177: pH->first = elem->next;
! 178: }
! 179: if( elem->next ){
! 180: elem->next->prev = elem->prev;
! 181: }
! 182: if( pH->ht ){
! 183: pEntry = &pH->ht[h];
! 184: if( pEntry->chain==elem ){
! 185: pEntry->chain = elem->next;
! 186: }
! 187: pEntry->count--;
! 188: assert( pEntry->count>=0 );
! 189: }
! 190: sqlite3_free( elem );
! 191: pH->count--;
! 192: if( pH->count<=0 ){
! 193: assert( pH->first==0 );
! 194: assert( pH->count==0 );
! 195: sqlite3HashClear(pH);
! 196: }
! 197: }
! 198:
! 199: /* Attempt to locate an element of the hash table pH with a key
! 200: ** that matches pKey,nKey. Return the data for this element if it is
! 201: ** found, or NULL if there is no match.
! 202: */
! 203: void *sqlite3HashFind(const Hash *pH, const char *pKey, int nKey){
! 204: HashElem *elem; /* The element that matches key */
! 205: unsigned int h; /* A hash on key */
! 206:
! 207: assert( pH!=0 );
! 208: assert( pKey!=0 );
! 209: assert( nKey>=0 );
! 210: if( pH->ht ){
! 211: h = strHash(pKey, nKey) % pH->htsize;
! 212: }else{
! 213: h = 0;
! 214: }
! 215: elem = findElementGivenHash(pH, pKey, nKey, h);
! 216: return elem ? elem->data : 0;
! 217: }
! 218:
! 219: /* Insert an element into the hash table pH. The key is pKey,nKey
! 220: ** and the data is "data".
! 221: **
! 222: ** If no element exists with a matching key, then a new
! 223: ** element is created and NULL is returned.
! 224: **
! 225: ** If another element already exists with the same key, then the
! 226: ** new data replaces the old data and the old data is returned.
! 227: ** The key is not copied in this instance. If a malloc fails, then
! 228: ** the new data is returned and the hash table is unchanged.
! 229: **
! 230: ** If the "data" parameter to this function is NULL, then the
! 231: ** element corresponding to "key" is removed from the hash table.
! 232: */
! 233: void *sqlite3HashInsert(Hash *pH, const char *pKey, int nKey, void *data){
! 234: unsigned int h; /* the hash of the key modulo hash table size */
! 235: HashElem *elem; /* Used to loop thru the element list */
! 236: HashElem *new_elem; /* New element added to the pH */
! 237:
! 238: assert( pH!=0 );
! 239: assert( pKey!=0 );
! 240: assert( nKey>=0 );
! 241: if( pH->htsize ){
! 242: h = strHash(pKey, nKey) % pH->htsize;
! 243: }else{
! 244: h = 0;
! 245: }
! 246: elem = findElementGivenHash(pH,pKey,nKey,h);
! 247: if( elem ){
! 248: void *old_data = elem->data;
! 249: if( data==0 ){
! 250: removeElementGivenHash(pH,elem,h);
! 251: }else{
! 252: elem->data = data;
! 253: elem->pKey = pKey;
! 254: assert(nKey==elem->nKey);
! 255: }
! 256: return old_data;
! 257: }
! 258: if( data==0 ) return 0;
! 259: new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) );
! 260: if( new_elem==0 ) return data;
! 261: new_elem->pKey = pKey;
! 262: new_elem->nKey = nKey;
! 263: new_elem->data = data;
! 264: pH->count++;
! 265: if( pH->count>=10 && pH->count > 2*pH->htsize ){
! 266: if( rehash(pH, pH->count*2) ){
! 267: assert( pH->htsize>0 );
! 268: h = strHash(pKey, nKey) % pH->htsize;
! 269: }
! 270: }
! 271: if( pH->ht ){
! 272: insertElement(pH, &pH->ht[h], new_elem);
! 273: }else{
! 274: insertElement(pH, 0, new_elem);
! 275: }
! 276: return 0;
! 277: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src