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

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