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/tal/tal.h>
   6
   7 struct invbloom {
   8         size_t n_elems;
   9         size_t id_size;
  10         u32 hashsum_bytes; /* 0 - 4. */
  11         u32 salt;
  12         s32 *count; /* [n_elems] */
  13         u8 *idsum; /* [n_elems][id_size] */
  14 };
  15
  16 /**
  17  * invbloom_new - create a new invertable bloom lookup table
  18  * @ctx: context to tal() from, or NULL.
  19  * @type: type to place into the buckets (must not contain padding)
  20  * @n_elems: number of entries in table
  21  * @salt: 32 bit seed for table
  22  *
  23  * Returns a new table, which can be freed with tal_free().
  24  */
  25 #define invbloom_new(ctx, type, n_elems, salt)  \
  26         invbloom_new_((ctx), sizeof(type), (n_elems), (salt))
  27 struct invbloom *invbloom_new_(const tal_t *ctx,
  28                                size_t id_size,
  29                                size_t n_elems, u32 salt);
  30
  31
  32 /**
  33  * invbloom_insert - add a new element
  34  * @ib: the invertable bloom lookup table.
  35  * @elem: the element
  36  *
  37  * This is guaranteed to be the inverse of invbloom_delete.
  38  */
  39 void invbloom_insert(struct invbloom *ib, const void *elem);
  40
  41 /**
  42  * invbloom_delete - remove an element
  43  * @ib: the invertable bloom lookup table.
  44  * @elem: the element
  45  *
  46  * Note that this doesn't check the element was previously added (as
  47  * that can not be done in general anyway).
  48  *
  49  * This is guaranteed to be the inverse of invbloom_delete.
  50  */
  51 void invbloom_delete(struct invbloom *ib, const void *elem);
  52
  53 /**
  54  * invbloom_get - check if an element is (probably) in the table.
  55  * @ib: the invertable bloom lookup table.
  56  * @elem: the element
  57  *
  58  * This may return a false negative if the table is too full.
  59  *
  60  * It will only return a false positive if deletions and insertions
  61  * don't match, and have managed to produce a result which matches the
  62  * element.  This is much less likely.
  63  */
  64 bool invbloom_get(const struct invbloom *ib, const void *elem);
  65
  66 /**
  67  * invbloom_extract - try to recover an entry added to a bloom lookup table.
  68  * @ctx: the context to tal() the return value from.
  69  * @ib: the invertable bloom lookup table.
  70  *
  71  * This may be able to recover (and delete) an element which was
  72  * invbloom_insert()ed into the table (and not deleted).  This will
  73  * not work if the table is too full.
  74  *
  75  * It may return a bogus element if deletions and insertions don't
  76  * match.
  77  */
  78 void *invbloom_extract(const tal_t *ctx, struct invbloom *ib);
  79
  80 /**
  81  * invbloom_extract_negative - try to recover an entry deleted from a bloom lookup table.
  82  * @ctx: the context to tal() the return value from.
  83  * @ib: the invertable bloom lookup table.
  84  *
  85  * This may be able to recover (and insert/undo) an element which was
  86  * invbloom_delete()ed from the table (and not inserted).  This will
  87  * not work if the table is too full.
  88  *
  89  * It may return a bogus element if deletions and insertions don't
  90  * match.
  91  */
  92 void *invbloom_extract_negative(const tal_t *ctx, struct invbloom *ib);
  93
  94 /**
  95  * invbloom_subtract - return the differences of two IBLTs.
  96  * @ib1: the invertable bloom lookup table to alter
  97  * @ib2: the invertable bloom lookup table to subtract.
  98  *
  99  * This produces exactly the same result as if a new table had all the
 100  * elements only in @ib1 inserted, then all the elements onlt in @ib2
 101  * deleted.
 102  *
 103  * ie. if @ib1 and @ib2 are similar, the result may be a usable by
 104  * invbloom_extract and invbloom_extract_negative.
 105  */
 106 void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2);
 107
 108 /**
 109  * invbloom_empty - is an invertable bloom lookup table completely clean?
 110  * @ib: the invertable bloom lookup table
 111  *
 112  * This is always true if @ib has had the same elements inserted and
 113  * deleted.  It is far less likely to be true if different ones were
 114  * deleted than inserted.
 115  */
 116 bool invbloom_empty(const struct invbloom *ib);
 117 #endif /* CCAN_INVBLOOM_H */