omaps

package module
v0.4.173 Latest Latest
Warning

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

 Go to latest Published: May 14, 2024 License: ISC Imports: 11 Imported by: 0

Documentation

Overview

Package omaps provides ordered Go hash-maps with order provided by B-Tree m-ary self-balancing ordered trees

Index

Constants

View Source 
const (
	BtreeDegree = 6 // each level has 2^6 children: 64
)

Variables

This section is empty.

Functions

func LessOrdered added in v0.4.142 

func LessOrdered[V constraints.Ordered](a, b V) (aBeforeB bool)

LessOrdered is btree.LessFunc for ordered values

Types

type BTreeMap 

type BTreeMap[K comparable, V any] struct {
	// contains filtered or unexported fields
}

BTreeMap is a reusable, promotable custom value-ordered mapping

  • 4/5 native Go map functions: Get Delete Length Range
  • — Put is implemented by consumers that can compare V values
  • convenience functions:
  • — Clear using fast, scavenging re-create
  • — Clone using range, optionally appending to provided instance
  • order functions:
  • — List
  • —
  • ordering structure is B-tree
  • B-tree offers:
  • — avoiding vector-copy of large sorted slices which is slow and
  • — avoiding linear traversal of linked-lists which is slow and
  • — is a more efficient structure than binary tree
  • non-thread-safe maps
  • mapping implementation is Go map

func NewBTreeMap 

func NewBTreeMap[K comparable, V btree.Ordered]() (orderedMap *BTreeMap[K, V])

NewBTreeMap returns a mapping whose values are provided in custom order

  • btree.Ordered does not include ~uintptr. For other ordered V, use NewBTreeMapAny

func NewBTreeMapAny 

func NewBTreeMapAny[K comparable, V any](less btree.LessFunc[V]) (orderedMap *BTreeMap[K, V])

NewBTreeMapAny returns a mapping whose values are provided in custom order

  • supports uintptr. If the ordered V is not uintptr, use NewBTreeMap

func (*BTreeMap[K, V]) Clear 

func (m *BTreeMap[K, V]) Clear()

Clear empties the map

  • clears by re-initializing the map
  • when instead ranging and deleting all keys, the unused size of the map is retained

func (*BTreeMap[K, V]) Clone 

func (m *BTreeMap[K, V]) Clone() (clone *BTreeMap[K, V])

Clone returns a shallow clone of the map

  • clone is done by ranging all keys

func (*BTreeMap[K, V]) Delete 

func (m *BTreeMap[K, V]) Delete(key K)

Delete removes mapping using key K.

  • if key K is not mapped, the map is unchanged.
  • O(log n)

func (*BTreeMap) Get 

func (m *BTreeMap) Get(key K) (value V, ok bool)

Get returns the value mapped by key or the V zero-value otherwise

  • ok: true if a mapping was found
  • O(1)

func (*BTreeMap) Length 

func (m *BTreeMap) Length() (length int)

Length returns the number of mappings

func (*BTreeMap[K, V]) List 

func (m *BTreeMap[K, V]) List(n ...int) (list []V)

List provides mapped values in order

  • n zero or missing means all items
  • n non-zero means this many items capped by length

func (*BTreeMap) Range 

func (m *BTreeMap) Range(rangeFunc func(key K, value V) (keepGoing bool)) (rangedAll bool)

Range traverses map bindings

  • iterates over map until rangeFunc returns false
  • order is undefined
  • similar to sync.Map.Range func (*sync.Map).Range(f func(key any, value any) bool)

type BtreeIterator 

type BtreeIterator[V any, T any] struct {
	// contains filtered or unexported fields
}

BtreeIterator retrieves B-tree values in order

  • V the type of values tree holds
  • T the type of values in the returned list

func NewBtreeIterator 

func NewBtreeIterator[V any, T any](
	tree *btree.BTreeG[V],
	converter ...BtreeIteratorFunc[V, T],
) (iterator *BtreeIterator[V, T])

NewBtreeIterator returns an object that can retrieve elements in order

  • V the type of values tree holds
  • T the type of values in the returned list

func (*BtreeIterator[V, T]) Iterate 

func (i *BtreeIterator[V, T]) Iterate(n int, list ...[]T) (results []T, err error)

Iterate returns a sorted list of the first n elements

  • n is how many items will be returned
  • list is an optional list where to store results
  • results is populated list

type BtreeIteratorFunc 

type BtreeIteratorFunc[V any, T any] func(value V) (valueToStore T, err error)

BtreeIteratorFunc is a function that converts B-tree V-values to slice storage T values

  • valueToStore nil: ignore the value

