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