Branch data Line data Source code
1 : : /** @file multiandpostlist.cc
2 : : * @brief N-way AND postlist
3 : : */
4 : : /* Copyright (C) 2007,2009 Olly Betts
5 : : * Copyright (C) 2009 Lemur Consulting Ltd
6 : : *
7 : : * This program is free software; you can redistribute it and/or
8 : : * modify it under the terms of the GNU General Public License as
9 : : * published by the Free Software Foundation; either version 2 of the
10 : : * License, or (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 "multiandpostlist.h"
25 : : #include "omassert.h"
26 : : #include "debuglog.h"
27 : :
28 : : void
29 : 1620 : MultiAndPostList::allocate_plist_and_max_wt()
30 : : {
31 : 1620 : plist = new PostList * [n_kids];
32 : : try {
33 : 1620 : max_wt = new Xapian::weight [n_kids];
34 : 0 : } catch (...) {
35 [ # # ]: 0 : delete [] plist;
36 : 0 : plist = NULL;
37 : 0 : throw;
38 : : }
39 : 1620 : }
40 : :
41 : 1620 : MultiAndPostList::~MultiAndPostList()
42 : : {
43 [ + - ][ # # ]: 1620 : if (plist) {
[ # # ]
44 [ + + ][ # # ]: 5616 : for (size_t i = 0; i < n_kids; ++i) {
[ # # ]
45 [ + - ][ # # ]: 3996 : delete plist[i];
[ # # ]
46 : : }
47 [ + - ][ # # ]: 1620 : delete [] plist;
[ # # ]
48 : : }
49 [ + - ][ # # ]: 1620 : delete [] max_wt;
[ # # ]
50 [ + - ][ # # ]: 1620 : }
[ # # ]
51 : :
52 : : Xapian::doccount
53 : 601 : MultiAndPostList::get_termfreq_min() const
54 : : {
55 : : // The number of matching documents is minimised when we have the minimum
56 : : // number of matching documents from each sub-postlist, and these are
57 : : // maximally disjoint.
58 : 601 : Xapian::doccount sum = plist[0]->get_termfreq_min();
59 [ + + ]: 601 : if (sum) {
60 [ + + ]: 662 : for (size_t i = 1; i < n_kids; ++i) {
61 : 496 : Xapian::doccount sum_old = sum;
62 : 496 : sum += plist[i]->get_termfreq_min();
63 : : // If sum < sum_old, the calculation overflowed and the true sum
64 : : // must be > db_size. Since we added a value <= db_size,
65 : : // subtracting db_size must un-overflow us.
66 [ + - + + ]: 496 : if (sum >= sum_old && sum <= db_size) {
67 : : // It's possible there's no overlap.
68 : 330 : return 0;
69 : : }
70 : 166 : sum -= db_size;
71 : : }
72 : : AssertRelParanoid(sum,<=,MultiAndPostList::get_termfreq_est());
73 : : }
74 : 601 : return sum;
75 : : }
76 : :
77 : : Xapian::doccount
78 : 1539 : MultiAndPostList::get_termfreq_max() const
79 : : {
80 : : // We can't match more documents than the least of our sub-postlists.
81 : 1539 : Xapian::doccount result = plist[0]->get_termfreq_max();
82 [ + + ]: 3834 : for (size_t i = 1; i < n_kids; ++i) {
83 : 2295 : Xapian::doccount tf = plist[i]->get_termfreq_max();
84 [ + + ]: 2295 : if (tf < result) result = tf;
85 : : }
86 : 1539 : return result;
87 : : }
88 : :
89 : : Xapian::doccount
90 : 2157 : MultiAndPostList::get_termfreq_est() const
91 : : {
92 : : // We calculate the estimate assuming independence. With this assumption,
93 : : // the estimate is the product of the estimates for the sub-postlists
94 : : // divided by db_size (n_kids - 1) times.
95 : 2157 : double result(plist[0]->get_termfreq_est());
96 [ + + ]: 5378 : for (size_t i = 1; i < n_kids; ++i) {
97 : 3221 : result = (result * plist[i]->get_termfreq_est()) / db_size;
98 : : }
99 : 2157 : return static_cast<Xapian::doccount>(result + 0.5);
100 : : }
101 : :
102 : : TermFreqs
103 : 96 : MultiAndPostList::get_termfreq_est_using_stats(
104 : : const Xapian::Weight::Internal & stats) const
105 : : {
106 : : LOGCALL(MATCH, TermFreqs, "MultiAndPostList::get_termfreq_est_using_stats", stats);
107 : : // We calculate the estimate assuming independence. With this assumption,
108 : : // the estimate is the product of the estimates for the sub-postlists
109 : : // divided by db_size (n_kids - 1) times.
110 : 96 : TermFreqs freqs(plist[0]->get_termfreq_est_using_stats(stats));
111 : :
112 : 96 : double freqest = double(freqs.termfreq);
113 : 96 : double relfreqest = double(freqs.reltermfreq);
114 : :
115 : : // Our caller should have ensured this.
116 : : Assert(stats.collection_size);
117 : :
118 [ + + ]: 256 : for (size_t i = 1; i < n_kids; ++i) {
119 : 160 : freqs = plist[i]->get_termfreq_est_using_stats(stats);
120 : :
121 : : // If the collection is empty, freqest should be 0 already, so leave
122 : : // it alone.
123 : 160 : freqest = (freqest * freqs.termfreq) / stats.collection_size;
124 : :
125 : : // If the rset is empty, relfreqest should be 0 already, so leave
126 : : // it alone.
127 [ - + ]: 160 : if (stats.rset_size != 0)
128 : 0 : relfreqest = (relfreqest * freqs.reltermfreq) / stats.rset_size;
129 : : }
130 : :
131 : 96 : RETURN(TermFreqs(static_cast<Xapian::doccount>(freqest + 0.5),
132 : : static_cast<Xapian::doccount>(relfreqest + 0.5)));
133 : : }
134 : :
135 : : Xapian::weight
136 : 615 : MultiAndPostList::get_maxweight() const
137 : : {
138 : 615 : return max_total;
139 : : }
140 : :
141 : : Xapian::docid
142 : 3312 : MultiAndPostList::get_docid() const
143 : : {
144 : 3312 : return did;
145 : : }
146 : :
147 : : Xapian::termcount
148 : 78 : MultiAndPostList::get_doclength() const
149 : : {
150 : : Assert(did);
151 : 78 : Xapian::termcount doclength = plist[0]->get_doclength();
152 [ + + ]: 208 : for (size_t i = 1; i < n_kids; ++i) {
153 : : AssertEq(doclength, plist[i]->get_doclength());
154 : : }
155 : 78 : return doclength;
156 : : }
157 : :
158 : : Xapian::weight
159 : 3511 : MultiAndPostList::get_weight() const
160 : : {
161 : : Assert(did);
162 : 3511 : Xapian::weight result = 0;
163 [ + + ]: 11967 : for (size_t i = 0; i < n_kids; ++i) {
164 : 8456 : result += plist[i]->get_weight();
165 : : }
166 : 3511 : return result;
167 : : }
168 : :
169 : : bool
170 : 9030 : MultiAndPostList::at_end() const
171 : : {
172 : 9030 : return (did == 0);
173 : : }
174 : :
175 : : Xapian::weight
176 : 1660 : MultiAndPostList::recalc_maxweight()
177 : : {
178 : 1660 : max_total = 0.0;
179 [ + + ]: 5751 : for (size_t i = 0; i < n_kids; ++i) {
180 : 4091 : Xapian::weight new_max = plist[i]->recalc_maxweight();
181 : 4091 : max_wt[i] = new_max;
182 : 4091 : max_total += new_max;
183 : : }
184 : 1660 : return max_total;
185 : : }
186 : :
187 : : PostList *
188 : 7385 : MultiAndPostList::find_next_match(Xapian::weight w_min)
189 : : {
190 : : advanced_plist0:
191 [ + + ]: 7385 : if (plist[0]->at_end()) {
192 : 1445 : did = 0;
193 : 1445 : return NULL;
194 : : }
195 : 5940 : did = plist[0]->get_docid();
196 [ + + ]: 13914 : for (size_t i = 1; i < n_kids; ++i) {
197 : : bool valid;
198 : 8830 : check_helper(i, did, w_min, valid);
199 [ + + ]: 8830 : if (!valid) {
200 : 7 : next_helper(0, w_min);
201 : 7 : goto advanced_plist0;
202 : : }
203 [ + + ]: 8823 : if (plist[i]->at_end()) {
204 : 126 : did = 0;
205 : 126 : return NULL;
206 : : }
207 : 8697 : Xapian::docid new_did = plist[i]->get_docid();
208 [ + + ]: 8697 : if (new_did != did) {
209 : 723 : skip_to_helper(0, new_did, w_min);
210 : 723 : goto advanced_plist0;
211 : : }
212 : : }
213 : 6655 : return NULL;
214 : : }
215 : :
216 : : PostList *
217 : 6548 : MultiAndPostList::next(Xapian::weight w_min)
218 : : {
219 : 6548 : next_helper(0, w_min);
220 : 6548 : return find_next_match(w_min);
221 : : }
222 : :
223 : : PostList *
224 : 107 : MultiAndPostList::skip_to(Xapian::docid did_min, Xapian::weight w_min)
225 : : {
226 : 107 : skip_to_helper(0, did_min, w_min);
227 : 107 : return find_next_match(w_min);
228 : : }
229 : :
230 : : std::string
231 : 0 : MultiAndPostList::get_description() const
232 : : {
233 : 0 : string desc("(");
234 : 0 : desc += plist[0]->get_description();
235 [ # # ]: 0 : for (size_t i = 1; i < n_kids; ++i) {
236 : 0 : desc += " AND ";
237 : 0 : desc += plist[i]->get_description();
238 : : }
239 : 0 : desc += ')';
240 : 0 : return desc;
241 : : }
242 : :
243 : : Xapian::termcount
244 : 52 : MultiAndPostList::get_wdf() const
245 : : {
246 : 52 : Xapian::termcount totwdf = 0;
247 [ + + ]: 208 : for (size_t i = 0; i < n_kids; ++i) {
248 : 156 : totwdf += plist[i]->get_wdf();
249 : : }
250 : 52 : return totwdf;
251 : : }
252 : :
253 : : Xapian::termcount
254 : 771 : MultiAndPostList::count_matching_subqs() const
255 : : {
256 : 771 : Xapian::termcount total = 0;
257 [ + + ]: 2565 : for (size_t i = 0; i < n_kids; ++i) {
258 : 1794 : total += plist[i]->count_matching_subqs();
259 : : }
260 : 771 : return total;
261 : : }
|
