xapian-core  1.4.25
multi_valuelist.cc
Go to the documentation of this file.
1 
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 
24 
25 #include <xapian/error.h>
26 
27 #include "omassert.h"
28 
29 #include <algorithm>
30 
31 using namespace std;
33 
34 struct SubValueList {
36  unsigned db_idx;
37 
38  SubValueList(ValueList * vl, unsigned db_idx_)
39  : valuelist(vl), db_idx(db_idx_) { }
40 
42  delete valuelist;
43  }
44 
45  void skip_to(Xapian::docid did, size_t multiplier) {
46  // Translate did from merged docid.
47  did = (did - 1) / multiplier + 1 + ((did - 1) % multiplier > db_idx);
48  valuelist->skip_to(did);
49  }
50 
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 
71  bool operator()(const SubValueList *a, const SubValueList *b) const {
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) const { delete p; }
82 };
83 
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 
106 {
107  for_each(valuelists.begin(), valuelists.end(), delete_ptr<SubValueList>());
108 }
109 
112 {
113  Assert(!at_end());
114  return current_docid;
115 }
116 
117 std::string
119 {
120  Assert(!at_end());
121  return valuelists.front()->get_value();
122 }
123 
126 {
127  return slot;
128 }
129 
130 bool
132 {
133  return valuelists.empty();
134 }
135 
136 void
138 {
139  if (current_docid == 0) {
140  // Make valuelists into a heap so that the one with the earliest
141  // sorting docid 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(),
158  } else {
159  // Advance to the next docid.
160  pop_heap(valuelists.begin(), valuelists.end(),
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(),
171  }
172  }
173 
174  current_docid = valuelists.front()->get_merged_docid(multiplier);
175 }
176 
177 void
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
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
213 {
214  return "MultiValueList()"; // FIXME: improve description...
215 }
#define Assert(COND)
Definition: omassert.h:122
ValueList * valuelist
void skip_to(Xapian::docid did, size_t multiplier)
Xapian::docid current_docid
Current docid (or 0 if we haven&#39;t started yet).
bool at_end() const
Return true if the current position is past the last entry in this list.
virtual bool at_end() const =0
Return true if the current position is past the last entry in this list.
#define AssertRel(A, REL, B)
Definition: omassert.h:123
Xapian::valueno slot
The value slot we&#39;re iterating over.
STL namespace.
Xapian::valueno get_valueno() const
Return the value slot for the current position/this iterator.
#define rare(COND)
Definition: config.h:565
SubValueList(ValueList *vl, unsigned db_idx_)
MultiValueList(const MultiValueList &)
Don&#39;t allow copying.
std::string get_value() const
Hierarchy of classes which Xapian can throw as exceptions.
Xapian::docid get_merged_docid(unsigned multiplier) const
Comparison functor which orders SubValueList* by ascending docid.
Xapian::docid get_docid() const
Return the docid at the current position.
std::string get_value() const
Return the value at the current position.
Class for merging ValueList objects from subdatabases.
bool check(Xapian::docid did)
Check if the specified docid occurs in this valuestream.
void skip_to(Xapian::docid)
Skip forward to the specified docid.
bool operator()(const SubValueList *a, const SubValueList *b) const
Order by ascending docid.
virtual Xapian::docid get_docid() const =0
Return the docid at the current position.
~MultiValueList()
Destructor.
virtual void next()=0
Advance the current position to the next document in the value stream.
Abstract base class for value streams.
Definition: valuelist.h:31
void next()
Advance the current position to the next document in the value stream.
bool at_end() const
virtual std::string get_value() const =0
Return the value at the current position.
std::string get_description() const
Return a string description of this object.
unsigned valueno
The number for a value slot in a document.
Definition: types.h:108
std::vector< SubValueList * > valuelists
Vector of sub-valuelists which we use as a heap.
Various assertion macros.
unsigned XAPIAN_DOCID_BASE_TYPE docid
A unique identifier for a document.
Definition: types.h:52
virtual void skip_to(Xapian::docid)=0
Skip forward to the specified docid.
A smart pointer that uses intrusive reference counting.
Definition: intrusive_ptr.h:81
Xapian::docid get_docid() const
void operator()(CLASS *p) const