Hash Map. More...

Data Structures
struct	map_key_t
	Map key stucture. More...

struct	map_entry_t
	Map entry structure. More...

struct	map_t
	Hash map structure. More...

Macros
#define	MAP_MIN_CAPACITY 16
	The minimum capacity of a map.

#define	MAP_MAX_LOAD_PERCENTAGE 75
	The maximum load percentage of a map before it resizes.

#define	MAP_TOMBSTONE ((map_entry_t*)1)
	The value used to indicate a tombstone (removed entry).

#define	MAP_KEY_MAX_LENGTH 40
	The maximum length of a key in the map.

#define	MAP_ENTRY_PTR_IS_VALID(entryPtr) ((entryPtr) != NULL && (entryPtr) != MAP_TOMBSTONE)
	Check if a map entry pointer is valid (not NULL or tombstone).

Functions
uint64_t	hash_object (const void *object, uint64_t length)
	Hash a object.

static map_key_t	map_key_buffer (const void *buffer, uint64_t length)
	Create a map key from a buffer.

static map_key_t	map_key_uint64 (uint64_t uint64)
	Create a map key from a uint64_t.

static map_key_t	map_key_string (const char *str)
	Create a map key from a string.

void	map_entry_init (map_entry_t *entry)
	Initialize a map entry.

uint64_t	map_init (map_t *map)
	Initialize a map.

void	map_deinit (map_t *map)
	Deinitialize a map.

uint64_t	map_insert (map_t map, const map_key_t key, map_entry_t *value)
	Insert a key-value pair into the map.

map_entry_t *	map_get (map_t map, const map_key_t key)
	Get a value from the map by key.

void	map_remove (map_t map, const map_key_t key)
	Remove a key-value pair from the map.

uint64_t	map_size (const map_t *map)
	Get the number of entries in the map.

uint64_t	map_capacity (const map_t *map)
	Get the capacity of the map.

bool	map_is_empty (const map_t *map)
	Check if the map is empty.

bool	map_contains (map_t map, const map_key_t key)
	Check if the map contains a key.

void	map_clear (map_t *map)
	Clear all entries from the map.

uint64_t	map_reserve (map_t *map, uint64_t minCapacity)
	Reserve space in the map for at least `minCapacity` entries.

Detailed Description

Hash Map.

Macro Definition Documentation

◆ MAP_ENTRY_PTR_IS_VALID

#define MAP_ENTRY_PTR_IS_VALID ( entryPtr ) ((entryPtr) != NULL && (entryPtr) != MAP_TOMBSTONE)

Check if a map entry pointer is valid (not NULL or tombstone).

Parameters

entryPtr The map entry pointer to check.

Returns: true if the entry pointer is valid, false otherwise.

Definition at line 67 of file map.h.

◆ MAP_KEY_MAX_LENGTH

#define MAP_KEY_MAX_LENGTH 40

The maximum length of a key in the map.

Definition at line 35 of file map.h.

◆ MAP_MAX_LOAD_PERCENTAGE

#define MAP_MAX_LOAD_PERCENTAGE 75

The maximum load percentage of a map before it resizes.

Definition at line 25 of file map.h.

◆ MAP_MIN_CAPACITY

#define MAP_MIN_CAPACITY 16

The minimum capacity of a map.

Definition at line 20 of file map.h.

◆ MAP_TOMBSTONE

#define MAP_TOMBSTONE ((map_entry_t*)1)

The value used to indicate a tombstone (removed entry).

Definition at line 30 of file map.h.

Function Documentation

◆ hash_object()

uint64_t hash_object	(	const void *	object,
		uint64_t	length
	)

Hash a object.

Parameters

object	The object to hash.
length	The length of the object in bytes.

Returns: The hash of the object.

Definition at line 42 of file map.c.

Referenced by map_key_buffer(), and map_key_uint64().

◆ map_capacity()

uint64_t map_capacity ( const map_t * map )

