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

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