/ Check-in [966b1a16]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Add locks to the in-memory database so that recursive writes will be detected and rejected. Ticket #436. (CVS 1090)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 966b1a16f6687df08f8c21787c1c8b1af1d79e1e
User & Date: drh 2003-08-27 22:52:34
Context
2003-08-27
22:54
Add locks to the in-memory backend so that recursive writes will be detected and rejected. Ticket #436. (CVS 1089) check-in: 3403d28a user: drh tags: trunk
22:52
Add locks to the in-memory database so that recursive writes will be detected and rejected. Ticket #436. (CVS 1090) check-in: 966b1a16 user: drh tags: trunk
2003-08-26
11:41
Fix compiler warnings under OpenVMS. Ticket #357. (CVS 1088) check-in: c95f347c user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree_rb.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
..
95
96
97
98
99
100
101

102

103
104
105
106
107
108
109
110
111
112
113

114
115
116
117
118
119
120
121
...
135
136
137
138
139
140
141



























142
143
144
145
146
147
148
...
632
633
634
635
636
637
638

639
640
641
642
643
644
645
...
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680

681
682
683
684
685
686




687
688
689
690
691
692
693
...
706
707
708
709
710
711
712





713
714
715
716
717
718
719
...
864
865
866
867
868
869
870





871
872
873
874
875
876
877
....
1142
1143
1144
1145
1146
1147
1148










1149
1150
1151
1152
1153
1154
1155
....
1245
1246
1247
1248
1249
1250
1251

1252
1253
1254
1255
1256
1257
1258
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree_rb.c,v 1.14 2003/06/29 18:29:48 drh Exp $
**
** This file implements an in-core database using Red-Black balanced
** binary trees.
**
** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC.
*/
#include "btree.h"
................................................................................

struct RbtCursor {
  BtCursorOps *pOps;        /* Function table */
  Rbtree    *pRbtree;
  BtRbTree *pTree;
  int       iTree;          /* Index of pTree in pRbtree */
  BtRbNode *pNode;

  u8 eSkip;                 /* Determines if next step operation is a no-op */

};

/*
** Legal values for RbtCursor.eSkip.
*/
#define SKIP_NONE     0   /* Always step the cursor */
#define SKIP_NEXT     1   /* The next sqliteRbtreeNext() is a no-op */
#define SKIP_PREV     2   /* The next sqliteRbtreePrevious() is a no-op */
#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */

struct BtRbTree {

  BtRbNode *pHead;   /* Head of the tree, or NULL */
};

struct BtRbNode {
  int nKey;
  void *pKey;
  int nData;
  void *pData;
................................................................................
  int *pRes
);
static int memRbtreeClearTable(Rbtree* tree, int n);
static int memRbtreeNext(RbtCursor* pCur, int *pRes);
static int memRbtreeLast(RbtCursor* pCur, int *pRes);
static int memRbtreePrevious(RbtCursor* pCur, int *pRes);




























/*
 * The key-compare function for the red-black trees. Returns as follows:
 *
 * (key1 < key2)             -1
 * (key1 == key2)             0 
 * (key1 > key2)              1
 *
................................................................................
{
  BtRbTree *pTree;
  assert( tree->eTransState != TRANS_NONE );

  memRbtreeClearTable(tree, n);
  pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
  assert(pTree);

  sqliteFree(pTree);

  if( tree->eTransState != TRANS_ROLLBACK ){
    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
    pRollbackOp->eOp = ROLLBACK_CREATE;
    pRollbackOp->iTab = n;
    btreeLogRollbackOp(tree, pRollbackOp);
................................................................................
    }
  }
  return SQLITE_OK;
}

/*
 * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
 * parameter is ignored, all cursors are capable of write-operations. 
 *
 * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
 */
static int memRbtreeCursor(
  Rbtree* tree,
  int iTable,
  int wrFlag,
  RbtCursor **ppCur
){

  assert(tree);
  *ppCur = sqliteMalloc(sizeof(RbtCursor));
  (*ppCur)->pTree  = sqliteHashFind(&tree->tblHash, 0, iTable);
  (*ppCur)->pRbtree = tree;
  (*ppCur)->iTree  = iTable;
  (*ppCur)->pOps = &sqliteRbtreeCursorOps;





  assert( (*ppCur)->pTree );
  return SQLITE_OK;
}

