rangeindex

Documentation

Overview

Package rangeindex provides a thread-safe, dynamically updatable in-memory index that stores sets of discrete keys, each associated with a value. Internally, adjacent keys with equal values are automatically merged into half-open ranges [Lo, Hi) to minimise memory use.

The public API is point-based: callers set, delete, and query individual keys. The range creation, merging, and splitting happens transparently inside the index.

It is backed by a B-tree (github.com/google/btree) and protected by a sync.RWMutex so that concurrent reads and writes are safe.

K is constrained to integer types so that the index can compute key+1 for half-open interval arithmetic.

Index

• type Index
  • func New[K constraints.Integer, V comparable]() *Index[K, V]
  • func NewWithDegree[K constraints.Integer, V comparable](degree int) *Index[K, V]
  • func (idx *Index[K, V]) Clear()
  • func (idx *Index[K, V]) CollectRanges() []Segment[K, V]
  • func (idx *Index[K, V]) Contains(key K) bool
  • func (idx *Index[K, V]) Delete(key K)
  • func (idx *Index[K, V]) Get(key K) (V, bool)
  • func (idx *Index[K, V]) Len() int
  • func (idx *Index[K, V]) Ranges(fn func(lo, hi K, value V) bool)
  • func (idx *Index[K, V]) Set(key K, value V)
  • func (idx *Index[K, V]) SetIfAbsent(key K, value V) bool
• type Segment

Types

type Index

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

Index is a thread-safe point-to-range index.

Callers operate on individual keys; internally the index stores non-overlapping half-open intervals [Lo, Hi) and automatically merges adjacent entries that carry the same value.

K must be an integer type (int, int64, uint32, …). V must be comparable (required for merge-on-equal-value).

func New

func New[K constraints.Integer, V comparable]() *Index[K, V]

New creates a new empty Index with the default B-tree degree.

func NewWithDegree

func NewWithDegree[K constraints.Integer, V comparable](degree int) *Index[K, V]

NewWithDegree creates a new empty Index with the given B-tree degree. Degree must be ≥ 2.

func (*Index[K, V]) Clear

func (idx *Index[K, V]) Clear()

Clear removes all segments.

func (*Index[K, V]) CollectRanges

func (idx *Index[K, V]) CollectRanges() []Segment[K, V]

CollectRanges returns a snapshot of all stored segments in ascending Lo order.

func (*Index[K, V]) Contains

func (idx *Index[K, V]) Contains(key K) bool

Contains returns true if key is covered by some segment.

func (*Index[K, V]) Delete

func (idx *Index[K, V]) Delete(key K)

Delete removes coverage for the given key. Internal ranges are split or trimmed as needed.

func (*Index[K, V]) Get

func (idx *Index[K, V]) Get(key K) (V, bool)

Get returns the value covering key, or the zero value and false if key is not covered by any segment.

func (*Index[K, V]) Len

func (idx *Index[K, V]) Len() int

Len returns the number of stored internal segments (not the number of covered keys). This is useful for observing how well merging is working.

func (*Index[K, V]) Ranges

func (idx *Index[K, V]) Ranges(fn func(lo, hi K, value V) bool)

Ranges iterates over all stored segments in ascending Lo order. Iteration stops early if fn returns false.

func (*Index[K, V]) Set

func (idx *Index[K, V]) Set(key K, value V)

Set assigns value to the given key. If adjacent keys carry the same value, the entries are merged into a single internal range automatically.

func (*Index[K, V]) SetIfAbsent

func (idx *Index[K, V]) SetIfAbsent(key K, value V) bool

SetIfAbsent assigns value to the given key only if it is not already covered by any segment. Returns true if the key was set, false if it was already present.

The check and insertion are atomic with respect to other Index operations.

type Segment

type Segment[K constraints.Integer, V comparable] struct {
	Lo    K
	Hi    K
	Value V
}

Segment is a read-only view of a stored range returned by iteration methods.