Documentation
¶
Overview ¶
Package genarray implements a generational array data structure.
A generational array is a contiguous block of memory, like a vanilla array, but the array index is extended with an incrementing "generation" that allows elements to be safely invalidated and removed, and their space in the array reused for future insertions.
Each array slot supports a 64-bit generation count. In rare cases this may eventually overflow, raising a panic with ErrRange on insertion.
Security model: note that keys are predictable and keys may be leaked through timing side-channel attacks. Do not treat these keys as secret values.
Index ¶
- Variables
- type Key
- type Store
- func (s *Store[ValueT]) Clear()
- func (s *Store[ValueT]) Contains(key Key) bool
- func (s *Store[ValueT]) Count() int
- func (s *Store[ValueT]) Delete(key Key) error
- func (s *Store[ValueT]) Get(key Key) (ValueT, bool)
- func (s *Store[ValueT]) Grow(n int)
- func (s *Store[ValueT]) Index(key Key) int
- func (s *Store[ValueT]) Insert(value ValueT) Key
- func (s *Store[ValueT]) Keys() func() (Key, bool)
- func (s *Store[ValueT]) Pairs() func() (iter.Pair[Key, ValueT], bool)
- func (s *Store[ValueT]) ReadKeys(r io.Reader, limit int) error
- func (s *Store[ValueT]) Update(key Key, value ValueT) error
- func (s *Store[ValueT]) Values() func() (ValueT, bool)
- func (s *Store[ValueT]) WriteKeys(w io.Writer) error
Examples ¶
Constants ¶
This section is empty.
Variables ¶
var ErrConflict = errors.New("key conflict")
var ErrLimit = errors.New("index exceeds limit")
var ErrNotFound = errors.New("not found")
var ErrRange = errors.New("value out of range")
Functions ¶
This section is empty.
Types ¶
type Key ¶
type Key struct {
// contains filtered or unexported fields
}
A Key uniquely references a value in a Store.
func KeyFromBytes ¶
KeyFromBytes decodes a key from an opaque 16-byte value. Provided a Store uses the same mask each time, this value is stable across different processes.
If src is not at least 16 bytes long, panics with io.ErrShortBuffer.
func ReadKey ¶
ReadKey Read reads and decodes a key from an opaque 16-byte value. Provided a Store uses the same mask each time, this value is stable across different processes.
func (Key) Bytes ¶
Bytes encodes a key as an opaque 16-byte value. Provided a Store uses the same mask each time, this value is stable across different processes.
If dest is not large enough to receive 16 bytes, panics with io.ErrShortBuffer.
type Store ¶
type Store[ValueT any] struct { // contains filtered or unexported fields }
Store is a collection of values, indexed by a unique key. The zero-value for a store is a useful value.
Example ¶
package main
import (
"fmt"
"github.com/tawesoft/golib/v2/ds/genarray"
"github.com/tawesoft/golib/v2/must"
)
func main() {
// declare a generational array Store
var store genarray.Store[string]
// insert "hello" and "world" into the Store and keep a reference
hello := store.Insert("hello")
world := store.Insert("world")
// we can retrieve a value using the returned key as a reference
value, ok := store.Get(hello)
must.Truef(ok, "failed to lookup hello key in store")
must.Equalf(value, "hello", "hello key lookup returned unexpected value %q", value)
// or delete a value...
err := store.Delete(world)
must.Equal(err, nil)
// after being deleted, cannot retrieve again
value, ok = store.Get(world)
must.Not(ok)
// nor delete again
err = store.Delete(world)
must.Equal(err, genarray.ErrNotFound)
// now insert a new element, reusing the space where "world" appeared
// previously in the Store's backing array.
everyone := store.Insert("everyone")
// keys are not equal despite the space being reused
must.Not(world == everyone)
// let's check the contents:
valueIterator := store.Values()
for {
value, ok := valueIterator()
if !ok {
break
}
fmt.Println(value)
}
fmt.Println(store.Count())
}
Output: hello everyone 2
func (*Store[ValueT]) Clear ¶
func (s *Store[ValueT]) Clear()
Clear (re)initialises a Store so that it is empty and any backing storage is released.
func (*Store[ValueT]) Contains ¶
Contains returns true iff the key is a valid reference to a current value.
func (*Store[ValueT]) Delete ¶
Delete removes an entry from the Store, referenced by Key, and overwrites the value in the store with the zero value for its type in order to prevent dangling references. If not found (or already deleted previously), returns ErrNotFound. Once removed, that Key will never again be a valid reference to a value, even if the underlying memory in the Store gets reused for a new value.
func (*Store[ValueT]) Get ¶
Get retrieves a copy of a value from the Store, referenced by Key. The second return value is true iff found.
func (*Store[ValueT]) Grow ¶
Grow increases the store's capacity, if necessary, to guarantee space for another n elements. After Grow(n), at least n elements can be appended to the store without another allocation. This is an optional optimisation.
Panics with ErrLimit if the new capacity would exceed the limit set in [Store.Init].
func (*Store[ValueT]) Index ¶ added in v2.13.0
Index returns an index, between 0 and Store.Count minus one inclusive, indicating, in ascending order, where a key would appear in the iteration generated by [Keys].
Panics with ErrNotFound if the key is no longer valid.
func (*Store[ValueT]) Insert ¶
Insert puts a copy of value in the Store, and returns a Key which uniquely identifies it for lookup later.
In the unlikely event that the 64-bit generation counter for an entry would overflow, or in the case that the limit set in [Store.Init] is exceeded, panics with ErrRange or ErrLimit.
func (*Store[ValueT]) Keys ¶
Keys returns an iterator function that generates each stored key. The order of iteration is not defined, except that Store.Keys, Store.Values and Store.Pairs produce values in the same order. It is not safe to mutate the Store during this iteration.
func (*Store[ValueT]) Pairs ¶
Pairs returns an iterator function that generates each stored (Key, Value) pair. The order of iteration is not defined, except that Store.Keys, Store.Values and Store.Pairs produce values in the same order. It is not safe to mutate the Store during this iteration.
func (*Store[ValueT]) ReadKeys ¶
ReadKeys (re)initialises a store from a binary serialisation, clearing its current contents and repopulating it with keys referencing zero values.
Limit, if greater than zero, sets an upper limit on the size (in number of elements) of the backing array. A small but maliciously crated input could otherwise consume a large amount of memory by encoding sparsely distributed keys.
It is left to the caller to deserialise values and associate them with their matching key using Store.Update.
This function reads until EOF. io.ReadLimiter may be useful.
The return value, if not nil, may be ErrLimit, ErrConflict if there is a duplicate key, or may represent an io read error.
func (*Store[ValueT]) Update ¶
Update modifies an existing value in the Store, referenced by Key. May return ErrNotFound if the key does not reference a valid current entry. Otherwise, returns nil.
func (*Store[ValueT]) Values ¶
Values returns an iterator function that generates each stored value. The order of iteration is not defined, except that Store.Keys, Store.Values and Store.Pairs produce values in the same order. It is not safe to mutate the Store during this iteration.
func (*Store[ValueT]) WriteKeys ¶
WriteKeys writes a binary serialisation of a Store's keys that can later be deserialised and associated with values.
It is left to the caller to serialise the values themselves. Note that because Store.Keys and Store.Values iterate in the same order, it is not strictly necessary to store redundant keys with the serialised values.
The return value, if not nil, may represent an io write error.
Source Files