Documentation
¶
Overview ¶
package skipfilter provides a data structure that combines a skiplist with a roaring bitmap cache.
This library was created to efficiently filter a multi-topic message input stream against a set of subscribers, each having a list of topic subscriptions expressed as regular expressions. Idealy, each subscriber should test each topic at most once to determine whether it wants to receive messages from the topic.
In this case, the skip list provides an efficient discontinuous slice of subscribers and the roaring bitmap for each topic provides an efficient ordered discontinuous set of all subscribers that have indicated that they wish to receive messages on the topic.
Filter bitmaps are stored in an LRU cache of variable size (default 100,000).
This package is not theadsafe.
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type SkipFilter ¶
type SkipFilter struct {
// contains filtered or unexported fields
}
func New ¶
func New(test func(value interface{}, filter interface{}) bool, size int) *SkipFilter
New creates a new SkipFilter.
test - should return true if the value passes the provided filter.
size - controls the size of the LRU cache. Defaults to 100,000 if 0 or less.
should be tuned to match or exceed the expected filter cardinality.
Example ¶
package main
import (
"fmt"
"github.com/kevburnsjr/skipfilter"
)
func main() {
sf := skipfilter.New(func(value interface{}, filter interface{}) bool {
return value.(int)%filter.(int) == 0
}, 10)
fmt.Printf("%d", sf.Len())
}
Output: 0
func (*SkipFilter) Add ¶
func (sf *SkipFilter) Add(value interface{})
Add adds a value to the set
Example ¶
package main
import (
"fmt"
"github.com/kevburnsjr/skipfilter"
)
func main() {
sf := skipfilter.New(func(value interface{}, filter interface{}) bool {
return value.(int)%filter.(int) == 0
}, 10)
for i := 0; i < 10; i++ {
sf.Add(i)
}
sf.Remove(0)
fmt.Printf("%d", sf.Len())
}
Output: 9
func (*SkipFilter) Len ¶
func (sf *SkipFilter) Len() int
Len returns the number of values in the set
func (*SkipFilter) MatchAny ¶
func (sf *SkipFilter) MatchAny(filterKeys ...interface{}) []interface{}
MatchAny returns a slice of values in the set matching any of the provided filters
Example ¶
package main
import (
"fmt"
"github.com/kevburnsjr/skipfilter"
)
func main() {
sf := skipfilter.New(func(value interface{}, filter interface{}) bool {
return value.(int)%filter.(int) == 0
}, 10)
for i := 0; i < 10; i++ {
sf.Add(i)
}
fmt.Printf("Multiples of 2: %+v\n", sf.MatchAny(2))
fmt.Printf("Multiples of 3: %+v\n", sf.MatchAny(3))
}
Output: Multiples of 2: [0 2 4 6 8] Multiples of 3: [0 3 6 9]
func (*SkipFilter) Remove ¶
func (sf *SkipFilter) Remove(value interface{})
Remove removes a value from the set
func (*SkipFilter) Walk ¶
func (sf *SkipFilter) Walk(start uint64, callback func(val interface{}) bool) uint64
Walk executes callback for each value in the set beginning at `start` index. Return true in callback to continue iterating, false to stop. Returned uint64 is index of `next` element (send as `start` to continue iterating)
Example (All) ¶
package main
import (
"fmt"
"github.com/kevburnsjr/skipfilter"
)
func main() {
sf := skipfilter.New(nil, 10)
for i := 0; i < 10; i++ {
sf.Add(i)
}
var n []int
sf.Walk(0, func(v interface{}) bool {
n = append(n, v.(int))
return true
})
fmt.Printf("%d", len(n))
}
Output: 10
Example (Limit) ¶
package main
import (
"fmt"
"github.com/kevburnsjr/skipfilter"
)
func main() {
sf := skipfilter.New(nil, 10)
for i := 0; i < 10; i++ {
sf.Add(i)
}
var n []int
sf.Walk(0, func(v interface{}) bool {
n = append(n, v.(int))
return len(n) < 5
})
fmt.Printf("%d", len(n))
}
Output: 5
Example (Start) ¶
package main
import (
"fmt"
"github.com/kevburnsjr/skipfilter"
)
func main() {
sf := skipfilter.New(nil, 10)
for i := 0; i < 10; i++ {
sf.Add(i)
}
var n []int
sf.Walk(5, func(v interface{}) bool {
n = append(n, v.(int))
return true
})
fmt.Printf("%d", len(n))
}
Output: 5
Source Files