LCOV - code coverage report
Current view: top level - matcher - boolorpostlist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 7028d852e609 Lines: 100 129 77.5 %
Date: 2019-02-17 14:59:59 Functions: 12 18 66.7 %
Branches: 53 98 54.1 %

           Branch data     Line data    Source code
       1                 :            : /** @file boolorpostlist.cc
       2                 :            :  * @brief PostList class implementing unweighted Query::OP_OR
       3                 :            :  */
       4                 :            : /* Copyright 2017,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                 :            : #include <config.h>
      22                 :            : 
      23                 :            : #include "boolorpostlist.h"
      24                 :            : 
      25                 :            : #include "heap.h"
      26                 :            : #include "postlisttree.h"
      27                 :            : 
      28                 :            : #include <algorithm>
      29                 :            : #include <functional>
      30                 :            : 
      31                 :            : using namespace std;
      32                 :            : 
      33                 :       2274 : BoolOrPostList::~BoolOrPostList()
      34                 :            : {
      35         [ +  - ]:        758 :     if (plist) {
      36         [ -  + ]:        758 :         for (size_t i = 0; i < n_kids; ++i) {
      37         [ #  # ]:          0 :             delete plist[i].pl;
      38                 :            :         }
      39         [ +  - ]:        758 :         delete [] plist;
      40                 :            :     }
      41         [ -  + ]:       1516 : }
      42                 :            : 
      43                 :            : Xapian::doccount
      44                 :        774 : BoolOrPostList::get_termfreq_min() const
      45                 :            : {
      46                 :            :     Assert(n_kids != 0);
      47         [ +  - ]:        774 :     Xapian::doccount res = plist[0].pl->get_termfreq_min();
      48         [ +  + ]:       1783 :     for (size_t i = 1; i < n_kids; ++i) {
      49         [ +  - ]:       1009 :         res = max(res, plist[i].pl->get_termfreq_min());
      50                 :            :     }
      51                 :        774 :     return res;
      52                 :            : }
      53                 :            : 
      54                 :            : Xapian::docid
      55                 :      11985 : BoolOrPostList::get_docid() const
      56                 :            : {
      57                 :            :     Assert(did != 0);
      58                 :      11985 :     return did;
      59                 :            : }
      60                 :            : 
      61                 :            : double
      62                 :          0 : BoolOrPostList::get_weight(Xapian::termcount, Xapian::termcount) const
      63                 :            : {
      64                 :          0 :     return 0;
      65                 :            : }
      66                 :            : 
      67                 :            : double
      68                 :         29 : BoolOrPostList::recalc_maxweight()
      69                 :            : {
      70                 :         29 :     return 0;
      71                 :            : }
      72                 :            : 
      73                 :            : PostList*
      74                 :       8418 : BoolOrPostList::next(double)
      75                 :            : {
      76         [ +  + ]:      19684 :     while (plist[0].did == did) {
      77                 :      11474 :         PostList* res = plist[0].pl->next(0);
      78         [ +  + ]:      11474 :         if (res) {
      79         [ +  - ]:         98 :             delete plist[0].pl;
      80                 :         98 :             plist[0].pl = res;
      81                 :            :         }
      82                 :            : 
      83         [ +  + ]:      11474 :         if (plist[0].pl->at_end()) {
      84         [ +  + ]:       1194 :             if (n_kids == 1) {
      85                 :            :                 // We've reached the end of all posting lists - prune
      86                 :            :                 // returning an at_end postlist.
      87                 :        208 :                 n_kids = 0;
      88                 :        208 :                 return plist[0].pl;
      89                 :            :             }
      90         [ +  - ]:        986 :             Heap::pop(plist, plist + n_kids, std::greater<PostListAndDocID>());
      91         [ +  - ]:        986 :             delete plist[--n_kids].pl;
      92                 :        986 :             continue;
      93                 :            :         }
      94                 :      10280 :         plist[0].did = plist[0].pl->get_docid();
      95         [ +  - ]:      10280 :         Heap::replace(plist, plist + n_kids, std::greater<PostListAndDocID>());
      96                 :            :     }
      97                 :            : 
      98         [ +  + ]:       8210 :     if (n_kids == 1) {
      99                 :        543 :         n_kids = 0;
     100                 :        543 :         return plist[0].pl;
     101                 :            :     }
     102                 :            : 
     103                 :       7667 :     did = plist[0].did;
     104                 :            : 
     105                 :       8418 :     return NULL;
     106                 :            : }
     107                 :            : 
     108                 :            : PostList*
     109                 :         26 : BoolOrPostList::skip_to(Xapian::docid did_min, double)
     110                 :            : {
     111         [ -  + ]:         26 :     if (rare(did_min <= did)) return NULL;
     112                 :         26 :     did = Xapian::docid(-1);
     113                 :         26 :     size_t j = 0;
     114         [ +  + ]:         78 :     for (size_t i = 0; i < n_kids; ++i) {
     115         [ +  + ]:         52 :         if (plist[i].did < did_min) {
     116                 :         26 :             PostList * res = plist[i].pl->skip_to(did_min, 0);
     117         [ -  + ]:         26 :             if (res) {
     118         [ #  # ]:          0 :                 delete plist[i].pl;
     119                 :          0 :                 plist[j].pl = res;
     120                 :            :             } else {
     121                 :         26 :                 plist[j].pl = plist[i].pl;
     122                 :            :             }
     123                 :            : 
     124         [ +  + ]:         26 :             if (plist[j].pl->at_end()) {
     125 [ +  - ][ -  + ]:          7 :                 if (j == 0 && i == n_kids - 1) {
     126                 :            :                     // We've reached the end of all posting lists - prune
     127                 :            :                     // returning an at_end postlist.
     128                 :          0 :                     n_kids = 0;
     129                 :          0 :                     return plist[j].pl;
     130                 :            :                 }
     131         [ +  - ]:          7 :                 delete plist[j].pl;
     132                 :          7 :                 continue;
     133                 :            :             }
     134                 :         19 :             plist[j].did = plist[j].pl->get_docid();
     135         [ +  + ]:         26 :         } else if (j != i) {
     136                 :          7 :             plist[j].pl = plist[i].pl;
     137                 :            :         }
     138                 :            : 
     139                 :         45 :         did = min(did, plist[j].did);
     140                 :            : 
     141                 :         45 :         ++j;
     142                 :            :     }
     143                 :            : 
     144                 :            :     Assert(j != 0);
     145                 :         26 :     n_kids = j;
     146         [ +  + ]:         26 :     if (n_kids == 1) {
     147                 :          7 :         n_kids = 0;
     148                 :          7 :         return plist[0].pl;
     149                 :            :     }
     150                 :            : 
     151                 :            :     // Restore the heap invariant.
     152         [ +  - ]:         19 :     Heap::make(plist, plist + n_kids, std::greater<PostListAndDocID>());
     153                 :            : 
     154                 :         26 :     return NULL;
     155                 :            : }
     156                 :            : 
     157                 :            : Xapian::doccount
     158                 :       1524 : BoolOrPostList::get_termfreq_max() const
     159                 :            : {
     160                 :            :     Assert(n_kids != 0);
     161                 :            :     // Maximum is if all sub-postlists are disjoint.
     162                 :       1524 :     Xapian::doccount result = plist[0].pl->get_termfreq_max();
     163         [ +  + ]:       3014 :     for (size_t i = 1; i < n_kids; ++i) {
     164                 :       1660 :         Xapian::doccount tf_max = plist[i].pl->get_termfreq_max();
     165                 :       1660 :         Xapian::doccount old_result = result;
     166                 :       1660 :         result += tf_max;
     167                 :            :         // Catch overflowing the type too.
     168 [ +  + ][ -  + ]:       1660 :         if (result >= db_size || result < old_result)
     169                 :        170 :             return db_size;
     170                 :            :     }
     171                 :       1354 :     return result;
     172                 :            : }
     173                 :            : 
     174                 :            : Xapian::doccount
     175                 :        824 : BoolOrPostList::get_termfreq_est() const
     176                 :            : {
     177         [ -  + ]:        824 :     if (rare(db_size == 0))
     178                 :          0 :         return 0;
     179                 :            :     Assert(n_kids != 0);
     180                 :            :     // We calculate the estimate assuming independence.  The simplest
     181                 :            :     // way to calculate this seems to be a series of (n_kids - 1) pairwise
     182                 :            :     // calculations, which gives the same answer regardless of the order.
     183                 :        824 :     double scale = 1.0 / db_size;
     184                 :        824 :     double P_est = plist[0].pl->get_termfreq_est() * scale;
     185         [ +  + ]:       1883 :     for (size_t i = 1; i < n_kids; ++i) {
     186                 :       1059 :         double P_i = plist[i].pl->get_termfreq_est() * scale;
     187                 :       1059 :         P_est += P_i - P_est * P_i;
     188                 :            :     }
     189                 :        824 :     return static_cast<Xapian::doccount>(P_est * db_size + 0.5);
     190                 :            : }
     191                 :            : 
     192                 :            : TermFreqs
     193                 :        729 : BoolOrPostList::get_termfreq_est_using_stats(
     194                 :            :         const Xapian::Weight::Internal& stats) const
     195                 :            : {
     196                 :            :     Assert(n_kids != 0);
     197                 :            :     // We calculate the estimate assuming independence.  The simplest
     198                 :            :     // way to calculate this seems to be a series of (n_kids - 1) pairwise
     199                 :            :     // calculations, which gives the same answer regardless of the order.
     200         [ +  - ]:        729 :     TermFreqs freqs(plist[0].pl->get_termfreq_est_using_stats(stats));
     201                 :            : 
     202                 :            :     // Our caller should have ensured this.
     203                 :            :     Assert(stats.collection_size);
     204                 :        729 :     double scale = 1.0 / stats.collection_size;
     205                 :        729 :     double P_est = freqs.termfreq * scale;
     206                 :        729 :     double rtf_scale = 0.0;
     207         [ -  + ]:        729 :     if (stats.rset_size != 0) {
     208                 :          0 :         rtf_scale = 1.0 / stats.rset_size;
     209                 :            :     }
     210                 :        729 :     double Pr_est = freqs.reltermfreq * rtf_scale;
     211                 :        729 :     double cf_scale = 1.0 / stats.total_term_count;
     212                 :        729 :     double Pc_est = freqs.collfreq * cf_scale;
     213                 :            : 
     214         [ +  + ]:       1693 :     for (size_t i = 1; i < n_kids; ++i) {
     215         [ +  - ]:        964 :         freqs = plist[i].pl->get_termfreq_est_using_stats(stats);
     216                 :        964 :         double P_i = freqs.termfreq * scale;
     217                 :        964 :         P_est += P_i - P_est * P_i;
     218                 :        964 :         double Pc_i = freqs.collfreq * cf_scale;
     219                 :        964 :         Pc_est += Pc_i - Pc_est * Pc_i;
     220                 :            :         // If the rset is empty, Pr_est should be 0 already, so leave
     221                 :            :         // it alone.
     222         [ -  + ]:        964 :         if (stats.rset_size != 0) {
     223                 :          0 :             double Pr_i = freqs.reltermfreq * rtf_scale;
     224                 :          0 :             Pr_est += Pr_i - Pr_est * Pr_i;
     225                 :            :         }
     226                 :            :     }
     227                 :        729 :     return TermFreqs(Xapian::doccount(P_est * stats.collection_size + 0.5),
     228                 :        729 :                      Xapian::doccount(Pr_est * stats.rset_size + 0.5),
     229                 :        729 :                      Xapian::termcount(Pc_est * stats.total_term_count + 0.5));
     230                 :            : }
     231                 :            : 
     232                 :            : bool
     233                 :       7895 : BoolOrPostList::at_end() const
     234                 :            : {
     235                 :            :     // We never need to return true here - if all but one child reaches
     236                 :            :     // at_end(), we prune to leave just that child.  If all children reach
     237                 :            :     // at_end() together, we prune to leave one of them which will then
     238                 :            :     // indicate at_end() for us.
     239                 :       7895 :     return false;
     240                 :            : }
     241                 :            : 
     242                 :            : std::string
     243                 :          0 : BoolOrPostList::get_description() const
     244                 :            : {
     245         [ #  # ]:          0 :     string desc = "BoolOrPostList(";
     246 [ #  # ][ #  # ]:          0 :     desc += plist[0].pl->get_description();
     247         [ #  # ]:          0 :     for (size_t i = 1; i < n_kids; ++i) {
     248         [ #  # ]:          0 :         desc += ", ";
     249 [ #  # ][ #  # ]:          0 :         desc += plist[i].pl->get_description();
     250                 :            :     }
     251         [ #  # ]:          0 :     desc += ')';
     252                 :          0 :     return desc;
     253                 :            : }
     254                 :            : 
     255                 :            : Xapian::termcount
     256                 :       7404 : BoolOrPostList::get_wdf() const
     257                 :            : {
     258                 :       9442 :     return for_all_matches([](PostList* pl) {
     259                 :       9442 :                                return pl->get_wdf();
     260         [ +  - ]:      16846 :                            });
     261                 :            : }
     262                 :            : 
     263                 :            : Xapian::termcount
     264                 :          0 : BoolOrPostList::count_matching_subqs() const
     265                 :            : {
     266                 :          0 :     return for_all_matches([](PostList* pl) {
     267                 :          0 :                                return pl->count_matching_subqs();
     268         [ #  # ]:          0 :                            });
     269                 :            : }
     270                 :            : 
     271                 :            : void
     272                 :          0 : BoolOrPostList::gather_position_lists(OrPositionList* orposlist)
     273                 :            : {
     274                 :          0 :     for_all_matches([&orposlist](PostList* pl) {
     275                 :          0 :                         pl->gather_position_lists(orposlist);
     276                 :          0 :                         return 0;
     277                 :          0 :                     });
     278                 :          0 : }

Generated by: LCOV version 1.11