Loading...
Searching...
No Matches
hash_table.h File Reference

libyang hash table More...

`#include <stddef.h>`
`#include <stdint.h>`
`#include "log.h"`
Include dependency graph for hash_table.h:

Go to the source code of this file.

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

## Functions

LIBYANG_API_DECL struct ly_ht * | lyht_dup (const struct ly_ht *orig)
| Make a duplicate of an existing hash table.
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.
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.
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.
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.
LIBYANG_API_DECL void | lyht_free (struct ly_ht *ht, void(*val_free)(void *val_p))
| Free a hash table.
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.
LIBYANG_API_DECL uint32_t | lyht_hash (const char *key, size_t len)
| Compute hash from a string.
LIBYANG_API_DECL uint32_t | lyht_hash_multi (uint32_t hash, const char *key_part, size_t len)
| Compute hash from (several) string(s).
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.
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.
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.
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.
LIBYANG_API_DECL LY_ERR | lyht_remove (struct ly_ht *ht, void *val_p, uint32_t hash)
| Remove a value from a hash table.
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.
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.
LIBYANG_API_DECL void * | lyht_set_cb_data (struct ly_ht *ht, void *new_cb_data)
| Set hash table value equal callback user data.

## 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

## lyht_value_equal_cb

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 74 of file hash_table.h.

## Function Documentation

## lyht_dup()

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.

## lyht_find()

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.

## lyht_find_next()

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.

## lyht_find_next_with_collision_cb()

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.

## lyht_find_with_val_cb()

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.

## lyht_free()

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

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.

## lyht_get_fixed_size()

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.

## lyht_hash()

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.

Uses XXH3_64bits internally if xxhash is available. See https://xxhash.com

Parameters

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

Returns
  Hash of the key.

## lyht_hash_multi()

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.

## lyht_insert()

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.

## lyht_insert_no_check()

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.

## lyht_insert_with_resize_cb()

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.

## lyht_new()

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.

## lyht_remove()

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.

## lyht_remove_with_resize_cb()

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.

## lyht_set_cb()

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.

## lyht_set_cb_data()

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.