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
36RB_HEAD(map, mentry);
37
38struct mentry {
39	RB_ENTRY(mentry)	 mlink;
40	char			 mkey[KLEN];
41	struct bt_arg		*mval;
42};
43
44int		 mcmp(const struct mentry *, const struct mentry *);
45struct mentry	*mget(struct map *, const char *);
46
47RB_GENERATE(map, mentry, mlink, mcmp);
48
49int
50mcmp(const struct mentry *me0, const struct mentry *me1)
51{
52	return strncmp(me0->mkey, me1->mkey, KLEN - 1);
53}
54
55struct mentry *
56mget(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
74struct map *
75map_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
86void
87map_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
100void
101map_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
113struct bt_arg *
114map_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
125void
126map_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
135static int
136map_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. */
149void
150map_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
180void
181map_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 */
194struct hist {
195	struct map	hmap;
196	int		hstep;
197};
198
199struct hist *
200hist_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
212void
213hist_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
226long
227hist_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 */
268static inline int
269hist_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
300void
301hist_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