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 647 : static int checkReadLocks(RbtCursor *pCur){
161 : RbtCursor *p;
162 : assert( pCur->wrFlag );
163 1288 : for(p=pCur->pTree->pCursors; p; p=p->pShared){
164 641 : if( p!=pCur ){
165 0 : if( p->wrFlag==0 ) return SQLITE_LOCKED;
166 0 : p->pNode = 0;
167 : }
168 : }
169 647 : 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 1271 : {
184 1271 : int mcmp = memcmp(pKey1, pKey2, (nKey1 <= nKey2)?nKey1:nKey2);
185 1271 : if( mcmp == 0){
186 284 : if( nKey1 == nKey2 ) return 0;
187 48 : return ((nKey1 < nKey2)?-1:1);
188 : }
189 987 : 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 127 : {
207 : BtRbNode *pY;
208 : BtRbNode *pb;
209 127 : pY = pX->pRight;
210 127 : pb = pY->pLeft;
211 :
212 127 : pY->pParent = pX->pParent;
213 127 : if( pX->pParent ){
214 33 : if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
215 24 : else pX->pParent->pRight = pY;
216 : }
217 127 : pY->pLeft = pX;
218 127 : pX->pParent = pY;
219 127 : pX->pRight = pb;
220 127 : if( pb ) pb->pParent = pX;
221 127 : if( pTree->pHead == pX ) pTree->pHead = pY;
222 127 : }
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 9 : {
239 : BtRbNode *pY;
240 : BtRbNode *pb;
241 9 : pY = pX->pLeft;
242 9 : pb = pY->pRight;
243 :
244 9 : pY->pParent = pX->pParent;
245 9 : if( pX->pParent ){
246 4 : if( pX->pParent->pLeft == pX ) pX->pParent->pLeft = pY;
247 2 : else pX->pParent->pRight = pY;
248 : }
249 9 : pY->pRight = pX;
250 9 : pX->pParent = pY;
251 9 : pX->pLeft = pb;
252 9 : if( pb ) pb->pParent = pX;
253 9 : if( pTree->pHead == pX ) pTree->pHead = pY;
254 9 : }
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 0 : static char *append_val(char * orig, char const * val){
263 : char *z;
264 0 : if( !orig ){
265 0 : z = sqliteStrDup( val );
266 : } else{
267 0 : z = 0;
268 0 : sqliteSetString(&z, orig, val, (char*)0);
269 0 : sqliteFree( orig );
270 : }
271 0 : 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 0 : {
281 : char buf[128];
282 : int i;
283 :
284 0 : for( i=0; i<indent; i++ ){
285 0 : orig = append_val(orig, " ");
286 : }
287 :
288 0 : sprintf(buf, "%p", pNode);
289 0 : orig = append_val(orig, buf);
290 :
291 0 : if( pNode ){
292 0 : indent += 3;
293 0 : if( pNode->isBlack ){
294 0 : orig = append_val(orig, " B \n");
295 : }else{
296 0 : orig = append_val(orig, " R \n");
297 : }
298 0 : orig = append_node( orig, pNode->pLeft, indent );
299 0 : orig = append_node( orig, pNode->pRight, indent );
300 : }else{
301 0 : orig = append_val(orig, "\n");
302 : }
303 0 : 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 0 : {
313 0 : char * str = append_node(0, pNode, 0);
314 0 : printf("%s", str);
315 :
316 : /* Suppress a warning message about print_node() being unused */
317 : (void)print_node;
318 0 : }
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 0 : {
330 : BtRbNode *pNode;
331 :
332 : /* 0 -> came from parent
333 : * 1 -> came from left
334 : * 2 -> came from right */
335 0 : int prev_step = 0;
336 :
337 0 : pNode = tree->pHead;
338 0 : while( pNode ){
339 0 : switch( prev_step ){
340 : case 0:
341 0 : if( pNode->pLeft ){
342 0 : pNode = pNode->pLeft;
343 : }else{
344 0 : prev_step = 1;
345 : }
346 0 : break;
347 : case 1:
348 0 : if( pNode->pRight ){
349 0 : pNode = pNode->pRight;
350 0 : prev_step = 0;
351 : }else{
352 0 : prev_step = 2;
353 : }
354 0 : break;
355 : case 2:
356 : /* Check red-black property (1) */
357 0 : if( !pNode->isBlack &&
358 : ( (pNode->pLeft && !pNode->pLeft->isBlack) ||
359 : (pNode->pRight && !pNode->pRight->isBlack) )
360 : ){
361 : char buf[128];
362 0 : sprintf(buf, "Red node with red child at %p\n", pNode);
363 0 : *msg = append_val(*msg, buf);
364 0 : *msg = append_node(*msg, tree->pHead, 0);
365 0 : *msg = append_val(*msg, "\n");
366 : }
367 :
368 : /* Check red-black property (2) */
369 : {
370 0 : int leftHeight = 0;
371 0 : int rightHeight = 0;
372 0 : if( pNode->pLeft ){
373 0 : leftHeight += pNode->pLeft->nBlackHeight;
374 0 : leftHeight += (pNode->pLeft->isBlack?1:0);
375 : }
376 0 : if( pNode->pRight ){
377 0 : rightHeight += pNode->pRight->nBlackHeight;
378 0 : rightHeight += (pNode->pRight->isBlack?1:0);
379 : }
380 0 : if( leftHeight != rightHeight ){
381 : char buf[128];
382 0 : sprintf(buf, "Different black-heights at %p\n", pNode);
383 0 : *msg = append_val(*msg, buf);
384 0 : *msg = append_node(*msg, tree->pHead, 0);
385 0 : *msg = append_val(*msg, "\n");
386 : }
387 0 : pNode->nBlackHeight = leftHeight;
388 : }
389 :
390 0 : if( pNode->pParent ){
391 0 : if( pNode == pNode->pParent->pLeft ) prev_step = 1;
392 0 : else prev_step = 2;
393 : }
394 0 : pNode = pNode->pParent;
395 : break;
396 : default: assert(0);
397 : }
398 : }
399 0 : }
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 547 : {
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 1272 : 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 178 : pGrandparent = pX->pParent->pParent;
423 : assert( pGrandparent );
424 : assert( pGrandparent->isBlack );
425 :
426 : /* Uncle of pX may or may not exist. */
427 178 : if( pX->pParent == pGrandparent->pLeft )
428 15 : pUncle = pGrandparent->pRight;
429 : else
430 163 : 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 229 : if( pUncle && !pUncle->isBlack ){
444 51 : pGrandparent->isBlack = 0;
445 51 : pUncle->isBlack = 1;
446 51 : pX->pParent->isBlack = 1;
447 51 : pX = pGrandparent;
448 : }else{
449 :
450 127 : if( pX->pParent == pGrandparent->pLeft ){
451 9 : 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 9 : pX = pX->pParent;
464 9 : 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 9 : pGrandparent->isBlack = 0;
479 9 : pX->pParent->isBlack = 1;
480 9 : rightRotate( pTree, pGrandparent );
481 :
482 : }else{
483 : /* This code is symetric to the illustrated case above. */
484 118 : if( pX == pX->pParent->pLeft ){
485 0 : pX = pX->pParent;
486 0 : rightRotate(pTree, pX);
487 : }
488 : assert( pGrandparent == pX->pParent->pParent );
489 118 : pGrandparent->isBlack = 0;
490 118 : pX->pParent->isBlack = 1;
491 118 : leftRotate( pTree, pGrandparent );
492 : }
493 : }
494 : }
495 547 : pTree->pHead->isBlack = 1;
496 547 : }
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 3 : {
516 : BtRbNode *pSib;
517 :
518 : /* TODO: Comment this code! */
519 6 : while( pX != pTree->pHead && (!pX || pX->isBlack) ){
520 0 : if( pX == pParent->pLeft ){
521 0 : pSib = pParent->pRight;
522 0 : if( pSib && !(pSib->isBlack) ){
523 0 : pSib->isBlack = 1;
524 0 : pParent->isBlack = 0;
525 0 : leftRotate(pTree, pParent);
526 0 : pSib = pParent->pRight;
527 : }
528 0 : if( !pSib ){
529 0 : pX = pParent;
530 0 : }else if(
531 : (!pSib->pLeft || pSib->pLeft->isBlack) &&
532 : (!pSib->pRight || pSib->pRight->isBlack) ) {
533 0 : pSib->isBlack = 0;
534 0 : pX = pParent;
535 : }else{
536 0 : if( (!pSib->pRight || pSib->pRight->isBlack) ){
537 0 : if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
538 0 : pSib->isBlack = 0;
539 0 : rightRotate( pTree, pSib );
540 0 : pSib = pParent->pRight;
541 : }
542 0 : pSib->isBlack = pParent->isBlack;
543 0 : pParent->isBlack = 1;
544 0 : if( pSib->pRight ) pSib->pRight->isBlack = 1;
545 0 : leftRotate(pTree, pParent);
546 0 : pX = pTree->pHead;
547 : }
548 : }else{
549 0 : pSib = pParent->pLeft;
550 0 : if( pSib && !(pSib->isBlack) ){
551 0 : pSib->isBlack = 1;
552 0 : pParent->isBlack = 0;
553 0 : rightRotate(pTree, pParent);
554 0 : pSib = pParent->pLeft;
555 : }
556 0 : if( !pSib ){
557 0 : pX = pParent;
558 0 : }else if(
559 : (!pSib->pLeft || pSib->pLeft->isBlack) &&
560 : (!pSib->pRight || pSib->pRight->isBlack) ){
561 0 : pSib->isBlack = 0;
562 0 : pX = pParent;
563 : }else{
564 0 : if( (!pSib->pLeft || pSib->pLeft->isBlack) ){
565 0 : if( pSib->pRight ) pSib->pRight->isBlack = 1;
566 0 : pSib->isBlack = 0;
567 0 : leftRotate( pTree, pSib );
568 0 : pSib = pParent->pLeft;
569 : }
570 0 : pSib->isBlack = pParent->isBlack;
571 0 : pParent->isBlack = 1;
572 0 : if( pSib->pLeft ) pSib->pLeft->isBlack = 1;
573 0 : rightRotate(pTree, pParent);
574 0 : pX = pTree->pHead;
575 : }
576 : }
577 0 : pParent = pX->pParent;
578 : }
579 3 : if( pX ) pX->isBlack = 1;
580 3 : }
581 :
582 : /*
583 : * Create table n in tree pRbtree. Table n must not exist.
584 : */
585 : static void btreeCreateTable(Rbtree* pRbtree, int n)
586 435 : {
587 435 : BtRbTree *pNewTbl = sqliteMalloc(sizeof(BtRbTree));
588 435 : sqliteHashInsert(&pRbtree->tblHash, 0, n, pNewTbl);
589 435 : }
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 792 : {
597 : assert( pRbtree->eTransState == TRANS_INCHECKPOINT ||
598 : pRbtree->eTransState == TRANS_INTRANSACTION );
599 792 : if( pRbtree->eTransState == TRANS_INTRANSACTION ){
600 792 : pRollbackOp->pNext = pRbtree->pTransRollback;
601 792 : pRbtree->pTransRollback = pRollbackOp;
602 : }
603 792 : if( pRbtree->eTransState == TRANS_INCHECKPOINT ){
604 0 : if( !pRbtree->pCheckRollback ){
605 0 : pRbtree->pCheckRollbackTail = pRollbackOp;
606 : }
607 0 : pRollbackOp->pNext = pRbtree->pCheckRollback;
608 0 : pRbtree->pCheckRollback = pRollbackOp;
609 : }
610 792 : }
611 :
612 : int sqliteRbtreeOpen(
613 : const char *zFilename,
614 : int mode,
615 : int nPg,
616 : Btree **ppBtree
617 298 : ){
618 298 : Rbtree **ppRbtree = (Rbtree**)ppBtree;
619 298 : *ppRbtree = (Rbtree *)sqliteMalloc(sizeof(Rbtree));
620 298 : if( sqlite_malloc_failed ) goto open_no_mem;
621 298 : sqliteHashInit(&(*ppRbtree)->tblHash, SQLITE_HASH_INT, 0);
622 :
623 : /* Create a binary tree for the SQLITE_MASTER table at location 2 */
624 298 : btreeCreateTable(*ppRbtree, 2);
625 298 : if( sqlite_malloc_failed ) goto open_no_mem;
626 298 : (*ppRbtree)->next_idx = 3;
627 298 : (*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 298 : (*ppRbtree)->aMetaData[2] = 4;
632 :
633 298 : return SQLITE_OK;
634 :
635 0 : open_no_mem:
636 0 : *ppBtree = 0;
637 0 : 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 137 : {
646 : assert( tree->eTransState != TRANS_NONE );
647 :
648 137 : *n = tree->next_idx++;
649 137 : btreeCreateTable(tree, *n);
650 137 : 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 137 : if( tree->eTransState != TRANS_ROLLBACK ){
655 137 : BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
656 137 : if( pRollbackOp==0 ) return SQLITE_NOMEM;
657 137 : pRollbackOp->eOp = ROLLBACK_DROP;
658 137 : pRollbackOp->iTab = *n;
659 137 : btreeLogRollbackOp(tree, pRollbackOp);
660 : }
661 :
662 137 : return SQLITE_OK;
663 : }
664 :
665 : /*
666 : * Delete table n from the supplied Rbtree.
667 : */
668 : static int memRbtreeDropTable(Rbtree* tree, int n)
669 354 : {
670 : BtRbTree *pTree;
671 : assert( tree->eTransState != TRANS_NONE );
672 :
673 354 : memRbtreeClearTable(tree, n);
674 354 : pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
675 : assert(pTree);
676 : assert( pTree->pCursors==0 );
677 354 : sqliteFree(pTree);
678 :
679 354 : if( tree->eTransState != TRANS_ROLLBACK ){
680 1 : BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
681 1 : if( pRollbackOp==0 ) return SQLITE_NOMEM;
682 1 : pRollbackOp->eOp = ROLLBACK_CREATE;
683 1 : pRollbackOp->iTab = n;
684 1 : btreeLogRollbackOp(tree, pRollbackOp);
685 : }
686 :
687 354 : return SQLITE_OK;
688 : }
689 :
690 : static int memRbtreeKeyCompare(RbtCursor* pCur, const void *pKey, int nKey,
691 : int nIgnore, int *pRes)
692 109 : {
693 : assert(pCur);
694 :
695 109 : if( !pCur->pNode ) {
696 0 : *pRes = -1;
697 : } else {
698 109 : if( (pCur->pNode->nKey - nIgnore) < 0 ){
699 0 : *pRes = -1;
700 : }else{
701 109 : *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey-nIgnore,
702 : pKey, nKey);
703 : }
704 : }
705 109 : 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 1373 : ){
720 : RbtCursor *pCur;
721 : assert(tree);
722 1373 : pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));
723 1373 : if( sqlite_malloc_failed ) return SQLITE_NOMEM;
724 1373 : pCur->pTree = sqliteHashFind(&tree->tblHash, 0, iTable);
725 : assert( pCur->pTree );
726 1373 : pCur->pRbtree = tree;
727 1373 : pCur->iTree = iTable;
728 1373 : pCur->pOps = &sqliteRbtreeCursorOps;
729 1373 : pCur->wrFlag = wrFlag;
730 1373 : pCur->pShared = pCur->pTree->pCursors;
731 1373 : pCur->pTree->pCursors = pCur;
732 :
733 : assert( (*ppCur)->pTree );
734 1373 : 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 643 : ){
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 643 : if( checkReadLocks(pCur) ){
761 0 : 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 643 : pData = sqliteMallocRaw(nData);
767 643 : if( sqlite_malloc_failed ) return SQLITE_NOMEM;
768 643 : 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 643 : memRbtreeMoveto( pCur, pKey, nKey, &match);
782 643 : if( match ){
783 547 : BtRbNode *pNode = sqliteMalloc(sizeof(BtRbNode));
784 547 : if( pNode==0 ) return SQLITE_NOMEM;
785 547 : pNode->nKey = nKey;
786 547 : pNode->pKey = sqliteMallocRaw(nKey);
787 547 : if( sqlite_malloc_failed ) return SQLITE_NOMEM;
788 547 : memcpy(pNode->pKey, pKey, nKey);
789 547 : pNode->nData = nData;
790 547 : pNode->pData = pData;
791 547 : if( pCur->pNode ){
792 321 : switch( match ){
793 : case -1:
794 : assert( !pCur->pNode->pRight );
795 305 : pNode->pParent = pCur->pNode;
796 305 : pCur->pNode->pRight = pNode;
797 305 : break;
798 : case 1:
799 : assert( !pCur->pNode->pLeft );
800 16 : pNode->pParent = pCur->pNode;
801 16 : pCur->pNode->pLeft = pNode;
802 : break;
803 : default:
804 : assert(0);
805 : }
806 : }else{
807 226 : pCur->pTree->pHead = pNode;
808 : }
809 :
810 : /* Point the cursor at the node just inserted, as per SQLite requirements */
811 547 : pCur->pNode = pNode;
812 :
813 : /* A new node has just been inserted, so run the balancing code */
814 547 : do_insert_balancing(pCur->pTree, pNode);
815 :
816 : /* Set up a rollback-op in case we have to roll this operation back */
817 547 : if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
818 541 : BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
819 541 : if( pOp==0 ) return SQLITE_NOMEM;
820 541 : pOp->eOp = ROLLBACK_DELETE;
821 541 : pOp->iTab = pCur->iTree;
822 541 : pOp->nKey = pNode->nKey;
823 541 : pOp->pKey = sqliteMallocRaw( pOp->nKey );
824 541 : if( sqlite_malloc_failed ) return SQLITE_NOMEM;
825 541 : memcpy( pOp->pKey, pNode->pKey, pOp->nKey );
826 541 : 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 96 : if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
835 96 : BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
836 96 : if( pOp==0 ) return SQLITE_NOMEM;
837 96 : pOp->iTab = pCur->iTree;
838 96 : pOp->nKey = pCur->pNode->nKey;
839 96 : pOp->pKey = sqliteMallocRaw( pOp->nKey );
840 96 : if( sqlite_malloc_failed ) return SQLITE_NOMEM;
841 96 : memcpy( pOp->pKey, pCur->pNode->pKey, pOp->nKey );
842 96 : pOp->nData = pCur->pNode->nData;
843 96 : pOp->pData = pCur->pNode->pData;
844 96 : pOp->eOp = ROLLBACK_INSERT;
845 96 : btreeLogRollbackOp(pCur->pRbtree, pOp);
846 : }else{
847 0 : sqliteFree( pCur->pNode->pData );
848 : }
849 :
850 : /* Actually clobber the nodes data */
851 96 : pCur->pNode->pData = pData;
852 96 : pCur->pNode->nData = nData;
853 : }
854 :
855 643 : 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 942 : ){
877 942 : BtRbNode *pTmp = 0;
878 :
879 942 : pCur->pNode = pCur->pTree->pHead;
880 942 : *pRes = -1;
881 3046 : while( pCur->pNode && *pRes ) {
882 1162 : *pRes = key_compare(pCur->pNode->pKey, pCur->pNode->nKey, pKey, nKey);
883 1162 : pTmp = pCur->pNode;
884 1162 : switch( *pRes ){
885 : case 1: /* cursor > key */
886 181 : pCur->pNode = pCur->pNode->pLeft;
887 181 : break;
888 : case -1: /* cursor < key */
889 793 : 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 942 : if( !pCur->pNode ) pCur->pNode = pTmp;
900 942 : pCur->eSkip = SKIP_NONE;
901 :
902 942 : 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 4 : {
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 4 : if( checkReadLocks(pCur) ){
931 0 : return SQLITE_LOCKED; /* The table pCur points to has a read lock */
932 : }
933 :
934 4 : pZ = pCur->pNode;
935 4 : if( !pZ ){
936 0 : return SQLITE_OK;
937 : }
938 :
939 : /* If we are not currently doing a rollback, set up a rollback op for this
940 : * deletion */
941 4 : if( pCur->pRbtree->eTransState != TRANS_ROLLBACK ){
942 4 : BtRollbackOp *pOp = sqliteMalloc( sizeof(BtRollbackOp) );
943 4 : if( pOp==0 ) return SQLITE_NOMEM;
944 4 : pOp->iTab = pCur->iTree;
945 4 : pOp->nKey = pZ->nKey;
946 4 : pOp->pKey = pZ->pKey;
947 4 : pOp->nData = pZ->nData;
948 4 : pOp->pData = pZ->pData;
949 4 : pOp->eOp = ROLLBACK_INSERT;
950 4 : 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 4 : if( pZ->pLeft && pZ->pRight ){
960 : BtRbNode *pTmp;
961 : int dummy;
962 0 : pCur->eSkip = SKIP_NONE;
963 0 : memRbtreeNext(pCur, &dummy);
964 : assert( dummy == 0 );
965 0 : if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
966 0 : sqliteFree(pZ->pKey);
967 0 : sqliteFree(pZ->pData);
968 : }
969 0 : pZ->pData = pCur->pNode->pData;
970 0 : pZ->nData = pCur->pNode->nData;
971 0 : pZ->pKey = pCur->pNode->pKey;
972 0 : pZ->nKey = pCur->pNode->nKey;
973 0 : pTmp = pZ;
974 0 : pZ = pCur->pNode;
975 0 : pCur->pNode = pTmp;
976 0 : pCur->eSkip = SKIP_NEXT;
977 : }else{
978 : int res;
979 4 : pCur->eSkip = SKIP_NONE;
980 4 : memRbtreeNext(pCur, &res);
981 4 : pCur->eSkip = SKIP_NEXT;
982 4 : if( res ){
983 2 : memRbtreeLast(pCur, &res);
984 2 : memRbtreePrevious(pCur, &res);
985 2 : pCur->eSkip = SKIP_PREV;
986 : }
987 4 : if( pCur->pRbtree->eTransState == TRANS_ROLLBACK ){
988 0 : sqliteFree(pZ->pKey);
989 0 : 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 4 : BtRbNode **ppParentSlot = 0;
997 : assert( !pZ->pLeft || !pZ->pRight ); /* pZ has at most one child */
998 4 : pChild = ((pZ->pLeft)?pZ->pLeft:pZ->pRight);
999 4 : if( pZ->pParent ){
1000 : assert( pZ == pZ->pParent->pLeft || pZ == pZ->pParent->pRight );
1001 1 : ppParentSlot = ((pZ == pZ->pParent->pLeft)
1002 : ?&pZ->pParent->pLeft:&pZ->pParent->pRight);
1003 1 : *ppParentSlot = pChild;
1004 : }else{
1005 3 : pCur->pTree->pHead = pChild;
1006 : }
1007 4 : 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 4 : if( pZ->isBlack ){
1016 3 : do_delete_balancing(pCur->pTree, pChild, pZ->pParent);
1017 : }
1018 :
1019 4 : sqliteFree(pZ);
1020 4 : return SQLITE_OK;
1021 : }
1022 :
1023 : /*
1024 : * Empty table n of the Rbtree.
1025 : */
1026 : static int memRbtreeClearTable(Rbtree* tree, int n)
1027 358 : {
1028 : BtRbTree *pTree;
1029 : BtRbNode *pNode;
1030 :
1031 358 : pTree = sqliteHashFind(&tree->tblHash, 0, n);
1032 : assert(pTree);
1033 :
1034 358 : pNode = pTree->pHead;
1035 1227 : while( pNode ){
1036 511 : if( pNode->pLeft ){
1037 71 : pNode = pNode->pLeft;
1038 : }
1039 440 : else if( pNode->pRight ){
1040 103 : pNode = pNode->pRight;
1041 : }
1042 : else {
1043 337 : BtRbNode *pTmp = pNode->pParent;
1044 337 : if( tree->eTransState == TRANS_ROLLBACK ){
1045 324 : sqliteFree( pNode->pKey );
1046 324 : sqliteFree( pNode->pData );
1047 : }else{
1048 13 : BtRollbackOp *pRollbackOp = sqliteMallocRaw(sizeof(BtRollbackOp));
1049 13 : if( pRollbackOp==0 ) return SQLITE_NOMEM;
1050 13 : pRollbackOp->eOp = ROLLBACK_INSERT;
1051 13 : pRollbackOp->iTab = n;
1052 13 : pRollbackOp->nKey = pNode->nKey;
1053 13 : pRollbackOp->pKey = pNode->pKey;
1054 13 : pRollbackOp->nData = pNode->nData;
1055 13 : pRollbackOp->pData = pNode->pData;
1056 13 : btreeLogRollbackOp(tree, pRollbackOp);
1057 : }
1058 337 : sqliteFree( pNode );
1059 337 : if( pTmp ){
1060 174 : if( pTmp->pLeft == pNode ) pTmp->pLeft = 0;
1061 103 : else if( pTmp->pRight == pNode ) pTmp->pRight = 0;
1062 : }
1063 337 : pNode = pTmp;
1064 : }
1065 : }
1066 :
1067 358 : pTree->pHead = 0;
1068 358 : return SQLITE_OK;
1069 : }
1070 :
1071 : static int memRbtreeFirst(RbtCursor* pCur, int *pRes)
1072 474 : {
1073 474 : if( pCur->pTree->pHead ){
1074 167 : pCur->pNode = pCur->pTree->pHead;
1075 447 : while( pCur->pNode->pLeft ){
1076 113 : pCur->pNode = pCur->pNode->pLeft;
1077 : }
1078 : }
1079 474 : if( pCur->pNode ){
1080 167 : *pRes = 0;
1081 : }else{
1082 307 : *pRes = 1;
1083 : }
1084 474 : pCur->eSkip = SKIP_NONE;
1085 474 : return SQLITE_OK;
1086 : }
1087 :
1088 : static int memRbtreeLast(RbtCursor* pCur, int *pRes)
1089 352 : {
1090 352 : if( pCur->pTree->pHead ){
1091 174 : pCur->pNode = pCur->pTree->pHead;
1092 503 : while( pCur->pNode->pRight ){
1093 155 : pCur->pNode = pCur->pNode->pRight;
1094 : }
1095 : }
1096 352 : if( pCur->pNode ){
1097 174 : *pRes = 0;
1098 : }else{
1099 178 : *pRes = 1;
1100 : }
1101 352 : pCur->eSkip = SKIP_NONE;
1102 352 : 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 636 : {
1113 636 : if( pCur->pNode && pCur->eSkip != SKIP_NEXT ){
1114 592 : if( pCur->pNode->pRight ){
1115 183 : pCur->pNode = pCur->pNode->pRight;
1116 380 : while( pCur->pNode->pLeft )
1117 14 : pCur->pNode = pCur->pNode->pLeft;
1118 : }else{
1119 409 : BtRbNode * pX = pCur->pNode;
1120 409 : pCur->pNode = pX->pParent;
1121 1053 : while( pCur->pNode && (pCur->pNode->pRight == pX) ){
1122 235 : pX = pCur->pNode;
1123 235 : pCur->pNode = pX->pParent;
1124 : }
1125 : }
1126 : }
1127 636 : pCur->eSkip = SKIP_NONE;
1128 :
1129 636 : if( !pCur->pNode ){
1130 291 : *pRes = 1;
1131 : }else{
1132 345 : *pRes = 0;
1133 : }
1134 :
1135 636 : return SQLITE_OK;
1136 : }
1137 :
1138 : static int memRbtreePrevious(RbtCursor* pCur, int *pRes)
1139 2 : {
1140 2 : if( pCur->pNode && pCur->eSkip != SKIP_PREV ){
1141 2 : if( pCur->pNode->pLeft ){
1142 0 : pCur->pNode = pCur->pNode->pLeft;
1143 0 : while( pCur->pNode->pRight )
1144 0 : pCur->pNode = pCur->pNode->pRight;
1145 : }else{
1146 2 : BtRbNode * pX = pCur->pNode;
1147 2 : pCur->pNode = pX->pParent;
1148 4 : while( pCur->pNode && (pCur->pNode->pLeft == pX) ){
1149 0 : pX = pCur->pNode;
1150 0 : pCur->pNode = pX->pParent;
1151 : }
1152 : }
1153 : }
1154 2 : pCur->eSkip = SKIP_NONE;
1155 :
1156 2 : if( !pCur->pNode ){
1157 2 : *pRes = 1;
1158 : }else{
1159 0 : *pRes = 0;
1160 : }
1161 :
1162 2 : return SQLITE_OK;
1163 : }
1164 :
1165 : static int memRbtreeKeySize(RbtCursor* pCur, int *pSize)
1166 154 : {
1167 154 : if( pCur->pNode ){
1168 154 : *pSize = pCur->pNode->nKey;
1169 : }else{
1170 0 : *pSize = 0;
1171 : }
1172 154 : return SQLITE_OK;
1173 : }
1174 :
1175 : static int memRbtreeKey(RbtCursor* pCur, int offset, int amt, char *zBuf)
1176 351 : {
1177 351 : if( !pCur->pNode ) return 0;
1178 702 : if( !pCur->pNode->pKey || ((amt + offset) <= pCur->pNode->nKey) ){
1179 351 : memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, amt);
1180 : }else{
1181 0 : memcpy(zBuf, ((char*)pCur->pNode->pKey)+offset, pCur->pNode->nKey-offset);
1182 0 : amt = pCur->pNode->nKey-offset;
1183 : }
1184 351 : return amt;
1185 : }
1186 :
1187 : static int memRbtreeDataSize(RbtCursor* pCur, int *pSize)
1188 865 : {
1189 865 : if( pCur->pNode ){
1190 865 : *pSize = pCur->pNode->nData;
1191 : }else{
1192 0 : *pSize = 0;
1193 : }
1194 865 : return SQLITE_OK;
1195 : }
1196 :
1197 : static int memRbtreeData(RbtCursor *pCur, int offset, int amt, char *zBuf)
1198 1714 : {
1199 1714 : if( !pCur->pNode ) return 0;
1200 1714 : if( (amt + offset) <= pCur->pNode->nData ){
1201 1714 : memcpy(zBuf, ((char*)pCur->pNode->pData)+offset, amt);
1202 : }else{
1203 0 : memcpy(zBuf, ((char*)pCur->pNode->pData)+offset ,pCur->pNode->nData-offset);
1204 0 : amt = pCur->pNode->nData-offset;
1205 : }
1206 1714 : return amt;
1207 : }
1208 :
1209 : static int memRbtreeCloseCursor(RbtCursor* pCur)
1210 1372 : {
1211 1372 : if( pCur->pTree->pCursors==pCur ){
1212 1372 : pCur->pTree->pCursors = pCur->pShared;
1213 : }else{
1214 0 : RbtCursor *p = pCur->pTree->pCursors;
1215 0 : while( p && p->pShared!=pCur ){ p = p->pShared; }
1216 : assert( p!=0 );
1217 0 : if( p ){
1218 0 : p->pShared = pCur->pShared;
1219 : }
1220 : }
1221 1372 : sqliteFree(pCur);
1222 1372 : return SQLITE_OK;
1223 : }
1224 :
1225 : static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
1226 1207 : {
1227 1207 : memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
1228 1207 : return SQLITE_OK;
1229 : }
1230 :
1231 : static int memRbtreeUpdateMeta(Rbtree* tree, int* aMeta)
1232 189 : {
1233 189 : memcpy( tree->aMetaData, aMeta, sizeof(int) * SQLITE_N_BTREE_META );
1234 189 : 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 0 : {
1244 0 : char * msg = 0;
1245 : HashElem *p;
1246 :
1247 0 : for(p=sqliteHashFirst(&tree->tblHash); p; p=sqliteHashNext(p)){
1248 0 : BtRbTree *pTree = sqliteHashData(p);
1249 0 : check_redblack_tree(pTree, &msg);
1250 : }
1251 :
1252 0 : return msg;
1253 : }
1254 :
1255 : static int memRbtreeSetCacheSize(Rbtree* tree, int sz)
1256 300 : {
1257 300 : return SQLITE_OK;
1258 : }
1259 :
1260 300 : static int memRbtreeSetSafetyLevel(Rbtree *pBt, int level){
1261 300 : return SQLITE_OK;
1262 : }
1263 :
1264 : static int memRbtreeBeginTrans(Rbtree* tree)
1265 718 : {
1266 718 : if( tree->eTransState != TRANS_NONE )
1267 0 : return SQLITE_ERROR;
1268 :
1269 : assert( tree->pTransRollback == 0 );
1270 718 : tree->eTransState = TRANS_INTRANSACTION;
1271 718 : return SQLITE_OK;
1272 : }
1273 :
1274 : /*
1275 : ** Delete a linked list of BtRollbackOp structures.
1276 : */
1277 1952 : static void deleteRollbackList(BtRollbackOp *pOp){
1278 4690 : while( pOp ){
1279 786 : BtRollbackOp *pTmp = pOp->pNext;
1280 786 : sqliteFree(pOp->pData);
1281 786 : sqliteFree(pOp->pKey);
1282 786 : sqliteFree(pOp);
1283 786 : pOp = pTmp;
1284 : }
1285 1952 : }
1286 :
1287 976 : static int memRbtreeCommit(Rbtree* tree){
1288 : /* Just delete pTransRollback and pCheckRollback */
1289 976 : deleteRollbackList(tree->pCheckRollback);
1290 976 : deleteRollbackList(tree->pTransRollback);
1291 976 : tree->pTransRollback = 0;
1292 976 : tree->pCheckRollback = 0;
1293 976 : tree->pCheckRollbackTail = 0;
1294 976 : tree->eTransState = TRANS_NONE;
1295 976 : return SQLITE_OK;
1296 : }
1297 :
1298 : /*
1299 : * Close the supplied Rbtree. Delete everything associated with it.
1300 : */
1301 : static int memRbtreeClose(Rbtree* tree)
1302 262 : {
1303 : HashElem *p;
1304 262 : memRbtreeCommit(tree);
1305 877 : while( (p=sqliteHashFirst(&tree->tblHash))!=0 ){
1306 353 : tree->eTransState = TRANS_ROLLBACK;
1307 353 : memRbtreeDropTable(tree, sqliteHashKeysize(p));
1308 : }
1309 262 : sqliteHashClear(&tree->tblHash);
1310 262 : sqliteFree(tree);
1311 262 : 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 8 : {
1319 : BtRollbackOp *pTmp;
1320 : RbtCursor cur;
1321 : int res;
1322 :
1323 8 : cur.pRbtree = pRbtree;
1324 8 : cur.wrFlag = 1;
1325 22 : while( pList ){
1326 6 : switch( pList->eOp ){
1327 : case ROLLBACK_INSERT:
1328 6 : cur.pTree = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
1329 : assert(cur.pTree);
1330 6 : cur.iTree = pList->iTab;
1331 6 : cur.eSkip = SKIP_NONE;
1332 6 : memRbtreeInsert( &cur, pList->pKey,
1333 : pList->nKey, pList->pData, pList->nData );
1334 6 : break;
1335 : case ROLLBACK_DELETE:
1336 0 : cur.pTree = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
1337 : assert(cur.pTree);
1338 0 : cur.iTree = pList->iTab;
1339 0 : cur.eSkip = SKIP_NONE;
1340 0 : memRbtreeMoveto(&cur, pList->pKey, pList->nKey, &res);
1341 : assert(res == 0);
1342 0 : memRbtreeDelete( &cur );
1343 0 : break;
1344 : case ROLLBACK_CREATE:
1345 0 : btreeCreateTable(pRbtree, pList->iTab);
1346 0 : break;
1347 : case ROLLBACK_DROP:
1348 0 : memRbtreeDropTable(pRbtree, pList->iTab);
1349 : break;
1350 : default:
1351 : assert(0);
1352 : }
1353 6 : sqliteFree(pList->pKey);
1354 6 : sqliteFree(pList->pData);
1355 6 : pTmp = pList->pNext;
1356 6 : sqliteFree(pList);
1357 6 : pList = pTmp;
1358 : }
1359 8 : }
1360 :
1361 : static int memRbtreeRollback(Rbtree* tree)
1362 4 : {
1363 4 : tree->eTransState = TRANS_ROLLBACK;
1364 4 : execute_rollback_list(tree, tree->pCheckRollback);
1365 4 : execute_rollback_list(tree, tree->pTransRollback);
1366 4 : tree->pTransRollback = 0;
1367 4 : tree->pCheckRollback = 0;
1368 4 : tree->pCheckRollbackTail = 0;
1369 4 : tree->eTransState = TRANS_NONE;
1370 4 : return SQLITE_OK;
1371 : }
1372 :
1373 : static int memRbtreeBeginCkpt(Rbtree* tree)
1374 0 : {
1375 0 : if( tree->eTransState != TRANS_INTRANSACTION )
1376 0 : return SQLITE_ERROR;
1377 :
1378 : assert( tree->pCheckRollback == 0 );
1379 : assert( tree->pCheckRollbackTail == 0 );
1380 0 : tree->eTransState = TRANS_INCHECKPOINT;
1381 0 : return SQLITE_OK;
1382 : }
1383 :
1384 : static int memRbtreeCommitCkpt(Rbtree* tree)
1385 0 : {
1386 0 : if( tree->eTransState == TRANS_INCHECKPOINT ){
1387 0 : if( tree->pCheckRollback ){
1388 0 : tree->pCheckRollbackTail->pNext = tree->pTransRollback;
1389 0 : tree->pTransRollback = tree->pCheckRollback;
1390 0 : tree->pCheckRollback = 0;
1391 0 : tree->pCheckRollbackTail = 0;
1392 : }
1393 0 : tree->eTransState = TRANS_INTRANSACTION;
1394 : }
1395 0 : return SQLITE_OK;
1396 : }
1397 :
1398 : static int memRbtreeRollbackCkpt(Rbtree* tree)
1399 2 : {
1400 2 : if( tree->eTransState != TRANS_INCHECKPOINT ) return SQLITE_OK;
1401 0 : tree->eTransState = TRANS_ROLLBACK;
1402 0 : execute_rollback_list(tree, tree->pCheckRollback);
1403 0 : tree->pCheckRollback = 0;
1404 0 : tree->pCheckRollbackTail = 0;
1405 0 : tree->eTransState = TRANS_INTRANSACTION;
1406 0 : 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 0 : {
1425 0 : return 0;
1426 : }
1427 :
1428 : /*
1429 : ** Return the full pathname of the underlying database file.
1430 : */
1431 0 : static const char *memRbtreeGetFilename(Rbtree *pBt){
1432 0 : 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 0 : static int memRbtreeCopyFile(Rbtree *pBt, Rbtree *pBt2){
1439 0 : 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 */
|
