wasCSharpSQLite – Blame information for rev 4

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 office 1 using System;
2 using System.Diagnostics;
3 using System.Text;
4  
5 using i64 = System.Int64;
6 using u8 = System.Byte;
7 using u32 = System.UInt32;
8  
9 using Pgno = System.UInt32;
10  
11 namespace Community.CsharpSqlite
12 {
13 using sqlite3_int64 = System.Int64;
14  
15 public partial class Sqlite3
16 {
17 /*
18 ** 2008 December 3
19 **
20 ** The author disclaims copyright to this source code. In place of
21 ** a legal notice, here is a blessing:
22 **
23 ** May you do good and not evil.
24 ** May you find forgiveness for yourself and forgive others.
25 ** May you share freely, never taking more than you give.
26 **
27 *************************************************************************
28 **
29 ** This module implements an object we call a "RowSet".
30 **
31 ** The RowSet object is a collection of rowids. Rowids
32 ** are inserted into the RowSet in an arbitrary order. Inserts
33 ** can be intermixed with tests to see if a given rowid has been
34 ** previously inserted into the RowSet.
35 **
36 ** After all inserts are finished, it is possible to extract the
37 ** elements of the RowSet in sorted order. Once this extraction
38 ** process has started, no new elements may be inserted.
39 **
40 ** Hence, the primitive operations for a RowSet are:
41 **
42 ** CREATE
43 ** INSERT
44 ** TEST
45 ** SMALLEST
46 ** DESTROY
47 **
48 ** The CREATE and DESTROY primitives are the constructor and destructor,
49 ** obviously. The INSERT primitive adds a new element to the RowSet.
50 ** TEST checks to see if an element is already in the RowSet. SMALLEST
51 ** extracts the least value from the RowSet.
52 **
53 ** The INSERT primitive might allocate additional memory. Memory is
54 ** allocated in chunks so most INSERTs do no allocation. There is an
55 ** upper bound on the size of allocated memory. No memory is freed
56 ** until DESTROY.
57 **
58 ** The TEST primitive includes a "batch" number. The TEST primitive
59 ** will only see elements that were inserted before the last change
60 ** in the batch number. In other words, if an INSERT occurs between
61 ** two TESTs where the TESTs have the same batch nubmer, then the
62 ** value added by the INSERT will not be visible to the second TEST.
63 ** The initial batch number is zero, so if the very first TEST contains
64 ** a non-zero batch number, it will see all prior INSERTs.
65 **
66 ** No INSERTs may occurs after a SMALLEST. An assertion will fail if
67 ** that is attempted.
68 **
69 ** The cost of an INSERT is roughly constant. (Sometime new memory
70 ** has to be allocated on an INSERT.) The cost of a TEST with a new
71 ** batch number is O(NlogN) where N is the number of elements in the RowSet.
72 ** The cost of a TEST using the same batch number is O(logN). The cost
73 ** of the first SMALLEST is O(NlogN). Second and subsequent SMALLEST
74 ** primitives are constant time. The cost of DESTROY is O(N).
75 **
76 ** There is an added cost of O(N) when switching between TEST and
77 ** SMALLEST primitives.
78 *************************************************************************
79 ** Included in SQLite3 port to C#-SQLite; 2008 Noah B Hart
80 ** C#-SQLite is an independent reimplementation of the SQLite software library
81 **
82 ** SQLITE_SOURCE_ID: 2010-08-23 18:52:01 42537b60566f288167f1b5864a5435986838e3a3
83 **
84 *************************************************************************
85 */
86 //#include "sqliteInt.h"
87  
88 /*
89 ** Target size for allocation chunks.
90 */
91 //#define ROWSET_ALLOCATION_SIZE 1024
92 const int ROWSET_ALLOCATION_SIZE = 1024;
93 /*
94 ** The number of rowset entries per allocation chunk.
95 */
96 //#define ROWSET_ENTRY_PER_CHUNK \
97 // ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry))
98 const int ROWSET_ENTRY_PER_CHUNK = 63;
99  
100 /*
101 ** Each entry in a RowSet is an instance of the following object.
102 */
103 public class RowSetEntry
104 {
105 public i64 v; /* ROWID value for this entry */
106 public RowSetEntry pRight; /* Right subtree (larger entries) or list */
107 public RowSetEntry pLeft; /* Left subtree (smaller entries) */
108 };
109  
110 /*
111 ** Index entries are allocated in large chunks (instances of the
112 ** following structure) to reduce memory allocation overhead. The
113 ** chunks are kept on a linked list so that they can be deallocated
114 ** when the RowSet is destroyed.
115 */
116 public class RowSetChunk
117 {
118 public RowSetChunk pNextChunk; /* Next chunk on list of them all */
119 public RowSetEntry[] aEntry = new RowSetEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */
120 };
121  
122 /*
123 ** A RowSet in an instance of the following structure.
124 **
125 ** A typedef of this structure if found in sqliteInt.h.
126 */
127 public class RowSet
128 {
129 public RowSetChunk pChunk; /* List of all chunk allocations */
130 public sqlite3 db; /* The database connection */
131 public RowSetEntry pEntry; /* /* List of entries using pRight */
132 public RowSetEntry pLast; /* Last entry on the pEntry list */
133 public RowSetEntry[] pFresh; /* Source of new entry objects */
134 public RowSetEntry pTree; /* Binary tree of entries */
135 public int nFresh; /* Number of objects on pFresh */
136 public bool isSorted; /* True if pEntry is sorted */
137 public u8 iBatch; /* Current insert batch */
138  
139 public RowSet( sqlite3 db, int N )
140 {
141 this.pChunk = null;
142 this.db = db;
143 this.pEntry = null;
144 this.pLast = null;
145 this.pFresh = new RowSetEntry[N];
146 this.pTree = null;
147 this.nFresh = N;
148 this.isSorted = true;
149 this.iBatch = 0;
150 }
151 };
152  
153 /*
154 ** Turn bulk memory into a RowSet object. N bytes of memory
155 ** are available at pSpace. The db pointer is used as a memory context
156 ** for any subsequent allocations that need to occur.
157 ** Return a pointer to the new RowSet object.
158 **
159 ** It must be the case that N is sufficient to make a Rowset. If not
160 ** an assertion fault occurs.
161 **
162 ** If N is larger than the minimum, use the surplus as an initial
163 ** allocation of entries available to be filled.
164 */
165 static RowSet sqlite3RowSetInit( sqlite3 db, object pSpace, u32 N )
166 {
167 RowSet p = new RowSet( db, (int)N );
168 //Debug.Assert(N >= ROUND8(sizeof(*p)) );
169 // p = pSpace;
170 // p.pChunk = 0;
171 // p.db = db;
172 // p.pEntry = 0;
173 // p.pLast = 0;
174 // p.pTree = 0;
175 // p.pFresh =(struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p);
176 // p.nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry));
177 // p.isSorted = 1;
178 // p.iBatch = 0;
179 return p;
180 }
181  
182 /*
183 ** Deallocate all chunks from a RowSet. This frees all memory that
184 ** the RowSet has allocated over its lifetime. This routine is
185 ** the destructor for the RowSet.
186 */
187 static void sqlite3RowSetClear( RowSet p )
188 {
189 RowSetChunk pChunk, pNextChunk;
190 for ( pChunk = p.pChunk; pChunk != null; pChunk = pNextChunk )
191 {
192 pNextChunk = pChunk.pNextChunk;
193 sqlite3DbFree( p.db, ref pChunk );
194 }
195 p.pChunk = null;
196 p.nFresh = 0;
197 p.pEntry = null;
198 p.pLast = null;
199 p.pTree = null;
200 p.isSorted = true;
201 }
202  
203 /*
204 ** Insert a new value into a RowSet.
205 **
206 ** The mallocFailed flag of the database connection is set if a
207 ** memory allocation fails.
208 */
209 static void sqlite3RowSetInsert( RowSet p, i64 rowid )
210 {
211 RowSetEntry pEntry; /* The new entry */
212 RowSetEntry pLast; /* The last prior entry */
213 Debug.Assert( p != null );
214 if ( p.nFresh == 0 )
215 {
216 RowSetChunk pNew;
217 pNew = new RowSetChunk();//sqlite3DbMallocRaw(p.db, sizeof(*pNew));
218 if ( pNew == null )
219 {
220 return;
221 }
222 pNew.pNextChunk = p.pChunk;
223 p.pChunk = pNew;
224 p.pFresh = pNew.aEntry;
225 p.nFresh = ROWSET_ENTRY_PER_CHUNK;
226 }
227 p.pFresh[p.pFresh.Length - p.nFresh] = new RowSetEntry();
228 pEntry = p.pFresh[p.pFresh.Length - p.nFresh];
229 p.nFresh--;
230 pEntry.v = rowid;
231 pEntry.pRight = null;
232 pLast = p.pLast;
233 if ( pLast != null )
234 {
235 if ( p.isSorted && rowid <= pLast.v )
236 {
237 p.isSorted = false;
238 }
239 pLast.pRight = pEntry;
240 }
241 else
242 {
243 Debug.Assert( p.pEntry == null );/* Fires if INSERT after SMALLEST */
244 p.pEntry = pEntry;
245 }
246 p.pLast = pEntry;
247 }
248  
249 /*
250 ** Merge two lists of RowSetEntry objects. Remove duplicates.
251 **
252 ** The input lists are connected via pRight pointers and are
253 ** assumed to each already be in sorted order.
254 */
255 static RowSetEntry rowSetMerge(
256 RowSetEntry pA, /* First sorted list to be merged */
257 RowSetEntry pB /* Second sorted list to be merged */
258 )
259 {
260 RowSetEntry head = new RowSetEntry();
261 RowSetEntry pTail;
262  
263 pTail = head;
264 while ( pA != null && pB != null )
265 {
266 Debug.Assert( pA.pRight == null || pA.v <= pA.pRight.v );
267 Debug.Assert( pB.pRight == null || pB.v <= pB.pRight.v );
268 if ( pA.v < pB.v )
269 {
270 pTail.pRight = pA;
271 pA = pA.pRight;
272 pTail = pTail.pRight;
273 }
274 else if ( pB.v < pA.v )
275 {
276 pTail.pRight = pB;
277 pB = pB.pRight;
278 pTail = pTail.pRight;
279 }
280 else
281 {
282 pA = pA.pRight;
283 }
284 }
285 if ( pA != null )
286 {
287 Debug.Assert( pA.pRight == null || pA.v <= pA.pRight.v );
288 pTail.pRight = pA;
289 }
290 else
291 {
292 Debug.Assert( pB == null || pB.pRight == null || pB.v <= pB.pRight.v );
293 pTail.pRight = pB;
294 }
295 return head.pRight;
296 }
297  
298 /*
299 ** Sort all elements on the pEntry list of the RowSet into ascending order.
300 */
301 static void rowSetSort( RowSet p )
302 {
303 u32 i;
304 RowSetEntry pEntry;
305 RowSetEntry[] aBucket = new RowSetEntry[40];
306  
307 Debug.Assert( p.isSorted == false );
308 //memset(aBucket, 0, sizeof(aBucket));
309 while ( p.pEntry != null )
310 {
311 pEntry = p.pEntry;
312 p.pEntry = pEntry.pRight;
313 pEntry.pRight = null;
314 for ( i = 0; aBucket[i] != null; i++ )
315 {
316 pEntry = rowSetMerge( aBucket[i], pEntry );
317 aBucket[i] = null;
318 }
319 aBucket[i] = pEntry;
320 }
321 pEntry = null;
322 for ( i = 0; i < aBucket.Length; i++ )//sizeof(aBucket)/sizeof(aBucket[0])
323 {
324 pEntry = rowSetMerge( pEntry, aBucket[i] );
325 }
326 p.pEntry = pEntry;
327 p.pLast = null;
328 p.isSorted = true;
329 }
330  
331 /*
332 ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
333 ** Convert this tree into a linked list connected by the pRight pointers
334 ** and return pointers to the first and last elements of the new list.
335 */
336 static void rowSetTreeToList(
337 RowSetEntry pIn, /* Root of the input tree */
338 ref RowSetEntry ppFirst, /* Write head of the output list here */
339 ref RowSetEntry ppLast /* Write tail of the output list here */
340 )
341 {
342 Debug.Assert( pIn != null );
343 if ( pIn.pLeft != null )
344 {
345 RowSetEntry p = new RowSetEntry();
346 rowSetTreeToList( pIn.pLeft, ref ppFirst, ref p );
347 p.pRight = pIn;
348 }
349 else
350 {
351 ppFirst = pIn;
352 }
353 if ( pIn.pRight != null )
354 {
355 rowSetTreeToList( pIn.pRight, ref pIn.pRight, ref ppLast );
356 }
357 else
358 {
359 ppLast = pIn;
360 }
361 Debug.Assert( ( ppLast ).pRight == null );
362 }
363  
364  
365 /*
366 ** Convert a sorted list of elements (connected by pRight) into a binary
367 ** tree with depth of iDepth. A depth of 1 means the tree contains a single
368 ** node taken from the head of *ppList. A depth of 2 means a tree with
369 ** three nodes. And so forth.
370 **
371 ** Use as many entries from the input list as required and update the
372 ** *ppList to point to the unused elements of the list. If the input
373 ** list contains too few elements, then construct an incomplete tree
374 ** and leave *ppList set to NULL.
375 **
376 ** Return a pointer to the root of the constructed binary tree.
377 */
378 static RowSetEntry rowSetNDeepTree(
379 ref RowSetEntry ppList,
380 int iDepth
381 )
382 {
383 RowSetEntry p; /* Root of the new tree */
384 RowSetEntry pLeft; /* Left subtree */
385 if ( ppList == null )
386 {
387 return null;
388 }
389 if ( iDepth == 1 )
390 {
391 p = ppList;
392 ppList = p.pRight;
393 p.pLeft = p.pRight = null;
394 return p;
395 }
396 pLeft = rowSetNDeepTree( ref ppList, iDepth - 1 );
397 p = ppList;
398 if ( p == null )
399 {
400 return pLeft;
401 }
402 p.pLeft = pLeft;
403 ppList = p.pRight;
404 p.pRight = rowSetNDeepTree( ref ppList, iDepth - 1 );
405 return p;
406 }
407  
408 /*
409 ** Convert a sorted list of elements into a binary tree. Make the tree
410 ** as deep as it needs to be in order to contain the entire list.
411 */
412 static RowSetEntry rowSetListToTree( RowSetEntry pList )
413 {
414 int iDepth; /* Depth of the tree so far */
415 RowSetEntry p; /* Current tree root */
416 RowSetEntry pLeft; /* Left subtree */
417  
418 Debug.Assert( pList != null );
419 p = pList;
420 pList = p.pRight;
421 p.pLeft = p.pRight = null;
422 for ( iDepth = 1; pList != null; iDepth++ )
423 {
424 pLeft = p;
425 p = pList;
426 pList = p.pRight;
427 p.pLeft = pLeft;
428 p.pRight = rowSetNDeepTree( ref pList, iDepth );
429 }
430 return p;
431 }
432  
433 /*
434 ** Convert the list in p.pEntry into a sorted list if it is not
435 ** sorted already. If there is a binary tree on p.pTree, then
436 ** convert it into a list too and merge it into the p.pEntry list.
437 */
438 static void rowSetToList( RowSet p )
439 {
440 if ( !p.isSorted )
441 {
442 rowSetSort( p );
443 }
444 if ( p.pTree != null )
445 {
446 RowSetEntry pHead = new RowSetEntry();
447 RowSetEntry pTail = new RowSetEntry();
448 rowSetTreeToList( p.pTree, ref pHead, ref pTail );
449 p.pTree = null;
450 p.pEntry = rowSetMerge( p.pEntry, pHead );
451 }
452 }
453  
454 /*
455 ** Extract the smallest element from the RowSet.
456 ** Write the element into *pRowid. Return 1 on success. Return
457 ** 0 if the RowSet is already empty.
458 **
459 ** After this routine has been called, the sqlite3RowSetInsert()
460 ** routine may not be called again.
461 */
462 static int sqlite3RowSetNext( RowSet p, ref i64 pRowid )
463 {
464 rowSetToList( p );
465 if ( p.pEntry != null )
466 {
467 pRowid = p.pEntry.v;
468 p.pEntry = p.pEntry.pRight;
469 if ( p.pEntry == null )
470 {
471 sqlite3RowSetClear( p );
472 }
473 return 1;
474 }
475 else
476 {
477 return 0;
478 }
479 }
480  
481 /*
482 ** Check to see if element iRowid was inserted into the the rowset as
483 ** part of any insert batch prior to iBatch. Return 1 or 0.
484 */
485 static int sqlite3RowSetTest( RowSet pRowSet, u8 iBatch, sqlite3_int64 iRowid )
486 {
487 RowSetEntry p;
488 if ( iBatch != pRowSet.iBatch )
489 {
490 if ( pRowSet.pEntry != null )
491 {
492 rowSetToList( pRowSet );
493 pRowSet.pTree = rowSetListToTree( pRowSet.pEntry );
494 pRowSet.pEntry = null;
495 pRowSet.pLast = null;
496 }
497 pRowSet.iBatch = iBatch;
498 }
499 p = pRowSet.pTree;
500 while ( p != null )
501 {
502 if ( p.v < iRowid )
503 {
504 p = p.pRight;
505 }
506 else if ( p.v > iRowid )
507 {
508 p = p.pLeft;
509 }
510 else
511 {
512 return 1;
513 }
514 }
515 return 0;
516 }
517  
518 }
519 }