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 "Row Set". 14 ** 15 ** The RowSet object is a bag of rowids. Rowids 16 ** are inserted into the bag in an arbitrary order. Then they are 17 ** pulled from the bag in sorted order. Rowids only appear in the 18 ** bag once. If the same rowid is inserted multiple times, the 19 ** second and subsequent inserts make no difference on the output. 20 ** 21 ** This implementation accumulates rowids in a linked list. For 22 ** output, it first sorts the linked list (removing duplicates during 23 ** the sort) then returns elements one by one by walking the list. 24 ** 25 ** Big chunks of rowid/next-ptr pairs are allocated at a time, to 26 ** reduce the malloc overhead. 27 */ 28 #include "sqliteInt.h" 29 30 /* 31 ** The number of rowset entries per allocation chunk. 32 */ 33 #define ROWSET_ENTRY_PER_CHUNK 63 34 35 /* 36 ** Each entry in a RowSet is an instance of the following 37 ** structure: 38 */ 39 struct RowSetEntry { 40 i64 v; /* ROWID value for this entry */ 41 struct RowSetEntry *pNext; /* Next entry on a list of all entries */ 42 }; 43 44 /* 45 ** Index entries are allocated in large chunks (instances of the 46 ** following structure) to reduce memory allocation overhead. The 47 ** chunks are kept on a linked list so that they can be deallocated 48 ** when the RowSet is destroyed. 49 */ 50 struct RowSetChunk { 51 struct RowSetChunk *pNext; /* Next chunk on list of them all */ 52 struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */ 53 }; 54 55 /* 56 ** A RowSet in an instance of the following structure. 57 ** 58 ** A typedef of this structure if found in sqliteInt.h. 59 */ 60 struct RowSet { 61 struct RowSetChunk *pChunk; /* List of all chunk allocations */ 62 sqlite3 *db; /* The database connection */ 63 struct RowSetEntry *pEntry; /* List of entries in the rowset */ 64 struct RowSetEntry *pLast; /* Last entry on the pEntry list */ 65 struct RowSetEntry *pFresh; /* Source of new entry objects */ 66 u16 nFresh; /* Number of objects on pFresh */ 67 u8 isSorted; /* True if content is sorted */ 68 }; 69 70 /* 71 ** Turn bulk memory into a RowSet object. N bytes of memory 72 ** are available at pSpace. The db pointer is used as a memory context 73 ** for any subsequent allocations that need to occur. 74 ** Return a pointer to the new RowSet object. 75 ** 76 ** If N is not sufficient memory to make even a minimum RowSet, 77 ** then return NULL. If N is larger than the minimum, use 78 ** the surplus as an initial allocation of entries available to 79 ** be filled. 80 */ 81 RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){ 82 RowSet *p; 83 if( N<sizeof(*p) ){ 84 p = 0; 85 }else{ 86 p = pSpace; 87 p->pChunk = 0; 88 p->db = db; 89 p->pEntry = 0; 90 p->pLast = 0; 91 p->pFresh = (struct RowSetEntry*)&p[1]; 92 p->nFresh = (u16)((N - sizeof(*p))/sizeof(struct RowSetEntry)); 93 p->isSorted = 1; 94 } 95 return p; 96 } 97 98 /* 99 ** Deallocate all chunks from a RowSet. 100 */ 101 void sqlite3RowSetClear(RowSet *p){ 102 struct RowSetChunk *pChunk, *pNextChunk; 103 for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){ 104 pNextChunk = pChunk->pNext; 105 sqlite3DbFree(p->db, pChunk); 106 } 107 p->pChunk = 0; 108 p->nFresh = 0; 109 p->pEntry = 0; 110 p->pLast = 0; 111 p->isSorted = 1; 112 } 113 114 /* 115 ** Insert a new value into a RowSet. 116 ** 117 ** The mallocFailed flag of the database connection is set if a 118 ** memory allocation fails. 119 */ 120 void sqlite3RowSetInsert(RowSet *p, i64 rowid){ 121 struct RowSetEntry *pEntry; 122 struct RowSetEntry *pLast; 123 if( p==0 ) return; /* Must have been a malloc failure */ 124 if( p->nFresh==0 ){ 125 struct RowSetChunk *pNew; 126 pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew)); 127 if( pNew==0 ){ 128 return; 129 } 130 pNew->pNext = p->pChunk; 131 p->pChunk = pNew; 132 p->pFresh = pNew->aEntry; 133 p->nFresh = ROWSET_ENTRY_PER_CHUNK; 134 } 135 pEntry = p->pFresh++; 136 p->nFresh--; 137 pEntry->v = rowid; 138 pEntry->pNext = 0; 139 pLast = p->pLast; 140 if( pLast ){ 141 if( p->isSorted && rowid<=pLast->v ){ 142 p->isSorted = 0; 143 } 144 pLast->pNext = pEntry; 145 }else{ 146 assert( p->pEntry==0 ); 147 p->pEntry = pEntry; 148 } 149 p->pLast = pEntry; 150 } 151 152 /* 153 ** Merge two lists of RowSet entries. Remove duplicates. 154 ** 155 ** The input lists are assumed to be in sorted order. 156 */ 157 static struct RowSetEntry *boolidxMerge( 158 struct RowSetEntry *pA, /* First sorted list to be merged */ 159 struct RowSetEntry *pB /* Second sorted list to be merged */ 160 ){ 161 struct RowSetEntry head; 162 struct RowSetEntry *pTail; 163 164 pTail = &head; 165 while( pA && pB ){ 166 assert( pA->pNext==0 || pA->v<=pA->pNext->v ); 167 assert( pB->pNext==0 || pB->v<=pB->pNext->v ); 168 if( pA->v<pB->v ){ 169 pTail->pNext = pA; 170 pA = pA->pNext; 171 pTail = pTail->pNext; 172 }else if( pB->v<pA->v ){ 173 pTail->pNext = pB; 174 pB = pB->pNext; 175 pTail = pTail->pNext; 176 }else{ 177 pA = pA->pNext; 178 } 179 } 180 if( pA ){ 181 assert( pA->pNext==0 || pA->v<=pA->pNext->v ); 182 pTail->pNext = pA; 183 }else{ 184 assert( pB==0 || pB->pNext==0 || pB->v<=pB->pNext->v ); 185 pTail->pNext = pB; 186 } 187 return head.pNext; 188 } 189 190 /* 191 ** Sort all elements of the RowSet into ascending order. 192 */ 193 static void sqlite3RowSetSort(RowSet *p){ 194 unsigned int i; 195 struct RowSetEntry *pEntry; 196 struct RowSetEntry *aBucket[40]; 197 198 assert( p->isSorted==0 ); 199 memset(aBucket, 0, sizeof(aBucket)); 200 while( p->pEntry ){ 201 pEntry = p->pEntry; 202 p->pEntry = pEntry->pNext; 203 pEntry->pNext = 0; 204 for(i=0; aBucket[i]; i++){ 205 pEntry = boolidxMerge(aBucket[i],pEntry); 206 aBucket[i] = 0; 207 } 208 aBucket[i] = pEntry; 209 } 210 pEntry = 0; 211 for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){ 212 pEntry = boolidxMerge(pEntry,aBucket[i]); 213 } 214 p->pEntry = pEntry; 215 p->pLast = 0; 216 p->isSorted = 1; 217 } 218 219 /* 220 ** Extract the next (smallest) element from the RowSet. 221 ** Write the element into *pRowid. Return 1 on success. Return 222 ** 0 if the RowSet is already empty. 223 */ 224 int sqlite3RowSetNext(RowSet *p, i64 *pRowid){ 225 if( !p->isSorted ){ 226 sqlite3RowSetSort(p); 227 } 228 if( p->pEntry ){ 229 *pRowid = p->pEntry->v; 230 p->pEntry = p->pEntry->pNext; 231 if( p->pEntry==0 ){ 232 sqlite3RowSetClear(p); 233 } 234 return 1; 235 }else{ 236 return 0; 237 } 238 } 239