LCOV - code coverage report
Current view: top level - backends/flint - flint_cursor.h (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core r Lines: 8 8 100.0 %
Date: 2011-08-21 Functions: 5 5 100.0 %
Branches: 2 2 100.0 %

           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 */

Generated by: LCOV version 1.8