hashmap.h File Reference

#include <core/system.h>
#include <core/string.h>
#include <aquila/errno.h>
#include <ds/queue.h>

Go to the source code of this file.

Data Structures
struct	hashmap
	A hash table. More...
struct	hashmap_node
	A hash table's node: an entry, with its key's hash. More...

Macros
#define	HASHMAP_DEFAULT   20
#define	HASHMAP_LOAD   2
#define	hashmap_for(n, h)

Typedefs
typedef uintptr_t	hash_t

Functions
static struct hashmap *	hashmap_new (size_t n, int(*eq)(void *, void *))
	Makes a new, empty hash table of n buckets (0: HASHMAP_DEFAULT).
static hash_t	hashmap_digest (const void *_id, size_t size)
	Returns the hash of a key of size bytes.
static void	hashmap_grow (struct hashmap *hashmap)
	Doubles a table's buckets, and moves each entry to its new bucket.
static int	hashmap_insert (struct hashmap *hashmap, hash_t hash, void *entry)
	Adds an entry to a hash table.
static struct hashmap_node *	hashmap_lookup (struct hashmap *hashmap, hash_t hash, void *key)
	Finds the node of the entry for a key, or returns NULL if there's none.
static int	hashmap_replace (struct hashmap *hashmap, hash_t hash, void *key, void *entry)
	Replaces the entry for a key, or adds it if there's none.
static void	hashmap_node_remove (struct hashmap *hashmap, struct hashmap_node *node)
	Removes a node from a hash table, and frees it (not its entry).
static void	hashmap_free (struct hashmap *hashmap)
	Frees a hash table and its nodes (not their entries).

Macro Definition Documentation

HASHMAP_DEFAULT

#define HASHMAP_DEFAULT   20

Definition at line 25 of file hashmap.h.

Referenced by hashmap_new().

hashmap_for

#define hashmap_for	(		n,
			h )

Value:

for (size_t __i__ = 0; __i__ < (h)->buckets_nr; ++__i__) \
    queue_for ((n), &(h)->buckets[__i__])

Definition at line 51 of file hashmap.h.

Referenced by vm_anon_copy_arefs(), vm_anon_destroy(), and vnode_pages_free().

HASHMAP_LOAD

#define HASHMAP_LOAD   2

Definition at line 29 of file hashmap.h.

Referenced by hashmap_insert().

Typedef Documentation

hash_t

typedef uintptr_t hash_t

Definition at line 22 of file hashmap.h.

Function Documentation

hashmap_digest()

hash_t hashmap_digest ( const void * _id, size_t size )

inlinestatic

Returns the hash of a key of size bytes.

Definition at line 85 of file hashmap.h.

hashmap_free()

void hashmap_free ( struct hashmap * hashmap )

inlinestatic

Frees a hash table and its nodes (not their entries).

Definition at line 235 of file hashmap.h.

References hashmap::buckets, hashmap::buckets_nr, and kfree().

hashmap_grow()

void hashmap_grow ( struct hashmap * hashmap )

inlinestatic

Doubles a table's buckets, and moves each entry to its new bucket.

The queue nodes are relinked rather than made anew. If there's no memory for the new buckets, the table stays as it is.

Definition at line 110 of file hashmap.h.

References buckets, hashmap::buckets, hashmap::buckets_nr, queue::count, hashmap_node::hash, hashmap_grow(), queue::head, kfree(), kmalloc(), M_ZERO, qnode::next, NULL, qnode::prev, queue::tail, and qnode::value.

Referenced by hashmap_grow(), and hashmap_insert().

hashmap_insert()

int hashmap_insert ( struct hashmap * hashmap, hash_t hash, void * entry )

inlinestatic

Adds an entry to a hash table.

Returns 0, -EINVAL for a bad table, or -ENOMEM if there was no memory for its node.

Definition at line 148 of file hashmap.h.

References hashmap::buckets, hashmap::buckets_nr, hashmap::count, hashmap_node::entry, hashmap_node::hash, hashmap_grow(), HASHMAP_LOAD, kfree(), kmalloc(), and hashmap_node::qnode.

Referenced by hashmap_replace().

hashmap_lookup()

struct hashmap_node * hashmap_lookup ( struct hashmap * hashmap, hash_t hash, void * key )

inlinestatic

Finds the node of the entry for a key, or returns NULL if there's none.

Definition at line 181 of file hashmap.h.

References hashmap::buckets, hashmap::buckets_nr, hashmap::count, hashmap_node::entry, hashmap::eq, hashmap_node::hash, NULL, and queue_for.

hashmap_new()

struct hashmap * hashmap_new ( size_t n, int(* eq )(void *, void *) )

inlinestatic

Makes a new, empty hash table of n buckets (0: HASHMAP_DEFAULT).

Returns it, or NULL if there was no memory for it.

Definition at line 57 of file hashmap.h.

References hashmap::buckets, hashmap::buckets_nr, hashmap::eq, HASHMAP_DEFAULT, kfree(), kmalloc(), memset(), and NULL.

hashmap_node_remove()

void hashmap_node_remove ( struct hashmap * hashmap, struct hashmap_node * node )

inlinestatic

Removes a node from a hash table, and frees it (not its entry).

Definition at line 220 of file hashmap.h.

References hashmap::buckets, hashmap::buckets_nr, hashmap::count, hashmap_node::hash, kfree(), and hashmap_node::qnode.

hashmap_replace()

int hashmap_replace ( struct hashmap * hashmap, hash_t hash, void * key, void * entry )

inlinestatic

Replaces the entry for a key, or adds it if there's none.

Returns 0, or what hashmap_insert() returned.

Definition at line 200 of file hashmap.h.

References hashmap::buckets, hashmap::buckets_nr, hashmap::count, hashmap_node::entry, hashmap::eq, hashmap_node::hash, hashmap_insert(), hashmap_replace(), and queue_for.

Referenced by hashmap_replace().