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

   1 /* Licensed under BSD-MIT - see LICENSE file for details */
   2 #include "invbloom.h"
   3 #include <ccan/hash/hash.h>
   4 #include <ccan/endian/endian.h>
   5 #include <assert.h>
   6
   7 /*      "We will show that hash_count values of 3 or 4 work well in practice"
   8
   9         From:
  10
  11         Eppstein, David, et al. "What's the difference?: efficient set reconciliation without prior context." ACM SIGCOMM Computer Communication Review. Vol. 41. No. 4. ACM, 2011. http://conferences.sigcomm.org/sigcomm/2011/papers/sigcomm/p218.pdf
  12 */
  13 #define NUM_HASHES 3
  14
  15 struct invbloom *invbloom_new_(const tal_t *ctx,
  16                                size_t id_size,
  17                                size_t n_elems,
  18                                u32 salt)
  19 {
  20         struct invbloom *ib = tal(ctx, struct invbloom);
  21
  22         if (ib) {
  23                 ib->n_elems = n_elems;
  24                 ib->id_size = id_size;
  25                 ib->salt = salt;
  26                 ib->singleton = NULL;
  27                 ib->count = tal_arrz(ib, s32, n_elems);
  28                 ib->idsum = tal_arrz(ib, u8, id_size * n_elems);
  29                 if (!ib->count || !ib->idsum)
  30                         ib = tal_free(ib);
  31         }
  32         return ib;
  33 }
  34
  35 void invbloom_singleton_cb_(struct invbloom *ib,
  36                             void (*cb)(struct invbloom *,
  37                                        size_t bucket, bool, void *),
  38                             void *data)
  39 {
  40         ib->singleton = cb;
  41         ib->singleton_data = data;
  42 }
  43
  44 static size_t hash_bucket(const struct invbloom *ib, const void *id, size_t i)
  45 {
  46         return hash((const char *)id, ib->id_size, ib->salt+i*7) % ib->n_elems;
  47 }
  48
  49 static u8 *idsum_ptr(const struct invbloom *ib, size_t bucket)
  50 {
  51         return (u8 *)ib->idsum + bucket * ib->id_size;
  52 }
  53
  54 static void check_for_singleton(struct invbloom *ib, size_t bucket, bool before)
  55 {
  56         if (!ib->singleton)
  57                 return;
  58
  59         if (ib->count[bucket] != 1 && ib->count[bucket] != -1)
  60                 return;
  61
  62         ib->singleton(ib, bucket, before, ib->singleton_data);
  63 }
  64
  65 static void add_to_bucket(struct invbloom *ib, size_t n, const u8 *id)
  66 {
  67         size_t i;
  68         u8 *idsum = idsum_ptr(ib, n);
  69
  70         check_for_singleton(ib, n, true);
  71
  72         ib->count[n]++;
  73
  74         for (i = 0; i < ib->id_size; i++)
  75                 idsum[i] ^= id[i];
  76
  77         check_for_singleton(ib, n, false);
  78 }
  79
  80 static void remove_from_bucket(struct invbloom *ib, size_t n, const u8 *id)
  81 {
  82         size_t i;
  83         u8 *idsum = idsum_ptr(ib, n);
  84
  85         check_for_singleton(ib, n, true);
  86
  87         ib->count[n]--;
  88         for (i = 0; i < ib->id_size; i++)
  89                 idsum[i] ^= id[i];
  90
  91         check_for_singleton(ib, n, false);
  92 }
  93
  94 void invbloom_insert(struct invbloom *ib, const void *id)
  95 {
  96         unsigned int i;
  97
  98         for (i = 0; i < NUM_HASHES; i++)
  99                 add_to_bucket(ib, hash_bucket(ib, id, i), id);
 100 }
 101
 102 void invbloom_delete(struct invbloom *ib, const void *id)
 103 {
 104         unsigned int i;
 105
 106         for (i = 0; i < NUM_HASHES; i++)
 107                 remove_from_bucket(ib, hash_bucket(ib, id, i), id);
 108 }
 109
 110 static bool all_zero(const u8 *mem, size_t size)
 111 {
 112         unsigned int i;
 113
 114         for (i = 0; i < size; i++)
 115                 if (mem[i])
 116                         return false;
 117         return true;
 118 }
 119
 120 bool invbloom_get(const struct invbloom *ib, const void *id)
 121 {
 122         unsigned int i;
 123
 124         for (i = 0; i < NUM_HASHES; i++) {
 125                 size_t h = hash_bucket(ib, id, i);
 126                 u8 *idsum = idsum_ptr(ib, h);
 127
 128                 if (ib->count[h] == 0 && all_zero(idsum, ib->id_size))
 129                         return false;
 130
 131                 if (ib->count[h] == 1)
 132                         return (memcmp(idsum, id, ib->id_size) == 0);
 133         }
 134         return false;
 135 }
 136
 137 static void *extract(const tal_t *ctx, struct invbloom *ib, int count)
 138 {
 139         size_t i;
 140
 141         /* FIXME: this makes full extraction O(n^2). */
 142         for (i = 0; i < ib->n_elems; i++) {
 143                 void *id;
 144
 145                 if (ib->count[i] != count)
 146                         continue;
 147
 148                 id = tal_dup_arr(ctx, u8, idsum_ptr(ib, i), ib->id_size, 0);
 149                 return id;
 150         }
 151         return NULL;
 152 }
 153
 154 void *invbloom_extract(const tal_t *ctx, struct invbloom *ib)
 155 {
 156         void *id;
 157
 158         id = extract(ctx, ib, 1);
 159         if (id)
 160                 invbloom_delete(ib, id);
 161         return id;
 162 }
 163
 164 void *invbloom_extract_negative(const tal_t *ctx, struct invbloom *ib)
 165 {
 166         void *id;
 167
 168         id = extract(ctx, ib, -1);
 169         if (id)
 170                 invbloom_insert(ib, id);
 171         return id;
 172 }
 173
 174 void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2)
 175 {
 176         size_t i;
 177
 178         assert(ib1->n_elems == ib2->n_elems);
 179         assert(ib1->id_size == ib2->id_size);
 180         assert(ib1->salt == ib2->salt);
 181
 182         for (i = 0; i < ib1->n_elems; i++)
 183                 check_for_singleton(ib1, i, true);
 184
 185         for (i = 0; i < ib1->n_elems * ib1->id_size; i++)
 186                 ib1->idsum[i] ^= ib2->idsum[i];
 187
 188         for (i = 0; i < ib1->n_elems; i++) {
 189                 ib1->count[i] -= ib2->count[i];
 190                 check_for_singleton(ib1, i, false);
 191         }
 192 }
 193
 194 bool invbloom_empty(const struct invbloom *ib)
 195 {
 196         size_t i;
 197
 198         for (i = 0; i < ib->n_elems; i++) {
 199                 if (ib->count[i])
 200                         return false;
 201                 if (!all_zero(idsum_ptr(ib, i), ib->id_size))
 202                         return false;
 203         }
 204         return true;
 205 }