porcupine

Documentation

Index

• type AVL
  • func NewAVL() *AVL[int, int]
  • func (t *AVL[K, V]) Get(key K) (V, error)
  • func (t *AVL[K, V]) Put(key K, value V) error
• type AVLNode
• type BST
  • func NewBSTree() BST[int, int]
  • func (t *BST[K, V]) Get(key K) (V, error)
  • func (t *BST[K, V]) Put(key K, value V) error
• type BSTNode
• type BTree
  • func NewBTree(degree int) *BTree
  • func (t *BTree) Delete(key int) error
  • func (t *BTree) Search(key int) ([]int, int, error)
  • func (t *BTree) Upsert(key int) error
• type ClusterConfig
• type ConcurrentAppendMap
  • func NewConcurrentAppendMap() *ConcurrentAppendMap
  • func (c *ConcurrentAppendMap) Del(key string) bool
  • func (c *ConcurrentAppendMap) Get(key string) int
  • func (c *ConcurrentAppendMap) In(key string) bool
  • func (c *ConcurrentAppendMap) Put(key string, value int) int
• type ConcurrentMap
  • func NewMap(numLocks int) *ConcurrentMap
  • func (m *ConcurrentMap) GetValue(key int) int
  • func (m *ConcurrentMap) Increment(key int)
• type LockingMap
  • func NewLockingMap() *LockingMap[string, int]
  • func (l *LockingMap[string, any]) Del(key string)
  • func (l *LockingMap[string, any]) Get(key string) (any, error)
  • func (l *LockingMap[string, any]) In(key string) bool
  • func (l *LockingMap[string, any]) Put(key string, value any)
• type MapSingleMutex
  • func NewMapSingleMutex() *MapSingleMutex
  • func (m *MapSingleMutex) GetValue(key int) int
  • func (m *MapSingleMutex) Increment(key int)
• type Node
  • func (n *Node) Search(key int) (*Node, int, error)
  • func (n *Node) SearchToDelete(key int) (*Node, int, error)
• type NodeType
• type OrderTable
• type Porcupine
  • func NewPorcupine(storeConfig string) Porcupine
  • func SpawnPorcupines(storeConfig string, clusterConfig string) []Porcupine
• type RadixNode
• type RadixTree
  • func NewRadixTree() *RadixTree
  • func (t *RadixTree) Insert(word string)
  • func (t *RadixTree) Search(word string) bool
  • func (t *RadixTree) StartsWith(prefix string) bool
• type RedBlack
  • func NewRedBlack() *RedBlack[int, int]
  • func (t *RedBlack[K, V]) Get(key K) (V, error)
  • func (t *RedBlack[K, V]) Put(key K, value V) error
• type RedBlackNode
• type Store
• type StoreCluster
• type Table
• type Trie
  • func NewTrie() *Trie
  • func (t *Trie) Insert(word string)
  • func (t *Trie) Search(word string) bool
  • func (t *Trie) StartsWith(prefix string) bool
• type TrieNode

Types

type AVL

type AVL[key constraints.Ordered, value any] struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

func NewAVL

func NewAVL() *AVL[int, int]

func (*AVL[K, V]) Get

func (t *AVL[K, V]) Get(key K) (V, error)

func (*AVL[K, V]) Put

func (t *AVL[K, V]) Put(key K, value V) error

type AVLNode

type AVLNode[key constraints.Ordered, value any] struct {
	// contains filtered or unexported fields
}

type BST

type BST[Key constraints.Ordered, Value any] struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

func NewBSTree

func NewBSTree() BST[int, int]

BST Property: all nodes left have key < x and right x > key.

func (*BST[K, V]) Get

func (t *BST[K, V]) Get(key K) (V, error)

take the pointer to the root node

func (*BST[K, V]) Put

func (t *BST[K, V]) Put(key K, value V) error

devolves into a linkedlist

type BSTNode

type BSTNode[Key constraints.Ordered, Value any] struct {
	// contains filtered or unexported fields
}

type BTree

type BTree struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

func NewBTree

func NewBTree(degree int) *BTree

func (*BTree) Delete

func (t *BTree) Delete(key int) error

func (*BTree) Search

func (t *BTree) Search(key int) ([]int, int, error)

func (*BTree) Upsert

func (t *BTree) Upsert(key int) error

type ClusterConfig

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

type ConcurrentAppendMap

type ConcurrentAppendMap struct {
	Fields *sync.Map
}

see: https://github.com/golang/go/issues/21035 see: https://github.com/golang/go/issues/28938 see: https://github.com/golang/go/issues/47643

func NewConcurrentAppendMap

func NewConcurrentAppendMap() *ConcurrentAppendMap

func (*ConcurrentAppendMap) Del

func (c *ConcurrentAppendMap) Del(key string) bool

func (*ConcurrentAppendMap) Get

func (c *ConcurrentAppendMap) Get(key string) int

func (*ConcurrentAppendMap) In

