wasCSharpSQLite – Blame information for rev
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | using System; |
2 | using System.Diagnostics; |
||
3 | using System.Text; |
||
4 | |||
5 | using u8 = System.Byte; |
||
6 | using u32 = System.UInt32; |
||
7 | |||
8 | namespace Community.CsharpSqlite |
||
9 | { |
||
10 | public partial class Sqlite3 |
||
11 | { |
||
12 | /* |
||
13 | ** 2001 September 22 |
||
14 | ** |
||
15 | ** The author disclaims copyright to this source code. In place of |
||
16 | ** a legal notice, here is a blessing: |
||
17 | ** |
||
18 | ** May you do good and not evil. |
||
19 | ** May you find forgiveness for yourself and forgive others. |
||
20 | ** May you share freely, never taking more than you give. |
||
21 | ** |
||
22 | ************************************************************************* |
||
23 | ** This is the implementation of generic hash-tables |
||
24 | ** used in SQLite. |
||
25 | ************************************************************************* |
||
26 | ** Included in SQLite3 port to C#-SQLite; 2008 Noah B Hart |
||
27 | ** C#-SQLite is an independent reimplementation of the SQLite software library |
||
28 | ** |
||
29 | ** SQLITE_SOURCE_ID: 2010-08-23 18:52:01 42537b60566f288167f1b5864a5435986838e3a3 |
||
30 | ** |
||
31 | ************************************************************************* |
||
32 | */ |
||
33 | //#include "sqliteInt.h" |
||
34 | //#include <assert.h> |
||
35 | |||
36 | /* Turn bulk memory into a hash table object by initializing the |
||
37 | ** fields of the Hash structure. |
||
38 | ** |
||
39 | ** "pNew" is a pointer to the hash table that is to be initialized. |
||
40 | */ |
||
41 | static void sqlite3HashInit( Hash pNew ) |
||
42 | { |
||
43 | Debug.Assert( pNew != null ); |
||
44 | pNew.first = null; |
||
45 | pNew.count = 0; |
||
46 | pNew.htsize = 0; |
||
47 | pNew.ht = null; |
||
48 | } |
||
49 | |||
50 | /* Remove all entries from a hash table. Reclaim all memory. |
||
51 | ** Call this routine to delete a hash table or to reset a hash table |
||
52 | ** to the empty state. |
||
53 | */ |
||
54 | static void sqlite3HashClear( Hash pH ) |
||
55 | { |
||
56 | HashElem elem; /* For looping over all elements of the table */ |
||
57 | |||
58 | Debug.Assert( pH != null ); |
||
59 | elem = pH.first; |
||
60 | pH.first = null; |
||
61 | //sqlite3_free( ref pH.ht ); |
||
62 | pH.ht = null; |
||
63 | pH.htsize = 0; |
||
64 | while ( elem != null ) |
||
65 | { |
||
66 | HashElem next_elem = elem.next; |
||
67 | ////sqlite3_free(ref elem ); |
||
68 | elem = next_elem; |
||
69 | } |
||
70 | pH.count = 0; |
||
71 | } |
||
72 | |||
73 | /* |
||
74 | ** The hashing function. |
||
75 | */ |
||
76 | static u32 strHash( string z, int nKey ) |
||
77 | { |
||
78 | int h = 0; |
||
79 | Debug.Assert( nKey >= 0 ); |
||
80 | int _z = 0; |
||
81 | while ( nKey > 0 ) |
||
82 | { |
||
83 | h = ( h << 3 ) ^ h ^ ( ( _z < z.Length ) ? (int)sqlite3UpperToLower[(byte)z[_z++]] : 0 ); |
||
84 | nKey--; |
||
85 | } |
||
86 | return (u32)h; |
||
87 | } |
||
88 | |||
89 | /* Link pNew element into the hash table pH. If pEntry!=0 then also |
||
90 | ** insert pNew into the pEntry hash bucket. |
||
91 | */ |
||
92 | static void insertElement( |
||
93 | Hash pH, /* The complete hash table */ |
||
94 | _ht pEntry, /* The entry into which pNew is inserted */ |
||
95 | HashElem pNew /* The element to be inserted */ |
||
96 | ) |
||
97 | { |
||
98 | HashElem pHead; /* First element already in pEntry */ |
||
99 | if ( pEntry != null ) |
||
100 | { |
||
101 | pHead = pEntry.count != 0 ? pEntry.chain : null; |
||
102 | pEntry.count++; |
||
103 | pEntry.chain = pNew; |
||
104 | } |
||
105 | else |
||
106 | { |
||
107 | pHead = null; |
||
108 | } |
||
109 | if ( pHead != null ) |
||
110 | { |
||
111 | pNew.next = pHead; |
||
112 | pNew.prev = pHead.prev; |
||
113 | if ( pHead.prev != null ) |
||
114 | { |
||
115 | pHead.prev.next = pNew; |
||
116 | } |
||
117 | else |
||
118 | { |
||
119 | pH.first = pNew; |
||
120 | } |
||
121 | pHead.prev = pNew; |
||
122 | } |
||
123 | else |
||
124 | { |
||
125 | pNew.next = pH.first; |
||
126 | if ( pH.first != null ) |
||
127 | { |
||
128 | pH.first.prev = pNew; |
||
129 | } |
||
130 | pNew.prev = null; |
||
131 | pH.first = pNew; |
||
132 | } |
||
133 | } |
||
134 | |||
135 | /* Resize the hash table so that it cantains "new_size" buckets. |
||
136 | ** |
||
137 | ** The hash table might fail to resize if sqlite3_malloc() fails or |
||
138 | ** if the new size is the same as the prior size. |
||
139 | ** Return TRUE if the resize occurs and false if not. |
||
140 | */ |
||
141 | static bool rehash( ref Hash pH, u32 new_size ) |
||
142 | { |
||
143 | _ht[] new_ht; /* The new hash table */ |
||
144 | HashElem elem; |
||
145 | HashElem next_elem; /* For looping over existing elements */ |
||
146 | |||
147 | #if SQLITE_MALLOC_SOFT_LIMIT |
||
148 | if( new_size*sizeof(struct _ht)>SQLITE_MALLOC_SOFT_LIMIT ){ |
||
149 | new_size = SQLITE_MALLOC_SOFT_LIMIT/sizeof(struct _ht); |
||
150 | } |
||
151 | if( new_size==pH->htsize ) return false; |
||
152 | #endif |
||
153 | |||
154 | /* There is a call to sqlite3Malloc() inside rehash(). If there is |
||
155 | ** already an allocation at pH.ht, then if this malloc() fails it |
||
156 | ** is benign (since failing to resize a hash table is a performance |
||
157 | ** hit only, not a fatal error). |
||
158 | */ |
||
159 | sqlite3BeginBenignMalloc(); |
||
160 | new_ht = new _ht[new_size]; //(struct _ht )sqlite3Malloc( new_size*sizeof(struct _ht) ); |
||
161 | for ( int i = 0; i < new_size; i++ ) |
||
162 | new_ht[i] = new _ht(); |
||
163 | sqlite3EndBenignMalloc(); |
||
164 | |||
165 | if ( new_ht == null ) |
||
166 | return false; |
||
167 | //sqlite3_free( ref pH.ht ); |
||
168 | pH.ht = new_ht; |
||
169 | // pH.htsize = new_size = sqlite3MallocSize(new_ht)/sizeof(struct _ht); |
||
170 | //memset(new_ht, 0, new_size*sizeof(struct _ht)); |
||
171 | pH.htsize = new_size; |
||
172 | |||
173 | for ( elem = pH.first, pH.first = null; elem != null; elem = next_elem ) |
||
174 | { |
||
175 | u32 h = strHash( elem.pKey, elem.nKey ) % new_size; |
||
176 | next_elem = elem.next; |
||
177 | insertElement( pH, new_ht[h], elem ); |
||
178 | } |
||
179 | return true; |
||
180 | } |
||
181 | |||
182 | /* This function (for internal use only) locates an element in an |
||
183 | ** hash table that matches the given key. The hash for this key has |
||
184 | ** already been computed and is passed as the 4th parameter. |
||
185 | */ |
||
186 | static HashElem findElementGivenHash( |
||
187 | Hash pH, /* The pH to be searched */ |
||
188 | string pKey, /* The key we are searching for */ |
||
189 | int nKey, /* Bytes in key (not counting zero terminator) */ |
||
190 | u32 h /* The hash for this key. */ |
||
191 | ) |
||
192 | { |
||
193 | HashElem elem; /* Used to loop thru the element list */ |
||
194 | int count; /* Number of elements left to test */ |
||
195 | |||
196 | if ( pH.ht != null && pH.ht[h] != null ) |
||
197 | { |
||
198 | _ht pEntry = pH.ht[h]; |
||
199 | elem = pEntry.chain; |
||
200 | count = (int)pEntry.count; |
||
201 | } |
||
202 | else |
||
203 | { |
||
204 | elem = pH.first; |
||
205 | count = (int)pH.count; |
||
206 | } |
||
207 | while ( count-- > 0 && ALWAYS( elem ) ) |
||
208 | { |
||
209 | if ( elem.nKey == nKey && elem.pKey.Equals( pKey, StringComparison.OrdinalIgnoreCase ) ) |
||
210 | { |
||
211 | return elem; |
||
212 | } |
||
213 | elem = elem.next; |
||
214 | } |
||
215 | return null; |
||
216 | } |
||
217 | |||
218 | /* Remove a single entry from the hash table given a pointer to that |
||
219 | ** element and a hash on the element's key. |
||
220 | */ |
||
221 | static void removeElementGivenHash( |
||
222 | Hash pH, /* The pH containing "elem" */ |
||
223 | ref HashElem elem, /* The element to be removed from the pH */ |
||
224 | u32 h /* Hash value for the element */ |
||
225 | ) |
||
226 | { |
||
227 | _ht pEntry; |
||
228 | if ( elem.prev != null ) |
||
229 | { |
||
230 | elem.prev.next = elem.next; |
||
231 | } |
||
232 | else |
||
233 | { |
||
234 | pH.first = elem.next; |
||
235 | } |
||
236 | if ( elem.next != null ) |
||
237 | { |
||
238 | elem.next.prev = elem.prev; |
||
239 | } |
||
240 | if ( pH.ht != null && pH.ht[h] != null ) |
||
241 | { |
||
242 | pEntry = pH.ht[h]; |
||
243 | if ( pEntry.chain == elem ) |
||
244 | { |
||
245 | pEntry.chain = elem.next; |
||
246 | } |
||
247 | pEntry.count--; |
||
248 | Debug.Assert( pEntry.count >= 0 ); |
||
249 | } |
||
250 | //sqlite3_free( ref elem ); |
||
251 | pH.count--; |
||
252 | if ( pH.count <= 0 ) |
||
253 | { |
||
254 | Debug.Assert( pH.first == null ); |
||
255 | Debug.Assert( pH.count == 0 ); |
||
256 | sqlite3HashClear( pH ); |
||
257 | } |
||
258 | } |
||
259 | |||
260 | /* Attempt to locate an element of the hash table pH with a key |
||
261 | ** that matches pKey,nKey. Return the data for this element if it is |
||
262 | ** found, or NULL if there is no match. |
||
263 | */ |
||
264 | static T sqlite3HashFind<T>( Hash pH, string pKey, int nKey, T nullType ) where T : class |
||
265 | { |
||
266 | HashElem elem; /* The element that matches key */ |
||
267 | u32 h; /* A hash on key */ |
||
268 | |||
269 | Debug.Assert( pH != null ); |
||
270 | Debug.Assert( pKey != null ); |
||
271 | Debug.Assert( nKey >= 0 ); |
||
272 | if ( pH.ht != null ) |
||
273 | { |
||
274 | h = strHash( pKey, nKey ) % pH.htsize; |
||
275 | } |
||
276 | else |
||
277 | { |
||
278 | h = 0; |
||
279 | } |
||
280 | elem = findElementGivenHash( pH, pKey, nKey, h ); |
||
281 | return elem != null ? (T)elem.data : nullType; |
||
282 | } |
||
283 | |||
284 | /* Insert an element into the hash table pH. The key is pKey,nKey |
||
285 | ** and the data is "data". |
||
286 | ** |
||
287 | ** If no element exists with a matching key, then a new |
||
288 | ** element is created and NULL is returned. |
||
289 | ** |
||
290 | ** If another element already exists with the same key, then the |
||
291 | ** new data replaces the old data and the old data is returned. |
||
292 | ** The key is not copied in this instance. If a malloc fails, then |
||
293 | ** the new data is returned and the hash table is unchanged. |
||
294 | ** |
||
295 | ** If the "data" parameter to this function is NULL, then the |
||
296 | ** element corresponding to "key" is removed from the hash table. |
||
297 | */ |
||
298 | static T sqlite3HashInsert<T>( ref Hash pH, string pKey, int nKey, T data ) where T : class |
||
299 | { |
||
300 | u32 h; /* the hash of the key modulo hash table size */ |
||
301 | |||
302 | HashElem elem; /* Used to loop thru the element list */ |
||
303 | HashElem new_elem; /* New element added to the pH */ |
||
304 | |||
305 | Debug.Assert( pH != null ); |
||
306 | Debug.Assert( pKey != null ); |
||
307 | Debug.Assert( nKey >= 0 ); |
||
308 | |||
309 | if ( pH.htsize != 0 ) |
||
310 | { |
||
311 | h = strHash( pKey, nKey ) % pH.htsize; |
||
312 | } |
||
313 | else |
||
314 | { |
||
315 | h = 0; |
||
316 | } |
||
317 | elem = findElementGivenHash( pH, pKey, nKey, h ); |
||
318 | if ( elem != null ) |
||
319 | { |
||
320 | T old_data = (T)elem.data; |
||
321 | if ( data == null ) |
||
322 | { |
||
323 | removeElementGivenHash( pH, ref elem, h ); |
||
324 | } |
||
325 | else |
||
326 | { |
||
327 | elem.data = data; |
||
328 | elem.pKey = pKey; |
||
329 | Debug.Assert( nKey == elem.nKey ); |
||
330 | } |
||
331 | return old_data; |
||
332 | } |
||
333 | if ( data == null ) |
||
334 | return data; |
||
335 | new_elem = new HashElem();//(HashElem)sqlite3Malloc( sizeof(HashElem) ); |
||
336 | if ( new_elem == null ) |
||
337 | return data; |
||
338 | new_elem.pKey = pKey; |
||
339 | new_elem.nKey = nKey; |
||
340 | new_elem.data = data; |
||
341 | pH.count++; |
||
342 | if ( pH.count >= 10 && pH.count > 2 * pH.htsize ) |
||
343 | { |
||
344 | if ( rehash( ref pH, pH.count * 2 ) ) |
||
345 | { |
||
346 | Debug.Assert( pH.htsize > 0 ); |
||
347 | h = strHash( pKey, nKey ) % pH.htsize; |
||
348 | } |
||
349 | } |
||
350 | if ( pH.ht != null ) |
||
351 | { |
||
352 | insertElement( pH, pH.ht[h], new_elem ); |
||
353 | |||
354 | } |
||
355 | else |
||
356 | { |
||
357 | insertElement( pH, null, new_elem ); |
||
358 | } |
||
359 | return null; |
||
360 | } |
||
361 | |||
362 | } |
||
363 | } |