imap

package
v0.1.3 Latest Latest
Warning

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

 Go to latest Published: Jun 4, 2023 License: AGPL-3.0 Imports: 8 Imported by: 0

Documentation

Index

Examples

Constants

View Source 
const IDLen = len(ID{})

IDLen is the length of the ID type

Variables

This section is empty.

Functions

func EncodeIDs 

func EncodeIDs(ids ...ID) []byte

EncodeIDs encodes IDs into a new slice of bytes. Each id is encoded sequentially using [Encode].

func MarshalID 

func MarshalID(value ID) ([]byte, error)

MarshalID is like MarshalIDs, but takes takes only a single value

func MarshalIDPair 

func MarshalIDPair(values [2]ID) ([]byte, error)

MarshalIDPair is like MarshalID but takes two ids

func MarshalIDs 

func MarshalIDs(dst []byte, ids ...ID) error

MarshalIDs is like EncodeIDs, but also takes a []byte to write to

func UnmarshalID 

func UnmarshalID(dest *ID, src []byte) error

UnmarshalID behaves like [dest.Decode], but produces an error when there are insufficient number of bytes in src.

func UnmarshalIDPair 

func UnmarshalIDPair(dest *[2]ID, src []byte) error

UnmarshalIDPair is like UnmarshalID but takes two ids.

func UnmarshalIDs 

func UnmarshalIDs(src []byte, dests ...*ID) error

UnmarshalIDs is like UnmarshalID but decodes into every destination passed.

Types

type DiskEngine 

type DiskEngine[Label comparable] struct {
	Path string

	MarshalLabel   func(label Label) ([]byte, error)
	UnmarshalLabel func(dest *Label, src []byte) error
}

DiskEngine represents an engine that persistently stores data on disk.

func (DiskEngine[Label]) Forward 

func (de DiskEngine[Label]) Forward() (KeyValueStore[Label, [2]ID], error)

func (DiskEngine[Label]) Reverse 

func (de DiskEngine[Label]) Reverse() (KeyValueStore[ID, Label], error)

type DiskStorage 

type DiskStorage[Key comparable, Value any] struct {
	DB *leveldb.DB

	MarshalKey     func(key Key) ([]byte, error)
	UnmarshalKey   func(dest *Key, src []byte) error
	MarshalValue   func(value Value) ([]byte, error)
	UnmarshalValue func(dest *Value, src []byte) error
}

DiskStorage implements Storage as an in-memory storage

func NewDiskStorage 

func NewDiskStorage[Key comparable, Value any](path string) (*DiskStorage[Key, Value], error)

NewDiskStorage creates a new disk-based storage with the given options. If the filepath already exists, it is deleted.

func (*DiskStorage[Key, Value]) Close 

func (ds *DiskStorage[Key, Value]) Close() error

func (*DiskStorage[Key, Value]) Count 

func (ds *DiskStorage[Key, Value]) Count() (count uint64, err error)

Count returns the number of objects in this DiskStorage.

func (*DiskStorage[Key, Value]) Delete 

func (ds *DiskStorage[Key, Value]) Delete(key Key) error

Delete deletes the given key from this storage

func (*DiskStorage[Key, Value]) Get 

func (ds *DiskStorage[Key, Value]) Get(key Key) (v Value, b bool, err error)

Get returns the given value if it exists

func (*DiskStorage[Key, Value]) GetZero 

func (ds *DiskStorage[Key, Value]) GetZero(key Key) (Value, error)

GetZero returns the value associated with Key, or the zero value otherwise.

func (*DiskStorage[Key, Value]) Has 

func (ds *DiskStorage[Key, Value]) Has(key Key) (bool, error)

func (*DiskStorage[Key, Value]) Iterate 

func (ds *DiskStorage[Key, Value]) Iterate(f func(Key, Value) error) error

Iterate calls f for all entries in Storage. there is no guarantee on order.

func (*DiskStorage[Key, Value]) Set 

func (ds *DiskStorage[Key, Value]) Set(key Key, value Value) error

type Engine 

