LCOV - code coverage report
Current view: top level - api - terminfo.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 53 58 91.4 %
Date: 2019-06-30 05:20:33 Functions: 4 4 100.0 %
Branches: 32 46 69.6 %

           Branch data     Line data    Source code
       1                 :            : /** @file terminfo.cc
       2                 :            :  * @brief Metadata for a term in a document
       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 "terminfo.h"
      24                 :            : 
      25                 :            : #include "omassert.h"
      26                 :            : 
      27                 :            : #include <algorithm>
      28                 :            : 
      29                 :            : using namespace std;
      30                 :            : 
      31                 :            : void
      32                 :          5 : TermInfo::merge() const
      33                 :            : {
      34                 :            :     Assert(!is_deleted());
      35                 :            :     inplace_merge(positions.begin(),
      36                 :          5 :                   positions.begin() + split,
      37                 :         10 :                   positions.end());
      38                 :          5 :     split = 0;
      39                 :          5 : }
      40                 :            : 
      41                 :            : bool
      42                 :    1296599 : TermInfo::add_position(Xapian::termcount wdf_inc, Xapian::termpos termpos)
      43                 :            : {
      44         [ +  + ]:    1296599 :     if (rare(is_deleted())) {
      45                 :         11 :         wdf = wdf_inc;
      46                 :         11 :         split = 0;
      47                 :         11 :         positions.push_back(termpos);
      48                 :         11 :         return true;
      49                 :            :     }
      50                 :            : 
      51                 :    1296588 :     wdf += wdf_inc;
      52                 :            : 
      53                 :            :     // Optimise the common case of adding positions in ascending order.
      54         [ +  + ]:    1296588 :     if (positions.empty()) {
      55                 :     432277 :         positions.push_back(termpos);
      56                 :     432277 :         return false;
      57                 :            :     }
      58         [ +  + ]:     864311 :     if (termpos > positions.back()) {
      59         [ +  + ]:     864258 :         if (split) {
      60                 :            :             // Check for duplicate before split.
      61                 :            :             auto i = lower_bound(positions.cbegin(),
      62                 :         20 :                                  positions.cbegin() + split,
      63                 :         20 :                                  termpos);
      64 [ +  - ][ -  + ]:         20 :             if (i != positions.cbegin() + split && *i == termpos)
                 [ -  + ]
      65                 :         20 :                 return false;
      66                 :            :         }
      67                 :     864258 :         positions.push_back(termpos);
      68                 :     864258 :         return false;
      69                 :            :     }
      70                 :            : 
      71         [ +  + ]:         53 :     if (termpos == positions.back()) {
      72                 :            :         // Duplicate of last entry.
      73                 :         48 :         return false;
      74                 :            :     }
      75                 :            : 
      76         [ -  + ]:          5 :     if (split > 0) {
      77                 :            :         // We could merge in the new entry at the same time, but that seems to
      78                 :            :         // make things much more complex for minor gains.
      79                 :          0 :         merge();
      80                 :            :     }
      81                 :            : 
      82                 :            :     // We keep positions sorted, so use lower_bound() which can binary chop to
      83                 :            :     // find the entry.
      84                 :          5 :     auto i = lower_bound(positions.cbegin(), positions.cend(), termpos);
      85                 :            :     // Add unless termpos is already in the list.
      86 [ +  - ][ +  - ]:          5 :     if (i == positions.cend() || *i != termpos) {
                 [ +  - ]
      87                 :          5 :         auto new_split = positions.size();
      88                 :            :         if (sizeof(split) < sizeof(Xapian::termpos)) {
      89                 :            :             if (rare(new_split > numeric_limits<decltype(split)>::max())) {
      90                 :            :                 // The split point would be beyond the size of the type used to
      91                 :            :                 // hold it, which is really unlikely if that type is 32-bit.
      92                 :            :                 // Just insert the old way in this case.
      93                 :            :                 positions.insert(i, termpos);
      94                 :            :                 return false;
      95                 :            :             }
      96                 :            :         } else {
      97                 :            :             // This assertion should always be true because we shouldn't have
      98                 :            :             // duplicate entries and the split point can't be after the final
      99                 :            :             // entry.
     100                 :            :             AssertRel(new_split, <=, numeric_limits<decltype(split)>::max());
     101                 :            :         }
     102                 :          5 :         split = new_split;
     103                 :          5 :         positions.push_back(termpos);
     104                 :            :     }
     105                 :          5 :     return false;
     106                 :            : }
     107                 :            : 
     108                 :            : bool
     109                 :         14 : TermInfo::remove_position(Xapian::termpos termpos)
     110                 :            : {
     111                 :            :     Assert(!is_deleted());
     112                 :            : 
     113         [ -  + ]:         14 :     if (rare(positions.empty()))
     114                 :          0 :         return false;
     115                 :            : 
     116                 :            :     // Special case removing the final position, which we can handle in O(1).
     117         [ +  + ]:         14 :     if (positions.back() == termpos) {
     118                 :         10 :         positions.pop_back();
     119         [ +  - ]:         10 :         if (split == positions.size()) {
     120                 :         10 :             split = 0;
     121                 :            :             // We removed the only entry from after the split.
     122                 :            :         }
     123                 :         10 :         return true;
     124                 :            :     }
     125                 :            : 
     126         [ -  + ]:          4 :     if (split > 0) {
     127                 :            :         // We could remove the requested entry at the same time, but that seems
     128                 :            :         // fiddly to do.
     129                 :          0 :         merge();
     130                 :            :     }
     131                 :            : 
     132                 :            :     // We keep positions sorted, so use lower_bound() which can binary chop to
     133                 :            :     // find the entry.
     134                 :          4 :     auto i = lower_bound(positions.cbegin(), positions.cend(), termpos);
     135 [ +  - ][ -  + ]:          4 :     if (i == positions.cend() || *i != termpos) {
                 [ -  + ]
     136                 :            :         // Not there.
     137                 :          0 :         return false;
     138                 :            :     }
     139                 :          4 :     positions.erase(i);
     140                 :          4 :     return true;
     141                 :            : }
     142                 :            : 
     143                 :            : Xapian::termpos
     144                 :          7 : TermInfo::remove_positions(Xapian::termpos termpos_first,
     145                 :            :                            Xapian::termpos termpos_last)
     146                 :            : {
     147                 :            :     Assert(!is_deleted());
     148                 :            : 
     149         [ -  + ]:          7 :     if (split > 0) {
     150                 :            :         // We could remove the requested entries at the same time, but that
     151                 :            :         // seems fiddly to do.
     152                 :          0 :         merge();
     153                 :            :     }
     154                 :            : 
     155                 :            :     // Find the range [i, j) that the specified termpos range maps to.  Use
     156                 :            :     // binary chop to search, since this is a sorted list.
     157                 :          7 :     auto i = lower_bound(positions.cbegin(), positions.cend(), termpos_first);
     158 [ +  + ][ +  + ]:          7 :     if (i == positions.cend() || *i > termpos_last) {
                 [ +  + ]
     159                 :          2 :         return 0;
     160                 :            :     }
     161                 :          5 :     auto j = upper_bound(i, positions.cend(), termpos_last);
     162                 :          5 :     size_t size_before = positions.size();
     163                 :          5 :     positions.erase(i, j);
     164                 :          5 :     return Xapian::termpos(size_before - positions.size());
     165                 :            : }

Generated by: LCOV version 1.11