byodb13

package
v0.0.0-...-9315a8a Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 27, 2024 License: MIT Imports: 17 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	BNODE_NODE = 1 // internal nodes without values
	BNODE_LEAF = 2 // leaf nodes with values
)
View Source 
const (
	MODE_UPSERT      = 0 // insert or replace
	MODE_UPDATE_ONLY = 1 // update existing keys
	MODE_INSERT_ONLY = 2 // only add new keys
)

update modes

View Source 
const (
	CMP_GE = +3 // >=
	CMP_GT = +2 // >
	CMP_LT = -2 // <
	CMP_LE = -3 // <=
)
View Source 
const (
	QL_UNINIT = 0
	// scalar
	QL_STR = TYPE_BYTES
	QL_I64 = TYPE_INT64
	// binary ops
	QL_CMP_GE = 10 // >=
	QL_CMP_GT = 11 // >
	QL_CMP_LT = 12 // <
	QL_CMP_LE = 13 // <=
	QL_CMP_EQ = 14 // ==
	QL_CMP_NE = 15 // !=
	QL_ADD    = 20
	QL_SUB    = 21
	QL_MUL    = 22
	QL_DIV    = 23
	QL_MOD    = 24
	QL_AND    = 30
	QL_OR     = 31
	// QL_IN     = 32
	// unary ops
	QL_NOT = 50
	QL_NEG = 51
	// others
	QL_SYM  = 100 // column
	QL_TUP  = 101 // tuple
	QL_STAR = 102 // select *
	QL_ERR  = 200 // error; from parsing or evaluation
)

syntax tree node types

View Source 
const (
	TYPE_ERROR = 0 // uninitialized
	TYPE_BYTES = 1
	TYPE_INT64 = 2
	TYPE_INF   = 0xff // do not use
)
View Source 
const (
	INDEX_ADD = 1
	INDEX_DEL = 2
)
View Source 
const (
	FLAG_DELETED = byte(1)
	FLAG_UPDATED = byte(2)
)

a prefix for values in KVTX.pending

View Source 
const BTREE_MAX_KEY_SIZE = 1000
View Source 
const BTREE_MAX_VAL_SIZE = 3000
View Source 
const BTREE_PAGE_SIZE = 4096
View Source 
const DB_SIG = "BuildYourOwnDB13"
View Source 
const FREE_LIST_CAP = (BTREE_PAGE_SIZE - FREE_LIST_HEADER) / 16
View Source 
const FREE_LIST_HEADER = 8
View Source 
const HEADER = 4
View Source 
const TABLE_PREFIX_MIN = 100

Variables

View Source 
var ErrorConflict = errors.New("cannot commit due to conflict")
View Source 
var INTERNAL_TABLES map[string]*TableDef = map[string]*TableDef{
	"@meta":  TDEF_META,
	"@table": TDEF_TABLE,
}
View Source 
var TDEF_META = &TableDef{
	Name:     "@meta",
	Types:    []uint32{TYPE_BYTES, TYPE_BYTES},
	Cols:     []string{"key", "val"},
	Indexes:  [][]string{{"key"}},
	Prefixes: []uint32{1},
}

internal table: metadata

View Source 
var TDEF_TABLE = &TableDef{
	Name:     "@table",
	Types:    []uint32{TYPE_BYTES, TYPE_BYTES},
	Cols:     []string{"name", "def"},
	Indexes:  [][]string{{"name"}},
	Prefixes: []uint32{2},
}

internal table: table schemas

Functions

This section is empty.

Types

type BIter 

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

B-tree iterator

func (*BIter) Deref 

func (iter *BIter) Deref() ([]byte, []byte)

current KV pair

func (*BIter) Next 

func (iter *BIter) Next()

func (*BIter) Prev 

func (iter *BIter) Prev()

func (*BIter) Valid 

func (iter *BIter) Valid() bool

type BNode 

type BNode []byte // can be dumped to the disk

type BTree 

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

func (*BTree) Delete 

func (tree *BTree) Delete(req *DeleteReq) bool

func (*BTree) Get 