type Engine[Label comparable] interface {
	Forward() (KeyValueStore[Label, [2]ID], error)
	Reverse() (KeyValueStore[ID, Label], error)
}

Engine creates Storages for an IMap

type ID 

type ID [4]byte

ID represents an ID of a specific element. Not all IDs are valid, see [Valid].

Users should not rely on the exact size of this data type. Instead they should use appropriate methods to compare values.

Internally, an ID is represented in big endian array of bytes. It effectively corresponds to a uint32.

Example 
// create a new id -- which isn't valid
var id ID
fmt.Println(id)
fmt.Println(id.Valid())

// increment the id -- it is now valid
fmt.Println(id.Inc())
fmt.Println(id.Valid())

// create the value 10
var ten ID
for i := 0; i < 10; i++ {
	ten.Inc()
}

// compare it to some other id -- it is no longer valid
fmt.Println(id.Less(ten))

Output:

ID(0)
false
ID(1)
true
true

func DecodeID 

func DecodeID(src []byte, index int) (id ID)

DecodeID works like DecodeIDs, but only decodes the id with index i

func DecodeIDs 

func DecodeIDs(src []byte) []ID

DecodeIDs decodes a set of ids encoded with EncodeIDs. The behaviour of slices that do not evenly divide into IDs is not defined.

func (*ID) Decode 

func (id *ID) Decode(src []byte)

Decode sets this id to be the values that has been decoded from src. src must be of at least size IDLen, or a runtime panic occurs.

func (ID) Encode 

func (id ID) Encode(dest []byte)

Encode encodes id using a big endian encoding into dest. dest must be of at least size IDLen.

Comparing two distinct slices using bytes.Compare produces the same result as using appropriate calls [Less].

func (*ID) Inc 

func (id *ID) Inc() ID

Inc increments this ID, returning a copy of the new value. It is the equivalent of the "++" operator.

When Inc() exceeds the maximum possible value for an ID, panics.

func (ID) Int 

func (id ID) Int(value *big.Int) *big.Int

Int writes the numerical value of this id into the given big int. The big.Int is returned for convenience.

func (ID) Less 

func (id ID) Less(other ID) bool

Less compares this ID to another id. An id is less than another id iff Inc() has been called fewer times.

func (*ID) LoadInt 

func (id *ID) LoadInt(value *big.Int) *ID

LoadInt sets the value of this id as an integer and returns it. Trying to load an integer bigger than the maximal id results in a panic.

The ID is returned for convenience.

func (*ID) Reset 

func (id *ID) Reset()

Reset resets this id to an invalid value

func (ID) String 

func (id ID) String() string

String formats this id as a string. It is only intended for debugging, and should not be used for production code.

func (ID) Valid 

func (id ID) Valid() bool

Valid checks if this ID is valid

type IMap 

type IMap[Label comparable] struct {
	// contains filtered or unexported fields
}

IMap holds forward and reverse mapping from Labels to IDs. An IMap may be read concurrently; however any operations which change internal state are not safe to access concurrently.

The zero map is not ready for use; it should be initialized using a call to [Reset].

Example 
package main

import (
	"fmt"
	"math/big"
	"strconv"
	"testing"
)

func main() {

	var mp IMap[string]
	mp.Reset(&MemoryEngine[string]{})

	lid := func(prefix string) func(id ID, err error) {
		return func(id ID, err error) {
			fmt.Println(prefix, id, err)
		}
	}

	lid2 := func(prefix string) func(id [2]ID, err error) {
		return func(id [2]ID, err error) {
			fmt.Println(prefix, id[0], err)
		}
	}

	lstr := func(prefix string) func(value string, err error) {
		return func(value string, err error) {
			fmt.Println(prefix, value, err)
		}
	}

	lid2("add")(mp.Add("hello"))
	lid2("add")(mp.Add("world"))
	lid2("add")(mp.Add("earth"))

	lid2("add<again>")(mp.Add("hello"))
	lid2("add<again>")(mp.Add("world"))
	lid2("add<again>")(mp.Add("earth"))

	lid("get")(mp.Forward("hello"))
	lid("get")(mp.Forward("world"))
	lid("get")(mp.Forward("earth"))

	lstr("reverse")(mp.Reverse(*new(ID).LoadInt(big.NewInt(1))))
	lstr("reverse")(mp.Reverse(*new(ID).LoadInt(big.NewInt(2))))
	lstr("reverse")(mp.Reverse(*new(ID).LoadInt(big.NewInt(3))))

	mp.MarkIdentical("earth", "world")

	lstr("reverse<again>")(mp.Reverse(*new(ID).LoadInt(big.NewInt(1))))
	lstr("reverse<again>")(mp.Reverse(*new(ID).LoadInt(big.NewInt(3))))

	lid2("add<again>")(mp.Add("hello"))
	lid2("add<again>")(mp.Add("world"))
	lid2("add<again>")(mp.Add("earth"))

}

