LCOV - code coverage report
Current view: top level - matcher - orpositionlist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 24 50 48.0 %
Date: 2019-06-30 05:20:33 Functions: 3 5 60.0 %
Branches: 21 54 38.9 %

           Branch data     Line data    Source code
       1                 :            : /** @file orpositionlist.cc
       2                 :            :  * @brief Merge two PositionList objects using an OR operation.
       3                 :            :  */
       4                 :            : /* Copyright (C) 2007,2010,2016,2017 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 "orpositionlist.h"
      24                 :            : 
      25                 :            : #include "debuglog.h"
      26                 :            : 
      27                 :            : using namespace std;
      28                 :            : 
      29                 :            : Xapian::termcount
      30                 :         56 : OrPositionList::get_approx_size() const
      31                 :            : {
      32                 :            :     LOGCALL(EXPAND, Xapian::termcount, "OrPositionList::get_approx_size", NO_ARGS);
      33                 :            :     // This is actually the upper bound, but generally there's only one term
      34                 :            :     // at each position, so it'll usually be correct too.
      35                 :         56 :     Xapian::termcount size = 0;
      36 [ +  - ][ +  + ]:        182 :     for (auto pl : pls) size += pl->get_approx_size();
      37                 :         56 :     RETURN(size);
      38                 :            : }
      39                 :            : 
      40                 :            : Xapian::termpos
      41                 :          0 : OrPositionList::back() const
      42                 :            : {
      43                 :            :     LOGCALL(EXPAND, Xapian::termpos, "OrPositionList::back", NO_ARGS);
      44                 :          0 :     Xapian::termpos result = 0;
      45         [ #  # ]:          0 :     for (auto pl : pls) {
      46 [ #  # ][ #  # ]:          0 :         result = max(result, pl->back());
      47                 :            :     }
      48                 :          0 :     RETURN(result);
      49                 :            : }
      50                 :            : 
      51                 :            : Xapian::termpos
      52                 :        252 : OrPositionList::get_position() const
      53                 :            : {
      54                 :            :     LOGCALL(EXPAND, Xapian::termpos, "OrPositionList::get_position", NO_ARGS);
      55                 :        252 :     RETURN(current_pos);
      56                 :            : }
      57                 :            : 
      58                 :            : // PositionList::next() is actually rarely used - ExactPhrasePostList will
      59                 :            : // never call it, while PhrasePostList will only call it once for the first
      60                 :            : // subquery and NearPostList will call it to start subqueries if we're near
      61                 :            : // the start of the document, and also if a candidate match has two subqueries
      62                 :            : // at the same position.
      63                 :            : bool
      64                 :          0 : OrPositionList::next()
      65                 :            : {
      66                 :            :     LOGCALL(EXPAND, bool, "OrPositionList::next", NO_ARGS);
      67                 :          0 :     bool first = current.empty();
      68         [ #  # ]:          0 :     if (first) current.resize(pls.size());
      69                 :          0 :     Xapian::termpos old_pos = current_pos;
      70                 :          0 :     current_pos = Xapian::termpos(-1);
      71                 :          0 :     size_t j = 0;
      72         [ #  # ]:          0 :     for (size_t i = 0; i != pls.size(); ++i) {
      73                 :          0 :         PositionList* pl = pls[i];
      74                 :            :         Xapian::termpos pos;
      75 [ #  # ][ #  # ]:          0 :         if (first || current[i] <= old_pos) {
                 [ #  # ]
      76 [ #  # ][ #  # ]:          0 :             if (!pl->next())
      77                 :          0 :                 continue;
      78         [ #  # ]:          0 :             pos = pl->get_position();
      79                 :            :         } else {
      80                 :          0 :             pos = current[i];
      81                 :            :         }
      82         [ #  # ]:          0 :         current_pos = min(current_pos, pos);
      83                 :          0 :         current[j] = pos;
      84         [ #  # ]:          0 :         if (i != j) pls[j] = pls[i];
      85                 :          0 :         ++j;
      86                 :            :     }
      87                 :          0 :     pls.resize(j);
      88                 :          0 :     RETURN(j != 0);
      89                 :            : }
      90                 :            : 
      91                 :            : // A min-heap seems like an obvious optimisation here, but is only useful when
      92                 :            : // handling clumps of terms - in particular when skip_to() advances all the
      93                 :            : // sublists, the heap doesn't help (but we have the cost of rebuilding it, or N
      94                 :            : // pop+push calls which has a worse complexity than rebuilding).
      95                 :            : bool
      96                 :        119 : OrPositionList::skip_to(Xapian::termpos termpos)
      97                 :            : {
      98                 :            :     LOGCALL(EXPAND, bool, "OrPositionList::skip_to", termpos);
      99                 :        119 :     bool first = current.empty();
     100 [ +  + ][ -  + ]:        119 :     if (!first && termpos <= current_pos)
     101                 :          0 :         RETURN(true);
     102         [ +  + ]:        119 :     if (first) current.resize(pls.size());
     103                 :        119 :     current_pos = Xapian::termpos(-1);
     104                 :        119 :     size_t j = 0;
     105         [ +  + ]:        385 :     for (size_t i = 0; i != pls.size(); ++i) {
     106                 :        266 :         PositionList* pl = pls[i];
     107                 :            :         Xapian::termpos pos;
     108 [ +  + ][ +  - ]:        266 :         if (first || termpos > current[i]) {
                 [ +  - ]
     109 [ +  - ][ +  + ]:        266 :             if (!pl->skip_to(termpos))
     110                 :         21 :                 continue;
     111         [ +  - ]:        245 :             pos = pl->get_position();
     112                 :            :         } else {
     113                 :          0 :             pos = current[i];
     114                 :            :         }
     115         [ +  - ]:        245 :         current_pos = min(current_pos, pos);
     116                 :        245 :         current[j] = pos;
     117         [ +  + ]:        245 :         if (i != j) pls[j] = pls[i];
     118                 :        245 :         ++j;
     119                 :            :     }
     120                 :        119 :     pls.resize(j);
     121                 :        119 :     RETURN(j != 0);
     122                 :            : }

Generated by: LCOV version 1.11