LCOV - code coverage report
Current view: top level - matcher - multiandpostlist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 7028d852e609 Lines: 95 112 84.8 %
Date: 2019-02-17 14:59:59 Functions: 15 17 88.2 %
Branches: 55 92 59.8 %

           Branch data     Line data    Source code
       1                 :            : /** @file multiandpostlist.cc
       2                 :            :  * @brief N-way AND postlist
       3                 :            :  */
       4                 :            : /* Copyright (C) 2007,2009,2011,2012,2015,2017 Olly Betts
       5                 :            :  * Copyright (C) 2009 Lemur Consulting Ltd
       6                 :            :  *
       7                 :            :  * This program is free software; you can redistribute it and/or
       8                 :            :  * modify it under the terms of the GNU General Public License as
       9                 :            :  * published by the Free Software Foundation; either version 2 of the
      10                 :            :  * License, or (at your option) any later version.
      11                 :            :  *
      12                 :            :  * This program is distributed in the hope that it will be useful,
      13                 :            :  * but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            :  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            :  * GNU General Public License for more details.
      16                 :            :  *
      17                 :            :  * You should have received a copy of the GNU General Public License
      18                 :            :  * along with this program; if not, write to the Free Software
      19                 :            :  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301 USA
      20                 :            :  */
      21                 :            : 
      22                 :            : #include <config.h>
      23                 :            : 
      24                 :            : #include "multiandpostlist.h"
      25                 :            : #include "omassert.h"
      26                 :            : #include "debuglog.h"
      27                 :            : 
      28                 :            : using namespace std;
      29                 :            : 
      30                 :            : void
      31                 :       1248 : MultiAndPostList::allocate_plist_and_max_wt()
      32                 :            : {
      33         [ +  - ]:       1248 :     plist = new PostList * [n_kids];
      34                 :            :     try {
      35 [ +  - ][ +  - ]:       4208 :         max_wt = new double [n_kids]();
                 [ +  + ]
      36                 :          0 :     } catch (...) {
      37         [ #  # ]:          0 :         delete [] plist;
      38                 :          0 :         plist = NULL;
      39                 :          0 :         throw;
      40                 :            :     }
      41                 :       1248 : }
      42                 :            : 
      43                 :       3744 : MultiAndPostList::~MultiAndPostList()
      44                 :            : {
      45         [ +  - ]:       1248 :     if (plist) {
      46         [ +  + ]:       4208 :         for (size_t i = 0; i < n_kids; ++i) {
      47         [ +  - ]:       2960 :             delete plist[i];
      48                 :            :         }
      49         [ +  - ]:       1248 :         delete [] plist;
      50                 :            :     }
      51         [ +  - ]:       1248 :     delete [] max_wt;
      52         [ -  + ]:       2496 : }
      53                 :            : 
      54                 :            : Xapian::doccount
      55                 :        486 : MultiAndPostList::get_termfreq_min() const
      56                 :            : {
      57                 :            :     // The number of matching documents is minimised when we have the minimum
      58                 :            :     // number of matching documents from each sub-postlist, and these are
      59                 :            :     // maximally disjoint.
      60                 :        486 :     Xapian::doccount sum = plist[0]->get_termfreq_min();
      61         [ +  + ]:        486 :     if (sum) {
      62         [ +  + ]:        544 :         for (size_t i = 1; i < n_kids; ++i) {
      63                 :        402 :             Xapian::doccount sum_old = sum;
      64                 :        402 :             sum += plist[i]->get_termfreq_min();
      65                 :            :             // If sum < sum_old, the calculation overflowed and the true sum
      66                 :            :             // must be > db_size.  Since we added a value <= db_size,
      67                 :            :             // subtracting db_size must un-overflow us.
      68 [ +  - ][ +  + ]:        402 :             if (sum >= sum_old && sum <= db_size) {
      69                 :            :                 // It's possible there's no overlap.
      70                 :        260 :                 return 0;
      71                 :            :             }
      72                 :        142 :             sum -= db_size;
      73                 :            :         }
      74                 :            :         AssertRelParanoid(sum,<=,MultiAndPostList::get_termfreq_est());
      75                 :            :     }
      76                 :        226 :     return sum;
      77                 :            : }
      78                 :            : 
      79                 :            : Xapian::doccount
      80                 :       1214 : MultiAndPostList::get_termfreq_max() const
      81                 :            : {
      82                 :            :     // We can't match more documents than the least of our sub-postlists.
      83                 :       1214 :     Xapian::doccount result = plist[0]->get_termfreq_max();
      84         [ +  + ]:       2924 :     for (size_t i = 1; i < n_kids; ++i) {
      85                 :       1710 :         Xapian::doccount tf = plist[i]->get_termfreq_max();
      86         [ +  + ]:       1710 :         if (tf < result) result = tf;
      87                 :            :     }
      88                 :       1214 :     return result;
      89                 :            : }
      90                 :            : 
      91                 :            : Xapian::doccount
      92                 :       1458 : MultiAndPostList::get_termfreq_est() const
      93                 :            : {
      94                 :            :     LOGCALL(MATCH, Xapian::doccount, "MultiAndPostList::get_termfreq_est", NO_ARGS);
      95         [ +  + ]:       1458 :     if (rare(db_size == 0))
      96                 :         37 :         RETURN(0);
      97                 :            :     // We calculate the estimate assuming independence.  With this assumption,
      98                 :            :     // the estimate is the product of the estimates for the sub-postlists
      99                 :            :     // divided by db_size (n_kids - 1) times.
     100                 :       1421 :     double result = plist[0]->get_termfreq_est();
     101         [ +  + ]:       3502 :     for (size_t i = 1; i < n_kids; ++i) {
     102                 :       2081 :         result = (result * plist[i]->get_termfreq_est()) / db_size;
     103                 :            :     }
     104                 :       1421 :     return static_cast<Xapian::doccount>(result + 0.5);
     105                 :            : }
     106                 :            : 
     107                 :            : TermFreqs
     108                 :         48 : MultiAndPostList::get_termfreq_est_using_stats(
     109                 :            :         const Xapian::Weight::Internal & stats) const
     110                 :            : {
     111                 :            :     LOGCALL(MATCH, TermFreqs, "MultiAndPostList::get_termfreq_est_using_stats", stats);
     112                 :            :     // We calculate the estimate assuming independence.  With this assumption,
     113                 :            :     // the estimate is the product of the estimates for the sub-postlists
     114                 :            :     // divided by db_size (n_kids - 1) times.
     115         [ +  - ]:         48 :     TermFreqs freqs(plist[0]->get_termfreq_est_using_stats(stats));
     116                 :            : 
     117                 :         48 :     double freqest = double(freqs.termfreq);
     118                 :         48 :     double relfreqest = double(freqs.reltermfreq);
     119                 :         48 :     double collfreqest = double(freqs.collfreq);
     120                 :            : 
     121                 :            :     // Our caller should have ensured this.
     122                 :            :     Assert(stats.collection_size);
     123                 :            : 
     124         [ +  + ]:        128 :     for (size_t i = 1; i < n_kids; ++i) {
     125         [ +  - ]:         80 :         freqs = plist[i]->get_termfreq_est_using_stats(stats);
     126                 :            : 
     127                 :            :         // If the collection is empty, freqest should be 0 already, so leave
     128                 :            :         // it alone.
     129                 :         80 :         freqest = (freqest * freqs.termfreq) / stats.collection_size;
     130                 :         80 :         collfreqest = (collfreqest * freqs.collfreq) / stats.total_term_count;
     131                 :            : 
     132                 :            :         // If the rset is empty, relfreqest should be 0 already, so leave
     133                 :            :         // it alone.
     134         [ -  + ]:         80 :         if (stats.rset_size != 0)
     135                 :          0 :             relfreqest = (relfreqest * freqs.reltermfreq) / stats.rset_size;
     136                 :            :     }
     137                 :            : 
     138                 :         48 :     RETURN(TermFreqs(static_cast<Xapian::doccount>(freqest + 0.5),
     139                 :            :                      static_cast<Xapian::doccount>(relfreqest + 0.5),
     140                 :            :                      static_cast<Xapian::termcount>(collfreqest + 0.5)));
     141                 :            : }
     142                 :            : 
     143                 :            : Xapian::docid
     144                 :       4515 : MultiAndPostList::get_docid() const
     145                 :            : {
     146                 :       4515 :     return did;
     147                 :            : }
     148                 :            : 
     149                 :            : double
     150                 :       2114 : MultiAndPostList::get_weight(Xapian::termcount doclen,
     151                 :            :                              Xapian::termcount unique_terms) const
     152                 :            : {
     153                 :            :     Assert(did);
     154                 :       2114 :     double result = 0;
     155         [ +  + ]:       6799 :     for (size_t i = 0; i < n_kids; ++i) {
     156                 :       4685 :         result += plist[i]->get_weight(doclen, unique_terms);
     157                 :            :     }
     158                 :       2114 :     return result;
     159                 :            : }
     160                 :            : 
     161                 :            : bool
     162                 :       5401 : MultiAndPostList::at_end() const
     163                 :            : {
     164                 :       5401 :     return (did == 0);
     165                 :            : }
     166                 :            : 
     167                 :            : double
     168                 :       1232 : MultiAndPostList::recalc_maxweight()
     169                 :            : {
     170                 :       1232 :     max_total = 0.0;
     171         [ +  + ]:       4166 :     for (size_t i = 0; i < n_kids; ++i) {
     172                 :       2934 :         double new_max = plist[i]->recalc_maxweight();
     173                 :       2934 :         max_wt[i] = new_max;
     174                 :       2934 :         max_total += new_max;
     175                 :            :     }
     176                 :       1232 :     return max_total;
     177                 :            : }
     178                 :            : 
     179                 :            : PostList *
     180                 :       5352 : MultiAndPostList::find_next_match(double w_min)
     181                 :            : {
     182                 :            : advanced_plist0:
     183         [ +  + ]:       6064 :     if (plist[0]->at_end()) {
     184                 :       1071 :         did = 0;
     185                 :       1071 :         return NULL;
     186                 :            :     }
     187                 :       4993 :     did = plist[0]->get_docid();
     188         [ +  + ]:      10857 :     for (size_t i = 1; i < n_kids; ++i) {
     189                 :            :         bool valid;
     190         [ +  - ]:       6671 :         check_helper(i, did, w_min, valid);
     191         [ +  + ]:       6671 :         if (!valid) {
     192         [ +  - ]:         15 :             next_helper(0, w_min);
     193                 :        712 :             goto advanced_plist0;
     194                 :            :         }
     195 [ +  - ][ +  + ]:       6656 :         if (plist[i]->at_end()) {
     196                 :         95 :             did = 0;
     197                 :         95 :             return NULL;
     198                 :            :         }
     199         [ +  - ]:       6561 :         Xapian::docid new_did = plist[i]->get_docid();
     200         [ +  + ]:       6561 :         if (new_did != did) {
     201         [ +  - ]:        697 :             skip_to_helper(0, new_did, w_min);
     202                 :        697 :             goto advanced_plist0;
     203                 :            :         }
     204                 :            :     }
     205                 :       5352 :     return NULL;
     206                 :            : }
     207                 :            : 
     208                 :            : PostList *
     209                 :       4739 : MultiAndPostList::next(double w_min)
     210                 :            : {
     211                 :       4739 :     next_helper(0, w_min);
     212                 :       4739 :     return find_next_match(w_min);
     213                 :            : }
     214                 :            : 
     215                 :            : PostList *
     216                 :        613 : MultiAndPostList::skip_to(Xapian::docid did_min, double w_min)
     217                 :            : {
     218                 :        613 :     skip_to_helper(0, did_min, w_min);
     219                 :        613 :     return find_next_match(w_min);
     220                 :            : }
     221                 :            : 
     222                 :            : std::string
     223                 :          0 : MultiAndPostList::get_description() const
     224                 :            : {
     225         [ #  # ]:          0 :     string desc("(");
     226 [ #  # ][ #  # ]:          0 :     desc += plist[0]->get_description();
     227         [ #  # ]:          0 :     for (size_t i = 1; i < n_kids; ++i) {
     228         [ #  # ]:          0 :         desc += " AND ";
     229 [ #  # ][ #  # ]:          0 :         desc += plist[i]->get_description();
     230                 :            :     }
     231         [ #  # ]:          0 :     desc += ')';
     232                 :          0 :     return desc;
     233                 :            : }
     234                 :            : 
     235                 :            : Xapian::termcount
     236                 :         28 : MultiAndPostList::get_wdf() const
     237                 :            : {
     238                 :         28 :     Xapian::termcount totwdf = 0;
     239         [ +  + ]:        112 :     for (size_t i = 0; i < n_kids; ++i) {
     240                 :         84 :         totwdf += plist[i]->get_wdf();
     241                 :            :     }
     242                 :         28 :     return totwdf;
     243                 :            : }
     244                 :            : 
     245                 :            : Xapian::termcount
     246                 :        695 : MultiAndPostList::count_matching_subqs() const
     247                 :            : {
     248                 :        695 :     Xapian::termcount total = 0;
     249         [ +  + ]:       2368 :     for (size_t i = 0; i < n_kids; ++i) {
     250                 :       1673 :         total += plist[i]->count_matching_subqs();
     251                 :            :     }
     252                 :        695 :     return total;
     253                 :            : }
     254                 :            : 
     255                 :            : void
     256                 :          0 : MultiAndPostList::gather_position_lists(OrPositionList* orposlist)
     257                 :            : {
     258         [ #  # ]:          0 :     for (size_t i = 0; i < n_kids; ++i) {
     259                 :          0 :         plist[i]->gather_position_lists(orposlist);
     260                 :            :     }
     261                 :          0 : }

Generated by: LCOV version 1.11