filetrie

Documentation

Overview

Package ctrie provides an implementation of the Ctrie data structure, which is a concurrent, lock-free hash trie. This data structure was originally presented in the paper Concurrent Tries with Efficient Non-Blocking Snapshots:

https://axel22.github.io/resources/docs/ctries-snapshot.pdf

Copyright 2015 Workiva, LLC Modified by stephane martin

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License

Index

• Variables
• type Ctrie
  • func New(hashFactory HashFactory) *Ctrie
  • func (c *Ctrie) Clear()
  • func (c *Ctrie) Filter(f func(Entry) bool, ch chan Entry)
  • func (c *Ctrie) ForEach(f func(Entry))
  • func (c *Ctrie) Insert(key string, value *utils.OFile) (inserted bool)
  • func (c *Ctrie) Iterate(ch chan Entry)
  • func (c *Ctrie) Lookup(key string) (*utils.OFile, bool)
  • func (c *Ctrie) ReadOnlySnapshot() *Ctrie
  • func (c *Ctrie) Remove(key string) (*utils.OFile, bool)
  • func (c *Ctrie) Set(key string, value *utils.OFile) (replaced bool)
  • func (c *Ctrie) Size() int
  • func (c *Ctrie) Snapshot() *Ctrie
• type Entry
• type HashFactory

Variables

var ErrEmptyList = errors.New("Empty list")

ErrEmptyList is returned when an invalid operation is performed on an empty list.

Types

type Ctrie

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

Ctrie is a concurrent, lock-free hash trie. By default, keys are hashed using FNV-1a unless a HashFactory is provided to New.

func New

func New(hashFactory HashFactory) *Ctrie

New creates an empty Ctrie which uses the provided HashFactory for key hashing. If nil is passed in, it will default to FNV-1a hashing.

func (*Ctrie) Clear

func (c *Ctrie) Clear()

Clear removes all keys from the Ctrie.

func (*Ctrie) Filter

func (c *Ctrie) Filter(f func(Entry) bool, ch chan Entry)

func (*Ctrie) ForEach

func (c *Ctrie) ForEach(f func(Entry))

func (*Ctrie) Insert

func (c *Ctrie) Insert(key string, value *utils.OFile) (inserted bool)

Insert adds the key-value pair to the Ctrie

func (*Ctrie) Iterate

func (c *Ctrie) Iterate(ch chan Entry)

Iterator returns a channel which yields the Entries of the Ctrie.

func (*Ctrie) Lookup

func (c *Ctrie) Lookup(key string) (*utils.OFile, bool)

Lookup returns the value for the associated key or returns false if the key doesn't exist.

func (*Ctrie) ReadOnlySnapshot

func (c *Ctrie) ReadOnlySnapshot() *Ctrie

ReadOnlySnapshot returns a stable, point-in-time snapshot of the Ctrie which is read-only. Write operations on a read-only snapshot will panic.

func (*Ctrie) Remove

func (c *Ctrie) Remove(key string) (*utils.OFile, bool)

Remove deletes the value for the associated key, returning true if it was removed or false if the entry doesn't exist.

func (*Ctrie) Set

func (c *Ctrie) Set(key string, value *utils.OFile) (replaced bool)

func (*Ctrie) Size

func (c *Ctrie) Size() int

Size returns the number of keys in the Ctrie.

func (*Ctrie) Snapshot

func (c *Ctrie) Snapshot() *Ctrie

Snapshot returns a stable, point-in-time snapshot of the Ctrie. If the Ctrie is read-only, the returned Ctrie will also be read-only.

type Entry

type Entry struct {
	Key   string
	Value *utils.OFile
}

Entry contains a Ctrie key-value pair.

type HashFactory

type HashFactory func() hash.Hash32

HashFactory returns a new Hash32 used to hash keys.