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

   1 /* CC0 license (public domain) - see LICENSE file for details */
   2 /* This code is based on ccan/strmap.c. */
   3 #include <ccan/intmap/intmap.h>
   4 #include <ccan/short_types/short_types.h>
   5 #include <ccan/str/str.h>
   6 #include <ccan/ilog/ilog.h>
   7 #include <assert.h>
   8 #include <stdlib.h>
   9 #include <errno.h>
  10
  11 struct node {
  12         /* These point to strings or nodes. */
  13         struct intmap child[2];
  14         /* The bit where these children differ (0 == lsb) */
  15         u8 bit_num;
  16 };
  17
  18 /* Closest member to this in a non-empty map. */
  19 static struct intmap *closest(struct intmap *n, intmap_index_t index)
  20 {
  21         /* Anything with NULL value is a node. */
  22         while (!n->v) {
  23                 u8 direction = (index >> n->u.n->bit_num) & 1;
  24                 n = &n->u.n->child[direction];
  25         }
  26         return n;
  27 }
  28
  29 void *intmap_get_(const struct intmap *map, intmap_index_t index)
  30 {
  31         struct intmap *n;
  32
  33         /* Not empty map? */
  34         if (!intmap_empty_(map)) {
  35                 n = closest((struct intmap *)map, index);
  36                 if (index == n->u.i)
  37                         return n->v;
  38         }
  39         errno = ENOENT;
  40         return NULL;
  41 }
  42
  43 bool intmap_add_(struct intmap *map, intmap_index_t index, const void *value)
  44 {
  45         struct intmap *n;
  46         struct node *newn;
  47         u8 bit_num, new_dir;
  48
  49         assert(value);
  50
  51         /* Empty map? */
  52         if (intmap_empty_(map)) {
  53                 map->u.i = index;
  54                 map->v = (void *)value;
  55                 return true;
  56         }
  57
  58         /* Find closest existing member. */
  59         n = closest(map, index);
  60
  61         /* Find highest bit where they differ. */
  62         bit_num = ilog64(n->u.i ^ index);
  63         if (bit_num == 0) {
  64                 errno = EEXIST;
  65                 return false;
  66         }
  67         bit_num--;
  68
  69         assert(bit_num < CHAR_BIT*sizeof(index));
  70
  71         /* Which direction do we go at this bit? */
  72         new_dir = (index >> bit_num) & 1;
  73
  74         /* Allocate new node. */
  75         newn = malloc(sizeof(*newn));
  76         if (!newn) {
  77                 errno = ENOMEM;
  78                 return false;
  79         }
  80         newn->bit_num = bit_num;
  81         newn->child[new_dir].v = (void *)value;
  82         newn->child[new_dir].u.i = index;
  83
  84         /* Find where to insert: not closest, but first which differs! */
  85         n = map;
  86         while (!n->v) {
  87                 u8 direction;
  88
  89                 /* Subtle: bit numbers are "backwards" for comparison */
  90                 if (n->u.n->bit_num < bit_num)
  91                         break;
  92
  93                 direction = (index >> n->u.n->bit_num) & 1;
  94                 n = &n->u.n->child[direction];
  95         }
  96
  97         newn->child[!new_dir] = *n;
  98         n->u.n = newn;
  99         n->v = NULL;
 100         return true;
 101 }
 102
 103 void *intmap_del_(struct intmap *map, intmap_index_t index)
 104 {
 105         struct intmap *parent = NULL, *n;
 106         u8 direction;
 107         void *value;
 108
 109         /* Empty map? */
 110         if (intmap_empty_(map)) {
 111                 errno = ENOENT;
 112                 return NULL;
 113         }
 114
 115         /* Find closest, but keep track of parent. */
 116         n = map;
 117         /* Anything with NULL value is a node. */
 118         while (!n->v) {
 119                 parent = n;
 120                 direction = (index >> n->u.n->bit_num) & 1;
 121                 n = &n->u.n->child[direction];
 122         }
 123
 124         /* Did we find it? */
 125         if (index != n->u.i) {
 126                 errno = ENOENT;
 127                 return NULL;
 128         }
 129
 130         value = n->v;
 131
 132         if (!parent) {
 133                 /* We deleted last node. */
 134                 intmap_init_(map);
 135         } else {
 136                 struct node *old = parent->u.n;
 137                 /* Raise other node to parent. */
 138                 *parent = old->child[!direction];
 139                 free(old);
 140         }
 141         errno = 0;
 142         return value;
 143 }
 144
 145 intmap_index_t intmap_first_(const struct intmap *map)
 146 {
 147         const struct intmap *n;
 148
 149         if (intmap_empty_(map)) {
 150                 errno = ENOENT;
 151                 return UINTMAP_NONE;
 152         }
 153
 154         n = map;
 155         /* Anything with NULL value is a node. */
 156         while (!n->v)
 157                 n = &n->u.n->child[0];
 158         errno = 0;
 159         return n->u.i;
 160 }
 161
 162 intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t index)
 163 {
 164         const struct intmap *n, *prev = NULL;
 165
 166         /* Special case of unincrementable value, or empty map */
 167         if (index == UINTMAP_NONE || intmap_empty_(map)) {
 168                 errno = ENOENT;
 169                 return UINTMAP_NONE;
 170         }
 171
 172         /* Follow down, track the last place where we could have set a bit
 173          * instead of clearing it: this is the higher alternative tree. */
 174         n = map;
 175         while (!n->v) {
 176                 u8 direction = (index >> n->u.n->bit_num) & 1;
 177                 if (!direction)
 178                         prev = n;
 179                 n = &n->u.n->child[direction];
 180         }
 181
 182         /* Found a successor? */
 183         if (n->u.i > index) {
 184                 errno = 0;
 185                 return n->u.i;
 186         }
 187
 188         /* Nowhere to go back up to? */
 189         if (!prev) {
 190                 errno = ENOENT;
 191                 return UINTMAP_NONE;
 192         }
 193
 194         /* Get first one from that other branch. */
 195         return intmap_first_(&prev->u.n->child[1]);
 196 }
 197
 198 static void clear(struct intmap n)
 199 {
 200         if (!n.v) {
 201                 clear(n.u.n->child[0]);
 202                 clear(n.u.n->child[1]);
 203                 free(n.u.n);
 204         }
 205 }
 206
 207 void intmap_clear_(struct intmap *map)
 208 {
 209         if (!intmap_empty_(map))
 210                 clear(*map);
 211         intmap_init_(map);
 212 }