/*

** 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 "RowSet".

**

** The RowSet object is a collection of rowids.  Rowids

** are inserted into the RowSet in an arbitrary order.  Inserts

** can be intermixed with tests to see if a given rowid has been

** previously inserted into the RowSet.

**

** After all inserts are finished, it is possible to extract the

** elements of the RowSet in sorted order.  Once this extraction

** process has started, no new elements may be inserted.

**

** Hence, the primitive operations for a RowSet are:

**

**    CREATE

**    INSERT

**    TEST

**    SMALLEST

**    DESTROY

**

** The CREATE and DESTROY primitives are the constructor and destructor,

** obviously.  The INSERT primitive adds a new element to the RowSet.

** TEST checks to see if an element is already in the RowSet.  SMALLEST

** extracts the least value from the RowSet.

**

** The INSERT primitive might allocate additional memory.  Memory is

** allocated in chunks so most INSERTs do no allocation.  There is an

** upper bound on the size of allocated memory.  No memory is freed

** until DESTROY.

**

** The TEST primitive includes a "batch" number.  The TEST primitive

** will only see elements that were inserted before the last change

** in the batch number.  In other words, if an INSERT occurs between

** two TESTs where the TESTs have the same batch number, then the

** value added by the INSERT will not be visible to the second TEST.

** The initial batch number is zero, so if the very first TEST contains

** a non-zero batch number, it will see all prior INSERTs.

**

** No INSERTs may occurs after a SMALLEST.  An assertion will fail if

** that is attempted.

**

** The cost of an INSERT is roughly constant.  (Sometimes new memory

** has to be allocated on an INSERT.)  The cost of a TEST with a new

** batch number is O(NlogN) where N is the number of elements in the RowSet.

** The cost of a TEST using the same batch number is O(logN).  The cost

** of the first SMALLEST is O(NlogN).  Second and subsequent SMALLEST

** primitives are constant time.  The cost of DESTROY is O(N).

**

** TEST and SMALLEST may not be used by the same RowSet.  This used to

** be possible, but the feature was not used, so it was removed in order

** to simplify the code.

*/

#include "sqliteInt.h"

/*

** Target size for allocation chunks.

*/

#define ROWSET_ALLOCATION_SIZE 1024

/*

** The number of rowset entries per allocation chunk.

*/

#define ROWSET_ENTRY_PER_CHUNK  \

                       ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry))

/*

** Each entry in a RowSet is an instance of the following object.

**

** This same object is reused to store a linked list of trees of RowSetEntry

** objects.  In that alternative use, pRight points to the next entry

** in the list, pLeft points to the tree, and v is unused.  The

** RowSet.pForest value points to the head of this forest list.

*/

struct RowSetEntry {           

  i64 v;                        /* ROWID value for this entry */

  struct RowSetEntry *pRight;   /* Right subtree (larger entries) or list */

  struct RowSetEntry *pLeft;    /* Left subtree (smaller entries) */

};

/*

** RowSetEntry objects 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 *pNextChunk;        /* 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 using pRight */

  struct RowSetEntry *pLast;     /* Last entry on the pEntry list */

  struct RowSetEntry *pFresh;    /* Source of new entry objects */

  struct RowSetEntry *pForest;   /* List of binary trees of entries */

  u16 nFresh;                    /* Number of objects on pFresh */

  u16 rsFlags;                   /* Various flags */

  int iBatch;                    /* Current insert batch */

};

/*

** Allowed values for RowSet.rsFlags

*/

#define ROWSET_SORTED  0x01   /* True if RowSet.pEntry is sorted */

#define ROWSET_NEXT    0x02   /* True if sqlite3RowSetNext() has been called */

/*

** Allocate a RowSet object.  Return NULL if a memory allocation

** error occurs.

*/

RowSet *sqlite3RowSetInit(sqlite3 *db){

  RowSet *p = sqlite3DbMallocRawNN(db, sizeof(*p));

  if( p ){

    int N = sqlite3DbMallocSize(db, p);

    p->pChunk = 0;

    p->db = db;

    p->pEntry = 0;

    p->pLast = 0;

    p->pForest = 0;

    p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p);

    p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry));

    p->rsFlags = ROWSET_SORTED;

    p->iBatch = 0;

  }

  return p;

}

