README
¶
critbitgo
Crit-bit trees in golang and its applications.
This implementation extended to handle the key that contains a null character from C implementation.
Usage
// Create Trie
trie := critbitgo.NewTrie()
// Insert
trie.Insert([]byte("aa"), "value1")
trie.Insert([]byte("bb"), "value2")
trie.Insert([]byte("ab"), "value3")
// Get
v, ok := trie.Get([]byte("aa"))
fmt.Println(v, ok) // -> value1 true
// Iterate containing keys
trie.Allprefixed([]byte{}, func(key []byte, value interface{}) bool {
fmt.Println(key, value) // -> [97 97] value1
// [97 98] value3
// [98 98] value2
return true
})
// Delete
v, ok = trie.Delete([]byte("aa"))
fmt.Println(v, ok) // -> value1 true
v, ok = trie.Delete([]byte("aa"))
fmt.Println(v, ok) // -> <nil> false
License
MIT
Documentation
¶
Index ¶
- type Net
- func (n *Net) Add(r *net.IPNet, value interface{}) (err error)
- func (n *Net) AddCIDR(s string, value interface{}) (err error)
- func (n *Net) Clear()
- func (n *Net) ContainedIP(ip net.IP) (contained bool, err error)
- func (n *Net) Delete(r *net.IPNet) (value interface{}, ok bool, err error)
- func (n *Net) DeleteCIDR(s string) (value interface{}, ok bool, err error)
- func (n *Net) Get(r *net.IPNet) (value interface{}, ok bool, err error)
- func (n *Net) GetCIDR(s string) (value interface{}, ok bool, err error)
- func (n *Net) Match(r *net.IPNet) (route *net.IPNet, value interface{}, err error)
- func (n *Net) MatchCIDR(s string) (route *net.IPNet, value interface{}, err error)
- func (n *Net) MatchIP(ip net.IP) (route *net.IPNet, value interface{}, err error)
- func (n *Net) Size() int
- func (n *Net) Walk(r *net.IPNet, handle func(*net.IPNet, interface{}) bool)
- func (n *Net) WalkMatch(r *net.IPNet, handle func(*net.IPNet, interface{}) bool)
- func (n *Net) WalkPrefix(r *net.IPNet, handle func(*net.IPNet, interface{}) bool)
- type SortedMap
- func (m *SortedMap) Clear()
- func (m *SortedMap) Contains(key string) bool
- func (m *SortedMap) Delete(key string) (value interface{}, ok bool)
- func (m *SortedMap) Each(prefix string, handle func(key string, value interface{}) bool) bool
- func (m *SortedMap) Get(key string) (value interface{}, ok bool)
- func (m *SortedMap) Keys() []string
- func (m *SortedMap) Set(key string, value interface{})
- func (m *SortedMap) Size() int
- type Trie
- func (t *Trie) Allprefixed(prefix []byte, handle func(key []byte, value interface{}) bool) bool
- func (t *Trie) Clear()
- func (t *Trie) Contains(key []byte) bool
- func (t *Trie) Delete(key []byte) (value interface{}, ok bool)
- func (t *Trie) Dump(w io.Writer)
- func (t *Trie) Get(key []byte) (value interface{}, ok bool)
- func (t *Trie) Insert(key []byte, value interface{}) bool
- func (t *Trie) LongestPrefix(given []byte) (key []byte, value interface{}, ok bool)
- func (t *Trie) Set(key []byte, value interface{})
- func (t *Trie) Size() int
- func (t *Trie) Walk(start []byte, handle func(key []byte, value interface{}) bool) bool
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Net ¶
type Net struct {
// contains filtered or unexported fields
}
IP routing table.
func (*Net) ContainedIP ¶ added in v1.2.0
Return a bool indicating whether a route would be found
func (*Net) Delete ¶
Delete a specific route. If `r` is not IP4/IPv6 network or a route is not found, `ok` is false.
func (*Net) DeleteCIDR ¶
Delete a specific route. If `s` is not CIDR notation or a route is not found, `ok` is false.
func (*Net) Get ¶
Get a specific route. If `r` is not IPv4/IPv6 network or a route is not found, `ok` is false.
func (*Net) GetCIDR ¶
Get a specific route. If `s` is not CIDR notation or a route is not found, `ok` is false.
func (*Net) Match ¶
Return a specific route by using the longest prefix matching. If `r` is not IPv4/IPv6 network or a route is not found, `route` is nil.
func (*Net) MatchCIDR ¶
Return a specific route by using the longest prefix matching. If `s` is not CIDR notation, or a route is not found, `route` is nil.
func (*Net) MatchIP ¶
Return a specific route by using the longest prefix matching. If `ip` is invalid IP, or a route is not found, `route` is nil.
func (*Net) Walk ¶ added in v1.3.0
Walk iterates routes from a given route. handle is called with arguments route and value (if handle returns `false`, the iteration is aborted)
type SortedMap ¶
type SortedMap struct {
// contains filtered or unexported fields
}
The map is sorted according to the natural ordering of its keys
type Trie ¶
type Trie struct {
// contains filtered or unexported fields
}
Crit-bit Tree
func (*Trie) Allprefixed ¶
fetching elements with a given prefix. handle is called with arguments key and value (if handle returns `false`, the iteration is aborted)
func (*Trie) LongestPrefix ¶ added in v1.1.0
Search for the longest matching key from the beginning of the given key. if `key` is in Trie, `ok` is true.
Source Files