libyang hash table More...

#include <stddef.h>
#include <stdint.h>
#include "log.h"

Include dependency graph for hash_table.h:

Typedefs
typedef ly_bool(*	lyht_value_equal_cb )(void val1_p, void val2_p, ly_bool mod, void *cb_data)
	Callback for checking hash table values equivalence. More...

Functions
LIBYANG_API_DECL struct ly_ht *	lyht_dup (const struct ly_ht *orig)
	Make a duplicate of an existing hash table. More...

LIBYANG_API_DECL LY_ERR	lyht_find (const struct ly_ht ht, void val_p, uint32_t hash, void **match_p)
	Find a value in a hash table. More...

LIBYANG_API_DECL LY_ERR	lyht_find_next (const struct ly_ht ht, void val_p, uint32_t hash, void **match_p)
	Find another equal value in the hash table. More...

LIBYANG_API_DECL LY_ERR	lyht_find_next_with_collision_cb (const struct ly_ht ht, void val_p, uint32_t hash, lyht_value_equal_cb val_equal, void **match_p)
	Find another equal value in the hash table. Same functionality as lyht_find_next() but allows to specify a collision val equal callback to be used for checking for matching colliding values. More...

LIBYANG_API_DECL LY_ERR	lyht_find_with_val_cb (const struct ly_ht ht, void val_p, uint32_t hash, lyht_value_equal_cb val_equal, void **match_p)
	Find a value in a hash table but use a custom val_equal callback. More...

LIBYANG_API_DECL void	lyht_free (struct ly_ht ht, void(val_free)(void *val_p))
	Free a hash table. More...

LIBYANG_API_DECL uint32_t	lyht_get_fixed_size (uint32_t item_count)
	Get suitable size of a hash table for a fixed number of items. More...

LIBYANG_API_DECL uint32_t	lyht_hash (const char *key, size_t len)
	Compute hash from a string. More...

LIBYANG_API_DECL uint32_t	lyht_hash_multi (uint32_t hash, const char *key_part, size_t len)
	Compute hash from (several) string(s). More...

LIBYANG_API_DECL LY_ERR	lyht_insert (struct ly_ht ht, void val_p, uint32_t hash, void **match_p)
	Insert a value into a hash table. More...

LIBYANG_API_DECL LY_ERR	lyht_insert_no_check (struct ly_ht ht, void val_p, uint32_t hash, void **match_p)
	Insert a value into a hash table, without checking whether the value has already been inserted. More...

LIBYANG_API_DECL LY_ERR	lyht_insert_with_resize_cb (struct ly_ht ht, void val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal, void **match_p)
	Insert a value into hash table. Same functionality as lyht_insert() but allows to specify a temporary val equal callback to be used in case the hash table will be resized after successful insertion. More...

LIBYANG_API_DECL struct ly_ht *	lyht_new (uint32_t size, uint16_t val_size, lyht_value_equal_cb val_equal, void *cb_data, uint16_t resize)
	Create new hash table. More...

LIBYANG_API_DECL LY_ERR	lyht_remove (struct ly_ht ht, void val_p, uint32_t hash)
	Remove a value from a hash table. More...

LIBYANG_API_DECL LY_ERR	lyht_remove_with_resize_cb (struct ly_ht ht, void val_p, uint32_t hash, lyht_value_equal_cb resize_val_equal)
	Remove a value from a hash table. Same functionality as lyht_remove() but allows to specify a temporary val equal callback to be used in case the hash table will be resized after successful removal. More...

LIBYANG_API_DECL lyht_value_equal_cb	lyht_set_cb (struct ly_ht *ht, lyht_value_equal_cb new_val_equal)
	Set hash table value equal callback. More...

LIBYANG_API_DECL void *	lyht_set_cb_data (struct ly_ht ht, void new_cb_data)
	Set hash table value equal callback user data. More...

Detailed Description

libyang hash table

Author: Radek Krejci rkrej.nosp@m.ci@c.nosp@m.esnet.nosp@m..cz; Michal Vasko mvask.nosp@m.o@ce.nosp@m.snet..nosp@m.cz Copyright (c) 2015 - 2023 CESNET, z.s.p.o.

This source code is licensed under BSD 3-Clause License (the "License"). You may not use this file except in compliance with the License. You may obtain a copy of the License at

https://opensource.org/licenses/BSD-3-Clause

Definition in file hash_table.h.

Typedef Documentation

