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 ** It must be the case that N is sufficient to make a Rowset. If not 77 ** an assertion fault occurs. 78 ** 79 ** If N is larger than the minimum, use the surplus as an initial 80 ** allocation of entries available to be filled. 81 */ 82 RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){ 83 RowSet *p; 84 assert( N >= sizeof(*p) ); 85 p = pSpace; 86 p->pChunk = 0; 87 p->db = db; 88 p->pEntry = 0; 89 p->pLast = 0; 90 p->pFresh = (struct RowSetEntry*)&p[1]; 91 p->nFresh = (u16)((N - sizeof(*p))/sizeof(struct RowSetEntry)); 92 p->isSorted = 1; 93 return p; 94 } 95 96 /* 97 ** Deallocate all chunks from a RowSet. 98 */ 99 void sqlite3RowSetClear(RowSet *p){ 100 struct RowSetChunk *pChunk, *pNextChunk; 101 for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){ 102 pNextChunk = pChunk->pNext; 103 sqlite3DbFree(p->db, pChunk); 104 } 105 p->pChunk = 0; 106 p->nFresh = 0; 107 p->pEntry = 0; 108 p->pLast = 0; 109 p->isSorted = 1; 110 } 111 112 /* 113 ** Insert a new value into a RowSet. 114 ** 115 ** The mallocFailed flag of the database connection is set if a 116 ** memory allocation fails. 117 */ 118 void sqlite3RowSetInsert(RowSet *p, i64 rowid){ 119 struct RowSetEntry *pEntry; 120 struct RowSetEntry *pLast; 121 if( p==0 ) return; /* Must have been a malloc failure */ 122 if( p->nFresh==0 ){ 123 struct RowSetChunk *pNew; 124 pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew)); 125 if( pNew==0 ){ 126 return; 127 } 128 pNew->pNext = p->pChunk; 129 p->pChunk = pNew; 130 p->pFresh = pNew->aEntry; 131 p->nFresh = ROWSET_ENTRY_PER_CHUNK; 132 } 133 pEntry = p->pFresh++; 134 p->nFresh--; 135 pEntry->v = rowid; 136 pEntry->pNext = 0; 137 pLast = p->pLast; 138 if( pLast ){ 139 if( p->isSorted && rowid<=pLast->v ){ 140 p->isSorted = 0; 141 } 142 pLast->pNext = pEntry; 143 }else{ 144 assert( p->pEntry==0 ); 145 p->pEntry = pEntry; 146 } 147 p->pLast = pEntry; 148 } 149 150 /* 151 ** Merge two lists of RowSet entries. Remove duplicates. 152 ** 153 ** The input lists are assumed to be in sorted order. 154 */ 155 static struct RowSetEntry *boolidxMerge( 156 struct RowSetEntry *pA, /* First sorted list to be merged */ 157 struct RowSetEntry *pB /* Second sorted list to be merged */ 158 ){ 159 struct RowSetEntry head; 160 struct RowSetEntry *pTail; 161 162 pTail = &head; 163 while( pA && pB ){ 164 assert( pA->pNext==0 || pA->v<=pA->pNext->v ); 165 assert( pB->pNext==0 || pB->v<=pB->pNext->v ); 166 if( pA->v<pB->v ){ 167 pTail->pNext = pA; 168 pA = pA->pNext; 169 pTail = pTail->pNext; 170 }else if( pB->v<pA->v ){ 171 pTail->pNext = pB; 172 pB = pB->pNext; 173 pTail = pTail->pNext; 174 }else{ 175 pA = pA->pNext; 176 } 177 } 178 if( pA ){ 179 assert( pA->pNext==0 || pA->v<=pA->pNext->v ); 180 pTail->pNext = pA; 181 }else{ 182 assert( pB==0 || pB->pNext==0 || pB->v<=pB->pNext->v ); 183 pTail->pNext = pB; 184 } 185 return head.pNext; 186 } 187 188 /* 189 ** Sort all elements of the RowSet into ascending order. 190 */ 191 static void sqlite3RowSetSort(RowSet *p){ 192 unsigned int i; 193 struct RowSetEntry *pEntry; 194 struct RowSetEntry *aBucket[40]; 195 196 assert( p->isSorted==0 ); 197 memset(aBucket, 0, sizeof(aBucket)); 198 while( p->pEntry ){ 199 pEntry = p->pEntry; 200 p->pEntry = pEntry->pNext; 201 pEntry->pNext = 0; 202 for(i=0; aBucket[i]; i++){ 203 pEntry = boolidxMerge(aBucket[i],pEntry); 204 aBucket[i] = 0; 205 } 206 aBucket[i] = pEntry; 207 } 208 pEntry = 0; 209 for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){ 210 pEntry = boolidxMerge(pEntry,aBucket[i]); 211 } 212 p->pEntry = pEntry; 213 p->pLast = 0; 214 p->isSorted = 1; 215 } 216 217 /* 218 ** Extract the next (smallest) element from the RowSet. 219 ** Write the element into *pRowid. Return 1 on success. Return 220 ** 0 if the RowSet is already empty. 221 */ 222 int sqlite3RowSetNext(RowSet *p, i64 *pRowid){ 223 if( !p->isSorted ){ 224 sqlite3RowSetSort(p); 225 } 226 if( p->pEntry ){ 227 *pRowid = p->pEntry->v; 228 p->pEntry = p->pEntry->pNext; 229 if( p->pEntry==0 ){ 230 sqlite3RowSetClear(p); 231 } 232 return 1; 233 }else{ 234 return 0; 235 } 236 } 237