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 4
  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->count = tal_arrz(ib, s32, n_elems);
  27                 ib->idsum = tal_arrz(ib, u8, id_size * n_elems);
  28                 if (!ib->count || !ib->idsum)
  29                         ib = tal_free(ib);
  30         }
  31         return ib;
  32 }
  33
  34 static size_t hash_bucket(const struct invbloom *ib, const void *id, size_t i)
  35 {
  36         return hash((const char *)id, ib->id_size, ib->salt+i*7) % ib->n_elems;
  37 }
  38
  39 static u8 *idsum_ptr(const struct invbloom *ib, size_t bucket)
  40 {
  41         return (u8 *)ib->idsum + bucket * ib->id_size;
  42 }
  43
  44 static void add_to_bucket(struct invbloom *ib, size_t n, const u8 *id)
  45 {
  46         size_t i;
  47         u8 *idsum = idsum_ptr(ib, n);
  48
  49         ib->count[n]++;
  50
  51         for (i = 0; i < ib->id_size; i++)
  52                 idsum[i] ^= id[i];
  53 }
  54
  55 static void remove_from_bucket(struct invbloom *ib, size_t n, const u8 *id)
  56 {
  57         size_t i;
  58         u8 *idsum = idsum_ptr(ib, n);
  59
  60         ib->count[n]--;
  61         for (i = 0; i < ib->id_size; i++)
  62                 idsum[i] ^= id[i];
  63 }
  64
  65 void invbloom_insert(struct invbloom *ib, const void *id)
  66 {
  67         unsigned int i;
  68
  69         for (i = 0; i < NUM_HASHES; i++)
  70                 add_to_bucket(ib, hash_bucket(ib, id, i), id);
  71 }
  72
  73 void invbloom_delete(struct invbloom *ib, const void *id)
  74 {
  75         unsigned int i;
  76
  77         for (i = 0; i < NUM_HASHES; i++)
  78                 remove_from_bucket(ib, hash_bucket(ib, id, i), id);
  79 }
  80
  81 static bool all_zero(const u8 *mem, size_t size)
  82 {
  83         unsigned int i;
  84
  85         for (i = 0; i < size; i++)
  86                 if (mem[i])
  87                         return false;
  88         return true;
  89 }
  90
  91 bool invbloom_get(const struct invbloom *ib, const void *id)
  92 {
  93         unsigned int i;
  94
  95         for (i = 0; i < NUM_HASHES; i++) {
  96                 size_t h = hash_bucket(ib, id, i);
  97                 u8 *idsum = idsum_ptr(ib, h);
  98
  99                 if (ib->count[h] == 0 && all_zero(idsum, ib->id_size))
 100                         return false;
 101
 102                 if (ib->count[h] == 1)
 103                         return (memcmp(idsum, id, ib->id_size) == 0);
 104         }
 105         return false;
 106 }
 107
 108 static void *extract(const tal_t *ctx, struct invbloom *ib, int count)
 109 {
 110         size_t i;
 111
 112         /* FIXME: this makes full extraction O(n^2). */
 113         for (i = 0; i < ib->n_elems; i++) {
 114                 void *id;
 115
 116                 if (ib->count[i] != count)
 117                         continue;
 118
 119                 id = tal_dup(ctx, u8, idsum_ptr(ib, i), ib->id_size, 0);
 120                 return id;
 121         }
 122         return NULL;
 123 }
 124
 125 void *invbloom_extract(const tal_t *ctx, struct invbloom *ib)
 126 {
 127         void *id;
 128
 129         id = extract(ctx, ib, 1);
 130         if (id)
 131                 invbloom_delete(ib, id);
 132         return id;
 133 }
 134
 135 void *invbloom_extract_negative(const tal_t *ctx, struct invbloom *ib)
 136 {
 137         void *id;
 138
 139         id = extract(ctx, ib, -1);
 140         if (id)
 141                 invbloom_insert(ib, id);
 142         return id;
 143 }
 144
 145 void invbloom_subtract(struct invbloom *ib1, const struct invbloom *ib2)
 146 {
 147         size_t i;
 148
 149         assert(ib1->n_elems == ib2->n_elems);
 150         assert(ib1->id_size == ib2->id_size);
 151         assert(ib1->salt == ib2->salt);
 152
 153         for (i = 0; i < ib1->n_elems; i++)
 154                 ib1->count[i] -= ib2->count[i];
 155
 156         for (i = 0; i < ib1->n_elems * ib1->id_size; i++)
 157                 ib1->idsum[i] ^= ib2->idsum[i];
 158 }
 159
 160 bool invbloom_empty(const struct invbloom *ib)
 161 {
 162         size_t i;
 163
 164         for (i = 0; i < ib->n_elems; i++) {
 165                 if (ib->count[i])
 166                         return false;
 167                 if (!all_zero(idsum_ptr(ib, i), ib->id_size))
 168                         return false;
 169         }
 170         return true;
 171 }