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