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){ |
56 | unsigned int h = 0; |
57 | unsigned char c; |
58 | while( (c = (unsigned char)*z++)!=0 ){ /*OPTIMIZATION-IF-TRUE*/ |
59 | /* Knuth multiplicative hashing. (Sorting & Searching, p. 510). |
60 | ** 0x9e3779b1 is 2654435761 which is the closest prime number to |
61 | ** (2**32)*golden_ratio, where golden_ratio = (sqrt(5) - 1)/2. */ |
62 | h += sqlite3UpperToLower[c]; |
63 | h *= 0x9e3779b1; |
64 | } |
65 | return h; |
66 | } |
67 | |
68 | |
69 | /* Link pNew element into the hash table pH. If pEntry!=0 then also |
70 | ** insert pNew into the pEntry hash bucket. |
71 | */ |
72 | static void insertElement( |
73 | Hash *pH, /* The complete hash table */ |
74 | struct _ht *pEntry, /* The entry into which pNew is inserted */ |
75 | HashElem *pNew /* The element to be inserted */ |
76 | ){ |
77 | HashElem *pHead; /* First element already in pEntry */ |
78 | if( pEntry ){ |
79 | pHead = pEntry->count ? pEntry->chain : 0; |
80 | pEntry->count++; |
81 | pEntry->chain = pNew; |
82 | }else{ |
83 | pHead = 0; |
84 | } |
85 | if( pHead ){ |
86 | pNew->next = pHead; |
87 | pNew->prev = pHead->prev; |
88 | if( pHead->prev ){ pHead->prev->next = pNew; } |
89 | else { pH->first = pNew; } |
90 | pHead->prev = pNew; |
91 | }else{ |
92 | pNew->next = pH->first; |
93 | if( pH->first ){ pH->first->prev = pNew; } |
94 | pNew->prev = 0; |
95 | pH->first = pNew; |
96 | } |
97 | } |
98 | |
99 | |
100 | /* Resize the hash table so that it cantains "new_size" buckets. |
101 | ** |
102 | ** The hash table might fail to resize if sqlite3_malloc() fails or |
103 | ** if the new size is the same as the prior size. |
104 | ** Return TRUE if the resize occurs and false if not. |
105 | */ |
106 | static int rehash(Hash *pH, unsigned int new_size){ |
107 | struct _ht *new_ht; /* The new hash table */ |
108 | HashElem *elem, *next_elem; /* For looping over existing elements */ |
109 | |
110 | #if SQLITE_MALLOC_SOFT_LIMIT>0 |
111 | if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){ |
112 | new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht); |
113 | } |
114 | if( new_size==pH->htsize ) return 0; |
115 | #endif |
116 | |
117 | /* The inability to allocates space for a larger hash table is |
118 | ** a performance hit but it is not a fatal error. So mark the |
119 | ** allocation as a benign. Use sqlite3Malloc()/memset(0) instead of |
120 | ** sqlite3MallocZero() to make the allocation, as sqlite3MallocZero() |
121 | ** only zeroes the requested number of bytes whereas this module will |
122 | ** use the actual amount of space allocated for the hash table (which |
123 | ** may be larger than the requested amount). |
124 | */ |
125 | sqlite3BeginBenignMalloc(); |
126 | new_ht = (struct _ht *)sqlite3Malloc( new_size*sizeof(struct _ht) ); |
127 | sqlite3EndBenignMalloc(); |
128 | |
129 | if( new_ht==0 ) return 0; |
130 | sqlite3_free(pH->ht); |
131 | pH->ht = new_ht; |
132 | pH->htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht); |
133 | memset(new_ht, 0, new_size*sizeof(struct _ht)); |
134 | for(elem=pH->first, pH->first=0; elem; elem = next_elem){ |
135 | unsigned int h = strHash(elem->pKey) % new_size; |
136 | next_elem = elem->next; |
137 | insertElement(pH, &new_ht[h], elem); |
138 | } |
139 | return 1; |
140 | } |
141 | |
142 | /* This function (for internal use only) locates an element in an |
143 | ** hash table that matches the given key. If no element is found, |
144 | ** a pointer to a static null element with HashElem.data==0 is returned. |
145 | ** If pH is not NULL, then the hash for this key is written to *pH. |
146 | */ |
147 | static HashElem *findElementWithHash( |
148 | const Hash *pH, /* The pH to be searched */ |
149 | const char *pKey, /* The key we are searching for */ |
150 | unsigned int *pHash /* Write the hash value here */ |
151 | ){ |
152 | HashElem *elem; /* Used to loop thru the element list */ |
153 | unsigned int count; /* Number of elements left to test */ |
154 | unsigned int h; /* The computed hash */ |
155 | static HashElem nullElement = { 0, 0, 0, 0 }; |
156 | |
157 | if( pH->ht ){ /*OPTIMIZATION-IF-TRUE*/ |
158 | struct _ht *pEntry; |
159 | h = strHash(pKey) % pH->htsize; |
160 | pEntry = &pH->ht[h]; |
161 | elem = pEntry->chain; |
162 | count = pEntry->count; |
163 | }else{ |
164 | h = 0; |
165 | elem = pH->first; |
166 | count = pH->count; |
167 | } |
168 | if( pHash ) *pHash = h; |
169 | while( count-- ){ |
170 | assert( elem!=0 ); |
171 | if( sqlite3StrICmp(elem->pKey,pKey)==0 ){ |
172 | return elem; |
173 | } |
174 | elem = elem->next; |
175 | } |
176 | return &nullElement; |
177 | } |
178 | |
179 | /* Remove a single entry from the hash table given a pointer to that |
180 | ** element and a hash on the element's key. |
181 | */ |
182 | static void removeElementGivenHash( |
183 | Hash *pH, /* The pH containing "elem" */ |
184 | HashElem* elem, /* The element to be removed from the pH */ |
185 | unsigned int h /* Hash value for the element */ |
186 | ){ |
187 | struct _ht *pEntry; |
188 | if( elem->prev ){ |
189 | elem->prev->next = elem->next; |
190 | }else{ |
191 | pH->first = elem->next; |
192 | } |
193 | if( elem->next ){ |
194 | elem->next->prev = elem->prev; |
195 | } |
196 | if( pH->ht ){ |
197 | pEntry = &pH->ht[h]; |
198 | if( pEntry->chain==elem ){ |
199 | pEntry->chain = elem->next; |
200 | } |
201 | assert( pEntry->count>0 ); |
202 | pEntry->count--; |
203 | } |
204 | sqlite3_free( elem ); |
205 | pH->count--; |
206 | if( pH->count==0 ){ |
207 | assert( pH->first==0 ); |
208 | assert( pH->count==0 ); |
209 | sqlite3HashClear(pH); |
210 | } |
211 | } |
212 | |
213 | /* Attempt to locate an element of the hash table pH with a key |
214 | ** that matches pKey. Return the data for this element if it is |
215 | ** found, or NULL if there is no match. |
216 | */ |
217 | void *sqlite3HashFind(const Hash *pH, const char *pKey){ |
218 | assert( pH!=0 ); |
219 | assert( pKey!=0 ); |
220 | return findElementWithHash(pH, pKey, 0)->data; |
221 | } |
222 | |
223 | /* Insert an element into the hash table pH. The key is pKey |
224 | ** and the data is "data". |
225 | ** |
226 | ** If no element exists with a matching key, then a new |
227 | ** element is created and NULL is returned. |
228 | ** |
229 | ** If another element already exists with the same key, then the |
230 | ** new data replaces the old data and the old data is returned. |
231 | ** The key is not copied in this instance. If a malloc fails, then |
232 | ** the new data is returned and the hash table is unchanged. |
233 | ** |
234 | ** If the "data" parameter to this function is NULL, then the |
235 | ** element corresponding to "key" is removed from the hash table. |
236 | */ |
237 | void *sqlite3HashInsert(Hash *pH, const char *pKey, void *data){ |
238 | unsigned int h; /* the hash of the key modulo hash table size */ |
239 | HashElem *elem; /* Used to loop thru the element list */ |
240 | HashElem *new_elem; /* New element added to the pH */ |
241 | |
242 | assert( pH!=0 ); |
243 | assert( pKey!=0 ); |
244 | elem = findElementWithHash(pH,pKey,&h); |
245 | if( elem->data ){ |
246 | void *old_data = elem->data; |
247 | if( data==0 ){ |
248 | removeElementGivenHash(pH,elem,h); |
249 | }else{ |
250 | elem->data = data; |
251 | elem->pKey = pKey; |
252 | } |
253 | return old_data; |
254 | } |
255 | if( data==0 ) return 0; |
256 | new_elem = (HashElem*)sqlite3Malloc( sizeof(HashElem) ); |
257 | if( new_elem==0 ) return data; |
258 | new_elem->pKey = pKey; |
259 | new_elem->data = data; |
260 | pH->count++; |
261 | if( pH->count>=10 && pH->count > 2*pH->htsize ){ |
262 | if( rehash(pH, pH->count*2) ){ |
263 | assert( pH->htsize>0 ); |
264 | h = strHash(pKey) % pH->htsize; |
265 | } |
266 | } |
267 | insertElement(pH, pH->ht ? &pH->ht[h] : 0, new_elem); |
268 | return 0; |
269 | } |
270 | |