LCOV - code coverage report
Current view: top level - backends/multi - multi_valuelist.cc (source / functions) Hit Total Coverage
Test: Test Coverage for xapian-core 954b5873a738 Lines: 63 66 95.5 %
Date: 2019-06-30 05:20:33 Functions: 10 11 90.9 %
Branches: 37 50 74.0 %

           Branch data     Line data    Source code
       1                 :            : /** @file multi_valuelist.cc
       2                 :            :  * @brief Class for merging ValueList objects from subdatabases.
       3                 :            :  */
       4                 :            : /* Copyright (C) 2007,2008,2009,2011,2017,2018 Olly Betts
       5                 :            :  *
       6                 :            :  * This program is free software; you can redistribute it and/or modify
       7                 :            :  * it under the terms of the GNU General Public License as published by
       8                 :            :  * the Free Software Foundation; either version 2 of the License, or
       9                 :            :  * (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 "multi_valuelist.h"
      24                 :            : 
      25                 :            : #include <xapian/error.h>
      26                 :            : 
      27                 :            : #include "heap.h"
      28                 :            : #include "omassert.h"
      29                 :            : 
      30                 :            : #include <algorithm>
      31                 :            : 
      32                 :            : using namespace std;
      33                 :            : using Xapian::Internal::intrusive_ptr;
      34                 :            : 
      35                 :            : /// Comparison functor which orders SubValueList* by ascending docid.
      36                 :            : struct CompareSubValueListsByDocId {
      37                 :            :     /// Order by ascending docid.
      38                 :      26745 :     bool operator()(const SubValueList *a, const SubValueList *b) const {
      39                 :      26745 :         Xapian::docid did_a = a->get_docid();
      40                 :      26745 :         Xapian::docid did_b = b->get_docid();
      41         [ +  + ]:      26745 :         if (did_a > did_b) return true;
      42         [ +  + ]:      23365 :         if (did_a < did_b) return false;
      43                 :      13958 :         return a->shard > b->shard;
      44                 :            :     }
      45                 :            : };
      46                 :            : 
      47                 :        250 : MultiValueList::MultiValueList(size_t n_shards_,
      48                 :            :                                SubValueList** valuelists_,
      49                 :            :                                Xapian::valueno slot_)
      50                 :            :     : count(n_shards_),
      51                 :            :       valuelists(valuelists_),
      52                 :            :       slot(slot_),
      53                 :        250 :       n_shards(n_shards_)
      54                 :            : {
      55                 :        250 : }
      56                 :            : 
      57                 :        750 : MultiValueList::~MultiValueList()
      58                 :            : {
      59         [ +  + ]:        256 :     while (count)
      60         [ +  - ]:          6 :         delete valuelists[--count];
      61         [ +  - ]:        250 :     delete [] valuelists;
      62         [ -  + ]:        500 : }
      63                 :            : 
      64                 :            : Xapian::docid
      65                 :      26624 : MultiValueList::get_docid() const
      66                 :            : {
      67                 :            :     Assert(!at_end());
      68                 :      26624 :     return current_docid;
      69                 :            : }
      70                 :            : 
      71                 :            : std::string
      72                 :      26615 : MultiValueList::get_value() const
      73                 :            : {
      74                 :            :     Assert(!at_end());
      75                 :      26615 :     return valuelists[0]->get_value();
      76                 :            : }
      77                 :            : 
      78                 :            : Xapian::valueno
      79                 :      26548 : MultiValueList::get_valueno() const
      80                 :            : {
      81                 :      26548 :     return slot;
      82                 :            : }
      83                 :            : 
      84                 :            : bool
      85                 :      27091 : MultiValueList::at_end() const
      86                 :            : {
      87                 :      27091 :     return count == 0;
      88                 :            : }
      89                 :            : 
      90                 :            : void
      91                 :        307 : MultiValueList::next()
      92                 :            : {
      93         [ +  + ]:        307 :     if (current_docid == 0) {
      94                 :            :         // Make valuelists into a heap so that the one with the earliest
      95                 :            :         // sorting docid is at the top of the heap.
      96                 :        250 :         size_t j = 0;
      97         [ +  + ]:        748 :         for (size_t i = 0; i != count; ++i) {
      98                 :        499 :             valuelists[i]->next();
      99         [ +  + ]:        498 :             if (valuelists[i]->at_end()) {
     100         [ +  - ]:          5 :                 delete valuelists[i];
     101                 :          5 :                 valuelists[i] = 0;
     102                 :            :             } else {
     103         [ -  + ]:        493 :                 if (i != j)
     104                 :          0 :                     swap(valuelists[i], valuelists[j]);
     105                 :        493 :                 ++j;
     106                 :            :             }
     107                 :            :         }
     108                 :        249 :         count = j;
     109         [ +  + ]:        249 :         if (rare(count == 0))
     110                 :          2 :             return;
     111                 :            : 
     112                 :            :         Heap::make(valuelists, valuelists + count,
     113         [ +  - ]:        247 :                    CompareSubValueListsByDocId());
     114                 :            :     } else {
     115                 :            :         // Advance to the next docid.
     116                 :         57 :         SubValueList * vl = valuelists[0];
     117                 :         57 :         vl->next();
     118         [ +  + ]:         57 :         if (vl->at_end()) {
     119                 :            :             Heap::pop(valuelists, valuelists + count,
     120         [ +  - ]:         33 :                       CompareSubValueListsByDocId());
     121         [ +  - ]:         33 :             delete vl;
     122         [ +  + ]:         33 :             if (--count == 0)
     123                 :         19 :                 return;
     124                 :            :         } else {
     125                 :            :             Heap::replace(valuelists, valuelists + count,
     126         [ +  - ]:         24 :                           CompareSubValueListsByDocId());
     127                 :            :         }
     128                 :            :     }
     129                 :            : 
     130                 :        306 :     current_docid = valuelists[0]->get_merged_docid(n_shards);
     131                 :            : }
     132                 :            : 
     133                 :            : void
     134                 :      26785 : MultiValueList::skip_to(Xapian::docid did)
     135                 :            : {
     136                 :            :     // Assume the skip is likely to be a long distance, and rebuild the heap
     137                 :            :     // from scratch.  FIXME: It would be useful to profile this against an
     138                 :            :     // approach more like that next() uses if this ever gets heavy use.
     139                 :      26785 :     size_t j = 0;
     140         [ +  + ]:      80277 :     for (size_t i = 0; i != count; ++i) {
     141                 :      53492 :         valuelists[i]->skip_to(did, n_shards);
     142         [ +  + ]:      53492 :         if (valuelists[i]->at_end()) {
     143         [ +  - ]:        456 :             delete valuelists[i];
     144                 :        456 :             valuelists[i] = 0;
     145                 :            :         } else {
     146         [ +  + ]:      53036 :             if (i != j)
     147                 :         40 :                 swap(valuelists[i], valuelists[j]);
     148                 :      53036 :             ++j;
     149                 :            :         }
     150                 :            :     }
     151                 :      26785 :     count = j;
     152         [ +  + ]:      26785 :     if (rare(count == 0))
     153                 :      26785 :         return;
     154                 :            : 
     155         [ +  - ]:      26560 :     Heap::make(valuelists, valuelists + count, CompareSubValueListsByDocId());
     156                 :            : 
     157                 :      26560 :     current_docid = valuelists[0]->get_merged_docid(n_shards);
     158                 :            : }
     159                 :            : 
     160                 :            : bool
     161                 :      10044 : MultiValueList::check(Xapian::docid did)
     162                 :            : {
     163                 :            :     // FIXME: just run check on the subvaluelist which would hold that docid.
     164                 :      10044 :     skip_to(did);
     165                 :      10044 :     return true;
     166                 :            : }
     167                 :            : 
     168                 :            : string
     169                 :          0 : MultiValueList::get_description() const
     170                 :            : {
     171         [ #  # ]:          0 :     return "MultiValueList()"; // FIXME: improve description...
     172                 :            : }

Generated by: LCOV version 1.11