backends/quartz/bcursor.cc

Go to the documentation of this file.
00001 /* bcursor.cc: Btree cursor implementation
00002  *
00003  * Copyright 1999,2000,2001 BrightStation PLC
00004  * Copyright 2002,2003,2004,2005,2006 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 "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     // Use the value of level stored in the cursor rather than the
00069     // Btree, since the Btree might have been deleted already.
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         // We've read the last key and tag, and we're now not positioned.
00085         // Simple fix - seek to the current key, and then it's as if we
00086         // read the key but not the tag.
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(&current_key);
00113     // FIXME: check for errors
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(&current_key);
00145     // FIXME: check for errors
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         // Can't find key - too long to possibly be present, so find the
00165         // truncated form but ignore "found".
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(&current_key);
00190     (void)err; // FIXME: check for errors
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, &current_tag);
00219 
00220     // We need to call B->next(...) after B->read_tag(...) so that the
00221     // cursor ends up on the next key.
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     // FIXME: this isn't the most efficient approach, but I struggled to
00235     // make the obvious approaches work.
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 }

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