Branch data Line data Source code
1 : : /** @file esetinternal.cc
2 : : * @brief Xapian::ESet::Internal class
3 : : */
4 : : /* Copyright (C) 2008,2010 Olly Betts
5 : : * Copyright (C) 2011 Action Without Borders
6 : : *
7 : : * This program is free software; you can redistribute it and/or modify
8 : : * it under the terms of the GNU General Public License as published by
9 : : * the Free Software Foundation; either version 2 of the License, or
10 : : * (at your option) any later version.
11 : : *
12 : : * This program is distributed in the hope that it will be useful,
13 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 : : * GNU General Public License for more details.
16 : : *
17 : : * You should have received a copy of the GNU General Public License
18 : : * along with this program; if not, write to the Free Software
19 : : * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 : : */
21 : :
22 : : #include <config.h>
23 : :
24 : : #include "esetinternal.h"
25 : :
26 : : #include "xapian/enquire.h"
27 : : #include "xapian/expanddecider.h"
28 : : #include "database.h"
29 : : #include "debuglog.h"
30 : : #include "omenquireinternal.h"
31 : : #include "expandweight.h"
32 : : #include "omassert.h"
33 : : #include "ortermlist.h"
34 : : #include "str.h"
35 : : #include "termlist.h"
36 : :
37 : : #include "autoptr.h"
38 : : #include <set>
39 : : #include <string>
40 : : #include <vector>
41 : :
42 : : using namespace std;
43 : :
44 : : namespace Xapian {
45 : :
46 : : string
47 : 0 : Internal::ExpandTerm::get_description() const
48 : : {
49 : 0 : string desc("ExpandTerm(");
50 : 0 : desc += str(wt);
51 : 0 : desc += ", ";
52 : 0 : desc += term;
53 : 0 : desc += ')';
54 : 0 : return desc;
55 : : }
56 : :
57 : : template<class CLASS> struct delete_ptr {
58 [ # # ]: 0 : void operator()(CLASS *p) { delete p; }
59 : : };
60 : :
61 : : struct CompareTermListSizeAscending {
62 : 160 : bool operator()(const TermList *a, const TermList *b) {
63 : 160 : return a->get_approx_size() > b->get_approx_size();
64 : : }
65 : : };
66 : :
67 : : /** Build a tree of binary TermList objects like QueryOptimiser does for
68 : : * OrPostList objects.
69 : : */
70 : : static TermList *
71 : 186 : build_termlist_tree(const Xapian::Database &db, const RSet & rset)
72 : : {
73 : : Assert(!rset.empty());
74 : :
75 : 186 : const set<Xapian::docid> & docids = rset.internal->get_items();
76 : :
77 : 186 : vector<TermList*> termlists;
78 : 186 : termlists.reserve(docids.size());
79 : :
80 : : try {
81 : 186 : const size_t multiplier = db.internal.size();
82 : 186 : set<Xapian::docid>::const_iterator i;
83 [ + + ]: 532 : for (i = docids.begin(); i != docids.end(); ++i) {
84 : 346 : Xapian::docid realdid = (*i - 1) / multiplier + 1;
85 : 346 : Xapian::doccount dbnumber = (*i - 1) % multiplier;
86 : :
87 : : // Push NULL first to avoid leaking the new TermList if push_back()
88 : : // throws.
89 : 346 : termlists.push_back(0);
90 : 346 : termlists.back() = db.internal[dbnumber]->open_term_list(realdid);
91 : : }
92 : :
93 : : Assert(!termlists.empty());
94 [ + + ]: 186 : if (termlists.size() == 1) return termlists[0];
95 : :
96 : : // Make termlists into a heap so that the longest termlist is at the
97 : : // top of the heap.
98 : : make_heap(termlists.begin(), termlists.end(),
99 : 160 : CompareTermListSizeAscending());
100 : :
101 : : // Now build a tree of binary TermList objects. The algorithm used to
102 : : // build the tree is like that used to build an optimal Huffman coding
103 : : // tree. If we called next() repeatedly, this arrangement would
104 : : // minimise the number of method calls. Generally we don't actually do
105 : : // that, but this arrangement is still likely to be a good one, and it
106 : : // does minimise the work in the worst case.
107 : 0 : while (true) {
108 : : AssertRel(termlists.size(), >=, 2);
109 : : // We build the tree such that at each branch:
110 : : //
111 : : // l.get_approx_size() >= r.get_approx_size()
112 : : //
113 : : // We do this so that the OrTermList class can be optimised
114 : : // assuming that this is the case.
115 : 160 : TermList * r = termlists.front();
116 : : pop_heap(termlists.begin(), termlists.end(),
117 : 160 : CompareTermListSizeAscending());
118 : 160 : termlists.pop_back();
119 : 160 : TermList * l = termlists.front();
120 : :
121 : 160 : TermList * pl = new OrTermList(l, r);
122 : :
123 [ + - ]: 160 : if (termlists.size() == 1) return pl;
124 : :
125 : : pop_heap(termlists.begin(), termlists.end(),
126 : 0 : CompareTermListSizeAscending());
127 : 0 : termlists.back() = pl;
128 : : push_heap(termlists.begin(), termlists.end(),
129 : 0 : CompareTermListSizeAscending());
130 : : }
131 : 0 : } catch (...) {
132 : 0 : for_each(termlists.begin(), termlists.end(), delete_ptr<TermList>());
133 : 0 : throw;
134 : 186 : }
135 : : }
136 : :
137 : : void
138 : 186 : ESet::Internal::expand(Xapian::termcount max_esize,
139 : : const Xapian::Database & db,
140 : : const RSet & rset,
141 : : const Xapian::ExpandDecider * edecider,
142 : : const Xapian::Internal::ExpandWeight & eweight,
143 : : Xapian::weight min_wt)
144 : : {
145 : : LOGCALL_VOID(EXPAND, "ESet::Internal::expand", max_esize | db | rset | edecider | eweight);
146 : : // These two cases are handled by our caller.
147 : : Assert(max_esize);
148 : : Assert(!rset.empty());
149 : : // This method should only be called once for a given ESet::Internal, so
150 : : // check we're empty.
151 : : Assert(ebound == 0);
152 : : Assert(items.empty());
153 : :
154 : 186 : AutoPtr<TermList> tree(build_termlist_tree(db, rset));
155 : : Assert(tree.get());
156 : :
157 : 186 : bool is_heap = false;
158 : 9290 : while (true) {
159 : : // See if the root needs replacing.
160 : 9476 : TermList * new_root = tree->next();
161 [ + + ]: 9476 : if (new_root) {
162 : : LOGLINE(EXPAND, "Replacing the root of the termlist tree");
163 : 160 : tree.reset(new_root);
164 : : }
165 : :
166 [ + + ]: 9476 : if (tree->at_end()) break;
167 : :
168 : 9290 : string term = tree->get_termname();
169 : :
170 : : // If there's an ExpandDecider, see if it accepts the term.
171 [ + + + + ]: 9290 : if (edecider && !(*edecider)(term)) continue;
[ + + ]
172 : :
173 : 8679 : ++ebound;
174 : :
175 : 8679 : Xapian::weight wt = eweight.get_weight(tree.get(), term);
176 : : // If the weights are equal, we prefer the lexically smaller term and
177 : : // so we use "<=" not "<" here.
178 [ + + ]: 8679 : if (wt <= min_wt) continue;
179 : :
180 : 4636 : items.push_back(Xapian::Internal::ExpandTerm(wt, term));
181 : :
182 : : // The candidate ESet is overflowing, so remove the worst element in it
183 : : // using a min-heap.
184 [ + + ]: 4636 : if (items.size() > max_esize) {
185 [ + + ]: 272 : if (rare(!is_heap)) {
186 : 65 : is_heap = true;
187 : 65 : make_heap(items.begin(), items.end());
188 : : } else {
189 : 207 : push_heap(items.begin(), items.end());
190 : : }
191 : 272 : pop_heap(items.begin(), items.end());
192 : 272 : items.pop_back();
193 : 4636 : min_wt = items.front().wt;
194 : : }
195 : : }
196 : :
197 : : // Now sort the contents of the new ESet.
198 [ + + ]: 186 : if (is_heap) {
199 : 65 : sort_heap(items.begin(), items.end());
200 : : } else {
201 : 121 : sort(items.begin(), items.end());
202 : 186 : }
203 : 186 : }
204 : :
205 : : string
206 : 1 : ESet::Internal::get_description() const
207 : : {
208 : 1 : string desc("ESet::Internal(ebound=");
209 : 1 : desc += str(ebound);
210 : :
211 : 1 : vector<Xapian::Internal::ExpandTerm>::const_iterator i;
212 [ - + ]: 1 : for (i = items.begin(); i != items.end(); ++i) {
213 : 0 : desc += ", ";
214 : 0 : desc += i->get_description();
215 : : }
216 : 1 : desc += ')';
217 : :
218 : 0 : return desc;
219 : : }
220 : :
221 : : }
|