Get the capacity of the map.

Parameters

map	The map to get the capacity of.

Returns: The capacity of the map.

Definition at line 284 of file map.c.

References map.

◆ map_clear()

void map_clear ( map_t * map )

Clear all entries from the map.

Note that this does not free the entries themselves, only removes them from the map.

Parameters

map	The map to clear.

Definition at line 299 of file map.c.

References boot_memory_map_t::length, map, and NULL.

◆ map_contains()

bool map_contains	(	map_t *	map,
		const map_key_t *	key
	)

Check if the map contains a key.

Parameters

map	The map to check.
key	The key to check for.

Returns: true if the map contains the key, false otherwise.

Definition at line 294 of file map.c.

References map, map_get(), and NULL.

◆ map_deinit()

void map_deinit ( map_t * map )

Deinitialize a map.

Parameters

map	The map to deinitialize.

Definition at line 182 of file map.c.

References free(), boot_memory_map_t::length, map, and NULL.

Referenced by aml_namespace_overlay_deinit(), futex_ctx_deinit(), and namespace_deinit().

◆ map_entry_init()

void map_entry_init ( map_entry_t * entry )

Initialize a map entry.

Parameters

entry The map entry to initialize.

Definition at line 71 of file map.c.

References map_key_t::hash, map_key_t::key, map_entry_t::key, map_key_t::len, and memset().

Referenced by aml_object_new(), dentry_new(), futex_ctx_get(), inode_new(), key_share(), local_listen_new(), mount_new(), path_flags_init(), and space_pin_depth_inc().

◆ map_get()

map_entry_t * map_get	(	map_t *	map,
		const map_key_t *	key
	)

Get a value from the map by key.

Parameters

map	The map to get from.
key	The key to get.

Returns: On success, the value. If the key does not exist, returns NULL.

Definition at line 236 of file map.c.

References ERR, map_entry_t::key, map, map_find_slot(), map_key_is_equal(), MAP_TOMBSTONE, and NULL.

Referenced by aml_namespace_add_child(), aml_namespace_find_child(), aml_namespace_overlay_get_highest_that_contains(), futex_ctx_get(), key_claim(), key_generate(), local_listen_find(), local_listen_new(), map_contains(), namespace_traverse_mount(), path_flags_get(), space_pin_depth_dec(), space_pin_depth_inc(), vfs_get_dentry_internal(), and vfs_get_inode().

◆ map_init()

uint64_t map_init ( map_t * map )

Initialize a map.

Parameters

map	The map to initialize.

Returns: On success, 0. On failure, ERR and errno is set.

Definition at line 172 of file map.c.

References boot_memory_map_t::length, map, and NULL.

Referenced by aml_namespace_overlay_init(), futex_ctx_init(), key_init(), local_listen_dir_init(), namespace_init(), path_flags_init(), space_init(), and vfs_map_init().

◆ map_insert()

uint64_t map_insert	(	map_t *	map,
		const map_key_t *	key,
		map_entry_t *	value
	)

Insert a key-value pair into the map.

If the key already exists, then an EEXIST error is returned.

Parameters

map	The map to insert into.
key	The key to insert.
value	The value to insert.

Returns: On success, 0. On failure, ERR and errno is set.

Definition at line 191 of file map.c.

References EEXIST, EINVAL, ENOMEM, ERR, errno, boot_memory_map_t::key, map_entry_t::key, boot_memory_map_t::length, map, map_find_slot(), map_key_is_equal(), MAP_MAX_LOAD_PERCENTAGE, MAP_MIN_CAPACITY, map_resize(), MAP_TOMBSTONE, and NULL.

Referenced by aml_namespace_add_child(), aml_namespace_commit(), futex_ctx_get(), key_share(), local_listen_new(), namespace_bind(), namespace_mount(), path_flags_init(), space_pin_depth_inc(), vfs_add_dentry(), and vfs_add_inode().

