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 provides interface and implementation of probabilistic 8 // data structure. 9 // 10 // The filter is resposible for creating small filter from a set of keys. 11 // These filter will then used to test whether a key is a member of the set. 12 // In many cases, a filter can cut down the number of disk seeks from a 13 // handful to a single disk seek per DB.Get call. 14 package filter 15 16 // Buffer is the interface that wraps basic Alloc, Write and WriteByte methods. 17 type Buffer interface { 18 // Alloc allocs n bytes of slice from the buffer. This also advancing 19 // write offset. 20 Alloc(n int) []byte 21 22 // Write appends the contents of p to the buffer. 23 Write(p []byte) (n int, err error) 24 25 // WriteByte appends the byte c to the buffer. 26 WriteByte(c byte) error 27 } 28 29 // Filter is the filter. 30 type Filter interface { 31 // Name returns the name of this policy. 32 // 33 // Note that if the filter encoding changes in an incompatible way, 34 // the name returned by this method must be changed. Otherwise, old 35 // incompatible filters may be passed to methods of this type. 36 Name() string 37 38 // NewGenerator creates a new filter generator. 39 NewGenerator() FilterGenerator 40 41 // Contains returns true if the filter contains the given key. 42 // 43 // The filter are filters generated by the filter generator. 44 Contains(filter, key []byte) bool 45 } 46 47 // FilterGenerator is the filter generator. 48 type FilterGenerator interface { 49 // Add adds a key to the filter generator. 50 // 51 // The key may become invalid after call to this method end, therefor 52 // key must be copied if implementation require keeping key for later 53 // use. The key should not modified directly, doing so may cause 54 // undefined results. 55 Add(key []byte) 56 57 // Generate generates filters based on keys passed so far. After call 58 // to Generate the filter generator maybe resetted, depends on implementation. 59 Generate(b Buffer) 60 } 61