1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
|
/**
* Copyright (C) 2012 10gen Inc.
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU Affero General Public License, version 3,
* as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU Affero General Public License for more details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#pragma once
#include "mongo/db/diskloc.h"
#include "mongo/db/jsobj.h"
#include "mongo/platform/cstdint.h"
namespace mongo {
class IndexDetails;
/**
* Physical location of a key within a btree. Comprised of the DiskLoc address of a btree
* bucket and the index of a key within that bucket.
*/
struct BtreeKeyLocation {
BtreeKeyLocation() :
pos() {
}
BtreeKeyLocation( DiskLoc initialBucket, int32_t initialPos ) :
bucket( initialBucket ),
pos( initialPos ) {
}
bool operator==( const BtreeKeyLocation& other ) const {
return bucket == other.bucket && pos == other.pos;
}
DiskLoc bucket; // Bucket within btree.
int32_t pos; // Index within bucket.
};
std::ostream& operator<<( std::ostream& stream, const BtreeKeyLocation& loc );
/**
* Logical btree position independent of the physical structure of a btree. This is used to
* track a position within a btree while the structure of the btree is changing.
*
* For example, a btree containing keys 'a', 'b', and 'c' might have all three keys in one
* bucket or alternatively 'b' within a left child of 'c'. The same LogicalBtreePosition can
* represent the position of 'b' in both cases and can retrieve the physical BtreeKeyLocation of
* 'b' in each case. If the btree is changed so that it lacks a 'b' key, the position will
* reference the lowest key greater than 'b'. This is desirable behavior when the logical btree
* position is used to implement a forward direction iterator.
*
* The class is seeded with a BtreeKeyLocation identifying a btree key. This initial physical
* location is cached in order to quickly check if the physical location corresponding to the
* logical position is unchanged and can be returned as is.
*
* NOTE Only supports V1 indexes.
*/
class LogicalBtreePosition {
public:
/**
* Create a position with the @param 'indexDetails', @param 'ordering', and initial key
* location @param 'initialLocation' specified.
* @fasserts if 'indexDetails' is not a V1 index.
*/
LogicalBtreePosition( const IndexDetails& indexDetails,
Ordering ordering,
const BtreeKeyLocation& initialLocation );
/** Initialize the position by reading the key at the supplied initial location. */
void init();
/**
* Invalidate the supplied initial location. This may be called when bucket containing the
* supplied location is deleted.
*/
void invalidateInitialLocation() { _initialLocationValid = false; }
/**
* Retrieve the current physical location in the btree corresponding to this logical
* position.
*/
BtreeKeyLocation currentLocation() const;
private:
const IndexDetails* _indexDetails;
Ordering _ordering;
BtreeKeyLocation _initialLocation;
bool _initialLocationValid;
BSONObj _key;
DiskLoc _record;
};
} // namespace mongo
|
