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