type BtreeOrdered 

type BtreeOrdered interface {
	// ~int | ~int8 | ~int16 | ~int32 | ~int64 |
	// ~uint | ~uint8 | ~uint16 | ~uint32 | ~uint64 |
	// ~float32 | ~float64 | ~string
	btree.Ordered
}

btree.Ordered does not include ~uintptr

type InsOrderedMap 

type InsOrderedMap[K comparable, V any] struct {
	// contains filtered or unexported fields
}

InsOrderedMap is a mapping whose values are provided in insertion order

  • updating mapped value for existing key does not update insertion order
  • native Go Map functions: Get Put Delete Length Range
  • convenience functions: Clear Clone
  • order function: List
  • debug function: Dump
  • —
  • ability to return values in insertion order
  • — can be achieved by retaining keys or values
  • ability to remove elements from the order by key
  • B-tree is not optimal because it cannot both maintain order and delete by key
  • a slice is not optimal because delete leads to large memory copy
  • therefore:
  • — as map value, have data value and insertion-order index
  • — B-tree provides insertion order for those combined values
  • — delete by key is fast in map and B-tree

func NewInsOrderedMap 

func NewInsOrderedMap[K comparable, V any]() (orderedMap *InsOrderedMap[K, V])

NewInsOrderedMap is a mapping whose keys are provided in insertion order.

func (*InsOrderedMap[K, V]) Clear 

func (m *InsOrderedMap[K, V]) Clear()

Clear empties the map

  • clears by re-initializing the map
  • when instead ranging and deleting all keys, the unused size of the map is retained

func (*InsOrderedMap[K, V]) Clone 

func (m *InsOrderedMap[K, V]) Clone() (clone *InsOrderedMap[K, V])

Clone returns a shallow clone of the map

func (*InsOrderedMap[K, V]) Delete 

func (m *InsOrderedMap[K, V]) Delete(key K)

Delete removes mapping using key K.

  • if key K is not mapped, the map is unchanged.

func (*InsOrderedMap[K, V]) Dump 

func (m *InsOrderedMap[K, V]) Dump() (s string)

Dump returns a debug string of ordered values

func (*InsOrderedMap[K, V]) Get 

func (m *InsOrderedMap[K, V]) Get(key K) (value V, ok bool)

Get returns the value mapped by key or the V zero-value otherwise

  • ok: true if a mapping was found
  • O(1)

func (*InsOrderedMap[K, V]) Length 

func (m *InsOrderedMap[K, V]) Length() (length int)

Length returns the number of mappings

func (*InsOrderedMap[K, V]) List 

func (m *InsOrderedMap[K, V]) List(n ...int) (list []V)

List provides the mapped values in order

  • if n is missing or zero, the entire map
  • otherwise, the first n elements capped by length

func (*InsOrderedMap[K, V]) Put 

func (m *InsOrderedMap[K, V]) Put(key K, value V)

Put saves or replaces a mapping

func (*InsOrderedMap[K, V]) Range 

func (m *InsOrderedMap[K, V]) Range(rangeFunc func(key K, value V) (keepGoing bool))

Range traverses map bindings

  • iterates over map until rangeFunc returns false
  • order is undefined
  • similar to: func (*sync.Map).Range(f func(key any, value any) bool)

type KeyOrderedMap 

type KeyOrderedMap[K constraints.Ordered, V any] struct {
	// contains filtered or unexported fields
}

KeyOrderedMap is a mapping whose keys are provided in order

  • native Go Map functions: Get Put Delete Length Range
  • convenience methods: Clear Clone
  • order method: List
  • — those methods are implemented because they require access to the underlying Go map
  • mapping implementation is Go Map
  • ordering structure is B-tree
  • B-tree offers:
  • — avoiding vector-copy of large sorted slices which is slow and
  • — avoiding linear traversal of linked-lists which is slow and
  • — is a more efficient structure than binary tree

func NewKeyOrderedMap 

func NewKeyOrderedMap[K btree.Ordered, V any]() (orderedMap *KeyOrderedMap[K, V])

NewKeyOrderedMap returns a mapping whose keys are provided in order.

func NewKeyOrderedMapOrdered 

func NewKeyOrderedMapOrdered[K constraints.Ordered, V any]() (orderedMap *KeyOrderedMap[K, V])

NewKeyOrderedMap returns a mapping whose keys are provided in order

func (*KeyOrderedMap[K, V]) Clear 

func (m *KeyOrderedMap[K, V]) Clear()

func (*KeyOrderedMap[K, V]) Clone 

func (m *KeyOrderedMap[K, V]) Clone() (clone *KeyOrderedMap[K, V])

