Static-memory hash map with LRU-like eviction for fixed RAM usage. More...

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>

Data Structures
struct	lru_kv_pair_t
	Single key/value slot with access tracking for the static LRU hash map. More...
struct	static_lru_hash_map_t
	Fixed-size hash map with LRU-like eviction for bounded memory usage. More...

Macros
#define	STATIC_LRU_EVICTION_LOAD_FACTOR 0.90
	Default configuration constants for the static LRU hash map.
#define	STATIC_LRU_TARGET_LOAD_FACTOR 0.75
	Evict down to 75% capacity.
#define	STATIC_LRU_AGING_INTERVAL 100000
	Age access counts every N operations.
#define	STATIC_LRU_MIN_SIZE 1024
	Minimum map size to prevent edge cases.

Functions
static_lru_hash_map_t *	static_lru_create_map (size_t size)
	Creates a new static LRU hash map with fixed size.
void	static_lru_free_map (static_lru_hash_map_t *map)
	Frees all memory associated with a static LRU hash map.
bool	static_lru_insert_map (static_lru_hash_map_t *map, uint64_t key, uint64_t value)
	Inserts a key-value pair into the static LRU hash map.
bool	static_lru_lookup_map (static_lru_hash_map_t map, uint64_t key, uint64_t out_value)
	Looks up a value by key in the static LRU hash map.
bool	static_lru_contains_key (const static_lru_hash_map_t *map, uint64_t key)
	Checks if a key exists in the map WITHOUT updating access count.
size_t	static_lru_evict (static_lru_hash_map_t *map, size_t entries_to_keep)
	Manually triggers eviction of least-used entries.
void	static_lru_age_counts (static_lru_hash_map_t *map)
	Manually ages all access counts.
double	static_lru_load_factor (const static_lru_hash_map_t *map)
	Returns the current load factor of the map.
size_t	static_lru_free_slots (const static_lru_hash_map_t *map)
	Returns the number of free slots available.

Detailed Description

Static-memory hash map with LRU-like eviction for fixed RAM usage.

This hash map variant has the following characteristics:

Fixed memory allocation set at creation time (never grows)
Tracks access frequency for each entry
Automatically evicts least-frequently-used entries when approaching capacity
Maintains a minimum percentage of free slots for new insertions
Uses approximate LFU (Least Frequently Used) with aging to prevent stale entries

Use this instead of hash_map_t when you need predictable, bounded memory usage and can tolerate eviction of less-frequently-accessed entries.

Definition in file static_lru_hash_map.h.

Macro Definition Documentation

◆ STATIC_LRU_AGING_INTERVAL

#define STATIC_LRU_AGING_INTERVAL 100000

Age access counts every N operations.

Definition at line 55 of file static_lru_hash_map.h.

Referenced by static_lru_insert_map().

◆ STATIC_LRU_EVICTION_LOAD_FACTOR

#define STATIC_LRU_EVICTION_LOAD_FACTOR 0.90

Default configuration constants for the static LRU hash map.

These can be overridden by defining them before including this header. Trigger eviction when 90% full

Definition at line 47 of file static_lru_hash_map.h.

Referenced by static_lru_create_map().

◆ STATIC_LRU_MIN_SIZE

#define STATIC_LRU_MIN_SIZE 1024

Minimum map size to prevent edge cases.

Definition at line 59 of file static_lru_hash_map.h.

Referenced by static_lru_create_map().

◆ STATIC_LRU_TARGET_LOAD_FACTOR

#define STATIC_LRU_TARGET_LOAD_FACTOR 0.75

Evict down to 75% capacity.

Definition at line 51 of file static_lru_hash_map.h.

Referenced by static_lru_create_map().

Function Documentation

◆ static_lru_age_counts()

void static_lru_age_counts ( static_lru_hash_map_t * map )

Manually ages all access counts.

Halves all access counts in the map. This is normally done automatically every STATIC_LRU_AGING_INTERVAL operations, but can be called manually to reset frequency tracking.

Parameters

map	Pointer to the hash map. Must not be NULL.

Definition at line 331 of file static_lru_hash_map.c.

References age_access_counts(), and static_lru_hash_map_t::age_counter.

◆ static_lru_contains_key()

bool static_lru_contains_key	(	const static_lru_hash_map_t *	map,
		uint64_t	key )

Checks if a key exists in the map WITHOUT updating access count.

This is useful when you need to check existence without affecting eviction priority.

Parameters

map	Pointer to the hash map to search. Must not be NULL.
key	The key to search for. Must not be 0.

Returns: Returns whether the key exists in the map.

Return values

true	Key exists in the map.
false	Key not found.

Note: Unlike static_lru_lookup_map(), this does NOT update access_count.

Definition at line 314 of file static_lru_hash_map.c.

References lru_kv_pair_t::key, static_lru_hash_map_t::size, static_lru_hash_map_t::table, and TOMBSTONE_KEY.

◆ static_lru_create_map()

static_lru_hash_map_t * static_lru_create_map ( size_t size )

Creates a new static LRU hash map with fixed size.

Allocates and initializes a new hash map structure with the given size. This is the ONLY allocation that will ever occur for this map - the size is fixed and will never grow. When the map fills up, old entries are evicted instead of allocating more memory.

Parameters

size	Fixed size of the hash table. Enforced minimum is STATIC_LRU_MIN_SIZE. Choose this based on your memory budget and expected working set.

Returns: Returns a pointer to the newly created hash map, or NULL if allocation fails.

Note: Memory usage: approximately (size * 24) bytes for the table.; The caller is responsible for freeing the returned hash map using static_lru_free_map().; A key value of 0 is reserved to indicate empty slots and cannot be used as a valid key.

