git.ozlabs.org Git - ccan/blob - ccan/strmap/strmap.c

   1 /* This code is based on ccan/strset.c. */
   2 #include <ccan/strmap/strmap.h>
   3 #include <ccan/short_types/short_types.h>
   4 #include <ccan/str/str.h>
   5 #include <ccan/ilog/ilog.h>
   6 #include <assert.h>
   7 #include <stdlib.h>
   8
   9 struct node {
  10         /* These point to strings or nodes. */
  11         struct strmap child[2];
  12         /* The byte number where first bit differs. */
  13         size_t byte_num;
  14         /* The bit where these children differ. */
  15         u8 bit_num;
  16 };
  17
  18 /* Closest member to this in a non-empty map. */
  19 static struct strmap *closest(struct strmap *n, const char *member)
  20 {
  21         size_t len = strlen(member);
  22         const u8 *bytes = (const u8 *)member;
  23
  24         /* Anything with NULL value is a node. */
  25         while (!n->v) {
  26                 u8 direction = 0;
  27
  28                 if (n->u.n->byte_num < len) {
  29                         u8 c = bytes[n->u.n->byte_num];
  30                         direction = (c >> n->u.n->bit_num) & 1;
  31                 }
  32                 n = &n->u.n->child[direction];
  33         }
  34         return n;
  35 }
  36
  37 void *strmap_get_(const struct strmap *map, const char *member)
  38 {
  39         struct strmap *n;
  40
  41         /* Empty map? */
  42         if (!map->u.n)
  43                 return NULL;
  44         n = closest((struct strmap *)map, member);
  45         if (streq(member, n->u.s))
  46                 return n->v;
  47         return NULL;
  48 }
  49
  50 bool strmap_add_(struct strmap *map, const char *member, const void *value)
  51 {
  52         size_t len = strlen(member);
  53         const u8 *bytes = (const u8 *)member;
  54         struct strmap *n;
  55         struct node *newn;
  56         size_t byte_num;
  57         u8 bit_num, new_dir;
  58
  59         assert(value);
  60
  61         /* Empty map? */
  62         if (!map->u.n) {
  63                 map->u.s = member;
  64                 map->v = (void *)value;
  65                 return true;
  66         }
  67
  68         /* Find closest existing member. */
  69         n = closest(map, member);
  70
  71         /* Find where they differ. */
  72         for (byte_num = 0; n->u.s[byte_num] == member[byte_num]; byte_num++) {
  73                 if (member[byte_num] == '\0') {
  74                         /* All identical! */
  75                         return false;
  76                 }
  77         }
  78
  79         /* Find which bit differs (if we had ilog8, we'd use it) */
  80         bit_num = ilog32_nz((u8)n->u.s[byte_num] ^ bytes[byte_num]) - 1;
  81         assert(bit_num < CHAR_BIT);
  82
  83         /* Which direction do we go at this bit? */
  84         new_dir = ((bytes[byte_num]) >> bit_num) & 1;
  85
  86         /* Allocate new node. */
  87         newn = malloc(sizeof(*newn));
  88         if (!newn) {
  89                 /* FIXME */
  90                 return false;
  91         }
  92         newn->byte_num = byte_num;
  93         newn->bit_num = bit_num;
  94         newn->child[new_dir].v = (void *)value;
  95         newn->child[new_dir].u.s = member;
  96
  97         /* Find where to insert: not closest, but first which differs! */
  98         n = map;
  99         while (!n->v) {
 100                 u8 direction = 0;
 101
 102                 if (n->u.n->byte_num > byte_num)
 103                         break;
 104                 /* Subtle: bit numbers are "backwards" for comparison */
 105                 if (n->u.n->byte_num == byte_num && n->u.n->bit_num < bit_num)
 106                         break;
 107
 108                 if (n->u.n->byte_num < len) {
 109                         u8 c = bytes[n->u.n->byte_num];
 110                         direction = (c >> n->u.n->bit_num) & 1;
 111                 }
 112                 n = &n->u.n->child[direction];
 113         }
 114
 115         newn->child[!new_dir] = *n;
 116         n->u.n = newn;
 117         n->v = NULL;
 118         return true;
 119 }
 120
 121 char *strmap_del_(struct strmap *map, const char *member, void **valuep)
 122 {
 123         size_t len = strlen(member);
 124         const u8 *bytes = (const u8 *)member;
 125         struct strmap *parent = NULL, *n;
 126         const char *ret = NULL;
 127         u8 direction = 0; /* prevent bogus gcc warning. */
 128
 129         /* Empty map? */
 130         if (!map->u.n)
 131                 return NULL;
 132
 133         /* Find closest, but keep track of parent. */
 134         n = map;
 135         /* Anything with NULL value is a node. */
 136         while (!n->v) {
 137                 u8 c = 0;
 138
 139                 parent = n;
 140                 if (n->u.n->byte_num < len) {
 141                         c = bytes[n->u.n->byte_num];
 142                         direction = (c >> n->u.n->bit_num) & 1;
 143                 } else
 144                         direction = 0;
 145                 n = &n->u.n->child[direction];
 146         }
 147
 148         /* Did we find it? */
 149         if (!streq(member, n->u.s))
 150                 return NULL;
 151
 152         ret = n->u.s;
 153         if (valuep)
 154                 *valuep = n->v;
 155
 156         if (!parent) {
 157                 /* We deleted last node. */
 158                 map->u.n = NULL;
 159         } else {
 160                 struct node *old = parent->u.n;
 161                 /* Raise other node to parent. */
 162                 *parent = old->child[!direction];
 163                 free(old);
 164         }
 165
 166         return (char *)ret;
 167 }
 168
 169 static bool iterate(struct strmap n,
 170                     bool (*handle)(const char *, void *, void *), void *data)
 171 {
 172         if (n.v)
 173                 return handle(n.u.s, n.v, data);
 174
 175         return iterate(n.u.n->child[0], handle, data)
 176                 || iterate(n.u.n->child[1], handle, data);
 177 }
 178
 179 void strmap_iterate_(const struct strmap *map,
 180                      bool (*handle)(const char *, void *, void *), void *data)
 181 {
 182         /* Empty map? */
 183         if (!map->u.n)
 184                 return;
 185
 186         iterate(*map, handle, data);
 187 }
 188
 189 const struct strmap *strmap_prefix_(const struct strmap *map,
 190                                     const char *prefix)
 191 {
 192         const struct strmap *n, *top;
 193         size_t len = strlen(prefix);
 194         const u8 *bytes = (const u8 *)prefix;
 195
 196         /* Empty map -> return empty map. */
 197         if (!map->u.n)
 198                 return map;
 199
 200         top = n = map;
 201
 202         /* We walk to find the top, but keep going to check prefix matches. */
 203         while (!n->v) {
 204                 u8 c = 0, direction;
 205
 206                 if (n->u.n->byte_num < len)
 207                         c = bytes[n->u.n->byte_num];
 208
 209                 direction = (c >> n->u.n->bit_num) & 1;
 210                 n = &n->u.n->child[direction];
 211                 if (c)
 212                         top = n;
 213         }
 214
 215         if (!strstarts(n->u.s, prefix)) {
 216                 /* Convenient return for prefixes which do not appear in map. */
 217                 static const struct strmap empty_map;
 218                 return &empty_map;
 219         }
 220
 221         return top;
 222 }
 223
 224 static void clear(struct strmap n)
 225 {
 226         if (!n.v) {
 227                 clear(n.u.n->child[0]);
 228                 clear(n.u.n->child[1]);
 229                 free(n.u.n);
 230         }
 231 }
 232
 233 void strmap_clear_(struct strmap *map)
 234 {
 235         if (map->u.n)
 236                 clear(*map);
 237         map->u.n = NULL;
 238 }