// engineTest performs a test for a given engine
func engineTest(t *testing.T, engine Engine[string], N int) {
	var mp IMap[string]
	mp.Reset(engine)
	defer mp.Close()

	// make i == i + 1
	for i := 0; i < N; i += 2 {
		canon, err := mp.MarkIdentical(strconv.Itoa(i), strconv.Itoa(i+1))
		if err != nil {
			t.Fatalf("MarkIdentical returned error %s", err)
		}
		got := canon.Int(big.NewInt(0)).Int64()
		want := int64(i + 1)
		if got != want {
			t.Errorf("MarkIdentical() got id = %s, want = %d", canon, want)
		}
	}

	// check that forward mappings work
	for i := 0; i < N; i++ {
		id, err := mp.Forward(strconv.Itoa(i))
		if err != nil {
			t.Errorf("Forward() returned error %s", err)
		}
		got := int(id.Int(big.NewInt(0)).Int64())
		want := i - (i % 2) + 1
		if got != want {
			t.Errorf("Forward() got = %d, want = %d", got, want)
		}
	}

	// check that reverse mappings work
	var id ID
	var big big.Int
	for i := 1; i < N; i++ {
		big.SetInt64(int64(i))

		got, err := mp.Reverse(*id.LoadInt(&big))
		if err != nil {
			t.Errorf("Reverse() returned error %s", err)
		}
		want := strconv.Itoa(i - 1)

		if got != want {
			t.Errorf("Reverse(%s) got = %q, want = %q", &big, got, want)
		}
	}
}

Output:

add ID(1) <nil>
add ID(2) <nil>
add ID(3) <nil>
add<again> ID(1) <nil>
add<again> ID(2) <nil>
add<again> ID(3) <nil>
get ID(1) <nil>
get ID(2) <nil>
get ID(3) <nil>
reverse hello <nil>
reverse world <nil>
reverse earth <nil>
reverse<again> hello <nil>
reverse<again> earth <nil>
add<again> ID(1) <nil>
add<again> ID(3) <nil>
add<again> ID(3) <nil>

func (*IMap[Label]) Add 

func (mp *IMap[Label]) Add(label Label) (ids [2]ID, err error)

Add inserts label into this IMap and returns a pair of corresponding ids. The first is the canonical id (for use in lookups) whereas the second is the original id.

When label (or any object marked identical to ID) already exists in this IMap, returns the corresponding ID.

func (*IMap[Label]) AddNew 

func (mp *IMap[Label]) AddNew(label Label) (ids [2]ID, old bool, err error)

AddNew behaves like Add, except additionally returns a boolean indiciating if the returned id existed previously.

func (*IMap[Label]) Close 

func (mp *IMap[Label]) Close() error

Close closes any storages related to this IMap.

Calling close multiple times results in err = nil.

func (*IMap[Label]) Forward 

func (mp *IMap[Label]) Forward(label Label) (ID, error)

Forward returns the id corresponding to the given label.

If the label is not contained in this map, the zero ID is returned. The zero ID is never returned for a valid id.

func (*IMap[Label]) IdentityMap 

func (mp *IMap[Label]) IdentityMap(storage KeyValueStore[Label, Label]) error

IdentityMap writes canonical label mappings to the given storage.

Concretely a pair (L1, L2) is written to storage iff 

