LCOV - code coverage report
Current view: top level - backends - prefix_compressed_strings.h (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 7028d852e609 Lines: 49 89 55.1 %
Date: 2019-02-17 14:59:59 Functions: 10 13 76.9 %
Branches: 18 56 32.1 %

           Branch data     Line data    Source code
       1                 :            : /** @file prefix_compressed_strings.h
       2                 :            :  * @brief Handle encoding and decoding prefix-compressed lists of strings
       3                 :            :  */
       4                 :            : /* Copyright (C) 2004,2005,2006,2007,2008,2009,2010,2018 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 XAPIAN_INCLUDED_PREFIX_COMPRESSED_STRINGS_H
      23                 :            : #define XAPIAN_INCLUDED_PREFIX_COMPRESSED_STRINGS_H
      24                 :            : 
      25                 :            : #include <xapian/error.h>
      26                 :            : 
      27                 :            : #include <algorithm>
      28                 :            : #include <string>
      29                 :            : 
      30                 :            : #include "honey/honey_spelling.h"
      31                 :            : #include "stringutils.h"
      32                 :            : 
      33                 :            : // We XOR the length values with this so that they are more likely to coincide
      34                 :            : // with lower case ASCII letters, which are likely to be common.  This means
      35                 :            : // that zlib should do a better job of compressing tag values - in tests, this
      36                 :            : // gave 5% better compression.
      37                 :            : #define MAGIC_XOR_VALUE 96
      38                 :            : 
      39                 :         98 : class PrefixCompressedStringItor {
      40                 :            :     const unsigned char * p;
      41                 :            :     size_t left;
      42                 :            :     std::string current;
      43                 :            : 
      44                 :            :     /** Number of constant characters on the end of the value.
      45                 :            :      *
      46                 :            :      *  Valid values once iterating are 0, 1, 2.  Before iteration, can be
      47                 :            :      *  0 (no head or tail), 2 (two tails), -1 (one head, one tail -> 1 once
      48                 :            :      *  iterating) or -2 (two heads, no tail -> 0 once iterating).
      49                 :            :      */
      50                 :            :     int tail = 0;
      51                 :            : 
      52                 :          7 :     PrefixCompressedStringItor(PrefixCompressedStringItor& o)
      53                 :          7 :         : p(o.p), left(o.left), current(o.current), tail(o.tail) {}
      54                 :            : 
      55                 :            :   public:
      56                 :            :     /** Construct for glass.
      57                 :            :      *
      58                 :            :      *  @param s  the encoded data.
      59                 :            :      */
      60                 :         42 :     explicit PrefixCompressedStringItor(const std::string& s)
      61                 :         42 :         : p(reinterpret_cast<const unsigned char *>(s.data())),
      62                 :         42 :           left(s.size()) {
      63         [ +  - ]:         42 :         if (left) {
      64         [ +  - ]:         42 :             operator++();
      65                 :            :         } else {
      66                 :          0 :             p = NULL;
      67                 :            :         }
      68                 :         42 :     }
      69                 :            : 
      70                 :            :     /** Construct for honey.
      71                 :            :      *
      72                 :            :      *  @param s    the encoded data.
      73                 :            :      *  @param key  the key
      74                 :            :      */
      75                 :          0 :     PrefixCompressedStringItor(const std::string& s,
      76                 :            :                                const std::string& key)
      77                 :          0 :         : p(reinterpret_cast<const unsigned char *>(s.data())),
      78                 :          0 :           left(s.size()) {
      79                 :            :         Assert(!key.empty());
      80                 :          0 :         unsigned char first_ch = key[0];
      81                 :            :         AssertRel(first_ch, <, Honey::KEY_PREFIX_WORD);
      82   [ #  #  #  # ]:          0 :         switch (first_ch) {
      83                 :            :             case Honey::KEY_PREFIX_BOOKEND:
      84                 :          0 :                 tail = -1;
      85                 :          0 :                 break;
      86                 :            :             case Honey::KEY_PREFIX_HEAD:
      87                 :          0 :                 tail = -2;
      88                 :          0 :                 break;
      89                 :            :             case Honey::KEY_PREFIX_TAIL:
      90                 :          0 :                 tail = 2;
      91                 :          0 :                 break;
      92                 :            :         }
      93         [ #  # ]:          0 :         if (tail != 0)
      94         [ #  # ]:          0 :             current.assign(key, 1, 2);
      95         [ #  # ]:          0 :         if (left) {
      96         [ #  # ]:          0 :             operator++();
      97                 :            :         } else {
      98                 :          0 :             p = NULL;
      99                 :            :         }
     100                 :          0 :     }
     101                 :            : 
     102                 :         49 :     const std::string & operator*() const {
     103                 :         49 :         return current;
     104                 :            :     }
     105                 :            : 
     106                 :          7 :     PrefixCompressedStringItor operator++(int) {
     107                 :          7 :         PrefixCompressedStringItor old(*this);
     108         [ +  - ]:          7 :         operator++();
     109                 :          7 :         return old;
     110                 :            :     }
     111                 :            : 
     112                 :         89 :     PrefixCompressedStringItor & operator++() {
     113         [ +  + ]:         89 :         if (left == 0) {
     114                 :         42 :             p = NULL;
     115                 :            :         } else {
     116                 :         47 :             size_t keep = 0;
     117         [ -  + ]:         47 :             if (rare(tail < 0)) {
     118                 :          0 :                 tail += 2;
     119                 :          0 :                 keep = current.size() - tail;
     120         [ +  + ]:         47 :             } else if (usual(!current.empty())) {
     121                 :          5 :                 keep = *p++ ^ MAGIC_XOR_VALUE;
     122                 :          5 :                 --left;
     123                 :            :             }
     124                 :            :             size_t add;
     125 [ +  - ][ -  + ]:         47 :             if (left == 0 || (add = *p ^ MAGIC_XOR_VALUE) >= left)
                 [ -  + ]
     126 [ #  # ][ #  # ]:          0 :                 throw Xapian::DatabaseCorruptError("Bad spelling data (too little left)");
                 [ #  # ]
     127                 :         47 :             current.replace(keep, current.size() - tail - keep,
     128                 :         47 :                             reinterpret_cast<const char *>(p + 1), add);
     129                 :         47 :             p += add + 1;
     130                 :         47 :             left -= add + 1;
     131                 :            :         }
     132                 :         89 :         return *this;
     133                 :            :     }
     134                 :            : 
     135                 :        139 :     bool at_end() const {
     136                 :        139 :         return p == NULL;
     137                 :            :     }
     138                 :            : };
     139                 :            : 
     140                 :        730 : class PrefixCompressedStringWriter {
     141                 :            :     std::string current;
     142                 :            :     std::string & out;
     143                 :            : 
     144                 :            :     int tail = 0;
     145                 :            : 
     146                 :            :   public:
     147                 :            :     /** Construct for glass.
     148                 :            :      *
     149                 :            :      *  @param out_  where to write data to.
     150                 :            :      */
     151                 :        730 :     explicit PrefixCompressedStringWriter(std::string& out_) : out(out_) { }
     152                 :            : 
     153                 :            :     /** Construct for honey.
     154                 :            :      *
     155                 :            :      *  @param out_  where to write data to.
     156                 :            :      *  @param key   the key.
     157                 :            :      */
     158                 :          0 :     PrefixCompressedStringWriter(std::string& out_,
     159                 :            :                                  const std::string& key)
     160                 :          0 :         : out(out_) {
     161                 :            :         Assert(!key.empty());
     162                 :          0 :         unsigned char first_ch = key[0];
     163                 :            :         AssertRel(first_ch, <, Honey::KEY_PREFIX_WORD);
     164   [ #  #  #  # ]:          0 :         switch (first_ch) {
     165                 :            :             case Honey::KEY_PREFIX_BOOKEND:
     166                 :          0 :                 tail = -1;
     167                 :          0 :                 break;
     168                 :            :             case Honey::KEY_PREFIX_HEAD:
     169                 :          0 :                 tail = -2;
     170                 :          0 :                 break;
     171                 :            :             case Honey::KEY_PREFIX_TAIL:
     172                 :          0 :                 tail = 2;
     173                 :          0 :                 break;
     174                 :            :         }
     175         [ #  # ]:          0 :         if (tail != 0)
     176         [ #  # ]:          0 :             current.assign(key, 1, 2);
     177                 :          0 :     }
     178                 :            : 
     179                 :        363 :     void append(const std::string & word) {
     180                 :            :         // If this isn't the first entry, see how much of the previous one
     181                 :            :         // we can reuse.
     182         [ -  + ]:        363 :         if (rare(tail < 0)) {
     183                 :            :             // First entry for BOOKEND or HEAD (tail is -1 or -2).
     184                 :            :             AssertRel(tail, >=, -2);
     185                 :            :             AssertEq(current[0], word[0]);
     186                 :          0 :             if (tail == -2) {
     187                 :            :                 AssertEq(current[1], word[1]);
     188                 :            :             } else {
     189                 :            :                 AssertEq(current.back(), word.back());
     190                 :            :             }
     191                 :          0 :             out += char((word.size() - 2) ^ MAGIC_XOR_VALUE);
     192                 :          0 :             out.append(word, -tail, word.size() - 2);
     193                 :          0 :             tail += 2;
     194         [ +  + ]:        363 :         } else if (usual(!current.empty())) {
     195                 :            :             // Incremental change.
     196                 :         34 :             if (tail)
     197                 :            :                 AssertEq(current[current.size() - 1], word[word.size() - 1]);
     198                 :         34 :             if (tail > 1)
     199                 :            :                 AssertEq(current[current.size() - 2], word[word.size() - 2]);
     200         [ +  - ]:         34 :             size_t i = common_prefix_length(current, word);
     201                 :            :             // Don't allow the reused prefix to overlap with tail
     202                 :         34 :             i = std::min(i, word.size() - tail);
     203         [ +  - ]:         34 :             out += char(i ^ MAGIC_XOR_VALUE);
     204                 :         34 :             size_t add = word.size() - i - tail;
     205         [ +  - ]:         34 :             out += char(add ^ MAGIC_XOR_VALUE);
     206         [ +  - ]:         34 :             out.append(word.data() + i, add);
     207                 :            :         } else {
     208                 :            :             // First entry for MIDDLE or TAIL (tail is 0 or 2).
     209                 :        329 :             if (tail) {
     210                 :            :                 AssertEq(current[current.size() - 1], word[word.size() - 1]);
     211                 :            :                 AssertEq(current[current.size() - 2], word[word.size() - 2]);
     212                 :            :             }
     213                 :        329 :             out += char((word.size() - tail) ^ MAGIC_XOR_VALUE);
     214                 :        329 :             out.append(word, 0, word.size() - tail);
     215                 :            :         }
     216                 :        363 :         current = word;
     217                 :        363 :     }
     218                 :            : };
     219                 :            : 
     220                 :            : struct PrefixCompressedStringItorGt {
     221                 :            :     /// Return true if and only if a's string is strictly greater than b's.
     222                 :          0 :     bool operator()(const PrefixCompressedStringItor *a,
     223                 :            :                     const PrefixCompressedStringItor *b) const {
     224                 :          0 :         return (**a > **b);
     225                 :            :     }
     226                 :            : };
     227                 :            : 
     228                 :            : #endif // XAPIAN_INCLUDED_PREFIX_COMPRESSED_STRINGS_H

Generated by: LCOV version 1.11