◆ map_is_empty()

bool map_is_empty ( const map_t * map )

Check if the map is empty.

Parameters

map	The map to check.

Returns: true if the map is empty, false otherwise.

Definition at line 289 of file map.c.

References boot_memory_map_t::length, and map.

Referenced by aml_namespace_commit().

◆ map_key_buffer()

static map_key_t map_key_buffer	(	const void *	buffer,
		uint64_t	length
	)

inlinestatic

Create a map key from a buffer.

Parameters

buffer	The buffer to create the key from.
length	The length of the buffer in bytes.

Returns: The map key.

Definition at line 99 of file map.h.

References assert, buffer, map_key_t::hash, hash_object(), map_key_t::key, map_key_t::len, MAP_KEY_MAX_LENGTH, and memcpy().

Referenced by aml_object_map_key(), dentry_cache_key(), key_claim(), key_generate(), key_share(), key_timer_handler(), map_key_string(), mount_cache_key(), path_flags_get(), and path_flags_init().

◆ map_key_string()

static map_key_t map_key_string ( const char * str )

inlinestatic

Create a map key from a string.

Parameters

str	The string to create the key from.

Returns: The map key.

Definition at line 130 of file map.h.

References map_key_buffer(), and strlen().

Referenced by local_listen_find(), local_listen_free(), local_listen_new(), and path_flags_init().

◆ map_key_uint64()

static map_key_t map_key_uint64 ( uint64_t uint64 )

inlinestatic

Create a map key from a uint64_t.

Parameters

uint64 The uint64_t to create the key from.

Returns: The map key.

Definition at line 115 of file map.h.

References map_key_t::hash, hash_object(), map_key_t::key, map_key_t::len, and memcpy().

Referenced by futex_ctx_get(), space_pin_depth_dec(), and space_pin_depth_inc().

◆ map_remove()

void map_remove	(	map_t *	map,
		const map_key_t *	key
	)

Remove a key-value pair from the map.

If the key does not exist, nothing happens.

Parameters

map	The map to remove from.
key	The key to remove.

Definition at line 258 of file map.c.

References ERR, map_entry_t::key, boot_memory_map_t::length, map, map_find_slot(), map_key_is_equal(), MAP_TOMBSTONE, and NULL.

Referenced by aml_namespace_commit(), aml_namespace_remove(), key_claim(), key_timer_handler(), local_listen_free(), space_pin_depth_dec(), vfs_remove_dentry(), and vfs_remove_inode().

◆ map_reserve()

uint64_t map_reserve	(	map_t *	map,
		uint64_t	minCapacity
	)

Reserve space in the map for at least minCapacity entries.

Parameters

map	The map to reserve space in.
minCapacity	The minimum capacity to reserve.

Returns: On success, 0. On failure, ERR and errno is set.

Definition at line 310 of file map.c.

References ENOMEM, ERR, errno, map, map_resize(), and next_power_of_two().

◆ map_size()

uint64_t map_size ( const map_t * map )

Get the number of entries in the map.

Parameters

map	The map to get the size of.

Returns: The number of entries in the map.

Definition at line 279 of file map.c.

References boot_memory_map_t::length, and map.

Data Structures

Macros

Functions

Detailed Description

Macro Definition Documentation

◆ MAP_ENTRY_PTR_IS_VALID

◆ MAP_KEY_MAX_LENGTH

◆ MAP_MAX_LOAD_PERCENTAGE

◆ MAP_MIN_CAPACITY

◆ MAP_TOMBSTONE

Function Documentation

◆ hash_object()

◆ map_capacity()

◆ map_clear()

◆ map_contains()

◆ map_deinit()

◆ map_entry_init()

◆ map_get()

◆ map_init()

◆ map_insert()

◆ map_is_empty()

◆ map_key_buffer()

◆ map_key_string()

◆ map_key_uint64()

◆ map_remove()

◆ map_reserve()

◆ map_size()