mp.Reverse(mp.Forward(L1)) == L2 && L1 != L2

func (*IMap[Label]) MarkIdentical 

func (mp *IMap[Label]) MarkIdentical(new, old Label) (canonical ID, err error)

MarkIdentical marks the two labels as being identical. It returns the ID corresponding to the label new.

Once applied, all future calls to [Forward] or [Add] with old will act as if being called by new. A previous ID corresponding to old (if any) is no longer valid.

NOTE(twiesing): Each call to MarkIdentical potentially requires iterating over all calls that were previously added to this map. This is a potentially slow operation and should be avoided.

func (*IMap[Label]) Next 

func (mp *IMap[Label]) Next() ID

Next returns a new unused id within this map It is always valid.

func (*IMap[Label]) Reset 

func (mp *IMap[Label]) Reset(engine Engine[Label]) error

Reset resets this IMap to be empty, finishing any previ

func (*IMap[Label]) Reverse 

func (mp *IMap[Label]) Reverse(id ID) (Label, error)

Reverse returns the label corresponding to the given id. When id is not contained in this map, the zero value of the label type is contained.

type KeyValueStore 

type KeyValueStore[Key comparable, Value any] interface {
	// Close closes this key
	Close() error

	// Set sets the given key to the given value
	Set(key Key, value Value) error

	// Get retrieves the value for Key from the given storage.
	// The second value indiciates if the value was found.
	Get(key Key) (Value, bool, error)

	// GetZero is like Get, but when the value does not exist returns the zero value
	GetZero(key Key) (Value, error)

	// Has is like Get, but returns only the second value.
	Has(key Key) (bool, error)

	// Delete deletes the given key from this storage
	Delete(key Key) error

	// Iterate calls f for all entries in Storage.
	//
	// When any f returns a non-nil error, that error is returned immediatly to the caller
	// and iteration stops.
	//
	// There is no guarantee on order.
	Iterate(f func(Key, Value) error) error

	// Count counts the number of elements in this store
	Count() (uint64, error)
}

KeyValueStore is something that holds a set of key-value pairs.

Key-Value stores support various read and write operations

type MemoryEngine 

type MemoryEngine[Label comparable] struct {
	FStorage MemoryStorage[Label, [2]ID]
	RStorage MemoryStorage[ID, Label]
}

MemoryEngine represents an engine that stores storages in memory

func (*MemoryEngine[Label]) Forward 

func (me *MemoryEngine[Label]) Forward() (KeyValueStore[Label, [2]ID], error)

func (*MemoryEngine[Label]) Reverse 

func (me *MemoryEngine[Label]) Reverse() (KeyValueStore[ID, Label], error)

type MemoryStorage 

type MemoryStorage[Key comparable, Value any] map[Key]Value

MemoryStorage implements Storage as an in-memory map

func (*MemoryStorage[Key, Value]) Close 

func (ims *MemoryStorage[Key, Value]) Close() error

Close closes this MapStorage, deleting all values

func (*MemoryStorage[Key, Value]) Count 

func (ims *MemoryStorage[Key, Value]) Count() (uint64, error)

func (MemoryStorage[Key, Value]) Delete 

func (ims MemoryStorage[Key, Value]) Delete(key Key) error

Delete deletes the given key from this storage

func (MemoryStorage[Key, Value]) Get 

func (ims MemoryStorage[Key, Value]) Get(key Key) (Value, bool, error)

Get returns the given value if it exists

func (MemoryStorage[Key, Value]) GetZero 

func (ims MemoryStorage[Key, Value]) GetZero(key Key) (Value, error)

GetZero returns the value associated with Key, or the zero value otherwise.

func (MemoryStorage[Key, Value]) Has 

func (ims MemoryStorage[Key, Value]) Has(key Key) (bool, error)

func (MemoryStorage[Key, Value]) Iterate 

func (ims MemoryStorage[Key, Value]) Iterate(f func(Key, Value) error) error

Iterate calls f for all entries in Storage. there is no guarantee on order.

func (MemoryStorage[Key, Value]) Set 

func (ims MemoryStorage[Key, Value]) Set(key Key, value Value) error

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.