flatmap.gno

  1// Package flatmap is a sorted-vector map — the STL flat_map / Abseil
  2// btree_map trade — as a pure, reusable package.
  3//
  4// Keys and values live in two parallel sorted slices instead of a hash table or
  5// a tree of nodes. Lookup is a binary search, O(log n) rather than O(1), but it
  6// touches contiguous memory instead of chasing pointers, iteration is already
  7// in key order with nothing to sort, and there is no per-entry node overhead.
  8// Insertion in the middle is O(n) because it shifts the tail. That is the whole
  9// bargain: cheap reads and cheap ordered iteration, paid for at write time.
 10//
 11// On chain the ordering is the real draw. A built-in gno map iterates in an
 12// unspecified order, so a Render built from one can differ between nodes — a
 13// consensus bug rather than a cosmetic one. A flat map is sorted by
 14// construction, so iteration is deterministic without a sort on every read.
 15//
 16// Appending in ascending key order is the fast path: it hits the end of the
 17// slice and shifts nothing.
 18//
 19// A live demo of this package is at
 20// [r/moul/x/daily/flatmapdemo](/r/moul/x/daily/flatmapdemo/v0).
 21package flatmap
 22
 23import "sort"
 24
 25// MaxEntries bounds the map so gas stays predictable.
 26const MaxEntries = 4096
 27
 28// FlatMap is a string->string map backed by parallel sorted slices.
 29type FlatMap struct {
 30	keys []string
 31	vals []string
 32}
 33
 34// New returns an empty FlatMap.
 35func New() *FlatMap { return &FlatMap{} }
 36
 37// Len returns the number of entries.
 38func (f *FlatMap) Len() int { return len(f.keys) }
 39
 40// IsEmpty reports whether the map holds nothing.
 41func (f *FlatMap) IsEmpty() bool { return len(f.keys) == 0 }
 42
 43// search returns the index where key is, or would be inserted, plus whether it
 44// is actually present.
 45func (f *FlatMap) search(key string) (int, bool) {
 46	i := sort.SearchStrings(f.keys, key)
 47	return i, i < len(f.keys) && f.keys[i] == key
 48}
 49
 50// Get returns the value for key.
 51func (f *FlatMap) Get(key string) (string, bool) {
 52	i, found := f.search(key)
 53	if !found {
 54		return "", false
 55	}
 56	return f.vals[i], true
 57}
 58
 59// Has reports whether key is present.
 60func (f *FlatMap) Has(key string) bool { _, found := f.search(key); return found }
 61
 62// Set inserts or updates key. Returns false only when the map is full and key
 63// is new — updating an existing key always succeeds.
 64func (f *FlatMap) Set(key, value string) bool {
 65	i, found := f.search(key)
 66	if found {
 67		f.vals[i] = value
 68		return true
 69	}
 70	if len(f.keys) >= MaxEntries {
 71		return false
 72	}
 73	// Grow by one, then shift the tail right to open a slot at i.
 74	f.keys = append(f.keys, "")
 75	f.vals = append(f.vals, "")
 76	copy(f.keys[i+1:], f.keys[i:])
 77	copy(f.vals[i+1:], f.vals[i:])
 78	f.keys[i] = key
 79	f.vals[i] = value
 80	return true
 81}
 82
 83// Delete removes key. Returns false when absent.
 84func (f *FlatMap) Delete(key string) bool {
 85	i, found := f.search(key)
 86	if !found {
 87		return false
 88	}
 89	copy(f.keys[i:], f.keys[i+1:])
 90	copy(f.vals[i:], f.vals[i+1:])
 91	f.keys = f.keys[:len(f.keys)-1]
 92	f.vals = f.vals[:len(f.vals)-1]
 93	return true
 94}
 95
 96// Keys returns the keys in sorted order, as a copy.
 97func (f *FlatMap) Keys() []string {
 98	out := make([]string, len(f.keys))
 99	copy(out, f.keys)
100	return out
101}
102
103// Values returns the values ordered by their keys, as a copy.
104func (f *FlatMap) Values() []string {
105	out := make([]string, len(f.vals))
106	copy(out, f.vals)
107	return out
108}
109
110// At returns the i-th entry in key order — the indexed access a hash map cannot
111// offer, and one reason to pay for sorted storage.
112func (f *FlatMap) At(i int) (key, value string, ok bool) {
113	if i < 0 || i >= len(f.keys) {
114		return "", "", false
115	}
116	return f.keys[i], f.vals[i], true
117}
118
119// Iterate calls fn for each entry in key order. Returning true stops.
120func (f *FlatMap) Iterate(fn func(key, value string) bool) {
121	for i := range f.keys {
122		if fn(f.keys[i], f.vals[i]) {
123			return
124		}
125	}
126}
127
128// Range calls fn for entries with lo <= key < hi, in key order. An empty hi
129// means "to the end". This is the other thing sorted storage buys: a range
130// query is two binary searches and a walk.
131func (f *FlatMap) Range(lo, hi string, fn func(key, value string) bool) {
132	start := sort.SearchStrings(f.keys, lo)
133	for i := start; i < len(f.keys); i++ {
134		if hi != "" && f.keys[i] >= hi {
135			return
136		}
137		if fn(f.keys[i], f.vals[i]) {
138			return
139		}
140	}
141}
142
143// Clone returns an independent copy.
144func (f *FlatMap) Clone() *FlatMap {
145	return &FlatMap{keys: f.Keys(), vals: f.Values()}
146}
147
148// Sorted reports whether the backing slice is in strictly ascending order.
149// Always true through the public API; exported so callers can assert it.
150func (f *FlatMap) Sorted() bool {
151	for i := 1; i < len(f.keys); i++ {
152		if f.keys[i-1] >= f.keys[i] {
153			return false
154		}
155	}
156	return len(f.keys) == len(f.vals)
157}