xref: /illumos-gate/usr/src/lib/libsqlite/src/btree_rb.c (revision 1da57d551424de5a9d469760be7c4b4d4f10a755)
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: btree_rb.c,v 1.24.2.1 2004/06/26 14:40:05 drh Exp $
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 
31 typedef struct BtRbTree BtRbTree;
32 typedef struct BtRbNode BtRbNode;
33 typedef struct BtRollbackOp BtRollbackOp;
34 typedef struct Rbtree Rbtree;
35 typedef struct RbtCursor RbtCursor;
36 
37 /* Forward declarations */
38 static BtOps sqliteRbtreeOps;
39 static 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  */
55 struct 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 
73 struct 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 
96 struct 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 
115 struct BtRbTree {
116   RbtCursor *pCursors;     /* All cursors pointing to this tree */
117   BtRbNode *pHead;         /* Head of the tree, or NULL */
118 };
119 
120 struct 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 */
134 static int memRbtreeMoveto(
135   RbtCursor* pCur,
136   const void *pKey,
137   int nKey,
138   int *pRes
139 );
140 static int memRbtreeClearTable(Rbtree* tree, int n);
141 static int memRbtreeNext(RbtCursor* pCur, int *pRes);
142 static int memRbtreeLast(RbtCursor* pCur, int *pRes);
143 static 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 */
checkReadLocks(RbtCursor * pCur)160 static 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  */
key_compare(void const * pKey1,int nKey1,void const * pKey2,int nKey2)182 static 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  */
leftRotate(BtRbTree * pTree,BtRbNode * pX)205 static 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  */
rightRotate(BtRbTree * pTree,BtRbNode * pX)237 static 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  */
append_val(char * orig,char const * val)262 static 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  */
append_node(char * orig,BtRbNode * pNode,int indent)279 static 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  */
print_node(BtRbNode * pNode)311 static 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  */
check_redblack_tree(BtRbTree * tree,char ** msg)328 static 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  */
do_insert_balancing(BtRbTree * pTree,BtRbNode * pX)407 static 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  */
513 static
do_delete_balancing(BtRbTree * pTree,BtRbNode * pX,BtRbNode * pParent)514 void 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  */
btreeCreateTable(Rbtree * pRbtree,int n)585 static 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  */
btreeLogRollbackOp(Rbtree * pRbtree,BtRollbackOp * pRollbackOp)595 static 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 
sqliteRbtreeOpen(const char * zFilename,int mode,int nPg,Btree ** ppBtree)612 int 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 
635 open_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  */
memRbtreeCreateTable(Rbtree * tree,int * n)644 static 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  */
memRbtreeDropTable(Rbtree * tree,int n)668 static 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 
memRbtreeKeyCompare(RbtCursor * pCur,const void * pKey,int nKey,int nIgnore,int * pRes)690 static 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  */
memRbtreeCursor(Rbtree * tree,int iTable,int wrFlag,RbtCursor ** ppCur)714 static 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  */
memRbtreeInsert(RbtCursor * pCur,const void * pKey,int nKey,const void * pDataInput,int nData)745 static 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 */
memRbtreeMoveto(RbtCursor * pCur,const void * pKey,int nKey,int * pRes)871 static 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 */
memRbtreeDelete(RbtCursor * pCur)920 static 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  */
memRbtreeClearTable(Rbtree * tree,int n)1026 static 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 
memRbtreeFirst(RbtCursor * pCur,int * pRes)1071 static 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 
memRbtreeLast(RbtCursor * pCur,int * pRes)1088 static 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 */
memRbtreeNext(RbtCursor * pCur,int * pRes)1111 static 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 
memRbtreePrevious(RbtCursor * pCur,int * pRes)1138 static 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 
memRbtreeKeySize(RbtCursor * pCur,int * pSize)1165 static 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 
memRbtreeKey(RbtCursor * pCur,int offset,int amt,char * zBuf)1175 static 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 
memRbtreeDataSize(RbtCursor * pCur,int * pSize)1187 static 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 
memRbtreeData(RbtCursor * pCur,int offset,int amt,char * zBuf)1197 static 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 
memRbtreeCloseCursor(RbtCursor * pCur)1209 static 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 
memRbtreeGetMeta(Rbtree * tree,int * aMeta)1225 static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
1226 {
1227   memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
1228   return SQLITE_OK;
1229 }
1230 
memRbtreeUpdateMeta(Rbtree * tree,int * aMeta)1231 static 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  */
memRbtreeIntegrityCheck(Rbtree * tree,int * aRoot,int nRoot)1242 static 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 
memRbtreeSetCacheSize(Rbtree * tree,int sz)1255 static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
1256 {
1257   return SQLITE_OK;
1258 }
1259 
memRbtreeSetSafetyLevel(Rbtree * pBt,int level)1260 static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){
1261   return SQLITE_OK;
1262 }
1263 
memRbtreeBeginTrans(Rbtree * tree)1264 static 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 */
deleteRollbackList(BtRollbackOp * pOp)1277 static 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 
memRbtreeCommit(Rbtree * tree)1287 static 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  */
memRbtreeClose(Rbtree * tree)1301 static 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  */
execute_rollback_list(Rbtree * pRbtree,BtRollbackOp * pList)1317 static 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 
memRbtreeRollback(Rbtree * tree)1361 static 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 
memRbtreeBeginCkpt(Rbtree * tree)1373 static 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 
memRbtreeCommitCkpt(Rbtree * tree)1384 static 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 
memRbtreeRollbackCkpt(Rbtree * tree)1398 static 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
memRbtreePageDump(Rbtree * tree,int pgno,int rec)1410 static int memRbtreePageDump(Rbtree* tree, int pgno, int rec)
1411 {
1412   assert(!"Cannot call sqliteRbtreePageDump");
1413   return SQLITE_OK;
1414 }
1415 
memRbtreeCursorDump(RbtCursor * pCur,int * aRes)1416 static int memRbtreeCursorDump(RbtCursor* pCur, int* aRes)
1417 {
1418   assert(!"Cannot call sqliteRbtreeCursorDump");
1419   return SQLITE_OK;
1420 }
1421 #endif
1422 
memRbtreePager(Rbtree * tree)1423 static struct Pager *memRbtreePager(Rbtree* tree)
1424 {
1425   return 0;
1426 }
1427 
1428 /*
1429 ** Return the full pathname of the underlying database file.
1430 */
memRbtreeGetFilename(Rbtree * pBt)1431 static 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 */
memRbtreeCopyFile(Rbtree * pBt,Rbtree * pBt2)1438 static int memRbtreeCopyFile(Rbtree *pBt, Rbtree *pBt2){
1439   return SQLITE_INTERNAL;  /* Not implemented */
1440 }
1441 
1442 static 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 
1468 static 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