/*

** Deallocate all chunks from a RowSet.  This frees all memory that

** the RowSet has allocated over its lifetime.  This routine is

** the destructor for the RowSet.

*/

void sqlite3RowSetClear(void *pArg){

  RowSet *p = (RowSet*)pArg;

  struct RowSetChunk *pChunk, *pNextChunk;

  for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){

    pNextChunk = pChunk->pNextChunk;

    sqlite3DbFree(p->db, pChunk);

  }

  p->pChunk = 0;

  p->nFresh = 0;

  p->pEntry = 0;

  p->pLast = 0;

  p->pForest = 0;

  p->rsFlags = ROWSET_SORTED;

}

/*

** Deallocate all chunks from a RowSet.  This frees all memory that

** the RowSet has allocated over its lifetime.  This routine is

** the destructor for the RowSet.

*/

void sqlite3RowSetDelete(void *pArg){

  sqlite3RowSetClear(pArg);

  sqlite3DbFree(((RowSet*)pArg)->db, pArg);

}

/*

** Allocate a new RowSetEntry object that is associated with the

** given RowSet.  Return a pointer to the new and completely uninitialized

** object.

**

** In an OOM situation, the RowSet.db->mallocFailed flag is set and this

** routine returns NULL.

*/

static struct RowSetEntry *rowSetEntryAlloc(RowSet *p){

  assert( p!=0 );

  if( p->nFresh==0 ){  /*OPTIMIZATION-IF-FALSE*/

    /* We could allocate a fresh RowSetEntry each time one is needed, but it

    ** is more efficient to pull a preallocated entry from the pool */

    struct RowSetChunk *pNew;

    pNew = sqlite3DbMallocRawNN(p->db, sizeof(*pNew));

    if( pNew==0 ){

      return 0;

    }

    pNew->pNextChunk = p->pChunk;

    p->pChunk = pNew;

    p->pFresh = pNew->aEntry;

    p->nFresh = ROWSET_ENTRY_PER_CHUNK;

  }

  p->nFresh--;

  return p->pFresh++;

}

/*

** 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;  /* The new entry */

  struct RowSetEntry *pLast;   /* The last prior entry */

  /* This routine is never called after sqlite3RowSetNext() */

  assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );

  pEntry = rowSetEntryAlloc(p);

  if( pEntry==0 ) return;

  pEntry->v = rowid;

  pEntry->pRight = 0;

  pLast = p->pLast;

  if( pLast ){

    if( rowid<=pLast->v ){  /*OPTIMIZATION-IF-FALSE*/

      /* Avoid unnecessary sorts by preserving the ROWSET_SORTED flags

      ** where possible */

      p->rsFlags &= ~ROWSET_SORTED;

    }

    pLast->pRight = pEntry;

  }else{

    p->pEntry = pEntry;

  }

  p->pLast = pEntry;

}

/*

** Merge two lists of RowSetEntry objects.  Remove duplicates.

**

** The input lists are connected via pRight pointers and are

** assumed to each already be in sorted order.

*/

static struct RowSetEntry *rowSetEntryMerge(

  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;

  assert( pA!=0 && pB!=0 );

  for(;;){

    assert( pA->pRight==0 || pA->v<=pA->pRight->v );

    assert( pB->pRight==0 || pB->v<=pB->pRight->v );

    if( pA->v<=pB->v ){

      if( pA->v<pB->v ) pTail = pTail->pRight = pA;

      pA = pA->pRight;

      if( pA==0 ){

        pTail->pRight = pB;

        break;

      }

    }else{

      pTail = pTail->pRight = pB;

      pB = pB->pRight;

      if( pB==0 ){

        pTail->pRight = pA;

        break;

      }

    }

  }

  return head.pRight;

}

/*

** Sort all elements on the list of RowSetEntry objects into order of

** increasing v.

*/