/*
 * Insert a new record into the Rbtree.  The key is given by (pKey,nKey)
................................................................................
){
  void * pData;
  int match;

  /* It is illegal to call sqliteRbtreeInsert() if we are
  ** not in a transaction */
  assert( pCur->pRbtree->eTransState != TRANS_NONE );






  /* Take a copy of the input data now, in case we need it for the 
   * replace case */
  pData = sqliteMalloc(nData);
  memcpy(pData, pDataInput, nData);

  /* Move the cursor to a node near the key to be inserted. If the key already
................................................................................
{
  BtRbNode *pZ;      /* The one being deleted */
  BtRbNode *pChild;  /* The child of the spliced out node */

  /* It is illegal to call sqliteRbtreeDelete() if we are
  ** not in a transaction */
  assert( pCur->pRbtree->eTransState != TRANS_NONE );






  pZ = pCur->pNode;
  if( !pZ ){
    return SQLITE_OK;
  }

  /* If we are not currently doing a rollback, set up a rollback op for this 
................................................................................
    return pCur->pNode->nData-offset;
  }
  assert(0);
}

static int memRbtreeCloseCursor(RbtCursor* pCur)
{










  sqliteFree(pCur);
  return SQLITE_OK;
}

static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
{
  memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
................................................................................
static void execute_rollback_list(Rbtree *pRbtree, BtRollbackOp *pList)
{
  BtRollbackOp *pTmp;
  RbtCursor cur;
  int res;

  cur.pRbtree = pRbtree;

  while( pList ){
    switch( pList->eOp ){
      case ROLLBACK_INSERT:
        cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
        assert(cur.pTree);
        cur.iTree  = pList->iTab;
        cur.eSkip  = SKIP_NONE;







|







 







>

>











>
|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







>







 







|









>

|
|
|
|
|
>
>
>
>







 







>
>
>
>
>







 







>
>
>
>
>







 







>
>
>
>
>
>
>
>
>
>







 







>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
..
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
...
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
...
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
...
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
...
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
...
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
....
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
....
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree_rb.c,v 1.15 2003/08/27 22:52:34 drh Exp $
**
** This file implements an in-core database using Red-Black balanced
** binary trees.
**
** It was contributed to SQLite by anonymous on 2003-Feb-04 23:24:49 UTC.
*/
#include "btree.h"
................................................................................

struct RbtCursor {
  BtCursorOps *pOps;        /* Function table */
  Rbtree    *pRbtree;
  BtRbTree *pTree;
  int       iTree;          /* Index of pTree in pRbtree */
  BtRbNode *pNode;
  RbtCursor *pShared;       /* List of all cursors on the same Rbtree */
  u8 eSkip;                 /* Determines if next step operation is a no-op */
  u8 wrFlag;                /* True if this cursor is open for writing */
};

/*
** Legal values for RbtCursor.eSkip.
*/
#define SKIP_NONE     0   /* Always step the cursor */
#define SKIP_NEXT     1   /* The next sqliteRbtreeNext() is a no-op */
#define SKIP_PREV     2   /* The next sqliteRbtreePrevious() is a no-op */
#define SKIP_INVALID  3   /* Calls to Next() and Previous() are invalid */

struct BtRbTree {
  RbtCursor *pCursors;     /* All cursors pointing to this tree */
  BtRbNode *pHead;         /* Head of the tree, or NULL */
};

struct BtRbNode {
  int nKey;
  void *pKey;
  int nData;
  void *pData;
................................................................................
  int *pRes
);
static int memRbtreeClearTable(Rbtree* tree, int n);
static int memRbtreeNext(RbtCursor* pCur, int *pRes);
static int memRbtreeLast(RbtCursor* pCur, int *pRes);
static int memRbtreePrevious(RbtCursor* pCur, int *pRes);


/*
** This routine checks all cursors that point to the same table
** as pCur points to.  If any of those cursors were opened with
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
** cursors point to the same table were opened with wrFlag==1
** then this routine returns SQLITE_OK.
**
** In addition to checking for read-locks (where a read-lock 
** means a cursor opened with wrFlag==0) this routine also NULLs
** out the pNode field of all other cursors.
** This is necessary because an insert 
** or delete might change erase the node out from under
** another cursor.
*/
static int checkReadLocks(RbtCursor *pCur){
  RbtCursor *p;
  assert( pCur->wrFlag );
  for(p=pCur->pTree->pCursors; p; p=p->pShared){
    if( p!=pCur ){
      if( p->wrFlag==0 ) return SQLITE_LOCKED;
      p->pNode = 0;
    }
  }
  return SQLITE_OK;
}

