00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include <config.h>
00023
00024 #include "safeerrno.h"
00025
00026 #include <xapian/error.h>
00027
00028 #include "flint_cursor.h"
00029 #include "flint_table.h"
00030 #include "flint_btreeutil.h"
00031 #include "omassert.h"
00032 #include "omdebug.h"
00033
00034 #ifdef XAPIAN_DEBUG_VERBOSE
00035 static string
00036 hex_encode(const string & input)
00037 {
00038 const char * table = "0123456789abcdef";
00039 string result;
00040 for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
00041 unsigned char val = *i;
00042 result += "\\x";
00043 result += table[val/16];
00044 result += table[val%16];
00045 }
00046
00047 return result;
00048 }
00049 #endif
00050
00051 #define DIR_START 11
00052
00053 FlintCursor::FlintCursor(FlintTable *B_)
00054 : is_positioned(false),
00055 is_after_end(false),
00056 tag_status(UNREAD),
00057 B(B_),
00058 level(B_->level)
00059 {
00060 C = new Cursor_[level + 1];
00061
00062 for (int j = 0; j < level; j++) {
00063 C[j].n = BLK_UNUSED;
00064 C[j].p = new byte[B->block_size];
00065 }
00066 C[level].n = B->C[level].n;
00067 C[level].p = B->C[level].p;
00068 }
00069
00070 FlintCursor::~FlintCursor()
00071 {
00072
00073
00074 for (int j = 0; j < level; j++) {
00075 delete [] C[j].p;
00076 }
00077 delete [] C;
00078 }
00079
00080 bool
00081 FlintCursor::prev()
00082 {
00083 DEBUGCALL(DB, bool, "FlintCursor::prev", "");
00084 Assert(B->level <= level);
00085 Assert(!is_after_end);
00086
00087 if (!is_positioned) {
00088
00089
00090
00091 (void)find_entry(current_key);
00092 tag_status = UNREAD;
00093 }
00094
00095 if (tag_status != UNREAD) {
00096 while (true) {
00097 if (! B->prev(C, 0)) {
00098 is_positioned = false;
00099 return false;
00100 }
00101 if (Item_(C[0].p, C[0].c).component_of() == 1) {
00102 break;
00103 }
00104 }
00105 }
00106
00107 while (true) {
00108 if (! B->prev(C, 0)) {
00109 is_positioned = false;
00110 return false;
00111 }
00112 if (Item_(C[0].p, C[0].c).component_of() == 1) {
00113 break;
00114 }
00115 }
00116 get_key(¤t_key);
00117 tag_status = UNREAD;
00118
00119 DEBUGLINE(DB, "Moved to entry: key=`" << hex_encode(current_key) << "'");
00120 return true;
00121 }
00122
00123 bool
00124 FlintCursor::next()
00125 {
00126 DEBUGCALL(DB, bool, "FlintCursor::next", "");
00127 Assert(B->level <= level);
00128 Assert(!is_after_end);
00129 if (tag_status == UNREAD) {
00130 while (true) {
00131 if (! B->next(C, 0)) {
00132 is_positioned = false;
00133 break;
00134 }
00135 if (Item_(C[0].p, C[0].c).component_of() == 1) {
00136 is_positioned = true;
00137 break;
00138 }
00139 }
00140 }
00141
00142 if (!is_positioned) {
00143 is_after_end = true;
00144 return false;
00145 }
00146
00147 get_key(¤t_key);
00148 tag_status = UNREAD;
00149
00150 DEBUGLINE(DB, "Moved to entry: key=`" << hex_encode(current_key) << "'");
00151 return true;
00152 }
00153
00154 bool
00155 FlintCursor::find_entry(const string &key)
00156 {
00157 DEBUGCALL(DB, bool, "FlintCursor::find_entry", key);
00158 Assert(B->level <= level);
00159
00160 is_after_end = false;
00161
00162 bool found;
00163
00164 is_positioned = true;
00165 if (key.size() > FLINT_BTREE_MAX_KEY_LEN) {
00166
00167
00168 B->form_key(key.substr(0, FLINT_BTREE_MAX_KEY_LEN));
00169 (void)(B->find(C));
00170 found = false;
00171 } else {
00172 B->form_key(key);
00173 found = B->find(C);
00174 }
00175
00176 if (!found) {
00177 if (C[0].c < DIR_START) {
00178 C[0].c = DIR_START;
00179 if (! B->prev(C, 0)) goto done;
00180 }
00181 while (Item_(C[0].p, C[0].c).component_of() != 1) {
00182 if (! B->prev(C, 0)) {
00183 is_positioned = false;
00184 throw Xapian::DatabaseCorruptError("find_entry failed to find any entry at all!");
00185 }
00186 }
00187 }
00188 done:
00189
00190 if (found)
00191 current_key = key;
00192 else
00193 get_key(¤t_key);
00194 tag_status = UNREAD;
00195
00196 DEBUGLINE(DB, "Found entry: key=`" << hex_encode(current_key) << "'");
00197 RETURN(found);
00198 }
00199
00200 bool
00201 FlintCursor::find_entry_ge(const string &key)
00202 {
00203 DEBUGCALL(DB, bool, "FlintCursor::find_entry_ge", key);
00204 Assert(B->level <= level);
00205
00206 is_after_end = false;
00207
00208 bool found;
00209
00210 is_positioned = true;
00211 if (key.size() > FLINT_BTREE_MAX_KEY_LEN) {
00212
00213
00214 B->form_key(key.substr(0, FLINT_BTREE_MAX_KEY_LEN));
00215 (void)(B->find(C));
00216 found = false;
00217 } else {
00218 B->form_key(key);
00219 found = B->find(C);
00220 }
00221
00222 if (found) {
00223 current_key = key;
00224 } else {
00225 if (! B->next(C, 0)) {
00226 is_after_end = true;
00227 is_positioned = false;
00228 RETURN(false);
00229 }
00230 Assert(Item_(C[0].p, C[0].c).component_of() == 1);
00231 get_key(¤t_key);
00232 }
00233 tag_status = UNREAD;
00234
00235 DEBUGLINE(DB, "Found entry: key=`" << hex_encode(current_key) << "'");
00236 RETURN(found);
00237 }
00238
00239 void
00240 FlintCursor::get_key(string * key) const
00241 {
00242 Assert(B->level <= level);
00243 Assert(is_positioned);
00244
00245 (void)Item_(C[0].p, C[0].c).key().read(key);
00246 }
00247
00248 bool
00249 FlintCursor::read_tag(bool keep_compressed)
00250 {
00251 DEBUGCALL(DB, bool, "FlintCursor::read_tag", keep_compressed);
00252 if (tag_status == UNREAD) {
00253 Assert(B->level <= level);
00254 Assert(is_positioned);
00255
00256 if (B->read_tag(C, ¤t_tag, keep_compressed)) {
00257 tag_status = COMPRESSED;
00258 } else {
00259 tag_status = UNCOMPRESSED;
00260 }
00261
00262
00263
00264 is_positioned = B->next(C, 0);
00265
00266 DEBUGLINE(DB, "tag=`" << hex_encode(current_tag) << "'");
00267 }
00268 return (tag_status == COMPRESSED);
00269 }
00270
00271 bool
00272 FlintCursor::del()
00273 {
00274 Assert(!is_after_end);
00275
00276 B->del(current_key);
00277
00278
00279
00280
00281
00282
00283 if (!find_entry_ge(current_key)) return is_positioned;
00284 return next();
00285 }