vendor/github.com/syndtr/goleveldb/leveldb/filter/bloom_test.go

   1 // Copyright (c) 2012, Suryandaru Triandana <syndtr@gmail.com>
   2 // All rights reserved.
   3 //
   4 // Use of this source code is governed by a BSD-style license that can be
   5 // found in the LICENSE file.
   6
   7 package filter
   8
   9 import (
  10         "encoding/binary"
  11         "github.com/syndtr/goleveldb/leveldb/util"
  12         "testing"
  13 )
  14
  15 type harness struct {
  16         t *testing.T
  17
  18         bloom     Filter
  19         generator FilterGenerator
  20         filter    []byte
  21 }
  22
  23 func newHarness(t *testing.T) *harness {
  24         bloom := NewBloomFilter(10)
  25         return &harness{
  26                 t:         t,
  27                 bloom:     bloom,
  28                 generator: bloom.NewGenerator(),
  29         }
  30 }
  31
  32 func (h *harness) add(key []byte) {
  33         h.generator.Add(key)
  34 }
  35
  36 func (h *harness) addNum(key uint32) {
  37         var b [4]byte
  38         binary.LittleEndian.PutUint32(b[:], key)
  39         h.add(b[:])
  40 }
  41
  42 func (h *harness) build() {
  43         b := &util.Buffer{}
  44         h.generator.Generate(b)
  45         h.filter = b.Bytes()
  46 }
  47
  48 func (h *harness) reset() {
  49         h.filter = nil
  50 }
  51
  52 func (h *harness) filterLen() int {
  53         return len(h.filter)
  54 }
  55
  56 func (h *harness) assert(key []byte, want, silent bool) bool {
  57         got := h.bloom.Contains(h.filter, key)
  58         if !silent && got != want {
  59                 h.t.Errorf("assert on '%v' failed got '%v', want '%v'", key, got, want)
  60         }
  61         return got
  62 }
  63
  64 func (h *harness) assertNum(key uint32, want, silent bool) bool {
  65         var b [4]byte
  66         binary.LittleEndian.PutUint32(b[:], key)
  67         return h.assert(b[:], want, silent)
  68 }
  69
  70 func TestBloomFilter_Empty(t *testing.T) {
  71         h := newHarness(t)
  72         h.build()
  73         h.assert([]byte("hello"), false, false)
  74         h.assert([]byte("world"), false, false)
  75 }
  76
  77 func TestBloomFilter_Small(t *testing.T) {
  78         h := newHarness(t)
  79         h.add([]byte("hello"))
  80         h.add([]byte("world"))
  81         h.build()
  82         h.assert([]byte("hello"), true, false)
  83         h.assert([]byte("world"), true, false)
  84         h.assert([]byte("x"), false, false)
  85         h.assert([]byte("foo"), false, false)
  86 }
  87
  88 func nextN(n int) int {
  89         switch {
  90         case n < 10:
  91                 n += 1
  92         case n < 100:
  93                 n += 10
  94         case n < 1000:
  95                 n += 100
  96         default:
  97                 n += 1000
  98         }
  99         return n
 100 }
 101
 102 func TestBloomFilter_VaryingLengths(t *testing.T) {
 103         h := newHarness(t)
 104         var mediocre, good int
 105         for n := 1; n < 10000; n = nextN(n) {
 106                 h.reset()
 107                 for i := 0; i < n; i++ {
 108                         h.addNum(uint32(i))
 109                 }
 110                 h.build()
 111
 112                 got := h.filterLen()
 113                 want := (n * 10 / 8) + 40
 114                 if got > want {
 115                         t.Errorf("filter len test failed, '%d' > '%d'", got, want)
 116                 }
 117
 118                 for i := 0; i < n; i++ {
 119                         h.assertNum(uint32(i), true, false)
 120                 }
 121
 122                 var rate float32
 123                 for i := 0; i < 10000; i++ {
 124                         if h.assertNum(uint32(i+1000000000), true, true) {
 125                                 rate++
 126                         }
 127                 }
 128                 rate /= 10000
 129                 if rate > 0.02 {
 130                         t.Errorf("false positive rate is more than 2%%, got %v, at len %d", rate, n)
 131                 }
 132                 if rate > 0.0125 {
 133                         mediocre++
 134                 } else {
 135                         good++
 136                 }
 137         }
 138         t.Logf("false positive rate: %d good, %d mediocre", good, mediocre)
 139         if mediocre > good/5 {
 140                 t.Error("mediocre false positive rate is more than expected")
 141         }
 142 }