/*
 * The key-compare function for the red-black trees. Returns as follows:
 *
 * (key1 < key2)             -1
 * (key1 == key2)             0 
 * (key1 > key2)              1
 *
................................................................................
{
  BtRbTree *pTree;
  assert( tree->eTransState != TRANS_NONE );

  memRbtreeClearTable(tree, n);
  pTree = sqliteHashInsert(&tree->tblHash, 0, n, 0);
  assert(pTree);
  assert( pTree->pCursors==0 );
  sqliteFree(pTree);

  if( tree->eTransState != TRANS_ROLLBACK ){
    BtRollbackOp *pRollbackOp = sqliteMalloc(sizeof(BtRollbackOp));
    pRollbackOp->eOp = ROLLBACK_CREATE;
    pRollbackOp->iTab = n;
    btreeLogRollbackOp(tree, pRollbackOp);
................................................................................
    }
  }
  return SQLITE_OK;
}

/*
 * Get a new cursor for table iTable of the supplied Rbtree. The wrFlag
 * parameter indicates that the cursor is open for writing.
 *
 * Note that RbtCursor.eSkip and RbtCursor.pNode both initialize to 0.
 */
static int memRbtreeCursor(
  Rbtree* tree,
  int iTable,
  int wrFlag,
  RbtCursor **ppCur
){
  RbtCursor *pCur;
  assert(tree);
  pCur = *ppCur = sqliteMalloc(sizeof(RbtCursor));
  pCur->pTree  = sqliteHashFind(&tree->tblHash, 0, iTable);
  pCur->pRbtree = tree;
  pCur->iTree  = iTable;
  pCur->pOps = &sqliteRbtreeCursorOps;
  pCur->wrFlag = wrFlag;
  pCur->pShared = pCur->pTree->pCursors;
  pCur->pTree->pCursors = pCur;
  

  assert( (*ppCur)->pTree );
  return SQLITE_OK;
}

/*
 * Insert a new record into the Rbtree.  The key is given by (pKey,nKey)
................................................................................
){
  void * pData;
  int match;

  /* It is illegal to call sqliteRbtreeInsert() if we are
  ** not in a transaction */
  assert( pCur->pRbtree->eTransState != TRANS_NONE );

  /* Make sure some other cursor isn't trying to read this same table */
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  /* Take a copy of the input data now, in case we need it for the 
   * replace case */
  pData = sqliteMalloc(nData);
  memcpy(pData, pDataInput, nData);

  /* Move the cursor to a node near the key to be inserted. If the key already
................................................................................
{
  BtRbNode *pZ;      /* The one being deleted */
  BtRbNode *pChild;  /* The child of the spliced out node */

  /* It is illegal to call sqliteRbtreeDelete() if we are
  ** not in a transaction */
  assert( pCur->pRbtree->eTransState != TRANS_NONE );

  /* Make sure some other cursor isn't trying to read this same table */
  if( checkReadLocks(pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }

  pZ = pCur->pNode;
  if( !pZ ){
    return SQLITE_OK;
  }

  /* If we are not currently doing a rollback, set up a rollback op for this 
................................................................................
    return pCur->pNode->nData-offset;
  }
  assert(0);
}

static int memRbtreeCloseCursor(RbtCursor* pCur)
{
  if( pCur->pTree->pCursors==pCur ){
    pCur->pTree->pCursors = pCur->pShared;
  }else{
    RbtCursor *p = pCur->pTree->pCursors;
    while( p && p->pShared!=pCur ){ p = p->pShared; }
    assert( p!=0 );
    if( p ){
      p->pShared = pCur->pShared;
    }
  }
  sqliteFree(pCur);
  return SQLITE_OK;
}

static int memRbtreeGetMeta(Rbtree* tree, int* aMeta)
{
  memcpy( aMeta, tree->aMetaData, sizeof(int) * SQLITE_N_BTREE_META );
................................................................................
static void execute_rollback_list(Rbtree *pRbtree, BtRollbackOp *pList)
{
  BtRollbackOp *pTmp;
  RbtCursor cur;
  int res;

  cur.pRbtree = pRbtree;
  cur.wrFlag = 1;
  while( pList ){
    switch( pList->eOp ){
      case ROLLBACK_INSERT:
        cur.pTree  = sqliteHashFind( &pRbtree->tblHash, 0, pList->iTab );
        assert(cur.pTree);
        cur.iTree  = pList->iTab;
        cur.eSkip  = SKIP_NONE;