1 /* $OpenBSD: map.c,v 1.3 2020/01/28 16:39:51 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(mtree, mentry); 45 46 #define KLEN 64 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 mtree *, const char *); 56 57 RB_GENERATE(mtree, 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 mtree *map, const char *key) 67 { 68 struct mentry me, *mep; 69 70 strlcpy(me.mkey, key, KLEN); 71 mep = RB_FIND(mtree, 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(mtree, map, mep); 79 } 80 81 return mep; 82 } 83 84 void 85 map_clear(struct bt_var *bv) 86 { 87 struct mtree *map = (struct mtree *)bv->bv_value; 88 struct mentry *mep; 89 90 while ((mep = RB_MIN(mtree, map)) != NULL) { 91 RB_REMOVE(mtree, map, mep); 92 free(mep); 93 } 94 95 assert(RB_EMPTY(map)); 96 free(map); 97 98 bv->bv_value = NULL; 99 } 100 101 void 102 map_delete(struct bt_var *bv, const char *key) 103 { 104 struct mtree *map = (struct mtree *)bv->bv_value; 105 struct mentry me, *mep; 106 107 strlcpy(me.mkey, key, KLEN); 108 mep = RB_FIND(mtree, map, &me); 109 if (mep != NULL) { 110 RB_REMOVE(mtree, map, mep); 111 free(mep); 112 } 113 } 114 115 struct bt_arg * 116 map_get(struct bt_var *bv, const char *key) 117 { 118 struct mtree *map = (struct mtree *)bv->bv_value; 119 struct mentry *mep; 120 121 mep = mget(map, key); 122 if (mep->mval == NULL) 123 mep->mval = ba_new(0, B_AT_LONG); 124 125 return mep->mval; 126 } 127 void 128 map_insert(struct bt_var *bv, const char *key, struct bt_arg *bval) 129 { 130 struct mtree *map = (struct mtree *)bv->bv_value; 131 struct mentry *mep; 132 long val; 133 134 if (map == NULL) { 135 map = calloc(1, sizeof(struct mtree)); 136 if (map == NULL) 137 err(1, "mtree: calloc"); 138 bv->bv_value = (struct bt_arg *)map; 139 } 140 141 mep = mget(map, key); 142 switch (bval->ba_type) { 143 case B_AT_STR: 144 case B_AT_LONG: 145 free(mep->mval); 146 mep->mval = bval; 147 break; 148 case B_AT_MF_COUNT: 149 if (mep->mval == NULL) 150 mep->mval = ba_new(0, B_AT_LONG); 151 val = (long)mep->mval->ba_value; 152 val++; 153 mep->mval->ba_value = (void *)val; 154 break; 155 case B_AT_MF_MAX: 156 if (mep->mval == NULL) 157 mep->mval = ba_new(0, B_AT_LONG); 158 val = (long)mep->mval->ba_value; 159 val = MAX(val, ba2long(bval->ba_value, NULL)); 160 mep->mval->ba_value = (void *)val; 161 break; 162 case B_AT_MF_MIN: 163 if (mep->mval == NULL) 164 mep->mval = ba_new(0, B_AT_LONG); 165 val = (long)mep->mval->ba_value; 166 val = MIN(val, ba2long(bval->ba_value, NULL)); 167 mep->mval->ba_value = (void *)val; 168 break; 169 case B_AT_MF_SUM: 170 if (mep->mval == NULL) 171 mep->mval = ba_new(0, B_AT_LONG); 172 val = (long)mep->mval->ba_value; 173 val += ba2long(bval->ba_value, NULL); 174 mep->mval->ba_value = (void *)val; 175 break; 176 default: 177 errx(1, "no insert support for type %d", bval->ba_type); 178 } 179 } 180 181 static struct bt_arg nullba = { {NULL }, (void *)0, NULL, B_AT_LONG }; 182 static struct bt_arg maxba = { { NULL }, (void *)LONG_MAX, NULL, B_AT_LONG }; 183 184 /* Print at most `top' entries of the map ordered by value. */ 185 void 186 map_print(struct bt_var *bv, size_t top) 187 { 188 struct mtree *map = (void *)bv->bv_value; 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, mtree, 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("@map[%s]: %s\n", mcur->mkey, ba2str(mcur->mval, NULL)); 211 bprev = mcur->mval; 212 } 213 } 214 215 void 216 map_zero(struct bt_var *bv) 217 { 218 struct mtree *map = (struct mtree *)bv->bv_value; 219 struct mentry *mep; 220 221 RB_FOREACH(mep, mtree, map) { 222 mep->mval->ba_value = 0; 223 mep->mval->ba_type = B_AT_LONG; 224 } 225 } 226