xapian-core/backends/multi/multi_valuelist.cc

   1 /** @file multi_valuelist.cc
   2  * @brief Class for merging ValueList objects from subdatabases.
   3  */
   4 /* Copyright (C) 2007,2008,2009,2011 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 "backends/multivaluelist.h"
  24
  25 #include <xapian/error.h>
  26
  27 #include "omassert.h"
  28
  29 #include <algorithm>
  30
  31 using namespace std;
  32 using Xapian::Internal::intrusive_ptr;
  33
  34 struct SubValueList {
  35     ValueList * valuelist;
  36     unsigned db_idx;
  37
  38     SubValueList(ValueList * vl, unsigned db_idx_)
  39         : valuelist(vl), db_idx(db_idx_) { }
  40
  41     ~SubValueList() {
  42         delete valuelist;
  43     }
  44
  45     void skip_to(Xapian::docid did, size_t multiplier) {
  46         // Translate did from merged docid.
  47         did = (did - db_idx - 2 + multiplier) / multiplier + 1;
  48         valuelist->skip_to(did);
  49     }
  50
  51     Xapian::docid get_docid() const {
  52         return valuelist->get_docid();
  53     }
  54
  55     Xapian::docid get_merged_docid(unsigned multiplier) const {
  56         return (valuelist->get_docid() - 1) * multiplier + db_idx + 1;
  57     }
  58
  59     std::string get_value() const { return valuelist->get_value(); }
  60
  61     void next() {
  62         valuelist->next();
  63     }
  64
  65     bool at_end() const { return valuelist->at_end(); }
  66 };
  67
  68 /// Comparison functor which orders SubValueList* by ascending docid.
  69 struct CompareSubValueListsByDocId {
  70     /// Order by ascending docid.
  71     bool operator()(const SubValueList *a, const SubValueList *b) {
  72         Xapian::docid did_a = a->get_docid();
  73         Xapian::docid did_b = b->get_docid();
  74         if (did_a > did_b) return true;
  75         if (did_a < did_b) return false;
  76         return a->db_idx > b->db_idx;
  77     }
  78 };
  79
  80 template<class CLASS> struct delete_ptr {
  81     void operator()(CLASS *p) { delete p; }
  82 };
  83
  84 MultiValueList::MultiValueList(const vector<intrusive_ptr<Xapian::Database::Internal> > & dbs,
  85                                Xapian::valueno slot_)
  86     : current_docid(0), slot(slot_), multiplier(dbs.size())
  87 {
  88     // The 0 and 1 cases should be handled by our caller.
  89     AssertRel(multiplier, >=, 2);
  90     valuelists.reserve(multiplier);
  91     try {
  92         unsigned db_idx = 0;
  93         vector<intrusive_ptr<Xapian::Database::Internal> >::const_iterator i;
  94         for (i = dbs.begin(); i != dbs.end(); ++i) {
  95             ValueList * vl = (*i)->open_value_list(slot);
  96             valuelists.push_back(new SubValueList(vl, db_idx));
  97             ++db_idx;
  98         }
  99     } catch (...) {
 100         for_each(valuelists.begin(), valuelists.end(), delete_ptr<SubValueList>());
 101         throw;
 102     }
 103 }
 104
 105 MultiValueList::~MultiValueList()
 106 {
 107     for_each(valuelists.begin(), valuelists.end(), delete_ptr<SubValueList>());
 108 }
 109
 110 Xapian::docid
 111 MultiValueList::get_docid() const
 112 {
 113     Assert(!at_end());
 114     return current_docid;
 115 }
 116
 117 std::string
 118 MultiValueList::get_value() const
 119 {
 120     Assert(!at_end());
 121     return valuelists.front()->get_value();
 122 }
 123
 124 Xapian::valueno
 125 MultiValueList::get_valueno() const
 126 {
 127     return slot;
 128 }
 129
 130 bool
 131 MultiValueList::at_end() const
 132 {
 133     return valuelists.empty();
 134 }
 135
 136 void
 137 MultiValueList::next()
 138 {
 139     if (current_docid == 0) {
 140         // Make valuelists into a heap so that the one (or one of the ones) with
 141         // earliest sorting term is at the top of the heap.
 142         vector<SubValueList *>::iterator i = valuelists.begin();
 143         while (i != valuelists.end()) {
 144             (*i)->next();
 145             if ((*i)->at_end()) {
 146                 SubValueList * vl = NULL;
 147                 swap(vl, *i);
 148                 i = valuelists.erase(i);
 149                 delete vl;
 150             } else {
 151                 ++i;
 152             }
 153         }
 154         if (rare(valuelists.empty()))
 155             return;
 156         make_heap(valuelists.begin(), valuelists.end(),
 157                   CompareSubValueListsByDocId());
 158     } else {
 159         // Advance to the next docid.
 160         pop_heap(valuelists.begin(), valuelists.end(),
 161                  CompareSubValueListsByDocId());
 162         SubValueList * vl = valuelists.back();
 163         vl->next();
 164         if (vl->at_end()) {
 165             delete vl;
 166             valuelists.pop_back();
 167             if (valuelists.empty()) return;
 168         } else {
 169             push_heap(valuelists.begin(), valuelists.end(),
 170                       CompareSubValueListsByDocId());
 171         }
 172     }
 173
 174     current_docid = valuelists.front()->get_merged_docid(multiplier);
 175 }
 176
 177 void
 178 MultiValueList::skip_to(Xapian::docid did)
 179 {
 180     // Assume the skip is likely to be a long distance, and rebuild the heap
 181     // from scratch.  FIXME: It would be useful to profile this against an
 182     // approach more like that next() uses if this ever gets heavy use.
 183     vector<SubValueList*>::iterator i = valuelists.begin();
 184     while (i != valuelists.end()) {
 185         (*i)->skip_to(did, multiplier);
 186         if ((*i)->at_end()) {
 187             SubValueList * vl = NULL;
 188             swap(vl, *i);
 189             i = valuelists.erase(i);
 190             delete vl;
 191         } else {
 192             ++i;
 193         }
 194     }
 195
 196     if (valuelists.empty()) return;
 197
 198     make_heap(valuelists.begin(), valuelists.end(), CompareSubValueListsByDocId());
 199
 200     current_docid = valuelists.front()->get_merged_docid(multiplier);
 201 }
 202
 203 bool
 204 MultiValueList::check(Xapian::docid did)
 205 {
 206     // FIXME: just run check on the subvaluelist which would hold that docid.
 207     skip_to(did);
 208     return true;
 209 }
 210
 211 string
 212 MultiValueList::get_description() const
 213 {
 214     return "MultiValueList()"; // FIXME: improve description...
 215 }