func (tree *BTree) Get(key []byte) ([]byte, bool)

func (*BTree) Seek 

func (tree *BTree) Seek(key []byte, cmp int) *BIter

find the closest position to a key with respect to the `cmp` relation

func (*BTree) SeekLE 

func (tree *BTree) SeekLE(key []byte) *BIter

find the closest position that is less or equal to the input key

func (*BTree) Update 

func (tree *BTree) Update(req *UpdateReq) bool

func (*BTree) Upsert 

func (tree *BTree) Upsert(key []byte, val []byte) bool

the interface

type CombinedIter 

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

an iterator that combines pending updates and the snapshot

func (*CombinedIter) Deref 

func (iter *CombinedIter) Deref() ([]byte, []byte)

func (*CombinedIter) Next 

func (iter *CombinedIter) Next()

func (*CombinedIter) Valid 

func (iter *CombinedIter) Valid() bool

type CommittedTX 

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

type DB 

type DB struct {
	Path string
	// contains filtered or unexported fields
}

func (*DB) Abort 

func (db *DB) Abort(tx *DBTX)

func (*DB) Begin 

func (db *DB) Begin(tx *DBTX)

func (*DB) Close 

func (db *DB) Close()

func (*DB) Commit 

func (db *DB) Commit(tx *DBTX) error

func (*DB) Open 

func (db *DB) Open() error

type DBTX 

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

DB transaction

func (*DBTX) Delete 

func (tx *DBTX) Delete(table string, rec Record) (bool, error)

func (*DBTX) Get 

func (tx *DBTX) Get(table string, rec *Record) (bool, error)

get a single row by the primary key

func (*DBTX) Insert 

func (tx *DBTX) Insert(table string, rec Record) (bool, error)

func (*DBTX) Revert 

func (tx *DBTX) Revert(save *TXSave)

func (*DBTX) Save 

func (tx *DBTX) Save(save *TXSave)

func (*DBTX) Scan 

func (tx *DBTX) Scan(table string, req *Scanner) error

func (*DBTX) Set 

func (tx *DBTX) Set(table string, dbreq *DBUpdateReq) (bool, error)

add a record

func (*DBTX) TableNew 

func (tx *DBTX) TableNew(tdef *TableDef) error

func (*DBTX) Update 

func (tx *DBTX) Update(table string, rec Record) (bool, error)

func (*DBTX) Upsert 

func (tx *DBTX) Upsert(table string, rec Record) (bool, error)

type DBUpdateReq 

type DBUpdateReq struct {
	// in
	Record Record
	Mode   int
	// out
	Updated bool
	Added   bool
}

type DeleteReq 

type DeleteReq struct {

	// in
	Key []byte
	// out
	Old []byte
	// contains filtered or unexported fields
}

type FreeList 

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

func (*FreeList) PopHead 

func (fl *FreeList) PopHead() uint64

get 1 item from the list head. return 0 on failure.

func (*FreeList) PushTail 

func (fl *FreeList) PushTail(ptr uint64)

add 1 item to the tail

func (*FreeList) SetMaxVer 

func (fl *FreeList) SetMaxVer(maxVer uint64)

make the newly added items available for consumption

type KV 

type KV struct {
	Path  string
	Fsync func(int) error // overridable; for testing
	// contains filtered or unexported fields
}

func (*KV) Abort 

func (kv *KV) Abort(tx *KVTX)

end a transaction: rollback

func (*KV) Begin 

func (kv *KV) Begin(tx *KVTX)

begin a transaction

func (*KV) Close 

func (db *KV) Close()

cleanups

func (*KV) Commit 

func (kv *KV) Commit(tx *KVTX) error

end a transaction: commit updates

func (*KV) Open 

func (db *KV) Open() error

open or create a DB file

type KVIter 

type KVIter interface {
	Deref() (key []byte, val []byte)
	Valid() bool
	Next()
}

type KVTX 

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

KV transaction

func (*KVTX) Del 

func (tx *KVTX) Del(req *DeleteReq) bool

func (*KVTX) Get 

