Annotation of embedaddon/php/ext/sqlite/libsqlite/src/btree_rb.c, revision 1.1.1.1
1.1 misho 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 195361 2005-09-07 15:11:33Z iliaa $
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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: */
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
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: */
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: */
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:
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: */
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: */
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:
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: */
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: */
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: */
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: */
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: */
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:
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:
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: */
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:
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:
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:
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:
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:
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:
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:
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:
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: */
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:
1255: static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
1256: {
1257: return SQLITE_OK;
1258: }
1259:
1260: static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){
1261: return SQLITE_OK;
1262: }
1263:
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: */
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:
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: */
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: */
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:
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:
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:
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:
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
1410: static int memRbtreePageDump(Rbtree* tree, int pgno, int rec)
1411: {
1412: assert(!"Cannot call sqliteRbtreePageDump");
1413: return SQLITE_OK;
1414: }
1415:
1416: static int memRbtreeCursorDump(RbtCursor* pCur, int* aRes)
1417: {
1418: assert(!"Cannot call sqliteRbtreeCursorDump");
1419: return SQLITE_OK;
1420: }
1421: #endif
1422:
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: */
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: */
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 */
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to btree_rb.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / php / ext / sqlite / libsqlite / src