Clone returns a shallow clone of the map

func (*KeyOrderedMap[K, V]) Delete 

func (m *KeyOrderedMap[K, V]) Delete(key K)

func (*KeyOrderedMap) Get 

func (m *KeyOrderedMap) Get(key K) (value V, ok bool)

Get returns the value mapped by key or the V zero-value otherwise

  • ok: true if a mapping was found
  • O(1)

func (*KeyOrderedMap) Length 

func (m *KeyOrderedMap) Length() (length int)

Length returns the number of mappings

func (*KeyOrderedMap[K, V]) List 

func (m *KeyOrderedMap[K, V]) List(n ...int) (list []K)

List provides mapped values in order

  • n zero or missing means all items
  • n non-zero means this many items capped by length

func (*KeyOrderedMap[K, V]) Put 

func (m *KeyOrderedMap[K, V]) Put(key K, value V)

func (*KeyOrderedMap) Range 

func (m *KeyOrderedMap) Range(rangeFunc func(key K, value V) (keepGoing bool)) (rangedAll bool)

Range traverses map bindings

  • iterates over map until rangeFunc returns false
  • order is undefined
  • similar to sync.Map.Range func (*sync.Map).Range(f func(key any, value any) bool)

type OrderedMap 

type OrderedMap[K comparable, V constraints.Ordered] struct {
	// contains filtered or unexported fields
}

OrderedMap is a mapping whose values are provided in order

  • mapping implementation is Go Map
  • ordering structure is B-tree
  • constraints.Ordered: integer float string
  • B-tree offers:
  • — avoiding vector-copy of large sorted slices which is slow and
  • — avoiding linear traversal of linked-lists which is slow and
  • — is a more efficient structure than binary tree

func NewOrderedMap 

func NewOrderedMap[K comparable, V btree.Ordered]() (orderedMap *OrderedMap[K, V])

NewOrderedMap returns a map for btree.Ordered, ie. not ~uintptr

func NewOrderedMapUintptr 

func NewOrderedMapUintptr[K comparable, V ~uintptr]() (orderedMap *OrderedMap[K, V])

NewOrderedMapUintptr returns a map for ~uintptr

func (*OrderedMap[K, V]) Put 

func (m *OrderedMap[K, V]) Put(key K, value V)

Put creates or replaces a mapping

type OrderedMapFunc 

type OrderedMapFunc[K comparable, V any] struct {
	// contains filtered or unexported fields
}

OrderedMapFunc is a mapping whose values are provided in custom order

  • mapping implementation is Go map
  • ordering structure is B-tree
  • B-tree offers:
  • — avoiding vector-copy of large sorted slices which is slow and
  • — avoiding linear traversal of linked-lists which is slow and
  • — is a more efficient structure than binary tree

func NewOrderedMapFunc 

func NewOrderedMapFunc[K comparable, V any](
	less func(a, b V) (aBeforeB bool),
) (orderedMap *OrderedMapFunc[K, V])

NewOrderedMapFunc returns a mapping whose values are provided in custom order.

  • less(a, b) implements sort order and returns:
  • — true if a sorts before b
  • — false if a is of equal rank to b, or a is after b
  • — a equals b must not return true
  • btree.Ordered does not include ~uintptr

func (*OrderedMapFunc[K, V]) Clone 

func (m *OrderedMapFunc[K, V]) Clone() (clone *OrderedMapFunc[K, V])

Clone returns a shallow clone of the map

  • clone is done by ranging all keys

func (*OrderedMapFunc[K, V]) Put 

func (m *OrderedMapFunc[K, V]) Put(key K, value V)

Put creates or replaces a mapping

type ThreadSafeInsOrderedMap 

type ThreadSafeInsOrderedMap[K comparable, V any] struct {
	InsOrderedMap[K, V]
	// contains filtered or unexported fields
}

ThreadSafeInsOrderedMap is a mapping whose values are provided in insertion order. Thread-safe.

  • implemented with RWMutex controlling InsOrderMap

func NewThreadSafeInsOrderedMap 

func NewThreadSafeInsOrderedMap[K comparable, V any]() (orderedMap *ThreadSafeInsOrderedMap[K, V])

func (*ThreadSafeInsOrderedMap[K, V]) Clear 

func (m *ThreadSafeInsOrderedMap[K, V]) Clear()

Clear empties the map

func (*ThreadSafeInsOrderedMap[K, V]) Clone 

func (m *ThreadSafeInsOrderedMap[K, V]) Clone() (clone *ThreadSafeInsOrderedMap[K, V])

Clone returns a shallow clone of the map

