LCOV - code coverage report
Current view: top level - matcher - valuerangepostlist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core fcfb185a9dd5 Lines: 65 97 67.0 %
Date: 2019-04-18 16:33:14 Functions: 11 16 68.8 %
Branches: 61 128 47.7 %

           Branch data     Line data    Source code
       1                 :            : /** @file valuerangepostlist.cc
       2                 :            :  * @brief Return document ids matching a range test on a specified doc value.
       3                 :            :  */
       4                 :            : /* Copyright 2007,2008,2009,2010,2011,2013,2016,2017 Olly Betts
       5                 :            :  * Copyright 2009 Lemur Consulting Ltd
       6                 :            :  * Copyright 2010 Richard Boulton
       7                 :            :  *
       8                 :            :  * This program is free software; you can redistribute it and/or modify
       9                 :            :  * it under the terms of the GNU General Public License as published by
      10                 :            :  * the Free Software Foundation; either version 2 of the License, or
      11                 :            :  * (at your option) any later version.
      12                 :            :  *
      13                 :            :  * This program is distributed in the hope that it will be useful,
      14                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      15                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      16                 :            :  * GNU General Public License for more details.
      17                 :            :  *
      18                 :            :  * You should have received a copy of the GNU General Public License
      19                 :            :  * along with this program; if not, write to the Free Software
      20                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
      21                 :            :  */
      22                 :            : 
      23                 :            : #include <config.h>
      24                 :            : 
      25                 :            : #include "valuerangepostlist.h"
      26                 :            : 
      27                 :            : #include "debuglog.h"
      28                 :            : #include "omassert.h"
      29                 :            : #include "str.h"
      30                 :            : #include "unicode/description_append.h"
      31                 :            : 
      32                 :            : using namespace std;
      33                 :            : 
      34                 :      35826 : ValueRangePostList::~ValueRangePostList()
      35                 :            : {
      36         [ +  + ]:      12150 :     delete valuelist;
      37         [ -  + ]:      23676 : }
      38                 :            : 
      39                 :            : Xapian::doccount
      40                 :      12146 : ValueRangePostList::get_termfreq_min() const
      41                 :            : {
      42                 :      12146 :     const string& lo = db->get_value_lower_bound(slot);
      43         [ +  - ]:      24292 :     const string& hi = db->get_value_upper_bound(slot);
      44 [ +  - ][ +  + ]:      12146 :     if (begin <= lo && (end.empty() || hi <= end)) {
         [ +  + ][ +  - ]
         [ -  + ][ +  + ]
      45                 :            :         // All set values lie within the range (this case is optimised at a
      46                 :            :         // higher level when the value frequency is the doc count, but not
      47                 :            :         // otherwise).
      48         [ +  - ]:         32 :         return db->get_value_freq(slot);
      49                 :            :     }
      50                 :            : 
      51                 :            :     // The bounds may not be tight, so one bound being within the range does
      52                 :            :     // not mean we can assume that at least one document matches.
      53                 :      24260 :     return 0;
      54                 :            : }
      55                 :            : 
      56                 :            : static double
      57                 :      47324 : string_frac(const string &s, size_t prefix)
      58                 :            : {
      59                 :      47324 :     double r = 0;
      60                 :      47324 :     double f = 1.0;
      61         [ +  + ]:     121925 :     for (size_t i = prefix; i != s.size(); ++i) {
      62                 :      74601 :         f /= 256.0;
      63                 :      74601 :         r += static_cast<unsigned char>(s[i]) * f;
      64                 :            :     }
      65                 :            : 
      66                 :      47324 :     return r;
      67                 :            : }
      68                 :            : 
      69                 :            : Xapian::doccount
      70                 :      12198 : ValueRangePostList::get_termfreq_est() const
      71                 :            : {
      72                 :            :     // Assume the values are evenly spread out between the min and max.
      73                 :            :     // FIXME: Perhaps we should store some sort of binned distribution?
      74                 :      12198 :     const string& lo = db->get_value_lower_bound(slot);
      75         [ +  - ]:      24396 :     const string& hi = db->get_value_upper_bound(slot);
      76                 :            :     AssertRel(lo, <=, hi);
      77                 :            : 
      78                 :      12198 :     size_t common_prefix_len = size_t(-1);
      79         [ +  + ]:      12319 :     do {
      80                 :      12363 :         ++common_prefix_len;
      81                 :            :         // lo <= hi so while we're in the common prefix hi can't run out
      82                 :            :         // before lo.
      83         [ +  + ]:      12363 :         if (common_prefix_len == lo.size()) {
      84         [ +  + ]:         44 :             if (common_prefix_len != hi.size())
      85                 :          4 :                 break;
      86                 :            :             // All values in the slot are the same.  We should have optimised
      87                 :            :             // to NULL if that singular value is outside the range, and if it's
      88                 :            :             // inside the range then we know that the frequency is exactly the
      89                 :            :             // value frequency.
      90                 :            :             Assert(begin <= lo && (end.empty() || hi <= end));
      91         [ +  - ]:         40 :             return db->get_value_freq(slot);
      92                 :            :         }
      93                 :            :         AssertRel(common_prefix_len, !=, hi.size());
      94                 :      12319 :     } while (lo[common_prefix_len] == hi[common_prefix_len]);
      95                 :            : 
      96                 :      12158 :     double l = string_frac(lo, common_prefix_len);
      97                 :      12158 :     double h = string_frac(hi, common_prefix_len);
      98                 :      12158 :     double denom = h - l;
      99         [ +  + ]:      12158 :     if (rare(denom == 0.0)) {
     100                 :            :         // Weird corner case - hi != lo (because that's handled inside the loop
     101                 :            :         // above) but they give the same string_frac value.  Because we only
     102                 :            :         // calculate the fraction starting from the first difference, this
     103                 :            :         // should only happen if hi is lo + one or more trailing zero bytes.
     104                 :            : 
     105 [ +  - ][ +  - ]:          4 :         if (begin <= lo && (end.empty() || hi <= end)) {
         [ +  + ][ +  - ]
         [ -  + ][ +  + ]
     106                 :            :             // All set values lie within the range (this case is optimised at a
     107                 :            :             // higher level when the value frequency is the doc count, but not
     108                 :            :             // otherwise).
     109         [ +  - ]:          2 :             return db->get_value_freq(slot);
     110                 :            :         }
     111                 :            : 
     112                 :            :         // There must be partial overlap - we just checked if the range
     113                 :            :         // dominates the bounds, and a range which is entirely outside the
     114                 :            :         // bounds is optimised to NULL at a higher level.
     115         [ +  - ]:          2 :         return db->get_value_freq(slot) / 2;
     116                 :            :     }
     117                 :            : 
     118                 :      12154 :     double b = l;
     119 [ +  - ][ +  + ]:      12154 :     if (begin > lo) {
     120                 :      11484 :         b = string_frac(begin, common_prefix_len);
     121                 :            :     }
     122                 :      12154 :     double e = h;
     123 [ +  + ][ +  - ]:      12154 :     if (!end.empty() && end < hi) {
         [ +  - ][ +  + ]
     124                 :            :         // end is empty for a ValueGePostList
     125                 :      11524 :         e = string_frac(end, common_prefix_len);
     126                 :            :     }
     127                 :            : 
     128         [ +  - ]:      12154 :     double est = (e - b) / denom * db->get_value_freq(slot);
     129                 :      24352 :     return Xapian::doccount(est + 0.5);
     130                 :            : }
     131                 :            : 
     132                 :            : TermFreqs
     133                 :          0 : ValueRangePostList::get_termfreq_est_using_stats(
     134                 :            :         const Xapian::Weight::Internal & stats) const
     135                 :            : {
     136                 :            :     LOGCALL(MATCH, TermFreqs, "ValueRangePostList::get_termfreq_est_using_stats", stats);
     137                 :            :     // FIXME: It's hard to estimate well - perhaps consider the values of
     138                 :            :     // begin and end like above?
     139                 :          0 :     RETURN(TermFreqs(stats.collection_size / 2,
     140                 :            :                      stats.rset_size / 2,
     141                 :            :                      stats.total_term_count / 2));
     142                 :            : }
     143                 :            : 
     144                 :            : Xapian::doccount
     145                 :      12150 : ValueRangePostList::get_termfreq_max() const
     146                 :            : {
     147                 :      12150 :     return db->get_value_freq(slot);
     148                 :            : }
     149                 :            : 
     150                 :            : Xapian::docid
     151                 :     202533 : ValueRangePostList::get_docid() const
     152                 :            : {
     153                 :            :     Assert(valuelist);
     154                 :            :     Assert(db);
     155                 :     202533 :     return valuelist->get_docid();
     156                 :            : }
     157                 :            : 
     158                 :            : double
     159                 :        149 : ValueRangePostList::get_weight(Xapian::termcount,
     160                 :            :                                Xapian::termcount) const
     161                 :            : {
     162                 :            :     Assert(db);
     163                 :        149 :     return 0;
     164                 :            : }
     165                 :            : 
     166                 :            : double
     167                 :      12150 : ValueRangePostList::recalc_maxweight()
     168                 :            : {
     169                 :            :     Assert(db);
     170                 :      12150 :     return 0;
     171                 :            : }
     172                 :            : 
     173                 :            : PositionList *
     174                 :          0 : ValueRangePostList::read_position_list()
     175                 :            : {
     176                 :            :     Assert(db);
     177                 :          0 :     return NULL;
     178                 :            : }
     179                 :            : 
     180                 :            : PostList *
     181                 :     202444 : ValueRangePostList::next(double)
     182                 :            : {
     183                 :            :     Assert(db);
     184         [ +  + ]:     202444 :     if (!valuelist) valuelist = db->open_value_list(slot);
     185                 :     202444 :     valuelist->next();
     186         [ +  + ]:     576737 :     while (!valuelist->at_end()) {
     187                 :     565221 :         const string & v = valuelist->get_value();
     188 [ +  - ][ +  + ]:     565221 :         if (v >= begin && v <= end) {
         [ +  - ][ +  + ]
                 [ +  + ]
     189                 :     190928 :             return NULL;
     190                 :            :         }
     191 [ +  - ][ +  + ]:     565221 :         valuelist->next();
     192                 :     374293 :     }
     193                 :      11516 :     db = NULL;
     194                 :     202444 :     return NULL;
     195                 :            : }
     196                 :            : 
     197                 :            : PostList *
     198                 :          0 : ValueRangePostList::skip_to(Xapian::docid did, double)
     199                 :            : {
     200                 :            :     Assert(db);
     201         [ #  # ]:          0 :     if (!valuelist) valuelist = db->open_value_list(slot);
     202                 :          0 :     valuelist->skip_to(did);
     203         [ #  # ]:          0 :     while (!valuelist->at_end()) {
     204                 :          0 :         const string & v = valuelist->get_value();
     205 [ #  # ][ #  # ]:          0 :         if (v >= begin && v <= end) {
         [ #  # ][ #  # ]
                 [ #  # ]
     206                 :          0 :             return NULL;
     207                 :            :         }
     208 [ #  # ][ #  # ]:          0 :         valuelist->next();
     209                 :          0 :     }
     210                 :          0 :     db = NULL;
     211                 :          0 :     return NULL;
     212                 :            : }
     213                 :            : 
     214                 :            : PostList *
     215                 :          0 : ValueRangePostList::check(Xapian::docid did, double, bool &valid)
     216                 :            : {
     217                 :            :     Assert(db);
     218                 :            :     AssertRelParanoid(did, <=, db->get_lastdocid());
     219         [ #  # ]:          0 :     if (!valuelist) valuelist = db->open_value_list(slot);
     220                 :          0 :     valid = valuelist->check(did);
     221         [ #  # ]:          0 :     if (!valid) {
     222                 :          0 :         return NULL;
     223                 :            :     }
     224                 :          0 :     const string & v = valuelist->get_value();
     225 [ #  # ][ #  # ]:          0 :     valid = (v >= begin && v <= end);
         [ #  # ][ #  # ]
     226                 :          0 :     return NULL;
     227                 :            : }
     228                 :            : 
     229                 :            : bool
     230                 :     214609 : ValueRangePostList::at_end() const
     231                 :            : {
     232                 :     214609 :     return (db == NULL);
     233                 :            : }
     234                 :            : 
     235                 :            : Xapian::termcount
     236                 :         48 : ValueRangePostList::count_matching_subqs() const
     237                 :            : {
     238                 :         48 :     return 1;
     239                 :            : }
     240                 :            : 
     241                 :            : string
     242                 :          0 : ValueRangePostList::get_description() const
     243                 :            : {
     244         [ #  # ]:          0 :     string desc = "ValueRangePostList(";
     245 [ #  # ][ #  # ]:          0 :     desc += str(slot);
     246         [ #  # ]:          0 :     desc += ", ";
     247         [ #  # ]:          0 :     description_append(desc, begin);
     248         [ #  # ]:          0 :     desc += ", ";
     249         [ #  # ]:          0 :     description_append(desc, end);
     250         [ #  # ]:          0 :     desc += ")";
     251                 :          0 :     return desc;
     252                 :            : }

Generated by: LCOV version 1.11