Replace the VDBE Fifo object with the new RowSet object. (CVS 5977)

FossilOrigin-Name: 39a0750b49cf55e9c0927169ca47db909f5c16ea

1 files changed, 238 insertions, 0 deletions

diff --git a/src/rowset.c b/src/rowset.c
new file mode 100644
index 000000000..2be962759
--- /dev/null
+++ b/src/rowset.c
@@ -0,0 +1,238 @@
+/*
+** 2008 December 3
+**
+** The author disclaims copyright to this source code.  In place of
+** a legal notice, here is a blessing:
+**
+**    May you do good and not evil.
+**    May you find forgiveness for yourself and forgive others.
+**    May you share freely, never taking more than you give.
+**
+*************************************************************************
+**
+** This module implements an object we call a "Row Set".
+**
+** The RowSet object is a bag of rowids.  Rowids
+** are inserted into the bag in an arbitrary order.  Then they are
+** pulled from the bag in sorted order.  Rowids only appear in the
+** bag once.  If the same rowid is inserted multiple times, the
+** second and subsequent inserts make no difference on the output.
+**
+** This implementation accumulates rowids in a linked list.  For
+** output, it first sorts the linked list (removing duplicates during
+** the sort) then returns elements one by one by walking the list.
+**
+** Big chunks of rowid/next-ptr pairs are allocated at a time, to
+** reduce the malloc overhead.
+*/
+#include "sqliteInt.h"
+
+/*
+** The number of rowset entries per allocation chunk.
+*/
+#define ROWSET_ENTRY_PER_CHUNK  63
+
+/*
+** Each entry in a RowSet is an instance of the following
+** structure:
+*/
+struct RowSetEntry {            
+  i64 v;                        /* ROWID value for this entry */
+  struct RowSetEntry *pNext;    /* Next entry on a list of all entries */
+};
+
+/*
+** Index entries are allocated in large chunks (instances of the
+** following structure) to reduce memory allocation overhead.  The
+** chunks are kept on a linked list so that they can be deallocated
+** when the RowSet is destroyed.
+*/
+struct RowSetChunk {
+  struct RowSetChunk *pNext;             /* Next chunk on list of them all */
+  struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */
+};
+
+/*
+** A RowSet in an instance of the following structure.
+**
+** A typedef of this structure if found in sqliteInt.h.
+*/
+struct RowSet {
+  struct RowSetChunk *pChunk;    /* List of all chunk allocations */
+  sqlite3 *db;                   /* The database connection */
+  struct RowSetEntry *pEntry;    /* List of entries in the rowset */
+  struct RowSetEntry *pLast;     /* Last entry on the pEntry list */
+  struct RowSetEntry *pFresh;    /* Source of new entry objects */
+  u16 nFresh;                    /* Number of objects on pFresh */
+  u8 isSorted;                   /* True if content is sorted */
+};
+
+/*
+** Turn bulk memory into a RowSet object.  N bytes of memory
+** are available at pSpace.  The db pointer is used as a memory context
+** for any subsequent allocations that need to occur.
+** Return a pointer to the new RowSet object.
+**
+** If N is not sufficient memory to make even a minimum RowSet,
+** then return NULL.  If N is larger than the minimum, use
+** the surplus as an initial allocation of entries available to
+** be filled.
+*/
+RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){
+  RowSet *p;
+  if( N<sizeof(*p) ){
+    p = 0;
+  }else{
+    p = pSpace;
+    p->pChunk = 0;
+    p->db = db;
+    p->pEntry = 0;
+    p->pLast = 0;
+    p->pFresh = (struct RowSetEntry*)&p[1];
+    p->nFresh = (u16)((N - sizeof(*p))/sizeof(struct RowSetEntry));
+    p->isSorted = 1;
+  }
+  return p;
+}
+
+/*
+** Deallocate all chunks from a RowSet.
+*/
+void sqlite3RowSetClear(RowSet *p){
+  struct RowSetChunk *pChunk, *pNextChunk;
+  for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){
+    pNextChunk = pChunk->pNext;
+    sqlite3DbFree(p->db, pChunk);
+  }
+  p->pChunk = 0;
+  p->nFresh = 0;
+  p->pEntry = 0;
+  p->pLast = 0;
+  p->isSorted = 1;
+}
+
+/*
+** Insert a new value into a RowSet.
+**
+** The mallocFailed flag of the database connection is set if a
+** memory allocation fails.
+*/
+void sqlite3RowSetInsert(RowSet *p, i64 rowid){
+  struct RowSetEntry *pEntry;
+  struct RowSetEntry *pLast;
+  if( p==0 ) return;  /* Must have been a malloc failure */
+  if( p->nFresh==0 ){
+    struct RowSetChunk *pNew;
+    pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew));
+    if( pNew==0 ){
+      return;
+    }
+    pNew->pNext = p->pChunk;
+    p->pChunk = pNew;
+    p->pFresh = pNew->aEntry;
+    p->nFresh = ROWSET_ENTRY_PER_CHUNK;
+  }
+  pEntry = p->pFresh++;
+  p->nFresh--;
+  pEntry->v = rowid;
+  pEntry->pNext = 0;
+  pLast = p->pLast;
+  if( pLast ){
+    if( p->isSorted && rowid<=pLast->v ){
+      p->isSorted = 0;
+    }
+    pLast->pNext = pEntry;
+  }else{
+    assert( p->pEntry==0 );
+    p->pEntry = pEntry;
+  }
+  p->pLast = pEntry;
+}
+
+/*
+** Merge two lists of RowSet entries.  Remove duplicates.
+**
+** The input lists are assumed to be in sorted order.
+*/
+static struct RowSetEntry *boolidxMerge(
+  struct RowSetEntry *pA,    /* First sorted list to be merged */
+  struct RowSetEntry *pB     /* Second sorted list to be merged */
+){
+  struct RowSetEntry head;
+  struct RowSetEntry *pTail;
+
+  pTail = &head;
+  while( pA && pB ){
+    assert( pA->pNext==0 || pA->v<=pA->pNext->v );
+    assert( pB->pNext==0 || pB->v<=pB->pNext->v );
+    if( pA->v<pB->v ){
+      pTail->pNext = pA;
+      pA = pA->pNext;
+      pTail = pTail->pNext;
+    }else if( pB->v<pA->v ){
+      pTail->pNext = pB;
+      pB = pB->pNext;
+      pTail = pTail->pNext;
+    }else{
+      pA = pA->pNext;
+    }
+  }
+  if( pA ){
+    assert( pA->pNext==0 || pA->v<=pA->pNext->v );
+    pTail->pNext = pA;
+  }else{
+    assert( pB==0 || pB->pNext==0 || pB->v<=pB->pNext->v );
+    pTail->pNext = pB;
+  }
+  return head.pNext;
+}
+
+/*
+** Sort all elements of the RowSet into ascending order.
+*/ 
+static void sqlite3RowSetSort(RowSet *p){
+  unsigned int i;
+  struct RowSetEntry *pEntry;
+  struct RowSetEntry *aBucket[40];
+
+  assert( p->isSorted==0 );
+  memset(aBucket, 0, sizeof(aBucket));
+  while( p->pEntry ){
+    pEntry = p->pEntry;
+    p->pEntry = pEntry->pNext;
+    pEntry->pNext = 0;
+    for(i=0; aBucket[i]; i++){
+      pEntry = boolidxMerge(aBucket[i],pEntry);
+      aBucket[i] = 0;
+    }
+    aBucket[i] = pEntry;
+  }
+  pEntry = 0;
+  for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
+    pEntry = boolidxMerge(pEntry,aBucket[i]);
+  }
+  p->pEntry = pEntry;
+  p->pLast = 0;
+  p->isSorted = 1;
+}
+
+/*
+** Extract the next (smallest) element from the RowSet.
+** Write the element into *pRowid.  Return 1 on success.  Return
+** 0 if the RowSet is already empty.
+*/
+int sqlite3RowSetNext(RowSet *p, i64 *pRowid){
+  if( !p->isSorted ){
+    sqlite3RowSetSort(p);
+  }
+  if( p->pEntry ){
+    *pRowid = p->pEntry->v;
+    p->pEntry = p->pEntry->pNext;
+    if( p->pEntry==0 ){
+      sqlite3RowSetClear(p);
+    }
+    return 1;
+  }else{
+    return 0;
+  }
+}