cedar

README

cedar

Package cedar implements an updatable double-array trie and aho corasick.

It is a Go port of cedar (see the paper).

Install

go get 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, the values are stored as int32
	ValLimit = math.MaxInt32
	// 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.

All fields fit in int32 (block indexes are < 2^24, counters are <= 257, and eHead is a node index which is bounded by ValLimit), which halves the per-block footprint compared to int.

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