See also: static_lru_free_map()

Definition at line 204 of file static_lru_hash_map.c.

References static_lru_hash_map_t::_padding, static_lru_hash_map_t::age_counter, static_lru_hash_map_t::count, static_lru_hash_map_t::max_count, static_lru_hash_map_t::size, STATIC_LRU_EVICTION_LOAD_FACTOR, STATIC_LRU_MIN_SIZE, STATIC_LRU_TARGET_LOAD_FACTOR, static_lru_hash_map_t::table, and static_lru_hash_map_t::target_count.

◆ static_lru_evict()

size_t static_lru_evict	(	static_lru_hash_map_t *	map,
		size_t	entries_to_keep )

Manually triggers eviction of least-used entries.

Forces an eviction cycle even if the map hasn't reached the eviction threshold. Useful for proactively freeing memory or resetting the cache.

Parameters

map	Pointer to the hash map. Must not be NULL.
entries_to_keep	Number of entries to keep after eviction. If 0, uses target_count.

Returns: Number of entries actually evicted.

Definition at line 328 of file static_lru_hash_map.c.

References evict_lru_entries().

◆ static_lru_free_map()

void static_lru_free_map ( static_lru_hash_map_t * map )

Frees all memory associated with a static LRU hash map.

Deallocates the hash table and the hash map structure itself.

Parameters

map	Pointer to the hash map to free. Can be NULL (no operation performed).

Note: This function does not free any memory pointed to by the values stored in the map.

See also: static_lru_create_map()

Definition at line 237 of file static_lru_hash_map.c.

References static_lru_hash_map_t::table.

◆ static_lru_free_slots()

size_t static_lru_free_slots ( const static_lru_hash_map_t * map )

Returns the number of free slots available.

Parameters

map	Pointer to the hash map. Must not be NULL.

Returns: Number of empty slots (size - count).

Definition at line 339 of file static_lru_hash_map.c.

References static_lru_hash_map_t::count, and static_lru_hash_map_t::size.

◆ static_lru_insert_map()

bool static_lru_insert_map	(	static_lru_hash_map_t *	map,
		uint64_t	key,
		uint64_t	value )

Inserts a key-value pair into the static LRU hash map.

Adds a new key-value pair to the hash map. If the map is approaching capacity (exceeds STATIC_LRU_EVICTION_LOAD_FACTOR), the least-frequently-used entries are automatically evicted before insertion.

If the key already exists, the value is updated and the access count is incremented.

Parameters

map	Pointer to the hash map. Must not be NULL.
key	The key to insert. Must not be 0 (reserved for empty slots).
value	The value to associate with the key.

Returns: Returns the result of the insertion operation.

Return values

true	Successfully inserted a NEW key-value pair.
false	Key already existed; value was updated instead.

Note: New entries start with access_count = 1.; Updating an existing entry increments its access_count (up to 255).; Time complexity: O(1) average, O(n) when eviction is triggered.

Warning: Using 0 as a key value will result in undefined behavior.

See also: static_lru_lookup_map()

Definition at line 245 of file static_lru_hash_map.c.

References lru_kv_pair_t::access_count, age_access_counts(), static_lru_hash_map_t::age_counter, static_lru_hash_map_t::count, evict_lru_entries(), lru_kv_pair_t::key, static_lru_hash_map_t::max_count, MIN_ACCESS_COUNT, static_lru_hash_map_t::size, STATIC_LRU_AGING_INTERVAL, static_lru_hash_map_t::table, TOMBSTONE_KEY, and lru_kv_pair_t::value.

◆ static_lru_load_factor()

double static_lru_load_factor ( const static_lru_hash_map_t * map )

Returns the current load factor of the map.

Parameters

map	Pointer to the hash map. Must not be NULL.

Returns: Current load factor as a value between 0.0 and 1.0.

Definition at line 337 of file static_lru_hash_map.c.

References static_lru_hash_map_t::count, and static_lru_hash_map_t::size.

◆ static_lru_lookup_map()

bool static_lru_lookup_map	(	static_lru_hash_map_t *	map,
		uint64_t	key,
		uint64_t *	out_value )

Looks up a value by key in the static LRU hash map.

Searches for the specified key and retrieves its associated value. Unlike the regular hash_map, this function DOES modify the map by incrementing the access_count of the found entry (to track usage frequency).

Parameters

map	Pointer to the hash map to search. Must not be NULL.
key	The key to search for. Must not be 0.
out_value	Pointer to store the found value. Must not be NULL. Only modified if the key is found.

Returns: Returns whether the key was found in the map.

Return values

true	Key found. The associated value is written to *out_value.
false	Key not found. *out_value is not modified.

Note: This function increments access_count on successful lookups.; Time complexity: O(1) average case.

See also: static_lru_insert_map()

Definition at line 284 of file static_lru_hash_map.c.

References lru_kv_pair_t::access_count, lru_kv_pair_t::key, static_lru_hash_map_t::size, static_lru_hash_map_t::table, TOMBSTONE_KEY, and lru_kv_pair_t::value.

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ STATIC_LRU_AGING_INTERVAL

◆ STATIC_LRU_EVICTION_LOAD_FACTOR

◆ STATIC_LRU_MIN_SIZE

◆ STATIC_LRU_TARGET_LOAD_FACTOR

Function Documentation

◆ static_lru_age_counts()

◆ static_lru_contains_key()

◆ static_lru_create_map()

◆ static_lru_evict()

◆ static_lru_free_map()

◆ static_lru_free_slots()

◆ static_lru_insert_map()

◆ static_lru_load_factor()

◆ static_lru_lookup_map()