File hash_map.h¶

FileList > docs > sw > include > opae > hash_map.h

A general-purpose hybrid array/list hash map implementation. More...

#include <stdint.h>
#include <stdbool.h>
#include <opae/types_enum.h>

Classes¶

Type	Name
struct	_opae_hash_map Hash map object.
struct	_opae_hash_map_item List link item.

Public Types¶

Type	Name
enum	_opae_hash_map_flags Flags used to initialize a hash map.
typedef struct _opae_hash_map	opae_hash_map Hash map object.
typedef enum _opae_hash_map_flags	opae_hash_map_flags Flags used to initialize a hash map.
typedef struct _opae_hash_map_item	opae_hash_map_item List link item.

Public Functions¶

Type	Name
fpga_result	opae_hash_map_add (opae_hash_map * hm, void * key, void * value) Map a key to a value.
fpga_result	opae_hash_map_destroy (opae_hash_map * hm) Tear down a hash map.
fpga_result	opae_hash_map_find (opae_hash_map * hm, void * key, void ** value) Retrieve the value for a given key.
fpga_result	opae_hash_map_init (opae_hash_map * hm, uint32_t num_buckets, uint32_t hash_seed, int flags, uint32_t()(uint32_t num_buckets, uint32_t hash_seed, void key) key_hash, int()(void keya, void keyb) key_compare, void()(void key, void context) key_cleanup, void()(void value, void context) value_cleanup) Initialize a hash map.*
bool	opae_hash_map_is_empty (opae_hash_map * hm) Determine whether a hash map is empty.
fpga_result	opae_hash_map_remove (opae_hash_map * hm, void * key) Remove a key/value association.
int	opae_u64_key_compare (void * keya, void * keyb) Convenience key comparison function for 64-bit values.
uint32_t	opae_u64_key_hash (uint32_t num_buckets, uint32_t hash_seed, void * key) Convenience hash function for arbitrary pointers/64-bit values.

Detailed Description¶

Presents a generic interface for mapping key objects to value objects. Both keys and values may be arbitrary data structures. The user supplies the means by which the hash of values is generated and by which the keys are compared to each other.

Public Types Documentation¶

enum _opae_hash_map_flags¶

Flags used to initialize a hash map.

enum _opae_hash_map_flags {
    OPAE_HASH_MAP_UNIQUE_KEYSPACE = (1u << 0)
};

OPAE_HASH_MAP_UNIQUE_KEYSPACE says that the user provides a guarantee that the key space is truly unique. In other words, when the provided hash function for keys A and B returns the same bucket index, the key comparison function when comparing A and B will never return a result saying that the keys are equal in value. This is helpful in situations where the key space is guaranteed to produce unique values, for example a memory allocator. When the key space is guaranteed to be unique, opae_hash_map_add() can implement a small performance improvement.

typedef opae_hash_map¶

Hash map object.

typedef struct _opae_hash_map opae_hash_map;

This structure defines the internals of the hash map. Each of the parameters supplied to opae_hash_map_init() is stored in the structure. All parameters are required, except key_cleanup and value_cleanup, which may optionally be NULL.

typedef opae_hash_map_flags¶

Flags used to initialize a hash map.

typedef enum _opae_hash_map_flags opae_hash_map_flags;

OPAE_HASH_MAP_UNIQUE_KEYSPACE says that the user provides a guarantee that the key space is truly unique. In other words, when the provided hash function for keys A and B returns the same bucket index, the key comparison function when comparing A and B will never return a result saying that the keys are equal in value. This is helpful in situations where the key space is guaranteed to produce unique values, for example a memory allocator. When the key space is guaranteed to be unique, opae_hash_map_add() can implement a small performance improvement.

typedef opae_hash_map_item¶

List link item.

typedef struct _opae_hash_map_item opae_hash_map_item;

This structure provides the association between key and value. When the supplied hash function for keys A and B returns the same bucket index, both A and B can co-exist on the same list rooted at the bucket index.

Public Functions Documentation¶

function opae_hash_map_add¶

Map a key to a value.

fpga_result opae_hash_map_add (
    opae_hash_map * hm,
    void * key,
    void * value
)

Inserts a mapping from key to value in the given hash map object. Subsequent calls to opae_hash_map_find() that are given the key will retrieve the value.

Parameters:

hm A pointer to the storage for the hash map object.
key The hash map key.
value The hash map value.

Returns:

