diff options
Diffstat (limited to 'src/pds.go')
| -rw-r--r-- | src/pds.go | 364 |
1 files changed, 193 insertions, 171 deletions
@@ -3,41 +3,41 @@ /// == Introduction /// /// Immutable collections provide an efficient, safe way to share collections -/// of data while minimizing locks. The collections in this package provide -/// Vector, Map, and SortedMap implementations. These act similarly to slices +/// of data while minimizing locks. The collections in this package provide +/// Vector, Map, and SortedMap implementations. These act similarly to slices /// and maps, respectively, except that altering a collection returns a new /// copy of the collection with that change. /// /// Because collections are unable to change, they are safe for multiple -/// goroutines to read from at the same time without a mutex. However, these +/// goroutines to read from at the same time without a mutex. However, these /// types of collections come with increased CPU & memory usage as compared /// with Go's built-in collection types so please evaluate for your specific /// use. /// /// == Collection Types /// -/// The Vector type provides an API similar to Go slices. They allow appending, -/// prepending, and updating of elements. Elements can also be fetched by index +/// The Vector type provides an API similar to Go slices. They allow appending, +/// prepending, and updating of elements. Elements can also be fetched by index /// or iterated over using a VectorIterator. /// -/// The Map & SortedMap types provide an API similar to Go maps. They allow +/// The Map & SortedMap types provide an API similar to Go maps. They allow /// values to be assigned to unique keys and allow for the deletion of keys. /// Values can be fetched by key and key/value pairs can be iterated over using -/// the appropriate iterator type. Both map types provide the same API. The +/// the appropriate iterator type. Both map types provide the same API. The /// SortedMap, however, provides iteration over sorted keys while the Map -/// provides iteration over unsorted keys. Maps improved performance and memory +/// provides iteration over unsorted keys. Maps improved performance and memory /// usage as compared to SortedMaps. /// /// == Hashing and Sorting /// /// Map types require the use of a Hasher implementation to calculate hashes for -/// their keys and check for key equality. SortedMaps require the use of a +/// their keys and check for key equality. SortedMaps require the use of a /// Comparer implementation to sort keys in the map. /// /// These collection types automatically provide built-in hasher and comparers -/// for int, string, and byte slice keys. If you are using one of these key types -/// then simply pass a nil into the constructor. Otherwise you will need to -/// implement a custom Hasher or Comparer type. Please see the provided +/// for int, string, and byte slice keys. If you are using one of these key +/// types then simply pass a nil into the constructor. Otherwise you will need +/// to implement a custom Hasher or Comparer type. Please see the provided /// implementations for reference. package pds @@ -54,262 +54,284 @@ import ( - - -// vectorNode represents either a branch or leaf node in a Vector. -type vectorNode[T any] interface { +/// vectorNode represents either a branch or leaf node in a Vector. +type vectorNode[T any] interface{ depth() uint - get(index int) T - set(index int, v T, mutable bool) vectorNode[T] - + get( index int) T + set( index int, v T, mutable bool) vectorNode[T] containsBefore(index int) bool - containsAfter(index int) bool + containsAfter( index int) bool + deleteBefore( index int, mutable bool) vectorNode[T] + deleteAfter( index int, mutable bool) vectorNode[T] +} + +/// mapNode represents any node in the map tree. +type mapNode[K, V any] interface{ + get( + key K, shift uint, keyHash uint32, h Hasher[K], + ) (value V, ok bool) + set( + key K, value V, shift uint, keyHash uint32, h Hasher[K], + mutable bool, resized *bool, + ) mapNode[K, V] + delete( + key K, shift uint, keyHash uint32, h Hasher[K], + mutable bool, resized *bool, + ) mapNode[K, V] +} + +/// sortedMapNode represents a branch or leaf node in the sorted map. +type sortedMapNode[K, V any] interface{ + minKey() K + indexOf( + key K, c Comparer[K], + ) int + get( + key K, c Comparer[K], + ) (value V, ok bool) + set( + key K, value V, c Comparer[K], mutable bool, resized *bool, + ) (sortedMapNode[K, V], sortedMapNode[K, V]) + delete( + key K, c Comparer[K], mutable bool, resized *bool, + ) sortedMapNode[K, V] +} + +/// mapLeafNode represents a node that stores a single key hash at the leaf of +/// the map tree. +type mapLeafNode[K, V any] interface{ + mapNode[K, V] + keyHashValue() uint32 +} + +/// Hasher hashes keys and checks them for equality. +type Hasher[K any] interface{ + /// Computes a hash for key. + Hash(key K) uint32 + /// Returns true if a and b are equal. + Equal(a, b K) bool +} - deleteBefore(index int, mutable bool) vectorNode[T] - deleteAfter(index int, mutable bool) vectorNode[T] +/// Comparer allows the comparison of two keys for the purpose of sorting. +type Comparer[K any] interface{ + /// Returns -1 if a is less than b, returns 1 if a is greater than b, + /// and returns 0 if a is equal to b. + Compare(a, b K) int } -/// Vector is a dense, ordered, indexed collections. They are analogous to slices -/// in Go. They can be updated by appending to the end of the vector, prepending -/// values to the beginning of the vector, or updating existing indexes in the -/// vector. -type Vector[T any] struct { - root vectorNode[T] // root node - origin int // offset to zero index element - size int // total number of elements in use + +/// Vector is a dense, ordered, indexed collections. They are analogous to +/// slices in Go. They can be updated by appending to the end of the vector, +/// prepending values to the beginning of the vector, or updating existing +/// indexes in the vector. +type Vector[T any] struct{ + root vectorNode[T] /// root node + origin int /// offset to zero index element + size int /// total number of elements in use } -// VectorBuilder represents an efficient builder for creating new Vectors. -type VectorBuilder[T any] struct { - vector *Vector[T] // current state +/// VectorBuilder represents an efficient builder for creating new Vectors. +type VectorBuilder[T any] struct{ + vector *Vector[T] /// current state } -// vectorBranchNode represents a branch of a Vector tree at a given depth. -type vectorBranchNode[T any] struct { - d uint // depth +/// vectorBranchNode represents a branch of a Vector tree at a given depth. +type vectorBranchNode[T any] struct{ + d uint /// depth children [vectorNodeSize]vectorNode[T] } -// vectorLeafNode represents a leaf node in a Vector. -type vectorLeafNode[T any] struct { +/// vectorLeafNode represents a leaf node in a Vector. +type vectorLeafNode[T any] struct{ children [vectorNodeSize]T - // bitset with ones at occupied positions, position 0 is the LSB + /// bitset with ones at occupied positions, position 0 is the LSB occupied uint32 } -// VectorIterator represents an ordered iterator over a vector. -type VectorIterator[T any] struct { - vector *Vector[T] // source vector - index int // current index position - - stack [32]vectorIteratorElem[T] // search stack - depth int // stack depth +/// VectorIterator represents an ordered iterator over a vector. +type VectorIterator[T any] struct{ + vector *Vector[T] /// source vector + index int /// current index position + stack [32]vectorIteratorElem[T] /// search stack + depth int /// stack depth } -// vectorIteratorElem represents the node and it's child index within the stack. -type vectorIteratorElem[T any] struct { +/// vectorIteratorElem represents the node and it's child index within the +/// stack. +type vectorIteratorElem[T any] struct{ node vectorNode[T] index int } -// Map represents an immutable hash map implementation. The map uses a Hasher -// to generate hashes and check for equality of key values. -// -// It is implemented as an Hash Array Mapped Trie. -type Map[K, V any] struct { - size int // total number of key/value pairs - root mapNode[K, V] // root node of trie - hasher Hasher[K] // hasher implementation -} - -// MapBuilder represents an efficient builder for creating Maps. -type MapBuilder[K, V any] struct { - m *Map[K, V] // current state +/// Map represents an immutable hash map implementation. The map uses a Hasher +/// to generate hashes and check for equality of key values. +/// +/// It is implemented as an Hash Array Mapped Trie. +type Map[K, V any] struct{ + size int /// total number of key/value pairs + root mapNode[K, V] /// root node of trie + hasher Hasher[K] /// hasher implementation } -// mapNode represents any node in the map tree. -type mapNode[K, V any] interface { - get(key K, shift uint, keyHash uint32, h Hasher[K]) (value V, ok bool) - set(key K, value V, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] - delete(key K, shift uint, keyHash uint32, h Hasher[K], mutable bool, resized *bool) mapNode[K, V] +/// MapBuilder represents an efficient builder for creating Maps. +type MapBuilder[K, V any] struct{ + m *Map[K, V] /// current state } -// mapLeafNode represents a node that stores a single key hash at the leaf of the map tree. -type mapLeafNode[K, V any] interface { - mapNode[K, V] - keyHashValue() uint32 -} - -// mapArrayNode is a map node that stores key/value pairs in a slice. -// Entries are stored in insertion order. An array node expands into a bitmap -// indexed node once a given threshold size is crossed. -type mapArrayNode[K, V any] struct { +/// mapArrayNode is a map node that stores key/value pairs in a slice. +/// Entries are stored in insertion order. An array node expands into a bitmap +/// indexed node once a given threshold size is crossed. +type mapArrayNode[K, V any] struct{ entries []mapEntry[K, V] } -// mapBitmapIndexedNode represents a map branch node with a variable number of -// node slots and indexed using a bitmap. Indexes for the node slots are -// calculated by counting the number of set bits before the target bit using popcount. -type mapBitmapIndexedNode[K, V any] struct { +/// mapBitmapIndexedNode represents a map branch node with a variable number of +/// node slots and indexed using a bitmap. Indexes for the node slots are +/// calculated by counting the number of set bits before the target bit using +/// popcount. +type mapBitmapIndexedNode[K, V any] struct{ bitmap uint32 nodes []mapNode[K, V] } -// mapHashArrayNode is a map branch node that stores nodes in a fixed length -// array. Child nodes are indexed by their index bit segment for the current depth. -type mapHashArrayNode[K, V any] struct { - count uint // number of set nodes - nodes [mapNodeSize]mapNode[K, V] // child node slots, may contain empties +/// mapHashArrayNode is a map branch node that stores nodes in a fixed length +/// array. Child nodes are indexed by their index bit segment for the current +/// depth. +type mapHashArrayNode[K, V any] struct{ + /// number of set nodes + count uint + /// child node slots, may contain empties + nodes [mapNodeSize]mapNode[K, V] } -// mapValueNode represents a leaf node with a single key/value pair. -// A value node can be converted to a hash collision leaf node if a different -// key with the same keyHash is inserted. -type mapValueNode[K, V any] struct { +/// mapValueNode represents a leaf node with a single key/value pair. +/// A value node can be converted to a hash collision leaf node if a different +/// key with the same keyHash is inserted. +type mapValueNode[K, V any] struct{ keyHash uint32 key K value V } -// mapHashCollisionNode represents a leaf node that contains two or more key/value -// pairs with the same key hash. Single pairs for a hash are stored as value nodes. -type mapHashCollisionNode[K, V any] struct { - keyHash uint32 // key hash for all entries +/// mapHashCollisionNode represents a leaf node that contains two or more +/// key/value pairs with the same key hash. Single pairs for a hash are stored +/// as value nodes. +type mapHashCollisionNode[K, V any] struct{ + keyHash uint32 /// key hash for all entries entries []mapEntry[K, V] } -// mapEntry represents a single key/value pair. -type mapEntry[K, V any] struct { +/// mapEntry represents a single key/value pair. +type mapEntry[K, V any] struct{ key K value V } -// MapIterator represents an iterator over a map's key/value pairs. Although -// map keys are not sorted, the iterator's order is deterministic. -type MapIterator[K, V any] struct { - m *Map[K, V] // source map - - stack [32]mapIteratorElem[K, V] // search stack - depth int // stack depth +/// MapIterator represents an iterator over a map's key/value pairs. Although +/// map keys are not sorted, the iterator's order is deterministic. +type MapIterator[K, V any] struct{ + m *Map[K, V] /// source map + stack [32]mapIteratorElem[K, V] /// search stack + depth int /// stack depth } -// mapIteratorElem represents a node/index pair in the MapIterator stack. -type mapIteratorElem[K, V any] struct { +/// mapIteratorElem represents a node/index pair in the MapIterator stack. +type mapIteratorElem[K, V any] struct{ node mapNode[K, V] index int } -// SortedMap represents a map of key/value pairs sorted by key. The sort order -// is determined by the Comparer used by the map. -// -// This map is implemented as a B+tree. -type SortedMap[K, V any] struct { - size int // total number of key/value pairs - root sortedMapNode[K, V] // root of b+tree +/// SortedMap represents a map of key/value pairs sorted by key. The sort order +/// is determined by the Comparer used by the map. +/// +/// This map is implemented as a B+tree. +type SortedMap[K, V any] struct{ + size int /// total number of key/value pairs + root sortedMapNode[K, V] /// root of b+tree comparer Comparer[K] } -// SortedMapBuilder represents an efficient builder for creating sorted maps. -type SortedMapBuilder[K, V any] struct { - m *SortedMap[K, V] // current state +/// SortedMapBuilder represents an efficient builder for creating sorted maps. +type SortedMapBuilder[K, V any] struct{ + m *SortedMap[K, V] /// current state } -// sortedMapNode represents a branch or leaf node in the sorted map. -type sortedMapNode[K, V any] interface { - minKey() K - indexOf(key K, c Comparer[K]) int - get(key K, c Comparer[K]) (value V, ok bool) - set(key K, value V, c Comparer[K], mutable bool, resized *bool) (sortedMapNode[K, V], sortedMapNode[K, V]) - delete(key K, c Comparer[K], mutable bool, resized *bool) sortedMapNode[K, V] -} - -// sortedMapBranchNode represents a branch in the sorted map. -type sortedMapBranchNode[K, V any] struct { +/// sortedMapBranchNode represents a branch in the sorted map. +type sortedMapBranchNode[K, V any] struct{ elems []sortedMapBranchElem[K, V] } -type sortedMapBranchElem[K, V any] struct { +type sortedMapBranchElem[K, V any] struct{ key K node sortedMapNode[K, V] } -// sortedMapLeafNode represents a leaf node in the sorted map. -type sortedMapLeafNode[K, V any] struct { +/// sortedMapLeafNode represents a leaf node in the sorted map. +type sortedMapLeafNode[K, V any] struct{ entries []mapEntry[K, V] } -// SortedMapIterator represents an iterator over a sorted map. -// Iteration can occur in natural or reverse order based on use of Next() or Prev(). -type SortedMapIterator[K, V any] struct { - m *SortedMap[K, V] // source map - - stack [32]sortedMapIteratorElem[K, V] // search stack - depth int // stack depth +/// SortedMapIterator represents an iterator over a sorted map. +/// Iteration can occur in natural or reverse order based on use of Next() or +/// Prev(). +type SortedMapIterator[K, V any] struct{ + m *SortedMap[K, V] /// source map + stack [32]sortedMapIteratorElem[K, V] /// search stack + depth int /// stack depth } -// sortedMapIteratorElem represents node/index pair in the SortedMapIterator stack. -type sortedMapIteratorElem[K, V any] struct { +/// sortedMapIteratorElem represents node/index pair in the SortedMapIterator +/// stack. +type sortedMapIteratorElem[K, V any] struct{ node sortedMapNode[K, V] index int } -// Hasher hashes keys and checks them for equality. -type Hasher[K any] interface { - // Computes a hash for key. - Hash(key K) uint32 - - // Returns true if a and b are equal. - Equal(a, b K) bool -} - -// reflectIntHasher implements a reflection-based Hasher for keys. +/// reflectIntHasher implements a reflection-based Hasher for keys. type reflectHasher[K any] struct{} -// defaultHasher implements Hasher. +/// defaultHasher implements Hasher. type defaultHasher[K any] struct{} -// Comparer allows the comparison of two keys for the purpose of sorting. -type Comparer[K any] interface { - // Returns -1 if a is less than b, returns 1 if a is greater than b, - // and returns 0 if a is equal to b. - Compare(a, b K) int -} - -// defaultComparer compares two values (int-ish and string-ish types are supported). Implements Comparer. +/// defaultComparer compares two values (int-ish and string-ish types are +/// supported). Implements Comparer. type defaultComparer[K any] struct{} -// reflectIntComparer compares two values using reflection. Implements Comparer. +/// reflectIntComparer compares two values using reflection. Implements +/// Comparer. type reflectComparer[K any] struct{} -// Set represents a collection of unique values. The set uses a Hasher -// to generate hashes and check for equality of key values. -// -// Internally, the Set stores values as keys of a Map[T,struct{}] -type Set[T any] struct { +/// Set represents a collection of unique values. The set uses a Hasher +/// to generate hashes and check for equality of key values. +/// +/// Internally, the Set stores values as keys of a Map[T,struct{}] +type Set[T any] struct{ m *Map[T, struct{}] } -// SetIterator represents an iterator over a set. -// Iteration can occur in natural or reverse order based on use of Next() or Prev(). -type SetIterator[T any] struct { +/// SetIterator represents an iterator over a set. +/// Iteration can occur in natural or reverse order based on use of Next() or +/// Prev(). +type SetIterator[T any] struct{ mi *MapIterator[T, struct{}] } -type SetBuilder[T any] struct { +type SetBuilder[T any] struct{ s Set[T] } -type SortedSet[T any] struct { +type SortedSet[T any] struct{ m *SortedMap[T, struct{}] } -// SortedSetIterator represents an iterator over a sorted set. -// Iteration can occur in natural or reverse order based on use of Next() or Prev(). -type SortedSetIterator[T any] struct { +/// SortedSetIterator represents an iterator over a sorted set. +/// Iteration can occur in natural or reverse order based on use of Next() or +/// Prev(). +type SortedSetIterator[T any] struct{ mi *SortedMapIterator[T, struct{}] } -type SortedSetBuilder[T any] struct { +type SortedSetBuilder[T any] struct{ s *SortedSet[T] } |