skipfilter

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 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]
  • 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

• New
• SkipFilter.Add
• SkipFilter.MatchAny
• SkipFilter.Walk (All)
• SkipFilter.Walk (Limit)
• SkipFilter.Walk (Start)

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
}