FPGA_OK on success, FPGA_INVALID_PARAM if hm is NULL, FPGA_NO_MEMORY if malloc() fails when allocating the list item, or FPGA_INVALID_PARAM if the key hash produced by key_hash is out of bounds.

function opae_hash_map_destroy¶

Tear down a hash map.

fpga_result opae_hash_map_destroy (
    opae_hash_map * hm
)

Given a hash map that was previously initialized by opae_hash_map_init(), destroy the hash map, releasing all keys, values, and the bucket array.

Parameters:

hm A pointer to the storage for the hash map object.

Returns:

FPGA_OK on success or FPGA_INVALID_PARAM is hm is NULL.

function opae_hash_map_find¶

Retrieve the value for a given key.

fpga_result opae_hash_map_find (
    opae_hash_map * hm,
    void * key,
    void ** value
)

Given a key that was previously passed to opae_hash_map_add(), retrieve its associated value.

Parameters:

hm A pointer to the storage for the hash map object.
key The hash map key.
value A pointer to receive the hash map value.

Returns:

FPGA_OK on success, FPGA_INVALID_PARAM if hm is NULL or if the key hash produced by key_hash is out of bounds, or FPGA_NOT_FOUND if the given key was not found in the hash map.

function opae_hash_map_init¶

Initialize a hash map.

fpga_result opae_hash_map_init (
    opae_hash_map * hm,
    uint32_t num_buckets,
    uint32_t hash_seed,
    int flags,
    uint32_t(*)(uint32_t num_buckets, uint32_t hash_seed, void *key) key_hash,
    int(*)(void *keya, void *keyb) key_compare,
    void(*)(void *key, void *context) key_cleanup,
    void(*)(void *value, void *context) value_cleanup
)

Populates the hash map data structure and allocates the buckets array.

Parameters:

hm A pointer to the storage for the hash map object.
num_buckets The desired size of the buckets array. Each array entry may be empty (NULL), or may contain a list of opae_hash_map_item structures for which the given key_hash function returned the same key hash value.
hash_seed A seed value used during key hash computation. This value will be the hash_seed parameter to the key hash function.
flags Initialization flags. See opae_hash_map_flags.
key_hash A pointer to a function that produces the hash value, given the number of buckets, the hash seed, and the key. Valid values are between 0 and num_buckets - 1, inclusively.
key_compare A pointer to a function that compares two keys. The return value is similar to that of strcmp(), where a negative value means that keya < keyb, 0 means that keya == keyb, and a positive values means that keya > keyb.
key_cleanup A pointer to a function that is called when a key is being removed from the map. This function is optional and may be NULL. When supplied, the function is responsible for freeing any resources allocated when the key was created.
value_cleanup A pointer to a function that is called when a value is being removed from the map. This function is optional and may be NULL. When supplied, the function is responsible for freeing any resources allocated when the value was created.

Returns:

FPGA_OK on success, FPGA_INVALID_PARAM if any of the required parameters are NULL, or FPGA_NO_MEMORY if the bucket array could not be allocated.

function opae_hash_map_is_empty¶

Determine whether a hash map is empty.

bool opae_hash_map_is_empty (
    opae_hash_map * hm
)

Parameters:

hm A pointer to the storage for the hash map object.

Returns:

true if there are no key/value mappings present, false otherwise.

function opae_hash_map_remove¶

Remove a key/value association.

fpga_result opae_hash_map_remove (
    opae_hash_map * hm,
    void * key
)

Given a key that was previously passed to opae_hash_map_add(), remove the key and its associated value, calling the cleanup functions as needed.

Parameters:

hm A pointer to the storage for the hash map object.
key The hash map key.

Returns:

FPGA_OK on success, FPGA_INVALID_PARAM when hm is NULL or when the key hash produced by key_hash is out of bounds, or FPGA_NOT_FOUND if the key is not found in the hash map.

function opae_u64_key_compare¶

Convenience key comparison function for 64-bit values.

int opae_u64_key_compare (
    void * keya,
    void * keyb
)

Simply converts the key pointers to uint64_t's and performs unsigned integer comparison.

function opae_u64_key_hash¶

Convenience hash function for arbitrary pointers/64-bit values.

uint32_t opae_u64_key_hash (
    uint32_t num_buckets,
    uint32_t hash_seed,
    void * key
)

Simply converts the key to a uint64_t and then performs the modulus operation with the configured num_buckets. hash_seed is unused.

The documentation for this class was generated from the following file docs/sw/include/opae/hash_map.h