Annotation of embedaddon/sqlite3/src/rowset.c, revision 1.1.1.1
1.1 misho 1: /*
2: ** 2008 December 3
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: **
13: ** This module implements an object we call a "RowSet".
14: **
15: ** The RowSet object is a collection of rowids. Rowids
16: ** are inserted into the RowSet in an arbitrary order. Inserts
17: ** can be intermixed with tests to see if a given rowid has been
18: ** previously inserted into the RowSet.
19: **
20: ** After all inserts are finished, it is possible to extract the
21: ** elements of the RowSet in sorted order. Once this extraction
22: ** process has started, no new elements may be inserted.
23: **
24: ** Hence, the primitive operations for a RowSet are:
25: **
26: ** CREATE
27: ** INSERT
28: ** TEST
29: ** SMALLEST
30: ** DESTROY
31: **
32: ** The CREATE and DESTROY primitives are the constructor and destructor,
33: ** obviously. The INSERT primitive adds a new element to the RowSet.
34: ** TEST checks to see if an element is already in the RowSet. SMALLEST
35: ** extracts the least value from the RowSet.
36: **
37: ** The INSERT primitive might allocate additional memory. Memory is
38: ** allocated in chunks so most INSERTs do no allocation. There is an
39: ** upper bound on the size of allocated memory. No memory is freed
40: ** until DESTROY.
41: **
42: ** The TEST primitive includes a "batch" number. The TEST primitive
43: ** will only see elements that were inserted before the last change
44: ** in the batch number. In other words, if an INSERT occurs between
45: ** two TESTs where the TESTs have the same batch nubmer, then the
46: ** value added by the INSERT will not be visible to the second TEST.
47: ** The initial batch number is zero, so if the very first TEST contains
48: ** a non-zero batch number, it will see all prior INSERTs.
49: **
50: ** No INSERTs may occurs after a SMALLEST. An assertion will fail if
51: ** that is attempted.
52: **
53: ** The cost of an INSERT is roughly constant. (Sometime new memory
54: ** has to be allocated on an INSERT.) The cost of a TEST with a new
55: ** batch number is O(NlogN) where N is the number of elements in the RowSet.
56: ** The cost of a TEST using the same batch number is O(logN). The cost
57: ** of the first SMALLEST is O(NlogN). Second and subsequent SMALLEST
58: ** primitives are constant time. The cost of DESTROY is O(N).
59: **
60: ** There is an added cost of O(N) when switching between TEST and
61: ** SMALLEST primitives.
62: */
63: #include "sqliteInt.h"
64:
65:
66: /*
67: ** Target size for allocation chunks.
68: */
69: #define ROWSET_ALLOCATION_SIZE 1024
70:
71: /*
72: ** The number of rowset entries per allocation chunk.
73: */
74: #define ROWSET_ENTRY_PER_CHUNK \
75: ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry))
76:
77: /*
78: ** Each entry in a RowSet is an instance of the following object.
79: */
80: struct RowSetEntry {
81: i64 v; /* ROWID value for this entry */
82: struct RowSetEntry *pRight; /* Right subtree (larger entries) or list */
83: struct RowSetEntry *pLeft; /* Left subtree (smaller entries) */
84: };
85:
86: /*
87: ** RowSetEntry objects are allocated in large chunks (instances of the
88: ** following structure) to reduce memory allocation overhead. The
89: ** chunks are kept on a linked list so that they can be deallocated
90: ** when the RowSet is destroyed.
91: */
92: struct RowSetChunk {
93: struct RowSetChunk *pNextChunk; /* Next chunk on list of them all */
94: struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */
95: };
96:
97: /*
98: ** A RowSet in an instance of the following structure.
99: **
100: ** A typedef of this structure if found in sqliteInt.h.
101: */
102: struct RowSet {
103: struct RowSetChunk *pChunk; /* List of all chunk allocations */
104: sqlite3 *db; /* The database connection */
105: struct RowSetEntry *pEntry; /* List of entries using pRight */
106: struct RowSetEntry *pLast; /* Last entry on the pEntry list */
107: struct RowSetEntry *pFresh; /* Source of new entry objects */
108: struct RowSetEntry *pTree; /* Binary tree of entries */
109: u16 nFresh; /* Number of objects on pFresh */
110: u8 isSorted; /* True if pEntry is sorted */
111: u8 iBatch; /* Current insert batch */
112: };
113:
114: /*
115: ** Turn bulk memory into a RowSet object. N bytes of memory
116: ** are available at pSpace. The db pointer is used as a memory context
117: ** for any subsequent allocations that need to occur.
118: ** Return a pointer to the new RowSet object.
119: **
120: ** It must be the case that N is sufficient to make a Rowset. If not
121: ** an assertion fault occurs.
122: **
123: ** If N is larger than the minimum, use the surplus as an initial
124: ** allocation of entries available to be filled.
125: */
126: RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){
127: RowSet *p;
128: assert( N >= ROUND8(sizeof(*p)) );
129: p = pSpace;
130: p->pChunk = 0;
131: p->db = db;
132: p->pEntry = 0;
133: p->pLast = 0;
134: p->pTree = 0;
135: p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p);
136: p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry));
137: p->isSorted = 1;
138: p->iBatch = 0;
139: return p;
140: }
141:
142: /*
143: ** Deallocate all chunks from a RowSet. This frees all memory that
144: ** the RowSet has allocated over its lifetime. This routine is
145: ** the destructor for the RowSet.
146: */
147: void sqlite3RowSetClear(RowSet *p){
148: struct RowSetChunk *pChunk, *pNextChunk;
149: for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){
150: pNextChunk = pChunk->pNextChunk;
151: sqlite3DbFree(p->db, pChunk);
152: }
153: p->pChunk = 0;
154: p->nFresh = 0;
155: p->pEntry = 0;
156: p->pLast = 0;
157: p->pTree = 0;
158: p->isSorted = 1;
159: }
160:
161: /*
162: ** Insert a new value into a RowSet.
163: **
164: ** The mallocFailed flag of the database connection is set if a
165: ** memory allocation fails.
166: */
167: void sqlite3RowSetInsert(RowSet *p, i64 rowid){
168: struct RowSetEntry *pEntry; /* The new entry */
169: struct RowSetEntry *pLast; /* The last prior entry */
170: assert( p!=0 );
171: if( p->nFresh==0 ){
172: struct RowSetChunk *pNew;
173: pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew));
174: if( pNew==0 ){
175: return;
176: }
177: pNew->pNextChunk = p->pChunk;
178: p->pChunk = pNew;
179: p->pFresh = pNew->aEntry;
180: p->nFresh = ROWSET_ENTRY_PER_CHUNK;
181: }
182: pEntry = p->pFresh++;
183: p->nFresh--;
184: pEntry->v = rowid;
185: pEntry->pRight = 0;
186: pLast = p->pLast;
187: if( pLast ){
188: if( p->isSorted && rowid<=pLast->v ){
189: p->isSorted = 0;
190: }
191: pLast->pRight = pEntry;
192: }else{
193: assert( p->pEntry==0 ); /* Fires if INSERT after SMALLEST */
194: p->pEntry = pEntry;
195: }
196: p->pLast = pEntry;
197: }
198:
199: /*
200: ** Merge two lists of RowSetEntry objects. Remove duplicates.
201: **
202: ** The input lists are connected via pRight pointers and are
203: ** assumed to each already be in sorted order.
204: */
205: static struct RowSetEntry *rowSetMerge(
206: struct RowSetEntry *pA, /* First sorted list to be merged */
207: struct RowSetEntry *pB /* Second sorted list to be merged */
208: ){
209: struct RowSetEntry head;
210: struct RowSetEntry *pTail;
211:
212: pTail = &head;
213: while( pA && pB ){
214: assert( pA->pRight==0 || pA->v<=pA->pRight->v );
215: assert( pB->pRight==0 || pB->v<=pB->pRight->v );
216: if( pA->v<pB->v ){
217: pTail->pRight = pA;
218: pA = pA->pRight;
219: pTail = pTail->pRight;
220: }else if( pB->v<pA->v ){
221: pTail->pRight = pB;
222: pB = pB->pRight;
223: pTail = pTail->pRight;
224: }else{
225: pA = pA->pRight;
226: }
227: }
228: if( pA ){
229: assert( pA->pRight==0 || pA->v<=pA->pRight->v );
230: pTail->pRight = pA;
231: }else{
232: assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v );
233: pTail->pRight = pB;
234: }
235: return head.pRight;
236: }
237:
238: /*
239: ** Sort all elements on the pEntry list of the RowSet into ascending order.
240: */
241: static void rowSetSort(RowSet *p){
242: unsigned int i;
243: struct RowSetEntry *pEntry;
244: struct RowSetEntry *aBucket[40];
245:
246: assert( p->isSorted==0 );
247: memset(aBucket, 0, sizeof(aBucket));
248: while( p->pEntry ){
249: pEntry = p->pEntry;
250: p->pEntry = pEntry->pRight;
251: pEntry->pRight = 0;
252: for(i=0; aBucket[i]; i++){
253: pEntry = rowSetMerge(aBucket[i], pEntry);
254: aBucket[i] = 0;
255: }
256: aBucket[i] = pEntry;
257: }
258: pEntry = 0;
259: for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
260: pEntry = rowSetMerge(pEntry, aBucket[i]);
261: }
262: p->pEntry = pEntry;
263: p->pLast = 0;
264: p->isSorted = 1;
265: }
266:
267:
268: /*
269: ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
270: ** Convert this tree into a linked list connected by the pRight pointers
271: ** and return pointers to the first and last elements of the new list.
272: */
273: static void rowSetTreeToList(
274: struct RowSetEntry *pIn, /* Root of the input tree */
275: struct RowSetEntry **ppFirst, /* Write head of the output list here */
276: struct RowSetEntry **ppLast /* Write tail of the output list here */
277: ){
278: assert( pIn!=0 );
279: if( pIn->pLeft ){
280: struct RowSetEntry *p;
281: rowSetTreeToList(pIn->pLeft, ppFirst, &p);
282: p->pRight = pIn;
283: }else{
284: *ppFirst = pIn;
285: }
286: if( pIn->pRight ){
287: rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast);
288: }else{
289: *ppLast = pIn;
290: }
291: assert( (*ppLast)->pRight==0 );
292: }
293:
294:
295: /*
296: ** Convert a sorted list of elements (connected by pRight) into a binary
297: ** tree with depth of iDepth. A depth of 1 means the tree contains a single
298: ** node taken from the head of *ppList. A depth of 2 means a tree with
299: ** three nodes. And so forth.
300: **
301: ** Use as many entries from the input list as required and update the
302: ** *ppList to point to the unused elements of the list. If the input
303: ** list contains too few elements, then construct an incomplete tree
304: ** and leave *ppList set to NULL.
305: **
306: ** Return a pointer to the root of the constructed binary tree.
307: */
308: static struct RowSetEntry *rowSetNDeepTree(
309: struct RowSetEntry **ppList,
310: int iDepth
311: ){
312: struct RowSetEntry *p; /* Root of the new tree */
313: struct RowSetEntry *pLeft; /* Left subtree */
314: if( *ppList==0 ){
315: return 0;
316: }
317: if( iDepth==1 ){
318: p = *ppList;
319: *ppList = p->pRight;
320: p->pLeft = p->pRight = 0;
321: return p;
322: }
323: pLeft = rowSetNDeepTree(ppList, iDepth-1);
324: p = *ppList;
325: if( p==0 ){
326: return pLeft;
327: }
328: p->pLeft = pLeft;
329: *ppList = p->pRight;
330: p->pRight = rowSetNDeepTree(ppList, iDepth-1);
331: return p;
332: }
333:
334: /*
335: ** Convert a sorted list of elements into a binary tree. Make the tree
336: ** as deep as it needs to be in order to contain the entire list.
337: */
338: static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){
339: int iDepth; /* Depth of the tree so far */
340: struct RowSetEntry *p; /* Current tree root */
341: struct RowSetEntry *pLeft; /* Left subtree */
342:
343: assert( pList!=0 );
344: p = pList;
345: pList = p->pRight;
346: p->pLeft = p->pRight = 0;
347: for(iDepth=1; pList; iDepth++){
348: pLeft = p;
349: p = pList;
350: pList = p->pRight;
351: p->pLeft = pLeft;
352: p->pRight = rowSetNDeepTree(&pList, iDepth);
353: }
354: return p;
355: }
356:
357: /*
358: ** Convert the list in p->pEntry into a sorted list if it is not
359: ** sorted already. If there is a binary tree on p->pTree, then
360: ** convert it into a list too and merge it into the p->pEntry list.
361: */
362: static void rowSetToList(RowSet *p){
363: if( !p->isSorted ){
364: rowSetSort(p);
365: }
366: if( p->pTree ){
367: struct RowSetEntry *pHead, *pTail;
368: rowSetTreeToList(p->pTree, &pHead, &pTail);
369: p->pTree = 0;
370: p->pEntry = rowSetMerge(p->pEntry, pHead);
371: }
372: }
373:
374: /*
375: ** Extract the smallest element from the RowSet.
376: ** Write the element into *pRowid. Return 1 on success. Return
377: ** 0 if the RowSet is already empty.
378: **
379: ** After this routine has been called, the sqlite3RowSetInsert()
380: ** routine may not be called again.
381: */
382: int sqlite3RowSetNext(RowSet *p, i64 *pRowid){
383: rowSetToList(p);
384: if( p->pEntry ){
385: *pRowid = p->pEntry->v;
386: p->pEntry = p->pEntry->pRight;
387: if( p->pEntry==0 ){
388: sqlite3RowSetClear(p);
389: }
390: return 1;
391: }else{
392: return 0;
393: }
394: }
395:
396: /*
397: ** Check to see if element iRowid was inserted into the the rowset as
398: ** part of any insert batch prior to iBatch. Return 1 or 0.
399: */
400: int sqlite3RowSetTest(RowSet *pRowSet, u8 iBatch, sqlite3_int64 iRowid){
401: struct RowSetEntry *p;
402: if( iBatch!=pRowSet->iBatch ){
403: if( pRowSet->pEntry ){
404: rowSetToList(pRowSet);
405: pRowSet->pTree = rowSetListToTree(pRowSet->pEntry);
406: pRowSet->pEntry = 0;
407: pRowSet->pLast = 0;
408: }
409: pRowSet->iBatch = iBatch;
410: }
411: p = pRowSet->pTree;
412: while( p ){
413: if( p->v<iRowid ){
414: p = p->pRight;
415: }else if( p->v>iRowid ){
416: p = p->pLeft;
417: }else{
418: return 1;
419: }
420: }
421: return 0;
422: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to rowset.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src