cedar

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.Jump([]byte("ab"), 0))
	fmt.Println(d.Find([]byte("bc"), 0))

	fmt.Println(d.PrefixMatch([]byte("bc"), 0))
	fmt.Println(d.ExactMatch([]byte("ab")))
}

License

This is released under the BSD-2 license, following the original license of C++ cedar.

Reference

• cedar - C++ implementation of efficiently-updatable double-array trie, and thanks for cedarwood.

Documentation

Index

• Constants
• Variables
• type Block
• type Cedar
  • func New(reduced ...bool) *Cedar
  • func (cd *Cedar) Delete(key []byte) error
  • func (cd *Cedar) ExactMatch(key []byte) (int, bool)
  • func (cd *Cedar) Find(key []byte, from int) (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) (to int, err error)
  • func (cd *Cedar) PrefixMatch(key []byte, n ...int) (ids []int)
  • func (cd *Cedar) PrefixPredict(key []byte, n ...int) (ids []int)
  • func (cd *Cedar) Update(key []byte, value int) 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 not have value
	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")
	// ErrInvalidVal invalid value error
	ErrInvalidVal = errors.New("cedar: invalid val")
)

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 {
	// Reduced option the reduced trie
	Reduced bool
	// contains filtered or unexported fields
}

Cedar holds all of the information about double array trie.

func New

func New(reduced ...bool) *Cedar

New initialize the Cedar for further use

func (*Cedar) Delete

func (cd *Cedar) Delete(key []byte) error

Delete the key from the trie, the internal interface that works on []byte

func (*Cedar) ExactMatch

func (cd *Cedar) ExactMatch(key []byte) (int, bool)

ExactMatch to check if `key` is in the dictionary.

func (*Cedar) Find

func (cd *Cedar) Find(key []byte, from int) (int, error)

Find key from double array trie, with `from` as the cursor to traverse the nodes.

func (*Cedar) Get

func (cd *Cedar) Get(key []byte) (value int, err error)

Get get the key value on []byte

func (*Cedar) Insert

func (cd *Cedar) Insert(key []byte, val int) error

Insert the key for the value on []byte

func (*Cedar) Jump

func (cd *Cedar) Jump(key []byte, from int) (to int, err error)

Jump jump a node `from` to another node by following the `path`, split by find()

func (*Cedar) PrefixMatch

func (cd *Cedar) PrefixMatch(key []byte, n ...int) (ids []int)

PrefixMatch return the collection of the common prefix in the dictionary with the `key`

func (*Cedar) PrefixPredict

func (cd *Cedar) PrefixPredict(key []byte, n ...int) (ids []int)

PrefixPredict eturn the list of words in the dictionary that has `key` as their prefix

func (*Cedar) Update

func (cd *Cedar) Update(key []byte, value int) error

Update the key for the value, it is public interface that works on []byte

func (*Cedar) Value

func (cd *Cedar) Value(path int) (val int, err error)

Value get the path value

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