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 "bcursor.h"
00027 #include "btree.h"
00028 #include "btree_util.h"
00029 #include "omassert.h"
00030 #include "omdebug.h"
00031
00032 #ifdef XAPIAN_DEBUG_VERBOSE
00033 static string
00034 hex_encode(const string & input)
00035 {
00036 const char * table = "0123456789abcdef";
00037 string result;
00038 for (string::const_iterator i = input.begin(); i != input.end(); ++i) {
00039 unsigned char val = *i;
00040 result += "\\x";
00041 result += table[val/16];
00042 result += table[val%16];
00043 }
00044
00045 return result;
00046 }
00047 #endif
00048
00049 Bcursor::Bcursor(Btree *B_)
00050 : is_positioned(false),
00051 is_after_end(false),
00052 have_read_tag(false),
00053 B(B_),
00054 level(B_->level)
00055 {
00056 C = new Cursor[level + 1];
00057
00058 for (int j = 0; j < level; j++) {
00059 C[j].n = BLK_UNUSED;
00060 C[j].p = new byte[B->block_size];
00061 }
00062 C[level].n = B->C[level].n;
00063 C[level].p = B->C[level].p;
00064 }
00065
00066 Bcursor::~Bcursor()
00067 {
00068
00069
00070 for (int j = 0; j < level; j++) {
00071 delete [] C[j].p;
00072 }
00073 delete [] C;
00074 }
00075
00076 bool
00077 Bcursor::prev()
00078 {
00079 DEBUGCALL(DB, bool, "Bcursor::prev", "");
00080 Assert(B->level <= level);
00081 Assert(!is_after_end);
00082
00083 if (!is_positioned) {
00084
00085
00086
00087 (void)find_entry(current_key);
00088 have_read_tag = false;
00089 }
00090
00091 if (have_read_tag) {
00092 while (true) {
00093 if (! B->prev(C, 0)) {
00094 is_positioned = false;
00095 return false;
00096 }
00097 if (Item(C[0].p, C[0].c).component_of() == 1) {
00098 break;
00099 }
00100 }
00101 }
00102
00103 while (true) {
00104 if (! B->prev(C, 0)) {
00105 is_positioned = false;
00106 return false;
00107 }
00108 if (Item(C[0].p, C[0].c).component_of() == 1) {
00109 break;
00110 }
00111 }
00112 get_key(¤t_key);
00113
00114 have_read_tag = false;
00115
00116 DEBUGLINE(DB, "Moved to entry: key=`" << hex_encode(current_key) << "'");
00117 return true;
00118 }
00119
00120 bool
00121 Bcursor::next()
00122 {
00123 DEBUGCALL(DB, bool, "Bcursor::next", "");
00124 Assert(B->level <= level);
00125 Assert(!is_after_end);
00126 if (!have_read_tag) {
00127 while (true) {
00128 if (! B->next(C, 0)) {
00129 is_positioned = false;
00130 break;
00131 }
00132 if (Item(C[0].p, C[0].c).component_of() == 1) {
00133 is_positioned = true;
00134 break;
00135 }
00136 }
00137 }
00138
00139 if (!is_positioned) {
00140 is_after_end = true;
00141 return false;
00142 }
00143
00144 get_key(¤t_key);
00145
00146 have_read_tag = false;
00147
00148 DEBUGLINE(DB, "Moved to entry: key=`" << hex_encode(current_key) << "'");
00149 return true;
00150 }
00151
00152 bool
00153 Bcursor::find_entry(const string &key)
00154 {
00155 DEBUGCALL(DB, bool, "Bcursor::find_entry", key);
00156 Assert(B->level <= level);
00157
00158 is_after_end = false;
00159
00160 bool found;
00161
00162 if (key.size() > BTREE_MAX_KEY_LEN) {
00163 is_positioned = true;
00164
00165
00166 B->form_key(key.substr(0, BTREE_MAX_KEY_LEN));
00167 (void)(B->find(C));
00168 found = false;
00169 } else {
00170 is_positioned = true;
00171 B->form_key(key);
00172 found = B->find(C);
00173 }
00174
00175 if (!found) {
00176 if (C[0].c < DIR_START) {
00177 C[0].c = DIR_START;
00178 if (! B->prev(C, 0)) goto done;
00179 }
00180 while (Item(C[0].p, C[0].c).component_of() != 1) {
00181 if (! B->prev(C, 0)) {
00182 is_positioned = false;
00183 break;
00184 }
00185 }
00186 }
00187 done:
00188
00189 bool err = get_key(¤t_key);
00190 (void)err;
00191 have_read_tag = false;
00192
00193 DEBUGLINE(DB, "Found entry: key=`" << hex_encode(current_key) << "'");
00194
00195 RETURN(found);
00196 }
00197
00198 bool
00199 Bcursor::get_key(string * key) const
00200 {
00201 Assert(B->level <= level);
00202
00203 if (!is_positioned) return false;
00204
00205 (void)Item(C[0].p, C[0].c).key().read(key);
00206 return true;
00207 }
00208
00209 void
00210 Bcursor::read_tag()
00211 {
00212 DEBUGCALL(DB, void, "Bcursor::read_tag", "");
00213 if (have_read_tag) return;
00214
00215 Assert(B->level <= level);
00216 Assert(is_positioned);
00217
00218 B->read_tag(C, ¤t_tag);
00219
00220
00221
00222 is_positioned = B->next(C, 0);
00223
00224 have_read_tag = true;
00225
00226 DEBUGLINE(DB, "tag=`" << hex_encode(current_tag) << "'");
00227 }
00228
00229 void
00230 Bcursor::del()
00231 {
00232 Assert(!is_after_end);
00233
00234
00235
00236 B->del(current_key);
00237 find_entry(current_key);
00238 next();
00239
00240 DEBUGLINE(DB, "Moved to entry: key=`" << hex_encode(current_key) << "'");
00241 }