Branch data Line data Source code
1 : : /* brass_cursor.cc: Btree cursor implementation
2 : : *
3 : : * Copyright 1999,2000,2001 BrightStation PLC
4 : : * Copyright 2002,2003,2004,2005,2006,2007,2008,2009,2010 Olly Betts
5 : : *
6 : : * This program is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU General Public License as
8 : : * published by the Free Software Foundation; either version 2 of the
9 : : * License, or (at your option) any later version.
10 : : *
11 : : * This program is distributed in the hope that it will be useful,
12 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 : : * GNU General Public License for more details.
15 : : *
16 : : * You should have received a copy of the GNU General Public License
17 : : * along with this program; if not, write to the Free Software
18 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301
19 : : * USA
20 : : */
21 : :
22 : : #include <config.h>
23 : :
24 : : #include "brass_cursor.h"
25 : :
26 : : #include "safeerrno.h"
27 : :
28 : : #include <xapian/error.h>
29 : :
30 : : #include "brass_table.h"
31 : : #include "debuglog.h"
32 : : #include "omassert.h"
33 : :
34 : : using namespace Brass;
35 : :
36 : : #ifdef XAPIAN_DEBUG_LOG
37 : : static string
38 : : hex_display_encode(const string & input)
39 : : {
40 : : const char * table = "0123456789abcdef";
41 : : string result;
42 : : for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
43 : : unsigned char val = *i;
44 : : result += "\\x";
45 : : result += table[val/16];
46 : : result += table[val%16];
47 : : }
48 : :
49 : : return result;
50 : : }
51 : : #endif
52 : :
53 : : #define DIR_START 11
54 : :
55 : 2004692 : BrassCursor::BrassCursor(const BrassTable *B_)
56 : : : is_positioned(false),
57 : : is_after_end(false),
58 : : tag_status(UNREAD),
59 : : B(B_),
60 : : version(B_->cursor_version),
61 : 2004692 : level(B_->level)
62 : : {
63 : 2004692 : B->cursor_created_since_last_modification = true;
64 [ + + ][ + + ]: 7740727 : C = new Brass::Cursor[level + 1];
65 : :
66 [ + + ][ + + ]: 5736035 : for (int j = 0; j < level; j++) {
67 : 3731343 : C[j].n = BLK_UNUSED;
68 : 3731343 : C[j].p = new byte[B->block_size];
69 : : }
70 : 2004692 : C[level].n = B->C[level].n;
71 : 2004692 : C[level].p = B->C[level].p;
72 : 2004692 : }
73 : :
74 : : void
75 : 6 : BrassCursor::rebuild()
76 : : {
77 : 6 : int new_level = B->level;
78 [ + - ]: 6 : if (new_level <= level) {
79 [ + + ]: 12 : for (int i = 0; i < new_level; i++) {
80 : 6 : C[i].n = BLK_UNUSED;
81 : : }
82 [ - + ]: 6 : for (int j = new_level; j < level; ++j) {
83 : 0 : delete C[j].p;
84 : : }
85 : : } else {
86 : 0 : Cursor * old_C = C;
87 [ # # ]: 0 : C = new Cursor[new_level + 1];
88 [ # # ]: 0 : for (int i = 0; i < level; i++) {
89 : 0 : C[i].p = old_C[i].p;
90 : 0 : C[i].n = BLK_UNUSED;
91 : : }
92 : 0 : delete old_C;
93 [ # # ]: 0 : for (int j = level; j < new_level; j++) {
94 : 0 : C[j].p = new byte[B->block_size];
95 : 0 : C[j].n = BLK_UNUSED;
96 : : }
97 : : }
98 : 6 : level = new_level;
99 : 6 : C[level].n = B->C[level].n;
100 : 6 : C[level].p = B->C[level].p;
101 : 6 : version = B->cursor_version;
102 : 6 : }
103 : :
104 : 2004692 : BrassCursor::~BrassCursor()
105 : : {
106 : : // Use the value of level stored in the cursor rather than the
107 : : // Btree, since the Btree might have been deleted already.
108 [ + + ][ + + ]: 5736035 : for (int j = 0; j < level; j++) {
109 [ + - ][ + - ]: 3731343 : delete [] C[j].p;
110 : : }
111 [ + - ][ + - ]: 2004692 : delete [] C;
112 : 2004692 : }
113 : :
114 : : bool
115 : 8 : BrassCursor::prev()
116 : : {
117 : : LOGCALL(DB, bool, "BrassCursor::prev", NO_ARGS);
118 : : Assert(!is_after_end);
119 [ + - ][ - + ]: 8 : if (B->cursor_version != version || !is_positioned) {
120 : : // Either the cursor needs rebuilding (in which case find_entry() will
121 : : // call rebuild() and then reposition the cursor), or we've read the
122 : : // last key and tag, and we're now not positioned (in which case we
123 : : // seek to the current key, and then it's as if we read the key but not
124 : : // the tag).
125 [ # # ]: 0 : if (!find_entry(current_key)) {
126 : : // Exact entry was no longer there after rebuild(), and we've
127 : : // automatically ended up on the entry before it.
128 : 0 : RETURN(true);
129 : : }
130 [ - + ]: 8 : } else if (tag_status != UNREAD) {
131 : 0 : while (true) {
132 [ # # ]: 0 : if (! B->prev(C, 0)) {
133 : 0 : is_positioned = false;
134 : 0 : RETURN(false);
135 : : }
136 [ # # ]: 0 : if (Item(C[0].p, C[0].c).component_of() == 1) {
137 : 0 : break;
138 : : }
139 : : }
140 : : }
141 : :
142 : 8 : while (true) {
143 [ - + ]: 8 : if (! B->prev(C, 0)) {
144 : 0 : is_positioned = false;
145 : 0 : RETURN(false);
146 : : }
147 [ + - ]: 8 : if (Item(C[0].p, C[0].c).component_of() == 1) {
148 : : break;
149 : : }
150 : : }
151 : 8 : get_key(¤t_key);
152 : 8 : tag_status = UNREAD;
153 : :
154 : : LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
155 : 8 : RETURN(true);
156 : : }
157 : :
158 : : bool
159 : 192732 : BrassCursor::next()
160 : : {
161 : : LOGCALL(DB, bool, "BrassCursor::next", NO_ARGS);
162 : : Assert(!is_after_end);
163 [ - + ]: 192732 : if (B->cursor_version != version) {
164 : : // find_entry() will call rebuild().
165 : 0 : (void)find_entry(current_key);
166 : : // If the key was found, we're now pointing to it, otherwise we're
167 : : // pointing to the entry before. Either way, we now want to move to
168 : : // the next key.
169 : : }
170 [ + + ]: 192732 : if (tag_status == UNREAD) {
171 : 291 : while (true) {
172 [ + + ]: 167430 : if (! B->next(C, 0)) {
173 : 77 : is_positioned = false;
174 : 77 : break;
175 : : }
176 [ + + ]: 167353 : if (Item(C[0].p, C[0].c).component_of() == 1) {
177 : 167062 : is_positioned = true;
178 : 167062 : break;
179 : : }
180 : : }
181 : : }
182 : :
183 [ + + ]: 192732 : if (!is_positioned) {
184 : 266 : is_after_end = true;
185 : 266 : RETURN(false);
186 : : }
187 : :
188 : 192466 : get_key(¤t_key);
189 : 192466 : tag_status = UNREAD;
190 : :
191 : : LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
192 : 192732 : RETURN(true);
193 : : }
194 : :
195 : : bool
196 : 2098823 : BrassCursor::find_entry(const string &key)
197 : : {
198 : : LOGCALL(DB, bool, "BrassCursor::find_entry", key);
199 [ - + ]: 2098823 : if (B->cursor_version != version) {
200 : 0 : rebuild();
201 : : }
202 : :
203 : 2098823 : is_after_end = false;
204 : :
205 : : bool found;
206 : :
207 : 2098823 : is_positioned = true;
208 [ + + ]: 2098823 : if (key.size() > BRASS_BTREE_MAX_KEY_LEN) {
209 : : // Can't find key - too long to possibly be present, so find the
210 : : // truncated form but ignore "found".
211 : 30 : B->form_key(key.substr(0, BRASS_BTREE_MAX_KEY_LEN));
212 : 30 : (void)(B->find(C));
213 : 30 : found = false;
214 : : } else {
215 : 2098793 : B->form_key(key);
216 : 2098793 : found = B->find(C);
217 : : }
218 : :
219 [ + + ]: 2098823 : if (!found) {
220 [ + + ]: 1906282 : if (C[0].c < DIR_START) {
221 : 38080 : C[0].c = DIR_START;
222 [ - + ]: 38080 : if (! B->prev(C, 0)) goto done;
223 : : }
224 [ + + ]: 5749571 : while (Item(C[0].p, C[0].c).component_of() != 1) {
225 [ - + ]: 3843289 : if (! B->prev(C, 0)) {
226 : 0 : is_positioned = false;
227 : 0 : throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
228 : : }
229 : : }
230 : : }
231 : : done:
232 : :
233 [ + + ]: 2098823 : if (found)
234 : 192541 : current_key = key;
235 : : else
236 : 1906282 : get_key(¤t_key);
237 : 2098823 : tag_status = UNREAD;
238 : :
239 : : LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
240 : 2098823 : RETURN(found);
241 : : }
242 : :
243 : : bool
244 : 1819 : BrassCursor::find_entry_ge(const string &key)
245 : : {
246 : : LOGCALL(DB, bool, "BrassCursor::find_entry_ge", key);
247 [ + + ]: 1819 : if (B->cursor_version != version) {
248 : 6 : rebuild();
249 : : }
250 : :
251 : 1819 : is_after_end = false;
252 : :
253 : : bool found;
254 : :
255 : 1819 : is_positioned = true;
256 [ - + ]: 1819 : if (key.size() > BRASS_BTREE_MAX_KEY_LEN) {
257 : : // Can't find key - too long to possibly be present, so find the
258 : : // truncated form but ignore "found".
259 : 0 : B->form_key(key.substr(0, BRASS_BTREE_MAX_KEY_LEN));
260 : 0 : (void)(B->find(C));
261 : 0 : found = false;
262 : : } else {
263 : 1819 : B->form_key(key);
264 : 1819 : found = B->find(C);
265 : : }
266 : :
267 [ + + ]: 1816 : if (found) {
268 : 1379 : current_key = key;
269 : : } else {
270 [ + + ]: 437 : if (! B->next(C, 0)) {
271 : 40 : is_after_end = true;
272 : 40 : is_positioned = false;
273 : 40 : RETURN(false);
274 : : }
275 : : Assert(Item(C[0].p, C[0].c).component_of() == 1);
276 : 397 : get_key(¤t_key);
277 : : }
278 : 1776 : tag_status = UNREAD;
279 : :
280 : : LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
281 : 1816 : RETURN(found);
282 : : }
283 : :
284 : : void
285 : 2099153 : BrassCursor::get_key(string * key) const
286 : : {
287 : : Assert(B->level <= level);
288 : : Assert(is_positioned);
289 : :
290 : 2099153 : (void)Item(C[0].p, C[0].c).key().read(key);
291 : 2099153 : }
292 : :
293 : : bool
294 : 1932604 : BrassCursor::read_tag(bool keep_compressed)
295 : : {
296 : : LOGCALL(DB, bool, "BrassCursor::read_tag", keep_compressed);
297 [ + + ]: 1932604 : if (tag_status == UNREAD) {
298 : : Assert(B->level <= level);
299 : : Assert(is_positioned);
300 : :
301 [ + + ]: 1932547 : if (B->read_tag(C, ¤t_tag, keep_compressed)) {
302 : 157 : tag_status = COMPRESSED;
303 : : } else {
304 : 1932390 : tag_status = UNCOMPRESSED;
305 : : }
306 : :
307 : : // We need to call B->next(...) after B->read_tag(...) so that the
308 : : // cursor ends up on the next key.
309 : 1932547 : is_positioned = B->next(C, 0);
310 : :
311 : : LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
312 : : }
313 : 1932604 : RETURN(tag_status == COMPRESSED);
314 : : }
315 : :
316 : : bool
317 : 18 : MutableBrassCursor::del()
318 : : {
319 : : Assert(!is_after_end);
320 : :
321 : : // MutableBrassCursor is only constructable from a non-const BrassTable*
322 : : // but we store that in the const BrassTable* "B" member of the BrassCursor
323 : : // class to avoid duplicating storage. So we know it is safe to cast away
324 : : // that const again here.
325 : 18 : (const_cast<BrassTable*>(B))->del(current_key);
326 : :
327 : : // If we're iterating an older revision of the tree, then the deletion
328 : : // happens in a new (uncommitted) revision and the cursor still sees
329 : : // the deleted key. But if we're iterating the new uncommitted revision
330 : : // then the deleted key is no longer visible. We need to handle both
331 : : // cases - either find_entry_ge() finds the deleted key or not.
332 [ + + ]: 18 : if (!find_entry_ge(current_key)) return is_positioned;
333 : 18 : return next();
334 : : }
|