third_party/sqlite/sqlite-src-3080704/src/rowset.c

   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.  (Sometimes 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 ** This same object is reused to store a linked list of trees of RowSetEntry
  81 ** objects.  In that alternative use, pRight points to the next entry
  82 ** in the list, pLeft points to the tree, and v is unused.  The
  83 ** RowSet.pForest value points to the head of this forest list.
  84 */
  85 struct RowSetEntry {
  86   i64 v;                        /* ROWID value for this entry */
  87   struct RowSetEntry *pRight;   /* Right subtree (larger entries) or list */
  88   struct RowSetEntry *pLeft;    /* Left subtree (smaller entries) */
  89 };
  90
  91 /*
  92 ** RowSetEntry objects are allocated in large chunks (instances of the
  93 ** following structure) to reduce memory allocation overhead.  The
  94 ** chunks are kept on a linked list so that they can be deallocated
  95 ** when the RowSet is destroyed.
  96 */
  97 struct RowSetChunk {
  98   struct RowSetChunk *pNextChunk;        /* Next chunk on list of them all */
  99   struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */
 100 };
 101
 102 /*
 103 ** A RowSet in an instance of the following structure.
 104 **
 105 ** A typedef of this structure if found in sqliteInt.h.
 106 */
 107 struct RowSet {
 108   struct RowSetChunk *pChunk;    /* List of all chunk allocations */
 109   sqlite3 *db;                   /* The database connection */
 110   struct RowSetEntry *pEntry;    /* List of entries using pRight */
 111   struct RowSetEntry *pLast;     /* Last entry on the pEntry list */
 112   struct RowSetEntry *pFresh;    /* Source of new entry objects */
 113   struct RowSetEntry *pForest;   /* List of binary trees of entries */
 114   u16 nFresh;                    /* Number of objects on pFresh */
 115   u16 rsFlags;                   /* Various flags */
 116   int iBatch;                    /* Current insert batch */
 117 };
 118
 119 /*
 120 ** Allowed values for RowSet.rsFlags
 121 */
 122 #define ROWSET_SORTED  0x01   /* True if RowSet.pEntry is sorted */
 123 #define ROWSET_NEXT    0x02   /* True if sqlite3RowSetNext() has been called */
 124
 125 /*
 126 ** Turn bulk memory into a RowSet object.  N bytes of memory
 127 ** are available at pSpace.  The db pointer is used as a memory context
 128 ** for any subsequent allocations that need to occur.
 129 ** Return a pointer to the new RowSet object.
 130 **
 131 ** It must be the case that N is sufficient to make a Rowset.  If not
 132 ** an assertion fault occurs.
 133 **
 134 ** If N is larger than the minimum, use the surplus as an initial
 135 ** allocation of entries available to be filled.
 136 */
 137 RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){
 138   RowSet *p;
 139   assert( N >= ROUND8(sizeof(*p)) );
 140   p = pSpace;
 141   p->pChunk = 0;
 142   p->db = db;
 143   p->pEntry = 0;
 144   p->pLast = 0;
 145   p->pForest = 0;
 146   p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p);
 147   p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry));
 148   p->rsFlags = ROWSET_SORTED;
 149   p->iBatch = 0;
 150   return p;
 151 }
 152
 153 /*
 154 ** Deallocate all chunks from a RowSet.  This frees all memory that
 155 ** the RowSet has allocated over its lifetime.  This routine is
 156 ** the destructor for the RowSet.
 157 */
 158 void sqlite3RowSetClear(RowSet *p){
 159   struct RowSetChunk *pChunk, *pNextChunk;
 160   for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){
 161     pNextChunk = pChunk->pNextChunk;
 162     sqlite3DbFree(p->db, pChunk);
 163   }
 164   p->pChunk = 0;
 165   p->nFresh = 0;
 166   p->pEntry = 0;
 167   p->pLast = 0;
 168   p->pForest = 0;
 169   p->rsFlags = ROWSET_SORTED;
 170 }
 171
 172 /*
 173 ** Allocate a new RowSetEntry object that is associated with the
 174 ** given RowSet.  Return a pointer to the new and completely uninitialized
 175 ** objected.
 176 **
 177 ** In an OOM situation, the RowSet.db->mallocFailed flag is set and this
 178 ** routine returns NULL.
 179 */
 180 static struct RowSetEntry *rowSetEntryAlloc(RowSet *p){
 181   assert( p!=0 );
 182   if( p->nFresh==0 ){
 183     struct RowSetChunk *pNew;
 184     pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew));
 185     if( pNew==0 ){
 186       return 0;
 187     }
 188     pNew->pNextChunk = p->pChunk;
 189     p->pChunk = pNew;
 190     p->pFresh = pNew->aEntry;
 191     p->nFresh = ROWSET_ENTRY_PER_CHUNK;
 192   }
 193   p->nFresh--;
 194   return p->pFresh++;
 195 }
 196
 197 /*
 198 ** Insert a new value into a RowSet.
 199 **
 200 ** The mallocFailed flag of the database connection is set if a
 201 ** memory allocation fails.
 202 */
 203 void sqlite3RowSetInsert(RowSet *p, i64 rowid){
 204   struct RowSetEntry *pEntry;  /* The new entry */
 205   struct RowSetEntry *pLast;   /* The last prior entry */
 206
 207   /* This routine is never called after sqlite3RowSetNext() */
 208   assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
 209
 210   pEntry = rowSetEntryAlloc(p);
 211   if( pEntry==0 ) return;
 212   pEntry->v = rowid;
 213   pEntry->pRight = 0;
 214   pLast = p->pLast;
 215   if( pLast ){
 216     if( (p->rsFlags & ROWSET_SORTED)!=0 && rowid<=pLast->v ){
 217       p->rsFlags &= ~ROWSET_SORTED;
 218     }
 219     pLast->pRight = pEntry;
 220   }else{
 221     p->pEntry = pEntry;
 222   }
 223   p->pLast = pEntry;
 224 }
 225
 226 /*
 227 ** Merge two lists of RowSetEntry objects.  Remove duplicates.
 228 **
 229 ** The input lists are connected via pRight pointers and are
 230 ** assumed to each already be in sorted order.
 231 */
 232 static struct RowSetEntry *rowSetEntryMerge(
 233   struct RowSetEntry *pA,    /* First sorted list to be merged */
 234   struct RowSetEntry *pB     /* Second sorted list to be merged */
 235 ){
 236   struct RowSetEntry head;
 237   struct RowSetEntry *pTail;
 238
 239   pTail = &head;
 240   while( pA && pB ){
 241     assert( pA->pRight==0 || pA->v<=pA->pRight->v );
 242     assert( pB->pRight==0 || pB->v<=pB->pRight->v );
 243     if( pA->v<pB->v ){
 244       pTail->pRight = pA;
 245       pA = pA->pRight;
 246       pTail = pTail->pRight;
 247     }else if( pB->v<pA->v ){
 248       pTail->pRight = pB;
 249       pB = pB->pRight;
 250       pTail = pTail->pRight;
 251     }else{
 252       pA = pA->pRight;
 253     }
 254   }
 255   if( pA ){
 256     assert( pA->pRight==0 || pA->v<=pA->pRight->v );
 257     pTail->pRight = pA;
 258   }else{
 259     assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v );
 260     pTail->pRight = pB;
 261   }
 262   return head.pRight;
 263 }
 264
 265 /*
 266 ** Sort all elements on the list of RowSetEntry objects into order of
 267 ** increasing v.
 268 */
 269 static struct RowSetEntry *rowSetEntrySort(struct RowSetEntry *pIn){
 270   unsigned int i;
 271   struct RowSetEntry *pNext, *aBucket[40];
 272
 273   memset(aBucket, 0, sizeof(aBucket));
 274   while( pIn ){
 275     pNext = pIn->pRight;
 276     pIn->pRight = 0;
 277     for(i=0; aBucket[i]; i++){
 278       pIn = rowSetEntryMerge(aBucket[i], pIn);
 279       aBucket[i] = 0;
 280     }
 281     aBucket[i] = pIn;
 282     pIn = pNext;
 283   }
 284   pIn = 0;
 285   for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
 286     pIn = rowSetEntryMerge(pIn, aBucket[i]);
 287   }
 288   return pIn;
 289 }
 290
 291
 292 /*
 293 ** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
 294 ** Convert this tree into a linked list connected by the pRight pointers
 295 ** and return pointers to the first and last elements of the new list.
 296 */
 297 static void rowSetTreeToList(
 298   struct RowSetEntry *pIn,         /* Root of the input tree */
 299   struct RowSetEntry **ppFirst,    /* Write head of the output list here */
 300   struct RowSetEntry **ppLast      /* Write tail of the output list here */
 301 ){
 302   assert( pIn!=0 );
 303   if( pIn->pLeft ){
 304     struct RowSetEntry *p;
 305     rowSetTreeToList(pIn->pLeft, ppFirst, &p);
 306     p->pRight = pIn;
 307   }else{
 308     *ppFirst = pIn;
 309   }
 310   if( pIn->pRight ){
 311     rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast);
 312   }else{
 313     *ppLast = pIn;
 314   }
 315   assert( (*ppLast)->pRight==0 );
 316 }
 317
 318
 319 /*
 320 ** Convert a sorted list of elements (connected by pRight) into a binary
 321 ** tree with depth of iDepth.  A depth of 1 means the tree contains a single
 322 ** node taken from the head of *ppList.  A depth of 2 means a tree with
 323 ** three nodes.  And so forth.
 324 **
 325 ** Use as many entries from the input list as required and update the
 326 ** *ppList to point to the unused elements of the list.  If the input
 327 ** list contains too few elements, then construct an incomplete tree
 328 ** and leave *ppList set to NULL.
 329 **
 330 ** Return a pointer to the root of the constructed binary tree.
 331 */
 332 static struct RowSetEntry *rowSetNDeepTree(
 333   struct RowSetEntry **ppList,
 334   int iDepth
 335 ){
 336   struct RowSetEntry *p;         /* Root of the new tree */
 337   struct RowSetEntry *pLeft;     /* Left subtree */
 338   if( *ppList==0 ){
 339     return 0;
 340   }
 341   if( iDepth==1 ){
 342     p = *ppList;
 343     *ppList = p->pRight;
 344     p->pLeft = p->pRight = 0;
 345     return p;
 346   }
 347   pLeft = rowSetNDeepTree(ppList, iDepth-1);
 348   p = *ppList;
 349   if( p==0 ){
 350     return pLeft;
 351   }
 352   p->pLeft = pLeft;
 353   *ppList = p->pRight;
 354   p->pRight = rowSetNDeepTree(ppList, iDepth-1);
 355   return p;
 356 }
 357
 358 /*
 359 ** Convert a sorted list of elements into a binary tree. Make the tree
 360 ** as deep as it needs to be in order to contain the entire list.
 361 */
 362 static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){
 363   int iDepth;           /* Depth of the tree so far */
 364   struct RowSetEntry *p;       /* Current tree root */
 365   struct RowSetEntry *pLeft;   /* Left subtree */
 366
 367   assert( pList!=0 );
 368   p = pList;
 369   pList = p->pRight;
 370   p->pLeft = p->pRight = 0;
 371   for(iDepth=1; pList; iDepth++){
 372     pLeft = p;
 373     p = pList;
 374     pList = p->pRight;
 375     p->pLeft = pLeft;
 376     p->pRight = rowSetNDeepTree(&pList, iDepth);
 377   }
 378   return p;
 379 }
 380
 381 /*
 382 ** Take all the entries on p->pEntry and on the trees in p->pForest and
 383 ** sort them all together into one big ordered list on p->pEntry.
 384 **
 385 ** This routine should only be called once in the life of a RowSet.
 386 */
 387 static void rowSetToList(RowSet *p){
 388
 389   /* This routine is called only once */
 390   assert( p!=0 && (p->rsFlags & ROWSET_NEXT)==0 );
 391
 392   if( (p->rsFlags & ROWSET_SORTED)==0 ){
 393     p->pEntry = rowSetEntrySort(p->pEntry);
 394   }
 395
 396   /* While this module could theoretically support it, sqlite3RowSetNext()
 397   ** is never called after sqlite3RowSetText() for the same RowSet.  So
 398   ** there is never a forest to deal with.  Should this change, simply
 399   ** remove the assert() and the #if 0. */
 400   assert( p->pForest==0 );
 401 #if 0
 402   while( p->pForest ){
 403     struct RowSetEntry *pTree = p->pForest->pLeft;
 404     if( pTree ){
 405       struct RowSetEntry *pHead, *pTail;
 406       rowSetTreeToList(pTree, &pHead, &pTail);
 407       p->pEntry = rowSetEntryMerge(p->pEntry, pHead);
 408     }
 409     p->pForest = p->pForest->pRight;
 410   }
 411 #endif
 412   p->rsFlags |= ROWSET_NEXT;  /* Verify this routine is never called again */
 413 }
 414
 415 /*
 416 ** Extract the smallest element from the RowSet.
 417 ** Write the element into *pRowid.  Return 1 on success.  Return
 418 ** 0 if the RowSet is already empty.
 419 **
 420 ** After this routine has been called, the sqlite3RowSetInsert()
 421 ** routine may not be called again.
 422 */
 423 int sqlite3RowSetNext(RowSet *p, i64 *pRowid){
 424   assert( p!=0 );
 425
 426   /* Merge the forest into a single sorted list on first call */
 427   if( (p->rsFlags & ROWSET_NEXT)==0 ) rowSetToList(p);
 428
 429   /* Return the next entry on the list */
 430   if( p->pEntry ){
 431     *pRowid = p->pEntry->v;
 432     p->pEntry = p->pEntry->pRight;
 433     if( p->pEntry==0 ){
 434       sqlite3RowSetClear(p);
 435     }
 436     return 1;
 437   }else{
 438     return 0;
 439   }
 440 }
 441
 442 /*
 443 ** Check to see if element iRowid was inserted into the rowset as
 444 ** part of any insert batch prior to iBatch.  Return 1 or 0.
 445 **
 446 ** If this is the first test of a new batch and if there exist entries
 447 ** on pRowSet->pEntry, then sort those entries into the forest at
 448 ** pRowSet->pForest so that they can be tested.
 449 */
 450 int sqlite3RowSetTest(RowSet *pRowSet, int iBatch, sqlite3_int64 iRowid){
 451   struct RowSetEntry *p, *pTree;
 452
 453   /* This routine is never called after sqlite3RowSetNext() */
 454   assert( pRowSet!=0 && (pRowSet->rsFlags & ROWSET_NEXT)==0 );
 455
 456   /* Sort entries into the forest on the first test of a new batch
 457   */
 458   if( iBatch!=pRowSet->iBatch ){
 459     p = pRowSet->pEntry;
 460     if( p ){
 461       struct RowSetEntry **ppPrevTree = &pRowSet->pForest;
 462       if( (pRowSet->rsFlags & ROWSET_SORTED)==0 ){
 463         p = rowSetEntrySort(p);
 464       }
 465       for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){
 466         ppPrevTree = &pTree->pRight;
 467         if( pTree->pLeft==0 ){
 468           pTree->pLeft = rowSetListToTree(p);
 469           break;
 470         }else{
 471           struct RowSetEntry *pAux, *pTail;
 472           rowSetTreeToList(pTree->pLeft, &pAux, &pTail);
 473           pTree->pLeft = 0;
 474           p = rowSetEntryMerge(pAux, p);
 475         }
 476       }
 477       if( pTree==0 ){
 478         *ppPrevTree = pTree = rowSetEntryAlloc(pRowSet);
 479         if( pTree ){
 480           pTree->v = 0;
 481           pTree->pRight = 0;
 482           pTree->pLeft = rowSetListToTree(p);
 483         }
 484       }
 485       pRowSet->pEntry = 0;
 486       pRowSet->pLast = 0;
 487       pRowSet->rsFlags |= ROWSET_SORTED;
 488     }
 489     pRowSet->iBatch = iBatch;
 490   }
 491
 492   /* Test to see if the iRowid value appears anywhere in the forest.
 493   ** Return 1 if it does and 0 if not.
 494   */
 495   for(pTree = pRowSet->pForest; pTree; pTree=pTree->pRight){
 496     p = pTree->pLeft;
 497     while( p ){
 498       if( p->v<iRowid ){
 499         p = p->pRight;
 500       }else if( p->v>iRowid ){
 501         p = p->pLeft;
 502       }else{
 503         return 1;
 504       }
 505     }
 506   }
 507   return 0;
 508 }