/ Check-in [b101cf70]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Extend the Rowset object to contain all the capabilities of Rowhash in addition to its legacy capabilities. Use Rowset to replace Rowhash. In addition to requiring less code, This removes the 2^32 result row limitation, uses less memory, and gives better bounds on worst-case performance. The Rowhash implementation has yet to be removed. (CVS 6534)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:b101cf70b75c9772aaf50e0eadd0cfa37c84d193
User & Date: drh 2009-04-22 00:47:01
References
2014-04-10
02:09 New ticket [10fb063b] Duplicate row output on an OR query. artifact: 530cc4a7 user: drh
Context
2009-04-22
02:15
Remove the rowhash object from the code. Rowset now fills its role. (CVS 6535) check-in: e963bed0 user: drh tags: trunk
00:47
Extend the Rowset object to contain all the capabilities of Rowhash in addition to its legacy capabilities. Use Rowset to replace Rowhash. In addition to requiring less code, This removes the 2^32 result row limitation, uses less memory, and gives better bounds on worst-case performance. The Rowhash implementation has yet to be removed. (CVS 6534) check-in: b101cf70 user: drh tags: trunk
2009-04-21
18:20
Move RowHashBlock.nUsed to RowHash.nUsed. Fix a typo in a comment in test_async.c. (CVS 6533) check-in: 799d31d9 user: danielk1977 tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/rowhash.c.

    27     27   ** The insert batch number is a parameter to the TEST primitive.  The
    28     28   ** hash table is rebuilt whenever the batch number increases.  TEST
    29     29   ** operations only look for INSERTs that occurred in prior batches.
    30     30   **
    31     31   ** The caller is responsible for insuring that there are no duplicate
    32     32   ** INSERTs.
    33     33   **
    34         -** $Id: rowhash.c,v 1.4 2009/04/21 18:20:45 danielk1977 Exp $
           34  +** $Id: rowhash.c,v 1.5 2009/04/22 00:47:01 drh Exp $
    35     35   */
    36     36   #include "sqliteInt.h"
    37     37   
    38     38   /*
    39     39   ** An upper bound on the size of heap allocations made by this module.
    40     40   ** Limiting the size of allocations helps to avoid memory fragmentation.
    41     41   */
................................................................................
   131    131   };
   132    132   
   133    133   /*
   134    134   ** RowHash structure. References to a structure of this type are passed
   135    135   ** around and used as opaque handles by code in other modules.
   136    136   */
   137    137   struct RowHash {
   138         -  int nUsed;              /* Number of used entries in first RowHashBlock */
   139         -  int nEntry;             /* Number of used entries over all RowHashBlocks */
          138  +  unsigned int nEntry;    /* Number of used entries over all RowHashBlocks */
   140    139     int iBatch;             /* The current insert batch number */
          140  +  u16 nUsed;              /* Number of used entries in first RowHashBlock */
   141    141     u8 nHeight;             /* Height of tree of hash pages */
   142    142     u8 nLinearLimit;        /* Linear search limit (used if pHash==0) */
   143    143     int nBucket;            /* Number of buckets in hash table */
   144    144     RowHashPage *pHash;     /* Pointer to root of hash table tree */
   145    145     RowHashBlock *pBlock;   /* Linked list of RowHashBlocks */
   146    146     sqlite3 *db;            /* Associated database connection */
   147    147   };

