1 /* $OpenBSD: map.c,v 1.24 2023/09/11 19:01:26 mpi Exp $ */
2
3 /*
4 * Copyright (c) 2020 Martin Pieuchot <mpi@openbsd.org>
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 /*
20 * Associative array implemented with RB-Tree.
21 */
22
23 #include <sys/queue.h>
24 #include <sys/tree.h>
25
26 #include <assert.h>
27 #include <err.h>
28 #include <limits.h>
29 #include <stdlib.h>
30 #include <stdio.h>
31 #include <string.h>
32
33 #include "bt_parser.h"
34 #include "btrace.h"
35
36 RB_HEAD(map, mentry);
37
38 struct mentry {
39 RB_ENTRY(mentry) mlink;
40 char mkey[KLEN];
41 struct bt_arg *mval;
42 };
43
44 int mcmp(const struct mentry *, const struct mentry *);
45 struct mentry *mget(struct map *, const char *);
46
47 RB_GENERATE(map, mentry, mlink, mcmp);
48
49 int
mcmp(const struct mentry * me0,const struct mentry * me1)50 mcmp(const struct mentry *me0, const struct mentry *me1)
51 {
52 return strncmp(me0->mkey, me1->mkey, KLEN - 1);
53 }
54
55 struct mentry *
mget(struct map * map,const char * key)56 mget(struct map *map, const char *key)
57 {
58 struct mentry me, *mep;
59
60 strlcpy(me.mkey, key, KLEN);
61 mep = RB_FIND(map, map, &me);
62 if (mep == NULL) {
63 mep = calloc(1, sizeof(struct mentry));
64 if (mep == NULL)
65 err(1, "mentry: calloc");
66
67 strlcpy(mep->mkey, key, KLEN);
68 RB_INSERT(map, map, mep);
69 }
70
71 return mep;
72 }
73
74 struct map *
map_new(void)75 map_new(void)
76 {
77 struct map *map;
78
79 map = calloc(1, sizeof(struct map));
80 if (map == NULL)
81 err(1, "map: calloc");
82
83 return map;
84 }
85
86 void
map_clear(struct map * map)87 map_clear(struct map *map)
88 {
89 struct mentry *mep;
90
91 while ((mep = RB_MIN(map, map)) != NULL) {
92 RB_REMOVE(map, map, mep);
93 free(mep);
94 }
95
96 assert(RB_EMPTY(map));
97 free(map);
98 }
99
100 void
map_delete(struct map * map,const char * key)101 map_delete(struct map *map, const char *key)
102 {
103 struct mentry me, *mep;
104
105 strlcpy(me.mkey, key, KLEN);
106 mep = RB_FIND(map, map, &me);
107 if (mep != NULL) {
108 RB_REMOVE(map, map, mep);
109 free(mep);
110 }
111 }
112
113 struct bt_arg *
map_get(struct map * map,const char * key)114 map_get(struct map *map, const char *key)
115 {
116 struct mentry *mep;
117
118 mep = mget(map, key);
119 if (mep->mval == NULL)
120 mep->mval = ba_new(0, B_AT_LONG);
121
122 return mep->mval;
123 }
124
125 void
map_insert(struct map * map,const char * key,void * cookie)126 map_insert(struct map *map, const char *key, void *cookie)
127 {
128 struct mentry *mep;
129
130 mep = mget(map, key);
131 free(mep->mval);
132 mep->mval = cookie;
133 }
134
135 static int
map_cmp(const void * a,const void * b)136 map_cmp(const void *a, const void *b)
137 {
138 const struct mentry *ma = *(const struct mentry **)a;
139 const struct mentry *mb = *(const struct mentry **)b;
140 long rv;
141
142 rv = bacmp(ma->mval, mb->mval);
143 if (rv != 0)
144 return (rv > 0 ? -1 : 1);
145 return mcmp(ma, mb);
146 }
147
148 /* Print at most `top' entries of the map ordered by value. */
149 void
map_print(struct map * map,size_t top,const char * name)150 map_print(struct map *map, size_t top, const char *name)
151 {
152 struct mentry **elms, *mep;
153 size_t i, count = 0;
154
155 if (map == NULL)
156 return;
157
158 RB_FOREACH(mep, map, map)
159 count++;
160
161 elms = calloc(count, sizeof(*elms));
162 if (elms == NULL)
163 err(1, NULL);
164
165 count = 0;
166 RB_FOREACH(mep, map, map)
167 elms[count++] = mep;
168
169 qsort(elms, count, sizeof(*elms), map_cmp);
170
171 for (i = 0; i < top && i < count; i++) {
172 mep = elms[i];
173 printf("@%s[%s]: %s\n", name, mep->mkey,
174 ba2str(mep->mval, NULL));
175 }
176
177 free(elms);
178 }
179
180 void
map_zero(struct map * map)181 map_zero(struct map *map)
182 {
183 struct mentry *mep;
184
185 RB_FOREACH(mep, map, map) {
186 mep->mval->ba_value = 0;
187 mep->mval->ba_type = B_AT_LONG;
188 }
189 }
190
191 /*
192 * Histogram implemented with map.
193 */
194 struct hist {
195 struct map hmap;
196 int hstep;
197 };
198
199 struct hist *
hist_new(long step)200 hist_new(long step)
201 {
202 struct hist *hist;
203
204 hist = calloc(1, sizeof(struct hist));
205 if (hist == NULL)
206 err(1, "hist: calloc");
207 hist->hstep = step;
208
209 return hist;
210 }
211
212 void
hist_increment(struct hist * hist,const char * bucket)213 hist_increment(struct hist *hist, const char *bucket)
214 {
215 struct bt_arg *ba;
216 long val;
217
218 ba = map_get(&hist->hmap, bucket);
219
220 assert(ba->ba_type == B_AT_LONG);
221 val = (long)ba->ba_value;
222 val++;
223 ba->ba_value = (void *)val;
224 }
225
226 long
hist_get_bin_suffix(long bin,char ** suffix)227 hist_get_bin_suffix(long bin, char **suffix)
228 {
229 #define EXA (PETA * 1024)
230 #define PETA (TERA * 1024)
231 #define TERA (GIGA * 1024)
232 #define GIGA (MEGA * 1024)
233 #define MEGA (KILO * 1024)
234 #define KILO (1024LL)
235
236 *suffix = "";
237 if (bin >= EXA) {
238 bin /= EXA;
239 *suffix = "E";
240 }
241 if (bin >= PETA) {
242 bin /= PETA;
243 *suffix = "P";
244 }
245 if (bin >= TERA) {
246 bin /= TERA;
247 *suffix = "T";
248 }
249 if (bin >= GIGA) {
250 bin /= GIGA;
251 *suffix = "G";
252 }
253 if (bin >= MEGA) {
254 bin /= MEGA;
255 *suffix = "M";
256 }
257 if (bin >= KILO) {
258 bin /= KILO;
259 *suffix = "K";
260 }
261 return bin;
262 }
263
264 /*
265 * Print bucket header where `upb' is the upper bound of the interval
266 * and `hstep' the width of the interval.
267 */
268 static inline int
hist_print_bucket(char * buf,size_t buflen,long upb,long hstep)269 hist_print_bucket(char *buf, size_t buflen, long upb, long hstep)
270 {
271 int l;
272
273 if (hstep != 0) {
274 /* Linear histogram */
275 l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb);
276 } else {
277 /* Power-of-two histogram */
278 if (upb < 0) {
279 l = snprintf(buf, buflen, "(..., 0)");
280 } else if (upb == 0) {
281 l = snprintf(buf, buflen, "[%lu]", upb);
282 } else {
283 long lob = upb / 2;
284 char *lsuf, *usuf;
285
286 upb = hist_get_bin_suffix(upb, &usuf);
287 lob = hist_get_bin_suffix(lob, &lsuf);
288
289 l = snprintf(buf, buflen, "[%lu%s, %lu%s)",
290 lob, lsuf, upb, usuf);
291 }
292 }
293
294 if (l < 0 || (size_t)l > buflen)
295 warn("string too long %d > %lu", l, sizeof(buf));
296
297 return l;
298 }
299
300 void
hist_print(struct hist * hist,const char * name)301 hist_print(struct hist *hist, const char *name)
302 {
303 struct map *map = &hist->hmap;
304 static char buf[80];
305 struct mentry *mep, *mcur;
306 long bmin, bprev, bin, val, max = 0;
307 int i, l, length = 52;
308
309 if (map == NULL)
310 return;
311
312 bprev = 0;
313 RB_FOREACH(mep, map, map) {
314 val = ba2long(mep->mval, NULL);
315 if (val > max)
316 max = val;
317 }
318 printf("@%s:\n", name);
319
320 /*
321 * Sort by ascending key.
322 */
323 bprev = -1;
324 for (;;) {
325 mcur = NULL;
326 bmin = LONG_MAX;
327
328 RB_FOREACH(mep, map, map) {
329 bin = atol(mep->mkey);
330 if ((bin <= bmin) && (bin > bprev)) {
331 mcur = mep;
332 bmin = bin;
333 }
334 }
335 if (mcur == NULL)
336 break;
337
338 bin = atol(mcur->mkey);
339 val = ba2long(mcur->mval, NULL);
340 i = (length * val) / max;
341 l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep);
342 snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|",
343 20 - l, val,
344 i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@",
345 length - i, "");
346 printf("%s\n", buf);
347
348 bprev = bin;
349 }
350 }
351