1 /* $OpenBSD: map.c,v 1.8 2020/07/11 14:52:14 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 #ifndef MIN 37 #define MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b)) 38 #endif 39 40 #ifndef MAX 41 #define MAX(_a,_b) ((_a) > (_b) ? (_a) : (_b)) 42 #endif 43 44 RB_HEAD(map, mentry); 45 46 #define KLEN 256 47 48 struct mentry { 49 RB_ENTRY(mentry) mlink; 50 char mkey[KLEN]; 51 struct bt_arg *mval; 52 }; 53 54 int mcmp(struct mentry *, struct mentry *); 55 struct mentry *mget(struct map *, const char *); 56 57 RB_GENERATE(map, mentry, mlink, mcmp); 58 59 int 60 mcmp(struct mentry *me0, struct mentry *me1) 61 { 62 return strncmp(me0->mkey, me1->mkey, KLEN - 1); 63 } 64 65 struct mentry * 66 mget(struct map *map, const char *key) 67 { 68 struct mentry me, *mep; 69 70 strlcpy(me.mkey, key, KLEN); 71 mep = RB_FIND(map, map, &me); 72 if (mep == NULL) { 73 mep = calloc(1, sizeof(struct mentry)); 74 if (mep == NULL) 75 err(1, "mentry: calloc"); 76 77 strlcpy(mep->mkey, key, KLEN); 78 RB_INSERT(map, map, mep); 79 } 80 81 return mep; 82 } 83 84 void 85 map_clear(struct map *map) 86 { 87 struct mentry *mep; 88 89 while ((mep = RB_MIN(map, map)) != NULL) { 90 RB_REMOVE(map, map, mep); 91 free(mep); 92 } 93 94 assert(RB_EMPTY(map)); 95 free(map); 96 } 97 98 void 99 map_delete(struct map *map, const char *key) 100 { 101 struct mentry me, *mep; 102 103 strlcpy(me.mkey, key, KLEN); 104 mep = RB_FIND(map, map, &me); 105 if (mep != NULL) { 106 RB_REMOVE(map, map, mep); 107 free(mep); 108 } 109 } 110 111 struct bt_arg * 112 map_get(struct map *map, const char *key) 113 { 114 struct mentry *mep; 115 116 mep = mget(map, key); 117 if (mep->mval == NULL) 118 mep->mval = ba_new(0, B_AT_LONG); 119 120 return mep->mval; 121 } 122 123 struct map * 124 map_insert(struct map *map, const char *key, struct bt_arg *bval, 125 struct dt_evt *dtev) 126 { 127 struct mentry *mep; 128 long val; 129 130 if (map == NULL) { 131 map = calloc(1, sizeof(struct map)); 132 if (map == NULL) 133 err(1, "map: calloc"); 134 } 135 136 mep = mget(map, key); 137 switch (bval->ba_type) { 138 case B_AT_STR: 139 case B_AT_LONG: 140 free(mep->mval); 141 mep->mval = bval; 142 break; 143 case B_AT_BI_RETVAL: 144 free(mep->mval); 145 mep->mval = ba_new(ba2long(bval, dtev), B_AT_LONG); 146 break; 147 case B_AT_MF_COUNT: 148 if (mep->mval == NULL) 149 mep->mval = ba_new(0, B_AT_LONG); 150 val = (long)mep->mval->ba_value; 151 val++; 152 mep->mval->ba_value = (void *)val; 153 break; 154 case B_AT_MF_MAX: 155 if (mep->mval == NULL) 156 mep->mval = ba_new(0, B_AT_LONG); 157 val = (long)mep->mval->ba_value; 158 val = MAX(val, ba2long(bval->ba_value, dtev)); 159 mep->mval->ba_value = (void *)val; 160 break; 161 case B_AT_MF_MIN: 162 if (mep->mval == NULL) 163 mep->mval = ba_new(0, B_AT_LONG); 164 val = (long)mep->mval->ba_value; 165 val = MIN(val, ba2long(bval->ba_value, dtev)); 166 mep->mval->ba_value = (void *)val; 167 break; 168 case B_AT_MF_SUM: 169 if (mep->mval == NULL) 170 mep->mval = ba_new(0, B_AT_LONG); 171 val = (long)mep->mval->ba_value; 172 val += ba2long(bval->ba_value, dtev); 173 mep->mval->ba_value = (void *)val; 174 break; 175 default: 176 errx(1, "no insert support for type %d", bval->ba_type); 177 } 178 179 return map; 180 } 181 182 static struct bt_arg nullba = BA_INITIALIZER(0, B_AT_LONG); 183 static struct bt_arg maxba = BA_INITIALIZER(LONG_MAX, B_AT_LONG); 184 185 /* Print at most `top' entries of the map ordered by value. */ 186 void 187 map_print(struct map *map, size_t top, const char *name) 188 { 189 struct mentry *mep, *mcur; 190 struct bt_arg *bhigh, *bprev; 191 size_t i; 192 193 if (map == NULL) 194 return; 195 196 bprev = &maxba; 197 for (i = 0; i < top; i++) { 198 mcur = NULL; 199 bhigh = &nullba; 200 RB_FOREACH(mep, map, map) { 201 if (bacmp(mep->mval, bhigh) >= 0 && 202 bacmp(mep->mval, bprev) < 0 && 203 mep->mval != bprev) { 204 mcur = mep; 205 bhigh = mcur->mval; 206 } 207 } 208 if (mcur == NULL) 209 break; 210 printf("@%s[%s]: %s\n", name, mcur->mkey, 211 ba2str(mcur->mval, NULL)); 212 bprev = mcur->mval; 213 } 214 } 215 216 void 217 map_zero(struct map *map) 218 { 219 struct mentry *mep; 220 221 RB_FOREACH(mep, map, map) { 222 mep->mval->ba_value = 0; 223 mep->mval->ba_type = B_AT_LONG; 224 } 225 } 226 227 /* 228 * Histogram implemmented with map. 229 */ 230 231 struct hist { 232 struct map hmap; 233 int hstep; 234 }; 235 236 struct hist * 237 hist_increment(struct hist *hist, const char *key, long step) 238 { 239 static struct bt_arg incba = BA_INITIALIZER(NULL, B_AT_MF_COUNT); 240 241 if (hist == NULL) { 242 hist = calloc(1, sizeof(struct hist)); 243 if (hist == NULL) 244 err(1, "hist: calloc"); 245 hist->hstep = step; 246 } 247 assert(hist->hstep == step); 248 249 return (struct hist *)map_insert(&hist->hmap, key, &incba, NULL); 250 } 251 252 long 253 hist_get_bin_suffix(long bin, char **suffix) 254 { 255 #define GIGA (MEGA * 1024) 256 #define MEGA (KILO * 1024) 257 #define KILO (1024) 258 259 *suffix = ""; 260 if (bin >= GIGA) { 261 bin /= GIGA; 262 *suffix = "G"; 263 } 264 if (bin >= MEGA) { 265 bin /= MEGA; 266 *suffix = "M"; 267 } 268 if (bin >= KILO) { 269 bin /= KILO; 270 *suffix = "K"; 271 } 272 273 return bin; 274 #undef MEGA 275 #undef KILO 276 } 277 278 /* 279 * Print bucket header where `upb' is the upper bound of the interval 280 * and `hstep' the width of the interval. 281 */ 282 static inline int 283 hist_print_bucket(char *buf, size_t buflen, long upb, long hstep) 284 { 285 int l; 286 287 if (hstep != 0) { 288 /* Linear histogram */ 289 l = snprintf(buf, buflen, "[%lu, %lu)", upb - hstep, upb); 290 } else { 291 /* Power-of-two histogram */ 292 if (upb < 0) { 293 l = snprintf(buf, buflen, "(..., 0)"); 294 } else if (upb < 2) { 295 l = snprintf(buf, buflen, "[%lu]", upb); 296 } else { 297 long lob = upb / 2; 298 char *lsuf, *usuf; 299 300 upb = hist_get_bin_suffix(upb, &usuf); 301 lob = hist_get_bin_suffix(lob, &lsuf); 302 303 l = snprintf(buf, buflen, "[%lu%s, %lu%s)", 304 lob, lsuf, upb, usuf); 305 } 306 } 307 308 if (l < 0 || (size_t)l > buflen) 309 warn("string too long %d > %lu", l, sizeof(buf)); 310 311 return l; 312 } 313 314 void 315 hist_print(struct hist *hist, const char *name) 316 { 317 struct map *map = &hist->hmap; 318 static char buf[80]; 319 struct mentry *mep, *mcur; 320 long bmin, bprev, bin, val, max = 0; 321 int i, l, length = 52; 322 323 if (map == NULL) 324 return; 325 326 bprev = 0; 327 RB_FOREACH(mep, map, map) { 328 val = ba2long(mep->mval, NULL); 329 if (val > max) 330 max = val; 331 } 332 printf("@%s:\n", name); 333 334 /* 335 * Sort by ascending key. 336 */ 337 bprev = -1; 338 for (;;) { 339 mcur = NULL; 340 bmin = LONG_MAX; 341 342 RB_FOREACH(mep, map, map) { 343 bin = atol(mep->mkey); 344 if ((bin <= bmin) && (bin > bprev)) { 345 mcur = mep; 346 bmin = bin; 347 } 348 } 349 if (mcur == NULL) 350 break; 351 352 bin = atol(mcur->mkey); 353 val = ba2long(mcur->mval, NULL); 354 i = (length * val) / max; 355 l = hist_print_bucket(buf, sizeof(buf), bin, hist->hstep); 356 snprintf(buf + l, sizeof(buf) - l, "%*ld |%.*s%*s|", 357 20 - l, val, 358 i, "@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@", 359 length - i, ""); 360 printf("%s\n", buf); 361 362 bprev = bin; 363 } 364 } 365