porcupine

Documentation

Index

• type AVLTree
  • func (a *AVLTree) Del(key string)
  • func (*AVLTree) Get(key string) int
  • func (a *AVLTree) In(key string) bool
  • func (a *AVLTree) Put(key string, value int) int
• 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 (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 HAMT
• type LockingMap
  • 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 RBNode
• type RedBlackTree
• type Store
• type StoreCluster
• type Table

Types

type AVLTree

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

func (*AVLTree) Del

func (a *AVLTree) Del(key string)

func (*AVLTree) Get

func (*AVLTree) Get(key string) int

func (*AVLTree) In

func (a *AVLTree) In(key string) bool

func (*AVLTree) Put

func (a *AVLTree) Put(key string, value int) int

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 (*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 HAMT

type HAMT struct {
}

type LockingMap

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

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
}

OrderTable is an interface for an unordered key-value data structure

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 RBNode

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

type RedBlackTree

type RedBlackTree 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
}

Table is an interface for an unordered key-value data structure