LCOV - code coverage report
Current view: top level - backends/glass - glass_cursor.h (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 7028d852e609 Lines: 54 59 91.5 %
Date: 2019-02-17 14:59:59 Functions: 16 17 94.1 %
Branches: 20 26 76.9 %

           Branch data     Line data    Source code
       1                 :            : /** @file glass_cursor.h
       2                 :            :  * @brief Interface to Btree cursors
       3                 :            :  */
       4                 :            : /* Copyright 1999,2000,2001 BrightStation PLC
       5                 :            :  * Copyright 2002,2003,2004,2006,2007,2008,2009,2010,2012,2013,2014,2016 Olly Betts
       6                 :            :  *
       7                 :            :  * This program is free software; you can redistribute it and/or
       8                 :            :  * modify it under the terms of the GNU General Public License as
       9                 :            :  * published by the Free Software Foundation; either version 2 of the
      10                 :            :  * License, or (at your option) any later version.
      11                 :            :  *
      12                 :            :  * This program is distributed in the hope that it will be useful,
      13                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            :  * GNU General Public License for more details.
      16                 :            :  *
      17                 :            :  * You should have received a copy of the GNU General Public License
      18                 :            :  * along with this program; if not, write to the Free Software
      19                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301
      20                 :            :  * USA
      21                 :            :  */
      22                 :            : 
      23                 :            : #ifndef XAPIAN_INCLUDED_GLASS_CURSOR_H
      24                 :            : #define XAPIAN_INCLUDED_GLASS_CURSOR_H
      25                 :            : 
      26                 :            : #include "glass_defs.h"
      27                 :            : 
      28                 :            : #include "alignment_cast.h"
      29                 :            : #include "omassert.h"
      30                 :            : 
      31                 :            : #include <algorithm>
      32                 :            : #include <cstring>
      33                 :            : #include <string>
      34                 :            : using std::string;
      35                 :            : 
      36                 :            : #define BLK_UNUSED uint4(-1)
      37                 :            : 
      38                 :            : namespace Glass {
      39                 :            : 
      40                 :            : class Cursor {
      41                 :            :     private:
      42                 :            :         // Prevent copying
      43                 :            :         Cursor(const Cursor &);
      44                 :            :         Cursor & operator=(const Cursor &);
      45                 :            : 
      46                 :            :         /// Pointer to reference counted data.
      47                 :            :         char * data;
      48                 :            : 
      49                 :            :     public:
      50                 :            :         /// Constructor.
      51                 :    2008405 :         Cursor() : data(0), c(-1), rewrite(false) { }
      52                 :            : 
      53                 :    4016450 :         ~Cursor() { destroy(); }
      54                 :            : 
      55                 :    5588688 :         uint8_t * init(unsigned block_size) {
      56 [ +  + ][ +  + ]:    5588688 :             if (data && refs() > 1) {
                 [ +  + ]
      57                 :     476769 :                 --refs();
      58                 :     476769 :                 data = NULL;
      59                 :            :             }
      60         [ +  + ]:    5588688 :             if (!data)
      61                 :     530933 :                 data = new char[block_size + 8];
      62                 :    5588688 :             refs() = 1;
      63                 :    5588688 :             set_n(BLK_UNUSED);
      64                 :    5588688 :             rewrite = false;
      65                 :    5588688 :             c = -1;
      66                 :    5588688 :             return reinterpret_cast<uint8_t*>(data + 8);
      67                 :            :         }
      68                 :            : 
      69                 :    1831679 :         const uint8_t * clone(const Cursor & o) {
      70         [ +  - ]:    1831679 :             if (data != o.data) {
      71                 :    1831679 :                 destroy();
      72                 :    1831679 :                 data = o.data;
      73                 :    1831679 :                 ++refs();
      74                 :            :             }
      75                 :    1831679 :             return reinterpret_cast<uint8_t*>(data + 8);
      76                 :            :         }
      77                 :            : 
      78                 :          0 :         void swap(Cursor & o) {
      79                 :          0 :             std::swap(data, o.data);
      80                 :          0 :             std::swap(c, o.c);
      81                 :          0 :             std::swap(rewrite, o.rewrite);
      82                 :          0 :         }
      83                 :            : 
      84                 :    3893530 :         void destroy() {
      85         [ +  + ]:    3893530 :             if (data) {
      86         [ +  + ]:    1885837 :                 if (--refs() == 0)
      87         [ +  - ]:     531022 :                     delete [] data;
      88                 :    1885837 :                 data = NULL;
      89                 :    1885837 :                 rewrite = false;
      90                 :            :             }
      91                 :    3893530 :         }
      92                 :            : 
      93                 :   19415432 :         uint4 & refs() const {
      94                 :            :             Assert(data);
      95                 :   19415432 :             return *alignment_cast<uint4*>(data);
      96                 :            :         }
      97                 :            : 
      98                 :            :         /** Get the block number.
      99                 :            :          *
     100                 :            :          *  Returns BLK_UNUSED if no block is currently loaded.
     101                 :            :          */
     102                 :   24745230 :         uint4 get_n() const {
     103                 :            :             Assert(data);
     104                 :   24745230 :             return *alignment_cast<uint4*>(data + 4);
     105                 :            :         }
     106                 :            : 
     107                 :   10867159 :         void set_n(uint4 n) {
     108                 :            :             Assert(data);
     109                 :            :             // Assert(refs() == 1);
     110                 :   10867159 :             *alignment_cast<uint4*>(data + 4) = n;
     111                 :   10867159 :         }
     112                 :            : 
     113                 :            :         /** Get pointer to block.
     114                 :            :          *
     115                 :            :          * Returns NULL if no block is currently loaded.
     116                 :            :          */
     117                 :   64984614 :         const uint8_t * get_p() const {
     118         [ -  + ]:   64984614 :             if (rare(!data)) return NULL;
     119                 :   64984614 :             return reinterpret_cast<uint8_t*>(data + 8);
     120                 :            :         }
     121                 :            : 
     122                 :    4097745 :         uint8_t * get_modifiable_p(unsigned block_size) {
     123         [ -  + ]:    4097745 :             if (rare(!data)) return NULL;
     124         [ +  + ]:    4097745 :             if (refs() > 1) {
     125                 :         95 :                 char * new_data = new char[block_size + 8];
     126                 :         95 :                 std::memcpy(new_data, data, block_size + 8);
     127                 :         95 :                 --refs();
     128                 :         95 :                 data = new_data;
     129                 :         95 :                 refs() = 1;
     130                 :            :             }
     131                 :    4097745 :             return reinterpret_cast<uint8_t*>(data + 8);
     132                 :            :         }
     133                 :            : 
     134                 :            :         /// offset in the block's directory
     135                 :            :         int c;
     136                 :            : 
     137                 :            :         /// true if the block is not the same as on disk, and so needs rewriting
     138                 :            :         bool rewrite;
     139                 :            : };
     140                 :            : 
     141                 :            : }
     142                 :            : 
     143                 :            : class GlassTable;
     144                 :            : 
     145                 :            : /** A cursor pointing to a position in a Btree table, for reading several
     146                 :            :  *  entries in order, or finding approximate matches.
     147                 :            :  */
     148                 :            : class GlassCursor {
     149                 :            :     private:
     150                 :            :         /// Copying not allowed
     151                 :            :         GlassCursor(const GlassCursor &);
     152                 :            : 
     153                 :            :         /// Assignment not allowed
     154                 :            :         GlassCursor & operator=(const GlassCursor &);
     155                 :            : 
     156                 :            :         /** Rebuild the cursor.
     157                 :            :          *
     158                 :            :          *  Called when the table has changed.
     159                 :            :          */
     160                 :            :         void rebuild();
     161                 :            : 
     162                 :            :     protected:
     163                 :            :         /** Whether the cursor is positioned at a valid entry.
     164                 :            :          *
     165                 :            :          *  false initially, and after the cursor has dropped
     166                 :            :          *  off either end of the list of items
     167                 :            :          */
     168                 :            :         bool is_positioned;
     169                 :            : 
     170                 :            :         /** Whether the cursor is off the end of the table.
     171                 :            :          */
     172                 :            :         bool is_after_end;
     173                 :            : 
     174                 :            :     private:
     175                 :            :         /** Status of the current_tag member. */
     176                 :            :         enum { UNREAD, UNREAD_ON_LAST_CHUNK, UNCOMPRESSED, COMPRESSED } tag_status;
     177                 :            : 
     178                 :            :     protected:
     179                 :            :         /// The Btree table
     180                 :            :         const GlassTable * B;
     181                 :            : 
     182                 :            :     private:
     183                 :            :         /// Pointer to an array of Cursors
     184                 :            :         Glass::Cursor * C;
     185                 :            : 
     186                 :            :         unsigned long version;
     187                 :            : 
     188                 :            :         /** The value of level in the Btree structure. */
     189                 :            :         int level;
     190                 :            : 
     191                 :            :         /** Get the key.
     192                 :            :          *
     193                 :            :          *  The key of the item at the cursor is copied into key.
     194                 :            :          *
     195                 :            :          *  The cursor must be positioned before calling this method.
     196                 :            :          *
     197                 :            :          *  e.g.
     198                 :            :          *
     199                 :            :          *    GlassCursor BC(&btree);
     200                 :            :          *    string key;
     201                 :            :          *
     202                 :            :          *    // Now do something to each key in the Btree
     203                 :            :          *    BC.rewind();
     204                 :            :          *    while (BC.next()) {
     205                 :            :          *        BC.get_key(&key);
     206                 :            :          *        do_something_to(key);
     207                 :            :          *    }
     208                 :            :          */
     209                 :            :         void get_key(string * key) const;
     210                 :            : 
     211                 :            :     public:
     212                 :            :         /** Create a cursor attached to a Btree.
     213                 :            :          *
     214                 :            :          *  Creates a cursor, which can be used to remember a position inside
     215                 :            :          *  the B-tree. The position is simply the item (key and tag) to which
     216                 :            :          *  the cursor points. A cursor is either positioned or unpositioned,
     217                 :            :          *  and is initially unpositioned.
     218                 :            :          *
     219                 :            :          *  NB: You must not try to use a GlassCursor after the Btree it is
     220                 :            :          *  attached to is destroyed.  It's safe to destroy the GlassCursor
     221                 :            :          *  after the Btree though, you just may not use the GlassCursor.
     222                 :            :          */
     223                 :            :         explicit GlassCursor(const GlassTable *B,
     224                 :            :                              const Glass::Cursor * C_ = NULL);
     225                 :            : 
     226                 :            :         /** Clone a cursor.
     227                 :            :          *
     228                 :            :          *  Creates a new cursor, primed with the blocks in the first cursor.
     229                 :            :          *  The new cursor is initially *unpositioned*.
     230                 :            :          */
     231                 :      99197 :         GlassCursor * clone() const {
     232         [ +  - ]:      99197 :             return new GlassCursor(B, C);
     233                 :            :         }
     234                 :            : 
     235                 :            :         /** Destroy the GlassCursor */
     236                 :            :         ~GlassCursor();
     237                 :            : 
     238                 :            :         /** Current key pointed to by cursor.
     239                 :            :          */
     240                 :            :         string current_key;
     241                 :            : 
     242                 :            :         /** Current tag pointed to by cursor.  You must call read_tag to
     243                 :            :          *  make this value available.
     244                 :            :          */
     245                 :            :         string current_tag;
     246                 :            : 
     247                 :            :         /** Position cursor on the dummy empty key.
     248                 :            :          *
     249                 :            :          *  Calling next() after this moves the cursor to the first entry.
     250                 :            :          */
     251                 :       1577 :         void rewind() {
     252         [ +  - ]:       1577 :             (void)find_entry_ge(string());
     253                 :       1577 :         }
     254                 :            : 
     255                 :            :         /** Read the tag from the table and store it in current_tag.
     256                 :            :          *
     257                 :            :          *  Some cursor users don't need the tag, so for efficiency we
     258                 :            :          *  only read it when asked to.
     259                 :            :          *
     260                 :            :          *  @param keep_compressed  Don't uncompress the tag - e.g. useful
     261                 :            :          *                          if it's just being opaquely copied
     262                 :            :          *                          (default: false).
     263                 :            :          *
     264                 :            :          *  @return     true if current_tag holds compressed data (always
     265                 :            :          *              false if keep_compressed was false).
     266                 :            :          */
     267                 :            :         bool read_tag(bool keep_compressed = false);
     268                 :            : 
     269                 :            :         /** Advance to the next key.
     270                 :            :          *
     271                 :            :          *  If cursor is unpositioned, the result is simply false.
     272                 :            :          *
     273                 :            :          *  If cursor is positioned, and points to the very last item in the
     274                 :            :          *  Btree the cursor is made unpositioned, and the result is false.
     275                 :            :          *  Otherwise the cursor is moved to the next item in the B-tree,
     276                 :            :          *  and the result is true.
     277                 :            :          *
     278                 :            :          *  Effectively, GlassCursor::next() loses the position of BC when it
     279                 :            :          *  drops off the end of the list of items. If this is awkward, one can
     280                 :            :          *  always arrange for a key to be present which has a rightmost
     281                 :            :          *  position in a set of keys,
     282                 :            :          */
     283                 :            :         bool next();
     284                 :            : 
     285                 :            :         /** Position the cursor on the highest entry with key <= @a key.
     286                 :            :          *
     287                 :            :          *  If the exact key is found in the table, the cursor will be
     288                 :            :          *  set to point to it, and the method will return true.
     289                 :            :          *
     290                 :            :          *  If the key is not found, the cursor will be set to point to
     291                 :            :          *  the key preceding that asked for, and the method will return
     292                 :            :          *  false.  If there is no key preceding that asked for, the cursor
     293                 :            :          *  will point to a null key.
     294                 :            :          *
     295                 :            :          *  Note:  Since the B-tree always contains a null key, which precedes
     296                 :            :          *  everything, a call to GlassCursor::find_entry always results in a
     297                 :            :          *  valid key being pointed to by the cursor.
     298                 :            :          *
     299                 :            :          *  Note: Calling this method with a null key, then calling next()
     300                 :            :          *  will leave the cursor pointing to the first key.
     301                 :            :          *
     302                 :            :          *  @param key    The key to look for in the table.
     303                 :            :          *
     304                 :            :          *  @return true if the exact key was found in the table, false
     305                 :            :          *          otherwise.
     306                 :            :          */
     307                 :            :         bool find_entry(const string &key);
     308                 :            : 
     309                 :            :         /** Position the cursor exactly on a key.
     310                 :            :          *
     311                 :            :          *  If key is found, the cursor will be set to it, the tag read.  If
     312                 :            :          *  it is not found, the cursor is left unpositioned.
     313                 :            :          *
     314                 :            :          *  @param key  The key to search for.
     315                 :            :          *  @return true if the key was found.
     316                 :            :          */
     317                 :            :         bool find_exact(const string &key);
     318                 :            : 
     319                 :            :         /// Position the cursor on the highest entry with key < @a key.
     320                 :            :         void find_entry_lt(const string &key);
     321                 :            : 
     322                 :            :         /** Position the cursor on the lowest entry with key >= @a key.
     323                 :            :          *
     324                 :            :          *  @return true if the exact key was found in the table, false
     325                 :            :          *          otherwise.
     326                 :            :          */
     327                 :            :         bool find_entry_ge(const string &key);
     328                 :            : 
     329                 :            :         /** Set the cursor to be off the end of the table.
     330                 :            :          */
     331                 :      10205 :         void to_end() { is_after_end = true; }
     332                 :            : 
     333                 :            :         /** Determine whether cursor is off the end of table.
     334                 :            :          *
     335                 :            :          *  @return true if the cursor has been moved off the end of the
     336                 :            :          *          table, past the last entry in it, and false otherwise.
     337                 :            :          */
     338                 :     344472 :         bool after_end() const { return is_after_end; }
     339                 :            : 
     340                 :            :         /// Return a pointer to the GlassTable we're a cursor for.
     341                 :            :         const GlassTable * get_table() const { return B; }
     342                 :            : };
     343                 :            : 
     344                 :         20 : class MutableGlassCursor : public GlassCursor {
     345                 :            :   public:
     346                 :            :     /** Create a mutable cursor attached to a Btree.
     347                 :            :      *
     348                 :            :      *  A mutable cursor allows the items to be deleted.
     349                 :            :      *
     350                 :            :      *  Creates a cursor, which can be used to remember a position inside
     351                 :            :      *  the B-tree. The position is simply the item (key and tag) to which
     352                 :            :      *  the cursor points. A cursor is either positioned or unpositioned,
     353                 :            :      *  and is initially unpositioned.
     354                 :            :      *
     355                 :            :      *  NB: You must not try to use a MutableGlassCursor after the Btree it is
     356                 :            :      *  attached to is destroyed.  It's safe to destroy the MutableGlassCursor
     357                 :            :      *  after the Btree though, you just may not use the MutableGlassCursor.
     358                 :            :      */
     359                 :         20 :     explicit MutableGlassCursor(GlassTable *B_) : GlassCursor(B_) { }
     360                 :            : 
     361                 :            :     /** Delete the current key/tag pair, leaving the cursor on the next
     362                 :            :      *  entry.
     363                 :            :      *
     364                 :            :      *  @return false if the cursor ends up unpositioned.
     365                 :            :      */
     366                 :            :     bool del();
     367                 :            : };
     368                 :            : 
     369                 :            : #ifdef DISABLE_GPL_LIBXAPIAN
     370                 :            : # error GPL source we cannot relicense included in libxapian
     371                 :            : #endif
     372                 :            : 
     373                 :            : #endif /* XAPIAN_INCLUDED_GLASS_CURSOR_H */

Generated by: LCOV version 1.11