LCOV - code coverage report
Current view: top level - backends/honey - honey_cursor.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 78 179 43.6 %
Date: 2019-06-30 05:20:33 Functions: 4 5 80.0 %
Branches: 56 253 22.1 %

           Branch data     Line data    Source code
       1                 :            : /** @file honey_cursor.cc
       2                 :            :  * @brief HoneyCursor class
       3                 :            :  */
       4                 :            : /* Copyright (C) 2017,2018 Olly Betts
       5                 :            :  *
       6                 :            :  * This program is free software; you can redistribute it and/or modify
       7                 :            :  * it under the terms of the GNU General Public License as published by
       8                 :            :  * the Free Software Foundation; either version 2 of the License, or
       9                 :            :  * (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 USA
      19                 :            :  */
      20                 :            : 
      21                 :            : #include <config.h>
      22                 :            : 
      23                 :            : //#define DEBUGGING
      24                 :            : 
      25                 :            : #include "honey_cursor.h"
      26                 :            : 
      27                 :            : #include <cerrno>
      28                 :            : #include <string>
      29                 :            : 
      30                 :            : #ifdef DEBUGGING
      31                 :            : # include <iostream>
      32                 :            : #endif
      33                 :            : 
      34                 :            : using namespace std;
      35                 :            : 
      36                 :            : bool
      37                 :   15101000 : HoneyCursor::do_next()
      38                 :            : {
      39         [ -  + ]:   15101000 :     if (is_at_end) {
      40                 :            :         Assert(false);
      41                 :          0 :         return false;
      42                 :            :     }
      43                 :            : 
      44         [ +  + ]:   15101000 :     if (val_size) {
      45                 :            :         // Skip val data we've not looked at.
      46                 :   14995679 :         store.skip(val_size);
      47                 :   14995679 :         val_size = 0;
      48                 :            :     }
      49                 :            : 
      50         [ +  + ]:   15101000 :     if (store.get_pos() >= root) {
      51                 :            :         AssertEq(store.get_pos(), root);
      52                 :         99 :         is_at_end = true;
      53                 :         99 :         return false;
      54                 :            :     }
      55                 :            : 
      56         [ +  - ]:   15100901 :     int ch = store.read();
      57         [ -  + ]:   15100901 :     if (ch == EOF) {
      58                 :            :         // The root check above should mean this can't legitimately happen.
      59 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("EOF reading key");
                 [ #  # ]
      60                 :            :     }
      61                 :            : 
      62                 :   15100901 :     size_t reuse = ch;
      63         [ -  + ]:   15100901 :     if (reuse > last_key.size()) {
      64 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseCorruptError("Reuse > previous key size");
                 [ #  # ]
      65                 :            :     }
      66         [ +  - ]:   15100901 :     ch = store.read();
      67         [ -  + ]:   15100901 :     if (ch == EOF) {
      68                 :            :         throw Xapian::DatabaseError("EOF/error while reading key length",
      69 [ #  # ][ #  # ]:          0 :                                     errno);
      70                 :            :     }
      71                 :   15100901 :     size_t key_size = ch;
      72                 :            :     char buf[256];
      73         [ +  - ]:   15100901 :     store.read(buf, key_size);
      74         [ +  - ]:   15100901 :     current_key.assign(last_key, 0, reuse);
      75         [ +  - ]:   15100901 :     current_key.append(buf, key_size);
      76         [ +  - ]:   15100901 :     last_key = current_key;
      77                 :            : 
      78                 :            : #ifdef DEBUGGING
      79                 :            :     {
      80                 :            :         string esc;
      81                 :            :         description_append(esc, current_key);
      82                 :            :         cerr << "K:" << esc << endl;
      83                 :            :     }
      84                 :            : #endif
      85                 :            : 
      86         [ +  - ]:   15101000 :     return next_from_index();
      87                 :            : }
      88                 :            : 
      89                 :            : bool
      90                 :   15100901 : HoneyCursor::next_from_index()
      91                 :            : {
      92                 :            :     char buf[8];
      93                 :            :     int r;
      94                 :            :     {
      95                 :            :         // FIXME: rework to take advantage of buffering that's happening
      96                 :            :         // anyway?
      97                 :   15100901 :         char * p = buf;
      98         [ +  - ]:   21336699 :         for (int i = 0; i < 8; ++i) {
      99         [ +  - ]:   21336699 :             int ch2 = store.read();
     100         [ -  + ]:   21336699 :             if (ch2 == EOF) {
     101                 :          0 :                 break;
     102                 :            :             }
     103                 :   21336699 :             *p++ = char(ch2);
     104         [ +  + ]:   21336699 :             if (ch2 < 128) break;
     105                 :            :         }
     106                 :   15100901 :         r = p - buf;
     107                 :            :     }
     108                 :   15100901 :     const char* p = buf;
     109                 :   15100901 :     const char* end = p + r;
     110         [ -  + ]:   15100901 :     if (!unpack_uint(&p, end, &val_size)) {
     111 [ #  # ][ #  # ]:          0 :         throw Xapian::DatabaseError("val_size unpack_uint invalid");
                 [ #  # ]
     112                 :            :     }
     113         [ -  + ]:   15100901 :     if (p != end) abort();
     114                 :   15100901 :     current_compressed = val_size & 1;
     115                 :   15100901 :     val_size >>= 1;
     116                 :            : 
     117                 :            :     // FIXME: Always resize to 0?  Not doing so avoids always having to clear
     118                 :            :     // all the data before reading it.
     119         [ -  + ]:   15100901 :     if (true && val_size == 0)
     120         [ #  # ]:          0 :         current_tag.resize(0);
     121                 :            : 
     122                 :   15100901 :     is_at_end = false;
     123                 :   15100901 :     return true;
     124                 :            : }
     125                 :            : 
     126                 :            : bool
     127                 :     105704 : HoneyCursor::read_tag(bool keep_compressed)
     128                 :            : {
     129         [ +  + ]:     105704 :     if (val_size) {
     130         [ +  + ]:     104568 :         if (store.was_forced_closed()) {
     131                 :          1 :             HoneyTable::throw_database_closed();
     132                 :            :         }
     133                 :            : 
     134                 :     104567 :         current_tag.resize(val_size);
     135                 :     104567 :         store.read(&(current_tag[0]), val_size);
     136                 :            : #ifdef DEBUGGING
     137                 :            :         {
     138                 :            :             cerr << "read " << val_size << " bytes of value data ending @"
     139                 :            :                  << store.get_pos() << endl;
     140                 :            :             string esc;
     141                 :            :             description_append(esc, current_tag);
     142                 :            :             cerr << "V:" << esc << endl;
     143                 :            :         }
     144                 :            : #endif
     145                 :     104567 :         val_size = 0;
     146                 :            :     }
     147 [ +  + ][ -  + ]:     105703 :     if (!keep_compressed && current_compressed) {
     148                 :            :         // Need to decompress.
     149         [ #  # ]:          0 :         comp_stream.decompress_start();
     150         [ #  # ]:          0 :         string new_tag;
     151         [ #  # ]:          0 :         if (!comp_stream.decompress_chunk(current_tag.data(),
     152                 :          0 :                                           current_tag.size(),
     153         [ #  # ]:          0 :                                           new_tag)) {
     154                 :            :             // Decompression didn't complete.
     155                 :          0 :             abort();
     156                 :            :         }
     157         [ #  # ]:          0 :         swap(current_tag, new_tag);
     158                 :          0 :         current_compressed = false;
     159                 :            : #ifdef DEBUGGING
     160                 :            :         {
     161                 :            :             cerr << "decompressed to " << current_tag.size()
     162                 :            :                  << "bytes of value data" << endl;
     163                 :            :         }
     164                 :            : #endif
     165                 :            :     }
     166                 :     105703 :     return current_compressed;
     167                 :            : }
     168                 :            : 
     169                 :            : bool
     170                 :      93111 : HoneyCursor::do_find(const string& key, bool greater_than)
     171                 :            : {
     172                 :            :     // FIXME: Actually use this!
     173                 :            :     (void)greater_than;
     174                 :            : 
     175                 :            : #ifdef DEBUGGING
     176                 :            :     {
     177                 :            :         string esc;
     178                 :            :         description_append(esc, key);
     179                 :            :         cerr << "do_find(" << esc << ", " << greater_than << ") @" << store.get_pos() << endl;
     180                 :            :     }
     181                 :            : #endif
     182                 :            : 
     183                 :            :     Assert(!key.empty());
     184                 :            : 
     185                 :      93111 :     bool use_index = true;
     186 [ +  + ][ +  + ]:      93111 :     if (!is_at_end && !last_key.empty() && last_key[0] == key[0]) {
         [ +  + ][ +  + ]
     187                 :      38650 :         int cmp0 = last_key.compare(key);
     188         [ +  + ]:      38650 :         if (cmp0 == 0) {
     189                 :       1138 :             current_key = last_key;
     190                 :       1138 :             return true;
     191                 :            :         }
     192         [ +  + ]:      37512 :         if (cmp0 < 0) {
     193                 :            :             // We're going forwards to a key with the same first character, so
     194                 :            :             // an array index won't help us.
     195                 :      37512 :             use_index = false;
     196                 :            :         }
     197                 :            :     }
     198                 :            : 
     199         [ +  + ]:      91973 :     if (store.was_forced_closed()) {
     200                 :          1 :         HoneyTable::throw_database_closed();
     201                 :            :     }
     202                 :            : 
     203         [ +  + ]:      91972 :     if (use_index) {
     204                 :      85335 :         store.rewind(root);
     205                 :      85335 :         int index_type = store.read();
     206   [ -  +  -  -  :      85335 :         switch (index_type) {
                      - ]
     207                 :            :             case EOF:
     208                 :          0 :                 return false;
     209                 :            :             case 0x00: {
     210                 :      85335 :                 unsigned char first = key[0] - store.read();
     211                 :      85335 :                 unsigned char range = store.read();
     212         [ +  + ]:      85335 :                 if (first > range) {
     213                 :         33 :                     is_at_end = true;
     214                 :         33 :                     return false;
     215                 :            :                 }
     216                 :      85302 :                 store.skip(first * 4); // FIXME: pointer width
     217                 :      85302 :                 off_t jump = store.read_uint4_be();
     218                 :      85302 :                 store.rewind(jump);
     219                 :            :                 // The jump point will be an entirely new key (because it is the first
     220                 :            :                 // key with that initial character), and we drop in as if this was the
     221                 :            :                 // first key so set last_key to be empty.
     222         [ +  - ]:      85302 :                 last_key = string();
     223                 :      85302 :                 break;
     224                 :            :             }
     225                 :            :             case 0x01: {
     226         [ #  # ]:          0 :                 size_t j = store.read_uint4_be();
     227         [ #  # ]:          0 :                 if (j == 0) {
     228                 :          0 :                     is_at_end = true;
     229                 :          0 :                     return false;
     230                 :            :                 }
     231                 :          0 :                 off_t base = store.get_pos();
     232                 :            :                 char kkey[SSTINDEX_BINARY_CHOP_KEY_SIZE];
     233                 :          0 :                 size_t kkey_len = 0;
     234                 :          0 :                 size_t i = 0;
     235         [ #  # ]:          0 :                 while (j - i > 1) {
     236                 :          0 :                     size_t k = i + (j - i) / 2;
     237         [ #  # ]:          0 :                     store.set_pos(base + k * SSTINDEX_BINARY_CHOP_ENTRY_SIZE);
     238         [ #  # ]:          0 :                     store.read(kkey, SSTINDEX_BINARY_CHOP_KEY_SIZE);
     239                 :          0 :                     kkey_len = 4;
     240 [ #  # ][ #  # ]:          0 :                     while (kkey_len > 0 && kkey[kkey_len - 1] == '\0') --kkey_len;
     241         [ #  # ]:          0 :                     int r = key.compare(0, SSTINDEX_BINARY_CHOP_KEY_SIZE, kkey, kkey_len);
     242         [ #  # ]:          0 :                     if (r < 0) {
     243                 :          0 :                         j = k;
     244                 :            :                     } else {
     245                 :          0 :                         i = k;
     246         [ #  # ]:          0 :                         if (r == 0) {
     247                 :          0 :                             break;
     248                 :            :                         }
     249                 :            :                     }
     250                 :            :                 }
     251         [ #  # ]:          0 :                 store.set_pos(base + i * SSTINDEX_BINARY_CHOP_ENTRY_SIZE);
     252         [ #  # ]:          0 :                 store.read(kkey, SSTINDEX_BINARY_CHOP_KEY_SIZE);
     253                 :          0 :                 kkey_len = 4;
     254 [ #  # ][ #  # ]:          0 :                 while (kkey_len > 0 && kkey[kkey_len - 1] == '\0') --kkey_len;
     255         [ #  # ]:          0 :                 off_t jump = store.read_uint4_be();
     256                 :          0 :                 store.rewind(jump);
     257                 :            :                 // The jump point is to the first key with prefix kkey, so will
     258                 :            :                 // work if we set last key to kkey.  Unless we're jumping to the
     259                 :            :                 // start of the table, in which case last_key needs to be empty.
     260 [ #  # ][ #  # ]:          0 :                 last_key.assign(kkey, jump == 0 ? 0 : kkey_len);
     261                 :          0 :                 break;
     262                 :            :             }
     263                 :            :             case 0x02: {
     264                 :            :                 // FIXME: If "close" just seek forwards?  Or consider seeking from
     265                 :            :                 // current index pos?
     266                 :            :                 // off_t pos = store.get_pos();
     267 [ #  # ][ #  # ]:          0 :                 string index_key, prev_index_key;
     268                 :          0 :                 make_unsigned<off_t>::type ptr = 0;
     269                 :          0 :                 int cmp0 = 1;
     270                 :            : #ifdef DEBUGGING
     271                 :            :                 {
     272                 :            :                     cerr << "Using skiplist index\n";
     273                 :            :                 }
     274                 :            : #endif
     275                 :            :                 while (true) {
     276         [ #  # ]:          0 :                     int reuse = store.read();
     277         [ #  # ]:          0 :                     if (reuse == EOF) break;
     278         [ #  # ]:          0 :                     int len = store.read();
     279         [ #  # ]:          0 :                     if (len == EOF) abort(); // FIXME
     280                 :            : #ifdef DEBUGGING
     281                 :            :                     {
     282                 :            :                         cerr << "reuse = " << reuse << " len = " << len << endl;
     283                 :            :                     }
     284                 :            : #endif
     285         [ #  # ]:          0 :                     index_key.resize(reuse + len);
     286 [ #  # ][ #  # ]:          0 :                     store.read(&index_key[reuse], len);
     287                 :            : 
     288                 :            : #ifdef DEBUGGING
     289                 :            :                     {
     290                 :            :                         string desc;
     291                 :            :                         description_append(desc, index_key);
     292                 :            :                         cerr << "Index key: " << desc << endl;
     293                 :            :                     }
     294                 :            : #endif
     295                 :            : 
     296         [ #  # ]:          0 :                     cmp0 = index_key.compare(key);
     297         [ #  # ]:          0 :                     if (cmp0 > 0) {
     298         [ #  # ]:          0 :                         index_key = prev_index_key;
     299                 :          0 :                         break;
     300                 :            :                     }
     301                 :            :                     char buf[8];
     302                 :          0 :                     char* e = buf;
     303                 :            :                     while (true) {
     304         [ #  # ]:          0 :                         int b = store.read();
     305                 :          0 :                         *e++ = b;
     306         [ #  # ]:          0 :                         if ((b & 0x80) == 0) break;
     307                 :            :                     }
     308                 :          0 :                     const char* p = buf;
     309 [ #  # ][ #  # ]:          0 :                     if (!unpack_uint(&p, e, &ptr) || p != e) abort(); // FIXME
                 [ #  # ]
     310                 :            : #ifdef DEBUGGING
     311                 :            :                     {
     312                 :            :                         cerr << " -> " << ptr << endl;
     313                 :            :                     }
     314                 :            : #endif
     315         [ #  # ]:          0 :                     if (cmp0 == 0)
     316                 :          0 :                         break;
     317         [ #  # ]:          0 :                     prev_index_key = index_key;
     318                 :            : #ifdef DEBUGGING
     319                 :            :                     {
     320                 :            :                         string desc;
     321                 :            :                         description_append(desc, prev_index_key);
     322                 :            :                         cerr << "prev_index_key -> " << desc << endl;
     323                 :            :                     }
     324                 :            : #endif
     325                 :          0 :                 }
     326                 :            : #ifdef DEBUGGING
     327                 :            :                 {
     328                 :            :                     string desc;
     329                 :            :                     description_append(desc, index_key);
     330                 :            :                     cerr << " index_key = " << desc << ", cmp0 = " << cmp0 << ", going to " << ptr << endl;
     331                 :            :                 }
     332                 :            : #endif
     333         [ #  # ]:          0 :                 store.set_pos(ptr);
     334                 :            : 
     335         [ #  # ]:          0 :                 if (ptr != 0) {
     336 [ #  # ][ #  # ]:          0 :                     last_key = current_key = index_key;
     337         [ #  # ]:          0 :                     bool res = next_from_index();
     338                 :            :                     (void)res;
     339                 :            :                     Assert(res);
     340         [ #  # ]:          0 :                     if (cmp0 == 0) {
     341                 :            :                         Assert(ptr != 0);
     342                 :          0 :                         return true;
     343                 :            :                     }
     344                 :          0 :                     store.skip(val_size);
     345                 :            :                 } else {
     346 [ #  # ][ #  # ]:          0 :                     last_key = current_key = string();
                 [ #  # ]
     347                 :            :                 }
     348                 :            : 
     349                 :            : #ifdef DEBUGGING
     350                 :            :                 {
     351                 :            :                     string desc;
     352                 :            :                     description_append(desc, current_key);
     353                 :            :                     cerr << "cmp0 was " << cmp0 << ", Dropped to data layer on key: " << desc << endl;
     354                 :            :                 }
     355                 :            : #endif
     356                 :            : 
     357 [ #  # ][ #  # ]:          0 :                 break;
     358                 :            :             }
     359                 :            :             default: {
     360         [ #  # ]:          0 :                 string m = "HoneyCursor: Unknown index type ";
     361 [ #  # ][ #  # ]:          0 :                 m += str(index_type);
     362 [ #  # ][ #  # ]:          0 :                 throw Xapian::DatabaseCorruptError(m);
     363                 :            :             }
     364                 :            :         }
     365                 :      85302 :         is_at_end = false;
     366                 :      85302 :         val_size = 0;
     367                 :            :     }
     368                 :            : 
     369         [ +  + ]:   15086643 :     while (do_next()) {
     370                 :   15086636 :         int cmp = current_key.compare(key);
     371         [ +  + ]:   15086636 :         if (cmp == 0) return true;
     372         [ +  + ]:   15033106 :         if (cmp > 0) break;
     373                 :            :     }
     374                 :      93110 :     return false;
     375                 :            : }
     376                 :            : 
     377                 :            : bool
     378                 :          0 : HoneyCursor::prev()
     379                 :            : {
     380         [ #  # ]:          0 :     if (store.was_forced_closed()) {
     381         [ #  # ]:          0 :         HoneyTable::throw_database_closed();
     382                 :            :     }
     383                 :            : 
     384         [ #  # ]:          0 :     string key;
     385         [ #  # ]:          0 :     if (is_at_end) {
     386                 :            :         // To position on the last key we just do a < search for a key greater
     387                 :            :         // than any possible key - one longer than the longest possible length
     388                 :            :         // and consisting entirely of the highest sorting byte value.
     389         [ #  # ]:          0 :         key.assign(HONEY_MAX_KEY_LENGTH + 1, '\xff');
     390                 :            :     } else {
     391         [ #  # ]:          0 :         if (current_key.empty())
     392                 :          0 :             return false;
     393         [ #  # ]:          0 :         key = current_key;
     394                 :            :     }
     395                 :            : 
     396                 :            :     // FIXME: use index - for an array index we can look at index points for
     397                 :            :     // first characters starting with key[0] and working down; for a binary
     398                 :            :     // chop index we can start at the entry including the current key, or the
     399                 :            :     // one before if this is the first key for that index entry; for a skiplist
     400                 :            :     // index we can find the previous entry at the index level above.
     401         [ #  # ]:          0 :     rewind();
     402                 :            : 
     403                 :            :     off_t pos;
     404         [ #  # ]:          0 :     string k;
     405                 :            :     size_t vs;
     406                 :            :     bool compressed;
     407         [ #  # ]:          0 :     do {
     408                 :          0 :         pos = store.get_pos();
     409         [ #  # ]:          0 :         k = current_key;
     410                 :          0 :         vs = val_size;
     411                 :          0 :         compressed = current_compressed;
     412 [ #  # ][ #  # ]:          0 :     } while (do_next() && current_key < key);
         [ #  # ][ #  # ]
     413                 :            : 
     414                 :            :     // Back up to previous entry.
     415                 :          0 :     is_at_end = false;
     416 [ #  # ][ #  # ]:          0 :     last_key = current_key = k;
     417                 :          0 :     val_size = vs;
     418                 :          0 :     current_compressed = compressed;
     419         [ #  # ]:          0 :     store.set_pos(pos);
     420                 :            : 
     421                 :          0 :     return true;
     422                 :            : }

Generated by: LCOV version 1.11