LCOV - code coverage report
Current view: top level - backends/honey - honey_postlist_encodings.h (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 100 112 89.3 %
Date: 2019-06-30 05:20:33 Functions: 7 7 100.0 %
Branches: 53 68 77.9 %

           Branch data     Line data    Source code
       1                 :            : /** @file honey_postlist_encodings.h
       2                 :            :  * @brief Encoding and decoding functions for honey postlists
       3                 :            :  */
       4                 :            : /* Copyright (C) 2015,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 USA
      19                 :            :  */
      20                 :            : 
      21                 :            : #ifndef XAPIAN_INCLUDED_HONEY_POSTLIST_ENCODINGS_H
      22                 :            : #define XAPIAN_INCLUDED_HONEY_POSTLIST_ENCODINGS_H
      23                 :            : 
      24                 :            : #include "pack.h"
      25                 :            : 
      26                 :            : inline void
      27                 :     150229 : encode_initial_chunk_header(Xapian::doccount termfreq,
      28                 :            :                             Xapian::termcount collfreq,
      29                 :            :                             Xapian::docid first,
      30                 :            :                             Xapian::docid last,
      31                 :            :                             Xapian::docid chunk_last,
      32                 :            :                             Xapian::termcount first_wdf,
      33                 :            :                             Xapian::termcount wdf_max,
      34                 :            :                             std::string & out)
      35                 :            : {
      36                 :            :     Assert(termfreq != 0);
      37                 :     150229 :     pack_uint(out, first - 1);
      38         [ +  + ]:     150229 :     if (termfreq == 1) {
      39                 :            :         // Special case for a term which only occurs in one document.  By
      40                 :            :         // Zipf's Law we expect these to be common in natural language
      41                 :            :         // (typically 40-60% of words in a large corpus:
      42                 :            :         // https://en.wikipedia.org/wiki/Hapax_legomenon ).  Another common
      43                 :            :         // example is unique ID boolean terms.
      44                 :            :         //
      45                 :            :         // There's no postlist data after the chunk header for such terms
      46                 :            :         // (since we know the first docid and its wdf from the data in
      47                 :            :         // the chunk header) so we can just encode the collfreq if it is
      48                 :            :         // non-zero - when decoding if there's no more data we'll know the
      49                 :            :         // collfreq is zero.
      50         [ +  + ]:      81833 :         if (collfreq) {
      51                 :      81830 :             pack_uint(out, collfreq);
      52                 :            :         }
      53                 :            :         AssertEq(first, last);
      54                 :            :         AssertEq(last, chunk_last);
      55                 :            :         AssertEq(collfreq, wdf_max);
      56                 :            :         AssertEq(collfreq, first_wdf);
      57         [ +  + ]:      68396 :     } else if (termfreq == 2) {
      58                 :            :         // A term which only occurs in two documents.  By Zipf's Law these
      59                 :            :         // are also fairly common (typically 10-15% of words in a large
      60                 :            :         // corpus: https://en.wikipedia.org/wiki/Hapax_legomenon )
      61                 :            :         //
      62                 :            :         // We have to encode collfreq == 0 explicitly or else the decoder can't
      63                 :            :         // distinguish between the cases:
      64                 :            :         //
      65                 :            :         //  tf = 1; collfreq = x
      66                 :            :         //  tf = 2; last = first + x + 1; collfreq = 0
      67                 :            :         //
      68                 :            :         // We turn this to our advantage to encode tf = 2 lists with constant
      69                 :            :         // wdf or where the second wdf is one more than the first (which are
      70                 :            :         // common cases) more compactly, so instead of:
      71                 :            :         //
      72                 :            :         // <first - 1> <collfreq> <last - first - 1> <first_wdf>
      73                 :            :         //
      74                 :            :         // We encode these as:
      75                 :            :         //
      76                 :            :         // <first - 1> <collfreq> <last - first - 1>
      77                 :            :         //
      78                 :            :         // And then when its omitted: first_wdf = collfreq >> 1
      79                 :            :         //
      80                 :            :         // The collfreq = 0 case is then a particular example of this.
      81                 :      22230 :         pack_uint(out, collfreq);
      82                 :            :         AssertRel(last, >, first);
      83                 :      22230 :         pack_uint(out, last - first - 1);
      84         [ +  + ]:      22230 :         if (first_wdf != (collfreq / 2)) {
      85                 :       1668 :             pack_uint(out, first_wdf);
      86                 :            :             AssertEq(max(first_wdf, collfreq - first_wdf), wdf_max);
      87                 :            :         } else {
      88                 :            :             AssertEq(collfreq - first_wdf, wdf_max);
      89                 :            :         }
      90         [ +  + ]:      46166 :     } else if (collfreq == 0) {
      91                 :            :         AssertEq(first_wdf, 0);
      92                 :            :         AssertEq(wdf_max, 0);
      93                 :          1 :         pack_uint(out, 0u);
      94                 :          1 :         pack_uint(out, termfreq - 3);
      95                 :          1 :         pack_uint(out, last - first - (termfreq - 1));
      96                 :          1 :         pack_uint(out, chunk_last - first);
      97                 :            :     } else {
      98                 :            :         AssertRel(collfreq, >=, termfreq);
      99                 :      46165 :         pack_uint(out, collfreq - termfreq + 1);
     100                 :      46165 :         pack_uint(out, termfreq - 3);
     101                 :      46165 :         pack_uint(out, last - first - (termfreq - 1));
     102                 :      46165 :         pack_uint(out, chunk_last - first);
     103                 :      46165 :         pack_uint(out, first_wdf - 1);
     104                 :            : 
     105         [ +  + ]:      46165 :         if (first_wdf >= collfreq - first_wdf - (termfreq - 2)) {
     106                 :            :             AssertEq(wdf_max, first_wdf);
     107                 :            :         } else {
     108                 :            :             AssertRel(wdf_max, >=, first_wdf);
     109                 :      18564 :             pack_uint(out, wdf_max - first_wdf);
     110                 :            :         }
     111                 :            :     }
     112                 :     150229 : }
     113                 :            : 
     114                 :            : inline bool
     115                 :     102668 : decode_initial_chunk_header(const char ** p, const char * end,
     116                 :            :                             Xapian::doccount & termfreq,
     117                 :            :                             Xapian::termcount & collfreq,
     118                 :            :                             Xapian::docid & first,
     119                 :            :                             Xapian::docid & last,
     120                 :            :                             Xapian::docid & chunk_last,
     121                 :            :                             Xapian::termcount & first_wdf,
     122                 :            :                             Xapian::termcount & wdf_max)
     123                 :            : {
     124         [ -  + ]:     102668 :     if (!unpack_uint(p, end, &first)) {
     125                 :          0 :         return false;
     126                 :            :     }
     127                 :     102668 :     ++first;
     128         [ +  + ]:     102668 :     if (*p == end) {
     129                 :         12 :         collfreq = 0;
     130         [ -  + ]:     102656 :     } else if (!unpack_uint(p, end, &collfreq)) {
     131                 :          0 :         return false;
     132                 :            :     }
     133         [ +  + ]:     102668 :     if (*p == end) {
     134                 :            :         // Single occurrence term.
     135                 :       2441 :         termfreq = 1;
     136                 :       2441 :         chunk_last = last = first;
     137                 :       2441 :         wdf_max = first_wdf = collfreq;
     138                 :       2441 :         return true;
     139                 :            :     }
     140                 :            : 
     141         [ -  + ]:     100227 :     if (!unpack_uint(p, end, &termfreq)) {
     142                 :          0 :         return false;
     143                 :            :     }
     144         [ +  + ]:     100227 :     if (*p == end) {
     145                 :            :         // Double occurrence term with first_wdf = floor(collfreq / 2).
     146                 :      46487 :         chunk_last = last = first + termfreq + 1;
     147                 :      46487 :         termfreq = 2;
     148                 :      46487 :         first_wdf = collfreq / 2;
     149         [ +  - ]:      46487 :         wdf_max = max(first_wdf, collfreq - first_wdf);
     150                 :      46487 :         return true;
     151                 :            :     }
     152                 :            : 
     153         [ -  + ]:      53740 :     if (!unpack_uint(p, end, &last)) {
     154                 :          0 :         return false;
     155                 :            :     }
     156         [ +  + ]:      53740 :     if (*p == end) {
     157                 :            :         // Double occurrence term.
     158                 :            :         Assert(collfreq != 0);
     159                 :        604 :         first_wdf = last;
     160                 :        604 :         chunk_last = last = first + termfreq + 1;
     161                 :        604 :         termfreq = 2;
     162         [ +  - ]:        604 :         wdf_max = max(first_wdf, collfreq - first_wdf);
     163                 :        604 :         return true;
     164                 :            :     }
     165                 :            : 
     166         [ -  + ]:      53136 :     if (!unpack_uint(p, end, &chunk_last)) {
     167                 :          0 :         return false;
     168                 :            :     }
     169                 :      53136 :     termfreq += 3;
     170                 :      53136 :     last += first + termfreq - 1;
     171                 :      53136 :     chunk_last += first;
     172                 :            : 
     173         [ +  + ]:      53136 :     if (collfreq == 0) {
     174                 :          2 :         wdf_max = first_wdf = 0;
     175                 :            :     } else {
     176                 :      53134 :         collfreq += (termfreq - 1);
     177         [ -  + ]:      53134 :         if (!unpack_uint(p, end, &first_wdf)) {
     178                 :          0 :             return false;
     179                 :            :         }
     180                 :      53134 :         ++first_wdf;
     181         [ +  + ]:      53134 :         if (first_wdf >= collfreq - first_wdf - (termfreq - 2)) {
     182                 :       1133 :             wdf_max = first_wdf;
     183                 :            :         } else {
     184         [ -  + ]:      52001 :             if (!unpack_uint(p, end, &wdf_max)) {
     185                 :          0 :                 return false;
     186                 :            :             }
     187                 :      52001 :             wdf_max += first_wdf;
     188                 :            :         }
     189                 :            :     }
     190                 :            : 
     191                 :     102668 :     return true;
     192                 :            : }
     193                 :            : 
     194                 :            : inline bool
     195                 :      99990 : decode_initial_chunk_header_freqs(const char ** p, const char * end,
     196                 :            :                                   Xapian::doccount & termfreq,
     197                 :            :                                   Xapian::termcount & collfreq)
     198                 :            : {
     199                 :            :     Xapian::docid first;
     200         [ -  + ]:      99990 :     if (!unpack_uint(p, end, &first)) {
     201                 :          0 :         return false;
     202                 :            :     }
     203                 :            :     // Not used in this case.
     204                 :            :     (void)first;
     205         [ +  + ]:      99990 :     if (*p == end) {
     206                 :          6 :         collfreq = 0;
     207         [ -  + ]:      99984 :     } else if (!unpack_uint(p, end, &collfreq)) {
     208                 :          0 :         return false;
     209                 :            :     }
     210         [ +  + ]:      99990 :     if (*p == end) {
     211                 :            :         // Single occurrence term.
     212                 :       4677 :         termfreq = 1;
     213                 :       4677 :         return true;
     214                 :            :     }
     215                 :            : 
     216         [ -  + ]:      95313 :     if (!unpack_uint(p, end, &termfreq)) {
     217                 :          0 :         return false;
     218                 :            :     }
     219         [ +  + ]:      95313 :     if (*p == end) {
     220                 :            :         // Double occurrence term with first_wdf = floor(collfreq / 2).
     221                 :      25325 :         termfreq = 2;
     222                 :      25325 :         return true;
     223                 :            :     }
     224                 :            : 
     225                 :            :     Xapian::docid last;
     226         [ -  + ]:      69988 :     if (!unpack_uint(p, end, &last)) {
     227                 :          0 :         return false;
     228                 :            :     }
     229                 :            :     // Not used in this case.
     230                 :            :     (void)last;
     231         [ +  + ]:      69988 :     if (*p == end) {
     232                 :            :         // Double occurrence term.
     233                 :            :         Assert(collfreq != 0);
     234                 :        304 :         termfreq = 2;
     235                 :        304 :         return true;
     236                 :            :     }
     237                 :            : 
     238                 :      69684 :     termfreq += 3;
     239         [ +  + ]:      69684 :     if (collfreq != 0) {
     240                 :      69683 :         collfreq += (termfreq - 1);
     241                 :            :     }
     242                 :            : 
     243                 :      99990 :     return true;
     244                 :            : }
     245                 :            : 
     246                 :            : inline void
     247                 :         43 : encode_delta_chunk_header(Xapian::docid chunk_first,
     248                 :            :                           Xapian::docid chunk_last,
     249                 :            :                           Xapian::termcount chunk_first_wdf,
     250                 :            :                           std::string & out)
     251                 :            : {
     252                 :            :     Assert(chunk_first_wdf != 0);
     253                 :         43 :     pack_uint(out, chunk_last - chunk_first);
     254                 :         43 :     pack_uint(out, chunk_first_wdf - 1);
     255                 :         43 : }
     256                 :            : 
     257                 :            : inline bool
     258                 :          9 : decode_delta_chunk_header(const char ** p, const char * end,
     259                 :            :                           Xapian::docid chunk_last,
     260                 :            :                           Xapian::docid& chunk_first,
     261                 :            :                           Xapian::termcount& chunk_first_wdf)
     262                 :            : {
     263   [ +  -  +  + ]:         18 :     if (!unpack_uint(p, end, &chunk_first) ||
                 [ +  + ]
     264                 :          9 :         !unpack_uint(p, end, &chunk_first_wdf)) {
     265                 :          4 :         return false;
     266                 :            :     }
     267                 :          5 :     chunk_first = chunk_last - chunk_first;
     268                 :          5 :     ++chunk_first_wdf;
     269                 :          5 :     return true;
     270                 :            : }
     271                 :            : 
     272                 :            : inline void
     273                 :         54 : encode_delta_chunk_header_no_wdf(Xapian::docid chunk_first,
     274                 :            :                                  Xapian::docid chunk_last,
     275                 :            :                                  std::string & out)
     276                 :            : {
     277                 :         54 :     pack_uint(out, chunk_last - chunk_first);
     278                 :         54 : }
     279                 :            : 
     280                 :            : inline bool
     281                 :          6 : decode_delta_chunk_header_no_wdf(const char ** p, const char * end,
     282                 :            :                                  Xapian::docid chunk_last,
     283                 :            :                                  Xapian::docid& chunk_first)
     284                 :            : {
     285         [ -  + ]:          6 :     if (!unpack_uint(p, end, &chunk_first)) {
     286                 :          0 :         return false;
     287                 :            :     }
     288                 :          6 :     chunk_first = chunk_last - chunk_first;
     289                 :          6 :     return true;
     290                 :            : }
     291                 :            : 
     292                 :            : #endif // XAPIAN_INCLUDED_HONEY_POSTLIST_ENCODINGS_H

Generated by: LCOV version 1.11