1/*
2** 2003 Feb 4
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** $Id$
13**
14** This file implements an in-core database using Red-Black balanced
15** binary trees.
16**
17** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC.
18*/
19#include "btree.h"
20#include "sqliteInt.h"
21#include <assert.h>
22
23/*
24** Omit this whole file if the SQLITE_OMIT_INMEMORYDB macro is
25** defined.  This allows a lot of code to be omitted for installations
26** that do not need it.
27*/
28#ifndef SQLITE_OMIT_INMEMORYDB
29
30
31typedef struct BtRbTree BtRbTree;
32typedef struct BtRbNode BtRbNode;
33typedef struct BtRollbackOp BtRollbackOp;
34typedef struct Rbtree Rbtree;
35typedef struct RbtCursor RbtCursor;
36
37/* Forward declarations */
38static BtOps sqliteRbtreeOps;
39static BtCursorOps sqliteRbtreeCursorOps;
40
41/*
42 * During each transaction (or checkpoint), a linked-list of
43 * "rollback-operations" is accumulated. If the transaction is rolled back,
44 * then the list of operations must be executed (to restore the database to
45 * it's state before the transaction started). If the transaction is to be
46 * committed, just delete the list.
47 *
48 * Each operation is represented as follows, depending on the value of eOp:
49 *
50 * ROLLBACK_INSERT  ->  Need to insert (pKey, pData) into table iTab.
51 * ROLLBACK_DELETE  ->  Need to delete the record (pKey) into table iTab.
52 * ROLLBACK_CREATE  ->  Need to create table iTab.
53 * ROLLBACK_DROP    ->  Need to drop table iTab.
54 */
55struct BtRollbackOp {
56  u8 eOp;
57  int iTab;
58  int nKey;
59  void *pKey;
60  int nData;
61  void *pData;
62  BtRollbackOp *pNext;
63};
64
65/*
66** Legal values for BtRollbackOp.eOp:
67*/
68#define ROLLBACK_INSERT 1 /* Insert a record */
69#define ROLLBACK_DELETE 2 /* Delete a record */
70#define ROLLBACK_CREATE 3 /* Create a table */
71#define ROLLBACK_DROP   4 /* Drop a table */
72
73struct Rbtree {
74  BtOps *pOps;    /* Function table */
75  int aMetaData[SQLITE_N_BTREE_META];
76
77  int next_idx;   /* next available table index */
78  Hash tblHash;   /* All created tables, by index */
79  u8 isAnonymous; /* True if this Rbtree is to be deleted when closed */
80  u8 eTransState; /* State of this Rbtree wrt transactions */
81
82  BtRollbackOp *pTransRollback;
83  BtRollbackOp *pCheckRollback;
84  BtRollbackOp *pCheckRollbackTail;
85};
86
87/*
88** Legal values for Rbtree.eTransState.
89*/
90#define TRANS_NONE           0  /* No transaction is in progress */
91#define TRANS_INTRANSACTION  1  /* A transaction is in progress */
92#define TRANS_INCHECKPOINT   2  /* A checkpoint is in progress  */
93#define TRANS_ROLLBACK       3  /* We are currently rolling back a checkpoint or
94                                 * transaction. */
95
96struct RbtCursor {
97  BtCursorOps *pOps;        /* Function table */
98  Rbtree    *pRbtree;
99  BtRbTree *pTree;
100  int       iTree;          /* Index of pTree in pRbtree */
101  BtRbNode *pNode;
102  RbtCursor *pShared;       /* List of all cursors on the same Rbtree */
103  u8 eSkip;                 /* Determines if next step operation is a no-op */
104  u8 wrFlag;                /* True if this cursor is open for writing */
105};
106
107/*
108** Legal values for RbtCursor.eSkip.
109*/
110#define SKIP_NONE     0   /* Always step the cursor */
111#define SKIP_NEXT     1   /* The next sqliteRbtreeNext() is a no-op */
112#define SKIP_PREV     2   /* The next sqliteRbtreePrevious() is a no-op */
113#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */
114
115struct BtRbTree {
116  RbtCursor *pCursors;     /* All cursors pointing to this tree */
117  BtRbNode *pHead;         /* Head of the tree, or NULL */
118};
119
120struct BtRbNode {
121  int nKey;
122  void *pKey;
123  int nData;
124  void *pData;
125  u8 isBlack;        /* true for a black node, 0 for a red node */
126  BtRbNode *pParent; /* Nodes parent node, NULL for the tree head */
127  BtRbNode *pLeft;   /* Nodes left child, or NULL */
128  BtRbNode *pRight;  /* Nodes right child, or NULL */
129
130  int nBlackHeight;  /* Only used during the red-black integrity check */
131};
132
133/* Forward declarations */
134static int memRbtreeMoveto(
135  RbtCursor* pCur,
136  const void *pKey,
137  int nKey,
138  int *pRes
139);
140static int memRbtreeClearTable(Rbtree* tree, int n);
141static int memRbtreeNext(RbtCursor* pCur, int *pRes);
142static int memRbtreeLast(RbtCursor* pCur, int *pRes);
143static int memRbtreePrevious(RbtCursor* pCur, int *pRes);
144
145
146/*
147** This routine checks all cursors that point to the same table
148** as pCur points to.  If any of those cursors were opened with
149** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
150** cursors point to the same table were opened with wrFlag==1
151** then this routine returns SQLITE_OK.
152**
153** In addition to checking for read-locks (where a read-lock
154** means a cursor opened with wrFlag==0) this routine also NULLs
155** out the pNode field of all other cursors.
156** This is necessary because an insert
157** or delete might change erase the node out from under
158** another cursor.
159*/
160static int checkReadLocks(RbtCursor *pCur){
161  RbtCursor *p;
162  assert( pCur->wrFlag );
163  for(p=pCur->pTree->pCursors; p; p=p->pShared){
164    if( p!=pCur ){
165      if( p->wrFlag==0 ) return SQLITE_LOCKED;
166      p->pNode = 0;
167    }
168  }
169  return SQLITE_OK;
170}
171
172/*
173 * The key-compare function for the red-black trees. Returns as follows:
174 *
175 * (key1 < key2)             -1
176 * (key1 == key2)             0
177 * (key1 > key2)              1
178 *
179 * Keys are compared using memcmp(). If one key is an exact prefix of the
180 * other, then the shorter key is less than the longer key.
181 */
182static int key_compare(void const*pKey1, int nKey1, void const*pKey2, int nKey2)
183{
184  int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2);
185  if( mcmp == 0){
186    if( nKey1 == nKey2 ) return 0;
187    return ((nKey1 < nKey2)?-1:1);
188  }
189  return ((mcmp>0)?1:-1);
190}
191
192/*
193 * Perform the LEFT-rotate transformation on node X of tree pTree. This
194 * transform is part of the red-black balancing code.
195 *
196 *        |                   |
197 *        X                   Y
198 *       / \                 / \
199 *      a   Y               X   c
200 *         / \             / \
201 *        b   c           a   b
202 *
203 *      BEFORE              AFTER
204 */
205static void leftRotate(BtRbTree *pTree, BtRbNode *pX)
206{
207  BtRbNode *pY;
208  BtRbNode *pb;
209  pY = pX->pRight;
210  pb = pY->pLeft;
211
212  pY->pParent = pX->pParent;
213  if( pX->pParent ){
214    if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
215    else pX->pParent->pRight = pY;
216  }
217  pY->pLeft = pX;
218  pX->pParent = pY;
219  pX->pRight = pb;
220  if( pb ) pb->pParent = pX;
221  if( pTree->pHead == pX ) pTree->pHead = pY;
222}
223
224/*
225 * Perform the RIGHT-rotate transformation on node X of tree pTree. This
226 * transform is part of the red-black balancing code.
227 *
228 *        |                   |
229 *        X                   Y
230 *       / \                 / \
231 *      Y   c               a   X
232 *     / \                     / \
233 *    a   b                   b   c
234 *
235 *      BEFORE              AFTER
236 */
237static void rightRotate(BtRbTree *pTree, BtRbNode *pX)
238{
239  BtRbNode *pY;
240  BtRbNode *pb;
241  pY = pX->pLeft;
242  pb = pY->pRight;
243
244  pY->pParent = pX->pParent;
245  if( pX->pParent ){
246    if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
247    else pX->pParent->pRight = pY;
248  }
249  pY->pRight = pX;
250  pX->pParent = pY;
251  pX->pLeft = pb;
252  if( pb ) pb->pParent = pX;
253  if( pTree->pHead == pX ) pTree->pHead = pY;
254}
255
256/*
257 * A string-manipulation helper function for check_redblack_tree(). If (orig ==
258 * NULL) a copy of val is returned. If (orig != NULL) then a copy of the *
259 * concatenation of orig and val is returned. The original orig is deleted
260 * (using sqliteFree()).
261 */
262static char *append_val(char * orig, char const * val){
263  char *z;
264  if( !orig ){
265    z = sqliteStrDup( val );
266  } else{
267    z = 0;
268    sqliteSetString(&z, orig, val, (char*)0);
269    sqliteFree( orig );
270  }
271  return z;
272}
273
274/*
275 * Append a string representation of the entire node to orig and return it.
276 * This is used to produce debugging information if check_redblack_tree() finds
277 * a problem with a red-black binary tree.
278 */
279static char *append_node(char * orig, BtRbNode *pNode, int indent)
280{
281  char buf[128];
282  int i;
283
284  for( i=0; i<indent; i++ ){
285      orig = append_val(orig, " ");
286  }
287
288  sprintf(buf, "%p", pNode);
289  orig = append_val(orig, buf);
290
291  if( pNode ){
292    indent += 3;
293    if( pNode->isBlack ){
294      orig = append_val(orig, " B \n");
295    }else{
296      orig = append_val(orig, " R \n");
297    }
298    orig = append_node( orig, pNode->pLeft, indent );
299    orig = append_node( orig, pNode->pRight, indent );
300  }else{
301    orig = append_val(orig, "\n");
302  }
303  return orig;
304}
305
306/*
307 * Print a representation of a node to stdout. This function is only included
308 * so you can call it from within a debugger if things get really bad.  It
309 * is not called from anyplace in the code.
310 */
311static void print_node(BtRbNode *pNode)
312{
313    char * str = append_node(0, pNode, 0);
314    printf("%s", str);
315
316    /* Suppress a warning message about print_node() being unused */
317    (void)print_node;
318}
319
320/*
321 * Check the following properties of the red-black tree:
322 * (1) - If a node is red, both of it's children are black
323 * (2) - Each path from a given node to a leaf (NULL) node passes thru the
324 *       same number of black nodes
325 *
326 * If there is a problem, append a description (using append_val() ) to *msg.
327 */
328static void check_redblack_tree(BtRbTree * tree, char ** msg)
329{
330  BtRbNode *pNode;
331
332  /* 0 -> came from parent
333   * 1 -> came from left
334   * 2 -> came from right */
335  int prev_step = 0;
336
337  pNode = tree->pHead;
338  while( pNode ){
339    switch( prev_step ){
340      case 0:
341        if( pNode->pLeft ){
342          pNode = pNode->pLeft;
343        }else{
344          prev_step = 1;
345        }
346        break;
347      case 1:
348        if( pNode->pRight ){
349          pNode = pNode->pRight;
350          prev_step = 0;
351        }else{
352          prev_step = 2;
353        }
354        break;
355      case 2:
356        /* Check red-black property (1) */
357        if( !pNode->isBlack &&
358            ( (pNode->pLeft && !pNode->pLeft->isBlack) ||
359              (pNode->pRight && !pNode->pRight->isBlack) )
360          ){
361          char buf[128];
362          sprintf(buf, "Red node with red child at %p\n", pNode);
363          *msg = append_val(*msg, buf);
364          *msg = append_node(*msg, tree->pHead, 0);
365          *msg = append_val(*msg, "\n");
366        }
367
368        /* Check red-black property (2) */
369        {
370          int leftHeight = 0;
371          int rightHeight = 0;
372          if( pNode->pLeft ){
373            leftHeight += pNode->pLeft->nBlackHeight;
374            leftHeight += (pNode->pLeft->isBlack?1:0);
375          }
376          if( pNode->pRight ){
377            rightHeight += pNode->pRight->nBlackHeight;
378            rightHeight += (pNode->pRight->isBlack?1:0);
379          }
380          if( leftHeight != rightHeight ){
381            char buf[128];
382            sprintf(buf, "Different black-heights at %p\n", pNode);
383            *msg = append_val(*msg, buf);
384            *msg = append_node(*msg, tree->pHead, 0);
385            *msg = append_val(*msg, "\n");
386          }
387          pNode->nBlackHeight = leftHeight;
388        }
389
390        if( pNode->pParent ){
391          if( pNode == pNode->pParent->pLeft ) prev_step = 1;
392          else prev_step = 2;
393        }
394        pNode = pNode->pParent;
395        break;
396      default: assert(0);
397    }
398  }
399}
400
401/*
402 * Node pX has just been inserted into pTree (by code in sqliteRbtreeInsert()).
403 * It is possible that pX is a red node with a red parent, which is a violation
404 * of the red-black tree properties. This function performs rotations and
405 * color changes to rebalance the tree
406 */
407static void do_insert_balancing(BtRbTree *pTree, BtRbNode *pX)
408{
409  /* In the first iteration of this loop, pX points to the red node just
410   * inserted in the tree. If the parent of pX exists (pX is not the root
411   * node) and is red, then the properties of the red-black tree are
412   * violated.
413   *
414   * At the start of any subsequent iterations, pX points to a red node
415   * with a red parent. In all other respects the tree is a legal red-black
416   * binary tree. */
417  while( pX != pTree->pHead && !pX->pParent->isBlack ){
418    BtRbNode *pUncle;
419    BtRbNode *pGrandparent;
420
421    /* Grandparent of pX must exist and must be black. */
422    pGrandparent = pX->pParent->pParent;
423    assert( pGrandparent );
424    assert( pGrandparent->isBlack );
425
426    /* Uncle of pX may or may not exist. */
427    if( pX->pParent == pGrandparent->pLeft )
428      pUncle = pGrandparent->pRight;
429    else
430      pUncle = pGrandparent->pLeft;
431
432    /* If the uncle of pX exists and is red, we do the following:
433     *       |                 |
434     *      G(b)              G(r)
435     *      /  \              /  \
436     *   U(r)   P(r)       U(b)  P(b)
437     *            \                \
438     *           X(r)              X(r)
439     *
440     *     BEFORE             AFTER
441     * pX is then set to G. If the parent of G is red, then the while loop
442     * will run again.  */
443    if( pUncle && !pUncle->isBlack ){
444      pGrandparent->isBlack = 0;
445      pUncle->isBlack = 1;
446      pX->pParent->isBlack = 1;
447      pX = pGrandparent;
448    }else{
449
450      if( pX->pParent == pGrandparent->pLeft ){
451        if( pX == pX->pParent->pRight ){
452          /* If pX is a right-child, do the following transform, essentially
453           * to change pX into a left-child:
454           *       |                  |
455           *      G(b)               G(b)
456           *      /  \               /  \
457           *   P(r)   U(b)        X(r)  U(b)
458           *      \                /
459           *     X(r)            P(r) <-- new X
460           *
461           *     BEFORE             AFTER
462           */
463          pX = pX->pParent;
464          leftRotate(pTree, pX);
465        }
466
467        /* Do the following transform, which balances the tree :)
468         *       |                  |
469         *      G(b)               P(b)
470         *      /  \               /  \
471         *   P(r)   U(b)        X(r)  G(r)
472         *    /                         \
473         *  X(r)                        U(b)
474         *
475         *     BEFORE             AFTER
476         */
477        assert( pGrandparent == pX->pParent->pParent );
478        pGrandparent->isBlack = 0;
479        pX->pParent->isBlack = 1;
480        rightRotate( pTree, pGrandparent );
481
482      }else{
483        /* This code is symetric to the illustrated case above. */
484        if( pX == pX->pParent->pLeft ){
485          pX = pX->pParent;
486          rightRotate(pTree, pX);
487        }
488        assert( pGrandparent == pX->pParent->pParent );
489        pGrandparent->isBlack = 0;
490        pX->pParent->isBlack = 1;
491        leftRotate( pTree, pGrandparent );
492      }
493    }
494  }
495  pTree->pHead->isBlack = 1;
496}
497
498/*
499 * A child of pParent, which in turn had child pX, has just been removed from
500 * pTree (the figure below depicts the operation, Z is being removed). pParent
501 * or pX, or both may be NULL.
502 *                |           |
503 *                P           P
504 *               / \         / \
505 *              Z           X
506 *             / \
507 *            X  nil
508 *
509 * This function is only called if Z was black. In this case the red-black tree
510 * properties have been violated, and pX has an "extra black". This function
511 * performs rotations and color-changes to re-balance the tree.
512 */
513static
514void do_delete_balancing(BtRbTree *pTree, BtRbNode *pX, BtRbNode *pParent)
515{
516  BtRbNode *pSib;
517
518  /* TODO: Comment this code! */
519  while( pX != pTree->pHead && (!pX || pX->isBlack) ){
520    if( pX == pParent->pLeft ){
521      pSib = pParent->pRight;
522      if( pSib && !(pSib->isBlack) ){
523        pSib->isBlack = 1;
524        pParent->isBlack = 0;
525        leftRotate(pTree, pParent);
526        pSib = pParent->pRight;
527      }
528      if( !pSib ){
529        pX = pParent;
530      }else if(
531          (!pSib->pLeft  || pSib->pLeft->isBlack) &&
532          (!pSib->pRight || pSib->pRight->isBlack) ) {
533        pSib->isBlack = 0;
534        pX = pParent;
535      }else{
536        if( (!pSib->pRight || pSib->pRight->isBlack) ){
537          if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
538          pSib->isBlack = 0;
539          rightRotate( pTree, pSib );
540          pSib = pParent->pRight;
541        }
542        pSib->isBlack = pParent->isBlack;
543        pParent->isBlack = 1;
544        if( pSib->pRight ) pSib->pRight->isBlack = 1;
545        leftRotate(pTree, pParent);
546        pX = pTree->pHead;
547      }
548    }else{
549      pSib = pParent->pLeft;
550      if( pSib && !(pSib->isBlack) ){
551        pSib->isBlack = 1;
552        pParent->isBlack = 0;
553        rightRotate(pTree, pParent);
554        pSib = pParent->pLeft;
555      }
556      if( !pSib ){
557        pX = pParent;
558      }else if(
559          (!pSib->pLeft  || pSib->pLeft->isBlack) &&
560          (!pSib->pRight || pSib->pRight->isBlack) ){
561        pSib->isBlack = 0;
562        pX = pParent;
563      }else{
564        if( (!pSib->pLeft || pSib->pLeft->isBlack) ){
565          if( pSib->pRight ) pSib->pRight->isBlack = 1;
566          pSib->isBlack = 0;
567          leftRotate( pTree, pSib );
568          pSib = pParent->pLeft;
569        }
570        pSib->isBlack = pParent->isBlack;
571        pParent->isBlack = 1;
572        if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
573        rightRotate(pTree, pParent);
574        pX = pTree->pHead;
575      }
576    }
577    pParent = pX->pParent;
578  }
579  if( pX ) pX->isBlack = 1;
580}
581
582/*
583 * Create table n in tree pRbtree. Table n must not exist.
584 */
585static void btreeCreateTable(Rbtree* pRbtree, int n)
586{
587  BtRbTree *pNewTbl = sqliteMalloc(sizeof(BtRbTree));
588  sqliteHashInsert(&pRbtree->tblHash, 0, n, pNewTbl);
589}
590
591/*
592 * Log a single "rollback-op" for the given Rbtree. See comments for struct
593 * BtRollbackOp.
594 */
595static void btreeLogRollbackOp(Rbtree* pRbtree, BtRollbackOp *pRollbackOp)
596{
597  assert( pRbtree->eTransState == TRANS_INCHECKPOINT ||
598      pRbtree->eTransState == TRANS_INTRANSACTION );
599  if( pRbtree->eTransState == TRANS_INTRANSACTION ){
600    pRollbackOp->pNext = pRbtree->pTransRollback;
601    pRbtree->pTransRollback = pRollbackOp;
602  }
603  if( pRbtree->eTransState == TRANS_INCHECKPOINT ){
604    if( !pRbtree->pCheckRollback ){
605      pRbtree->pCheckRollbackTail = pRollbackOp;
606    }
607    pRollbackOp->pNext = pRbtree->pCheckRollback;
608    pRbtree->pCheckRollback = pRollbackOp;
609  }
610}
611
612int sqliteRbtreeOpen(
613  const char *zFilename,
614  int mode,
615  int nPg,
616  Btree **ppBtree
617){
618  Rbtree **ppRbtree = (Rbtree**)ppBtree;
619  *ppRbtree = (Rbtree *)sqliteMalloc(sizeof(Rbtree));
620  if( sqlite_malloc_failed ) goto open_no_mem;
621  sqliteHashInit(&(*ppRbtree)->tblHash, SQLITE_HASH_INT, 0);
622
623  /* Create a binary tree for the SQLITE_MASTER table at location 2 */
624  btreeCreateTable(*ppRbtree, 2);
625  if( sqlite_malloc_failed ) goto open_no_mem;
626  (*ppRbtree)->next_idx = 3;
627  (*ppRbtree)->pOps = &sqliteRbtreeOps;
628  /* Set file type to 4; this is so that "attach ':memory:' as ...."  does not
629  ** think that the database in uninitialised and refuse to attach
630  */
631  (*ppRbtree)->aMetaData[2] = 4;
632
633  return SQLITE_OK;
634
635open_no_mem:
636  *ppBtree = 0;
637  return SQLITE_NOMEM;
638}
639
640/*
641 * Create a new table in the supplied Rbtree. Set *n to the new table number.
642 * Return SQLITE_OK if the operation is a success.
643 */
644static int memRbtreeCreateTable(Rbtree* tree, int* n)
645{
646  assert( tree->eTransState != TRANS_NONE );
647
648  *n = tree->next_idx++;
649  btreeCreateTable(tree, *n);
650  if( sqlite_malloc_failed ) return SQLITE_NOMEM;
651
652  /* Set up the rollback structure (if we are not doing this as part of a
653   * rollback) */
654  if( tree->eTransState != TRANS_ROLLBACK ){
655    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
656    if( pRollbackOp==0 ) return SQLITE_NOMEM;
657    pRollbackOp->eOp = ROLLBACK_DROP;
658    pRollbackOp->iTab = *n;
659    btreeLogRollbackOp(tree, pRollbackOp);
660  }
661
662  return SQLITE_OK;
663}
664
665/*
666 * Delete table n from the supplied Rbtree.
667 */
668static int memRbtreeDropTable(Rbtree* tree, int n)
669{
670  BtRbTree *pTree;
671  assert( tree->eTransState != TRANS_NONE );
672
673  memRbtreeClearTable(tree, n);
674  pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
675  assert(pTree);
676  assert( pTree->pCursors==0 );
677  sqliteFree(pTree);
678
679  if( tree->eTransState != TRANS_ROLLBACK ){
680    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
681    if( pRollbackOp==0 ) return SQLITE_NOMEM;
682    pRollbackOp->eOp = ROLLBACK_CREATE;
683    pRollbackOp->iTab = n;
684    btreeLogRollbackOp(tree, pRollbackOp);
685  }
686
687  return SQLITE_OK;
688}
689
690static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey,
691                                 int nIgnore, int *pRes)
692{
693  assert(pCur);
694
695  if( !pCur->pNode ) {
696    *pRes = -1;
697  } else {
698    if( (pCur->pNode->nKey - nIgnore) < 0 ){
699      *pRes = -1;
700    }else{
701      *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore,
702          pKey, nKey);
703    }
704  }
705  return SQLITE_OK;
706}
707
708/*
709 * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
710 * parameter indicates that the cursor is open for writing.
711 *
712 * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
713 */
714static int memRbtreeCursor(
715  Rbtree* tree,
716  int iTable,
717  int wrFlag,
718  RbtCursor **ppCur
719){
720  RbtCursor *pCur;
721  assert(tree);
722  pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));
723  if( sqlite_malloc_failed ) return SQLITE_NOMEM;
724  pCur->pTree  = sqliteHashFind(&tree->tblHash, 0, iTable);
725  assert( pCur->pTree );
726  pCur->pRbtree = tree;
727  pCur->iTree  = iTable;
728  pCur->pOps = &sqliteRbtreeCursorOps;
729  pCur->wrFlag = wrFlag;
730  pCur->pShared = pCur->pTree->pCursors;
731  pCur->pTree->pCursors = pCur;
732
733  assert( (*ppCur)->pTree );
734  return SQLITE_OK;
735}
736
737/*
738 * Insert a new record into the Rbtree.  The key is given by (pKey,nKey)
739 * and the data is given by (pData,nData).  The cursor is used only to
740 * define what database the record should be inserted into.  The cursor
741 * is left pointing at the new record.
742 *
743 * If the key exists already in the tree, just replace the data.
744 */
745static int memRbtreeInsert(
746  RbtCursor* pCur,
747  const void *pKey,
748  int nKey,
749  const void *pDataInput,
750  int nData
751){
752  void * pData;
753  int match;
754
755  /* It is illegal to call sqliteRbtreeInsert() if we are
756  ** not in a transaction */
757  assert( pCur->pRbtree->eTransState != TRANS_NONE );
758
759  /* Make sure some other cursor isn't trying to read this same table */
760  if( checkReadLocks(pCur) ){
761    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
762  }
763
764  /* Take a copy of the input data now, in case we need it for the
765   * replace case */
766  pData = sqliteMallocRaw(nData);
767  if( sqlite_malloc_failed ) return SQLITE_NOMEM;
768  memcpy(pData, pDataInput, nData);
769
770  /* Move the cursor to a node near the key to be inserted. If the key already
771   * exists in the table, then (match == 0). In this case we can just replace
772   * the data associated with the entry, we don't need to manipulate the tree.
773   *
774   * If there is no exact match, then the cursor points at what would be either
775   * the predecessor (match == -1) or successor (match == 1) of the
776   * searched-for key, were it to be inserted. The new node becomes a child of
777   * this node.
778   *
779   * The new node is initially red.
780   */
781  memRbtreeMoveto( pCur, pKey, nKey, &match);
782  if( match ){
783    BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode));
784    if( pNode==0 ) return SQLITE_NOMEM;
785    pNode->nKey = nKey;
786    pNode->pKey = sqliteMallocRaw(nKey);
787    if( sqlite_malloc_failed ) return SQLITE_NOMEM;
788    memcpy(pNode->pKey, pKey, nKey);
789    pNode->nData = nData;
790    pNode->pData = pData;
791    if( pCur->pNode ){
792      switch( match ){
793        case -1:
794          assert( !pCur->pNode->pRight );
795          pNode->pParent = pCur->pNode;
796          pCur->pNode->pRight = pNode;
797          break;
798        case 1:
799          assert( !pCur->pNode->pLeft );
800          pNode->pParent = pCur->pNode;
801          pCur->pNode->pLeft = pNode;
802          break;
803        default:
804          assert(0);
805      }
806    }else{
807      pCur->pTree->pHead = pNode;
808    }
809
810    /* Point the cursor at the node just inserted, as per SQLite requirements */
811    pCur->pNode = pNode;
812
813    /* A new node has just been inserted, so run the balancing code */
814    do_insert_balancing(pCur->pTree, pNode);
815
816    /* Set up a rollback-op in case we have to roll this operation back */
817    if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
818      BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
819      if( pOp==0 ) return SQLITE_NOMEM;
820      pOp->eOp = ROLLBACK_DELETE;
821      pOp->iTab = pCur->iTree;
822      pOp->nKey = pNode->nKey;
823      pOp->pKey = sqliteMallocRaw( pOp->nKey );
824      if( sqlite_malloc_failed ) return SQLITE_NOMEM;
825      memcpy( pOp->pKey, pNode->pKey, pOp->nKey );
826      btreeLogRollbackOp(pCur->pRbtree, pOp);
827    }
828
829  }else{
830    /* No need to insert a new node in the tree, as the key already exists.
831     * Just clobber the current nodes data. */
832
833    /* Set up a rollback-op in case we have to roll this operation back */
834    if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
835      BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
836      if( pOp==0 ) return SQLITE_NOMEM;
837      pOp->iTab = pCur->iTree;
838      pOp->nKey = pCur->pNode->nKey;
839      pOp->pKey = sqliteMallocRaw( pOp->nKey );
840      if( sqlite_malloc_failed ) return SQLITE_NOMEM;
841      memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey );
842      pOp->nData = pCur->pNode->nData;
843      pOp->pData = pCur->pNode->pData;
844      pOp->eOp = ROLLBACK_INSERT;
845      btreeLogRollbackOp(pCur->pRbtree, pOp);
846    }else{
847      sqliteFree( pCur->pNode->pData );
848    }
849
850    /* Actually clobber the nodes data */
851    pCur->pNode->pData = pData;
852    pCur->pNode->nData = nData;
853  }
854
855  return SQLITE_OK;
856}
857
858/* Move the cursor so that it points to an entry near pKey.
859** Return a success code.
860**
861**     *pRes<0      The cursor is left pointing at an entry that
862**                  is smaller than pKey or if the table is empty
863**                  and the cursor is therefore left point to nothing.
864**
865**     *pRes==0     The cursor is left pointing at an entry that
866**                  exactly matches pKey.
867**
868**     *pRes>0      The cursor is left pointing at an entry that
869**                  is larger than pKey.
870*/
871static int memRbtreeMoveto(
872  RbtCursor* pCur,
873  const void *pKey,
874  int nKey,
875  int *pRes
876){
877  BtRbNode *pTmp = 0;
878
879  pCur->pNode = pCur->pTree->pHead;
880  *pRes = -1;
881  while( pCur->pNode && *pRes ) {
882    *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey);
883    pTmp = pCur->pNode;
884    switch( *pRes ){
885      case 1:    /* cursor > key */
886        pCur->pNode = pCur->pNode->pLeft;
887        break;
888      case -1:   /* cursor < key */
889        pCur->pNode = pCur->pNode->pRight;
890        break;
891    }
892  }
893
894  /* If (pCur->pNode == NULL), then we have failed to find a match. Set
895   * pCur->pNode to pTmp, which is either NULL (if the tree is empty) or the
896   * last node traversed in the search. In either case the relation ship
897   * between pTmp and the searched for key is already stored in *pRes. pTmp is
898   * either the successor or predecessor of the key we tried to move to. */
899  if( !pCur->pNode ) pCur->pNode = pTmp;
900  pCur->eSkip = SKIP_NONE;
901
902  return SQLITE_OK;
903}
904
905
906/*
907** Delete the entry that the cursor is pointing to.
908**
909** The cursor is left pointing at either the next or the previous
910** entry.  If the cursor is left pointing to the next entry, then
911** the pCur->eSkip flag is set to SKIP_NEXT which forces the next call to
912** sqliteRbtreeNext() to be a no-op.  That way, you can always call
913** sqliteRbtreeNext() after a delete and the cursor will be left
914** pointing to the first entry after the deleted entry.  Similarly,
915** pCur->eSkip is set to SKIP_PREV is the cursor is left pointing to
916** the entry prior to the deleted entry so that a subsequent call to
917** sqliteRbtreePrevious() will always leave the cursor pointing at the
918** entry immediately before the one that was deleted.
919*/
920static int memRbtreeDelete(RbtCursor* pCur)
921{
922  BtRbNode *pZ;      /* The one being deleted */
923  BtRbNode *pChild;  /* The child of the spliced out node */
924
925  /* It is illegal to call sqliteRbtreeDelete() if we are
926  ** not in a transaction */
927  assert( pCur->pRbtree->eTransState != TRANS_NONE );
928
929  /* Make sure some other cursor isn't trying to read this same table */
930  if( checkReadLocks(pCur) ){
931    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
932  }
933
934  pZ = pCur->pNode;
935  if( !pZ ){
936    return SQLITE_OK;
937  }
938
939  /* If we are not currently doing a rollback, set up a rollback op for this
940   * deletion */
941  if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
942    BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
943    if( pOp==0 ) return SQLITE_NOMEM;
944    pOp->iTab = pCur->iTree;
945    pOp->nKey = pZ->nKey;
946    pOp->pKey = pZ->pKey;
947    pOp->nData = pZ->nData;
948    pOp->pData = pZ->pData;
949    pOp->eOp = ROLLBACK_INSERT;
950    btreeLogRollbackOp(pCur->pRbtree, pOp);
951  }
952
953  /* First do a standard binary-tree delete (node pZ is to be deleted). How
954   * to do this depends on how many children pZ has:
955   *
956   * If pZ has no children or one child, then splice out pZ.  If pZ has two
957   * children, splice out the successor of pZ and replace the key and data of
958   * pZ with the key and data of the spliced out successor.  */
959  if( pZ->pLeft && pZ->pRight ){
960    BtRbNode *pTmp;
961    int dummy;
962    pCur->eSkip = SKIP_NONE;
963    memRbtreeNext(pCur, &dummy);
964    assert( dummy == 0 );
965    if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
966      sqliteFree(pZ->pKey);
967      sqliteFree(pZ->pData);
968    }
969    pZ->pData = pCur->pNode->pData;
970    pZ->nData = pCur->pNode->nData;
971    pZ->pKey = pCur->pNode->pKey;
972    pZ->nKey = pCur->pNode->nKey;
973    pTmp = pZ;
974    pZ = pCur->pNode;
975    pCur->pNode = pTmp;
976    pCur->eSkip = SKIP_NEXT;
977  }else{
978    int res;
979    pCur->eSkip = SKIP_NONE;
980    memRbtreeNext(pCur, &res);
981    pCur->eSkip = SKIP_NEXT;
982    if( res ){
983      memRbtreeLast(pCur, &res);
984      memRbtreePrevious(pCur, &res);
985      pCur->eSkip = SKIP_PREV;
986    }
987    if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
988        sqliteFree(pZ->pKey);
989        sqliteFree(pZ->pData);
990    }
991  }
992
993  /* pZ now points at the node to be spliced out. This block does the
994   * splicing. */
995  {
996    BtRbNode **ppParentSlot = 0;
997    assert( !pZ->pLeft || !pZ->pRight ); /* pZ has at most one child */
998    pChild = ((pZ->pLeft)?pZ->pLeft:pZ->pRight);
999    if( pZ->pParent ){
1000      assert( pZ == pZ->pParent->pLeft || pZ == pZ->pParent->pRight );
1001      ppParentSlot = ((pZ == pZ->pParent->pLeft)
1002          ?&pZ->pParent->pLeft:&pZ->pParent->pRight);
1003      *ppParentSlot = pChild;
1004    }else{
1005      pCur->pTree->pHead = pChild;
1006    }
1007    if( pChild ) pChild->pParent = pZ->pParent;
1008  }
1009
1010  /* pZ now points at the spliced out node. pChild is the only child of pZ, or
1011   * NULL if pZ has no children. If pZ is black, and not the tree root, then we
1012   * will have violated the "same number of black nodes in every path to a
1013   * leaf" property of the red-black tree. The code in do_delete_balancing()
1014   * repairs this. */
1015  if( pZ->isBlack ){
1016    do_delete_balancing(pCur->pTree, pChild, pZ->pParent);
1017  }
1018
1019  sqliteFree(pZ);
1020  return SQLITE_OK;
1021}
1022
1023/*
1024 * Empty table n of the Rbtree.
1025 */
1026static int memRbtreeClearTable(Rbtree* tree, int n)
1027{
1028  BtRbTree *pTree;
1029  BtRbNode *pNode;
1030
1031  pTree = sqliteHashFind(&tree->tblHash, 0, n);
1032  assert(pTree);
1033
1034  pNode = pTree->pHead;
1035  while( pNode ){
1036    if( pNode->pLeft ){
1037      pNode = pNode->pLeft;
1038    }
1039    else if( pNode->pRight ){
1040      pNode = pNode->pRight;
1041    }
1042    else {
1043      BtRbNode *pTmp = pNode->pParent;
1044      if( tree->eTransState == TRANS_ROLLBACK ){
1045        sqliteFree( pNode->pKey );
1046        sqliteFree( pNode->pData );
1047      }else{
1048        BtRollbackOp *pRollbackOp = sqliteMallocRaw(sizeof(BtRollbackOp));
1049        if( pRollbackOp==0 ) return SQLITE_NOMEM;
1050        pRollbackOp->eOp = ROLLBACK_INSERT;
1051        pRollbackOp->iTab = n;
1052        pRollbackOp->nKey = pNode->nKey;
1053        pRollbackOp->pKey = pNode->pKey;
1054        pRollbackOp->nData = pNode->nData;
1055        pRollbackOp->pData = pNode->pData;
1056        btreeLogRollbackOp(tree, pRollbackOp);
1057      }
1058      sqliteFree( pNode );
1059      if( pTmp ){
1060        if( pTmp->pLeft == pNode ) pTmp->pLeft = 0;
1061        else if( pTmp->pRight == pNode ) pTmp->pRight = 0;
1062      }
1063      pNode = pTmp;
1064    }
1065  }
1066
1067  pTree->pHead = 0;
1068  return SQLITE_OK;
1069}
1070
1071static int memRbtreeFirst(RbtCursor* pCur, int *pRes)
1072{
1073  if( pCur->pTree->pHead ){
1074    pCur->pNode = pCur->pTree->pHead;
1075    while( pCur->pNode->pLeft ){
1076      pCur->pNode = pCur->pNode->pLeft;
1077    }
1078  }
1079  if( pCur->pNode ){
1080    *pRes = 0;
1081  }else{
1082    *pRes = 1;
1083  }
1084  pCur->eSkip = SKIP_NONE;
1085  return SQLITE_OK;
1086}
1087
1088static int memRbtreeLast(RbtCursor* pCur, int *pRes)
1089{
1090  if( pCur->pTree->pHead ){
1091    pCur->pNode = pCur->pTree->pHead;
1092    while( pCur->pNode->pRight ){
1093      pCur->pNode = pCur->pNode->pRight;
1094    }
1095  }
1096  if( pCur->pNode ){
1097    *pRes = 0;
1098  }else{
1099    *pRes = 1;
1100  }
1101  pCur->eSkip = SKIP_NONE;
1102  return SQLITE_OK;
1103}
1104
1105/*
1106** Advance the cursor to the next entry in the database.  If
1107** successful then set *pRes=0.  If the cursor
1108** was already pointing to the last entry in the database before
1109** this routine was called, then set *pRes=1.
1110*/
1111static int memRbtreeNext(RbtCursor* pCur, int *pRes)
1112{
1113  if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){
1114    if( pCur->pNode->pRight ){
1115      pCur->pNode = pCur->pNode->pRight;
1116      while( pCur->pNode->pLeft )
1117        pCur->pNode = pCur->pNode->pLeft;
1118    }else{
1119      BtRbNode * pX = pCur->pNode;
1120      pCur->pNode = pX->pParent;
1121      while( pCur->pNode && (pCur->pNode->pRight == pX) ){
1122        pX = pCur->pNode;
1123        pCur->pNode = pX->pParent;
1124      }
1125    }
1126  }
1127  pCur->eSkip = SKIP_NONE;
1128
1129  if( !pCur->pNode ){
1130    *pRes = 1;
1131  }else{
1132    *pRes = 0;
1133  }
1134
1135  return SQLITE_OK;
1136}
1137
1138static int memRbtreePrevious(RbtCursor* pCur, int *pRes)
1139{
1140  if( pCur->pNode && pCur->eSkip != SKIP_PREV ){
1141    if( pCur->pNode->pLeft ){
1142      pCur->pNode = pCur->pNode->pLeft;
1143      while( pCur->pNode->pRight )
1144        pCur->pNode = pCur->pNode->pRight;
1145    }else{
1146      BtRbNode * pX = pCur->pNode;
1147      pCur->pNode = pX->pParent;
1148      while( pCur->pNode && (pCur->pNode->pLeft == pX) ){
1149        pX = pCur->pNode;
1150        pCur->pNode = pX->pParent;
1151      }
1152    }
1153  }
1154  pCur->eSkip = SKIP_NONE;
1155
1156  if( !pCur->pNode ){
1157    *pRes = 1;
1158  }else{
1159    *pRes = 0;
1160  }
1161
1162  return SQLITE_OK;
1163}
1164
1165static int memRbtreeKeySize(RbtCursor* pCur, int *pSize)
1166{
1167  if( pCur->pNode ){
1168    *pSize = pCur->pNode->nKey;
1169  }else{
1170    *pSize = 0;
1171  }
1172  return SQLITE_OK;
1173}
1174
1175static int memRbtreeKey(RbtCursor* pCur, int offset, int amt, char *zBuf)
1176{
1177  if( !pCur->pNode ) return 0;
1178  if( !pCur->pNode->pKey || ((amt + offset) <= pCur->pNode->nKey) ){
1179    memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, amt);
1180  }else{
1181    memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, pCur->pNode->nKey-offset);
1182    amt = pCur->pNode->nKey-offset;
1183  }
1184  return amt;
1185}
1186
1187static int memRbtreeDataSize(RbtCursor* pCur, int *pSize)
1188{
1189  if( pCur->pNode ){
1190    *pSize = pCur->pNode->nData;
1191  }else{
1192    *pSize = 0;
1193  }
1194  return SQLITE_OK;
1195}
1196
1197static int memRbtreeData(RbtCursor *pCur, int offset, int amt, char *zBuf)
1198{
1199  if( !pCur->pNode ) return 0;
1200  if( (amt + offset) <= pCur->pNode->nData ){
1201    memcpy(zBuf, ((char*)pCur->pNode->pData)+offset, amt);
1202  }else{
1203    memcpy(zBuf, ((char*)pCur->pNode->pData)+offset ,pCur->pNode->nData-offset);
1204    amt = pCur->pNode->nData-offset;
1205  }
1206  return amt;
1207}
1208
1209static int memRbtreeCloseCursor(RbtCursor* pCur)
1210{
1211  if( pCur->pTree->pCursors==pCur ){
1212    pCur->pTree->pCursors = pCur->pShared;
1213  }else{
1214    RbtCursor *p = pCur->pTree->pCursors;
1215    while( p && p->pShared!=pCur ){ p = p->pShared; }
1216    assert( p!=0 );
1217    if( p ){
1218      p->pShared = pCur->pShared;
1219    }
1220  }
1221  sqliteFree(pCur);
1222  return SQLITE_OK;
1223}
1224
1225static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
1226{
1227  memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
1228  return SQLITE_OK;
1229}
1230
1231static int memRbtreeUpdateMeta(Rbtree* tree, int* aMeta)
1232{
1233  memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META );
1234  return SQLITE_OK;
1235}
1236
1237/*
1238 * Check that each table in the Rbtree meets the requirements for a red-black
1239 * binary tree. If an error is found, return an explanation of the problem in
1240 * memory obtained from sqliteMalloc(). Parameters aRoot and nRoot are ignored.
1241 */
1242static char *memRbtreeIntegrityCheck(Rbtree* tree, int* aRoot, int nRoot)
1243{
1244  char * msg = 0;
1245  HashElem *p;
1246
1247  for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){
1248    BtRbTree *pTree = sqliteHashData(p);
1249    check_redblack_tree(pTree, &msg);
1250  }
1251
1252  return msg;
1253}
1254
1255static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
1256{
1257  return SQLITE_OK;
1258}
1259
1260static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){
1261  return SQLITE_OK;
1262}
1263
1264static int memRbtreeBeginTrans(Rbtree* tree)
1265{
1266  if( tree->eTransState != TRANS_NONE )
1267    return SQLITE_ERROR;
1268
1269  assert( tree->pTransRollback == 0 );
1270  tree->eTransState = TRANS_INTRANSACTION;
1271  return SQLITE_OK;
1272}
1273
1274/*
1275** Delete a linked list of BtRollbackOp structures.
1276*/
1277static void deleteRollbackList(BtRollbackOp *pOp){
1278  while( pOp ){
1279    BtRollbackOp *pTmp = pOp->pNext;
1280    sqliteFree(pOp->pData);
1281    sqliteFree(pOp->pKey);
1282    sqliteFree(pOp);
1283    pOp = pTmp;
1284  }
1285}
1286
1287static int memRbtreeCommit(Rbtree* tree){
1288  /* Just delete pTransRollback and pCheckRollback */
1289  deleteRollbackList(tree->pCheckRollback);
1290  deleteRollbackList(tree->pTransRollback);
1291  tree->pTransRollback = 0;
1292  tree->pCheckRollback = 0;
1293  tree->pCheckRollbackTail = 0;
1294  tree->eTransState = TRANS_NONE;
1295  return SQLITE_OK;
1296}
1297
1298/*
1299 * Close the supplied Rbtree. Delete everything associated with it.
1300 */
1301static int memRbtreeClose(Rbtree* tree)
1302{
1303  HashElem *p;
1304  memRbtreeCommit(tree);
1305  while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){
1306    tree->eTransState = TRANS_ROLLBACK;
1307    memRbtreeDropTable(tree, sqliteHashKeysize(p));
1308  }
1309  sqliteHashClear(&tree->tblHash);
1310  sqliteFree(tree);
1311  return SQLITE_OK;
1312}
1313
1314/*
1315 * Execute and delete the supplied rollback-list on pRbtree.
1316 */
1317static void execute_rollback_list(Rbtree *pRbtree, BtRollbackOp *pList)
1318{
1319  BtRollbackOp *pTmp;
1320  RbtCursor cur;
1321  int res;
1322
1323  cur.pRbtree = pRbtree;
1324  cur.wrFlag = 1;
1325  while( pList ){
1326    switch( pList->eOp ){
1327      case ROLLBACK_INSERT:
1328        cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
1329        assert(cur.pTree);
1330        cur.iTree  = pList->iTab;
1331        cur.eSkip  = SKIP_NONE;
1332        memRbtreeInsert( &cur, pList->pKey,
1333            pList->nKey, pList->pData, pList->nData );
1334        break;
1335      case ROLLBACK_DELETE:
1336        cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
1337        assert(cur.pTree);
1338        cur.iTree  = pList->iTab;
1339        cur.eSkip  = SKIP_NONE;
1340        memRbtreeMoveto(&cur, pList->pKey, pList->nKey, &res);
1341        assert(res == 0);
1342        memRbtreeDelete( &cur );
1343        break;
1344      case ROLLBACK_CREATE:
1345        btreeCreateTable(pRbtree, pList->iTab);
1346        break;
1347      case ROLLBACK_DROP:
1348        memRbtreeDropTable(pRbtree, pList->iTab);
1349        break;
1350      default:
1351        assert(0);
1352    }
1353    sqliteFree(pList->pKey);
1354    sqliteFree(pList->pData);
1355    pTmp = pList->pNext;
1356    sqliteFree(pList);
1357    pList = pTmp;
1358  }
1359}
1360
1361static int memRbtreeRollback(Rbtree* tree)
1362{
1363  tree->eTransState = TRANS_ROLLBACK;
1364  execute_rollback_list(tree, tree->pCheckRollback);
1365  execute_rollback_list(tree, tree->pTransRollback);
1366  tree->pTransRollback = 0;
1367  tree->pCheckRollback = 0;
1368  tree->pCheckRollbackTail = 0;
1369  tree->eTransState = TRANS_NONE;
1370  return SQLITE_OK;
1371}
1372
1373static int memRbtreeBeginCkpt(Rbtree* tree)
1374{
1375  if( tree->eTransState != TRANS_INTRANSACTION )
1376    return SQLITE_ERROR;
1377
1378  assert( tree->pCheckRollback == 0 );
1379  assert( tree->pCheckRollbackTail == 0 );
1380  tree->eTransState = TRANS_INCHECKPOINT;
1381  return SQLITE_OK;
1382}
1383
1384static int memRbtreeCommitCkpt(Rbtree* tree)
1385{
1386  if( tree->eTransState == TRANS_INCHECKPOINT ){
1387    if( tree->pCheckRollback ){
1388      tree->pCheckRollbackTail->pNext = tree->pTransRollback;
1389      tree->pTransRollback = tree->pCheckRollback;
1390      tree->pCheckRollback = 0;
1391      tree->pCheckRollbackTail = 0;
1392    }
1393    tree->eTransState = TRANS_INTRANSACTION;
1394  }
1395  return SQLITE_OK;
1396}
1397
1398static int memRbtreeRollbackCkpt(Rbtree* tree)
1399{
1400  if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK;
1401  tree->eTransState = TRANS_ROLLBACK;
1402  execute_rollback_list(tree, tree->pCheckRollback);
1403  tree->pCheckRollback = 0;
1404  tree->pCheckRollbackTail = 0;
1405  tree->eTransState = TRANS_INTRANSACTION;
1406  return SQLITE_OK;
1407}
1408
1409#ifdef SQLITE_TEST
1410static int memRbtreePageDump(Rbtree* tree, int pgno, int rec)
1411{
1412  assert(!"Cannot call sqliteRbtreePageDump");
1413  return SQLITE_OK;
1414}
1415
1416static int memRbtreeCursorDump(RbtCursor* pCur, int* aRes)
1417{
1418  assert(!"Cannot call sqliteRbtreeCursorDump");
1419  return SQLITE_OK;
1420}
1421#endif
1422
1423static struct Pager *memRbtreePager(Rbtree* tree)
1424{
1425  return 0;
1426}
1427
1428/*
1429** Return the full pathname of the underlying database file.
1430*/
1431static const char *memRbtreeGetFilename(Rbtree *pBt){
1432  return 0;  /* A NULL return indicates there is no underlying file */
1433}
1434
1435/*
1436** The copy file function is not implemented for the in-memory database
1437*/
1438static int memRbtreeCopyFile(Rbtree *pBt, Rbtree *pBt2){
1439  return SQLITE_INTERNAL;  /* Not implemented */
1440}
1441
1442static BtOps sqliteRbtreeOps = {
1443    (int(*)(Btree*)) memRbtreeClose,
1444    (int(*)(Btree*,int)) memRbtreeSetCacheSize,
1445    (int(*)(Btree*,int)) memRbtreeSetSafetyLevel,
1446    (int(*)(Btree*)) memRbtreeBeginTrans,
1447    (int(*)(Btree*)) memRbtreeCommit,
1448    (int(*)(Btree*)) memRbtreeRollback,
1449    (int(*)(Btree*)) memRbtreeBeginCkpt,
1450    (int(*)(Btree*)) memRbtreeCommitCkpt,
1451    (int(*)(Btree*)) memRbtreeRollbackCkpt,
1452    (int(*)(Btree*,int*)) memRbtreeCreateTable,
1453    (int(*)(Btree*,int*)) memRbtreeCreateTable,
1454    (int(*)(Btree*,int)) memRbtreeDropTable,
1455    (int(*)(Btree*,int)) memRbtreeClearTable,
1456    (int(*)(Btree*,int,int,BtCursor**)) memRbtreeCursor,
1457    (int(*)(Btree*,int*)) memRbtreeGetMeta,
1458    (int(*)(Btree*,int*)) memRbtreeUpdateMeta,
1459    (char*(*)(Btree*,int*,int)) memRbtreeIntegrityCheck,
1460    (const char*(*)(Btree*)) memRbtreeGetFilename,
1461    (int(*)(Btree*,Btree*)) memRbtreeCopyFile,
1462    (struct Pager*(*)(Btree*)) memRbtreePager,
1463#ifdef SQLITE_TEST
1464    (int(*)(Btree*,int,int)) memRbtreePageDump,
1465#endif
1466};
1467
1468static BtCursorOps sqliteRbtreeCursorOps = {
1469    (int(*)(BtCursor*,const void*,int,int*)) memRbtreeMoveto,
1470    (int(*)(BtCursor*)) memRbtreeDelete,
1471    (int(*)(BtCursor*,const void*,int,const void*,int)) memRbtreeInsert,
1472    (int(*)(BtCursor*,int*)) memRbtreeFirst,
1473    (int(*)(BtCursor*,int*)) memRbtreeLast,
1474    (int(*)(BtCursor*,int*)) memRbtreeNext,
1475    (int(*)(BtCursor*,int*)) memRbtreePrevious,
1476    (int(*)(BtCursor*,int*)) memRbtreeKeySize,
1477    (int(*)(BtCursor*,int,int,char*)) memRbtreeKey,
1478    (int(*)(BtCursor*,const void*,int,int,int*)) memRbtreeKeyCompare,
1479    (int(*)(BtCursor*,int*)) memRbtreeDataSize,
1480    (int(*)(BtCursor*,int,int,char*)) memRbtreeData,
1481    (int(*)(BtCursor*)) memRbtreeCloseCursor,
1482#ifdef SQLITE_TEST
1483    (int(*)(BtCursor*,int*)) memRbtreeCursorDump,
1484#endif
1485
1486};
1487
1488#endif /* SQLITE_OMIT_INMEMORYDB */
1489