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*/
80struct 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*/
92struct 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*/
102struct 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*/
126RowSet *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*/
147void 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*/
167void 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*/
205static 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*/
241static 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*/
273static 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*/
308static 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*/
338static 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*/
362static 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*/
382int 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*/
400int 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}
423