| 1 |
|
| /* po_row.h - the one row shape every operator moves. |
| 2 |
|
| * |
| 3 |
|
| * This is phase 0's record decision arriving where it pays off. `where`, |
| 4 |
|
| * `by`, `count` and `p95` are ONE implementation each because a log line is a |
| 5 |
|
| * row and a span is a row and a metric point is a row. The signals differ in |
| 6 |
|
| * which fields are populated, not in what a row is. |
| 7 |
|
| * |
| 8 |
|
| * Strings are (pointer, length) into memory the caller owns for the life of |
| 9 |
|
| * the query - a segment mapping, or a seeded buffer. Nothing here allocates |
| 10 |
|
| * per row; a scan over a million rows must not be a million mallocs. |
| 11 |
|
| */ |
| 12 |
|
| #ifndef PO_ROW_H |
| 13 |
|
| #define PO_ROW_H |
| 14 |
|
| |
| 15 |
|
| #include "punk_observe/po_compat.h" |
| 16 |
|
| #include "punk_observe/po_rec.h" |
| 17 |
|
| |
| 18 |
|
| #define PO_ROW_ATTRS 8 |
| 19 |
|
| |
| 20 |
|
| typedef struct { |
| 21 |
|
| const char *key; size_t key_len; |
| 22 |
|
| const char *val; size_t val_len; |
| 23 |
|
| } po_kv; |
| 24 |
|
| |
| 25 |
|
| typedef struct { |
| 26 |
|
| po_u64 t; |
| 27 |
|
| int kind; /* PO_METRIC | PO_LOG | PO_SPAN */ |
| 28 |
|
| |
| 29 |
|
| double value; /* metric */ |
| 30 |
|
| int value_is_int; |
| 31 |
|
| po_u64 ivalue; |
| 32 |
|
| |
| 33 |
|
| const char *body; size_t body_len; /* log body, span name, metric name */ |
| 34 |
|
| uint16_t severity; /* log */ |
| 35 |
|
| po_u64 duration; /* span */ |
| 36 |
|
| uint8_t status, span_kind; /* span */ |
| 37 |
|
| |
| 38 |
|
| po_u64 trace_hi, trace_lo, span_id; |
| 39 |
|
| const char *service; size_t service_len; |
| 40 |
|
| |
| 41 |
|
| po_kv attr[PO_ROW_ATTRS]; |
| 42 |
|
| int nattr; |
| 43 |
|
| } po_row; |
| 44 |
|
| |
| 45 |
|
| /* An identifier the way a person typed it, as the two integers a row holds. |
| 46 |
|
| * |
| 47 |
|
| * BOTH SPELLINGS, because both are things somebody pastes: 32 hex characters |
| 48 |
|
| * is the wire form every other tool prints, and `<hi>-<lo>` decimal is what |
| 49 |
|
| * this UI's own links carry. A span id is a single decimal integer. |
| 50 |
|
| * |
| 51 |
|
| * Returns 0 for anything that is not an identifier at all, which the caller |
| 52 |
|
| * turns into a predicate that matches nothing - the same answer as before, |
| 53 |
|
| * but now reached because the input was not an id rather than because the |
| 54 |
|
| * column could not be read. |
| 55 |
|
| * |
| 56 |
|
| * The Perl side has the same parse in povw_trace_id_c, on SVs. This one is |
| 57 |
|
| * plain bytes so that the ROW layer can use it, and so the literal is parsed |
| 58 |
|
| * ONCE when the query is planned rather than once per row scanned. */ |
| 59 |
35 |
| static int po_parse_id(const char *p, size_t len, po_u64 *hi, po_u64 *lo) { |
| 60 |
35 |
| size_t i, start = 0, end; |
| 61 |
|
| |
| 62 |
35 |
| *hi = 0; *lo = 0; |
| 63 |
35 |
▶ | if (!p) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!p) return 0; |
0 |
35 |
35 |
|
| 64 |
35 |
▶ | while (start < len && (p[start] == ' ' || p[start] == '\t')) start++; |
Branch: 3 branches
| Branch | True | False | Total |
| while (start < len && (p[start] == ' ' || p[start] == '\t')) start++; |
35 |
0 |
35 |
| while (start < len && (p[start] == ' ' || p[start] == '\t')) start++; |
0 |
35 |
35 |
| while (start < len && (p[start] == ' ' || p[start] == '\t')) start++; |
0 |
35 |
35 |
|
| 65 |
35 |
| end = len; |
| 66 |
35 |
▶ | while (end > start && (p[end - 1] == ' ' || p[end - 1] == '\t')) end--; |
Branch: 3 branches
| Branch | True | False | Total |
| while (end > start && (p[end - 1] == ' ' || p[end - 1] == '\t')) end--; |
35 |
0 |
35 |
| while (end > start && (p[end - 1] == ' ' || p[end - 1] == '\t')) end--; |
0 |
35 |
35 |
| while (end > start && (p[end - 1] == ' ' || p[end - 1] == '\t')) end--; |
0 |
35 |
35 |
|
| 67 |
35 |
| p += start; |
| 68 |
35 |
| len = end - start; |
| 69 |
35 |
▶ | if (!len) return 0; |
Branch: 1 branch
| Branch | True | False | Total |
| if (!len) return 0; |
0 |
35 |
35 |
|
| 70 |
|
| |
| 71 |
35 |
▶ | if (len == 32) { /* the wire form */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (len == 32) { /* the wire form */ |
5 |
30 |
35 |
|
| 72 |
5 |
| po_u64 h = 0, l = 0; |
| 73 |
165 |
▶ | for (i = 0; i < 32; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < 32; i++) { |
160 |
5 |
165 |
|
| 74 |
|
| int d; |
| 75 |
160 |
| char c = p[i]; |
| 76 |
160 |
▶ | if (c >= '0' && c <= '9') d = c - '0'; |
Branch: 2 branches
| Branch | True | False | Total |
| if (c >= '0' && c <= '9') d = c - '0'; |
160 |
0 |
160 |
| if (c >= '0' && c <= '9') d = c - '0'; |
155 |
5 |
160 |
|
| 77 |
5 |
▶ | else if (c >= 'a' && c <= 'f') d = c - 'a' + 10; |
Branch: 2 branches
| Branch | True | False | Total |
| else if (c >= 'a' && c <= 'f') d = c - 'a' + 10; |
5 |
0 |
5 |
| else if (c >= 'a' && c <= 'f') d = c - 'a' + 10; |
5 |
0 |
5 |
|
| 78 |
0 |
▶ | else if (c >= 'A' && c <= 'F') d = c - 'A' + 10; |
Branch: 2 branches
| Branch | True | False | Total |
| else if (c >= 'A' && c <= 'F') d = c - 'A' + 10; |
0 |
0 |
0 |
| else if (c >= 'A' && c <= 'F') d = c - 'A' + 10; |
0 |
0 |
0 |
|
| 79 |
0 |
| else goto decimal; |
| 80 |
160 |
▶ | if (i < 16) h = (h << 4) | (po_u64)d; |
Branch: 1 branch
| Branch | True | False | Total |
| if (i < 16) h = (h << 4) | (po_u64)d; |
80 |
80 |
160 |
|
| 81 |
80 |
| else l = (l << 4) | (po_u64)d; |
| 82 |
|
| } |
| 83 |
5 |
| *hi = h; *lo = l; |
| 84 |
5 |
▶ | return (h || l) ? 1 : 0; /* an all-zero id is not one */ |
Branch: 2 branches
| Branch | True | False | Total |
| return (h || l) ? 1 : 0; /* an all-zero id is not one */ |
0 |
5 |
5 |
| return (h || l) ? 1 : 0; /* an all-zero id is not one */ |
0 |
0 |
0 |
|
| 85 |
|
| } |
| 86 |
|
| |
| 87 |
30 |
| decimal: |
| 88 |
|
| { /* `<hi>-<lo>`, or a bare integer for a span id */ |
| 89 |
30 |
| size_t dash = 0; |
| 90 |
30 |
| int found = 0; |
| 91 |
30 |
| po_u64 a = 0, b = 0; |
| 92 |
125 |
▶ | for (i = 0; i < len; i++) if (p[i] == '-') { dash = i; found = 1; break; } |
Branch: 2 branches
| Branch | True | False | Total |
| for (i = 0; i < len; i++) if (p[i] == '-') { dash = i; found = 1; break; } |
15 |
95 |
110 |
| for (i = 0; i < len; i++) if (p[i] == '-') { dash = i; found = 1; break; } |
110 |
15 |
125 |
|
| 93 |
175 |
▶ | for (i = 0; i < len; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < len; i++) { |
145 |
30 |
175 |
|
| 94 |
145 |
▶ | if (found && i == dash) continue; |
Branch: 2 branches
| Branch | True | False | Total |
| if (found && i == dash) continue; |
85 |
60 |
145 |
| if (found && i == dash) continue; |
15 |
70 |
85 |
|
| 95 |
130 |
▶ | if (p[i] < '0' || p[i] > '9') return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (p[i] < '0' || p[i] > '9') return 0; |
130 |
0 |
130 |
| if (p[i] < '0' || p[i] > '9') return 0; |
0 |
130 |
130 |
|
| 96 |
|
| } |
| 97 |
30 |
▶ | if (!found) { |
Branch: 1 branch
| Branch | True | False | Total |
| if (!found) { |
15 |
15 |
30 |
|
| 98 |
75 |
▶ | for (i = 0; i < len; i++) b = b * 10 + (po_u64)(p[i] - '0'); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < len; i++) b = b * 10 + (po_u64)(p[i] - '0'); |
60 |
15 |
75 |
|
| 99 |
15 |
| *hi = 0; *lo = b; |
| 100 |
15 |
| return 1; |
| 101 |
|
| } |
| 102 |
15 |
▶ | if (!dash || dash + 1 >= len) return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!dash || dash + 1 >= len) return 0; |
15 |
0 |
15 |
| if (!dash || dash + 1 >= len) return 0; |
0 |
15 |
15 |
|
| 103 |
50 |
▶ | for (i = 0; i < dash; i++) a = a * 10 + (po_u64)(p[i] - '0'); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < dash; i++) a = a * 10 + (po_u64)(p[i] - '0'); |
35 |
15 |
50 |
|
| 104 |
50 |
▶ | for (i = dash + 1; i < len; i++) b = b * 10 + (po_u64)(p[i] - '0'); |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = dash + 1; i < len; i++) b = b * 10 + (po_u64)(p[i] - '0'); |
35 |
15 |
50 |
|
| 105 |
15 |
| *hi = a; *lo = b; |
| 106 |
15 |
▶ | return (a || b) ? 1 : 0; |
Branch: 2 branches
| Branch | True | False | Total |
| return (a || b) ? 1 : 0; |
0 |
15 |
15 |
| return (a || b) ? 1 : 0; |
0 |
0 |
0 |
|
| 107 |
|
| } |
| 108 |
|
| } |
| 109 |
|
| |
| 110 |
|
| /* Does this field name an identifier column? */ |
| 111 |
|
| #define PO_IS_TRACE_ID(f, n) ((n) == 8 && memcmp((f), "trace_id", 8) == 0) |
| 112 |
|
| #define PO_IS_SPAN_ID(f, n) ((n) == 7 && memcmp((f), "span_id", 7) == 0) |
| 113 |
|
| |
| 114 |
41263 |
| static const char *po_row_str(const po_row *r, const char *f, size_t flen, |
| 115 |
|
| size_t *out_len) { |
| 116 |
|
| int i; |
| 117 |
41263 |
▶ | if (flen == 4 && memcmp(f, "body", 4) == 0) { *out_len = r->body_len; return r->body; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 4 && memcmp(f, "body", 4) == 0) { *out_len = r->body_len; return r->body; } |
19 |
41244 |
41263 |
| if (flen == 4 && memcmp(f, "body", 4) == 0) { *out_len = r->body_len; return r->body; } |
14 |
5 |
19 |
|
| 118 |
41249 |
▶ | if (flen == 7 && memcmp(f, "service", 7) == 0) { *out_len = r->service_len; return r->service; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 7 && memcmp(f, "service", 7) == 0) { *out_len = r->service_len; return r->service; } |
33235 |
8014 |
41249 |
| if (flen == 7 && memcmp(f, "service", 7) == 0) { *out_len = r->service_len; return r->service; } |
33235 |
0 |
33235 |
|
| 119 |
8014 |
▶ | if (flen == 4 && memcmp(f, "name", 4) == 0) { *out_len = r->body_len; return r->body; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 4 && memcmp(f, "name", 4) == 0) { *out_len = r->body_len; return r->body; } |
5 |
8009 |
8014 |
| if (flen == 4 && memcmp(f, "name", 4) == 0) { *out_len = r->body_len; return r->body; } |
5 |
0 |
5 |
|
| 120 |
9007 |
▶ | for (i = 0; i < r->nattr; i++) |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < r->nattr; i++) |
3551 |
5456 |
9007 |
|
| 121 |
3551 |
▶ | if (r->attr[i].key_len == flen && memcmp(r->attr[i].key, f, flen) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (r->attr[i].key_len == flen && memcmp(r->attr[i].key, f, flen) == 0) { |
2743 |
808 |
3551 |
| if (r->attr[i].key_len == flen && memcmp(r->attr[i].key, f, flen) == 0) { |
2553 |
190 |
2743 |
|
| 122 |
2553 |
| *out_len = r->attr[i].val_len; |
| 123 |
2553 |
| return r->attr[i].val; |
| 124 |
|
| } |
| 125 |
5456 |
| *out_len = 0; |
| 126 |
5456 |
| return NULL; |
| 127 |
|
| } |
| 128 |
|
| |
| 129 |
|
| /* Numeric field access. Returns 1 if the field has a numeric meaning on this |
| 130 |
|
| * row, so a comparison against a missing field is FALSE rather than zero - |
| 131 |
|
| * `where duration > 0` must not match a row that has no duration. */ |
| 132 |
13808 |
| static int po_row_num(const po_row *r, const char *f, size_t flen, double *out) { |
| 133 |
13808 |
▶ | if (flen == 5 && memcmp(f, "value", 5) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 5 && memcmp(f, "value", 5) == 0) { |
504 |
13304 |
13808 |
| if (flen == 5 && memcmp(f, "value", 5) == 0) { |
372 |
132 |
504 |
|
| 134 |
372 |
▶ | *out = r->value_is_int ? (double)r->ivalue : r->value; |
Branch: 1 branch
| Branch | True | False | Total |
| *out = r->value_is_int ? (double)r->ivalue : r->value; |
0 |
372 |
372 |
|
| 135 |
372 |
| return r->kind == PO_METRIC; |
| 136 |
|
| } |
| 137 |
13436 |
▶ | if (flen == 8 && memcmp(f, "duration", 8) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 8 && memcmp(f, "duration", 8) == 0) { |
12898 |
538 |
13436 |
| if (flen == 8 && memcmp(f, "duration", 8) == 0) { |
4696 |
8202 |
12898 |
|
| 138 |
4696 |
| *out = (double)r->duration; |
| 139 |
4696 |
| return r->kind == PO_SPAN; |
| 140 |
|
| } |
| 141 |
8740 |
▶ | if (flen == 8 && memcmp(f, "severity", 8) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 8 && memcmp(f, "severity", 8) == 0) { |
8202 |
538 |
8740 |
| if (flen == 8 && memcmp(f, "severity", 8) == 0) { |
8202 |
0 |
8202 |
|
| 142 |
8202 |
| *out = (double)r->severity; |
| 143 |
8202 |
| return r->kind == PO_LOG; |
| 144 |
|
| } |
| 145 |
|
| /* THE TWO SPAN COLUMNS THE ROW COULD NOT ANSWER. |
| 146 |
|
| * |
| 147 |
|
| * `status` and `kind` are declared columns for the trace and span sources |
| 148 |
|
| * - the parser accepts them and validates them - and this function did |
| 149 |
|
| * not know either. So `where status == 2` compared against a field that |
| 150 |
|
| * did not exist, which is FALSE for every row: a filter for the failures |
| 151 |
|
| * matched nothing at all, on a store holding forty-seven of them, and |
| 152 |
|
| * said so by returning zero rather than by refusing. |
| 153 |
|
| * |
| 154 |
|
| * A column the language admits and the row cannot answer is worse than |
| 155 |
|
| * one it rejects: a rejected column is a message, an unanswerable one is |
| 156 |
|
| * an empty result that looks like an answer. */ |
| 157 |
538 |
▶ | if (flen == 6 && memcmp(f, "status", 6) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 6 && memcmp(f, "status", 6) == 0) { |
60 |
478 |
538 |
| if (flen == 6 && memcmp(f, "status", 6) == 0) { |
60 |
0 |
60 |
|
| 158 |
60 |
| *out = (double)r->status; |
| 159 |
60 |
| return r->kind == PO_SPAN; |
| 160 |
|
| } |
| 161 |
478 |
▶ | if (flen == 4 && memcmp(f, "kind", 4) == 0) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 4 && memcmp(f, "kind", 4) == 0) { |
23 |
455 |
478 |
| if (flen == 4 && memcmp(f, "kind", 4) == 0) { |
15 |
8 |
23 |
|
| 162 |
15 |
| *out = (double)r->span_kind; |
| 163 |
15 |
| return r->kind == PO_SPAN; |
| 164 |
|
| } |
| 165 |
463 |
▶ | if (flen == 1 && f[0] == 't') { *out = (double)r->t; return 1; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 1 && f[0] == 't') { *out = (double)r->t; return 1; } |
49 |
414 |
463 |
| if (flen == 1 && f[0] == 't') { *out = (double)r->t; return 1; } |
49 |
0 |
49 |
|
| 166 |
414 |
▶ | if (flen == 4 && memcmp(f, "time", 4) == 0) { *out = (double)r->t; return 1; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (flen == 4 && memcmp(f, "time", 4) == 0) { *out = (double)r->t; return 1; } |
8 |
406 |
414 |
| if (flen == 4 && memcmp(f, "time", 4) == 0) { *out = (double)r->t; return 1; } |
8 |
0 |
8 |
|
| 167 |
|
| { /* a numeric-looking attribute */ |
| 168 |
|
| size_t vl; |
| 169 |
406 |
| const char *v = po_row_str(r, f, flen, &vl); |
| 170 |
406 |
▶ | if (v && vl) { |
Branch: 2 branches
| Branch | True | False | Total |
| if (v && vl) { |
145 |
261 |
406 |
| if (v && vl) { |
145 |
0 |
145 |
|
| 171 |
145 |
| double acc = 0; size_t i; int any = 0, neg = 0, dot = 0; double frac = 0.1; |
| 172 |
145 |
▶ | for (i = 0; i < vl; i++) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (i = 0; i < vl; i++) { |
145 |
0 |
145 |
|
| 173 |
145 |
▶ | if (i == 0 && v[i] == '-') { neg = 1; continue; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (i == 0 && v[i] == '-') { neg = 1; continue; } |
145 |
0 |
145 |
| if (i == 0 && v[i] == '-') { neg = 1; continue; } |
0 |
145 |
145 |
|
| 174 |
145 |
▶ | if (v[i] == '.' && !dot) { dot = 1; continue; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (v[i] == '.' && !dot) { dot = 1; continue; } |
0 |
145 |
145 |
| if (v[i] == '.' && !dot) { dot = 1; continue; } |
0 |
0 |
0 |
|
| 175 |
145 |
▶ | if (v[i] < '0' || v[i] > '9') return 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (v[i] < '0' || v[i] > '9') return 0; |
138 |
7 |
145 |
| if (v[i] < '0' || v[i] > '9') return 0; |
138 |
0 |
138 |
|
| 176 |
0 |
▶ | if (!dot) acc = acc * 10 + (v[i] - '0'); |
Branch: 1 branch
| Branch | True | False | Total |
| if (!dot) acc = acc * 10 + (v[i] - '0'); |
0 |
0 |
0 |
|
| 177 |
0 |
| else { acc += (v[i] - '0') * frac; frac /= 10; } |
| 178 |
0 |
| any = 1; |
| 179 |
|
| } |
| 180 |
0 |
▶ | if (any) { *out = neg ? -acc : acc; return 1; } |
Branch: 2 branches
| Branch | True | False | Total |
| if (any) { *out = neg ? -acc : acc; return 1; } |
0 |
0 |
0 |
| if (any) { *out = neg ? -acc : acc; return 1; } |
0 |
0 |
0 |
|
| 181 |
|
| } |
| 182 |
|
| } |
| 183 |
261 |
| return 0; |
| 184 |
|
| } |
| 185 |
|
| |
| 186 |
|
| /* ---- ordering ------------------------------------------------------------ |
| 187 |
|
| * |
| 188 |
|
| * A row is 200-odd bytes and a result set is bounded by the planner's budget, |
| 189 |
|
| * so this sorts the ROWS rather than an index into them: one memcpy per swap |
| 190 |
|
| * against an indirection on every comparison and every read afterwards. |
| 191 |
|
| * |
| 192 |
|
| * A plain insertion sort would be quadratic on the case that matters - the |
| 193 |
|
| * store hands rows over in time order, and `slowest` wants them in duration |
| 194 |
|
| * order, so the input is arbitrary with respect to the key. This is a |
| 195 |
|
| * bottom-up merge, which is O(n log n) whatever the input looks like and, |
| 196 |
|
| * unlike quicksort, has no arrangement that degrades it. |
| 197 |
|
| */ |
| 198 |
|
| typedef int (*po_row_cmp_fn)(const po_row *a, const po_row *b, void *ud); |
| 199 |
|
| |
| 200 |
124 |
| static void po_rows_merge(po_row *src, po_row *dst, size_t lo, size_t mid, |
| 201 |
|
| size_t hi, po_row_cmp_fn cmp, void *ud) { |
| 202 |
124 |
| size_t i = lo, j = mid, k = lo; |
| 203 |
393 |
▶ | while (i < mid && j < hi) |
Branch: 2 branches
| Branch | True | False | Total |
| while (i < mid && j < hi) |
356 |
37 |
393 |
| while (i < mid && j < hi) |
269 |
87 |
356 |
|
| 204 |
269 |
▶ | dst[k++] = cmp(&src[j], &src[i], ud) < 0 ? src[j++] : src[i++]; |
Branch: 1 branch
| Branch | True | False | Total |
| dst[k++] = cmp(&src[j], &src[i], ud) < 0 ? src[j++] : src[i++]; |
158 |
111 |
269 |
|
| 205 |
341 |
▶ | while (i < mid) dst[k++] = src[i++]; |
Branch: 1 branch
| Branch | True | False | Total |
| while (i < mid) dst[k++] = src[i++]; |
217 |
124 |
341 |
|
| 206 |
186 |
▶ | while (j < hi) dst[k++] = src[j++]; |
Branch: 1 branch
| Branch | True | False | Total |
| while (j < hi) dst[k++] = src[j++]; |
62 |
124 |
186 |
|
| 207 |
124 |
| } |
| 208 |
|
| |
| 209 |
10 |
| static void po_rows_sort(po_row *rows, size_t n, po_row_cmp_fn cmp, void *ud) { |
| 210 |
10 |
| po_row *buf, *a = rows, *b; |
| 211 |
|
| size_t width; |
| 212 |
|
| |
| 213 |
10 |
▶ | if (n < 2) return; |
Branch: 1 branch
| Branch | True | False | Total |
| if (n < 2) return; |
0 |
10 |
10 |
|
| 214 |
10 |
| buf = (po_row *)malloc(n * sizeof(po_row)); |
| 215 |
10 |
▶ | if (!buf) return; /* unsorted beats not answering */ |
Branch: 1 branch
| Branch | True | False | Total |
| if (!buf) return; /* unsorted beats not answering */ |
0 |
10 |
10 |
|
| 216 |
10 |
| b = buf; |
| 217 |
|
| |
| 218 |
46 |
▶ | for (width = 1; width < n; width *= 2) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (width = 1; width < n; width *= 2) { |
36 |
10 |
46 |
|
| 219 |
|
| size_t lo; |
| 220 |
160 |
▶ | for (lo = 0; lo < n; lo += 2 * width) { |
Branch: 1 branch
| Branch | True | False | Total |
| for (lo = 0; lo < n; lo += 2 * width) { |
124 |
36 |
160 |
|
| 221 |
124 |
| size_t mid = lo + width < n ? lo + width : n; |
| 222 |
124 |
| size_t hi = lo + 2 * width < n ? lo + 2 * width : n; |
| 223 |
124 |
| po_rows_merge(a, b, lo, mid, hi, cmp, ud); |
| 224 |
|
| } |
| 225 |
36 |
| { po_row *t = a; a = b; b = t; } |
| 226 |
|
| } |
| 227 |
10 |
▶ | if (a != rows) memcpy(rows, a, n * sizeof(po_row)); |
Branch: 1 branch
| Branch | True | False | Total |
| if (a != rows) memcpy(rows, a, n * sizeof(po_row)); |
6 |
4 |
10 |
|
| 228 |
10 |
| free(buf); |
| 229 |
|
| } |
| 230 |
|
| |
| 231 |
|
| /* Longest first. A row with no duration - a log line, a metric point - sorts |
| 232 |
|
| * to the BOTTOM rather than being treated as zero-length, because "the |
| 233 |
|
| * slowest" of a set that has no durations in it is not the first row of it. */ |
| 234 |
97 |
| static int po_row_cmp_dur(const po_row *a, const po_row *b, void *ud) { |
| 235 |
97 |
▶ | po_u64 da = (a->kind == PO_SPAN) ? a->duration : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| po_u64 da = (a->kind == PO_SPAN) ? a->duration : 0; |
97 |
0 |
97 |
|
| 236 |
97 |
▶ | po_u64 db = (b->kind == PO_SPAN) ? b->duration : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| po_u64 db = (b->kind == PO_SPAN) ? b->duration : 0; |
97 |
0 |
97 |
|
| 237 |
|
| (void)ud; |
| 238 |
97 |
▶ | if (da != db) return da > db ? -1 : 1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (da != db) return da > db ? -1 : 1; |
93 |
4 |
97 |
| if (da != db) return da > db ? -1 : 1; |
84 |
9 |
93 |
|
| 239 |
|
| /* A stable tie-break, so two runs of the same query agree. */ |
| 240 |
4 |
▶ | if (a->t != b->t) return a->t > b->t ? -1 : 1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (a->t != b->t) return a->t > b->t ? -1 : 1; |
4 |
0 |
4 |
| if (a->t != b->t) return a->t > b->t ? -1 : 1; |
4 |
0 |
4 |
|
| 241 |
0 |
| return 0; |
| 242 |
|
| } |
| 243 |
|
| |
| 244 |
3 |
| static void po_rows_sort_dur(po_row *rows, uint32_t n) { |
| 245 |
3 |
| po_rows_sort(rows, (size_t)n, po_row_cmp_dur, NULL); |
| 246 |
3 |
| } |
| 247 |
|
| |
| 248 |
|
| /* `sort by <field>`, numerically where the field has a numeric meaning on |
| 249 |
|
| * both rows and by bytes otherwise - which is what makes `sort by service` |
| 250 |
|
| * and `sort by duration` both do the obvious thing. */ |
| 251 |
|
| typedef struct { const char *f; size_t flen; int desc; } po_row_sort_key; |
| 252 |
|
| |
| 253 |
172 |
| static int po_row_cmp_field(const po_row *a, const po_row *b, void *ud) { |
| 254 |
172 |
| po_row_sort_key *k = (po_row_sort_key *)ud; |
| 255 |
172 |
| double na = 0, nb = 0; |
| 256 |
172 |
| int ha = po_row_num(a, k->f, k->flen, &na); |
| 257 |
172 |
| int hb = po_row_num(b, k->f, k->flen, &nb); |
| 258 |
172 |
| int r = 0; |
| 259 |
|
| |
| 260 |
172 |
▶ | if (ha && hb) r = na < nb ? -1 : (na > nb ? 1 : 0); |
Branch: 3 branches
| Branch | True | False | Total |
| if (ha && hb) r = na < nb ? -1 : (na > nb ? 1 : 0); |
98 |
74 |
172 |
| if (ha && hb) r = na < nb ? -1 : (na > nb ? 1 : 0); |
98 |
0 |
98 |
| if (ha && hb) r = na < nb ? -1 : (na > nb ? 1 : 0); |
1 |
97 |
98 |
|
| 261 |
74 |
▶ | else if (ha != hb) r = ha ? -1 : 1; /* a row missing the field sorts last */ |
Branch: 2 branches
| Branch | True | False | Total |
| else if (ha != hb) r = ha ? -1 : 1; /* a row missing the field sorts last */ |
0 |
74 |
74 |
| else if (ha != hb) r = ha ? -1 : 1; /* a row missing the field sorts last */ |
0 |
0 |
0 |
|
| 262 |
|
| else { |
| 263 |
74 |
| size_t la = 0, lb = 0; |
| 264 |
74 |
| const char *sa = po_row_str(a, k->f, k->flen, &la); |
| 265 |
74 |
| const char *sb = po_row_str(b, k->f, k->flen, &lb); |
| 266 |
74 |
▶ | if (!sa && !sb) r = 0; |
Branch: 2 branches
| Branch | True | False | Total |
| if (!sa && !sb) r = 0; |
3 |
71 |
74 |
| if (!sa && !sb) r = 0; |
0 |
3 |
3 |
|
| 267 |
74 |
▶ | else if (!sa) r = 1; |
Branch: 1 branch
| Branch | True | False | Total |
| else if (!sa) r = 1; |
3 |
71 |
74 |
|
| 268 |
71 |
▶ | else if (!sb) r = -1; |
Branch: 1 branch
| Branch | True | False | Total |
| else if (!sb) r = -1; |
0 |
71 |
71 |
|
| 269 |
|
| else { |
| 270 |
71 |
| size_t n = la < lb ? la : lb; |
| 271 |
71 |
▶ | r = n ? memcmp(sa, sb, n) : 0; |
Branch: 1 branch
| Branch | True | False | Total |
| r = n ? memcmp(sa, sb, n) : 0; |
71 |
0 |
71 |
|
| 272 |
71 |
▶ | if (r == 0 && la != lb) r = la < lb ? -1 : 1; |
Branch: 3 branches
| Branch | True | False | Total |
| if (r == 0 && la != lb) r = la < lb ? -1 : 1; |
37 |
34 |
71 |
| if (r == 0 && la != lb) r = la < lb ? -1 : 1; |
0 |
37 |
37 |
| if (r == 0 && la != lb) r = la < lb ? -1 : 1; |
0 |
0 |
0 |
|
| 273 |
71 |
▶ | if (r) r = r < 0 ? -1 : 1; |
Branch: 2 branches
| Branch | True | False | Total |
| if (r) r = r < 0 ? -1 : 1; |
34 |
37 |
71 |
| if (r) r = r < 0 ? -1 : 1; |
26 |
8 |
34 |
|
| 274 |
|
| } |
| 275 |
|
| } |
| 276 |
172 |
▶ | if (r == 0) return a->t > b->t ? -1 : (a->t < b->t ? 1 : 0); |
Branch: 2 branches
| Branch | True | False | Total |
| if (r == 0) return a->t > b->t ? -1 : (a->t < b->t ? 1 : 0); |
37 |
135 |
172 |
| if (r == 0) return a->t > b->t ? -1 : (a->t < b->t ? 1 : 0); |
37 |
0 |
37 |
|
| 277 |
135 |
▶ | return k->desc ? -r : r; |
Branch: 1 branch
| Branch | True | False | Total |
| return k->desc ? -r : r; |
45 |
90 |
135 |
|
| 278 |
|
| } |
| 279 |
|
| |
| 280 |
7 |
| static void po_rows_sort_field(po_row *rows, uint32_t n, const char *f, |
| 281 |
|
| size_t flen, int desc) { |
| 282 |
|
| po_row_sort_key k; |
| 283 |
7 |
| k.f = f; k.flen = flen; k.desc = desc; |
| 284 |
7 |
| po_rows_sort(rows, (size_t)n, po_row_cmp_field, &k); |
| 285 |
7 |
| } |
| 286 |
|
| |
| 287 |
|
| #endif /* PO_ROW_H */ |