Branch data Line data Source code
1 : : /* chert_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 "chert_cursor.h"
25 : :
26 : : #include "safeerrno.h"
27 : :
28 : : #include <xapian/error.h>
29 : :
30 : : #include "chert_table.h"
31 : : #include "debuglog.h"
32 : : #include "omassert.h"
33 : :
34 : : #ifdef XAPIAN_DEBUG_LOG
35 : : static string
36 : : hex_display_encode(const string & input)
37 : : {
38 : : const char * table = "0123456789abcdef";
39 : : string result;
40 : : for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
41 : : unsigned char val = *i;
42 : : result += "\\x";
43 : : result += table[val/16];
44 : : result += table[val%16];
45 : : }
46 : :
47 : : return result;
48 : : }
49 : : #endif
50 : :
51 : : #define DIR_START 11
52 : :
53 : 2015087 : ChertCursor::ChertCursor(const ChertTable *B_)
54 : : : is_positioned(false),
55 : : is_after_end(false),
56 : : tag_status(UNREAD),
57 : : B(B_),
58 : : version(B_->cursor_version),
59 : 2015087 : level(B_->level)
60 : : {
61 : 2015087 : B->cursor_created_since_last_modification = true;
62 [ + + ][ + + ]: 7761679 : C = new Cursor[level + 1];
63 : :
64 [ + + ][ + + ]: 5746592 : for (int j = 0; j < level; j++) {
65 : 3731505 : C[j].n = BLK_UNUSED;
66 : 3731505 : C[j].p = new byte[B->block_size];
67 : : }
68 : 2015087 : C[level].n = B->C[level].n;
69 : 2015087 : C[level].p = B->C[level].p;
70 : 2015087 : }
71 : :
72 : : void
73 : 6 : ChertCursor::rebuild()
74 : : {
75 : 6 : int new_level = B->level;
76 [ + - ]: 6 : if (new_level <= level) {
77 [ + + ]: 12 : for (int i = 0; i < new_level; i++) {
78 : 6 : C[i].n = BLK_UNUSED;
79 : : }
80 [ - + ]: 6 : for (int j = new_level; j < level; ++j) {
81 : 0 : delete C[j].p;
82 : : }
83 : : } else {
84 : 0 : Cursor * old_C = C;
85 [ # # ]: 0 : C = new Cursor[new_level + 1];
86 [ # # ]: 0 : for (int i = 0; i < level; i++) {
87 : 0 : C[i].p = old_C[i].p;
88 : 0 : C[i].n = BLK_UNUSED;
89 : : }
90 : 0 : delete old_C;
91 [ # # ]: 0 : for (int j = level; j < new_level; j++) {
92 : 0 : C[j].p = new byte[B->block_size];
93 : 0 : C[j].n = BLK_UNUSED;
94 : : }
95 : : }
96 : 6 : level = new_level;
97 : 6 : C[level].n = B->C[level].n;
98 : 6 : C[level].p = B->C[level].p;
99 : 6 : version = B->cursor_version;
100 : 6 : }
101 : :
102 : 2015087 : ChertCursor::~ChertCursor()
103 : : {
104 : : // Use the value of level stored in the cursor rather than the
105 : : // Btree, since the Btree might have been deleted already.
106 [ + + ][ + + ]: 5746592 : for (int j = 0; j < level; j++) {
107 [ + - ][ + - ]: 3731505 : delete [] C[j].p;
108 : : }
109 [ + - ][ + - ]: 2015087 : delete [] C;
110 : 2015087 : }
111 : :
112 : : bool
113 : 5112 : ChertCursor::prev()
114 : : {
115 : : LOGCALL(DB, bool, "ChertCursor::prev", NO_ARGS);
116 : : Assert(!is_after_end);
117 [ + - ][ - + ]: 5112 : if (B->cursor_version != version || !is_positioned) {
118 : : // Either the cursor needs rebuilding (in which case find_entry() will
119 : : // call rebuild() and then reposition the cursor), or we've read the
120 : : // last key and tag, and we're now not positioned (in which case we
121 : : // seek to the current key, and then it's as if we read the key but not
122 : : // the tag).
123 [ # # ]: 0 : if (!find_entry(current_key)) {
124 : : // Exact entry was no longer there after rebuild(), and we've
125 : : // automatically ended up on the entry before it.
126 : 0 : RETURN(true);
127 : : }
128 [ - + ]: 5112 : } else if (tag_status != UNREAD) {
129 : 0 : while (true) {
130 [ # # ]: 0 : if (! B->prev(C, 0)) {
131 : 0 : is_positioned = false;
132 : 0 : RETURN(false);
133 : : }
134 [ # # ]: 0 : if (Item(C[0].p, C[0].c).component_of() == 1) {
135 : 0 : break;
136 : : }
137 : : }
138 : : }
139 : :
140 : 5112 : while (true) {
141 [ - + ]: 5112 : if (! B->prev(C, 0)) {
142 : 0 : is_positioned = false;
143 : 0 : RETURN(false);
144 : : }
145 [ + - ]: 5112 : if (Item(C[0].p, C[0].c).component_of() == 1) {
146 : : break;
147 : : }
148 : : }
149 : 5112 : get_key(¤t_key);
150 : 5112 : tag_status = UNREAD;
151 : :
152 : : LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
153 : 5112 : RETURN(true);
154 : : }
155 : :
156 : : bool
157 : 202848 : ChertCursor::next()
158 : : {
159 : : LOGCALL(DB, bool, "ChertCursor::next", NO_ARGS);
160 : : Assert(!is_after_end);
161 [ - + ]: 202848 : if (B->cursor_version != version) {
162 : : // find_entry() will call rebuild().
163 : 0 : (void)find_entry(current_key);
164 : : // If the key was found, we're now pointing to it, otherwise we're
165 : : // pointing to the entry before. Either way, we now want to move to
166 : : // the next key.
167 : : }
168 [ + + ]: 202848 : if (tag_status == UNREAD) {
169 : 291 : while (true) {
170 [ + + ]: 177544 : if (! B->next(C, 0)) {
171 : 108 : is_positioned = false;
172 : 108 : break;
173 : : }
174 [ + + ]: 177436 : if (Item(C[0].p, C[0].c).component_of() == 1) {
175 : 177145 : is_positioned = true;
176 : 177145 : break;
177 : : }
178 : : }
179 : : }
180 : :
181 [ + + ]: 202848 : if (!is_positioned) {
182 : 301 : is_after_end = true;
183 : 301 : RETURN(false);
184 : : }
185 : :
186 : 202547 : get_key(¤t_key);
187 : 202547 : tag_status = UNREAD;
188 : :
189 : : LOGLINE(DB, "Moved to entry: key=" << hex_display_encode(current_key));
190 : 202848 : RETURN(true);
191 : : }
192 : :
193 : : bool
194 : 2109213 : ChertCursor::find_entry(const string &key)
195 : : {
196 : : LOGCALL(DB, bool, "ChertCursor::find_entry", key);
197 [ - + ]: 2109213 : if (B->cursor_version != version) {
198 : 0 : rebuild();
199 : : }
200 : :
201 : 2109213 : is_after_end = false;
202 : :
203 : : bool found;
204 : :
205 : 2109213 : is_positioned = true;
206 [ + + ]: 2109213 : if (key.size() > CHERT_BTREE_MAX_KEY_LEN) {
207 : : // Can't find key - too long to possibly be present, so find the
208 : : // truncated form but ignore "found".
209 : 30 : B->form_key(key.substr(0, CHERT_BTREE_MAX_KEY_LEN));
210 : 30 : (void)(B->find(C));
211 : 30 : found = false;
212 : : } else {
213 : 2109183 : B->form_key(key);
214 : 2109183 : found = B->find(C);
215 : : }
216 : :
217 [ + + ]: 2109213 : if (!found) {
218 [ + + ]: 1911429 : if (C[0].c < DIR_START) {
219 : 38080 : C[0].c = DIR_START;
220 [ - + ]: 38080 : if (! B->prev(C, 0)) goto done;
221 : : }
222 [ + + ]: 5754718 : while (Item(C[0].p, C[0].c).component_of() != 1) {
223 [ - + ]: 3843289 : if (! B->prev(C, 0)) {
224 : 0 : is_positioned = false;
225 : 0 : throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
226 : : }
227 : : }
228 : : }
229 : : done:
230 : :
231 [ + + ]: 2109213 : if (found)
232 : 197784 : current_key = key;
233 : : else
234 : 1911429 : get_key(¤t_key);
235 : 2109213 : tag_status = UNREAD;
236 : :
237 : : LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
238 : 2109213 : RETURN(found);
239 : : }
240 : :
241 : : bool
242 : 17122 : ChertCursor::find_entry_ge(const string &key)
243 : : {
244 : : LOGCALL(DB, bool, "ChertCursor::find_entry_ge", key);
245 [ + + ]: 17122 : if (B->cursor_version != version) {
246 : 6 : rebuild();
247 : : }
248 : :
249 : 17122 : is_after_end = false;
250 : :
251 : : bool found;
252 : :
253 : 17122 : is_positioned = true;
254 [ - + ]: 17122 : if (key.size() > CHERT_BTREE_MAX_KEY_LEN) {
255 : : // Can't find key - too long to possibly be present, so find the
256 : : // truncated form but ignore "found".
257 : 0 : B->form_key(key.substr(0, CHERT_BTREE_MAX_KEY_LEN));
258 : 0 : (void)(B->find(C));
259 : 0 : found = false;
260 : : } else {
261 : 17122 : B->form_key(key);
262 : 17122 : found = B->find(C);
263 : : }
264 : :
265 [ + + ]: 17119 : if (found) {
266 : 6573 : current_key = key;
267 : : } else {
268 [ + + ]: 10546 : if (! B->next(C, 0)) {
269 : 5132 : is_after_end = true;
270 : 5132 : is_positioned = false;
271 : 5132 : RETURN(false);
272 : : }
273 : : Assert(Item(C[0].p, C[0].c).component_of() == 1);
274 : 5414 : get_key(¤t_key);
275 : : }
276 : 11987 : tag_status = UNREAD;
277 : :
278 : : LOGLINE(DB, "Found entry: key=" << hex_display_encode(current_key));
279 : 17119 : RETURN(found);
280 : : }
281 : :
282 : : void
283 : 2124502 : ChertCursor::get_key(string * key) const
284 : : {
285 : : Assert(B->level <= level);
286 : : Assert(is_positioned);
287 : :
288 : 2124502 : (void)Item(C[0].p, C[0].c).key().read(key);
289 : 2124502 : }
290 : :
291 : : bool
292 : 1932789 : ChertCursor::read_tag(bool keep_compressed)
293 : : {
294 : : LOGCALL(DB, bool, "ChertCursor::read_tag", keep_compressed);
295 [ + + ]: 1932789 : if (tag_status == UNREAD) {
296 : : Assert(B->level <= level);
297 : : Assert(is_positioned);
298 : :
299 [ + + ]: 1932732 : if (B->read_tag(C, ¤t_tag, keep_compressed)) {
300 : 157 : tag_status = COMPRESSED;
301 : : } else {
302 : 1932575 : tag_status = UNCOMPRESSED;
303 : : }
304 : :
305 : : // We need to call B->next(...) after B->read_tag(...) so that the
306 : : // cursor ends up on the next key.
307 : 1932732 : is_positioned = B->next(C, 0);
308 : :
309 : : LOGLINE(DB, "tag=" << hex_display_encode(current_tag));
310 : : }
311 : 1932789 : RETURN(tag_status == COMPRESSED);
312 : : }
313 : :
314 : : bool
315 : 18 : MutableChertCursor::del()
316 : : {
317 : : Assert(!is_after_end);
318 : :
319 : : // MutableChertCursor is only constructable from a non-const ChertTable*
320 : : // but we store that in the const ChertTable* "B" member of the ChertCursor
321 : : // class to avoid duplicating storage. So we know it is safe to cast away
322 : : // that const again here.
323 : 18 : (const_cast<ChertTable*>(B))->del(current_key);
324 : :
325 : : // If we're iterating an older revision of the tree, then the deletion
326 : : // happens in a new (uncommitted) revision and the cursor still sees
327 : : // the deleted key. But if we're iterating the new uncommitted revision
328 : : // then the deleted key is no longer visible. We need to handle both
329 : : // cases - either find_entry_ge() finds the deleted key or not.
330 [ + + ]: 18 : if (!find_entry_ge(current_key)) return is_positioned;
331 : 18 : return next();
332 : : }
|
