Annotation of embedaddon/sqlite3/src/rowset.c, revision 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