monotone

monotone Mtn Source Tree

Root/sqlite/btree_rb.c

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

Archive Download this file

Branches

Tags

Quick Links:     www.monotone.ca    -     Downloads    -     Documentation    -     Wiki    -     Code Forge    -     Build Status