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 #define sintmap_index_t int64_t
  15 #endif
  16
  17 /**
  18  * struct intmap - representation of an integer map
  19  *
  20  * It's exposed here to allow you to embed it and so we can inline the
  21  * trivial functions.
  22  */
  23 struct intmap {
  24         union {
  25                 struct node *n;
  26                 intmap_index_t i;
  27         } u;
  28         void *v;
  29 };
  30
  31 /**
  32  * UINTMAP - declare a type-specific intmap (for unsigned integers)
  33  * @membertype: type for this map's values, or void * for any pointer.
  34  *
  35  * You use this to create your own typed intmap for a particular
  36  * (non-NULL) pointer type.
  37  *
  38  * Example:
  39  *      UINTMAP(int *) uint_intmap;
  40  *      uintmap_init(&uint_intmap);
  41  */
  42 #define UINTMAP(membertype)                                     \
  43         TCON_WRAP(struct intmap, membertype uintmap_canary)
  44
  45 /**
  46  * SINTMAP - declare a type-specific intmap (for signed integers)
  47  * @membertype: type for this map's values, or void * for any pointer.
  48  *
  49  * You use this to create your own typed intmap for a particular type.
  50  * You can use an integer type as membertype, *but* remember you can't
  51  * use "0" as a value!
  52  *
  53  * This is different from UINTMAP because we want it to sort into
  54  * least (most negative) to largest order.
  55  *
  56  * Example:
  57  *      SINTMAP(int *) sint_intmap;
  58  *      sintmap_init(&sint_intmap);
  59  */
  60 #define SINTMAP(membertype)                                     \
  61         TCON_WRAP(struct intmap, membertype sintmap_canary)
  62
  63 /**
  64  * uintmap_init - initialize an unsigned integer map (empty)
  65  * @umap: the typed intmap to initialize.
  66  *
  67  * For completeness; if you've arranged for it to be NULL already you don't
  68  * need this.
  69  *
  70  * Example:
  71  *      UINTMAP(int *) uint_intmap;
  72  *
  73  *      uintmap_init(&uint_intmap);
  74  */
  75 #define uintmap_init(umap) intmap_init_(uintmap_unwrap_(umap))
  76
  77 /**
  78  * sintmap_init - initialize a signed integer map (empty)
  79  * @smap: the typed intmap to initialize.
  80  *
  81  * For completeness; if you've arranged for it to be NULL already you don't
  82  * need this.
  83  *
  84  * Example:
  85  *      SINTMAP(int *) sint_intmap;
  86  *
  87  *      sintmap_init(&sint_intmap);
  88  */
  89 #define sintmap_init(smap) intmap_init_(sintmap_unwrap_(smap))
  90
  91 static inline void intmap_init_(struct intmap *map)
  92 {
  93         map->u.n = NULL;
  94         map->v = NULL;
  95 }
  96
  97 /**
  98  * uintmap_empty - is this unsigned integer map empty?
  99  * @umap: the typed intmap to check.
 100  *
 101  * Example:
 102  *      if (!uintmap_empty(&uint_intmap))
 103  *              abort();
 104  */
 105 #define uintmap_empty(umap) intmap_empty_(uintmap_unwrap_(umap))
 106
 107 /**
 108  * sintmap_empty - is this signed integer map empty?
 109  * @smap: the typed intmap to check.
 110  *
 111  * Example:
 112  *      if (!sintmap_empty(&sint_intmap))
 113  *              abort();
 114  */
 115 #define sintmap_empty(smap) intmap_empty_(sintmap_unwrap_(smap))
 116
 117 static inline bool intmap_empty_(const struct intmap *map)
 118 {
 119         return map->v == NULL && map->u.n == NULL;
 120 }
 121
 122 /**
 123  * uintmap_get - get a value from an unsigned integer map
 124  * @umap: the typed intmap to search.
 125  * @index: the unsigned index to search for.
 126  *
 127  * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
 128  *
 129  * Example:
 130  *      int *val = uintmap_get(&uint_intmap, 100);
 131  *      if (val)
 132  *              printf("100 => %i\n", *val);
 133  */
 134 #define uintmap_get(umap, index)                                        \
 135         tcon_cast((umap), uintmap_canary,                               \
 136                       intmap_get_(uintmap_unwrap_(umap), (index)))
 137
 138 /**
 139  * sintmap_get - get a value from a signed integer map
 140  * @smap: the typed intmap to search.
 141  * @index: the signed index to search for.
 142  *
 143  * Returns the value, or NULL if it isn't in the map (and sets errno = ENOENT).
 144  *
 145  * Example:
 146  *      int *val2 = sintmap_get(&sint_intmap, -100);
 147  *      if (val2)
 148  *              printf("-100 => %i\n", *val2);
 149  */
 150 #define sintmap_get(smap, index)                                        \
 151         tcon_cast((smap), sintmap_canary,                               \
 152                   intmap_get_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
 153
 154 void *intmap_get_(const struct intmap *map, intmap_index_t index);
 155
 156 /**
 157  * uintmap_add - place a member in an unsigned integer map.
 158  * @umap: the typed intmap to add to.
 159  * @index: the unsigned index to place in the map.
 160  * @value: the (non-NULL) value.
 161  *
 162  * This returns false if we run out of memory (errno = ENOMEM), or
 163  * (more normally) if that index already appears in the map (EEXIST).
 164  *
 165  * Note that the value is not copied, just the pointer.
 166  *
 167  * Example:
 168  *      val = malloc(sizeof *val);
 169  *      *val = 17;
 170  *      if (!uintmap_add(&uint_intmap, 100, val))
 171  *              printf("100 was already in the map\n");
 172  */
 173 #define uintmap_add(umap, index, value)                                 \
 174         intmap_add_(uintmap_unwrap_(tcon_check((umap), uintmap_canary,  \
 175                                                (value))),               \
 176                     (index), (void *)(value))
 177
 178 /**
 179  * sintmap_add - place a member in a signed integer map.
 180  * @smap: the typed intmap to add to.
 181  * @index: the signed index to place in the map.
 182  * @value: the (non-NULL) value.
 183  *
 184  * This returns false if we run out of memory (errno = ENOMEM), or
 185  * (more normally) if that index already appears in the map (EEXIST).
 186  *
 187  * Note that the value is not copied, just the pointer.
 188  *
 189  * Example:
 190  *      val = malloc(sizeof *val);
 191  *      *val = 17;
 192  *      if (!sintmap_add(&sint_intmap, -100, val))
 193  *              printf("-100 was already in the map\n");
 194  */
 195 #define sintmap_add(smap, index, value)                                 \
 196         intmap_add_(sintmap_unwrap_(tcon_check((smap), sintmap_canary,  \
 197                                                (value))),               \
 198                     SINTMAP_OFF(index), (void *)(value))
 199
 200 bool intmap_add_(struct intmap *map, intmap_index_t member, const void *value);
 201
 202 /**
 203  * uintmap_del - remove a member from an unsigned integer map.
 204  * @umap: the typed intmap to delete from.
 205  * @index: the unsigned index to remove from the map.
 206  *
 207  * This returns the value, or NULL if there was no value at that
 208  * index.
 209  *
 210  * Example:
 211  *      if (uintmap_del(&uint_intmap, 100) == NULL)
 212  *              printf("100 was not in the map?\n");
 213  */
 214 #define uintmap_del(umap, index)                                        \
 215         tcon_cast((umap), uintmap_canary,                               \
 216                   intmap_del_(uintmap_unwrap_(umap), (index)))
 217
 218 /**
 219  * sintmap_del - remove a member from a signed integer map.
 220  * @smap: the typed intmap to delete from.
 221  * @index: the signed index to remove from the map.
 222  *
 223  * This returns the value, or NULL if there was no value at that
 224  * index.
 225  *
 226  * Example:
 227  *      if (sintmap_del(&sint_intmap, -100) == NULL)
 228  *              printf("-100 was not in the map?\n");
 229  */
 230 #define sintmap_del(smap, index)                                        \
 231         tcon_cast((smap), sintmap_canary,                               \
 232                   intmap_del_(sintmap_unwrap_(smap), SINTMAP_OFF(index)))
 233
 234 void *intmap_del_(struct intmap *map, intmap_index_t index);
 235
 236 /**
 237  * uintmap_clear - remove every member from an unsigned integer map.
 238  * @umap: the typed intmap to clear.
 239  *
 240  * The map will be empty after this.
 241  *
 242  * Example:
 243  *      uintmap_clear(&uint_intmap);
 244  */
 245 #define uintmap_clear(umap) intmap_clear_(uintmap_unwrap_(umap))
 246
 247 /**
 248  * sintmap_clear - remove every member from a signed integer map.
 249  * @smap: the typed intmap to clear.
 250  *
 251  * The map will be empty after this.
 252  *
 253  * Example:
 254  *      sintmap_clear(&sint_intmap);
 255  */
 256 #define sintmap_clear(smap) intmap_clear_(sintmap_unwrap_(smap))
 257
 258 void intmap_clear_(struct intmap *map);
 259
 260 /**
 261  * uintmap_first - get first value in an unsigned intmap
 262  * @umap: the typed intmap to iterate through.
 263  * @indexp: a pointer to store the index.
 264  *
 265  * Returns NULL if the map is empty, otherwise populates *@indexp and
 266  * returns the lowest entry.
 267  */
 268 #define uintmap_first(umap, indexp)                                     \
 269         tcon_cast((umap), uintmap_canary,                               \
 270                   intmap_first_(uintmap_unwrap_(umap), (indexp)))
 271
 272 void *intmap_first_(const struct intmap *map, intmap_index_t *indexp);
 273
 274 /**
 275  * sintmap_first - get first value in a signed intmap
 276  * @smap: the typed intmap to iterate through.
 277  * @indexp: a pointer to store the index.
 278  *
 279  * Returns NULL if the map is empty, otherwise populates *@indexp and
 280  * returns the lowest entry.
 281  */
 282 #define sintmap_first(smap, indexp)                                     \
 283         tcon_cast((smap), sintmap_canary,                               \
 284                   sintmap_first_(sintmap_unwrap_(smap), (indexp)))
 285
 286 /**
 287  * uintmap_after - get the closest following index in an unsigned intmap
 288  * @umap: the typed intmap to iterate through.
 289  * @indexp: the preceding index (may not exist)
 290  *
 291  * Returns NULL if the there is no entry > @indexp, otherwise
 292  * populates *@indexp and returns the lowest entry > @indexp.
 293  */
 294 #define uintmap_after(umap, indexp)                                     \
 295         tcon_cast((umap), uintmap_canary,                               \
 296                   intmap_after_(uintmap_unwrap_(umap), (indexp)))
 297
 298 void *intmap_after_(const struct intmap *map, intmap_index_t *indexp);
 299
 300 /**
 301  * sintmap_after - get the closest following index in a signed intmap
 302  * @smap: the typed intmap to iterate through.
 303  * @indexp: the preceding index (may not exist)
 304  *
 305  * Returns NULL if the there is no entry > @indexp, otherwise
 306  * populates *@indexp and returns the lowest entry > @indexp.
 307  */
 308 #define sintmap_after(smap, indexp)                                     \
 309         tcon_cast((smap), sintmap_canary,                               \
 310                   sintmap_after_(sintmap_unwrap_(smap), (indexp)))
 311
 312 /**
 313  * uintmap_last - get last value in an unsigned intmap
 314  * @umap: the typed intmap to iterate through.
 315  * @indexp: a pointer to store the index.
 316  *
 317  * Returns NULL if the map is empty, otherwise populates *@indexp and
 318  * returns the highest entry.
 319  */
 320 #define uintmap_last(umap, indexp)                                      \
 321         tcon_cast((umap), uintmap_canary,                               \
 322                   intmap_last_(uintmap_unwrap_(umap), (indexp)))
 323
 324 void *intmap_last_(const struct intmap *map, intmap_index_t *indexp);
 325
 326 /**
 327  * sintmap_last - get last value in a signed intmap
 328  * @smap: the typed intmap to iterate through.
 329  * @indexp: a pointer to store the index.
 330  *
 331  * Returns NULL if the map is empty, otherwise populates *@indexp and
 332  * returns the highest entry.
 333  */
 334 #define sintmap_last(smap, indexp)                                      \
 335         tcon_cast((smap), sintmap_canary,                               \
 336                   sintmap_last_(sintmap_unwrap_(smap), (indexp)))
 337
 338 /**
 339  * uintmap_iterate - ordered iteration over an unsigned intmap
 340  * @umap: the typed intmap to iterate through.
 341  * @handle: the function to call.
 342  * @arg: the argument for the function (types should match).
 343  *
 344  * @handle's prototype should be:
 345  *      bool @handle(intmap_index_t index, type value, typeof(arg) arg)
 346  *
 347  * If @handle returns false, the iteration will stop and uintmap_iterate will
 348  * return false, otherwise uintmap_iterate will return true.
 349  * You should not alter the map within the @handle function!
 350  *
 351  * Example:
 352  *      typedef UINTMAP(int *) umap_intp;
 353  *      static bool dump_some(intmap_index_t index, int *value, int *num)
 354  *      {
 355  *              // Only dump out num nodes.
 356  *              if (*(num--) == 0)
 357  *                      return false;
 358  *              printf("%lu=>%i\n", (unsigned long)index, *value);
 359  *              return true;
 360  *      }
 361  *
 362  *      static void dump_map(const umap_intp *map)
 363  *      {
 364  *              int max = 100;
 365  *              uintmap_iterate(map, dump_some, &max);
 366  *              if (max < 0)
 367  *                      printf("... (truncated to 100 entries)\n");
 368  *      }
 369  */
 370 #define uintmap_iterate(map, handle, arg)                               \
 371         intmap_iterate_(tcon_unwrap(map),                               \
 372                         typesafe_cb_cast(bool (*)(intmap_index_t,       \
 373                                                   void *, void *),      \
 374                                          bool (*)(intmap_index_t,       \
 375                                                   tcon_type((map),      \
 376                                                             uintmap_canary), \
 377                                                   __typeof__(arg)), (handle)), \
 378                         (arg), 0)
 379
 380 /**
 381  * sintmap_iterate - ordered iteration over a signed intmap
 382  * @smap: the typed intmap to iterate through.
 383  * @handle: the function to call.
 384  * @arg: the argument for the function (types should match).
 385  *
 386  * @handle's prototype should be:
 387  *      bool @handle(sintmap_index_t index, type value, typeof(arg) arg)
 388  *
 389  * If @handle returns false, the iteration will stop and sintmap_iterate will
 390  * return false, otherwise sintmap_iterate will return true.
 391  * You should not alter the map within the @handle function!
 392  *
 393  * Example:
 394  *      typedef SINTMAP(int *) smap_intp;
 395  *      static bool dump_some(sintmap_index_t index, int *value, int *num)
 396  *      {
 397  *              // Only dump out num nodes.
 398  *              if (*(num--) == 0)
 399  *                      return false;
 400  *              printf("%li=>%i\n", (long)index, *value);
 401  *              return true;
 402  *      }
 403  *
 404  *      static void dump_map(const smap_intp *map)
 405  *      {
 406  *              int max = 100;
 407  *              sintmap_iterate(map, dump_some, &max);
 408  *              if (max < 0)
 409  *                      printf("... (truncated to 100 entries)\n");
 410  *      }
 411  */
 412 #define sintmap_iterate(map, handle, arg)                               \
 413         intmap_iterate_(tcon_unwrap(map),                               \
 414                         typesafe_cb_cast(bool (*)(intmap_index_t,       \
 415                                                   void *, void *),      \
 416                                          bool (*)(sintmap_index_t,      \
 417                                                   tcon_type((map),      \
 418                                                             sintmap_canary), \
 419                                                   __typeof__(arg)), (handle)), \
 420                         (arg), SINTMAP_OFFSET)
 421
 422 bool intmap_iterate_(const struct intmap *map,
 423                      bool (*handle)(intmap_index_t, void *, void *),
 424                      void *data,
 425                      intmap_index_t offset);
 426
 427 /* TODO: We could implement intmap_prefix. */
 428
 429 /* These make sure it really is a uintmap/sintmap */
 430 #define uintmap_unwrap_(u) (tcon_unwrap(u) + 0*tcon_sizeof((u), uintmap_canary))
 431 #define sintmap_unwrap_(s) (tcon_unwrap(s) + 0*tcon_sizeof((s), sintmap_canary))
 432
 433 /* We have to offset indices if they're signed, so ordering works. */
 434 #define SINTMAP_OFFSET          ((intmap_index_t)1 << (sizeof(intmap_index_t)*8-1))
 435 #define SINTMAP_OFF(index)      ((intmap_index_t)(index) + SINTMAP_OFFSET)
 436 #define SINTMAP_UNOFF(index)    ((intmap_index_t)(index) - SINTMAP_OFFSET)
 437
 438 /* Due to multi-evaluation, these can't be macros */
 439 static inline void *sintmap_first_(const struct intmap *map,
 440                                    sintmap_index_t *indexp)
 441 {
 442         intmap_index_t i;
 443         void *ret = intmap_first_(map, &i);
 444         *indexp = SINTMAP_UNOFF(i);
 445         return ret;
 446
 447 }
 448
 449 static inline void *sintmap_after_(const struct intmap *map,
 450                                    sintmap_index_t *indexp)
 451 {
 452         intmap_index_t i = SINTMAP_OFF(*indexp);
 453         void *ret = intmap_after_(map, &i);
 454         *indexp = SINTMAP_UNOFF(i);
 455         return ret;
 456 }
 457
 458 static inline void *sintmap_last_(const struct intmap *map,
 459                                   sintmap_index_t *indexp)
 460 {
 461         intmap_index_t i;
 462         void *ret = intmap_last_(map, &i);
 463         *indexp = SINTMAP_UNOFF(i);
 464         return ret;
 465
 466 }
 467 #endif /* CCAN_INTMAP_H */