static struct RowSetEntry *rowSetEntrySort(struct RowSetEntry *pIn){

  unsigned int i;

  struct RowSetEntry *pNext, *aBucket[40];

  memset(aBucket, 0, sizeof(aBucket));

  while( pIn ){

    pNext = pIn->pRight;

    pIn->pRight = 0;

    for(i=0; aBucket[i]; i++){

      pIn = rowSetEntryMerge(aBucket[i], pIn);

      aBucket[i] = 0;

    }

    aBucket[i] = pIn;

    pIn = pNext;

  }

  pIn = aBucket[0];

  for(i=1; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){

    if( aBucket[i]==0 ) continue;

    pIn = pIn ? rowSetEntryMerge(pIn, aBucket[i]) : aBucket[i];

  }

  return pIn;

}

/*

** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.

** Convert this tree into a linked list connected by the pRight pointers

** and return pointers to the first and last elements of the new list.

*/

static void rowSetTreeToList(

  struct RowSetEntry *pIn,         /* Root of the input tree */

  struct RowSetEntry **ppFirst,    /* Write head of the output list here */

  struct RowSetEntry **ppLast      /* Write tail of the output list here */

){

  assert( pIn!=0 );

  if( pIn->pLeft ){

    struct RowSetEntry *p;

    rowSetTreeToList(pIn->pLeft, ppFirst, &p);

    p->pRight = pIn;

  }else{

    *ppFirst = pIn;

  }

  if( pIn->pRight ){

    rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast);

  }else{

    *ppLast = pIn;

  }

  assert( (*ppLast)->pRight==0 );

}

/*

** Convert a sorted list of elements (connected by pRight) into a binary

** tree with depth of iDepth.  A depth of 1 means the tree contains a single

** node taken from the head of *ppList.  A depth of 2 means a tree with

** three nodes.  And so forth.

**

** Use as many entries from the input list as required and update the

** *ppList to point to the unused elements of the list.  If the input

** list contains too few elements, then construct an incomplete tree

** and leave *ppList set to NULL.

**

** Return a pointer to the root of the constructed binary tree.

*/

static struct RowSetEntry *rowSetNDeepTree(

  struct RowSetEntry **ppList,

  int iDepth

){

  struct RowSetEntry *p;         /* Root of the new tree */

  struct RowSetEntry *pLeft;     /* Left subtree */

  if( *ppList==0 ){ /*OPTIMIZATION-IF-TRUE*/

    /* Prevent unnecessary deep recursion when we run out of entries */

    return 0;

  }

  if( iDepth>1 ){   /*OPTIMIZATION-IF-TRUE*/

    /* This branch causes a *balanced* tree to be generated.  A valid tree

    ** is still generated without this branch, but the tree is wildly

    ** unbalanced and inefficient. */

    pLeft = rowSetNDeepTree(ppList, iDepth-1);

    p = *ppList;

    if( p==0 ){     /*OPTIMIZATION-IF-FALSE*/

      /* It is safe to always return here, but the resulting tree

      ** would be unbalanced */

      return pLeft;

    }

    p->pLeft = pLeft;

    *ppList = p->pRight;

    p->pRight = rowSetNDeepTree(ppList, iDepth-1);

  }else{

    p = *ppList;

    *ppList = p->pRight;

    p->pLeft = p->pRight = 0;

  }

  return p;

}

/*

** Convert a sorted list of elements into a binary tree. Make the tree

** as deep as it needs to be in order to contain the entire list.

*/

static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){

  int iDepth;           /* Depth of the tree so far */

  struct RowSetEntry *p;       /* Current tree root */

  struct RowSetEntry *pLeft;   /* Left subtree */

  assert( pList!=0 );

  p = pList;

  pList = p->pRight;

  p->pLeft = p->pRight = 0;

  for(iDepth=1; pList; iDepth++){

    pLeft = p;

    p = pList;

    pList = p->pRight;

    p->pLeft = pLeft;

    p->pRight = rowSetNDeepTree(&pList, iDepth);

  }

  return p;

}

