wasCSharpSQLite – Blame information for rev 4
?pathlinks?
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 | } |