Branch data Line data Source code
1 : : /** @file ortermlist.cc
2 : : * @brief Merge two TermList objects using an OR operation.
3 : : */
4 : : /* Copyright (C) 2007,2010 Olly Betts
5 : : *
6 : : * This program is free software; you can redistribute it and/or
7 : : * modify it under the terms of the GNU General Public License as
8 : : * published by the Free Software Foundation; either version 2 of the
9 : : * License, or (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 "ortermlist.h"
24 : :
25 : : #include "debuglog.h"
26 : : #include "omassert.h"
27 : :
28 : : #include <xapian/positioniterator.h>
29 : :
30 : : using namespace std;
31 : :
32 : : void
33 : 27497 : OrTermList::check_started() const
34 : : {
35 : : Assert(!left_current.empty());
36 : : Assert(!right_current.empty());
37 : 27497 : }
38 : :
39 : 769 : OrTermList::~OrTermList()
40 : : {
41 [ + + ][ # # ]: 769 : delete left;
[ + - ]
42 [ + + ][ # # ]: 769 : delete right;
[ - + ]
43 [ + - ][ # # ]: 769 : }
[ - + ]
44 : :
45 : : Xapian::termcount
46 : 1327 : OrTermList::get_approx_size() const
47 : : {
48 : : LOGCALL(EXPAND, Xapian::termcount, "OrTermList::get_approx_size", NO_ARGS);
49 : : // This is actually the upper bound, but we only use this to order the
50 : : // binary tree of OrTermList objects so it's probably not worth trying
51 : : // to be more sophisticated.
52 : 1327 : RETURN(left->get_approx_size() + right->get_approx_size());
53 : : }
54 : :
55 : : void
56 : 8012 : OrTermList::accumulate_stats(Xapian::Internal::ExpandStats & stats) const
57 : : {
58 : : LOGCALL_VOID(EXPAND, "OrTermList::accumulate_stats", stats);
59 : 8012 : check_started();
60 [ + + ]: 8012 : if (left_current <= right_current) left->accumulate_stats(stats);
61 [ + + ]: 8012 : if (left_current >= right_current) right->accumulate_stats(stats);
62 : 8012 : }
63 : :
64 : : string
65 : 9365 : OrTermList::get_termname() const
66 : : {
67 : : LOGCALL(EXPAND, string, "OrTermList::get_termname", NO_ARGS);
68 : 9365 : check_started();
69 [ + + ]: 9365 : if (left_current < right_current) RETURN(left_current);
70 : 9365 : RETURN(right_current);
71 : : }
72 : :
73 : : Xapian::termcount
74 : 749 : OrTermList::get_wdf() const
75 : : {
76 : : LOGCALL(EXPAND, Xapian::termcount, "OrTermList::get_wdf", NO_ARGS);
77 : 749 : check_started();
78 [ + + ]: 749 : if (left_current < right_current) RETURN(left->get_wdf());
79 [ + + ]: 680 : if (left_current > right_current) RETURN(right->get_wdf());
80 : 749 : RETURN(left->get_wdf() + right->get_wdf());
81 : : }
82 : :
83 : : Xapian::doccount
84 : 0 : OrTermList::get_termfreq() const
85 : : {
86 : : LOGCALL(EXPAND, Xapian::doccount, "OrTermList::get_termfreq", NO_ARGS);
87 : 0 : check_started();
88 [ # # ]: 0 : if (left_current < right_current) RETURN(left->get_termfreq());
89 : : Assert(left_current > right_current || left->get_termfreq() == right->get_termfreq());
90 : 0 : RETURN(right->get_termfreq());
91 : : }
92 : :
93 : : #if 0 // This method isn't actually used anywhere currently.
94 : : Xapian::termcount
95 : : OrTermList::get_collection_freq() const
96 : : {
97 : : LOGCALL(EXPAND, Xapian::termcount, "OrTermList::get_collection_freq", NO_ARGS);
98 : : check_started();
99 : : if (left_current < right_current) RETURN(left->get_collection_freq());
100 : : Assert(left_current > right_current || left->get_collection_freq() == right->get_collection_freq());
101 : : RETURN(right->get_collection_freq());
102 : : }
103 : : #endif
104 : :
105 : : // Helper function.
106 : : inline void
107 : 12963 : handle_prune(TermList *& old, TermList * result)
108 : : {
109 [ + + ]: 12963 : if (result) {
110 [ + - ]: 411 : delete old;
111 : 411 : old = result;
112 : : }
113 : 12963 : }
114 : :
115 : : TermList *
116 : 10134 : OrTermList::next()
117 : : {
118 : : LOGCALL(EXPAND, TermList *, "OrTermList::next", NO_ARGS);
119 : : // If we've not started yet, both left_current and right_current will be
120 : : // empty, so we'll take the third case below which is what we want to do to
121 : : // get started.
122 [ + + ]: 10134 : if (left_current < right_current) {
123 : 5322 : handle_prune(left, left->next());
124 [ + + ]: 5322 : if (left->at_end()) {
125 : 9 : TermList *ret = right;
126 : 9 : right = NULL;
127 : 9 : RETURN(ret);
128 : : }
129 : 5313 : left_current = left->get_termname();
130 [ + + ]: 4812 : } else if (left_current > right_current) {
131 : 1983 : handle_prune(right, right->next());
132 [ + + ]: 1983 : if (right->at_end()) {
133 : 142 : TermList *ret = left;
134 : 142 : left = NULL;
135 : 142 : RETURN(ret);
136 : : }
137 : 1841 : right_current = right->get_termname();
138 : : } else {
139 : : AssertEq(left_current, right_current);
140 : 2829 : handle_prune(left, left->next());
141 : 2829 : handle_prune(right, right->next());
142 [ + + ]: 2829 : if (left->at_end()) {
143 : : // right->at_end() may also be true, but our parent will deal with
144 : : // that.
145 : 537 : TermList *ret = right;
146 : 537 : right = NULL;
147 : 537 : RETURN(ret);
148 : : }
149 [ + + ]: 2292 : if (right->at_end()) {
150 : 81 : TermList *ret = left;
151 : 81 : left = NULL;
152 : 81 : RETURN(ret);
153 : : }
154 : 2211 : left_current = left->get_termname();
155 : 2211 : right_current = right->get_termname();
156 : : }
157 : 10134 : RETURN(NULL);
158 : : }
159 : :
160 : : TermList *
161 : 0 : OrTermList::skip_to(const string & term)
162 : : {
163 : : LOGCALL(EXPAND, TermList *, "OrTermList::skip_to", term);
164 : : // If we've not started yet, both left_current and right_current will be
165 : : // empty, so we'll take the third case below which is what we want to do to
166 : : // get started.
167 [ # # ]: 0 : if (left_current < right_current) {
168 : 0 : handle_prune(left, left->skip_to(term));
169 [ # # ]: 0 : if (left->at_end()) {
170 : 0 : TermList *ret = right;
171 : 0 : right = NULL;
172 : 0 : RETURN(ret);
173 : : }
174 : 0 : left_current = left->get_termname();
175 [ # # ]: 0 : } else if (left_current > right_current) {
176 : 0 : handle_prune(right, right->skip_to(term));
177 [ # # ]: 0 : if (right->at_end()) {
178 : 0 : TermList *ret = left;
179 : 0 : left = NULL;
180 : 0 : RETURN(ret);
181 : : }
182 : 0 : right_current = right->get_termname();
183 : : } else {
184 : : AssertEq(left_current, right_current);
185 : 0 : handle_prune(left, left->skip_to(term));
186 : 0 : handle_prune(right, right->skip_to(term));
187 [ # # ]: 0 : if (left->at_end()) {
188 : : // right->at_end() may also be true, but our parent will deal with
189 : : // that.
190 : 0 : TermList *ret = right;
191 : 0 : right = NULL;
192 : 0 : RETURN(ret);
193 : : }
194 [ # # ]: 0 : if (right->at_end()) {
195 : 0 : TermList *ret = left;
196 : 0 : left = NULL;
197 : 0 : RETURN(ret);
198 : : }
199 : 0 : left_current = left->get_termname();
200 : 0 : right_current = right->get_termname();
201 : : }
202 : 0 : RETURN(NULL);
203 : : }
204 : :
205 : : bool
206 : 9365 : OrTermList::at_end() const
207 : : {
208 : : LOGCALL(EXPAND, bool, "OrTermList::at_end", NO_ARGS);
209 : 9365 : check_started();
210 : : // next() should have pruned if either child is at_end().
211 : : Assert(!left->at_end());
212 : : Assert(!right->at_end());
213 : 9365 : RETURN(false);
214 : : }
215 : :
216 : : Xapian::termcount
217 : 0 : OrTermList::positionlist_count() const
218 : : {
219 : : Assert(false);
220 : 0 : return 0;
221 : : }
222 : :
223 : : Xapian::PositionIterator
224 : 0 : OrTermList::positionlist_begin() const
225 : : {
226 : : Assert(false);
227 : 0 : return Xapian::PositionIterator(NULL);
228 : : }
229 : :
230 : :
231 : : Xapian::doccount
232 : 6 : FreqAdderOrTermList::get_termfreq() const
233 : : {
234 : : LOGCALL(EXPAND, Xapian::doccount, "FreqAdderOrTermList::get_termfreq", NO_ARGS);
235 : 6 : check_started();
236 [ + + ]: 6 : if (left_current < right_current) RETURN(left->get_termfreq());
237 [ - + ]: 3 : if (left_current > right_current) RETURN(right->get_termfreq());
238 : 6 : RETURN(left->get_termfreq() + right->get_termfreq());
239 : : }
|
