README
¶
cedar
Package cedar implementes double-array trie and aho corasick
It is implements the cedar and paper by golang.
Install
go get -u github.com/vcaesar/cedar
Usage
package main
import (
"fmt"
"github.com/vcaesar/cedar"
)
func main() {
// Create a new cedar trie.
d := cedar.New()
d.Insert([]byte("ab"), 1)
d.Insert([]byte("abc"), 2)
d.Insert([]byte("abcd"), 3)
fmt.Println(d.Find([]byte("ab"), 0))
fmt.Println(d.Find([]byte("bc"), 0))
fmt.Println(d.PrefixMatch([]byte("bc"), 0))
}
License
This is released under the BSD-2 license, following the original license of C++ cedar.
Reference
Documentation
¶
Index ¶
- Constants
- Variables
- type Block
- type Cedar
- func (cd *Cedar) Delete(key []byte, reduced ...bool) error
- func (cd *Cedar) Find(key []byte, from int, reduced ...bool) (int, error)
- func (cd *Cedar) Get(key []byte) (value int, err error)
- func (cd *Cedar) Insert(key []byte, val int) error
- func (cd *Cedar) Jump(key []byte, from int, reduced ...bool) (to int, err error)
- func (cd *Cedar) Update(key []byte, value int, reduced ...bool) error
- func (cd *Cedar) Value(path int) (val int, err error)
- type NInfo
- type Node
Constants ¶
const ( // ValLimit cedar value limit ValLimit = int(^uint(0) >> 1) NoVal = -1 )
Variables ¶
var ( // ErrNoKey not have key error ErrNoKey = errors.New("cedar: not have key") // ErrNoVal not have value error ErrNoVal = errors.New("cedar: not have val") // ErrInvalidKey invalid key error ErrInvalidKey = errors.New("cedar: invalid key") // ErrInvalidValue invalid value error ErrInvalidVal = errors.New("cedar: invalid val") )
Functions ¶
This section is empty.
Types ¶
type Block ¶
type Block struct {
// contains filtered or unexported fields
}
Block stores the linked-list pointers and the stats info for blocks.
Because of type conversion, this version all int16 and int32 uses int, witch will be optimized in the next version.
type Cedar ¶
type Cedar struct {
// contains filtered or unexported fields
}
Cedar holds all of the information about double array trie.
func (*Cedar) Find ¶
Find key from double array trie, with `from` as the cursor to traverse the nodes.
func (*Cedar) Jump ¶
Jump jump a node `from` to another node by following the `path`, split by find()
type NInfo ¶
type NInfo struct {
// contains filtered or unexported fields
}
NInfo stores the information about the trie
type Node ¶
type Node struct {
// contains filtered or unexported fields
}
Node contains the array of `base` and `check` as specified in the paper: "An efficient implementation of trie structures" https://dl.acm.org/citation.cfm?id=146691
Source Files
Directories