cedar

README

gocedar

a cedar trie implement in go with mmap

Documentation

Index

• Constants
• Variables
• type Block
• type Cedar
  • func New(opt *Options) *Cedar
  • func (c *Cedar) Close()
  • 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 MMap
  • func NewMMap(mmapDir string) *MMap
  • func (m *MMap) AddBlock(c *Cedar, capacity int)
  • func (m *MMap) InitData(c *Cedar)
  • func (m *MMap) OpenFile()
• type MetaInfo
• type NInfo
• type Node
• type Options

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 {
	*MetaInfo
	// contains filtered or unexported fields
}

Cedar holds all of the information about double array trie.

func New

func New(opt *Options) *Cedar

New initialize the Cedar for further use

func (*Cedar) Close

func (c *Cedar) Close()

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 MMap

type MMap struct {
	// contains filtered or unexported fields
}

func NewMMap

func NewMMap(mmapDir string) *MMap

func (*MMap) AddBlock

func (m *MMap) AddBlock(c *Cedar, capacity int)

addBlock in Cedar inplace depends on c.capacity

func (*MMap) InitData

func (m *MMap) InitData(c *Cedar)

initData in Cedar inplace

func (*MMap) OpenFile

func (m *MMap) OpenFile()

type MetaInfo

type MetaInfo struct {
	LoadSize int // key size when mmaped
	Reduced  bool
	// contains filtered or unexported fields
}

nolint

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

type Options

type Options struct {
	Reduced  bool
	UseMMap  bool
	MMapPath string
}