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

   1 /* Licensed under BSD-MIT - see LICENSE file for details */
   2 #ifndef CCAN_INVBLOOM_H
   3 #define CCAN_INVBLOOM_H
   4 #include <ccan/short_types/short_types.h>
   5 #include <ccan/typesafe_cb/typesafe_cb.h>
   6 #include <ccan/tal/tal.h>
   7
   8 struct invbloom {
   9         size_t n_elems;
  10         size_t id_size;
  11         u32 salt;
  12         s32 *count; /* [n_elems] */
  13         u8 *idsum; /* [n_elems][id_size] */
  14         void (*singleton)(struct invbloom *ib, size_t elem, bool, void *);
  15         void *singleton_data;
  16 };
  17
  18 /**
  19  * invbloom_new - create a new invertable bloom lookup table
  20  * @ctx: context to tal() from, or NULL.
  21  * @type: type to place into the buckets (must not contain padding)
  22  * @n_elems: number of entries in table
  23  * @salt: 32 bit seed for table
  24  *
  25  * Returns a new table, which can be freed with tal_free().
  26  */
  27 #define invbloom_new(ctx, type, n_elems, salt)  \
  28         invbloom_new_((ctx), sizeof(type), (n_elems), (salt))
  29 struct invbloom *invbloom_new_(const tal_t *ctx,
  30                                size_t id_size,
  31                                size_t n_elems, u32 salt);
  32
  33 /**
  34  * invbloom_singleton_cb - set callback for a singleton created/destroyed.
  35  * @ib: the invertable bloom lookup table.
  36  * @cb: the function to call (or NULL for none)
  37  * @data: the data to hand to the function.
  38  *
  39  * This may be called by any function which mutates the table,
  40  * possibly multiple times for a single call.  The particular
  41  * @ib bucket will be consistent, but the rest of the table may
  42  * not be.
  43  *
  44  * @cb is of form "void @cb(struct invbloom *ib, size_t bucket, bool
  45  * before, data)".  @before is true if the call is done before the
  46  * singleton in @bucket is removed (ie. ib->counts[bucket] is -1 or 1,
  47  * but is about to change).  @before is false if the call is done
  48  * after the operation, and the bucket is now a singleton.
  49  */
  50 #define invbloom_singleton_cb(ib, cb, data)                     \
  51         invbloom_singleton_cb_((ib),                            \
  52                typesafe_cb_preargs(void, void *, (cb), (data),  \
  53                                    struct invbloom *, size_t, bool), (data))
  54
  55 void invbloom_singleton_cb_(struct invbloom *ib,
  56                             void (*cb)(struct invbloom *,
  57                                        size_t bucket, bool before, void *),
  58                             void *data);
  59
  60 /**
  61  * invbloom_insert - add a new element
  62  * @ib: the invertable bloom lookup table.
  63  * @elem: the element
  64  *
  65  * This is guaranteed to be the inverse of invbloom_delete.
  66  */
  67 void invbloom_insert(struct invbloom *ib, const void *elem);
  68
  69 /**
  70  * invbloom_delete - remove an element
  71  * @ib: the invertable bloom lookup table.
  72  * @elem: the element
  73  *
  74  * Note that this doesn't check the element was previously added (as
  75  * that can not be done in general anyway).
  76  *
  77  * This is guaranteed to be the inverse of invbloom_delete.
  78  */
  79 void invbloom_delete(struct invbloom *ib, const void *elem);
  80
  81 /**
  82  * invbloom_get - check if an element is (probably) in the table.
  83  * @ib: the invertable bloom lookup table.
  84  * @elem: the element
  85  *
  86  * This may return a false negative if the table is too full.
  87  *
  88  * It will only return a false positive if deletions and insertions
  89  * don't match, and have managed to produce a result which matches the
  90  * element.  This is much less likely.
  91  */
  92 bool invbloom_get(const struct invbloom *ib, const void *elem);
  93
  94 /**
  95  * invbloom_extract - try to recover an entry added to a bloom lookup table.
  96  * @ctx: the context to tal() the return value from.
  97  * @ib: the invertable bloom lookup table.
  98  *
  99  * This may be able to recover (and delete) an element which was
 100  * invbloom_insert()ed into the table (and not deleted).  This will
 101  * not work if the table is too full.
 102  *
 103  * It may return a bogus element if deletions and insertions don't
 104  * match.
 105  */
 106 void *invbloom_extract(const tal_t *ctx, struct invbloom *ib);
 107
 108 /**
 109  * invbloom_extract_negative - try to recover an entry deleted from a bloom lookup table.
 110  * @ctx: the context to tal() the return value from.
 111  * @ib: the invertable bloom lookup table.
 112  *
 113  * This may be able to recover (and insert/undo) an element which was
 114  * invbloom_delete()ed from the table (and not inserted).  This will
 115  * not work if the table is too full.
 116  *
 117  * It may return a bogus element if deletions and insertions don't
 118  * match.
 119  */
 120 void *invbloom_extract_negative(const tal_t *ctx, struct invbloom *ib);
 121
 122 /**
 123  * invbloom_subtract - return the differences of two IBLTs.
 124  * @ib1: the invertable bloom lookup table to alter
 125  * @ib2: the invertable bloom lookup table to subtract.
 126  *
 127  * This produces exactly the same result as if a new table had all the
 128  * elements only in @ib1 inserted, then all the elements onlt in @ib2
 129  * deleted.
 130  *
 131  * ie. if @ib1 and @ib2 are similar, the result may be a usable by
 132  * invbloom_extract and invbloom_extract_negative.
 133  */
 134 void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2);
 135
 136 /**
 137  * invbloom_empty - is an invertable bloom lookup table completely clean?
 138  * @ib: the invertable bloom lookup table
 139  *
 140  * This is always true if @ib has had the same elements inserted and
 141  * deleted.  It is far less likely to be true if different ones were
 142  * deleted than inserted.
 143  */
 144 bool invbloom_empty(const struct invbloom *ib);
 145 #endif /* CCAN_INVBLOOM_H */