Branch data Line data Source code
1 : : /** @file chert_compact.cc
2 : : * @brief Compact a chert database, or merge and compact several.
3 : : */
4 : : /* Copyright (C) 2004,2005,2006,2007,2008,2009,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
19 : : * USA
20 : : */
21 : :
22 : : #include <config.h>
23 : :
24 : : #include <xapian/compactor.h>
25 : :
26 : : #include <algorithm>
27 : : #include <queue>
28 : :
29 : : #include <cstdio>
30 : :
31 : : #include "safeerrno.h"
32 : : #include <sys/types.h>
33 : : #include "safesysstat.h"
34 : :
35 : : #include "chert_table.h"
36 : : #include "chert_compact.h"
37 : : #include "chert_cursor.h"
38 : : #include "internaltypes.h"
39 : : #include "pack.h"
40 : : #include "utils.h"
41 : : #include "valuestats.h"
42 : :
43 : : #include "../byte_length_strings.h"
44 : : #include "../prefix_compressed_strings.h"
45 : : #include <xapian.h>
46 : :
47 : : using namespace std;
48 : :
49 : : // Put all the helpers in a namespace to avoid symbols colliding with those of
50 : : // the same name in xapian-compact-flint.cc.
51 : : namespace ChertCompact {
52 : :
53 : : static inline bool
54 : 1293 : is_metainfo_key(const string & key)
55 : : {
56 [ + + ][ + + ]: 1293 : return key.size() == 1 && key[0] == '\0';
57 : : }
58 : :
59 : : static inline bool
60 : 1260 : is_user_metadata_key(const string & key)
61 : : {
62 [ + + ][ + + ]: 1260 : return key.size() > 1 && key[0] == '\0' && key[1] == '\xc0';
[ - + ]
63 : : }
64 : :
65 : : static inline bool
66 : 1400 : is_valuestats_key(const string & key)
67 : : {
68 [ + + ][ + + ]: 1400 : return key.size() > 1 && key[0] == '\0' && key[1] == '\xd0';
[ + + ]
69 : : }
70 : :
71 : : static inline bool
72 : 1266 : is_valuechunk_key(const string & key)
73 : : {
74 [ + + ][ + + ]: 1266 : return key.size() > 1 && key[0] == '\0' && key[1] == '\xd8';
[ + + ]
75 : : }
76 : :
77 : : static inline bool
78 : 1727 : is_doclenchunk_key(const string & key)
79 : : {
80 [ + + ][ + + ]: 1727 : return key.size() > 1 && key[0] == '\0' && key[1] == '\xe0';
[ + - ]
81 : : }
82 : :
83 : : class PostlistCursor : private ChertCursor {
84 : : Xapian::docid offset;
85 : :
86 : : public:
87 : : string key, tag;
88 : : Xapian::docid firstdid;
89 : : Xapian::termcount tf, cf;
90 : :
91 : 22 : PostlistCursor(ChertTable *in, Xapian::docid offset_)
92 : 22 : : ChertCursor(in), offset(offset_), firstdid(0)
93 : : {
94 : 22 : find_entry(string());
95 : 22 : next();
96 : 22 : }
97 : :
98 : 22 : ~PostlistCursor()
99 : : {
100 [ + - ]: 22 : delete ChertCursor::get_table();
101 : 22 : }
102 : :
103 : 1293 : bool next() {
104 [ + + ]: 1293 : if (!ChertCursor::next()) return false;
105 : : // We put all chunks into the non-initial chunk form here, then fix up
106 : : // the first chunk for each term in the merged database as we merge.
107 : 1271 : read_tag();
108 : 1271 : key = current_key;
109 : 1271 : tag = current_tag;
110 : 1271 : tf = cf = 0;
111 [ + + ]: 1271 : if (is_metainfo_key(key)) return true;
112 [ - + ]: 1249 : if (is_user_metadata_key(key)) return true;
113 [ + + ]: 1249 : if (is_valuestats_key(key)) return true;
114 [ + + ]: 1109 : if (is_valuechunk_key(key)) {
115 : 146 : const char * p = key.data();
116 : 146 : const char * end = p + key.length();
117 : 146 : p += 2;
118 : : Xapian::valueno slot;
119 [ - + ]: 146 : if (!unpack_uint(&p, end, &slot))
120 : 0 : throw Xapian::DatabaseCorruptError("bad value key");
121 : : Xapian::docid did;
122 [ - + ]: 146 : if (!unpack_uint_preserving_sort(&p, end, &did))
123 : 0 : throw Xapian::DatabaseCorruptError("bad value key");
124 : 146 : did += offset;
125 : :
126 : 146 : key.assign("\0\xd8", 2);
127 : 146 : pack_uint(key, slot);
128 : 146 : pack_uint_preserving_sort(key, did);
129 : 146 : return true;
130 : : }
131 : :
132 : : // Adjust key if this is *NOT* an initial chunk.
133 : : // key is: pack_string_preserving_sort(key, tname)
134 : : // plus optionally: pack_uint_preserving_sort(key, did)
135 : 963 : const char * d = key.data();
136 : 963 : const char * e = d + key.size();
137 [ + + ]: 963 : if (is_doclenchunk_key(key)) {
138 : 31 : d += 2;
139 : : } else {
140 : 932 : string tname;
141 [ - + ]: 932 : if (!unpack_string_preserving_sort(&d, e, tname))
142 : 932 : throw Xapian::DatabaseCorruptError("Bad postlist key");
143 : : }
144 : :
145 [ + + ]: 963 : if (d == e) {
146 : : // This is an initial chunk for a term, so adjust tag header.
147 : 945 : d = tag.data();
148 : 945 : e = d + tag.size();
149 [ + - + - ]: 945 : if (!unpack_uint(&d, e, &tf) ||
[ - + ][ - + ]
150 : : !unpack_uint(&d, e, &cf) ||
151 : : !unpack_uint(&d, e, &firstdid)) {
152 : 0 : throw Xapian::DatabaseCorruptError("Bad postlist key");
153 : : }
154 : 945 : ++firstdid;
155 : 945 : tag.erase(0, d - tag.data());
156 : : } else {
157 : : // Not an initial chunk, so adjust key.
158 : 18 : size_t tmp = d - key.data();
159 [ + - - + ]: 18 : if (!unpack_uint_preserving_sort(&d, e, &firstdid) || d != e)
[ - + ]
160 : 0 : throw Xapian::DatabaseCorruptError("Bad postlist key");
161 [ + + ]: 18 : if (is_doclenchunk_key(key)) {
162 : 9 : key.erase(tmp);
163 : : } else {
164 : 9 : key.erase(tmp - 1);
165 : : }
166 : : }
167 : 963 : firstdid += offset;
168 : 1293 : return true;
169 : : }
170 : : };
171 : :
172 : : class PostlistCursorGt {
173 : : public:
174 : : /** Return true if and only if a's key is strictly greater than b's key.
175 : : */
176 : 1263 : bool operator()(const PostlistCursor *a, const PostlistCursor *b) {
177 [ + + ]: 1263 : if (a->key > b->key) return true;
178 [ + + ]: 869 : if (a->key != b->key) return false;
179 : 1263 : return (a->firstdid > b->firstdid);
180 : : }
181 : : };
182 : :
183 : : static string
184 : 70 : encode_valuestats(Xapian::doccount freq,
185 : : const string & lbound, const string & ubound)
186 : : {
187 : 70 : string value;
188 : 70 : pack_uint(value, freq);
189 : 70 : pack_string(value, lbound);
190 : : // We don't store or count empty values, so neither of the bounds
191 : : // can be empty. So we can safely store an empty upper bound when
192 : : // the bounds are equal.
193 [ + - ]: 70 : if (lbound != ubound) value += ubound;
194 : 0 : return value;
195 : : }
196 : :
197 : : static void
198 : 11 : merge_postlists(Xapian::Compactor & compactor,
199 : : ChertTable * out, vector<Xapian::docid>::const_iterator offset,
200 : : vector<string>::const_iterator b,
201 : : vector<string>::const_iterator e,
202 : : Xapian::docid last_docid)
203 : : {
204 : 11 : totlen_t tot_totlen = 0;
205 : 11 : Xapian::termcount doclen_lbound = static_cast<Xapian::termcount>(-1);
206 : 11 : Xapian::termcount wdf_ubound = 0;
207 : 11 : Xapian::termcount doclen_ubound = 0;
208 : 11 : priority_queue<PostlistCursor *, vector<PostlistCursor *>, PostlistCursorGt> pq;
209 [ + + ]: 33 : for ( ; b != e; ++b, ++offset) {
210 : 22 : ChertTable *in = new ChertTable("postlist", *b, true);
211 : 22 : in->open();
212 [ - + ]: 22 : if (in->empty()) {
213 : : // Skip empty tables.
214 [ # # ]: 0 : delete in;
215 : 0 : continue;
216 : : }
217 : :
218 : : // PostlistCursor takes ownership of ChertTable in and is
219 : : // responsible for deleting it.
220 : 22 : PostlistCursor * cur = new PostlistCursor(in, *offset);
221 : : // Merge the METAINFO tags from each database into one.
222 : : // They have a key consisting of a single zero byte.
223 : : // They may be absent, if the database contains no documents. If it
224 : : // has user metadata we'll still get here.
225 [ + - ]: 22 : if (is_metainfo_key(cur->key)) {
226 : 22 : const char * data = cur->tag.data();
227 : 22 : const char * end = data + cur->tag.size();
228 : 22 : Xapian::docid dummy_did = 0;
229 [ - + ]: 22 : if (!unpack_uint(&data, end, &dummy_did)) {
230 : 0 : throw Xapian::DatabaseCorruptError("Tag containing meta information is corrupt.");
231 : : }
232 : :
233 : : Xapian::termcount doclen_lbound_tmp;
234 [ - + ]: 22 : if (!unpack_uint(&data, end, &doclen_lbound_tmp)) {
235 : 0 : throw Xapian::DatabaseCorruptError("Tag containing meta information is corrupt.");
236 : : }
237 : 22 : doclen_lbound = min(doclen_lbound, doclen_lbound_tmp);
238 : :
239 : : Xapian::termcount wdf_ubound_tmp;
240 [ - + ]: 22 : if (!unpack_uint(&data, end, &wdf_ubound_tmp)) {
241 : 0 : throw Xapian::DatabaseCorruptError("Tag containing meta information is corrupt.");
242 : : }
243 : 22 : wdf_ubound = max(wdf_ubound, wdf_ubound_tmp);
244 : :
245 : : Xapian::termcount doclen_ubound_tmp;
246 [ - + ]: 22 : if (!unpack_uint(&data, end, &doclen_ubound_tmp)) {
247 : 0 : throw Xapian::DatabaseCorruptError("Tag containing meta information is corrupt.");
248 : : }
249 : 22 : doclen_ubound_tmp += wdf_ubound_tmp;
250 : 22 : doclen_ubound = max(doclen_ubound, doclen_ubound_tmp);
251 : :
252 : 22 : totlen_t totlen = 0;
253 [ - + ]: 22 : if (!unpack_uint_last(&data, end, &totlen)) {
254 : 0 : throw Xapian::DatabaseCorruptError("Tag containing meta information is corrupt.");
255 : : }
256 : 22 : tot_totlen += totlen;
257 [ - + ]: 22 : if (tot_totlen < totlen) {
258 : 0 : throw "totlen wrapped!";
259 : : }
260 : : }
261 [ + - ]: 22 : if (cur->next()) {
262 : 22 : pq.push(cur);
263 : : } else {
264 [ # # ]: 0 : delete cur;
265 : : }
266 : : }
267 : :
268 : : {
269 : 11 : string tag;
270 : 11 : pack_uint(tag, last_docid);
271 : 11 : pack_uint(tag, doclen_lbound);
272 : 11 : pack_uint(tag, wdf_ubound);
273 : 11 : pack_uint(tag, doclen_ubound - wdf_ubound);
274 : 11 : pack_uint_last(tag, tot_totlen);
275 : 11 : out->add(string(1, '\0'), tag);
276 : : }
277 : :
278 : 11 : string last_key;
279 : : {
280 : : // Merge user metadata.
281 : 11 : vector<string> tags;
282 [ + - ]: 11 : while (!pq.empty()) {
283 : 11 : PostlistCursor * cur = pq.top();
284 : 11 : const string& key = cur->key;
285 [ + - ]: 11 : if (!is_user_metadata_key(key)) break;
286 : :
287 [ # # ]: 0 : if (key != last_key) {
288 [ # # ]: 0 : if (tags.size() > 1) {
289 : : Assert(!last_key.empty());
290 : : // FIXME: It would be better to merge all duplicates for a
291 : : // key in one call, but currently we don't in multipass
292 : : // mode.
293 : : out->add(last_key,
294 : : compactor.resolve_duplicate_metadata(last_key,
295 : : tags.size(),
296 : 0 : &tags[0]));
297 [ # # ]: 0 : } else if (tags.size() == 1) {
298 : : Assert(!last_key.empty());
299 : 0 : out->add(last_key, tags[0]);
300 : : }
301 : 0 : tags.resize(0);
302 : 0 : last_key = key;
303 : : }
304 : 0 : tags.push_back(cur->tag);
305 : :
306 : 0 : pq.pop();
307 [ # # ]: 0 : if (cur->next()) {
308 : 0 : pq.push(cur);
309 : : } else {
310 [ # # ]: 0 : delete cur;
311 : : }
312 : : }
313 [ - + ]: 11 : if (tags.size() > 1) {
314 : : Assert(!last_key.empty());
315 : : out->add(last_key,
316 : : compactor.resolve_duplicate_metadata(last_key,
317 : : tags.size(),
318 : 0 : &tags[0]));
319 [ - + ]: 11 : } else if (tags.size() == 1) {
320 : : Assert(!last_key.empty());
321 : 0 : out->add(last_key, tags[0]);
322 : 11 : }
323 : : }
324 : :
325 : : {
326 : : // Merge valuestats.
327 : 11 : Xapian::doccount freq = 0;
328 : 11 : string lbound, ubound;
329 : :
330 : 11 : string last_tag;
331 [ + - ]: 151 : while (!pq.empty()) {
332 : 151 : PostlistCursor * cur = pq.top();
333 : 151 : const string& key = cur->key;
334 [ + + ]: 151 : if (!is_valuestats_key(key)) break;
335 [ + + ]: 140 : if (key != last_key) {
336 : : // For the first valuestats key, last_key will be the previous
337 : : // key we wrote, which we don't want to overwrite. This is the
338 : : // only time that freq will be 0, so check that.
339 [ + + ]: 70 : if (freq) {
340 : 65 : out->add(last_key, encode_valuestats(freq, lbound, ubound));
341 : 65 : freq = 0;
342 : : }
343 : 70 : last_key = key;
344 : : }
345 : :
346 : 140 : const string & tag = cur->tag;
347 : :
348 : 140 : const char * pos = tag.data();
349 : 140 : const char * end = pos + tag.size();
350 : :
351 : : Xapian::doccount f;
352 : 140 : string l, u;
353 [ - + ]: 140 : if (!unpack_uint(&pos, end, &f)) {
354 [ # # ]: 0 : if (*pos == 0) throw Xapian::DatabaseCorruptError("Incomplete stats item in value table");
355 : 0 : throw Xapian::RangeError("Frequency statistic in value table is too large");
356 : : }
357 [ - + ]: 140 : if (!unpack_string(&pos, end, l)) {
358 [ # # ]: 0 : if (*pos == 0) throw Xapian::DatabaseCorruptError("Incomplete stats item in value table");
359 : 0 : throw Xapian::RangeError("Lower bound in value table is too large");
360 : : }
361 : 140 : size_t len = end - pos;
362 [ + + ]: 140 : if (len == 0) {
363 : 4 : u = l;
364 : : } else {
365 : 136 : u.assign(pos, len);
366 : : }
367 [ + + ]: 140 : if (freq == 0) {
368 : 70 : freq = f;
369 : 70 : lbound = l;
370 : 70 : ubound = u;
371 : : } else {
372 : 70 : freq += f;
373 [ + + ]: 70 : if (l < lbound) lbound = l;
374 [ + + ]: 70 : if (u > ubound) ubound = u;
375 : : }
376 : :
377 : 140 : pq.pop();
378 [ + - ]: 140 : if (cur->next()) {
379 : 140 : pq.push(cur);
380 : : } else {
381 [ # # ]: 0 : delete cur;
382 : : }
383 : : }
384 : :
385 [ + + ]: 11 : if (freq) {
386 : 5 : out->add(last_key, encode_valuestats(freq, lbound, ubound));
387 : 11 : }
388 : : }
389 : :
390 : : // Merge valuestream chunks.
391 [ + - ]: 157 : while (!pq.empty()) {
392 : 157 : PostlistCursor * cur = pq.top();
393 : 157 : const string & key = cur->key;
394 [ + + ]: 157 : if (!is_valuechunk_key(key)) break;
395 : : Assert(!is_user_metadata_key(key));
396 : 146 : out->add(key, cur->tag);
397 : 146 : pq.pop();
398 [ + - ]: 146 : if (cur->next()) {
399 : 146 : pq.push(cur);
400 : : } else {
401 [ # # ]: 0 : delete cur;
402 : : }
403 : : }
404 : :
405 : 11 : Xapian::termcount tf = 0, cf = 0; // Initialise to avoid warnings.
406 : 11 : vector<pair<Xapian::docid, string> > tags;
407 : 963 : while (true) {
408 : 974 : PostlistCursor * cur = NULL;
409 [ + + ]: 974 : if (!pq.empty()) {
410 : 963 : cur = pq.top();
411 : 963 : pq.pop();
412 : : }
413 : : Assert(cur == NULL || !is_user_metadata_key(cur->key));
414 [ + + ][ + + ]: 974 : if (cur == NULL || cur->key != last_key) {
[ + + ]
415 [ + + ]: 757 : if (!tags.empty()) {
416 : 746 : string first_tag;
417 : 746 : pack_uint(first_tag, tf);
418 : 746 : pack_uint(first_tag, cf);
419 : 746 : pack_uint(first_tag, tags[0].first - 1);
420 : 746 : string tag = tags[0].second;
421 [ + + ]: 746 : tag[0] = (tags.size() == 1) ? '1' : '0';
422 : 746 : first_tag += tag;
423 : 746 : out->add(last_key, first_tag);
424 : :
425 : 746 : string term;
426 [ + + ]: 746 : if (!is_doclenchunk_key(last_key)) {
427 : 735 : const char * p = last_key.data();
428 : 735 : const char * end = p + last_key.size();
429 [ + - - + ]: 735 : if (!unpack_string_preserving_sort(&p, end, term) || p != end)
[ - + ]
430 : 0 : throw Xapian::DatabaseCorruptError("Bad postlist chunk key");
431 : : }
432 : :
433 : 746 : vector<pair<Xapian::docid, string> >::const_iterator i;
434 : 746 : i = tags.begin();
435 [ + + ]: 963 : while (++i != tags.end()) {
436 : 217 : tag = i->second;
437 [ + + ]: 217 : tag[0] = (i + 1 == tags.end()) ? '1' : '0';
438 : 217 : out->add(pack_chert_postlist_key(term, i->first), tag);
439 : 746 : }
440 : : }
441 : 757 : tags.clear();
442 [ + + ]: 757 : if (cur == NULL) break;
443 : 746 : tf = cf = 0;
444 : 746 : last_key = cur->key;
445 : : }
446 : 963 : tf += cur->tf;
447 : 963 : cf += cur->cf;
448 : 963 : tags.push_back(make_pair(cur->firstdid, cur->tag));
449 [ + + ]: 963 : if (cur->next()) {
450 : 941 : pq.push(cur);
451 : : } else {
452 [ + - ]: 22 : delete cur;
453 : : }
454 : 11 : }
455 : 11 : }
456 : :
457 : : struct MergeCursor : public ChertCursor {
458 : 2 : MergeCursor(ChertTable *in) : ChertCursor(in) {
459 : 2 : find_entry(string());
460 : 2 : next();
461 : 2 : }
462 : :
463 : 2 : ~MergeCursor() {
464 [ + - ]: 2 : delete ChertCursor::get_table();
465 : 2 : }
466 : : };
467 : :
468 : : struct CursorGt {
469 : : /// Return true if and only if a's key is strictly greater than b's key.
470 : 0 : bool operator()(const ChertCursor *a, const ChertCursor *b) {
471 [ # # ]: 0 : if (b->after_end()) return false;
472 [ # # ]: 0 : if (a->after_end()) return true;
473 : 0 : return (a->current_key > b->current_key);
474 : : }
475 : : };
476 : :
477 : : static void
478 : 1 : merge_spellings(ChertTable * out,
479 : : vector<string>::const_iterator b,
480 : : vector<string>::const_iterator e)
481 : : {
482 : 1 : priority_queue<MergeCursor *, vector<MergeCursor *>, CursorGt> pq;
483 [ + + ]: 3 : for ( ; b != e; ++b) {
484 : 2 : ChertTable *in = new ChertTable("spelling", *b, true, DONT_COMPRESS, true);
485 : 2 : in->open();
486 [ + + ]: 2 : if (!in->empty()) {
487 : : // The MergeCursor takes ownership of ChertTable in and is
488 : : // responsible for deleting it.
489 : 1 : pq.push(new MergeCursor(in));
490 : : } else {
491 [ + - ]: 1 : delete in;
492 : : }
493 : : }
494 : :
495 [ + + ]: 6 : while (!pq.empty()) {
496 : 5 : MergeCursor * cur = pq.top();
497 : 5 : pq.pop();
498 : :
499 : 5 : string key = cur->current_key;
500 [ - + # # ]: 5 : if (pq.empty() || pq.top()->current_key > key) {
[ + - ]
501 : : // No need to merge the tags, just copy the (possibly compressed)
502 : : // tag value.
503 : 5 : bool compressed = cur->read_tag(true);
504 : 5 : out->add(key, cur->current_tag, compressed);
505 [ + + ]: 5 : if (cur->next()) {
506 : 4 : pq.push(cur);
507 : : } else {
508 [ + - ]: 1 : delete cur;
509 : : }
510 : 5 : continue;
511 : : }
512 : :
513 : : // Merge tag values with the same key:
514 : 0 : string tag;
515 [ # # ]: 0 : if (key[0] != 'W') {
516 : : // We just want the union of words, so copy over the first instance
517 : : // and skip any identical ones.
518 : : priority_queue<PrefixCompressedStringItor *,
519 : : vector<PrefixCompressedStringItor *>,
520 : 0 : PrefixCompressedStringItorGt> pqtag;
521 : : // Stick all the MergeCursor pointers in a vector because their
522 : : // current_tag members must remain valid while we're merging their
523 : : // tags, but we need to call next() on them all afterwards.
524 : 0 : vector<MergeCursor *> vec;
525 : 0 : vec.reserve(pq.size());
526 : :
527 : 0 : while (true) {
528 : 0 : cur->read_tag();
529 : 0 : pqtag.push(new PrefixCompressedStringItor(cur->current_tag));
530 : 0 : vec.push_back(cur);
531 [ # # # # ]: 0 : if (pq.empty() || pq.top()->current_key != key) break;
[ # # ]
532 : 0 : cur = pq.top();
533 : 0 : pq.pop();
534 : : }
535 : :
536 : 0 : PrefixCompressedStringWriter wr(tag);
537 : 0 : string lastword;
538 [ # # ]: 0 : while (!pqtag.empty()) {
539 : 0 : PrefixCompressedStringItor * it = pqtag.top();
540 : 0 : string word = **it;
541 [ # # ]: 0 : if (word != lastword) {
542 : 0 : lastword = word;
543 : 0 : wr.append(lastword);
544 : : }
545 : 0 : ++*it;
546 : 0 : pqtag.pop();
547 [ # # ]: 0 : if (!it->at_end()) {
548 : 0 : pqtag.push(it);
549 : : } else {
550 [ # # ]: 0 : delete it;
551 : : }
552 : : }
553 : :
554 : 0 : vector<MergeCursor *>::const_iterator i;
555 [ # # ]: 0 : for (i = vec.begin(); i != vec.end(); ++i) {
556 : 0 : cur = *i;
557 [ # # ]: 0 : if (cur->next()) {
558 : 0 : pq.push(cur);
559 : : } else {
560 [ # # ]: 0 : delete cur;
561 : : }
562 : 0 : }
563 : : } else {
564 : : // We want to sum the frequencies from tags for the same key.
565 : 0 : Xapian::termcount tot_freq = 0;
566 : 0 : while (true) {
567 : 0 : cur->read_tag();
568 : : Xapian::termcount freq;
569 : 0 : const char * p = cur->current_tag.data();
570 : 0 : const char * end = p + cur->current_tag.size();
571 [ # # # # ]: 0 : if (!unpack_uint_last(&p, end, &freq) || freq == 0) {
[ # # ]
572 : 0 : throw Xapian::DatabaseCorruptError("Bad spelling word freq");
573 : : }
574 : 0 : tot_freq += freq;
575 [ # # ]: 0 : if (cur->next()) {
576 : 0 : pq.push(cur);
577 : : } else {
578 [ # # ]: 0 : delete cur;
579 : : }
580 [ # # ][ # # ]: 0 : if (pq.empty() || pq.top()->current_key != key) break;
[ # # ]
581 : 0 : cur = pq.top();
582 : 0 : pq.pop();
583 : : }
584 : 0 : tag.resize(0);
585 : 0 : pack_uint_last(tag, tot_freq);
586 : : }
587 : 0 : out->add(key, tag);
588 : 1 : }
589 : 1 : }
590 : :
591 : : static void
592 : 1 : merge_synonyms(ChertTable * out,
593 : : vector<string>::const_iterator b,
594 : : vector<string>::const_iterator e)
595 : : {
596 : 1 : priority_queue<MergeCursor *, vector<MergeCursor *>, CursorGt> pq;
597 [ + + ]: 3 : for ( ; b != e; ++b) {
598 : 2 : ChertTable *in = new ChertTable("synonym", *b, true, DONT_COMPRESS, true);
599 : 2 : in->open();
600 [ + + ]: 2 : if (!in->empty()) {
601 : : // The MergeCursor takes ownership of ChertTable in and is
602 : : // responsible for deleting it.
603 : 1 : pq.push(new MergeCursor(in));
604 : : } else {
605 [ + - ]: 1 : delete in;
606 : : }
607 : : }
608 : :
609 [ + + ]: 2 : while (!pq.empty()) {
610 : 1 : MergeCursor * cur = pq.top();
611 : 1 : pq.pop();
612 : :
613 : 1 : string key = cur->current_key;
614 [ - + # # ]: 1 : if (pq.empty() || pq.top()->current_key > key) {
[ + - ]
615 : : // No need to merge the tags, just copy the (possibly compressed)
616 : : // tag value.
617 : 1 : bool compressed = cur->read_tag(true);
618 : 1 : out->add(key, cur->current_tag, compressed);
619 [ - + ]: 1 : if (cur->next()) {
620 : 0 : pq.push(cur);
621 : : } else {
622 [ + - ]: 1 : delete cur;
623 : : }
624 : 1 : continue;
625 : : }
626 : :
627 : : // Merge tag values with the same key:
628 : 0 : string tag;
629 : :
630 : : // We just want the union of words, so copy over the first instance
631 : : // and skip any identical ones.
632 : : priority_queue<ByteLengthPrefixedStringItor *,
633 : : vector<ByteLengthPrefixedStringItor *>,
634 : 0 : ByteLengthPrefixedStringItorGt> pqtag;
635 : 0 : vector<MergeCursor *> vec;
636 : :
637 : 0 : while (true) {
638 : 0 : cur->read_tag();
639 : 0 : pqtag.push(new ByteLengthPrefixedStringItor(cur->current_tag));
640 : 0 : vec.push_back(cur);
641 [ # # # # ]: 0 : if (pq.empty() || pq.top()->current_key != key) break;
[ # # ]
642 : 0 : cur = pq.top();
643 : 0 : pq.pop();
644 : : }
645 : :
646 : 0 : string lastword;
647 [ # # ]: 0 : while (!pqtag.empty()) {
648 : 0 : ByteLengthPrefixedStringItor * it = pqtag.top();
649 [ # # ]: 0 : if (**it != lastword) {
650 : 0 : lastword = **it;
651 : 0 : tag += byte(lastword.size() ^ MAGIC_XOR_VALUE);
652 : 0 : tag += lastword;
653 : : }
654 : 0 : ++*it;
655 : 0 : pqtag.pop();
656 [ # # ]: 0 : if (!it->at_end()) {
657 : 0 : pqtag.push(it);
658 : : } else {
659 : 0 : delete it;
660 : : }
661 : : }
662 : :
663 : 0 : vector<MergeCursor *>::const_iterator i;
664 [ # # ]: 0 : for (i = vec.begin(); i != vec.end(); ++i) {
665 : 0 : cur = *i;
666 [ # # ]: 0 : if (cur->next()) {
667 : 0 : pq.push(cur);
668 : : } else {
669 [ # # ]: 0 : delete cur;
670 : : }
671 : : }
672 : :
673 : 0 : out->add(key, tag);
674 : 1 : }
675 : 1 : }
676 : :
677 : : static void
678 : 0 : multimerge_postlists(Xapian::Compactor & compactor,
679 : : ChertTable * out, const char * tmpdir,
680 : : Xapian::docid last_docid,
681 : : vector<string> tmp, vector<Xapian::docid> off)
682 : : {
683 : 0 : unsigned int c = 0;
684 [ # # ]: 0 : while (tmp.size() > 3) {
685 : 0 : vector<string> tmpout;
686 : 0 : tmpout.reserve(tmp.size() / 2);
687 : 0 : vector<Xapian::docid> newoff;
688 : 0 : newoff.resize(tmp.size() / 2);
689 [ # # ]: 0 : for (unsigned int i = 0, j; i < tmp.size(); i = j) {
690 : 0 : j = i + 2;
691 [ # # ]: 0 : if (j == tmp.size() - 1) ++j;
692 : :
693 : 0 : string dest = tmpdir;
694 : : char buf[64];
695 : 0 : sprintf(buf, "/tmp%u_%u.", c, i / 2);
696 : 0 : dest += buf;
697 : :
698 : : // Don't compress temporary tables, even if the final table would
699 : : // be.
700 : 0 : ChertTable tmptab("postlist", dest, false);
701 : : // Use maximum blocksize for temporary tables.
702 : 0 : tmptab.create_and_open(65536);
703 : :
704 : : merge_postlists(compactor, &tmptab, off.begin() + i,
705 : 0 : tmp.begin() + i, tmp.begin() + j, 0);
706 [ # # ]: 0 : if (c > 0) {
707 [ # # ]: 0 : for (unsigned int k = i; k < j; ++k) {
708 : 0 : unlink((tmp[k] + "DB").c_str());
709 : 0 : unlink((tmp[k] + "baseA").c_str());
710 : 0 : unlink((tmp[k] + "baseB").c_str());
711 : : }
712 : : }
713 : 0 : tmpout.push_back(dest);
714 : 0 : tmptab.flush_db();
715 : 0 : tmptab.commit(1);
716 : : }
717 : 0 : swap(tmp, tmpout);
718 : 0 : swap(off, newoff);
719 : 0 : ++c;
720 : : }
721 : : merge_postlists(compactor,
722 : 0 : out, off.begin(), tmp.begin(), tmp.end(), last_docid);
723 [ # # ]: 0 : if (c > 0) {
724 [ # # ]: 0 : for (size_t k = 0; k < tmp.size(); ++k) {
725 : 0 : unlink((tmp[k] + "DB").c_str());
726 : 0 : unlink((tmp[k] + "baseA").c_str());
727 : 0 : unlink((tmp[k] + "baseB").c_str());
728 : : }
729 : : }
730 : 0 : }
731 : :
732 : : static void
733 : 27 : merge_docid_keyed(const char * tablename,
734 : : ChertTable *out, const vector<string> & inputs,
735 : : const vector<Xapian::docid> & offset, bool lazy)
736 : : {
737 [ + + ]: 81 : for (size_t i = 0; i < inputs.size(); ++i) {
738 : 54 : Xapian::docid off = offset[i];
739 : :
740 : 54 : ChertTable in(tablename, inputs[i], true, DONT_COMPRESS, lazy);
741 : 54 : in.open();
742 [ - + ]: 54 : if (in.empty()) continue;
743 : :
744 : 54 : ChertCursor cur(&in);
745 : 54 : cur.find_entry(string());
746 : :
747 : 54 : string key;
748 [ + + ]: 21414 : while (cur.next()) {
749 : : // Adjust the key if this isn't the first database.
750 [ + + ]: 21360 : if (off) {
751 : : Xapian::docid did;
752 : 363 : const char * d = cur.current_key.data();
753 : 363 : const char * e = d + cur.current_key.size();
754 [ - + ]: 363 : if (!unpack_uint_preserving_sort(&d, e, &did)) {
755 : 0 : string msg = "Bad key in ";
756 : 0 : msg += inputs[i];
757 : 0 : throw Xapian::DatabaseCorruptError(msg);
758 : : }
759 : 363 : did += off;
760 : 363 : key.resize(0);
761 : 363 : pack_uint_preserving_sort(key, did);
762 [ + + ]: 363 : if (d != e) {
763 : : // Copy over the termname for the position table.
764 : 333 : key.append(d, e - d);
765 : : }
766 : : } else {
767 : 20997 : key = cur.current_key;
768 : : }
769 : 21360 : bool compressed = cur.read_tag(true);
770 : 21360 : out->add(key, cur.current_tag, compressed);
771 : : }
772 : : }
773 : 27 : }
774 : :
775 : : }
776 : :
777 : : using namespace ChertCompact;
778 : :
779 : : void
780 : 11 : compact_chert(Xapian::Compactor & compactor,
781 : : const char * destdir, const vector<string> & sources,
782 : : const vector<Xapian::docid> & offset, size_t block_size,
783 : : Xapian::Compactor::compaction_level compaction, bool multipass,
784 : : Xapian::docid last_docid) {
785 : : enum table_type {
786 : : POSTLIST, RECORD, TERMLIST, POSITION, VALUE, SPELLING, SYNONYM
787 : : };
788 : : struct table_list {
789 : : // The "base name" of the table.
790 : : const char * name;
791 : : // The type.
792 : : table_type type;
793 : : // zlib compression strategy to use on tags.
794 : : int compress_strategy;
795 : : // Create tables after position lazily.
796 : : bool lazy;
797 : : };
798 : :
799 : : static const table_list tables[] = {
800 : : // name type compress_strategy lazy
801 : : { "postlist", POSTLIST, DONT_COMPRESS, false },
802 : : { "record", RECORD, Z_DEFAULT_STRATEGY, false },
803 : : { "termlist", TERMLIST, Z_DEFAULT_STRATEGY, false },
804 : : { "position", POSITION, DONT_COMPRESS, true },
805 : : { "spelling", SPELLING, Z_DEFAULT_STRATEGY, true },
806 : : { "synonym", SYNONYM, Z_DEFAULT_STRATEGY, true }
807 : : };
808 : : const table_list * tables_end = tables +
809 : 11 : (sizeof(tables) / sizeof(tables[0]));
810 : :
811 [ + + ][ + + ]: 77 : for (const table_list * t = tables; t < tables_end; ++t) {
812 : : // The postlist table requires an N-way merge, adjusting the
813 : : // headers of various blocks. The spelling and synonym tables also
814 : : // need special handling. The other tables have keys sorted in
815 : : // docid order, so we can merge them by simply copying all the keys
816 : : // from each source table in turn.
817 : 66 : compactor.set_status(t->name, string());
818 : :
819 : 66 : string dest = destdir;
820 : 66 : dest += '/';
821 : 66 : dest += t->name;
822 : 66 : dest += '.';
823 : :
824 : 66 : bool output_will_exist = !t->lazy;
825 : :
826 : : // Sometimes stat can fail for benign reasons (e.g. >= 2GB file
827 : : // on certain systems).
828 : 66 : bool bad_stat = false;
829 : :
830 : 66 : off_t in_size = 0;
831 : :
832 : 66 : vector<string> inputs;
833 : 66 : inputs.reserve(sources.size());
834 : 66 : size_t inputs_present = 0;
835 [ + + ]: 198 : for (vector<string>::const_iterator src = sources.begin();
836 : : src != sources.end(); ++src) {
837 : 132 : string s(*src);
838 : 132 : s += t->name;
839 : 132 : s += '.';
840 : :
841 : : struct stat sb;
842 [ + + ]: 132 : if (stat(s + "DB", &sb) == 0) {
843 : 78 : in_size += sb.st_size / 1024;
844 : 78 : output_will_exist = true;
845 : 78 : ++inputs_present;
846 [ - + ]: 54 : } else if (errno != ENOENT) {
847 : : // We get ENOENT for an optional table.
848 : 0 : bad_stat = true;
849 : 0 : output_will_exist = true;
850 : 0 : ++inputs_present;
851 : : }
852 : 132 : inputs.push_back(s);
853 : : }
854 : :
855 : : // If any inputs lack a termlist table, suppress it in the output.
856 [ + + ][ - + ]: 66 : if (t->type == TERMLIST && inputs_present != sources.size()) {
[ - + ]
857 [ # # ]: 0 : if (inputs_present != 0) {
858 : 0 : string m = str(inputs_present);
859 : 0 : m += " of ";
860 : 0 : m += str(sources.size());
861 : 0 : m += " inputs present, so suppressing output";
862 : 0 : compactor.set_status(t->name, m);
863 : 0 : continue;
864 : : }
865 : 0 : output_will_exist = false;
866 : : }
867 : :
868 [ + + ]: 66 : if (!output_will_exist) {
869 : 26 : compactor.set_status(t->name, "doesn't exist");
870 : 26 : continue;
871 : : }
872 : :
873 : 40 : ChertTable out(t->name, dest, false, t->compress_strategy, t->lazy);
874 [ + + ]: 40 : if (!t->lazy) {
875 : 33 : out.create_and_open(block_size);
876 : : } else {
877 : 7 : out.erase();
878 : 7 : out.set_block_size(block_size);
879 : : }
880 : :
881 : 40 : out.set_full_compaction(compaction != compactor.STANDARD);
882 [ - + ]: 40 : if (compaction == compactor.FULLER) out.set_max_item_size(1);
883 : :
884 [ + + + + ]: 40 : switch (t->type) {
885 : : case POSTLIST:
886 [ - + ][ # # ]: 11 : if (multipass && inputs.size() > 3) {
[ - + ]
887 : : multimerge_postlists(compactor, &out, destdir, last_docid,
888 : 0 : inputs, offset);
889 : : } else {
890 : : merge_postlists(compactor, &out, offset.begin(),
891 : : inputs.begin(), inputs.end(),
892 : 11 : last_docid);
893 : : }
894 : 11 : break;
895 : : case SPELLING:
896 : 1 : merge_spellings(&out, inputs.begin(), inputs.end());
897 : 1 : break;
898 : : case SYNONYM:
899 : 1 : merge_synonyms(&out, inputs.begin(), inputs.end());
900 : 1 : break;
901 : : default:
902 : : // Position, Record, Termlist
903 : 27 : merge_docid_keyed(t->name, &out, inputs, offset, t->lazy);
904 : : break;
905 : : }
906 : :
907 : : // Commit as revision 1.
908 : 40 : out.flush_db();
909 : 40 : out.commit(1);
910 : :
911 : 40 : off_t out_size = 0;
912 [ + - ]: 40 : if (!bad_stat) {
913 : : struct stat sb;
914 [ + - ]: 40 : if (stat(dest + "DB", &sb) == 0) {
915 : 40 : out_size = sb.st_size / 1024;
916 : : } else {
917 : 0 : bad_stat = (errno != ENOENT);
918 : : }
919 : : }
920 [ - + ]: 40 : if (bad_stat) {
921 : 0 : compactor.set_status(t->name, "Done (couldn't stat all the DB files)");
922 : : } else {
923 : 40 : string status;
924 [ + + ]: 40 : if (out_size == in_size) {
925 : 5 : status = "Size unchanged (";
926 : : } else {
927 : : off_t delta;
928 [ + + ]: 35 : if (out_size < in_size) {
929 : 6 : delta = in_size - out_size;
930 : 6 : status = "Reduced by ";
931 : : } else {
932 : 29 : delta = out_size - in_size;
933 : 29 : status = "INCREASED by ";
934 : : }
935 : 35 : status += str(100 * delta / in_size);
936 : 35 : status += "% ";
937 : 35 : status += str(delta);
938 : 35 : status += "K (";
939 : 35 : status += str(in_size);
940 : 35 : status += "K -> ";
941 : : }
942 : 40 : status += str(out_size);
943 : 40 : status += "K)";
944 : 40 : compactor.set_status(t->name, status);
945 : : }
946 : : }
947 : 11 : }
|
