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 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 * 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 * 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 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 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 * 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 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 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 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 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 * 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 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 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 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 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