Changes to src/rowset.c.

     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   **
    13         -** This module implements an object we call a "Row Set".
           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.
    14     52   **
    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.
           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).
    20     59   **
    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.
           60  +** There is an added cost of O(N) when switching between TEST and
           61  +** SMALLEST primitives.
    24     62   **
    25         -** Big chunks of rowid/next-ptr pairs are allocated at a time, to
    26         -** reduce the malloc overhead.
    27         -**
    28         -** $Id: rowset.c,v 1.4 2009/04/01 19:35:55 drh Exp $
           63  +** $Id: rowset.c,v 1.5 2009/04/22 00:47:01 drh Exp $
    29     64   */
    30     65   #include "sqliteInt.h"
    31     66   
           67  +
           68  +/*
           69  +** Target size for allocation chunks.
           70  +*/
           71  +#define ROWSET_ALLOCATION_SIZE 1024
           72  +
    32     73   /*
    33     74   ** The number of rowset entries per allocation chunk.
    34     75   */
    35         -#define ROWSET_ENTRY_PER_CHUNK  63
           76  +#define ROWSET_ENTRY_PER_CHUNK  \
           77  +                       ((ROWSET_ALLOCATION_SIZE-8)/sizeof(struct RowSetEntry))
    36     78   
    37     79   /*
    38         -** Each entry in a RowSet is an instance of the following
    39         -** structure:
           80  +** Each entry in a RowSet is an instance of the following object.
    40     81   */
    41     82   struct RowSetEntry {            
    42     83     i64 v;                        /* ROWID value for this entry */
    43         -  struct RowSetEntry *pNext;    /* Next entry on a list of all entries */
           84  +  struct RowSetEntry *pRight;   /* Right subtree (larger entries) or list */
           85  +  struct RowSetEntry *pLeft;    /* Left subtree (smaller entries) */
    44     86   };
    45     87   
    46     88   /*
    47         -** Index entries are allocated in large chunks (instances of the
           89  +** RowSetEntry objects are allocated in large chunks (instances of the
    48     90   ** following structure) to reduce memory allocation overhead.  The
    49     91   ** chunks are kept on a linked list so that they can be deallocated
    50     92   ** when the RowSet is destroyed.
    51     93   */
    52     94   struct RowSetChunk {
    53         -  struct RowSetChunk *pNext;             /* Next chunk on list of them all */
           95  +  struct RowSetChunk *pNextChunk;        /* Next chunk on list of them all */
    54     96     struct RowSetEntry aEntry[ROWSET_ENTRY_PER_CHUNK]; /* Allocated entries */
    55     97   };
    56     98   
    57     99   /*
    58    100   ** A RowSet in an instance of the following structure.
    59    101   **
    60    102   ** A typedef of this structure if found in sqliteInt.h.
    61    103   */
    62    104   struct RowSet {
    63    105     struct RowSetChunk *pChunk;    /* List of all chunk allocations */
    64    106     sqlite3 *db;                   /* The database connection */
    65         -  struct RowSetEntry *pEntry;    /* List of entries in the rowset */
          107  +  struct RowSetEntry *pEntry;    /* List of entries using pRight */
    66    108     struct RowSetEntry *pLast;     /* Last entry on the pEntry list */
    67    109     struct RowSetEntry *pFresh;    /* Source of new entry objects */
          110  +  struct RowSetEntry *pTree;     /* Binary tree of entries */
    68    111     u16 nFresh;                    /* Number of objects on pFresh */
    69         -  u8 isSorted;                   /* True if content is sorted */
          112  +  u8 isSorted;                   /* True if pEntry is sorted */
          113  +  u8 iBatch;                     /* Current insert batch */
    70    114   };
    71    115   
    72    116   /*
    73    117   ** Turn bulk memory into a RowSet object.  N bytes of memory
    74    118   ** are available at pSpace.  The db pointer is used as a memory context
    75    119   ** for any subsequent allocations that need to occur.
    76    120   ** Return a pointer to the new RowSet object.
................................................................................
    85    129     RowSet *p;
    86    130     assert( N >= sizeof(*p) );
    87    131     p = pSpace;
    88    132     p->pChunk = 0;
    89    133     p->db = db;
    90    134     p->pEntry = 0;
    91    135     p->pLast = 0;
          136  +  p->pTree = 0;
    92    137     p->pFresh = (struct RowSetEntry*)&p[1];
    93    138     p->nFresh = (u16)((N - sizeof(*p))/sizeof(struct RowSetEntry));
    94    139     p->isSorted = 1;
          140  +  p->iBatch = 0;
    95    141     return p;
    96    142   }
    97    143   
    98    144   /*
    99         -** Deallocate all chunks from a RowSet.
          145  +** Deallocate all chunks from a RowSet.  This frees all memory that
          146  +** the RowSet has allocated over its lifetime.  This routine is
          147  +** the destructor for the RowSet.
   100    148   */
   101    149   void sqlite3RowSetClear(RowSet *p){
   102    150     struct RowSetChunk *pChunk, *pNextChunk;
   103    151     for(pChunk=p->pChunk; pChunk; pChunk = pNextChunk){
   104         -    pNextChunk = pChunk->pNext;
          152  +    pNextChunk = pChunk->pNextChunk;
   105    153       sqlite3DbFree(p->db, pChunk);
   106    154     }
   107    155     p->pChunk = 0;
   108    156     p->nFresh = 0;
   109    157     p->pEntry = 0;
   110    158     p->pLast = 0;
          159  +  p->pTree = 0;
   111    160     p->isSorted = 1;
   112    161   }
   113    162   
   114    163   /*
   115    164   ** Insert a new value into a RowSet.
   116    165   **
   117    166   ** The mallocFailed flag of the database connection is set if a
   118    167   ** memory allocation fails.
   119    168   */
   120    169   void sqlite3RowSetInsert(RowSet *p, i64 rowid){
   121         -  struct RowSetEntry *pEntry;
   122         -  struct RowSetEntry *pLast;
          170  +  struct RowSetEntry *pEntry;  /* The new entry */
          171  +  struct RowSetEntry *pLast;   /* The last prior entry */
   123    172     assert( p!=0 );
   124    173     if( p->nFresh==0 ){
   125    174       struct RowSetChunk *pNew;
   126    175       pNew = sqlite3DbMallocRaw(p->db, sizeof(*pNew));
   127    176       if( pNew==0 ){
   128    177         return;
   129    178       }
   130         -    pNew->pNext = p->pChunk;
          179  +    pNew->pNextChunk = p->pChunk;
   131    180       p->pChunk = pNew;
   132    181       p->pFresh = pNew->aEntry;
   133    182       p->nFresh = ROWSET_ENTRY_PER_CHUNK;
   134    183     }
   135    184     pEntry = p->pFresh++;
   136    185     p->nFresh--;
   137    186     pEntry->v = rowid;
   138         -  pEntry->pNext = 0;
          187  +  pEntry->pRight = 0;
   139    188     pLast = p->pLast;
   140    189     if( pLast ){
   141    190       if( p->isSorted && rowid<=pLast->v ){
   142    191         p->isSorted = 0;
   143    192       }
   144         -    pLast->pNext = pEntry;
          193  +    pLast->pRight = pEntry;
   145    194     }else{
   146         -    assert( p->pEntry==0 );
          195  +    assert( p->pEntry==0 ); /* Fires if INSERT after SMALLEST */
   147    196       p->pEntry = pEntry;
   148    197     }
   149    198     p->pLast = pEntry;
   150    199   }
   151    200   
   152    201   /*
   153         -** Merge two lists of RowSet entries.  Remove duplicates.
          202  +** Merge two lists of RowSetEntry objects.  Remove duplicates.
   154    203   **
   155         -** The input lists are assumed to be in sorted order.
          204  +** The input lists are connected via pRight pointers and are 
          205  +** assumed to each already be in sorted order.
   156    206   */
   157         -static struct RowSetEntry *boolidxMerge(
          207  +static struct RowSetEntry *rowSetMerge(
   158    208     struct RowSetEntry *pA,    /* First sorted list to be merged */
   159    209     struct RowSetEntry *pB     /* Second sorted list to be merged */
   160    210   ){
   161    211     struct RowSetEntry head;
   162    212     struct RowSetEntry *pTail;
   163    213   
   164    214     pTail = &head;
   165    215     while( pA && pB ){
   166         -    assert( pA->pNext==0 || pA->v<=pA->pNext->v );
   167         -    assert( pB->pNext==0 || pB->v<=pB->pNext->v );
          216  +    assert( pA->pRight==0 || pA->v<=pA->pRight->v );
          217  +    assert( pB->pRight==0 || pB->v<=pB->pRight->v );
   168    218       if( pA->v<pB->v ){
   169         -      pTail->pNext = pA;
   170         -      pA = pA->pNext;
   171         -      pTail = pTail->pNext;
          219  +      pTail->pRight = pA;
          220  +      pA = pA->pRight;
          221  +      pTail = pTail->pRight;
   172    222       }else if( pB->v<pA->v ){
   173         -      pTail->pNext = pB;
   174         -      pB = pB->pNext;
   175         -      pTail = pTail->pNext;
          223  +      pTail->pRight = pB;
          224  +      pB = pB->pRight;
          225  +      pTail = pTail->pRight;
   176    226       }else{
   177         -      pA = pA->pNext;
          227  +      pA = pA->pRight;
   178    228       }
   179    229     }
   180    230     if( pA ){
   181         -    assert( pA->pNext==0 || pA->v<=pA->pNext->v );
   182         -    pTail->pNext = pA;
          231  +    assert( pA->pRight==0 || pA->v<=pA->pRight->v );
          232  +    pTail->pRight = pA;
   183    233     }else{
   184         -    assert( pB==0 || pB->pNext==0 || pB->v<=pB->pNext->v );
   185         -    pTail->pNext = pB;
          234  +    assert( pB==0 || pB->pRight==0 || pB->v<=pB->pRight->v );
          235  +    pTail->pRight = pB;
   186    236     }
   187         -  return head.pNext;
          237  +  return head.pRight;
   188    238   }
   189    239   
   190    240   /*
   191         -** Sort all elements of the RowSet into ascending order.
          241  +** Sort all elements on the pEntry list of the RowSet into ascending order.
   192    242   */ 
   193         -static void sqlite3RowSetSort(RowSet *p){
          243  +static void rowSetSort(RowSet *p){
   194    244     unsigned int i;
   195    245     struct RowSetEntry *pEntry;
   196    246     struct RowSetEntry *aBucket[40];
   197    247   
   198    248     assert( p->isSorted==0 );
   199    249     memset(aBucket, 0, sizeof(aBucket));
   200    250     while( p->pEntry ){
   201    251       pEntry = p->pEntry;
   202         -    p->pEntry = pEntry->pNext;
   203         -    pEntry->pNext = 0;
          252  +    p->pEntry = pEntry->pRight;
          253  +    pEntry->pRight = 0;
   204    254       for(i=0; aBucket[i]; i++){
   205         -      pEntry = boolidxMerge(aBucket[i],pEntry);
          255  +      pEntry = rowSetMerge(aBucket[i], pEntry);
   206    256         aBucket[i] = 0;
   207    257       }
   208    258       aBucket[i] = pEntry;
   209    259     }
   210    260     pEntry = 0;
   211    261     for(i=0; i<sizeof(aBucket)/sizeof(aBucket[0]); i++){
   212         -    pEntry = boolidxMerge(pEntry,aBucket[i]);
          262  +    pEntry = rowSetMerge(pEntry, aBucket[i]);
   213    263     }
   214    264     p->pEntry = pEntry;
   215    265     p->pLast = 0;
   216    266     p->isSorted = 1;
   217    267   }
   218    268   
          269  +
          270  +/*
          271  +** The input, pIn, is a binary tree (or subtree) of RowSetEntry objects.
          272  +** Convert this tree into a linked list connected by the pRight pointers
          273  +** and return pointers to the first and last elements of the new list.
          274  +*/
          275  +static void rowSetTreeToList(
          276  +  struct RowSetEntry *pIn,         /* Root of the input tree */
          277  +  struct RowSetEntry **ppFirst,    /* Write head of the output list here */
          278  +  struct RowSetEntry **ppLast      /* Write tail of the output list here */
          279  +){
          280  +  if( pIn==0 ){
          281  +    *ppFirst = *ppLast = 0;
          282  +  }
          283  +  if( pIn->pLeft ){
          284  +    struct RowSetEntry *p;
          285  +    rowSetTreeToList(pIn->pLeft, ppFirst, &p);
          286  +    p->pRight = pIn;
          287  +  }else{
          288  +    *ppFirst = pIn;
          289  +  }
          290  +  if( pIn->pRight ){
          291  +    rowSetTreeToList(pIn->pRight, &pIn->pRight, ppLast);
          292  +  }else{
          293  +    *ppLast = pIn;
          294  +  }
          295  +  assert( (*ppLast)->pRight==0 );
          296  +}
          297  +
          298  +
          299  +/*
          300  +** Convert a sorted list of elements (connected by pRight) into a binary
          301  +** tree with depth of iDepth.  A depth of 1 means the tree contains a single
          302  +** node taken from the head of *ppList.  A depth of 2 means a tree with
          303  +** three nodes.  And so forth.
          304  +**
          305  +** Use as many entries from the input list as required and update the
          306  +** *ppList to point to the unused elements of the list.  If the input
          307  +** list contains too few elements, then construct an incomplete tree
          308  +** and leave *ppList set to NULL.
          309  +**
          310  +** Return a pointer to the root of the constructed binary tree.
          311  +*/
          312  +static struct RowSetEntry *rowSetNDeepTree(
          313  +  struct RowSetEntry **ppList,
          314  +  int iDepth
          315  +){
          316  +  struct RowSetEntry *p;         /* Root of the new tree */
          317  +  struct RowSetEntry *pLeft;     /* Left subtree */
          318  +  if( *ppList==0 ){
          319  +    return 0;
          320  +  }
          321  +  if( iDepth==1 ){
          322  +    p = *ppList;
          323  +    *ppList = p->pRight;
          324  +    p->pLeft = p->pRight = 0;
          325  +    return p;
          326  +  }
          327  +  pLeft = rowSetNDeepTree(ppList, iDepth-1);
          328  +  p = *ppList;
          329  +  if( p==0 ){
          330  +    return pLeft;
          331  +  }
          332  +  p->pLeft = pLeft;
          333  +  *ppList = p->pRight;
          334  +  p->pRight = rowSetNDeepTree(ppList, iDepth-1);
          335  +  return p;
          336  +}
          337  +
          338  +/*
          339  +** Convert a sorted list of elements into a binary tree. Make the tree
          340  +** as deep as it needs to be in order to contain the entire list.
          341  +*/
          342  +static struct RowSetEntry *rowSetListToTree(struct RowSetEntry *pList){
          343  +  int iDepth;           /* Depth of the tree so far */
          344  +  struct RowSetEntry *p;       /* Current tree root */
          345  +  struct RowSetEntry *pLeft;   /* Left subtree */
          346  +
          347  +  if( pList==0 ){
          348  +    return 0;
          349  +  }
          350  +  p = pList;
          351  +  pList = p->pRight;
          352  +  p->pLeft = p->pRight = 0;
          353  +  for(iDepth=1; pList; iDepth++){
          354  +    pLeft = p;
          355  +    p = pList;
          356  +    pList = p->pRight;
          357  +    p->pLeft = pLeft;
          358  +    p->pRight = rowSetNDeepTree(&pList, iDepth);
          359  +  }
          360  +  return p;
          361  +}
          362  +
          363  +/*
          364  +** Convert the list in p->pEntry into a sorted list if it is not
          365  +** sorted already.  If there is a binary tree on p->pTree, then
          366  +** convert it into a list too and merge it into the p->pEntry list.
          367  +*/
          368  +static void rowSetToList(RowSet *p){
          369  +  if( !p->isSorted ){
          370  +    rowSetSort(p);
          371  +  }
          372  +  if( p->pTree ){
          373  +    struct RowSetEntry *pHead, *pTail;
          374  +    rowSetTreeToList(p->pTree, &pHead, &pTail);
          375  +    p->pTree = 0;
          376  +    p->pEntry = rowSetMerge(p->pEntry, pHead);
          377  +  }
          378  +}
          379  +
   219    380   /*
   220         -** Extract the next (smallest) element from the RowSet.
          381  +** Extract the smallest element from the RowSet.
   221    382   ** Write the element into *pRowid.  Return 1 on success.  Return
   222    383   ** 0 if the RowSet is already empty.
          384  +**
          385  +** After this routine has been called, the sqlite3RowSetInsert()
          386  +** routine may not be called again.  
   223    387   */
   224    388   int sqlite3RowSetNext(RowSet *p, i64 *pRowid){
   225         -  if( !p->isSorted ){
   226         -    sqlite3RowSetSort(p);
   227         -  }
          389  +  rowSetToList(p);
   228    390     if( p->pEntry ){
   229    391       *pRowid = p->pEntry->v;
   230         -    p->pEntry = p->pEntry->pNext;
          392  +    p->pEntry = p->pEntry->pRight;
   231    393       if( p->pEntry==0 ){
   232    394         sqlite3RowSetClear(p);
   233    395       }
   234    396       return 1;
   235    397     }else{
   236    398       return 0;
   237    399     }
   238    400   }
          401  +
          402  +/*
          403  +** Check to see if element iRowid was inserted into the the rowset as
          404  +** part of any insert batch prior to iBatch.  Return 1 or 0.
          405  +*/
          406  +int sqlite3RowSetTest(RowSet *pRowSet, u8 iBatch, sqlite3_int64 iRowid){
          407  +  struct RowSetEntry *p;
          408  +  if( iBatch!=pRowSet->iBatch ){
          409  +    if( pRowSet->pEntry ){
          410  +      rowSetToList(pRowSet);
          411  +      pRowSet->pTree = rowSetListToTree(pRowSet->pEntry);
          412  +      pRowSet->pEntry = 0;
          413  +      pRowSet->pLast = 0;
          414  +    }
          415  +    pRowSet->iBatch = iBatch;
          416  +  }
          417  +  p = pRowSet->pTree;
          418  +  while( p ){
          419  +    if( p->v<iRowid ){
          420  +      p = p->pRight;
          421  +    }else if( p->v>iRowid ){
          422  +      p = p->pLeft;
          423  +    }else{
          424  +      return 1;
          425  +    }
          426  +  }
          427  +  return 0;
          428  +}

Changes to src/sqliteInt.h.

     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14         -** @(#) $Id: sqliteInt.h,v 1.856 2009/04/21 16:15:15 drh Exp $
           14  +** @(#) $Id: sqliteInt.h,v 1.857 2009/04/22 00:47:01 drh Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
    19     19   /*
    20     20   ** Include the configuration header output by 'configure' if we're using the
    21     21   ** autoconf-based build
................................................................................
  2396   2396   void sqlite3BitvecDestroy(Bitvec*);
  2397   2397   u32 sqlite3BitvecSize(Bitvec*);
  2398   2398   int sqlite3BitvecBuiltinTest(int,int*);
  2399   2399   
  2400   2400   RowSet *sqlite3RowSetInit(sqlite3*, void*, unsigned int);
  2401   2401   void sqlite3RowSetClear(RowSet*);
  2402   2402   void sqlite3RowSetInsert(RowSet*, i64);
         2403  +int sqlite3RowSetTest(RowSet*, u8 iBatch, i64);
  2403   2404   int sqlite3RowSetNext(RowSet*, i64*);
  2404   2405   
  2405   2406   int sqlite3RowhashInsert(sqlite3*, RowHash **pp, i64 iVal);
  2406   2407   int sqlite3RowhashTest(RowHash *p, int iSet, i64 iVal, int *pExists);
  2407   2408   void sqlite3RowhashDestroy(RowHash *p);
  2408   2409   
  2409   2410   void sqlite3CreateView(Parse*,Token*,Token*,Token*,Select*,int,int);

Changes to src/vdbe.c.

    39     39   **
    40     40   ** Various scripts scan this source file in order to generate HTML
    41     41   ** documentation, headers files, or other derived files.  The formatting
    42     42   ** of the code in this file is, therefore, important.  See other comments
    43     43   ** in this file for details.  If in doubt, do not deviate from existing
    44     44   ** commenting and indentation practices when changing or adding code.
    45     45   **
    46         -** $Id: vdbe.c,v 1.835 2009/04/21 16:15:15 drh Exp $
           46  +** $Id: vdbe.c,v 1.836 2009/04/22 00:47:01 drh Exp $
    47     47   */
    48     48   #include "sqliteInt.h"
    49     49   #include "vdbeInt.h"
    50     50   
    51     51   /*
    52     52   ** The following global variable is incremented every time a cursor
    53     53   ** moves, either by the OP_SeekXX, OP_Next, or OP_Prev opcodes.  The test
................................................................................
   424    424       fprintf(out, " NULL");
   425    425     }else if( (p->flags & (MEM_Int|MEM_Str))==(MEM_Int|MEM_Str) ){
   426    426       fprintf(out, " si:%lld", p->u.i);
   427    427     }else if( p->flags & MEM_Int ){
   428    428       fprintf(out, " i:%lld", p->u.i);
   429    429     }else if( p->flags & MEM_Real ){
   430    430       fprintf(out, " r:%g", p->r);
          431  +  }else if( p->flags & MEM_RowSet ){
          432  +    fprintf(out, " (rowset)");
   431    433     }else{
   432    434       char zBuf[200];
   433    435       sqlite3VdbeMemPrettyPrint(p, zBuf);
   434    436       fprintf(out, " ");
   435    437       fprintf(out, "%s", zBuf);
   436    438     }
   437    439   }
................................................................................
  4627   4629     int iSet = pOp->p4.i;
  4628   4630     assert( pIn3->flags&MEM_Int );
  4629   4631   
  4630   4632     /* If there is anything other than a row-hash object in memory cell P1,
  4631   4633     ** delete it now and initialize P1 with an empty row-hash (a null pointer
  4632   4634     ** is an acceptable representation of an empty row-hash).
  4633   4635     */
  4634         -  if( (pIn1->flags & MEM_RowHash)==0 ){
  4635         -    sqlite3VdbeMemReleaseExternal(pIn1);
  4636         -    pIn1->u.pRowHash = 0;
  4637         -    pIn1->flags = MEM_RowHash;
         4636  +  if( (pIn1->flags & MEM_RowSet)==0 ){
         4637  +    sqlite3VdbeMemSetRowSet(pIn1);
         4638  +    if( (pIn1->flags & MEM_RowSet)==0 ) goto no_mem;
  4638   4639     }
  4639   4640   
  4640   4641     assert( pOp->p4type==P4_INT32 );
  4641   4642     if( iSet ){
  4642   4643       int exists;
  4643         -    rc = sqlite3RowhashTest(pIn1->u.pRowHash, pOp->p4.i, pIn3->u.i, &exists);
         4644  +    exists = sqlite3RowSetTest(pIn1->u.pRowSet, iSet>=0 ? iSet & 0xf : 0xff,
         4645  +                               pIn3->u.i);
  4644   4646       if( exists ){
  4645   4647         pc = pOp->p2 - 1;
  4646   4648         break;
  4647   4649       }
  4648   4650     }
  4649   4651     if( iSet>=0 ){
  4650         -    rc = sqlite3RowhashInsert(db, &pIn1->u.pRowHash, pIn3->u.i);
         4652  +    sqlite3RowSetInsert(pIn1->u.pRowSet, pIn3->u.i);
  4651   4653     }
  4652   4654     break;
  4653   4655   }
  4654   4656   
  4655   4657   
  4656   4658   #ifndef SQLITE_OMIT_TRIGGER
  4657   4659   /* Opcode: ContextPush * * *