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

   1 /* CC0 license (public domain) - see LICENSE file for details */
   2 #ifndef CCAN_INTMAP_H
   3 #define CCAN_INTMAP_H
   4 #include "config.h"
   5 #include <ccan/tcon/tcon.h>
   6 #include <ccan/typesafe_cb/typesafe_cb.h>
   7 #include <inttypes.h>
   8 #include <stdlib.h>
   9 #include <stdbool.h>
  10
  11 /* Must be an unsigned type. */
  12 #ifndef intmap_index_t
  13 #define intmap_index_t uint64_t
  14 #endif
  15
  16 /* Maximum possible values of each type */
  17 #define UINTMAP_NONE ((intmap_index_t)-1)
  18 #define SINTMAP_NONE (((intmap_index_t)1 << (sizeof(intmap_index_t)*8))-1)
  19
  20 /**
  21  * struct intmap - representation of an integer map
  22  *
  23  * It's exposed here to allow you to embed it and so we can inline the
  24  * trivial functions.
  25  */
  26 struct intmap {
  27         union {
  28                 struct node *n;
  29                 intmap_index_t i;
  30         } u;
  31         void *v;
  32 };
  33
  34 /**
  35  * UINTMAP - declare a type-specific intmap (for unsigned integers)
  36  * @membertype: type for this map's values, or void * for any pointer.
  37  *
  38  * You use this to create your own typed intmap for a particular
  39  * (non-NULL) pointer type.
  40  *
  41  * Example:
  42  *      UINTMAP(int *) uint_intmap;
  43  *      uintmap_init(&uint_intmap);
  44  */
  45 #define UINTMAP(membertype)                                     \
  46         TCON_WRAP(struct intmap, membertype uintmap_canary)
  47
  48 /**
  49  * SINTMAP - declare a type-specific intmap (for signed integers)
  50  * @membertype: type for this map's values, or void * for any pointer.
  51  *
  52  * You use this to create your own typed intmap for a particular type.
  53  * You can use an integer type as membertype, *but* remember you can't
  54  * use "0" as a value!
  55  *
  56  * This is different from UINTMAP because we want it to sort into
  57  * least (most negative) to largest order.
  58  *
  59  * Example:
  60  *      SINTMAP(int *) sint_intmap;
  61  *      sintmap_init(&sint_intmap);
  62  */
  63 #define SINTMAP(membertype)                                     \
  64         TCON_WRAP(struct intmap, membertype sintmap_canary)
  65
  66 /**
  67  * uintmap_init - initialize an unsigned integer map (empty)
  68  * @umap: the typed intmap to initialize.
  69  *
  70  * For completeness; if you've arranged for it to be NULL already you don't
  71  * need this.
  72  *
  73  * Example:
  74  *      UINTMAP(int *) uint_intmap;
  75  *
  76  *      uintmap_init(&uint_intmap);
  77  */
  78 #define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap))
  79
  80 /**
  81  * sintmap_init - initialize a signed integer map (empty)
  82  * @smap: the typed intmap to initialize.
  83  *
  84  * For completeness; if you've arranged for it to be NULL already you don't
  85  * need this.
  86  *
  87  * Example:
  88  *      SINTMAP(int *) sint_intmap;
  89  *
  90  *      sintmap_init(&sint_intmap);
  91  */
  92 #define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap))
  93
  94 static inline void intmap_init_(struct intmap *map)
  95 {
  96         map->u.n = NULL;
  97         map->v = NULL;
  98 }
  99
 100 /**
 101  * uintmap_empty - is this unsigned integer map empty?
 102  * @umap: the typed intmap to check.
 103  *
 104  * Example:
 105  *      if (!uintmap_empty(&uint_intmap))
 106  *              abort();
 107  */
 108 #define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap))
 109
 110 /**
 111  * sintmap_empty - is this signed integer map empty?
 112  * @smap: the typed intmap to check.
 113  *
 114  * Example:
 115  *      if (!sintmap_empty(&sint_intmap))
 116  *              abort();
 117  */
 118 #define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap))
 119
 120 static inline bool intmap_empty_(const struct intmap *map)
 121 {
 122         return map->v == NULL && map->u.n == NULL;
 123 }
 124
 125 /**
 126  * uintmap_get - get a value from an unsigned integer map
 127  * @umap: the typed intmap to search.
 128  * @index: the unsigned index to search for.
 129  *
 130  * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
 131  *
 132  * Example:
 133  *      int *val = uintmap_get(&uint_intmap, 100);
 134  *      if (val)
 135  *              printf("100 => %i\n", *val);
 136  */
 137 #define uintmap_get(umap, index)                                        \
 138         tcon_cast((umap), uintmap_canary,                               \
 139                       intmap_get_(uintmap_unwrap_(umap), (index)))
 140
 141 /**
 142  * sintmap_get - get a value from a signed integer map
 143  * @smap: the typed intmap to search.
 144  * @index: the signed index to search for.
 145  *
 146  * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
 147  *
 148  * Example:
 149  *      int *val2 = sintmap_get(&sint_intmap, -100);
 150  *      if (val2)
 151  *              printf("-100 => %i\n", *val2);
 152  */
 153 #define sintmap_get(smap, index)                                        \
 154         tcon_cast((smap), sintmap_canary,                               \
 155                   intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
 156
 157 void *intmap_get_(const struct intmap *map, intmap_index_t index);
 158
 159 /**
 160  * uintmap_add - place a member in an unsigned integer map.
 161  * @umap: the typed intmap to add to.
 162  * @index: the unsigned index to place in the map.
 163  * @value: the (non-NULL) value.
 164  *
 165  * This returns false if we run out of memory (errno = ENOMEM), or
 166  * (more normally) if that index already appears in the map (EEXIST).
 167  *
 168  * Note that the value is not copied, just the pointer.
 169  *
 170  * Example:
 171  *      val = malloc(sizeof *val);
 172  *      *val = 17;
 173  *      if (!uintmap_add(&uint_intmap, 100, val))
 174  *              printf("100 was already in the map\n");
 175  */
 176 #define uintmap_add(umap, index, value)                                 \
 177         intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary,  \
 178                                                (value))),               \
 179                     (index), (void *)(value))
 180
 181 /**
 182  * sintmap_add - place a member in a signed integer map.
 183  * @smap: the typed intmap to add to.
 184  * @index: the signed index to place in the map.
 185  * @value: the (non-NULL) value.
 186  *
 187  * This returns false if we run out of memory (errno = ENOMEM), or
 188  * (more normally) if that index already appears in the map (EEXIST).
 189  *
 190  * Note that the value is not copied, just the pointer.
 191  *
 192  * Example:
 193  *      val = malloc(sizeof *val);
 194  *      *val = 17;
 195  *      if (!sintmap_add(&sint_intmap, -100, val))
 196  *              printf("-100 was already in the map\n");
 197  */
 198 #define sintmap_add(smap, index, value)                                 \
 199         intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary,  \
 200                                                (value))),               \
 201                     SINTMAP_OFF(index), (void *)(value))
 202
 203 bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value);
 204
 205 /**
 206  * uintmap_del - remove a member from an unsigned integer map.
 207  * @umap: the typed intmap to delete from.
 208  * @index: the unsigned index to remove from the map.
 209  *
 210  * This returns the value, or NULL if there was no value at that
 211  * index.
 212  *
 213  * Example:
 214  *      if (uintmap_del(&uint_intmap, 100) == NULL)
 215  *              printf("100 was not in the map?\n");
 216  */
 217 #define uintmap_del(umap, index)                                        \
 218         tcon_cast((umap), uintmap_canary,                               \
 219                   intmap_del_(uintmap_unwrap_(umap), (index)))
 220
 221 /**
 222  * sintmap_del - remove a member from a signed integer map.
 223  * @smap: the typed intmap to delete from.
 224  * @index: the signed index to remove from the map.
 225  *
 226  * This returns the value, or NULL if there was no value at that
 227  * index.
 228  *
 229  * Example:
 230  *      if (sintmap_del(&sint_intmap, -100) == NULL)
 231  *              printf("-100 was not in the map?\n");
 232  */
 233 #define sintmap_del(smap, index)                                        \
 234         tcon_cast((smap), sintmap_canary,                               \
 235                   intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
 236
 237 void *intmap_del_(struct intmap *map, intmap_index_t index);
 238
 239 /**
 240  * uintmap_clear - remove every member from an unsigned integer map.
 241  * @umap: the typed intmap to clear.
 242  *
 243  * The map will be empty after this.
 244  *
 245  * Example:
 246  *      uintmap_clear(&uint_intmap);
 247  */
 248 #define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap))
 249
 250 /**
 251  * sintmap_clear - remove every member from a signed integer map.
 252  * @smap: the typed intmap to clear.
 253  *
 254  * The map will be empty after this.
 255  *
 256  * Example:
 257  *      sintmap_clear(&sint_intmap);
 258  */
 259 #define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap))
 260
 261 void intmap_clear_(struct intmap *map);
 262
 263 /**
 264  * uintmap_first - get first index in an unsigned intmap
 265  * @umap: the typed intmap to iterate through.
 266  *
 267  * Returns UINTMAP_NONE and sets errno to ENOENT if it's empty.
 268  * Otherwise errno is set to 0.
 269  */
 270 #define uintmap_first(umap)                     \
 271         intmap_first_(uintmap_unwrap_(umap))
 272
 273 /**
 274  * sintmap_first - get first index in a signed intmap
 275  * @smap: the typed intmap to iterate through.
 276  *
 277  * Returns SINTMAP_NONE and sets errno to ENOENT if it's
 278  * empty.  Otherwise errno is set to 0.
 279  */
 280 #define sintmap_first(smap)                                     \
 281         SINTMAP_UNOFF(intmap_first_(sintmap_unwrap_(smap)))
 282
 283 intmap_index_t intmap_first_(const struct intmap *map);
 284
 285 /**
 286  * uintmap_after - get the closest following index in an unsigned intmap
 287  * @umap: the typed intmap to iterate through.
 288  * @i: the preceeding index (may not exist)
 289  *
 290  * Returns UINTMAP_NONE and sets errno to ENOENT if there are no
 291  * others.  Otherwise errno is set to 0.
 292  */
 293 #define uintmap_after(umap, i)                          \
 294         intmap_after_(uintmap_unwrap_(umap), (i))
 295
 296 /**
 297  * sintmap_after - get the closest following index in a signed intmap
 298  * @smap: the typed intmap to iterate through.
 299  * @i: the preceeding index.
 300  *
 301  * Returns SINTMAP_NONE and sets errno to ENOENT if there are no
 302  * others.  Otherwise errno is set to 0.
 303  */
 304 #define sintmap_after(smap, i)                                          \
 305         SINTMAP_UNOFF(intmap_after_(sintmap_unwrap_(smap), SINTMAP_OFF((i))))
 306
 307 intmap_index_t intmap_after_(const struct intmap *map, intmap_index_t i);
 308
 309 /* TODO: We could implement intmap_prefix, intmap_iterate... */
 310
 311 /* These make sure it really is a uintmap/sintmap */
 312 #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary))
 313 #define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary))
 314
 315 /* We have to offset indices if they're signed, so ordering works. */
 316 #define SINTMAP_OFFSET          ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1))
 317 #define SINTMAP_OFF(index)      ((intmap_index_t)(index) + SINTMAP_OFFSET)
 318 #define SINTMAP_UNOFF(index)    ((intmap_index_t)(index) - SINTMAP_OFFSET)
 319
 320 #endif /* CCAN_INTMAP_H */