typedef ly_bool(* lyht_value_equal_cb)(void *val1_p, void *val2_p, ly_bool mod, void *cb_data)

Callback for checking hash table values equivalence.

Parameters

[in]	val1_p	Pointer to the first value, the one being searched (inserted/removed).
[in]	val2_p	Pointer to the second value, the one stored in the hash table.
[in]	mod	Whether the operation modifies the hash table (insert or remove) or not (find).
[in]	cb_data	User callback data.

Returns: false (non-equal) or true (equal).

Definition at line 72 of file hash_table.h.

Function Documentation

LIBYANG_API_DECL struct ly_ht* lyht_dup ( const struct ly_ht * orig )

Make a duplicate of an existing hash table.

Parameters

[in] orig Original hash table to duplicate.

Returns: Duplicated hash table orig, NULL on error.

LIBYANG_API_DECL LY_ERR lyht_find	(	const struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		void **	match_p
	)

Find a value in a hash table.

Parameters

[in]	ht	Hash table to search in.
[in]	val_p	Pointer to the value to find.
[in]	hash	Hash of the stored value.
[out]	match_p	Pointer to the matching value, optional.

Returns: LY_SUCCESS if value was found,; LY_ENOTFOUND if not found.

LIBYANG_API_DECL LY_ERR lyht_find_next	(	const struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		void **	match_p
	)

Find another equal value in the hash table.

Parameters

[in]	ht	Hash table to search in.
[in]	val_p	Pointer to the previously found value in `ht`.
[in]	hash	Hash of the previously found value.
[out]	match_p	Pointer to the matching value, optional.

Returns: LY_SUCCESS if value was found,; LY_ENOTFOUND if not found.

LIBYANG_API_DECL LY_ERR lyht_find_next_with_collision_cb	(	const struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		lyht_value_equal_cb	val_equal,
		void **	match_p
	)

Find another equal value in the hash table. Same functionality as lyht_find_next() but allows to specify a collision val equal callback to be used for checking for matching colliding values.

Parameters

[in]	ht	Hash table to search in.
[in]	val_p	Pointer to the previously found value in `ht`.
[in]	hash	Hash of the previously found value.
[in]	val_equal	Callback for checking value equivalence. Called with `mod` 1 when searching for the first value and then uses `mod` 0 to check all the following collisions.
[out]	match_p	Pointer to the matching value, optional.

Returns: LY_SUCCESS if value was found,; LY_ENOTFOUND if not found.

LIBYANG_API_DECL LY_ERR lyht_find_with_val_cb	(	const struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		lyht_value_equal_cb	val_equal,
		void **	match_p
	)

Find a value in a hash table but use a custom val_equal callback.

Parameters

[in]	ht	Hash table to search in.
[in]	val_p	Pointer to the value to find.
[in]	hash	Hash of the stored value.
[in]	val_equal	Callback for checking value equivalence.
[out]	match_p	Pointer to the matching value, optional.

Returns: LY_SUCCESS if value was found,; LY_ENOTFOUND if not found.

LIBYANG_API_DECL void lyht_free	(	struct ly_ht *	ht,
		void()(void val_p)	val_free
	)

Free a hash table.

Parameters

[in]	ht	Hash table to be freed.
[in]	val_free	Optional callback for freeing all the stored values, `val_p` is a pointer to a stored value.

LIBYANG_API_DECL uint32_t lyht_get_fixed_size ( uint32_t item_count )

Get suitable size of a hash table for a fixed number of items.

Parameters

[in] item_count Number of stored items.

Returns: Hash table size.

LIBYANG_API_DECL uint32_t lyht_hash	(	const char *	key,
		size_t	len
	)

Compute hash from a string.

Bob Jenkin's one-at-a-time hash http://www.burtleburtle.net/bob/hash/doobs.html

Spooky hash is faster, but it works only for little endian architectures.

Parameters

[in]	key	Key to hash.
[in]	len	Length of `key`.

Returns: Hash of the key.

LIBYANG_API_DECL uint32_t lyht_hash_multi	(	uint32_t	hash,
		const char *	key_part,
		size_t	len
	)

Compute hash from (several) string(s).

Usage:

init hash to 0
repeatedly call lyht_hash_multi(), provide hash from the last call
call lyht_hash_multi() with key_part = NULL to finish the hash

Parameters

[in]	hash	Previous hash.
[in]	key_part	Next key to hash,
[in]	len	Length of `key_part`.

Returns: Hash with the next key.

