Branch data Line data Source code
1 : : /* flint_cursor.h: Interface to Btree cursors
2 : : *
3 : : * Copyright 1999,2000,2001 BrightStation PLC
4 : : * Copyright 2002,2003,2004,2006,2007,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 : : #ifndef OM_HGUARD_FLINT_CURSOR_H
23 : : #define OM_HGUARD_FLINT_CURSOR_H
24 : :
25 : : #include <xapian/visibility.h>
26 : :
27 : : #include "flint_types.h"
28 : :
29 : : #include <string>
30 : : using std::string;
31 : :
32 : : #define BLK_UNUSED uint4(-1)
33 : :
34 : : class Cursor_ {
35 : : private:
36 : : // Prevent copying
37 : : Cursor_(const Cursor_ &);
38 : : Cursor_ & operator=(const Cursor_ &);
39 : :
40 : : public:
41 : : /// Constructor, to initialise important elements.
42 : 532570 : Cursor_() : p(0), c(-1), n(BLK_UNUSED), rewrite(false)
43 : 532570 : {}
44 : :
45 : : /// pointer to a block
46 : : byte * p;
47 : : /// offset in the block's directory
48 : : int c;
49 : : /** block number
50 : : *
51 : : * n is kept in tandem with p. The unassigned state is when
52 : : * p == 0 and n == BLK_UNUSED.
53 : : *
54 : : * Setting n to BLK_UNUSED is necessary in at least some cases.
55 : : */
56 : :
57 : : uint4 n;
58 : : /// true if the block is not the same as on disk, and so needs rewriting
59 : : bool rewrite;
60 : : };
61 : :
62 : : class FlintTable;
63 : :
64 : : /** A cursor pointing to a position in a Btree table, for reading several
65 : : * entries in order, or finding approximate matches.
66 : : */
67 : : class XAPIAN_VISIBILITY_DEFAULT FlintCursor {
68 : : private:
69 : : /// Copying not allowed
70 : : FlintCursor(const FlintCursor &);
71 : :
72 : : /// Assignment not allowed
73 : : FlintCursor & operator=(const FlintCursor &);
74 : :
75 : : /** Rebuild the cursor.
76 : : *
77 : : * Called when the table has changed.
78 : : */
79 : : void rebuild();
80 : :
81 : : /** Whether the cursor is positioned at a valid entry.
82 : : *
83 : : * false initially, and after the cursor has dropped
84 : : * off either end of the list of items
85 : : */
86 : : bool is_positioned;
87 : :
88 : : /** Whether the cursor is off the end of the table.
89 : : */
90 : : bool is_after_end;
91 : :
92 : : /** Status of the current_tag member. */
93 : : enum { UNREAD, UNCOMPRESSED, COMPRESSED } tag_status;
94 : :
95 : : /// The Btree table
96 : : FlintTable * B;
97 : :
98 : : /// Pointer to an array of Cursors
99 : : Cursor_ * C;
100 : :
101 : : unsigned long version;
102 : :
103 : : /** The value of level in the Btree structure. */
104 : : int level;
105 : :
106 : : /** Get the key.
107 : : *
108 : : * The key of the item at the cursor is copied into key.
109 : : *
110 : : * The cursor must be positioned before calling this method.
111 : : *
112 : : * e.g.
113 : : *
114 : : * FlintCursor BC(&btree);
115 : : * string key;
116 : : *
117 : : * // Now do something to each key in the Btree
118 : : * BC.find_entry(""); // must give result true
119 : : *
120 : : * while (BC.next()) {
121 : : * BC.get_key(&key);
122 : : * do_something_to(key);
123 : : * }
124 : : */
125 : : void get_key(string * key) const;
126 : :
127 : : public:
128 : : /** Create a cursor attached to a Btree.
129 : : *
130 : : * Creates a cursor, which can be used to remember a position inside
131 : : * the B-tree. The position is simply the item (key and tag) to which
132 : : * the cursor points. A cursor is either positioned or unpositioned,
133 : : * and is initially unpositioned.
134 : : *
135 : : * NB: You must not try to use a FlintCursor after the Btree it is
136 : : * attached to is destroyed. It's safe to destroy the FlintCursor
137 : : * after the Btree though, you just may not use the FlintCursor.
138 : : */
139 : : FlintCursor(FlintTable *B);
140 : :
141 : : /** Destroy the FlintCursor */
142 : : ~FlintCursor();
143 : :
144 : : /** Current key pointed to by cursor.
145 : : */
146 : : string current_key;
147 : :
148 : : /** Current tag pointed to by cursor. You must call read_tag to
149 : : * make this value available.
150 : : */
151 : : string current_tag;
152 : :
153 : : /** Read the tag from the table and store it in current_tag.
154 : : *
155 : : * Some cursor users don't need the tag, so for efficiency we
156 : : * only read it when asked to.
157 : : *
158 : : * @param keep_compressed Don't uncompress the tag - e.g. useful
159 : : * if it's just being opaquely copied
160 : : * (default: false).
161 : : *
162 : : * @return true if current_tag holds compressed data (always
163 : : * false if keep_compressed was false).
164 : : */
165 : : bool read_tag(bool keep_compressed = false);
166 : :
167 : : /** Advance to the next key.
168 : : *
169 : : * If cursor is unpositioned, the result is simply false.
170 : : *
171 : : * If cursor is positioned, and points to the very last item in the
172 : : * Btree the cursor is made unpositioned, and the result is false.
173 : : * Otherwise the cursor is moved to the next item in the B-tree,
174 : : * and the result is true.
175 : : *
176 : : * Effectively, FlintCursor::next() loses the position of BC when it
177 : : * drops off the end of the list of items. If this is awkward, one can
178 : : * always arrange for a key to be present which has a rightmost
179 : : * position in a set of keys,
180 : : */
181 : : bool next();
182 : :
183 : : /** Move to the previous key.
184 : : *
185 : : * This is like FlintCursor::next, but BC is taken to the previous
186 : : * rather than next item.
187 : : */
188 : : bool prev();
189 : :
190 : : /** Position the cursor on the highest entry with key <= @a key.
191 : : *
192 : : * If the exact key is found in the table, the cursor will be
193 : : * set to point to it, and the method will return true.
194 : : *
195 : : * If the key is not found, the cursor will be set to point to
196 : : * the key preceding that asked for, and the method will return
197 : : * false. If there is no key preceding that asked for, the cursor
198 : : * will point to a null key.
199 : : *
200 : : * Note: Since the B-tree always contains a null key, which precedes
201 : : * everything, a call to FlintCursor::find_entry always results in a
202 : : * valid key being pointed to by the cursor.
203 : : *
204 : : * Note: Calling this method with a null key, then calling next()
205 : : * will leave the cursor pointing to the first key.
206 : : *
207 : : * @param key The key to look for in the table.
208 : : *
209 : : * @return true if the exact key was found in the table, false
210 : : * otherwise.
211 : : */
212 : : bool find_entry(const string &key);
213 : :
214 : : /// Position the cursor on the highest entry with key < @a key.
215 : 28 : void find_entry_lt(const string &key) {
216 [ + + ]: 28 : if (find_entry(key)) prev();
217 : 28 : }
218 : :
219 : : /** Position the cursor on the lowest entry with key >= @a key.
220 : : *
221 : : * @return true if the exact key was found in the table, false
222 : : * otherwise.
223 : : */
224 : : bool find_entry_ge(const string &key);
225 : :
226 : : /** Set the cursor to be off the end of the table.
227 : : */
228 : 77 : void to_end() { is_after_end = true; }
229 : :
230 : : /** Determine whether cursor is off the end of table.
231 : : *
232 : : * @return true if the cursor has been moved off the end of the
233 : : * table, past the last entry in it, and false otherwise.
234 : : */
235 : 7547 : bool after_end() const { return is_after_end; }
236 : :
237 : : /** Delete the current key/tag pair, leaving the cursor on the next
238 : : * entry.
239 : : *
240 : : * @return false if the cursor ends up unpositioned.
241 : : */
242 : : bool del();
243 : :
244 : : /// Return a pointer to the FlintTable we're a cursor for.
245 : 24 : FlintTable * get_table() const { return B; }
246 : : };
247 : :
248 : : #endif /* OM_HGUARD_FLINT_CURSOR_H */
|
