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