LIBYANG_API_DECL LY_ERR lyht_insert	(	struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		void **	match_p
	)

Insert a value into a hash table.

Parameters

[in]	ht	Hash table to insert into.
[in]	val_p	Pointer to the value to insert. Be careful, if the values stored in the hash table are pointers, `val_p` must be a pointer to a pointer.
[in]	hash	Hash of the stored value.
[out]	match_p	Pointer to the stored value, optional

Returns: LY_SUCCESS on success,; LY_EEXIST in case the value is already present.; LY_EMEM in case of memory allocation failure.

LIBYANG_API_DECL LY_ERR lyht_insert_no_check	(	struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		void **	match_p
	)

Insert a value into a hash table, without checking whether the value has already been inserted.

Parameters

[in]	ht	Hash table to insert into.
[in]	val_p	Pointer to the value to insert. Be careful, if the values stored in the hash table are pointers, `val_p` must be a pointer to a pointer.
[in]	hash	Hash of the stored value.
[out]	match_p	Pointer to the stored value, optional

Returns: LY_SUCCESS on success,; LY_EMEM in case of memory allocation failure.

LIBYANG_API_DECL LY_ERR lyht_insert_with_resize_cb	(	struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		lyht_value_equal_cb	resize_val_equal,
		void **	match_p
	)

Insert a value into hash table. Same functionality as lyht_insert() but allows to specify a temporary val equal callback to be used in case the hash table will be resized after successful insertion.

Parameters

[in]	ht	Hash table to insert into.
[in]	val_p	Pointer to the value to insert. Be careful, if the values stored in the hash table are pointers, `val_p` must be a pointer to a pointer.
[in]	hash	Hash of the stored value.
[in]	resize_val_equal	Val equal callback to use for resizing.
[out]	match_p	Pointer to the stored value, optional

Returns: LY_SUCCESS on success,; LY_EEXIST in case the value is already present.; LY_EMEM in case of memory allocation failure.

LIBYANG_API_DECL struct ly_ht* lyht_new	(	uint32_t	size,
		uint16_t	val_size,
		lyht_value_equal_cb	val_equal,
		void *	cb_data,
		uint16_t	resize
	)

Create new hash table.

Parameters

[in]	size	Starting size of the hash table (capacity of values), must be power of 2.
[in]	val_size	Size in bytes of value (the stored hashed item).
[in]	val_equal	Callback for checking value equivalence.
[in]	cb_data	User data always passed to `val_equal`.
[in]	resize	Whether to resize the table on too few/too many records taken.

Returns: Empty hash table, NULL on error.

LIBYANG_API_DECL LY_ERR lyht_remove	(	struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash
	)

Remove a value from a hash table.

Parameters

[in]	ht	Hash table to remove from.
[in]	val_p	Pointer to value to be removed. Be careful, if the values stored in the hash table are pointers, `val_p` must be a pointer to a pointer.
[in]	hash	Hash of the stored value.

Returns: LY_SUCCESS on success,; LY_ENOTFOUND if value was not found.

LIBYANG_API_DECL LY_ERR lyht_remove_with_resize_cb	(	struct ly_ht *	ht,
		void *	val_p,
		uint32_t	hash,
		lyht_value_equal_cb	resize_val_equal
	)

Remove a value from a hash table. Same functionality as lyht_remove() but allows to specify a temporary val equal callback to be used in case the hash table will be resized after successful removal.

Parameters

[in]	ht	Hash table to remove from.
[in]	val_p	Pointer to value to be removed. Be careful, if the values stored in the hash table are pointers, `val_p` must be a pointer to a pointer.
[in]	hash	Hash of the stored value.
[in]	resize_val_equal	Val equal callback to use for resizing.

Returns: LY_SUCCESS on success,; LY_ENOTFOUND if value was not found.

LIBYANG_API_DECL lyht_value_equal_cb lyht_set_cb	(	struct ly_ht *	ht,
		lyht_value_equal_cb	new_val_equal
	)

Set hash table value equal callback.

Parameters

[in]	ht	Hash table to modify.
[in]	new_val_equal	New callback for checking value equivalence.

Returns: Previous callback for checking value equivalence.

LIBYANG_API_DECL void* lyht_set_cb_data	(	struct ly_ht *	ht,
		void *	new_cb_data
	)

Set hash table value equal callback user data.

Parameters

[in]	ht	Hash table to modify.
[in]	new_cb_data	New data for values callback.

Returns: Previous data for values callback.

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation