stdlib

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Sep 16, 2026 License: Apache-2.0 Imports: 10 Imported by: 0

Documentation

Overview

LRU provides a fast, production‑grade Least Recently Used cache implementation.

Why this implementation exists

  • Predictable O(1) operations using a hashmap + doubly‑linked list
  • Minimal allocations, generic over key/value (Go 1.18+)
  • Clean separation of concerns: core data structure is intentionally NOT concurrent; a tiny wrapper adds threadsafety when you need it
  • Ergonomic eviction hook for metrics/cleanup

When to use which type

  • LRU[K,V] — Use this inside a larger component that already holds a lock (e.g., a sharded in‑memory store where the shard mutex protects map+LRU+TTL updates atomically). This avoids double‑locking.
  • SafeLRU[K,V] — Use this as a standalone cache when you don’t have an outer lock. It wraps LRU with an RWMutex, providing safe concurrent access.

Usage 

// Non‑concurrent (fastest). Guard with your own locks.
l := stdlib.NewLRU[string, []byte](10_000, nil)
l.Set("k", []byte("v"))
if v, ok := l.Get("k"); ok { _ = v }

// Threadsafe wrapper for standalone use.
sl := stdlib.NewSafeLRU(stdlib.NewLRU[string, []byte](10_000, nil))
sl.Set("k", []byte("v"))

Package stdlib implements reusable, high‑performance primitives.

This file provides a Count‑Min Sketch (CMS) used by TinyLFU admission policies to maintain approximate frequency counts under tight memory bounds.

Design highlights

  • Fixed memory: depth × width counters, independent of key cardinality
  • 64‑bit FNV‑1a base hash + per‑row salts (no heap allocs per op)
  • Saturating uint32 counters with periodic aging (halving)
  • Zero external dependencies

Recommended configuration 

depth = 4 rows, width = power‑of‑two (e.g., 1<<16) is a good default.
agingEvery = N ops between global halving; tune to workload recency.

Concurrency: the sketch is NOT internally synchronized. Callers should coordinate access (e.g., shard‑level locks). This mirrors the LRU core.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func Hash64Bytes 

func Hash64Bytes(b []byte) uint64

Hash64Bytes computes FNV‑1a over a byte slice.

func Hash64String 

func Hash64String(s string) uint64

Hash64String computes a stable 64‑bit hash for strings using FNV‑1a.

func OptimalBloomFilterSize 

func OptimalBloomFilterSize(numKeys int64, falsePositiveRate float64) (uint64, uint8)

Types

type Array 

type Array[T any] struct {
	// contains filtered or unexported fields
}

func NewStack 

func NewStack[T any]() *Array[T]

NewStack creates and returns a new stack.

func (*Array[T]) IsEmpty 

func (s *Array[T]) IsEmpty() bool

IsEmpty returns true if the stack is empty, false otherwise.

func (*Array[T]) Length 

func (s *Array[T]) Length() int

Size returns the number of elements in the stack.

func (*Array[T]) Peek 

func (s *Array[T]) Peek() T

Peek returns the top element of the stack without removing it.

func (*Array[T]) Pop 

func (s *Array[T]) Pop() T

Pop removes and returns the top element from the stack.

func (*Array[T]) Push 

func (s *Array[T]) Push(value T)

Push adds an element to the top of the stack.

type BitSet 

type BitSet struct {
	Bits []uint64
	Size uint64
}

BitSet represents a set of bits, using an underlying slice of uint64.

func NewBitSet 

func NewBitSet(size uint64) *BitSet

NewBitSet creates a new BitSet with the specified number of bits.

func (*BitSet) AllSet 

func (bs *BitSet) AllSet() bool

AllSet checks if all bits in the bitset are set to 1.

func (*BitSet) AnySet 

func (bs *BitSet) AnySet() bool

AnySet checks if any bit in the bitset is set to 1.

func (*BitSet) Clear 

func (bs *BitSet) Clear(pos uint64) error

Clear sets the bit at the given position to 0.

func (*BitSet) ClearAll 

func (b *BitSet) ClearAll()

Efficiently clear all the blocks by resetting the underlying slice.

func (*BitSet) CountSetBits 

func (bs *BitSet) CountSetBits() uint64

CountSetBits counts the number of bits that are set to 1.

func (*BitSet) GetSize 

func (bs *BitSet) GetSize() uint64

GetSize returns the total number of bits in the bitset.

func (*BitSet) IsSet 

func (bs *BitSet) IsSet(pos uint64) (bool, error)

IsSet checks whether the bit at the given position is set (1).

func (*BitSet) NoneSet 

func (bs *BitSet) NoneSet() bool

NoneSet checks if no bits in the bitset are set (i.e., all bits are 0).

func (*BitSet) Set 

func (bs *BitSet) Set(pos uint64) error

Set sets the bit at the given position to 1.

func (*BitSet) String 

func (bs *BitSet) String() string

String representation of the BitSet (for debugging purposes).

func (*BitSet) Toggle 

func (bs *BitSet) Toggle(pos uint64) error

Toggle flips the bit at the given position.

type BloomFilter 

type BloomFilter struct {
	Size      uint64
	HashCount uint8
	Bitset    *BitSet
}

func NewBloomFilter 

func NewBloomFilter(size uint64, hashCount uint8) *BloomFilter

func NewBloomFilterWithPositiveRate 

func NewBloomFilterWithPositiveRate(size uint64, rate float64) *BloomFilter

func (*BloomFilter) Add 

func (bf *BloomFilter) Add(key string)

func (*BloomFilter) ClearAll 

func (bf *BloomFilter) ClearAll()

func (*BloomFilter) Deserialize 

func (bf *BloomFilter) Deserialize(data []byte) error

Deserialize deserializes the Bloom filter from a byte slice.

func (*BloomFilter) Exists 

func (bf *BloomFilter) Exists(key string) bool

func (*BloomFilter) Hash 

func (bf *BloomFilter) Hash(key string, seed uint64) uint64

func (*BloomFilter) MemoryUsage 

func (bf *BloomFilter) MemoryUsage() uint64

func (*BloomFilter) Merge 

func (bf *BloomFilter) Merge(other *BloomFilter) error

func (*BloomFilter) Serialize 

func (bf *BloomFilter) Serialize() ([]byte, error)

type ConcurrentMap 

type ConcurrentMap struct {
	Data map[string]string
	Id   string
	sync.RWMutex
}

Dictionary - the dictionary object with key of type string & vlaue of type string

func (*ConcurrentMap) Add 

func (dict *ConcurrentMap) Add(key string, value string)

Add adds a new item to the dictionary

func (*ConcurrentMap) Clear 

func (dict *ConcurrentMap) Clear()

Clear removes all the Reports from the dictionary

func (*ConcurrentMap) Exist 

func (dict *ConcurrentMap) Exist(key string) bool

Exist returns true if the key exists in the dictionary

func (*ConcurrentMap) Get 

func (dict *ConcurrentMap) Get(key string) string

Get returns the value associated with the key

func (*ConcurrentMap) GetKeys 

func (dict *ConcurrentMap) GetKeys() []string

GetKeys returns a slice of all the keys present

func (*ConcurrentMap) GetValues 

func (dict *ConcurrentMap) GetValues() []string

GetValues returns a slice of all the values present

func (*ConcurrentMap) Remove 

func (dict *ConcurrentMap) Remove(key string) bool

Remove removes a value from the dictionary, given its key

func (*ConcurrentMap) Size 

func (dict *ConcurrentMap) Size() int

Size returns the amount of elements in the dictionary

type CountMinSketch 

type CountMinSketch struct {
	// contains filtered or unexported fields
}

CountMinSketch maintains approximate per‑key frequency counts using a compact 2D array of counters addressed by multiple hash functions. It never underestimates frequency; collisions can overestimate counts.

func NewCountMinSketch 

func NewCountMinSketch(depth int, width uint64, agingEvery uint64) (*CountMinSketch, error)

NewCountMinSketch constructs a sketch with the given depth (rows), width (columns per row), and optional automatic aging interval.

  • depth must be 1..8
  • width must be >= 16; power‑of‑two is recommended for speed

func (*CountMinSketch) Age 

func (c *CountMinSketch) Age()

Age halves all counters, biasing the sketch toward recent history. This is a bulk operation and should be called infrequently (e.g., every 50k–500k ops).

func (*CountMinSketch) Estimate 

func (c *CountMinSketch) Estimate(h uint64) uint32

Estimate returns the approximate frequency for the provided 64‑bit hash. The value is the minimum counter across rows, which guarantees no underestimation.

func (*CountMinSketch) Increment 

func (c *CountMinSketch) Increment(h uint64)

Increment records one observation for the provided 64‑bit key hash. The hash should be well‑distributed; see Hash64* helpers below.

func (*CountMinSketch) Reset 

func (c *CountMinSketch) Reset()

Reset zeroes all counters and the op counter. Useful for tests or hard resets.

type Hasher 

type Hasher[K any] func(K) uint64

Hasher converts a key to a 64‑bit hash suitable for the sketch. Callers can provide Hash64String/Hash64Bytes or their own function.

type LRU 

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

LRU is a minimal, high‑performance Least Recently Used cache.

Concurrency model

  • LRU itself does not synchronize; callers must coordinate concurrency.
  • This design allows callers that already hold an outer lock (e.g., a shard RWMutex) to update map+TTL+LRU atomically with a single critical section.
  • For standalone concurrent use, wrap with SafeLRU.

Invariants

  • c.ll’s front is MRU (most recently used), back is LRU (least recently used).
  • c.items maps keys to their list element for O(1) lookups/moves.

Complexity

  • Get/Peek/Set/Delete: amortized O(1).
  • Keys/Purge iterate over the list (O(n)).

func NewLRU 

func NewLRU[K comparable, V any](capacity int, onEvict OnEvict[K, V]) *LRU[K, V]

New creates an LRU with the given capacity. cap must be >= 0.

func (*LRU[K, V]) Capacity 

func (c *LRU[K, V]) Capacity() int

Capacity returns the maximum number of items the cache can hold.

func (*LRU[K, V]) Delete 

func (c *LRU[K, V]) Delete(key K) bool

Delete removes key if present and returns true on success. The eviction hook is invoked for symmetry with Set‑triggered evictions.

func (*LRU[K, V]) Get 

func (c *LRU[K, V]) Get(key K) (v V, ok bool)

Get retrieves a value and moves it to the front (MRU). ok=false if not found.

func (*LRU[K, V]) Keys 

func (c *LRU[K, V]) Keys() []K

Keys returns a slice of the keys in the cache, from most- to least-recently used.

func (*LRU[K, V]) Len 

func (c *LRU[K, V]) Len() int

Len returns the number of items in the cache.

func (*LRU[K, V]) Peek 

func (c *LRU[K, V]) Peek(key K) (v V, ok bool)

Peek retrieves the value for key WITHOUT updating recency. Useful for inspection when recency‑sensitive behavior must not change. If key is absent, ok is false and v is the zero value of V.

func (*LRU[K, V]) Purge 

func (c *LRU[K, V]) Purge()

Purge removes all entries from the cache. If an eviction callback is set, it is invoked for each removed entry (from LRU toward MRU). The cache remains usable after Purge.

func (*LRU[K, V]) Set 

func (c *LRU[K, V]) Set(key K, value V) (evicted bool)

Set inserts a new key or updates an existing one. The entry becomes the most‑recently used. If the insertion pushes the cache beyond capacity, the least‑recently used item is evicted and the eviction hook (if present) is called. The return value reports whether an eviction occurred.

func (*LRU[K, V]) TailKey 

func (c *LRU[K, V]) TailKey() (K, bool)

TailKey returns the least-recently used key. If the cache is empty, ok=false and the zero value of K is returned.

type LinkedList 

type LinkedList[T any] struct {

	// Note that Node here holds both Next and Prev Node
	// however only the Next node is used in LinkedList methods.
	Head *Node[T]
	// contains filtered or unexported fields
}

LinkedList structure with length of the list and its head

func NewLinkedList 

func NewLinkedList[T any]() *LinkedList[T]

NewLinkedList returns a new instance of a linked list

func (*LinkedList[T]) AddAtBeg 

func (ll *LinkedList[T]) AddAtBeg(val T)

AddAtBeg adds a new snode with given value at the beginning of the list.

func (*LinkedList[T]) AddAtEnd 

func (ll *LinkedList[T]) AddAtEnd(val T)

AddAtEnd adds a new snode with given value at the end of the list.

func (*LinkedList[T]) CheckRangeFromIndex 

func (ll *LinkedList[T]) CheckRangeFromIndex(left, right int) error

func (*LinkedList[T]) Count 

func (ll *LinkedList[T]) Count() int

Count returns the current size of the list.

func (*LinkedList[T]) DelAtBeg 

func (ll *LinkedList[T]) DelAtBeg() (T, bool)

DelAtBeg deletes the snode at the head(beginning) of the list and returns its value. Returns false if the list is empty.

func (*LinkedList[T]) DelAtEnd 

func (ll *LinkedList[T]) DelAtEnd() (T, bool)

DelAtEnd deletes the snode at the tail(end) of the list and returns its value. Returns false if the list is empty.

func (*LinkedList[T]) DelByPos 

func (ll *LinkedList[T]) DelByPos(pos int) (T, bool)

DelByPos deletes the node at the middle based on position in the list and returns its value. Returns false if the list is empty or length is not more than given position

func (*LinkedList[T]) Display 

func (ll *LinkedList[T]) Display()

Display prints out the elements of the list.

func (*LinkedList[T]) Reverse 

func (ll *LinkedList[T]) Reverse()

Reverse reverses the list.

func (*LinkedList[T]) ReversePartition 

func (ll *LinkedList[T]) ReversePartition(left, right int) error

ReversePartition Reverse the linked list from the ath to the bth node

type Node 

type Node[T any] struct {
	Val  T
	Prev *Node[T]
	Next *Node[T]
}

Node Structure representing the linkedlist node. This node is shared across different implementations.

func NewLinkedListNode 

func NewLinkedListNode[T any](val T) *Node[T]

Create new node.

type OnEvict 

type OnEvict[K comparable, V any] func(key K, value V)

OnEvict is called whenever an entry is evicted from the cache (due to capacity pressure or Purge). Implementations MUST be fast and non‑blocking: do not perform slow I/O or take contended locks here. Typical uses include metrics and best‑effort cleanup of resources owned by the value.

type SafeLRU 

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

SafeLRU wraps an LRU with an internal RWMutex to provide threadsafe access.

When to prefer SafeLRU

  • Use SafeLRU when you are employing the cache as a standalone component and do not already hold an external lock.
  • If you already guard updates with a higher‑level mutex (e.g., sharded cache design), prefer the bare LRU to avoid double‑locking and contention.

func NewSafeLRU 

func NewSafeLRU[K comparable, V any](core *LRU[K, V]) *SafeLRU[K, V]

NewSafe wraps a non-concurrent LRU into a threadsafe instance using RWMutex. The core LRU must be non-nil.

func (*SafeLRU[K, V]) Capacity 

func (s *SafeLRU[K, V]) Capacity() int

Capacity returns the maximum number of items the cache can hold. This is a read operation.

func (*SafeLRU[K, V]) Delete 

func (s *SafeLRU[K, V]) Delete(k K) bool

Delete removes key if present and returns true on success. The eviction

func (*SafeLRU[K, V]) Get 

func (s *SafeLRU[K, V]) Get(k K) (V, bool)

Get retrieves a value and moves it to the front (MRU). ok=false if not found. This is a write operation because it updates recency.

func (*SafeLRU[K, V]) Keys 

func (s *SafeLRU[K, V]) Keys() []K

Keys returns a slice of the keys in the cache, from most- to least-recently used.

func (*SafeLRU[K, V]) Len 

func (s *SafeLRU[K, V]) Len() int

Len returns the number of items in the cache. This is a read operation.

func (*SafeLRU[K, V]) Peek 

func (s *SafeLRU[K, V]) Peek(k K) (V, bool)

Peek retrieves the value for key WITHOUT updating recency. Useful for inspection when recency‑sensitive behavior must not change. If key is absent, ok is false and v is the zero value of V.

func (*SafeLRU[K, V]) Purge 

func (s *SafeLRU[K, V]) Purge()

Purge removes all entries from the cache. If an eviction callback is set,

func (*SafeLRU[K, V]) Set 

func (s *SafeLRU[K, V]) Set(k K, v V) bool

Set inserts a new key or updates an existing one. The entry becomes the most‑recently used. If the insertion pushes the cache beyond capacity, the least‑recently used item is evicted and the eviction hook (if present) is called. The return value reports whether an eviction occurred.

type TinyLFU 

type TinyLFU[K any] struct {
	// contains filtered or unexported fields
}

TinyLFU implements the admission test using a Count‑Min Sketch. It is NOT internally synchronized; coordinate access externally as needed (e.g., with shard‑level locks in your cache engine).

func NewTinyLFU 

func NewTinyLFU[K any](depth int, width uint64, agingEvery uint64, hash Hasher[K]) (*TinyLFU[K], error)

NewTinyLFU constructs a TinyLFU with the provided parameters and hash function. For convenience, this keeps the classic signature. Prefer NewTinyLFUWithOptions for full control.

func NewTinyLFUWithOptions 

func NewTinyLFUWithOptions[K any](opt TinyLFUOptions[K]) (*TinyLFU[K], error)

NewTinyLFUWithOptions constructs a TinyLFU using TinyLFUOptions. Hash is required; panics if nil. Returns an error if the underlying sketch cannot be created (invalid depth/width, etc.).

func (*TinyLFU[K]) Age 

func (t *TinyLFU[K]) Age()

Age halves all counters, biasing the sketch toward recent history. Use when you manage aging externally. If you configured AgingEvery>0, aging will also occur automatically within Record/RecordN.

func (*TinyLFU[K]) Estimate 

func (t *TinyLFU[K]) Estimate(key K) uint32

Estimate returns the sketch’s current frequency estimate for key.

func (*TinyLFU[K]) Record 

func (t *TinyLFU[K]) Record(key K)

Record registers an access for key (hit or miss). Call this on every request, whether the key is currently in the cache or not. This is how TinyLFU learns popularity and protects the cache from one‑hit wonders.

func (*TinyLFU[K]) RecordN 

func (t *TinyLFU[K]) RecordN(key K, n uint32)

RecordN registers n accesses for key. Useful when you want to batch multiple observations at once (e.g., aggregating counters from another system).

func (*TinyLFU[K]) Reset 

func (t *TinyLFU[K]) Reset()

Reset zeroes all counters and the op counter. Useful for tests or hard resets.

func (*TinyLFU[K]) ShouldAdmit 

func (t *TinyLFU[K]) ShouldAdmit(incoming, victim K) bool

ShouldAdmit compares the estimated frequency of the incoming key against that of the victim key. It returns true if the policy decides to admit the incoming item (i.e., evict the victim) and false if the newcomer should be rejected. When AdmitOnEqual is true, ties admit the newcomer.

func (*TinyLFU[K]) ShouldAdmitAgainst 

func (t *TinyLFU[K]) ShouldAdmitAgainst(incoming K, victimFreq uint32) bool

ShouldAdmitAgainst compares the incoming key’s frequency against an explicit victim frequency (useful when you already fetched the victim’s frequency or when the exact victim key is unknown). Honors AdmitOnEqual.

func (*TinyLFU[K]) VictimFreq 

func (t *TinyLFU[K]) VictimFreq(victim K) uint32

VictimFreq is a convenience helper that reads the current frequency estimate for a would‑be victim key.

type TinyLFUOptions 

type TinyLFUOptions[K any] struct {
	Depth        int
	Width        uint64
	AgingEvery   uint64
	AdmitOnEqual bool
	Hash         Hasher[K]
}

TinyLFUOptions configures a TinyLFU instance.

Recommended defaults: 

Depth:       4
Width:       1<<16 (per row)
AgingEvery:  50_000 .. 500_000 (workload dependent)
AdmitOnEqual: true (admit newcomer when frequencies tie)

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.