backends/flint/flint_cursor.cc

Go to the documentation of this file.
00001 /* flint_cursor.cc: Btree cursor implementation
00002  *
00003  * Copyright 1999,2000,2001 BrightStation PLC
00004  * Copyright 2002,2003,2004,2005,2006,2007 Olly Betts
00005  *
00006  * This program is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU General Public License as
00008  * published by the Free Software Foundation; either version 2 of the
00009  * License, or (at your option) any later version.
00010  *
00011  * This program is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014  * GNU General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU General Public License
00017  * along with this program; if not, write to the Free Software
00018  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
00019  * USA
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     // Use the value of level stored in the cursor rather than the
00073     // Btree, since the Btree might have been deleted already.
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         // We've read the last key and tag, and we're now not positioned.
00089         // Simple fix - seek to the current key, and then it's as if we
00090         // read the key but not the tag.
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(&current_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(&current_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         // Can't find key - too long to possibly be present, so find the
00167         // truncated form but ignore "found".
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(&current_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         // Can't find key - too long to possibly be present, so find the
00213         // truncated form but ignore "found".
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(&current_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, &current_tag, keep_compressed)) {
00257             tag_status = COMPRESSED;
00258         } else {
00259             tag_status = UNCOMPRESSED;
00260         }
00261 
00262         // We need to call B->next(...) after B->read_tag(...) so that the
00263         // cursor ends up on the next key.
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     // If we're iterating an older revision of the tree, then the deletion
00279     // happens in a new (uncommitted) revision and the cursor still sees
00280     // the deleted key.  But if we're iterating the new uncommitted revision
00281     // then the deleted key is no longer visible.  We need to handle both
00282     // cases - either find_entry_ge() finds the deleted key or not.
00283     if (!find_entry_ge(current_key)) return is_positioned;
00284     return next();
00285 }

Documentation for Xapian (version 1.0.10).
Generated on 24 Dec 2008 by Doxygen 1.5.2.