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