Implementation of static-memory hash map with LRU-like eviction. More...

#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
#include <string.h>
#include "aaruformat/static_lru_hash_map.h"

Macros
#define	MIN_ACCESS_COUNT 1
	New entries start with this access count.
#define	TOMBSTONE_KEY 0
	Marker for empty/deleted slots (key=0 reserved).

Functions
static void	age_access_counts (static_lru_hash_map_t *map)
	Ages all access counts by halving them.
static void	rehash_in_place (static_lru_hash_map_t *map)
	Rehashes all entries in place after eviction.
static size_t	evict_lru_entries (static_lru_hash_map_t *map, size_t target_count_out)
	Evicts least-frequently-used entries to make room for new insertions.
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

Implementation of static-memory hash map with LRU-like eviction.

This implementation provides a hash map with:

Fixed memory allocation (size set at creation, never grows)
Automatic eviction of least-frequently-used entries when approaching capacity
Access frequency tracking with periodic aging to prevent stale hot entries
Same API style as hash_map.c for easy migration

Eviction Strategy: Approximate LFU (Least Frequently Used) with Aging

Each entry has an 8-bit access_count (0-255, saturates)
Count is incremented on each lookup or update
Counts are halved periodically (aging) to favor recent accesses
Eviction removes entries with lowest access_count first

Collision Resolution: Open addressing with linear probing (same as hash_map.c)

Definition in file static_lru_hash_map.c.

Macro Definition Documentation

◆ MIN_ACCESS_COUNT

#define MIN_ACCESS_COUNT 1

New entries start with this access count.

Definition at line 49 of file static_lru_hash_map.c.

Referenced by static_lru_insert_map().

◆ TOMBSTONE_KEY

#define TOMBSTONE_KEY 0

Marker for empty/deleted slots (key=0 reserved).

Definition at line 50 of file static_lru_hash_map.c.

Referenced by age_access_counts(), evict_lru_entries(), rehash_in_place(), static_lru_contains_key(), static_lru_insert_map(), and static_lru_lookup_map().

Function Documentation

◆ age_access_counts()

void age_access_counts ( static_lru_hash_map_t * map )

static

Ages all access counts by halving them.

This prevents old "hot" entries from permanently occupying the cache. Called automatically every STATIC_LRU_AGING_INTERVAL operations.

Parameters

map	Pointer to the hash map.

Definition at line 64 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, and TOMBSTONE_KEY.

Referenced by static_lru_age_counts(), and static_lru_insert_map().

◆ evict_lru_entries()

size_t evict_lru_entries	(	static_lru_hash_map_t *	map,
		size_t	target_count_out )

static

Evicts least-frequently-used entries to make room for new insertions.

Algorithm:

Build a histogram of access counts (256 buckets for uint8_t)
Find the cutoff access_count that covers enough entries to evict
Mark entries at or below the cutoff as deleted
Rehash remaining entries to fix probe chains

Time complexity: O(n) where n = map size

Parameters

map	Pointer to the hash map.
target_count_out	Target count after eviction. If 0, uses map->target_count.

Returns: Number of entries evicted.

Definition at line 139 of file static_lru_hash_map.c.

References lru_kv_pair_t::access_count, static_lru_hash_map_t::count, lru_kv_pair_t::key, rehash_in_place(), static_lru_hash_map_t::size, static_lru_hash_map_t::table, static_lru_hash_map_t::target_count, TOMBSTONE_KEY, and lru_kv_pair_t::value.

Referenced by static_lru_evict(), and static_lru_insert_map().

◆ rehash_in_place()

void rehash_in_place ( static_lru_hash_map_t * map )

static

Rehashes all entries in place after eviction.

After evicting entries, the linear probing chains are broken. This function rebuilds the table to restore proper probe sequences.

Note: This temporarily allocates a second table. For truly static memory, a more complex in-place algorithm would be needed.

Parameters

map	Pointer to the hash map.

Definition at line 87 of file static_lru_hash_map.c.

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

Referenced by evict_lru_entries().

◆ 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.

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ MIN_ACCESS_COUNT

◆ TOMBSTONE_KEY

Function Documentation

◆ age_access_counts()

◆ evict_lru_entries()

◆ rehash_in_place()

◆ 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()