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