15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2008 December 3 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The author disclaims copyright to this source code. In place of 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** a legal notice, here is a blessing: 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you do good and not evil. 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you find forgiveness for yourself and forgive others. 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** May you share freely, never taking more than you give. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)************************************************************************* 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** This module implements an object we call a "RowSet". 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The RowSet object is a collection of rowids. Rowids 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** are inserted into the RowSet in an arbitrary order. Inserts 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** can be intermixed with tests to see if a given rowid has been 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** previously inserted into the RowSet. 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** After all inserts are finished, it is possible to extract the 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** elements of the RowSet in sorted order. Once this extraction 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** process has started, no new elements may be inserted. 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Hence, the primitive operations for a RowSet are: 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** CREATE 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** INSERT 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** TEST 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** SMALLEST 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** DESTROY 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The CREATE and DESTROY primitives are the constructor and destructor, 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** obviously. The INSERT primitive adds a new element to the RowSet. 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** TEST checks to see if an element is already in the RowSet. SMALLEST 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** extracts the least value from the RowSet. 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The INSERT primitive might allocate additional memory. Memory is 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** allocated in chunks so most INSERTs do no allocation. There is an 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** upper bound on the size of allocated memory. No memory is freed 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** until DESTROY. 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The TEST primitive includes a "batch" number. The TEST primitive 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** will only see elements that were inserted before the last change 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** in the batch number. In other words, if an INSERT occurs between 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** two TESTs where the TESTs have the same batch nubmer, then the 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** value added by the INSERT will not be visible to the second TEST. 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The initial batch number is zero, so if the very first TEST contains 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** a non-zero batch number, it will see all prior INSERTs. 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** No INSERTs may occurs after a SMALLEST. An assertion will fail if 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** that is attempted. 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The cost of an INSERT is roughly constant. (Sometime new memory 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** has to be allocated on an INSERT.) The cost of a TEST with a new 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** batch number is O(NlogN) where N is the number of elements in the RowSet. 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The cost of a TEST using the same batch number is O(logN). The cost 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** of the first SMALLEST is O(NlogN). Second and subsequent SMALLEST 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** primitives are constant time. The cost of DESTROY is O(N). 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** There is an added cost of O(N) when switching between TEST and 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** SMALLEST primitives. 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "sqliteInt.h" 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Target size for allocation chunks. 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define ROWSET_ALLOCATION_SIZE 1024 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The number of rowset entries per allocation chunk. 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#define ROWSET_ENTRY_PER_CHUNK \ 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry)) 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Each entry in a RowSet is an instance of the following object. 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct RowSetEntry { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) i64 v; /* ROWID value for this entry */ 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pRight; /* Right subtree (larger entries) or list */ 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pLeft; /* Left subtree (smaller entries) */ 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** RowSetEntry objects are allocated in large chunks (instances of the 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** following structure) to reduce memory allocation overhead. The 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** chunks are kept on a linked list so that they can be deallocated 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** when the RowSet is destroyed. 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct RowSetChunk { 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetChunk *pNextChunk; /* Next chunk on list of them all */ 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */ 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** A RowSet in an instance of the following structure. 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** A typedef of this structure if found in sqliteInt.h. 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)struct RowSet { 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetChunk *pChunk; /* List of all chunk allocations */ 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3 *db; /* The database connection */ 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pEntry; /* List of entries using pRight */ 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pLast; /* Last entry on the pEntry list */ 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pFresh; /* Source of new entry objects */ 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pTree; /* Binary tree of entries */ 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u16 nFresh; /* Number of objects on pFresh */ 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u8 isSorted; /* True if pEntry is sorted */ 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) u8 iBatch; /* Current insert batch */ 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Turn bulk memory into a RowSet object. N bytes of memory 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** are available at pSpace. The db pointer is used as a memory context 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** for any subsequent allocations that need to occur. 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return a pointer to the new RowSet object. 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** It must be the case that N is sufficient to make a Rowset. If not 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** an assertion fault occurs. 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** If N is larger than the minimum, use the surplus as an initial 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** allocation of entries available to be filled. 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)RowSet *sqlite3RowSetInit(sqlite3 *db, void *pSpace, unsigned int N){ 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) RowSet *p; 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( N >= ROUND8(sizeof(*p)) ); 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = pSpace; 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pChunk = 0; 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->db = db; 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pEntry = 0; 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLast = 0; 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pTree = 0; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pFresh = (struct RowSetEntry*)(ROUND8(sizeof(*p)) + (char*)p); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->nFresh = (u16)((N - ROUND8(sizeof(*p)))/sizeof(struct RowSetEntry)); 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->isSorted = 1; 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->iBatch = 0; 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Deallocate all chunks from a RowSet. This frees all memory that 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** the RowSet has allocated over its lifetime. This routine is 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** the destructor for the RowSet. 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void sqlite3RowSetClear(RowSet *p){ 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetChunk *pChunk, *pNextChunk; 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){ 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNextChunk = pChunk->pNextChunk; 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3DbFree(p->db, pChunk); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pChunk = 0; 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->nFresh = 0; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pEntry = 0; 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLast = 0; 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pTree = 0; 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->isSorted = 1; 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Insert a new value into a RowSet. 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The mallocFailed flag of the database connection is set if a 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** memory allocation fails. 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void sqlite3RowSetInsert(RowSet *p, i64 rowid){ 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pEntry; /* The new entry */ 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pLast; /* The last prior entry */ 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( p!=0 ); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->nFresh==0 ){ 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetChunk *pNew; 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew)); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pNew==0 ){ 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pNew->pNextChunk = p->pChunk; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pChunk = pNew; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pFresh = pNew->aEntry; 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->nFresh = ROWSET_ENTRY_PER_CHUNK; 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry = p->pFresh++; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->nFresh--; 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry->v = rowid; 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry->pRight = 0; 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pLast = p->pLast; 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pLast ){ 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->isSorted && rowid<=pLast->v ){ 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->isSorted = 0; 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pLast->pRight = pEntry; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( p->pEntry==0 ); /* Fires if INSERT after SMALLEST */ 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pEntry = pEntry; 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLast = pEntry; 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Merge two lists of RowSetEntry objects. Remove duplicates. 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The input lists are connected via pRight pointers and are 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** assumed to each already be in sorted order. 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static struct RowSetEntry *rowSetMerge( 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pA, /* First sorted list to be merged */ 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pB /* Second sorted list to be merged */ 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)){ 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry head; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pTail; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTail = &head; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( pA && pB ){ 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pA->pRight==0 || pA->v<=pA->pRight->v ); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pB->pRight==0 || pB->v<=pB->pRight->v ); 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pA->v<pB->v ){ 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTail->pRight = pA; 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pA = pA->pRight; 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTail = pTail->pRight; 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else if( pB->v<pA->v ){ 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTail->pRight = pB; 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pB = pB->pRight; 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTail = pTail->pRight; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pA = pA->pRight; 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pA ){ 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pA->pRight==0 || pA->v<=pA->pRight->v ); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTail->pRight = pA; 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v ); 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pTail->pRight = pB; 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return head.pRight; 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Sort all elements on the pEntry list of the RowSet into ascending order. 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void rowSetSort(RowSet *p){ 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) unsigned int i; 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pEntry; 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *aBucket[40]; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( p->isSorted==0 ); 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) memset(aBucket, 0, sizeof(aBucket)); 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( p->pEntry ){ 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry = p->pEntry; 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pEntry = pEntry->pRight; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry->pRight = 0; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0; aBucket[i]; i++){ 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry = rowSetMerge(aBucket[i], pEntry); 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aBucket[i] = 0; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) aBucket[i] = pEntry; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry = 0; 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){ 2605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pEntry = rowSetMerge(pEntry, aBucket[i]); 2615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pEntry = pEntry; 2635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLast = 0; 2645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->isSorted = 1; 2655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects. 2705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Convert this tree into a linked list connected by the pRight pointers 2715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** and return pointers to the first and last elements of the new list. 2725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 2735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void rowSetTreeToList( 2745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pIn, /* Root of the input tree */ 2755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry **ppFirst, /* Write head of the output list here */ 2765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry **ppLast /* Write tail of the output list here */ 2775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)){ 2785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pIn!=0 ); 2795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pIn->pLeft ){ 2805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *p; 2815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rowSetTreeToList(pIn->pLeft, ppFirst, &p); 2825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pRight = pIn; 2835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *ppFirst = pIn; 2855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pIn->pRight ){ 2875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast); 2885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 2895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *ppLast = pIn; 2905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( (*ppLast)->pRight==0 ); 2925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 2965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Convert a sorted list of elements (connected by pRight) into a binary 2975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** tree with depth of iDepth. A depth of 1 means the tree contains a single 2985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** node taken from the head of *ppList. A depth of 2 means a tree with 2995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** three nodes. And so forth. 3005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Use as many entries from the input list as required and update the 3025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** *ppList to point to the unused elements of the list. If the input 3035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** list contains too few elements, then construct an incomplete tree 3045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** and leave *ppList set to NULL. 3055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Return a pointer to the root of the constructed binary tree. 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static struct RowSetEntry *rowSetNDeepTree( 3095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry **ppList, 3105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iDepth 3115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)){ 3125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *p; /* Root of the new tree */ 3135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pLeft; /* Left subtree */ 3145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( *ppList==0 ){ 3155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 3165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( iDepth==1 ){ 3185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = *ppList; 3195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *ppList = p->pRight; 3205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLeft = p->pRight = 0; 3215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 3225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pLeft = rowSetNDeepTree(ppList, iDepth-1); 3245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = *ppList; 3255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p==0 ){ 3265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return pLeft; 3275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLeft = pLeft; 3295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *ppList = p->pRight; 3305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pRight = rowSetNDeepTree(ppList, iDepth-1); 3315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 3325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Convert a sorted list of elements into a binary tree. Make the tree 3365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** as deep as it needs to be in order to contain the entire list. 3375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){ 3395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int iDepth; /* Depth of the tree so far */ 3405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *p; /* Current tree root */ 3415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pLeft; /* Left subtree */ 3425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) assert( pList!=0 ); 3445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = pList; 3455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pList = p->pRight; 3465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLeft = p->pRight = 0; 3475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for(iDepth=1; pList; iDepth++){ 3485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pLeft = p; 3495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = pList; 3505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pList = p->pRight; 3515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pLeft = pLeft; 3525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pRight = rowSetNDeepTree(&pList, iDepth); 3535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return p; 3555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Convert the list in p->pEntry into a sorted list if it is not 3595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** sorted already. If there is a binary tree on p->pTree, then 3605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** convert it into a list too and merge it into the p->pEntry list. 3615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)static void rowSetToList(RowSet *p){ 3635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( !p->isSorted ){ 3645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rowSetSort(p); 3655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->pTree ){ 3675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *pHead, *pTail; 3685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rowSetTreeToList(p->pTree, &pHead, &pTail); 3695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pTree = 0; 3705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pEntry = rowSetMerge(p->pEntry, pHead); 3715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Extract the smallest element from the RowSet. 3765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Write the element into *pRowid. Return 1 on success. Return 3775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 0 if the RowSet is already empty. 3785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** 3795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** After this routine has been called, the sqlite3RowSetInsert() 3805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** routine may not be called again. 3815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 3825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int sqlite3RowSetNext(RowSet *p, i64 *pRowid){ 3835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rowSetToList(p); 3845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->pEntry ){ 3855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) *pRowid = p->pEntry->v; 3865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p->pEntry = p->pEntry->pRight; 3875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->pEntry==0 ){ 3885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) sqlite3RowSetClear(p); 3895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 3915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 3925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 3935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 3945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 3955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/* 3975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** Check to see if element iRowid was inserted into the the rowset as 3985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)** part of any insert batch prior to iBatch. Return 1 or 0. 3995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)*/ 4005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)int sqlite3RowSetTest(RowSet *pRowSet, u8 iBatch, sqlite3_int64 iRowid){ 4015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) struct RowSetEntry *p; 4025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( iBatch!=pRowSet->iBatch ){ 4035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( pRowSet->pEntry ){ 4045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) rowSetToList(pRowSet); 4055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pRowSet->pTree = rowSetListToTree(pRowSet->pEntry); 4065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pRowSet->pEntry = 0; 4075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pRowSet->pLast = 0; 4085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) pRowSet->iBatch = iBatch; 4105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = pRowSet->pTree; 4125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while( p ){ 4135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if( p->v<iRowid ){ 4145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = p->pRight; 4155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else if( p->v>iRowid ){ 4165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) p = p->pLeft; 4175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) }else{ 4185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 1; 4195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 4215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return 0; 4225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 423