/*

** Extract the smallest element from the RowSet.

** Write the element into *pRowid.  Return 1 on success.  Return

** 0 if the RowSet is already empty.

**

** After this routine has been called, the sqlite3RowSetInsert()

** routine may not be called again.

**

** This routine may not be called after sqlite3RowSetTest() has

** been used.  Older versions of RowSet allowed that, but as the

** capability was not used by the code generator, it was removed

** for code economy.

*/

int sqlite3RowSetNext(RowSet *p, i64 *pRowid){

  assert( p!=0 );

  assert( p->pForest==0 );  /* Cannot be used with sqlite3RowSetText() */

  /* Merge the forest into a single sorted list on first call */

  if( (p->rsFlags & ROWSET_NEXT)==0 ){  /*OPTIMIZATION-IF-FALSE*/

    if( (p->rsFlags & ROWSET_SORTED)==0 ){  /*OPTIMIZATION-IF-FALSE*/

      p->pEntry = rowSetEntrySort(p->pEntry);

    }

    p->rsFlags |= ROWSET_SORTED|ROWSET_NEXT;

  }

  /* Return the next entry on the list */

  if( p->pEntry ){

    *pRowid = p->pEntry->v;

    p->pEntry = p->pEntry->pRight;

    if( p->pEntry==0 ){ /*OPTIMIZATION-IF-TRUE*/

      /* Free memory immediately, rather than waiting on sqlite3_finalize() */

      sqlite3RowSetClear(p);

    }

    return 1;

  }else{

    return 0;

  }

}

/*

** Check to see if element iRowid was inserted into the rowset as

** part of any insert batch prior to iBatch.  Return 1 or 0.

**

** If this is the first test of a new batch and if there exist entries

** on pRowSet->pEntry, then sort those entries into the forest at

** pRowSet->pForest so that they can be tested.

*/

int sqlite3RowSetTest(RowSet *pRowSet, int iBatch, sqlite3_int64 iRowid){

  struct RowSetEntry *p, *pTree;

  /* This routine is never called after sqlite3RowSetNext() */

  assert( pRowSet!=0 && (pRowSet->rsFlags & ROWSET_NEXT)==0 );

  /* Sort entries into the forest on the first test of a new batch.

  ** To save unnecessary work, only do this when the batch number changes.

  */

  if( iBatch!=pRowSet->iBatch ){  /*OPTIMIZATION-IF-FALSE*/

    p = pRowSet->pEntry;

    if( p ){

      struct RowSetEntry **ppPrevTree = &pRowSet->pForest;

      if( (pRowSet->rsFlags & ROWSET_SORTED)==0 ){ /*OPTIMIZATION-IF-FALSE*/

        /* Only sort the current set of entries if they need it */

        p = rowSetEntrySort(p);

      }

      for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){

        ppPrevTree = &pTree->pRight;

        if( pTree->pLeft==0 ){

          pTree->pLeft = rowSetListToTree(p);

          break;

        }else{

          struct RowSetEntry *pAux, *pTail;

          rowSetTreeToList(pTree->pLeft, &pAux, &pTail);

          pTree->pLeft = 0;

          p = rowSetEntryMerge(pAux, p);

        }

      }

      if( pTree==0 ){

        *ppPrevTree = pTree = rowSetEntryAlloc(pRowSet);

        if( pTree ){

          pTree->v = 0;

          pTree->pRight = 0;

          pTree->pLeft = rowSetListToTree(p);

        }

      }

      pRowSet->pEntry = 0;

      pRowSet->pLast = 0;

      pRowSet->rsFlags |= ROWSET_SORTED;

    }

    pRowSet->iBatch = iBatch;

  }

  /* Test to see if the iRowid value appears anywhere in the forest.

  ** Return 1 if it does and 0 if not.

  */

  for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){

    p = pTree->pLeft;

    while( p ){

      if( p->v<iRowid ){

        p = p->pRight;

      }else if( p->v>iRowid ){

        p = p->pLeft;

      }else{

        return 1;

      }

    }

  }

  return 0;

}