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

   1 #ifndef CCAN_JMAP_H
   2 #define CCAN_JMAP_H
   3 #include <stddef.h>
   4 #include <Judy.h>
   5 #include <stdbool.h>
   6 #include <string.h>
   7 #include <ccan/compiler/compiler.h>
   8 #include <assert.h>
   9 #ifdef DEBUG
  10 #include <stdio.h>
  11 #endif
  12
  13 /**
  14  * jmap_new - create a new, empty jmap.
  15  *
  16  * See Also:
  17  *      JMAP_DEFINE_TYPE()
  18  *
  19  * Example:
  20  *      struct jmap *map = jmap_new();
  21  *      if (!map)
  22  *              errx(1, "Failed to allocate jmap");
  23  */
  24 struct jmap *jmap_new(void);
  25
  26 /**
  27  * jmap_free - destroy a jmap.
  28  * @map: the map returned from jmap_new.
  29  *
  30  * Example:
  31  *      jmap_free(map);
  32  */
  33 void jmap_free(const struct jmap *map);
  34
  35 /* This is exposed in the header so we can inline.  Treat it as private! */
  36 struct jmap {
  37         Pvoid_t judy;
  38         JError_t err;
  39         const char *errstr;
  40         /* Used if !NDEBUG */
  41         int num_accesses;
  42         /* Used if DEBUG */
  43         unsigned long *acc_value;
  44         unsigned long acc_index;
  45         const char *funcname;
  46 };
  47 const char *COLD jmap_error_(struct jmap *map);
  48
  49 /* Debugging checks. */
  50 static inline void jmap_debug_add_access(const struct jmap *map,
  51                                          unsigned long index,
  52                                          unsigned long *val,
  53                                          const char *funcname)
  54 {
  55 #ifdef DEBUG
  56         if (!map->acc_value) {
  57                 ((struct jmap *)map)->acc_value = val;
  58                 ((struct jmap *)map)->acc_index = index;
  59                 ((struct jmap *)map)->funcname = funcname;
  60         }
  61 #endif
  62         if (val)
  63                 assert(++((struct jmap *)map)->num_accesses);
  64 }
  65
  66 static inline void jmap_debug_del_access(struct jmap *map, unsigned long **val)
  67 {
  68         assert(--map->num_accesses >= 0);
  69 #ifdef DEBUG
  70         if (map->acc_value == *val)
  71                 map->acc_value = NULL;
  72 #endif
  73         /* Set it to some invalid value.  Not NULL, they might rely on that! */
  74         assert(memset(val, 0x42, sizeof(*val)));
  75 }
  76
  77 static inline void jmap_debug_access(struct jmap *map)
  78 {
  79 #ifdef DEBUG
  80         if (map->num_accesses && map->acc_value)
  81                 fprintf(stderr,
  82                         "jmap: still got index %lu, val %lu (%p) from %s\n",
  83                         map->acc_index, *map->acc_value, map->acc_value,
  84                         map->funcname);
  85 #endif
  86         assert(!map->num_accesses);
  87 }
  88
  89 /**
  90  * jmap_error - test for an error in the a previous jmap_ operation.
  91  * @map: the map to test.
  92  *
  93  * Under normal circumstances, return NULL to indicate no error has occurred.
  94  * Otherwise, it will return a string containing the error.  This string
  95  * can only be freed by jmap_free() on the map.
  96  *
  97  * Other than out-of-memory, errors are caused by memory corruption or
  98  * interface misuse.
  99  *
 100  * Example:
 101  *      struct jmap *map = jmap_new();
 102  *      const char *errstr;
 103  *
 104  *      if (!map)
 105  *              err(1, "allocating jmap");
 106  *      errstr = jmap_error(map);
 107  *      if (errstr)
 108  *              errx(1, "Woah, error on newly created map?! %s", errstr);
 109  */
 110 static inline const char *jmap_error(struct jmap *map)
 111 {
 112         if (JU_ERRNO(&map->err) <= JU_ERRNO_NFMAX)
 113                 return NULL;
 114         return jmap_error_(map);
 115 }
 116
 117 /**
 118  * jmap_add - add or replace a value for a given index in the map.
 119  * @map: map from jmap_new
 120  * @index: the index to map
 121  * @value: the value to associate with the index
 122  *
 123  * Adds index into the map; replaces value if it's already there.
 124  * Returns false on error (out of memory).
 125  *
 126  * Example:
 127  *      if (!jmap_add(map, 0, 1))
 128  *              err(1, "jmap_add failed!");
 129  */
 130 static inline bool jmap_add(struct jmap *map,
 131                             unsigned long index, unsigned long value)
 132 {
 133         unsigned long *val;
 134         jmap_debug_access(map);
 135         val = (unsigned long *)JudyLIns(&map->judy, index, &map->err);
 136         if (val == PJERR)
 137                 return false;
 138         *val = value;
 139         return true;
 140 }
 141
 142 /**
 143  * jmap_set - change a value for an existing index in the map.
 144  * @map: map from jmap_new
 145  * @index: the index to map
 146  * @value: the value to associate with the index
 147  *
 148  * This sets the value of an index if it already exists, and return true,
 149  * otherwise returns false and does nothing.
 150  *
 151  * Example:
 152  *      if (!jmap_set(map, 0, 2))
 153  *              err(1, "jmap_set: index 0 not found");
 154  */
 155 static inline bool jmap_set(const struct jmap *map,
 156                             unsigned long index, unsigned long value)
 157 {
 158         unsigned long *val;
 159         val = (unsigned long *)JudyLGet(map->judy, index,
 160                                         (JError_t *)&map->err);
 161         if (val && val != PJERR) {
 162                 *val = value;
 163                 return true;
 164         }
 165         return false;
 166 }
 167
 168 /**
 169  * jmap_del - remove an index from the map.
 170  * @map: map from jmap_new
 171  * @index: the index to map
 172  *
 173  * Example:
 174  *      if (!jmap_del(map, 0))
 175  *              err(1, "jmap_del failed!");
 176  */
 177 static inline bool jmap_del(struct jmap *map, unsigned long index)
 178 {
 179         jmap_debug_access(map);
 180         return JudyLDel(&map->judy, index, &map->err) == 1;
 181 }
 182
 183 /**
 184  * jmap_test - test if a given index is defined.
 185  * @map: map from jmap_new
 186  * @index: the index to find
 187  *
 188  * Example:
 189  *      jmap_add(map, 0, 1);
 190  *      assert(jmap_test(map, 0));
 191  */
 192 static inline bool jmap_test(const struct jmap *map, unsigned long index)
 193 {
 194         return JudyLGet(map->judy, index, (JError_t *)&map->err) != NULL;
 195 }
 196
 197 /**
 198  * jmap_get - get a value for a given index.
 199  * @map: map from jmap_new
 200  * @index: the index to find
 201  * @invalid: the value to return if the index isn't found.
 202  *
 203  * Example:
 204  *      jmap_add(map, 0, 1);
 205  *      assert(jmap_get(map, 0, -1) == 1);
 206  *
 207  * See Also:
 208  *      jmap_getval()
 209  */
 210 static inline unsigned long jmap_get(const struct jmap *map,
 211                                      unsigned long index,
 212                                      unsigned long invalid)
 213 {
 214         unsigned long *val;
 215         val = (unsigned long *)JudyLGet(map->judy, index,
 216                                         (JError_t *)&map->err);
 217         if (!val || val == PJERR)
 218                 return invalid;
 219         return *val;
 220 }
 221
 222 /**
 223  * jmap_popcount - get population of (some part of) the map.
 224  * @map: map from jmap_new
 225  * @start: first index to count
 226  * @end_incl: last index to count (use -1 for end).
 227  *
 228  * Example:
 229  *      assert(jmap_popcount(map, 0, 1000) <= jmap_popcount(map, 0, 2000));
 230  */
 231 static inline unsigned long jmap_popcount(const struct jmap *map,
 232                                           unsigned long start,
 233                                           unsigned long end_incl)
 234 {
 235         return JudyLCount(map->judy, start, end_incl, (JError_t *)&map->err);
 236 }
 237
 238 /**
 239  * jmap_nth - return the index of the nth value in the map.
 240  * @map: map from jmap_new
 241  * @n: which index we are interested in (0-based)
 242  * @invalid: what to return if n >= map population
 243  *
 244  * This normally returns the nth index in the map, and often there is a
 245  * convenient known-invalid value (ie. something which is never in the
 246  * map).  Otherwise you can use jmap_nthval().
 247  *
 248  * Example:
 249  *      unsigned long i, index;
 250  *
 251  *      // We know 0 isn't in map.
 252  *      assert(!jmap_test(map, 0));
 253  *      for (i = 0; (index = jmap_nth(map, i, 0)) != 0; i++) {
 254  *              assert(jmap_popcount(map, 0, index) == i);
 255  *              printf("Index %lu = %lu\n", i, index);
 256  *      }
 257  *
 258  * See Also:
 259  *      jmap_nthval();
 260  */
 261 static inline unsigned long jmap_nth(const struct jmap *map,
 262                                      unsigned long n, unsigned long invalid)
 263 {
 264         unsigned long index;
 265         if (!JudyLByCount(map->judy, n+1, &index, (JError_t *)&map->err))
 266                 index = invalid;
 267         return index;
 268 }
 269
 270 /**
 271  * jmap_first - return the first index in the map.
 272  * @map: map from jmap_new
 273  * @invalid: return value if jmap is empty.
 274  *
 275  * This is equivalent to jmap_nth(map, 0, invalid).
 276  *
 277  * Example:
 278  *      assert(!jmap_test(map, 0));
 279  *      printf("Map indices (increasing order):");
 280  *      for (i = jmap_first(map, 0); i; i = jmap_next(map, i, 0))
 281  *              printf(" %lu", i);
 282  *      printf("\n");
 283  *
 284  * See Also:
 285  *      jmap_firstval()
 286  */
 287 static inline unsigned long jmap_first(const struct jmap *map,
 288                                        unsigned long invalid)
 289 {
 290         unsigned long index = 0;
 291         if (!JudyLFirst(map->judy, &index, (JError_t *)&map->err))
 292                 index = invalid;
 293         else
 294                 assert(index != invalid);
 295         return index;
 296 }
 297
 298 /**
 299  * jmap_next - return the next index in the map.
 300  * @map: map from jmap_new
 301  * @prev: previous index
 302  * @invalid: return value if there prev was final index in map.
 303  *
 304  * This is usually used to find an adjacent index after jmap_first.
 305  * See Also:
 306  *      jmap_nextval()
 307  */
 308 static inline unsigned long jmap_next(const struct jmap *map,
 309                                       unsigned long prev,
 310                                       unsigned long invalid)
 311 {
 312         if (!JudyLNext(map->judy, &prev, (JError_t *)&map->err))
 313                 prev = invalid;
 314         else
 315                 assert(prev != invalid);
 316         return prev;
 317 }
 318
 319 /**
 320  * jmap_last - return the last index in the map.
 321  * @map: map from jmap_new
 322  * @invalid: return value if map is empty.
 323  *
 324  * Example:
 325  *      assert(!jmap_test(map, 0));
 326  *      printf("Map indices (increasing order):");
 327  *      for (i = jmap_last(map, 0); i; i = jmap_prev(map, i, 0))
 328  *              printf(" %lu", i);
 329  *      printf("\n");
 330  * See Also:
 331  *      jmap_lastval()
 332  */
 333 static inline unsigned long jmap_last(const struct jmap *map,
 334                                       unsigned long invalid)
 335 {
 336         unsigned long index = -1;
 337         if (!JudyLLast(map->judy, &index, (JError_t *)&map->err))
 338                 index = invalid;
 339         else
 340                 assert(index != invalid);
 341         return index;
 342 }
 343
 344 /**
 345  * jmap_prev - return the previous index in the map.
 346  * @map: map from jmap_new
 347  * @prev: previous index
 348  * @invalid: return value if no previous indices are in the map.
 349  *
 350  * This is usually used to find an prior adjacent index after jmap_last.
 351  * See Also:
 352  *      jmap_prevval()
 353  */
 354 static inline unsigned long jmap_prev(const struct jmap *map,
 355                                       unsigned long prev,
 356                                       unsigned long invalid)
 357 {
 358         if (!JudyLPrev(map->judy, &prev, (JError_t *)&map->err))
 359                 prev = invalid;
 360         else
 361                 assert(prev != invalid);
 362         return prev;
 363 }
 364
 365 /**
 366  * jmap_getval - access a value in-place for a given index.
 367  * @map: map from jmap_new
 368  * @index: the index to find
 369  *
 370  * Returns a pointer into the map, or NULL if the index isn't in the
 371  * map.  Like the other val functions (jmap_nthval, jmap_firstval
 372  * etc), this pointer cannot be used after a jmap_add or jmap_del
 373  * call, and you must call jmap_putval() once you are finished.
 374  *
 375  * Unless you define NDEBUG, jmap_add and kmap_del will check that you
 376  * have called jmap_putval().
 377  *
 378  * Example:
 379  *      unsigned long *p;
 380  *      jmap_add(map, 0, 1);
 381  *      p = jmap_getval(map, 0);
 382  *      if (!p)
 383  *              errx(1, "Could not find 0 in map!");
 384  *      if (*p != 1)
 385  *              errx(1, "Value in map was not 0?!");
 386  *      *p = 7;
 387  *      jmap_putval(map, &p);
 388  *      // Accessing p now would probably crash.
 389  *
 390  * See Also:
 391  *      jmap_putval(), jmap_firstval()
 392  */
 393 static inline unsigned long *jmap_getval(struct jmap *map, unsigned long index)
 394 {
 395         unsigned long *val;
 396         val = (unsigned long *)JudyLGet(map->judy, index,
 397                                         (JError_t *)&map->err);
 398         jmap_debug_add_access(map, index, val, "jmap_getval");
 399         return val;
 400 }
 401
 402 /**
 403  * jmap_putval - revoke access to a value.
 404  * @map: map from jmap_new
 405  * @p: the pointer to a pointer to the value
 406  *
 407  * @p is a pointer to the (successful) value retuned from one of the
 408  * jmap_*val functions (listed below).  After this, it will be invalid.
 409  *
 410  * Unless NDEBUG is defined, this will actually alter the value of p
 411  * to point to garbage to help avoid accidental use.
 412  *
 413  * See Also:
 414  *      jmap_getval(), jmap_nthval(), jmap_firstval(), jmap_nextval(),
 415  *              jmap_lastval(), jmap_prevval().
 416  */
 417 static inline void jmap_putval(struct jmap *map, unsigned long **p)
 418 {
 419         jmap_debug_del_access(map, p);
 420 }
 421
 422 /**
 423  * jmap_nthval - access the value of the nth value in the map.
 424  * @map: map from jmap_new
 425  * @n: which index we are interested in (0-based)
 426  *
 427  * This returns a pointer to the value at the nth index in the map,
 428  * or NULL if there are n is greater than the population of the map.
 429  * You must use jmap_putval() on the pointer once you are done with it.
 430  *
 431  * Example:
 432  *      unsigned long *val;
 433  *
 434  *      // We know 0 isn't in map.
 435  *      assert(!jmap_test(map, 0));
 436  *      for (i = 0; (val = jmap_nthval(map, i, &index)) != NULL; i++) {
 437  *              assert(jmap_popcount(map, 0, index) == i);
 438  *              printf("Index %lu = %lu, value = %lu\n", i, index, *val);
 439  *              jmap_putval(map, &val);
 440  *      }
 441  *
 442  * See Also:
 443  *      jmap_nth();
 444  */
 445 static inline unsigned long *jmap_nthval(const struct jmap *map,
 446                                          unsigned long n, unsigned long *index)
 447 {
 448         unsigned long *val;
 449         val = (unsigned long *)JudyLByCount(map->judy, n+1, index,
 450                                      (JError_t *)&map->err);
 451         jmap_debug_add_access(map, *index, val, "jmap_nthval");
 452         return val;
 453 }
 454
 455 /**
 456  * jmap_firstval - access the first value in the map.
 457  * @map: map from jmap_new
 458  * @index: set to the first index in the map.
 459  *
 460  * Returns NULL if the map is empty; otherwise this returns a pointer to
 461  * the first value, which you must call jmap_putval() on!
 462  *
 463  * Example:
 464  *      // Add one to every value.
 465  *      for (val = jmap_firstval(map, &i); val; val = jmap_nextval(map, &i)) {
 466  *              (*val)++;
 467  *              jmap_putval(map, &val);
 468  *      }
 469  *      printf("\n");
 470  *
 471  * See Also:
 472  *      jmap_first, jmap_nextval()
 473  */
 474 static inline unsigned long *jmap_firstval(const struct jmap *map,
 475                                            unsigned long *index)
 476 {
 477         unsigned long *val;
 478         *index = 0;
 479         val = (unsigned long *)JudyLFirst(map->judy, index,
 480                                           (JError_t *)&map->err);
 481         jmap_debug_add_access(map, *index, val, "jmap_firstval");
 482         return val;
 483 }
 484
 485 /**
 486  * jmap_nextval - access the next value in the map.
 487  * @map: map from jmap_new
 488  * @index: previous index, updated with the new index.
 489  *
 490  * This returns a pointer to a value (which you must call jmap_putval on)
 491  * or NULL.  This usually used to find an adjacent value after jmap_firstval.
 492  *
 493  * See Also:
 494  *      jmap_firstval(), jmap_putval()
 495  */
 496 static inline unsigned long *jmap_nextval(const struct jmap *map,
 497                                           unsigned long *index)
 498 {
 499         unsigned long *val;
 500         val = (unsigned long *)JudyLNext(map->judy, index,
 501                                          (JError_t *)&map->err);
 502         jmap_debug_add_access(map, *index, val, "jmap_nextval");
 503         return val;
 504 }
 505
 506 /**
 507  * jmap_lastval - access the last value in the map.
 508  * @map: map from jmap_new
 509  * @index: set to the last index in the map.
 510  *
 511  * See Also:
 512  *      jmap_last(), jmap_putval()
 513  */
 514 static inline unsigned long *jmap_lastval(const struct jmap *map,
 515                                           unsigned long *index)
 516 {
 517         unsigned long *val;
 518         *index = -1;
 519         val = (unsigned long *)JudyLLast(map->judy, index,
 520                                          (JError_t *)&map->err);
 521         jmap_debug_add_access(map, *index, val, "jmap_lastval");
 522         return val;
 523 }
 524
 525 /**
 526  * jmap_prevval - access the previous value in the map.
 527  * @map: map from jmap_new
 528  * @index: previous index, updated with the new index.
 529  *
 530  * This returns a pointer to a value (which you must call jmap_putval on)
 531  * or NULL.  This usually used to find an adjacent value after jmap_lastval.
 532  *
 533  * See Also:
 534  *      jmap_lastval(), jmap_putval()
 535  */
 536 static inline unsigned long *jmap_prevval(const struct jmap *map,
 537                                           unsigned long *index)
 538 {
 539         unsigned long *val;
 540         val = (unsigned long *)JudyLPrev(map->judy, index,
 541                                          (JError_t *)&map->err);
 542         jmap_debug_add_access(map, *index, val, "jmap_prevval");
 543         return val;
 544 }
 545 #endif /* CCAN_JMAP_H */