1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
|
/** @file
* @brief Metadata for a term in a document
*/
/* Copyright 2017,2018 Olly Betts
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
* published by the Free Software Foundation; either version 2 of the
* License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, see
* <https://www.gnu.org/licenses/>.
*/
#include <config.h>
#include "terminfo.h"
#include "omassert.h"
#include <algorithm>
#include <limits>
using namespace std;
void
TermInfo::merge() const
{
Assert(!is_deleted());
inplace_merge(positions.begin(),
positions.begin() + split,
positions.end());
split = 0;
}
bool
TermInfo::add_position(Xapian::termcount wdf_inc, Xapian::termpos termpos)
{
if (rare(is_deleted())) {
wdf = wdf_inc;
split = 0;
positions.push_back(termpos);
return true;
}
wdf += wdf_inc;
// Optimise the common case of adding positions in ascending order.
if (positions.empty()) {
positions.push_back(termpos);
return false;
}
if (termpos > positions.back()) {
if (split) {
// Check for duplicate before split.
auto i = lower_bound(positions.cbegin(),
positions.cbegin() + split,
termpos);
if (i != positions.cbegin() + split && *i == termpos)
return false;
}
positions.push_back(termpos);
return false;
}
if (termpos == positions.back()) {
// Duplicate of last entry.
return false;
}
if (split > 0) {
// We could merge in the new entry at the same time, but that seems to
// make things much more complex for minor gains.
merge();
}
// We keep positions sorted, so use lower_bound() which can binary chop to
// find the entry.
auto i = lower_bound(positions.cbegin(), positions.cend(), termpos);
// Add unless termpos is already in the list.
if (i == positions.cend() || *i != termpos) {
auto new_split = positions.size();
if constexpr(sizeof(split) < sizeof(Xapian::termpos)) {
if (rare(new_split > numeric_limits<decltype(split)>::max())) {
// The split point would be beyond the size of the type used to
// hold it, which is really unlikely if that type is 32-bit.
// Just insert the old way in this case.
positions.insert(i, termpos);
return false;
}
} else {
// This assertion should always be true because we shouldn't have
// duplicate entries and the split point can't be after the final
// entry.
AssertRel(new_split, <=, numeric_limits<decltype(split)>::max());
}
split = new_split;
positions.push_back(termpos);
}
return false;
}
bool
TermInfo::remove_position(Xapian::termpos termpos)
{
Assert(!is_deleted());
if (rare(positions.empty()))
return false;
// Special case removing the final position, which we can handle in O(1).
if (positions.back() == termpos) {
positions.pop_back();
if (split == positions.size()) {
split = 0;
// We removed the only entry from after the split.
}
return true;
}
if (split > 0) {
// We could remove the requested entry at the same time, but that seems
// fiddly to do.
merge();
}
// We keep positions sorted, so use lower_bound() which can binary chop to
// find the entry.
auto i = lower_bound(positions.cbegin(), positions.cend(), termpos);
if (i == positions.cend() || *i != termpos) {
// Not there.
return false;
}
positions.erase(i);
return true;
}
Xapian::termpos
TermInfo::remove_positions(Xapian::termpos termpos_first,
Xapian::termpos termpos_last)
{
Assert(!is_deleted());
if (split > 0) {
// We could remove the requested entries at the same time, but that
// seems fiddly to do.
merge();
}
// Find the range [i, j) that the specified termpos range maps to. Use
// binary chop to search, since this is a sorted list.
auto i = lower_bound(positions.cbegin(), positions.cend(), termpos_first);
if (i == positions.cend() || *i > termpos_last) {
return 0;
}
auto j = upper_bound(i, positions.cend(), termpos_last);
size_t size_before = positions.size();
positions.erase(i, j);
return Xapian::termpos(size_before - positions.size());
}
|
