README
¶
Generic Skipfilter
This package 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 theadsafe.
Documentation
¶
Index ¶
- type SkipFilter
- func (sf *SkipFilter[V, VK, F, VF]) Add(value V)
- func (sf *SkipFilter[V, VK, F, VF]) Len() int
- func (sf *SkipFilter[V, VK, F, VF]) MatchAny(filterKeys ...F) []V
- func (sf *SkipFilter[V, VK, F, VF]) Remove(value VK) (_ V, found bool)
- func (sf *SkipFilter[V, VK, F, VF]) Walk(start uint64, callback func(val V) bool) uint64
- type SkipKeyer
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type SkipFilter ¶
type SkipFilter[V SkipKeyer[VK], VK comparable, F SkipKeyer[VF], VF comparable] struct { // contains filtered or unexported fields }
SkipFilter combines a skip list with an lru cache of roaring bitmaps
func New ¶
func New[V SkipKeyer[VK], VK comparable, F SkipKeyer[VF], VF comparable](test func(value V, filter F) bool, size int) *SkipFilter[V, VK, F, VF]
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"
"strconv"
"github.com/nolotz/skipfilter"
)
type Object struct {
Key int
}
func (o *Object) SkipKey() int {
return o.Key
}
func (o *Object) String() string {
return strconv.Itoa(o.Key)
}
type Filter struct {
Key int
Value int
}
func (f *Filter) SkipKey() int {
return f.Key
}
func main() {
sf := skipfilter.New[*Object, int, *Filter, int](func(value *Object, filter *Filter) bool {
return value.Key%filter.Value == 0
}, 10)
fmt.Printf("%d", sf.Len())
}
Output: 0
func (*SkipFilter[V, VK, F, VF]) Add ¶
func (sf *SkipFilter[V, VK, F, VF]) Add(value V)
Add adds a value to the set
Example ¶
package main
import (
"fmt"
"strconv"
"github.com/nolotz/skipfilter"
)
type Object struct {
Key int
}
func (o *Object) SkipKey() int {
return o.Key
}
func (o *Object) String() string {
return strconv.Itoa(o.Key)
}
type Filter struct {
Key int
Value int
}
func (f *Filter) SkipKey() int {
return f.Key
}
func main() {
sf := skipfilter.New[*Object, int, *Filter, int](func(value *Object, filter *Filter) bool {
return value.Key%filter.Value == 0
}, 10)
for i := 0; i < 10; i++ {
sf.Add(&Object{
Key: i,
})
}
sf.Remove(0)
fmt.Printf("%d", sf.Len())
}
Output: 9
func (*SkipFilter[V, VK, F, VF]) Len ¶
func (sf *SkipFilter[V, VK, F, VF]) Len() int
Len returns the number of values in the set
func (*SkipFilter[V, VK, F, VF]) MatchAny ¶
func (sf *SkipFilter[V, VK, F, VF]) MatchAny(filterKeys ...F) []V
MatchAny returns a slice of values in the set matching any of the provided filters
Example ¶
package main
import (
"fmt"
"strconv"
"github.com/nolotz/skipfilter"
)
type Object struct {
Key int
}
func (o *Object) SkipKey() int {
return o.Key
}
func (o *Object) String() string {
return strconv.Itoa(o.Key)
}
type Filter struct {
Key int
Value int
}
func (f *Filter) SkipKey() int {
return f.Key
}
func main() {
sf := skipfilter.New[*Object, int, *Filter, int](func(value *Object, filter *Filter) bool {
return value.Key%filter.Value == 0
}, 10)
for i := 0; i < 10; i++ {
sf.Add(&Object{
Key: i,
})
}
fmt.Printf("Multiples of 2: %+v\n", sf.MatchAny(&Filter{
Key: 1,
Value: 2,
}))
fmt.Printf("Multiples of 3: %+v\n", sf.MatchAny(&Filter{
Key: 2,
Value: 3,
}))
}
Output: Multiples of 2: [0 2 4 6 8] Multiples of 3: [0 3 6 9]
func (*SkipFilter[V, VK, F, VF]) Remove ¶
func (sf *SkipFilter[V, VK, F, VF]) Remove(value VK) (_ V, found bool)
Remove removes a value from the set
func (*SkipFilter[V, VK, F, VF]) Walk ¶
func (sf *SkipFilter[V, VK, F, VF]) Walk(start uint64, callback func(val V) 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"
"strconv"
"github.com/nolotz/skipfilter"
)
type Object struct {
Key int
}
func (o *Object) SkipKey() int {
return o.Key
}
func (o *Object) String() string {
return strconv.Itoa(o.Key)
}
type Filter struct {
Key int
Value int
}
func (f *Filter) SkipKey() int {
return f.Key
}
func main() {
sf := skipfilter.New[*Object, int, *Filter, int](nil, 10)
for i := 0; i < 10; i++ {
sf.Add(&Object{
Key: i,
})
}
var n []*Object
sf.Walk(0, func(v *Object) bool {
n = append(n, v)
return true
})
fmt.Printf("%d", len(n))
}
Output: 10
Example (Limit) ¶
package main
import (
"fmt"
"strconv"
"github.com/nolotz/skipfilter"
)
type Object struct {
Key int
}
func (o *Object) SkipKey() int {
return o.Key
}
func (o *Object) String() string {
return strconv.Itoa(o.Key)
}
type Filter struct {
Key int
Value int
}
func (f *Filter) SkipKey() int {
return f.Key
}
func main() {
sf := skipfilter.New[*Object, int, *Filter, int](nil, 10)
for i := 0; i < 10; i++ {
sf.Add(&Object{
Key: i,
})
}
var n []int
sf.Walk(0, func(v *Object) bool {
n = append(n, v.Key)
return len(n) < 5
})
fmt.Printf("%d", len(n))
}
Output: 5
Example (Start) ¶
package main
import (
"fmt"
"strconv"
"github.com/nolotz/skipfilter"
)
type Object struct {
Key int
}
func (o *Object) SkipKey() int {
return o.Key
}
func (o *Object) String() string {
return strconv.Itoa(o.Key)
}
type Filter struct {
Key int
Value int
}
func (f *Filter) SkipKey() int {
return f.Key
}
func main() {
sf := skipfilter.New[*Object, int, *Filter, int](nil, 10)
for i := 0; i < 10; i++ {
sf.Add(&Object{
Key: i,
})
}
var n []int
sf.Walk(5, func(v *Object) bool {
n = append(n, v.Key)
return true
})
fmt.Printf("%d", len(n))
}
Output: 5
type SkipKeyer ¶
type SkipKeyer[K comparable] interface { SkipKey() K }
Source Files