Branch data Line data Source code
1 : : /** @file brass_compact.cc
2 : : * @brief Compact a brass 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 "brass_table.h"
36 : : #include "brass_compact.h"
37 : : #include "brass_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 flint_compact.cc.
51 : : namespace BrassCompact {
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 BrassCursor {
84 : : Xapian::docid offset;
85 : :
86 : : public:
87 : : string key, tag;
88 : : Xapian::docid firstdid;
89 : : Xapian::termcount tf, cf;
90 : :
91 : 22 : PostlistCursor(BrassTable *in, Xapian::docid offset_)
92 : 22 : : BrassCursor(in), offset(offset_), firstdid(0)
93 : : {
94 : 22 : find_entry(string());
95 : 22 : next();
96 : 22 : }
97 : :
98 : 22 : ~PostlistCursor()
99 : : {
100 [ + - ]: 22 : delete BrassCursor::get_table();
101 : 22 : }
102 : :
103 : 1293 : bool next() {
104 [ + + ]: 1293 : if (!BrassCursor::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 : : BrassTable * 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 : BrassTable *in = new BrassTable("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 BrassTable 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 : : out->add(last_key,
291 : : compactor.resolve_duplicate_metadata(last_key,
292 : : tags.size(),
293 : 0 : &tags[0]));
294 [ # # ]: 0 : } else if (tags.size() == 1) {
295 : : Assert(!last_key.empty());
296 : 0 : out->add(last_key, tags[0]);
297 : : }
298 : 0 : tags.resize(0);
299 : 0 : last_key = key;
300 : : }
301 : 0 : tags.push_back(cur->tag);
302 : :
303 : 0 : pq.pop();
304 [ # # ]: 0 : if (cur->next()) {
305 : 0 : pq.push(cur);
306 : : } else {
307 [ # # ]: 0 : delete cur;
308 : : }
309 : : }
310 [ - + ]: 11 : if (tags.size() > 1) {
311 : : Assert(!last_key.empty());
312 : : out->add(last_key,
313 : : compactor.resolve_duplicate_metadata(last_key,
314 : : tags.size(),
315 : 0 : &tags[0]));
316 [ - + ]: 11 : } else if (tags.size() == 1) {
317 : : Assert(!last_key.empty());
318 : 0 : out->add(last_key, tags[0]);
319 : 11 : }
320 : : }
321 : :
322 : : {
323 : : // Merge valuestats.
324 : 11 : Xapian::doccount freq = 0;
325 : 11 : string lbound, ubound;
326 : :
327 : 11 : string last_tag;
328 [ + - ]: 151 : while (!pq.empty()) {
329 : 151 : PostlistCursor * cur = pq.top();
330 : 151 : const string& key = cur->key;
331 [ + + ]: 151 : if (!is_valuestats_key(key)) break;
332 [ + + ]: 140 : if (key != last_key) {
333 : : // For the first valuestats key, last_key will be the previous
334 : : // key we wrote, which we don't want to overwrite. This is the
335 : : // only time that freq will be 0, so check that.
336 [ + + ]: 70 : if (freq) {
337 : 65 : out->add(last_key, encode_valuestats(freq, lbound, ubound));
338 : 65 : freq = 0;
339 : : }
340 : 70 : last_key = key;
341 : : }
342 : :
343 : 140 : const string & tag = cur->tag;
344 : :
345 : 140 : const char * pos = tag.data();
346 : 140 : const char * end = pos + tag.size();
347 : :
348 : : Xapian::doccount f;
349 : 140 : string l, u;
350 [ - + ]: 140 : if (!unpack_uint(&pos, end, &f)) {
351 [ # # ]: 0 : if (*pos == 0) throw Xapian::DatabaseCorruptError("Incomplete stats item in value table");
352 : 0 : throw Xapian::RangeError("Frequency statistic in value table is too large");
353 : : }
354 [ - + ]: 140 : if (!unpack_string(&pos, end, l)) {
355 [ # # ]: 0 : if (*pos == 0) throw Xapian::DatabaseCorruptError("Incomplete stats item in value table");
356 : 0 : throw Xapian::RangeError("Lower bound in value table is too large");
357 : : }
358 : 140 : size_t len = end - pos;
359 [ + + ]: 140 : if (len == 0) {
360 : 4 : u = l;
361 : : } else {
362 : 136 : u.assign(pos, len);
363 : : }
364 [ + + ]: 140 : if (freq == 0) {
365 : 70 : freq = f;
366 : 70 : lbound = l;
367 : 70 : ubound = u;
368 : : } else {
369 : 70 : freq += f;
370 [ + + ]: 70 : if (l < lbound) lbound = l;
371 [ + + ]: 70 : if (u > ubound) ubound = u;
372 : : }
373 : :
374 : 140 : pq.pop();
375 [ + - ]: 140 : if (cur->next()) {
376 : 140 : pq.push(cur);
377 : : } else {
378 [ # # ]: 0 : delete cur;
379 : : }
380 : : }
381 : :
382 [ + + ]: 11 : if (freq) {
383 : 5 : out->add(last_key, encode_valuestats(freq, lbound, ubound));
384 : 11 : }
385 : : }
386 : :
387 : : // Merge valuestream chunks.
388 [ + - ]: 157 : while (!pq.empty()) {
389 : 157 : PostlistCursor * cur = pq.top();
390 : 157 : const string & key = cur->key;
391 [ + + ]: 157 : if (!is_valuechunk_key(key)) break;
392 : : Assert(!is_user_metadata_key(key));
393 : 146 : out->add(key, cur->tag);
394 : 146 : pq.pop();
395 [ + - ]: 146 : if (cur->next()) {
396 : 146 : pq.push(cur);
397 : : } else {
398 [ # # ]: 0 : delete cur;
399 : : }
400 : : }
401 : :
402 : 11 : Xapian::termcount tf = 0, cf = 0; // Initialise to avoid warnings.
403 : 11 : vector<pair<Xapian::docid, string> > tags;
404 : 963 : while (true) {
405 : 974 : PostlistCursor * cur = NULL;
406 [ + + ]: 974 : if (!pq.empty()) {
407 : 963 : cur = pq.top();
408 : 963 : pq.pop();
409 : : }
410 : : Assert(cur == NULL || !is_user_metadata_key(cur->key));
411 [ + + ][ + + ]: 974 : if (cur == NULL || cur->key != last_key) {
[ + + ]
412 [ + + ]: 757 : if (!tags.empty()) {
413 : 746 : string first_tag;
414 : 746 : pack_uint(first_tag, tf);
415 : 746 : pack_uint(first_tag, cf);
416 : 746 : pack_uint(first_tag, tags[0].first - 1);
417 : 746 : string tag = tags[0].second;
418 [ + + ]: 746 : tag[0] = (tags.size() == 1) ? '1' : '0';
419 : 746 : first_tag += tag;
420 : 746 : out->add(last_key, first_tag);
421 : :
422 : 746 : string term;
423 [ + + ]: 746 : if (!is_doclenchunk_key(last_key)) {
424 : 735 : const char * p = last_key.data();
425 : 735 : const char * end = p + last_key.size();
426 [ + - - + ]: 735 : if (!unpack_string_preserving_sort(&p, end, term) || p != end)
[ - + ]
427 : 0 : throw Xapian::DatabaseCorruptError("Bad postlist chunk key");
428 : : }
429 : :
430 : 746 : vector<pair<Xapian::docid, string> >::const_iterator i;
431 : 746 : i = tags.begin();
432 [ + + ]: 963 : while (++i != tags.end()) {
433 : 217 : tag = i->second;
434 [ + + ]: 217 : tag[0] = (i + 1 == tags.end()) ? '1' : '0';
435 : 217 : out->add(pack_brass_postlist_key(term, i->first), tag);
436 : 746 : }
437 : : }
438 : 757 : tags.clear();
439 [ + + ]: 757 : if (cur == NULL) break;
440 : 746 : tf = cf = 0;
441 : 746 : last_key = cur->key;
442 : : }
443 : 963 : tf += cur->tf;
444 : 963 : cf += cur->cf;
445 : 963 : tags.push_back(make_pair(cur->firstdid, cur->tag));
446 [ + + ]: 963 : if (cur->next()) {
447 : 941 : pq.push(cur);
448 : : } else {
449 [ + - ]: 22 : delete cur;
450 : : }
451 : 11 : }
452 : 11 : }
453 : :
454 : : struct MergeCursor : public BrassCursor {
455 : 2 : MergeCursor(BrassTable *in) : BrassCursor(in) {
456 : 2 : find_entry(string());
457 : 2 : next();
458 : 2 : }
459 : :
460 : 2 : ~MergeCursor() {
461 [ + - ]: 2 : delete BrassCursor::get_table();
462 : 2 : }
463 : : };
464 : :
465 : : struct CursorGt {
466 : : /// Return true if and only if a's key is strictly greater than b's key.
467 : 0 : bool operator()(const BrassCursor *a, const BrassCursor *b) {
468 [ # # ]: 0 : if (b->after_end()) return false;
469 [ # # ]: 0 : if (a->after_end()) return true;
470 : 0 : return (a->current_key > b->current_key);
471 : : }
472 : : };
473 : :
474 : : static void
475 : 1 : merge_spellings(BrassTable * out,
476 : : vector<string>::const_iterator b,
477 : : vector<string>::const_iterator e)
478 : : {
479 : 1 : priority_queue<MergeCursor *, vector<MergeCursor *>, CursorGt> pq;
480 [ + + ]: 3 : for ( ; b != e; ++b) {
481 : 2 : BrassTable *in = new BrassTable("spelling", *b, true, DONT_COMPRESS, true);
482 : 2 : in->open();
483 [ + + ]: 2 : if (!in->empty()) {
484 : : // The MergeCursor takes ownership of BrassTable in and is
485 : : // responsible for deleting it.
486 : 1 : pq.push(new MergeCursor(in));
487 : : } else {
488 [ + - ]: 1 : delete in;
489 : : }
490 : : }
491 : :
492 [ + + ]: 6 : while (!pq.empty()) {
493 : 5 : MergeCursor * cur = pq.top();
494 : 5 : pq.pop();
495 : :
496 : 5 : string key = cur->current_key;
497 [ - + # # ]: 5 : if (pq.empty() || pq.top()->current_key > key) {
[ + - ]
498 : : // No need to merge the tags, just copy the (possibly compressed)
499 : : // tag value.
500 : 5 : bool compressed = cur->read_tag(true);
501 : 5 : out->add(key, cur->current_tag, compressed);
502 [ + + ]: 5 : if (cur->next()) {
503 : 4 : pq.push(cur);
504 : : } else {
505 [ + - ]: 1 : delete cur;
506 : : }
507 : 5 : continue;
508 : : }
509 : :
510 : : // Merge tag values with the same key:
511 : 0 : string tag;
512 [ # # ]: 0 : if (key[0] != 'W') {
513 : : // We just want the union of words, so copy over the first instance
514 : : // and skip any identical ones.
515 : : priority_queue<PrefixCompressedStringItor *,
516 : : vector<PrefixCompressedStringItor *>,
517 : 0 : PrefixCompressedStringItorGt> pqtag;
518 : : // Stick all the MergeCursor pointers in a vector because their
519 : : // current_tag members must remain valid while we're merging their
520 : : // tags, but we need to call next() on them all afterwards.
521 : 0 : vector<MergeCursor *> vec;
522 : 0 : vec.reserve(pq.size());
523 : :
524 : 0 : while (true) {
525 : 0 : cur->read_tag();
526 : 0 : pqtag.push(new PrefixCompressedStringItor(cur->current_tag));
527 : 0 : vec.push_back(cur);
528 [ # # # # ]: 0 : if (pq.empty() || pq.top()->current_key != key) break;
[ # # ]
529 : 0 : cur = pq.top();
530 : 0 : pq.pop();
531 : : }
532 : :
533 : 0 : PrefixCompressedStringWriter wr(tag);
534 : 0 : string lastword;
535 [ # # ]: 0 : while (!pqtag.empty()) {
536 : 0 : PrefixCompressedStringItor * it = pqtag.top();
537 : 0 : string word = **it;
538 [ # # ]: 0 : if (word != lastword) {
539 : 0 : lastword = word;
540 : 0 : wr.append(lastword);
541 : : }
542 : 0 : ++*it;
543 : 0 : pqtag.pop();
544 [ # # ]: 0 : if (!it->at_end()) {
545 : 0 : pqtag.push(it);
546 : : } else {
547 [ # # ]: 0 : delete it;
548 : : }
549 : : }
550 : :
551 : 0 : vector<MergeCursor *>::const_iterator i;
552 [ # # ]: 0 : for (i = vec.begin(); i != vec.end(); ++i) {
553 : 0 : cur = *i;
554 [ # # ]: 0 : if (cur->next()) {
555 : 0 : pq.push(cur);
556 : : } else {
557 [ # # ]: 0 : delete cur;
558 : : }
559 : 0 : }
560 : : } else {
561 : : // We want to sum the frequencies from tags for the same key.
562 : 0 : Xapian::termcount tot_freq = 0;
563 : 0 : while (true) {
564 : 0 : cur->read_tag();
565 : : Xapian::termcount freq;
566 : 0 : const char * p = cur->current_tag.data();
567 : 0 : const char * end = p + cur->current_tag.size();
568 [ # # # # ]: 0 : if (!unpack_uint_last(&p, end, &freq) || freq == 0) {
[ # # ]
569 : 0 : throw Xapian::DatabaseCorruptError("Bad spelling word freq");
570 : : }
571 : 0 : tot_freq += freq;
572 [ # # ]: 0 : if (cur->next()) {
573 : 0 : pq.push(cur);
574 : : } else {
575 [ # # ]: 0 : delete cur;
576 : : }
577 [ # # ][ # # ]: 0 : if (pq.empty() || pq.top()->current_key != key) break;
[ # # ]
578 : 0 : cur = pq.top();
579 : 0 : pq.pop();
580 : : }
581 : 0 : tag.resize(0);
582 : 0 : pack_uint_last(tag, tot_freq);
583 : : }
584 : 0 : out->add(key, tag);
585 : 1 : }
586 : 1 : }
587 : :
588 : : static void
589 : 1 : merge_synonyms(BrassTable * out,
590 : : vector<string>::const_iterator b,
591 : : vector<string>::const_iterator e)
592 : : {
593 : 1 : priority_queue<MergeCursor *, vector<MergeCursor *>, CursorGt> pq;
594 [ + + ]: 3 : for ( ; b != e; ++b) {
595 : 2 : BrassTable *in = new BrassTable("synonym", *b, true, DONT_COMPRESS, true);
596 : 2 : in->open();
597 [ + + ]: 2 : if (!in->empty()) {
598 : : // The MergeCursor takes ownership of BrassTable in and is
599 : : // responsible for deleting it.
600 : 1 : pq.push(new MergeCursor(in));
601 : : } else {
602 [ + - ]: 1 : delete in;
603 : : }
604 : : }
605 : :
606 [ + + ]: 2 : while (!pq.empty()) {
607 : 1 : MergeCursor * cur = pq.top();
608 : 1 : pq.pop();
609 : :
610 : 1 : string key = cur->current_key;
611 [ - + # # ]: 1 : if (pq.empty() || pq.top()->current_key > key) {
[ + - ]
612 : : // No need to merge the tags, just copy the (possibly compressed)
613 : : // tag value.
614 : 1 : bool compressed = cur->read_tag(true);
615 : 1 : out->add(key, cur->current_tag, compressed);
616 [ - + ]: 1 : if (cur->next()) {
617 : 0 : pq.push(cur);
618 : : } else {
619 [ + - ]: 1 : delete cur;
620 : : }
621 : 1 : continue;
622 : : }
623 : :
624 : : // Merge tag values with the same key:
625 : 0 : string tag;
626 : :
627 : : // We just want the union of words, so copy over the first instance
628 : : // and skip any identical ones.
629 : : priority_queue<ByteLengthPrefixedStringItor *,
630 : : vector<ByteLengthPrefixedStringItor *>,
631 : 0 : ByteLengthPrefixedStringItorGt> pqtag;
632 : 0 : vector<MergeCursor *> vec;
633 : :
634 : 0 : while (true) {
635 : 0 : cur->read_tag();
636 : 0 : pqtag.push(new ByteLengthPrefixedStringItor(cur->current_tag));
637 : 0 : vec.push_back(cur);
638 [ # # # # ]: 0 : if (pq.empty() || pq.top()->current_key != key) break;
[ # # ]
639 : 0 : cur = pq.top();
640 : 0 : pq.pop();
641 : : }
642 : :
643 : 0 : string lastword;
644 [ # # ]: 0 : while (!pqtag.empty()) {
645 : 0 : ByteLengthPrefixedStringItor * it = pqtag.top();
646 [ # # ]: 0 : if (**it != lastword) {
647 : 0 : lastword = **it;
648 : 0 : tag += byte(lastword.size() ^ MAGIC_XOR_VALUE);
649 : 0 : tag += lastword;
650 : : }
651 : 0 : ++*it;
652 : 0 : pqtag.pop();
653 [ # # ]: 0 : if (!it->at_end()) {
654 : 0 : pqtag.push(it);
655 : : } else {
656 : 0 : delete it;
657 : : }
658 : : }
659 : :
660 : 0 : vector<MergeCursor *>::const_iterator i;
661 [ # # ]: 0 : for (i = vec.begin(); i != vec.end(); ++i) {
662 : 0 : cur = *i;
663 [ # # ]: 0 : if (cur->next()) {
664 : 0 : pq.push(cur);
665 : : } else {
666 [ # # ]: 0 : delete cur;
667 : : }
668 : : }
669 : :
670 : 0 : out->add(key, tag);
671 : 1 : }
672 : 1 : }
673 : :
674 : : static void
675 : 0 : multimerge_postlists(Xapian::Compactor & compactor,
676 : : BrassTable * out, const char * tmpdir,
677 : : Xapian::docid last_docid,
678 : : vector<string> tmp, vector<Xapian::docid> off)
679 : : {
680 : 0 : unsigned int c = 0;
681 [ # # ]: 0 : while (tmp.size() > 3) {
682 : 0 : vector<string> tmpout;
683 : 0 : tmpout.reserve(tmp.size() / 2);
684 : 0 : vector<Xapian::docid> newoff;
685 : 0 : newoff.resize(tmp.size() / 2);
686 [ # # ]: 0 : for (unsigned int i = 0, j; i < tmp.size(); i = j) {
687 : 0 : j = i + 2;
688 [ # # ]: 0 : if (j == tmp.size() - 1) ++j;
689 : :
690 : 0 : string dest = tmpdir;
691 : : char buf[64];
692 : 0 : sprintf(buf, "/tmp%u_%u.", c, i / 2);
693 : 0 : dest += buf;
694 : :
695 : : // Don't compress temporary tables, even if the final table would
696 : : // be.
697 : 0 : BrassTable tmptab("postlist", dest, false);
698 : : // Use maximum blocksize for temporary tables.
699 : 0 : tmptab.create_and_open(65536);
700 : :
701 : : merge_postlists(compactor, &tmptab, off.begin() + i,
702 : 0 : tmp.begin() + i, tmp.begin() + j, 0);
703 [ # # ]: 0 : if (c > 0) {
704 [ # # ]: 0 : for (unsigned int k = i; k < j; ++k) {
705 : 0 : unlink((tmp[k] + "DB").c_str());
706 : 0 : unlink((tmp[k] + "baseA").c_str());
707 : 0 : unlink((tmp[k] + "baseB").c_str());
708 : : }
709 : : }
710 : 0 : tmpout.push_back(dest);
711 : 0 : tmptab.flush_db();
712 : 0 : tmptab.commit(1);
713 : : }
714 : 0 : swap(tmp, tmpout);
715 : 0 : swap(off, newoff);
716 : 0 : ++c;
717 : : }
718 : : merge_postlists(compactor,
719 : 0 : out, off.begin(), tmp.begin(), tmp.end(), last_docid);
720 [ # # ]: 0 : if (c > 0) {
721 [ # # ]: 0 : for (size_t k = 0; k < tmp.size(); ++k) {
722 : 0 : unlink((tmp[k] + "DB").c_str());
723 : 0 : unlink((tmp[k] + "baseA").c_str());
724 : 0 : unlink((tmp[k] + "baseB").c_str());
725 : : }
726 : : }
727 : 0 : }
728 : :
729 : : static void
730 : 27 : merge_docid_keyed(const char * tablename,
731 : : BrassTable *out, const vector<string> & inputs,
732 : : const vector<Xapian::docid> & offset, bool lazy)
733 : : {
734 [ + + ]: 81 : for (size_t i = 0; i < inputs.size(); ++i) {
735 : 54 : Xapian::docid off = offset[i];
736 : :
737 : 54 : BrassTable in(tablename, inputs[i], true, DONT_COMPRESS, lazy);
738 : 54 : in.open();
739 [ - + ]: 54 : if (in.empty()) continue;
740 : :
741 : 54 : BrassCursor cur(&in);
742 : 54 : cur.find_entry(string());
743 : :
744 : 54 : string key;
745 [ + + ]: 21414 : while (cur.next()) {
746 : : // Adjust the key if this isn't the first database.
747 [ + + ]: 21360 : if (off) {
748 : : Xapian::docid did;
749 : 363 : const char * d = cur.current_key.data();
750 : 363 : const char * e = d + cur.current_key.size();
751 [ - + ]: 363 : if (!unpack_uint_preserving_sort(&d, e, &did)) {
752 : 0 : string msg = "Bad key in ";
753 : 0 : msg += inputs[i];
754 : 0 : throw Xapian::DatabaseCorruptError(msg);
755 : : }
756 : 363 : did += off;
757 : 363 : key.resize(0);
758 : 363 : pack_uint_preserving_sort(key, did);
759 [ + + ]: 363 : if (d != e) {
760 : : // Copy over the termname for the position table.
761 : 333 : key.append(d, e - d);
762 : : }
763 : : } else {
764 : 20997 : key = cur.current_key;
765 : : }
766 : 21360 : bool compressed = cur.read_tag(true);
767 : 21360 : out->add(key, cur.current_tag, compressed);
768 : : }
769 : : }
770 : 27 : }
771 : :
772 : : }
773 : :
774 : : using namespace BrassCompact;
775 : :
776 : : void
777 : 11 : compact_brass(Xapian::Compactor & compactor,
778 : : const char * destdir, const vector<string> & sources,
779 : : const vector<Xapian::docid> & offset, size_t block_size,
780 : : Xapian::Compactor::compaction_level compaction, bool multipass,
781 : : Xapian::docid last_docid) {
782 : : enum table_type {
783 : : POSTLIST, RECORD, TERMLIST, POSITION, VALUE, SPELLING, SYNONYM
784 : : };
785 : : struct table_list {
786 : : // The "base name" of the table.
787 : : const char * name;
788 : : // The type.
789 : : table_type type;
790 : : // zlib compression strategy to use on tags.
791 : : int compress_strategy;
792 : : // Create tables after position lazily.
793 : : bool lazy;
794 : : };
795 : :
796 : : static const table_list tables[] = {
797 : : // name type compress_strategy lazy
798 : : { "postlist", POSTLIST, DONT_COMPRESS, false },
799 : : { "record", RECORD, Z_DEFAULT_STRATEGY, false },
800 : : { "termlist", TERMLIST, Z_DEFAULT_STRATEGY, false },
801 : : { "position", POSITION, DONT_COMPRESS, true },
802 : : { "spelling", SPELLING, Z_DEFAULT_STRATEGY, true },
803 : : { "synonym", SYNONYM, Z_DEFAULT_STRATEGY, true }
804 : : };
805 : : const table_list * tables_end = tables +
806 : 11 : (sizeof(tables) / sizeof(tables[0]));
807 : :
808 [ + + ][ + + ]: 77 : for (const table_list * t = tables; t < tables_end; ++t) {
809 : : // The postlist table requires an N-way merge, adjusting the
810 : : // headers of various blocks. The spelling and synonym tables also
811 : : // need special handling. The other tables have keys sorted in
812 : : // docid order, so we can merge them by simply copying all the keys
813 : : // from each source table in turn.
814 : 66 : compactor.set_status(t->name, string());
815 : :
816 : 66 : string dest = destdir;
817 : 66 : dest += '/';
818 : 66 : dest += t->name;
819 : 66 : dest += '.';
820 : :
821 : 66 : bool output_will_exist = !t->lazy;
822 : :
823 : : // Sometimes stat can fail for benign reasons (e.g. >= 2GB file
824 : : // on certain systems).
825 : 66 : bool bad_stat = false;
826 : :
827 : 66 : off_t in_size = 0;
828 : :
829 : 66 : vector<string> inputs;
830 : 66 : inputs.reserve(sources.size());
831 : 66 : size_t inputs_present = 0;
832 [ + + ]: 198 : for (vector<string>::const_iterator src = sources.begin();
833 : : src != sources.end(); ++src) {
834 : 132 : string s(*src);
835 : 132 : s += t->name;
836 : 132 : s += '.';
837 : :
838 : : struct stat sb;
839 [ + + ]: 132 : if (stat(s + "DB", &sb) == 0) {
840 : 78 : in_size += sb.st_size / 1024;
841 : 78 : output_will_exist = true;
842 : 78 : ++inputs_present;
843 [ - + ]: 54 : } else if (errno != ENOENT) {
844 : : // We get ENOENT for an optional table.
845 : 0 : bad_stat = true;
846 : 0 : output_will_exist = true;
847 : 0 : ++inputs_present;
848 : : }
849 : 132 : inputs.push_back(s);
850 : : }
851 : :
852 : : // If any inputs lack a termlist table, suppress it in the output.
853 [ + + ][ - + ]: 66 : if (t->type == TERMLIST && inputs_present != sources.size()) {
[ - + ]
854 [ # # ]: 0 : if (inputs_present != 0) {
855 : 0 : string m = str(inputs_present);
856 : 0 : m += " of ";
857 : 0 : m += str(sources.size());
858 : 0 : m += " inputs present, so suppressing output";
859 : 0 : compactor.set_status(t->name, m);
860 : 0 : continue;
861 : : }
862 : 0 : output_will_exist = false;
863 : : }
864 : :
865 [ + + ]: 66 : if (!output_will_exist) {
866 : 26 : compactor.set_status(t->name, "doesn't exist");
867 : 26 : continue;
868 : : }
869 : :
870 : 40 : BrassTable out(t->name, dest, false, t->compress_strategy, t->lazy);
871 [ + + ]: 40 : if (!t->lazy) {
872 : 33 : out.create_and_open(block_size);
873 : : } else {
874 : 7 : out.erase();
875 : 7 : out.set_block_size(block_size);
876 : : }
877 : :
878 : 40 : out.set_full_compaction(compaction != compactor.STANDARD);
879 [ - + ]: 40 : if (compaction == compactor.FULLER) out.set_max_item_size(1);
880 : :
881 [ + + + + ]: 40 : switch (t->type) {
882 : : case POSTLIST:
883 [ - + ][ # # ]: 11 : if (multipass && inputs.size() > 3) {
[ - + ]
884 : : multimerge_postlists(compactor, &out, destdir, last_docid,
885 : 0 : inputs, offset);
886 : : } else {
887 : : merge_postlists(compactor, &out, offset.begin(),
888 : : inputs.begin(), inputs.end(),
889 : 11 : last_docid);
890 : : }
891 : 11 : break;
892 : : case SPELLING:
893 : 1 : merge_spellings(&out, inputs.begin(), inputs.end());
894 : 1 : break;
895 : : case SYNONYM:
896 : 1 : merge_synonyms(&out, inputs.begin(), inputs.end());
897 : 1 : break;
898 : : default:
899 : : // Position, Record, Termlist
900 : 27 : merge_docid_keyed(t->name, &out, inputs, offset, t->lazy);
901 : : break;
902 : : }
903 : :
904 : : // Commit as revision 1.
905 : 40 : out.flush_db();
906 : 40 : out.commit(1);
907 : :
908 : 40 : off_t out_size = 0;
909 [ + - ]: 40 : if (!bad_stat) {
910 : : struct stat sb;
911 [ + - ]: 40 : if (stat(dest + "DB", &sb) == 0) {
912 : 40 : out_size = sb.st_size / 1024;
913 : : } else {
914 : 0 : bad_stat = (errno != ENOENT);
915 : : }
916 : : }
917 [ - + ]: 40 : if (bad_stat) {
918 : 0 : compactor.set_status(t->name, "Done (couldn't stat all the DB files)");
919 : : } else {
920 : 40 : string status;
921 [ + + ]: 40 : if (out_size == in_size) {
922 : 5 : status = "Size unchanged (";
923 : : } else {
924 : : off_t delta;
925 [ + + ]: 35 : if (out_size < in_size) {
926 : 6 : delta = in_size - out_size;
927 : 6 : status = "Reduced by ";
928 : : } else {
929 : 29 : delta = out_size - in_size;
930 : 29 : status = "INCREASED by ";
931 : : }
932 : 35 : status += str(100 * delta / in_size);
933 : 35 : status += "% ";
934 : 35 : status += str(delta);
935 : 35 : status += "K (";
936 : 35 : status += str(in_size);
937 : 35 : status += "K -> ";
938 : : }
939 : 40 : status += str(out_size);
940 : 40 : status += "K)";
941 : 40 : compactor.set_status(t->name, status);
942 : : }
943 : : }
944 : 11 : }
|
