This repository has been archived by the owner on Aug 13, 2019. It is now read-only.
-
Notifications
You must be signed in to change notification settings - Fork 180
/
postings.go
315 lines (261 loc) · 6.23 KB
/
postings.go
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
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
// Copyright 2017 The Prometheus Authors
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package tsdb
import (
"encoding/binary"
"sort"
"strings"
)
type memPostings struct {
m map[term][]uint32
}
type term struct {
name, value string
}
// Postings returns an iterator over the postings list for s.
func (p *memPostings) get(t term) Postings {
l := p.m[t]
if l == nil {
return emptyPostings
}
return &listPostings{list: l, idx: -1}
}
// add adds a document to the index. The caller has to ensure that no
// term argument appears twice.
func (p *memPostings) add(id uint32, terms ...term) {
for _, t := range terms {
p.m[t] = append(p.m[t], id)
}
}
// Postings provides iterative access over a postings list.
type Postings interface {
// Next advances the iterator and returns true if another value was found.
Next() bool
// Seek advances the iterator to value v or greater and returns
// true if a value was found.
Seek(v uint32) bool
// At returns the value at the current iterator position.
At() uint32
// Err returns the last error of the iterator.
Err() error
}
// errPostings is an empty iterator that always errors.
type errPostings struct {
err error
}
func (e errPostings) Next() bool { return false }
func (e errPostings) Seek(uint32) bool { return false }
func (e errPostings) At() uint32 { return 0 }
func (e errPostings) Err() error { return e.err }
func expandPostings(p Postings) (res []uint32, err error) {
for p.Next() {
res = append(res, p.At())
}
return res, p.Err()
}
// Intersect returns a new postings list over the intersection of the
// input postings.
func Intersect(its ...Postings) Postings {
if len(its) == 0 {
return errPostings{err: nil}
}
a := its[0]
for _, b := range its[1:] {
a = newIntersectPostings(a, b)
}
return a
}
var emptyPostings = errPostings{}
type intersectPostings struct {
a, b Postings
aok, bok bool
cur uint32
}
func newIntersectPostings(a, b Postings) *intersectPostings {
it := &intersectPostings{a: a, b: b}
it.aok = it.a.Next()
it.bok = it.b.Next()
return it
}
func (it *intersectPostings) At() uint32 {
return it.cur
}
func (it *intersectPostings) Next() bool {
for {
if !it.aok || !it.bok {
return false
}
av, bv := it.a.At(), it.b.At()
if av < bv {
it.aok = it.a.Seek(bv)
} else if bv < av {
it.bok = it.b.Seek(av)
} else {
it.cur = av
it.aok = it.a.Next()
it.bok = it.b.Next()
return true
}
}
}
func (it *intersectPostings) Seek(id uint32) bool {
it.aok = it.a.Seek(id)
it.bok = it.b.Seek(id)
return it.Next()
}
func (it *intersectPostings) Err() error {
if it.a.Err() != nil {
return it.a.Err()
}
return it.b.Err()
}
// Merge returns a new iterator over the union of the input iterators.
func Merge(its ...Postings) Postings {
if len(its) == 0 {
return nil
}
a := its[0]
for _, b := range its[1:] {
a = newMergePostings(a, b)
}
return a
}
type mergePostings struct {
a, b Postings
aok, bok bool
cur uint32
}
func newMergePostings(a, b Postings) *mergePostings {
it := &mergePostings{a: a, b: b}
it.aok = it.a.Next()
it.bok = it.b.Next()
return it
}
func (it *mergePostings) At() uint32 {
return it.cur
}
func (it *mergePostings) Next() bool {
if !it.aok && !it.bok {
return false
}
if !it.aok {
it.cur = it.b.At()
it.bok = it.b.Next()
return true
}
if !it.bok {
it.cur = it.a.At()
it.aok = it.a.Next()
return true
}
acur, bcur := it.a.At(), it.b.At()
if acur < bcur {
it.cur = acur
it.aok = it.a.Next()
return true
}
if bcur < acur {
it.cur = bcur
it.bok = it.b.Next()
return true
}
it.cur = acur
it.aok = it.a.Next()
it.bok = it.b.Next()
return true
}
func (it *mergePostings) Seek(id uint32) bool {
it.aok = it.a.Seek(id)
it.bok = it.b.Seek(id)
return it.Next()
}
func (it *mergePostings) Err() error {
if it.a.Err() != nil {
return it.a.Err()
}
return it.b.Err()
}
// listPostings implements the Postings interface over a plain list.
type listPostings struct {
list []uint32
idx int
}
func newListPostings(list []uint32) *listPostings {
return &listPostings{list: list, idx: -1}
}
func (it *listPostings) At() uint32 {
return it.list[it.idx]
}
func (it *listPostings) Next() bool {
it.idx++
return it.idx < len(it.list)
}
func (it *listPostings) Seek(x uint32) bool {
// Do binary search between current position and end.
it.idx += sort.Search(len(it.list)-it.idx, func(i int) bool {
return it.list[i+it.idx] >= x
})
return it.idx < len(it.list)
}
func (it *listPostings) Err() error {
return nil
}
// bigEndianPostings implements the Postings interface over a byte stream of
// big endian numbers.
type bigEndianPostings struct {
list []byte
idx int
}
func newBigEndianPostings(list []byte) *bigEndianPostings {
return &bigEndianPostings{list: list, idx: -1}
}
func (it *bigEndianPostings) At() uint32 {
idx := 4 * it.idx
return binary.BigEndian.Uint32(it.list[idx : idx+4])
}
func (it *bigEndianPostings) Next() bool {
it.idx++
return it.idx*4 < len(it.list)
}
func (it *bigEndianPostings) Seek(x uint32) bool {
num := len(it.list) / 4
// Do binary search between current position and end.
it.idx += sort.Search(num-it.idx, func(i int) bool {
idx := 4 * (it.idx + i)
val := binary.BigEndian.Uint32(it.list[idx : idx+4])
return val >= x
})
return it.idx*4 < len(it.list)
}
func (it *bigEndianPostings) Err() error {
return nil
}
type stringset map[string]struct{}
func (ss stringset) set(s string) {
ss[s] = struct{}{}
}
func (ss stringset) has(s string) bool {
_, ok := ss[s]
return ok
}
func (ss stringset) String() string {
return strings.Join(ss.slice(), ",")
}
func (ss stringset) slice() []string {
slice := make([]string, 0, len(ss))
for k := range ss {
slice = append(slice, k)
}
sort.Strings(slice)
return slice
}