wasCSharpSQLite – Blame information for rev 1

Subversion Repositories:
Rev:
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 }