func (*ThreadSafeInsOrderedMap[K, V]) Delete 

func (m *ThreadSafeInsOrderedMap[K, V]) Delete(key K)

Delete removes mapping using key K.

  • if key K is not mapped, the map is unchanged.

func (*ThreadSafeInsOrderedMap[K, V]) Get 

func (m *ThreadSafeInsOrderedMap[K, V]) Get(key K) (value V, ok bool)

func (*ThreadSafeInsOrderedMap[K, V]) Length 

func (m *ThreadSafeInsOrderedMap[K, V]) Length() (length int)

func (*ThreadSafeInsOrderedMap[K, V]) List 

func (m *ThreadSafeInsOrderedMap[K, V]) List(n ...int) (list []V)

List provides the mapped values in order

func (*ThreadSafeInsOrderedMap[K, V]) Put 

func (m *ThreadSafeInsOrderedMap[K, V]) Put(key K, value V)

Put saves or replaces a mapping

func (*ThreadSafeInsOrderedMap[K, V]) PutIf 

func (m *ThreadSafeInsOrderedMap[K, V]) PutIf(key K, value V, putIf func(value V) (doPut bool)) (wasNewKey bool)

Put saves or replaces a mapping

type ThreadSafeOrderedMapFunc 

type ThreadSafeOrderedMapFunc[K comparable, V any] struct {
	// contains filtered or unexported fields
}

ThreadSafeOrderedMapFunc is a mapping whose values are provided in custom order. Thread-safe.

  • mapping implementation is Go Map
  • native Go map functions: Get Put Delete Length Range
  • convenience methods: Clone Clear
  • order methods: List
  • ordering structure is B-tree
  • B-tree offers:
  • — avoiding vector-copy of large sorted slices which is slow and
  • — avoiding linear traversal of linked-lists which is slow and
  • — is a more efficient structure than binary tree

func NewThreadSafeOrderedMapFunc 

func NewThreadSafeOrderedMapFunc[K comparable, V any](
	less func(a, b V) (aBeforeB bool),
) (orderedMap *ThreadSafeOrderedMapFunc[K, V])

NewThreadSafeOrderedMapFunc returns a mapping whose values are provided in custom order. Thread-safe.

func (*ThreadSafeOrderedMapFunc[K, V]) Clear 

func (m *ThreadSafeOrderedMapFunc[K, V]) Clear(useRange ...bool)

func (*ThreadSafeOrderedMapFunc[K, V]) Clone 

func (m *ThreadSafeOrderedMapFunc[K, V]) Clone() (clone *ThreadSafeOrderedMapFunc[K, V])

func (*ThreadSafeOrderedMapFunc[K, V]) Delete 

func (m *ThreadSafeOrderedMapFunc[K, V]) Delete(key K, useZeroValue ...bool)

func (*ThreadSafeOrderedMapFunc) Get 

func (m *ThreadSafeOrderedMapFunc) Get(key K) (value V, ok bool)

func (*ThreadSafeOrderedMapFunc[K, V]) GetOrCreate 

func (m *ThreadSafeOrderedMapFunc[K, V]) GetOrCreate(
	key K,
	newV func() (value *V),
	makeV func() (value V),
) (value V, hasValue bool)

GetOrCreate returns an item from the map if it exists otherwise creates it.

  • newV or makeV are invoked in the critical section, ie. these functions may not access the map or deadlock
  • if a key is mapped, its value is returned
  • otherwise, if newV and makeV are both nil, nil is returned.
  • otherwise, if newV is present, it is invoked to return a pointer ot a value. A nil return value from newV causes panic. A new mapping is created using the value pointed to by the newV return value.
  • otherwise, a mapping is created using whatever makeV returns
  • newV and makeV may not access the map. The map’s write lock is held during their execution
  • GetOrCreate is an atomic, thread-safe operation
  • value insert is O(log n)

func (*ThreadSafeOrderedMapFunc) Length 

func (m *ThreadSafeOrderedMapFunc) Length() (length int)

func (*ThreadSafeOrderedMapFunc[K, V]) List 

func (m *ThreadSafeOrderedMapFunc[K, V]) List(n ...int) (list []V)

List provides mapped values in order

  • n zero or missing means all items
  • n non-zero means this many items capped by length

func (*ThreadSafeOrderedMapFunc[K, V]) Put 

func (m *ThreadSafeOrderedMapFunc[K, V]) Put(key K, value V)

func (*ThreadSafeOrderedMapFunc) Range 

func (m *ThreadSafeOrderedMapFunc) Range(rangeFunc func(key K, value V) (keepGoing bool))

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.