func (c *ConcurrentAppendMap) In(key string) bool

func (*ConcurrentAppendMap) Put

func (c *ConcurrentAppendMap) Put(key string, value int) int

type ConcurrentMap

type ConcurrentMap struct {
	Data map[int]int
	// contains filtered or unexported fields
}

ConcurrentMap uses multiple local mutexes partitioned by the hash of the key to allow concurrent writes.

func NewMap

func NewMap(numLocks int) *ConcurrentMap

the relationship between the number of locks and the size of the underlying `bucket index modulo lock array size`

func (*ConcurrentMap) GetValue

func (m *ConcurrentMap) GetValue(key int) int

This seems to make reads slightly more expensive as you're acquiring/releasing multiple locks one for the global RWMutex and a second access to the partioned lock

func (*ConcurrentMap) Increment

func (m *ConcurrentMap) Increment(key int)

Writes are much quicker as they can be parallelised as long as the hashing function behaves properly and segments the keys

type LockingMap

type LockingMap[K string, V any] struct {
	sync.RWMutex
	Fields map[K]V
}

func NewLockingMap

func NewLockingMap() *LockingMap[string, int]

func (*LockingMap[string, any]) Del

func (l *LockingMap[string, any]) Del(key string)

func (*LockingMap[string, any]) Get

func (l *LockingMap[string, any]) Get(key string) (any, error)

func (*LockingMap[string, any]) In

func (l *LockingMap[string, any]) In(key string) bool

func (*LockingMap[string, any]) Put

func (l *LockingMap[string, any]) Put(key string, value any)

type MapSingleMutex

type MapSingleMutex struct {
	Data map[int]int
	sync.RWMutex
}

MapSingleMutex uses a single global mutex to protect all operations on the map.

func NewMapSingleMutex

func NewMapSingleMutex() *MapSingleMutex

func (*MapSingleMutex) GetValue

func (m *MapSingleMutex) GetValue(key int) int

func (*MapSingleMutex) Increment

func (m *MapSingleMutex) Increment(key int)

type Node

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

func (*Node) Search

func (n *Node) Search(key int) (*Node, int, error)

func (*Node) SearchToDelete

func (n *Node) SearchToDelete(key int) (*Node, int, error)

TODO(refactor): collapse this function into one

type NodeType

type NodeType int

const (
	ROOT_NODE NodeType = iota + 1
	INTERNAL_NODE
	LEAF_NODE
)

type OrderTable

type OrderTable[Key constraints.Ordered, Value any] interface {
	Get(Key) (Value, error)
	Range(Key, Key) ([]Value, error)
	Put(Key, Value) error
	Del(Key) error
	In(Key) bool
}

type Porcupine

type Porcupine struct {
	Store Store[string, any]
	Name  string
	// contains filtered or unexported fields
}

Porcupine is a global in-memory read/write store.

func NewPorcupine

func NewPorcupine(storeConfig string) Porcupine

New `Porcupine` instance. This should not be copied after instantiation. todo: hold a *Porcupine on init

func SpawnPorcupines

func SpawnPorcupines(storeConfig string, clusterConfig string) []Porcupine

type RadixNode

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

type RadixTree

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

func NewRadixTree

func NewRadixTree() *RadixTree

func (*RadixTree) Insert

func (t *RadixTree) Insert(word string)

func (*RadixTree) Search

func (t *RadixTree) Search(word string) bool

func (*RadixTree) StartsWith

func (t *RadixTree) StartsWith(prefix string) bool

type RedBlack

type RedBlack[key constraints.Ordered, value any] struct {
	sync.RWMutex
	// contains filtered or unexported fields
}

func NewRedBlack

func NewRedBlack() *RedBlack[int, int]

func (*RedBlack[K, V]) Get

func (t *RedBlack[K, V]) Get(key K) (V, error)

func (*RedBlack[K, V]) Put

func (t *RedBlack[K, V]) Put(key K, value V) error

type RedBlackNode

type RedBlackNode[key constraints.Ordered, value any] struct {
	// contains filtered or unexported fields
}

type Store

type Store[Key any, Value any] interface {
	Get(Key) (Value, error)
	Put(Key, Value) error
	Del(Key) error
	In(Key) bool
}

Store is an interface for a key-value store.

type StoreCluster

type StoreCluster[Key comparable, Value any] interface {
	Store[Key, Value]
	Strategy() string
	Mode() string
}

mode: 1. available 2. consistent

type Table

type Table[Key comparable, Value any] interface {
	Get(Key) (Value, error)
	Put(Key, Value) error
	Del(Key) error
	In(Key) bool
}

type Trie

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

func NewTrie

func NewTrie() *Trie

func (*Trie) Insert

func (t *Trie) Insert(word string)

insert into the tree

func (*Trie) Search

func (t *Trie) Search(word string) bool

exact substring match

func (*Trie) StartsWith

func (t *Trie) StartsWith(prefix string) bool

This is the prefix search

type TrieNode

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