func (tx *KVTX) Get(key []byte) ([]byte, bool)

point query. combines captured updates with the snapshot

func (*KVTX) Revert 

func (tx *KVTX) Revert(save *TXSave)

func (*KVTX) Save 

func (tx *KVTX) Save(save *TXSave)

func (*KVTX) Seek 

func (tx *KVTX) Seek(key1 []byte, cmp1 int, key2 []byte, cmp2 int) KVIter

range query. combines captured updates with the snapshot

func (*KVTX) Set 

func (tx *KVTX) Set(key []byte, val []byte) bool

func (*KVTX) Update 

func (tx *KVTX) Update(req *UpdateReq) bool

capture updates

type KeyRange 

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

start <= key <= stop

type LNode 

type LNode []byte

node format: | next | pointer + version | unused | | 8B | n*(8B+8B) | ... |

type Parser 

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

type QLCreateTable 

type QLCreateTable struct {
	Def TableDef
}

stmt: create table

type QLDelete 

type QLDelete struct {
	QLScan
}

stmt: delete

type QLEvalContex 

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

for evaluating expressions

type QLInsert 

type QLInsert struct {
	Table  string
	Mode   int // insert | upsert | replace
	Names  []string
	Values [][]QLNode
}

stmt: insert

type QLNode 

type QLNode struct {
	Value
	Kids []QLNode
}

syntax tree

type QLResult 

type QLResult struct {
	Records RecordIter
	Added   uint64
	Updated uint64
	Deleted uint64
}

func DBTXExecString 

func DBTXExecString(tx *DBTX, input []byte) (QLResult, error)

type QLScan 

type QLScan struct {
	Table  string // table name
	Key1   QLNode // index by
	Key2   QLNode
	Filter QLNode // filter
	Offset int64  // limit
	Limit  int64
}

common structure for queries: `INDEX BY`, `FILTER`, `LIMIT`

type QLSelect 

type QLSelect struct {
	QLScan
	Names  []string // expr AS name
	Output []QLNode
}

stmt: select

type QLUpdate 

type QLUpdate struct {
	QLScan
	Names  []string
	Values []QLNode
}

stmt: update

type Record 

type Record struct {
	Cols []string
	Vals []Value
}

table row

func (*Record) AddInt64 

func (rec *Record) AddInt64(col string, val int64) *Record

func (*Record) AddStr 

func (rec *Record) AddStr(col string, val []byte) *Record

func (*Record) Get 

func (rec *Record) Get(key string) *Value

type RecordIter 

type RecordIter interface {
	Valid() bool
	Next()
	Deref(*Record) error
}

type Scanner 

type Scanner struct {
	// the range, from Key1 to Key2
	Cmp1 int // CMP_??
	Cmp2 int
	Key1 Record
	Key2 Record
	// contains filtered or unexported fields
}

the iterator for range queries

func (*Scanner) Deref 

func (sc *Scanner) Deref(rec *Record)

return the current row

func (*Scanner) Next 

func (sc *Scanner) Next()

move the underlying B-tree iterator

func (*Scanner) Valid 

func (sc *Scanner) Valid() bool

within the range or not?

type StmtSplitter 

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

func (*StmtSplitter) Feed 

func (self *StmtSplitter) Feed(line string)

func (*StmtSplitter) Pop 

func (self *StmtSplitter) Pop() ([]byte, bool)

type TXSave 

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

for reverting updates inside a TX

type TableDef 

type TableDef struct {
	// user defined
	Name    string
	Types   []uint32   // column types
	Cols    []string   // column names
	Indexes [][]string // the first index is the primary key
	// auto-assigned B-tree key prefixes for different tables and indexes
	Prefixes []uint32
}

table schema

type UpdateReq 

type UpdateReq struct {

	// out
	Added   bool   // added a new key
	Updated bool   // added a new key or an old key was changed
	Old     []byte // the value before the update
	// in
	Key  []byte
	Val  []byte
	Mode int
	// contains filtered or unexported fields
}

type Value 

type Value struct {
	Type uint32
	I64  int64
	Str  []byte
}

table cell

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.