include/punk_observe/po_tsidx.h

filter: Statementstmt 99.0% 103 / 104 Branchbran 86.0% 74 / 86 Conditioncond n/a MC/DCmcdc n/a Subroutinesub n/a Podpod n/a totaltotal 93.1% 177 / 190 CC 0 SCAR 0
CC
0
Cov
0%
CRAP 0
« include/punk_observe/po_merge.h ↑ Summary include/punk_observe/po_gorilla.h »
1 /* po_tsidx.h - the inverted index: label pair to series.
2 *
3 * "service=api" -> [12, 15, 16, 17, 88, 91, ...]
4 * "http.route=/x" -> [15, 91, ...]
5 *
6 * `where service = "api" and http.route = "/x"` is an INTERSECTION of two
7 * sorted lists, smallest first, which is a linear merge needing no allocation
8 * beyond the output. That is the whole design.
9 *
10 * Stored gap-encoded: the gaps between consecutive ids are small, so varints
11 * make the list a fraction of its raw size, with a skip table every 128
12 * entries so an intersection can SEEK rather than scan.
13 *
14 * A roaring bitmap would beat this on very dense postings. It is not used,
15 * because postings here are sparse by construction - most label pairs belong
16 * to a small fraction of series - and a second compressed-set implementation
17 * is a second thing to get wrong. If profiling in phase 9 shows a dense case
18 * dominating, that is the moment to add it, with the number that justified it.
19 */
20 #ifndef PO_TSIDX_H
21 #define PO_TSIDX_H
22  
23 #include "punk_observe/po_compat.h"
24 #include "punk_observe/po_rec.h"
25  
26 #define PO_SKIP_EVERY 128
27  
28 /* ---- building ------------------------------------------------------------ */
29  
30 typedef struct {
31 uint32_t *id;
32 uint32_t n, cap;
33 int sorted;
34 } po_postings;
35  
36 106 static int po_postings_init(po_postings *p) {
37 106 memset(p, 0, sizeof(*p));
38 106 p->cap = 16;
39 106 p->id = (uint32_t *)malloc(p->cap * sizeof(uint32_t));
40 106 p->sorted = 1;
41 106 return p->id != NULL;
42 }
43  
44 106 static void po_postings_free(po_postings *p) {
45 106 free(p->id); p->id = NULL; p->n = p->cap = 0;
46 106 }
47  
48 78825 static int po_postings_add(po_postings *p, uint32_t id) {
49 78825 ▶ if (p->n == p->cap) {
Branch: 1 branch
BranchTrueFalseTotal
if (p->n == p->cap) { 466 78359 78825
50 466 uint32_t want = p->cap * 2;
51 466 uint32_t *ni = (uint32_t *)realloc(p->id, want * sizeof(uint32_t));
52 466 ▶ if (!ni) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!ni) return 0; 0 466 466
53 466 p->id = ni; p->cap = want;
54 }
55 78825 ▶ if (p->n && id <= p->id[p->n - 1]) p->sorted = 0;
Branch: 2 branches
BranchTrueFalseTotal
if (p->n && id <= p->id[p->n - 1]) p->sorted = 0; 78719 106 78825
if (p->n && id <= p->id[p->n - 1]) p->sorted = 0; 5 78714 78719
56 78825 p->id[p->n++] = id;
57 78825 return 1;
58 }
59  
60 21 static int po_u32cmp(const void *a, const void *b) {
61 21 uint32_t x = *(const uint32_t *)a, y = *(const uint32_t *)b;
62 21 ▶ return x < y ? -1 : (x > y ? 1 : 0);
Branch: 1 branch
BranchTrueFalseTotal
return x < y ? -1 : (x > y ? 1 : 0); 17 4 21
63 }
64  
65 /* Sort and dedupe. A series can carry the same label pair only once, but a
66 * caller feeding one record per point would add it repeatedly, so the list is
67 * made a set here rather than trusting every caller to. */
68 106 static void po_postings_finish(po_postings *p) {
69 106 uint32_t i, w = 0;
70 106 ▶ if (!p->sorted) qsort(p->id, p->n, sizeof(uint32_t), po_u32cmp);
Branch: 1 branch
BranchTrueFalseTotal
if (!p->sorted) qsort(p->id, p->n, sizeof(uint32_t), po_u32cmp); 1 105 106
71 78931 ▶ for (i = 0; i < p->n; i++)
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < p->n; i++) 78825 106 78931
72 78825 ▶ if (i == 0 || p->id[i] != p->id[i - 1]) p->id[w++] = p->id[i];
Branch: 2 branches
BranchTrueFalseTotal
if (i == 0 || p->id[i] != p->id[i - 1]) p->id[w++] = p->id[i]; 78719 106 78825
if (i == 0 || p->id[i] != p->id[i - 1]) p->id[w++] = p->id[i]; 78716 3 78719
73 106 p->n = w;
74 106 p->sorted = 1;
75 106 }
76  
77 /* Encode gap-varints plus a skip table.
78 *
79 * [varint count][skip count][ (u32 id, u32 bitoff) * skips ][gap varints]
80 */
81 106 static size_t po_postings_encode(const po_postings *p, char **out) {
82 106 size_t cap = 16 + (size_t)p->n * 5 + ((size_t)p->n / PO_SKIP_EVERY + 1) * 8;
83 106 char *b = (char *)malloc(cap);
84 106 size_t o = 0;
85 106 uint32_t i, prev = 0, skips = (p->n + PO_SKIP_EVERY - 1) / PO_SKIP_EVERY;
86 size_t skip_at;
87  
88 106 ▶ if (!b) { *out = NULL; return 0; }
Branch: 1 branch
BranchTrueFalseTotal
if (!b) { *out = NULL; return 0; } 0 106 106
89  
90 #define PUTV(v) do { po_u64 _v = (v); \
91 do { unsigned char _c = (unsigned char)(_v & 0x7F); _v >>= 7; \
92 if (_v) _c |= 0x80; b[o++] = (char)_c; } while (_v); } while (0)
93  
94 195 ▶ PUTV((po_u64)p->n);
Branch: 2 branches
BranchTrueFalseTotal
PUTV((po_u64)p->n); 89 106 195
PUTV((po_u64)p->n); 89 106 195
95 108 ▶ PUTV((po_u64)skips);
Branch: 2 branches
BranchTrueFalseTotal
PUTV((po_u64)skips); 2 106 108
PUTV((po_u64)skips); 2 106 108
96 106 skip_at = o;
97 106 o += (size_t)skips * 8; /* filled in as we go */
98  
99 78928 ▶ for (i = 0; i < p->n; i++) {
Branch: 1 branch
BranchTrueFalseTotal
for (i = 0; i < p->n; i++) { 78822 106 78928
100 78822 ▶ if (i % PO_SKIP_EVERY == 0) {
Branch: 1 branch
BranchTrueFalseTotal
if (i % PO_SKIP_EVERY == 0) { 673 78149 78822
101 673 uint32_t s = i / PO_SKIP_EVERY;
102 673 uint32_t v = po_le32(p->id[i]);
103 673 uint32_t f = po_le32((uint32_t)o);
104 673 memcpy(b + skip_at + (size_t)s * 8, &v, 4);
105 673 memcpy(b + skip_at + (size_t)s * 8 + 4, &f, 4);
106 1438 ▶ PUTV((po_u64)p->id[i]); /* skip entries store the id whole */
Branch: 2 branches
BranchTrueFalseTotal
PUTV((po_u64)p->id[i]); /* skip entries store the id whole */ 765 673 1438
PUTV((po_u64)p->id[i]); /* skip entries store the id whole */ 765 673 1438
107 }
108 79187 ▶ else PUTV((po_u64)(p->id[i] - prev));
Branch: 2 branches
BranchTrueFalseTotal
else PUTV((po_u64)(p->id[i] - prev)); 1038 78149 79187
else PUTV((po_u64)(p->id[i] - prev)); 1038 78149 79187
109 78822 prev = p->id[i];
110 }
111 #undef PUTV
112 106 *out = b;
113 106 return o;
114 }
115  
116 /* ---- reading ------------------------------------------------------------- */
117  
118 typedef struct {
119 const unsigned char *b;
120 size_t len, pos;
121 uint32_t n, i, prev;
122 const unsigned char *skip;
123 uint32_t skips;
124 } po_post_r;
125  
126 78764 static po_u64 po_getv(const unsigned char *b, size_t len, size_t *pos) {
127 78764 po_u64 v = 0; int sh = 0;
128 80610 ▶ while (*pos < len) {
Branch: 1 branch
BranchTrueFalseTotal
while (*pos < len) { 80610 0 80610
129 80610 unsigned char c = b[(*pos)++];
130 80610 v |= (po_u64)(c & 0x7F) << sh;
131 80610 ▶ if (!(c & 0x80)) return v;
Branch: 1 branch
BranchTrueFalseTotal
if (!(c & 0x80)) return v; 78764 1846 80610
132 1846 sh += 7;
133 1846 ▶ if (sh > 63) break;
Branch: 1 branch
BranchTrueFalseTotal
if (sh > 63) break; 0 1846 1846
134 }
135 0 return v;
136 }
137  
138 156 static int po_post_open(po_post_r *r, const void *buf, size_t len) {
139 156 size_t pos = 0;
140 156 const unsigned char *b = (const unsigned char *)buf;
141 156 memset(r, 0, sizeof(*r));
142 156 r->b = b; r->len = len;
143 156 r->n = (uint32_t)po_getv(b, len, &pos);
144 156 r->skips = (uint32_t)po_getv(b, len, &pos);
145 156 ▶ if (pos + (size_t)r->skips * 8 > len) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (pos + (size_t)r->skips * 8 > len) return 0; 0 156 156
146 156 r->skip = b + pos;
147 156 r->pos = pos + (size_t)r->skips * 8;
148 156 return 1;
149 }
150  
151 78558 static int po_post_next(po_post_r *r, uint32_t *id) {
152 78558 ▶ if (r->i >= r->n || r->pos >= r->len) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (r->i >= r->n || r->pos >= r->len) return 0; 78452 106 78558
if (r->i >= r->n || r->pos >= r->len) return 0; 0 78452 78452
153 {
154 78452 po_u64 v = po_getv(r->b, r->len, &r->pos);
155 78452 ▶ if (r->i % PO_SKIP_EVERY == 0) r->prev = (uint32_t)v;
Branch: 1 branch
BranchTrueFalseTotal
if (r->i % PO_SKIP_EVERY == 0) r->prev = (uint32_t)v; 703 77749 78452
156 77749 else r->prev = r->prev + (uint32_t)v;
157 }
158 78452 *id = r->prev;
159 78452 r->i++;
160 78452 return 1;
161 }
162  
163 /* Seek to the first id >= target, using the skip table to avoid decoding
164 * every gap. This is what makes an intersection sublinear on the larger list. */
165 15302 static int po_post_seek(po_post_r *r, uint32_t target, uint32_t *id) {
166 uint32_t s;
167 44166 ▶ for (s = r->skips; s > 0; s--) {
Branch: 1 branch
BranchTrueFalseTotal
for (s = r->skips; s > 0; s--) { 44166 0 44166
168 uint32_t sid, soff;
169 44166 memcpy(&sid, r->skip + (size_t)(s - 1) * 8, 4); sid = po_le32(sid);
170 44166 memcpy(&soff, r->skip + (size_t)(s - 1) * 8 + 4, 4); soff = po_le32(soff);
171 44166 ▶ if (sid <= target) {
Branch: 1 branch
BranchTrueFalseTotal
if (sid <= target) { 15302 28864 44166
172 15302 uint32_t block = s - 1;
173 15302 ▶ if (block * PO_SKIP_EVERY >= r->i) {
Branch: 1 branch
BranchTrueFalseTotal
if (block * PO_SKIP_EVERY >= r->i) { 113 15189 15302
174 113 r->i = block * PO_SKIP_EVERY;
175 113 r->pos = soff;
176 }
177 15302 break;
178 }
179 }
180 30417 ▶ while (po_post_next(r, id)) if (*id >= target) return 1;
Branch: 2 branches
BranchTrueFalseTotal
while (po_post_next(r, id)) if (*id >= target) return 1; 15265 15115 30380
while (po_post_next(r, id)) if (*id >= target) return 1; 30380 37 30417
181 37 return 0;
182 }
183  
184 /* Intersect two encoded lists. SMALLEST FIRST is the caller's job and it is
185 * the difference between a merge and a scan. */
186 50 static uint32_t po_post_intersect(const void *a, size_t alen,
187 const void *b, size_t blen,
188 uint32_t *out, uint32_t outmax) {
189 po_post_r ra, rb;
190 50 uint32_t ia, ib, n = 0;
191 50 ▶ if (!po_post_open(&ra, a, alen) || !po_post_open(&rb, b, blen)) return 0;
Branch: 2 branches
BranchTrueFalseTotal
if (!po_post_open(&ra, a, alen) || !po_post_open(&rb, b, blen)) return 0; 50 0 50
if (!po_post_open(&ra, a, alen) || !po_post_open(&rb, b, blen)) return 0; 0 50 50
192 50 ▶ if (!po_post_next(&ra, &ia)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_post_next(&ra, &ia)) return 0; 0 50 50
193 50 ▶ if (!po_post_next(&rb, &ib)) return 0;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_post_next(&rb, &ib)) return 0; 50 0 50
194 for (;;) {
195 16920 ▶ if (ia == ib) {
Branch: 1 branch
BranchTrueFalseTotal
if (ia == ib) { 1618 15302 16920
196 1618 ▶ if (n < outmax) out[n] = ia;
Branch: 1 branch
BranchTrueFalseTotal
if (n < outmax) out[n] = ia; 1618 0 1618
197 1618 n++;
198 1618 ▶ if (!po_post_next(&ra, &ia)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_post_next(&ra, &ia)) break; 6 1612 1618
199 1612 ▶ if (!po_post_next(&rb, &ib)) break;
Branch: 1 branch
BranchTrueFalseTotal
if (!po_post_next(&rb, &ib)) break; 7 1605 1612
200 }
201 15302 ▶ else if (ia < ib) { if (!po_post_seek(&ra, ib, &ia)) break; }
Branch: 2 branches
BranchTrueFalseTotal
else if (ia < ib) { if (!po_post_seek(&ra, ib, &ia)) break; } 7804 7498 15302
else if (ia < ib) { if (!po_post_seek(&ra, ib, &ia)) break; } 18 7786 7804
202 7498 ▶ else { if (!po_post_seek(&rb, ia, &ib)) break; }
Branch: 1 branch
BranchTrueFalseTotal
else { if (!po_post_seek(&rb, ia, &ib)) break; } 19 7479 7498
203 }
204 50 return n;
205 }
206  
207 #endif /* PO_TSIDX_H */
« include/punk_observe/po_merge.h ↑ Summary include/punk_observe/po_gorilla.h »