napr_hash.c File Reference

Implementation of the high-performance hash table. More...

#include "debug.h"
#include "napr_hash.h"
#include "xxhash.h"

Include dependency graph for napr_hash.c:

Go to the source code of this file.

Functions
napr_hash_t *	napr_hash_str_make (apr_pool_t *pool, apr_size_t nel, apr_size_t ffactor)
	Create a hash table optimized for storing C strings as keys.
napr_hash_t *	napr_hash_make (apr_pool_t *pool, apr_size_t nel, apr_size_t ffactor, get_key_callback_fn_t get_key, get_key_len_callback_fn_t get_key_len, key_cmp_callback_fn_t key_cmp, hash_callback_fn_t hash)
	Create a hash table with custom key handling and hashing functions.
void *	napr_hash_search (napr_hash_t *hash, const void *key, apr_size_t key_len, apr_uint32_t *hash_value)
	Searches the hash table for an item.
void	napr_hash_remove (napr_hash_t *hash, void *data, apr_uint32_t hash_value)
	Removes an item from the hash table.
apr_status_t	napr_hash_set (napr_hash_t *hash, void *data, apr_uint32_t hash_value)
	Inserts or updates an item in the hash table.
apr_pool_t *	napr_hash_pool_get (const napr_hash_t *thehash)
	Get a pointer to the pool from which the hash table was allocated.
napr_hash_index_t *	napr_hash_first (apr_pool_t *pool, napr_hash_t *hash)
	Start iterating over the entries in a hash table.
napr_hash_index_t *	napr_hash_next (napr_hash_index_t *index)
	Continue iterating over the entries in a hash table.
void	napr_hash_this (napr_hash_index_t *hi, const void **key, apr_size_t *klen, void **val)
	Get the current entry's details from the iteration state.

Detailed Description

Implementation of the high-performance hash table.

Definition in file napr_hash.c.

Function Documentation

napr_hash_first()

napr_hash_index_t * napr_hash_first	(	apr_pool_t *	pool,
		napr_hash_t *	hash
	)

Start iterating over the entries in a hash table.

Parameters

[in]	pool	The pool to allocate the iterator from. If NULL, a non-thread-safe internal iterator is used.
[in]	hash	The hash table to iterate over.

Returns

A pointer to the iterator.

Remarks

There is no restriction on adding or deleting hash entries during an iteration, but the results may be unpredictable unless only deleting the current entry.

napr_hash_index_t *hi;
void *val;
for (hi = napr_hash_first(p, ht); hi; hi = napr_hash_next(hi)) {
    napr_hash_this(hi, NULL, NULL, &val);
    // process val
}

Definition at line 280 of file napr_hash.c.

References napr_hash_next().

Here is the call graph for this function:

napr_hash_make()

napr_hash_t * napr_hash_make ( apr_pool_t *  pool, apr_size_t  nel, apr_size_t  ffactor, get_key_callback_fn_t  get_key, get_key_len_callback_fn_t  get_key_len, key_cmp_callback_fn_t  key_cmp, hash_callback_fn_t  hash  )

extern

Create a hash table with custom key handling and hashing functions.

Parameters

[in]	pool	The pool to allocate the hash table from.
[in]	nel	The desired number of pre-allocated buckets (will be rounded up to the next power of 2).
[in]	ffactor	The maximum number of collisions for a given key before resizing.
[in]	get_key	A callback to extract the key from a data item.
[in]	get_key_len	A callback to get the length of the key.
[in]	key_cmp	A callback to compare two keys.
[in]	hash	A callback to compute the hash of a key.

Returns

A pointer to the newly created hash table.

Definition at line 100 of file napr_hash.c.

References DEBUG_ERR.

Referenced by napr_hash_str_make().

Here is the caller graph for this function:

napr_hash_next()

napr_hash_index_t * napr_hash_next

(

napr_hash_index_t *

index

)

Continue iterating over the entries in a hash table.

Parameters

[in]

index

The current iteration state.

Returns

A pointer to the next iteration state, or NULL if there are no more entries.

Definition at line 294 of file napr_hash.c.

Referenced by napr_hash_first().

Here is the caller graph for this function:

napr_hash_pool_get()

apr_pool_t * napr_hash_pool_get

(

const napr_hash_t *

thehash

)

Get a pointer to the pool from which the hash table was allocated.

Parameters

[in]

thehash

The hash table.

Returns

The APR pool.

Definition at line 275 of file napr_hash.c.

napr_hash_remove()

void napr_hash_remove ( napr_hash_t *  hash, void *  data, apr_uint32_t  hash_value  )

extern

Removes an item from the hash table.

Parameters

[in]	hash	The hash table.
[in]	data	The data item to remove.
[in]	hash_value	The pre-computed hash of the item's key.

Definition at line 210 of file napr_hash.c.

References DEBUG_DBG.

napr_hash_search()

void * napr_hash_search ( napr_hash_t *  hash, const void *  key, apr_size_t  key_len, apr_uint32_t *  hash_value  )

extern

Searches the hash table for an item.

Parameters

[in]	hash	The hash table to search.
[in]	key	The key to search for.
[in]	key_len	The length of the key.
[out]	hash_value	A pointer to store the computed hash of the key. Can be NULL.

Returns

A pointer to the found data item, or NULL if not found. If an item is not found, the computed hash value is stored in hash_value for efficient subsequent insertion.

Definition at line 145 of file napr_hash.c.

Referenced by ft_report_duplicates(), and ft_report_json().

Here is the caller graph for this function:

napr_hash_set()

apr_status_t napr_hash_set ( napr_hash_t *  hash, void *  data, apr_uint32_t  hash_value  )

extern

Inserts or updates an item in the hash table.

Parameters

[in]	hash	The hash table.
[in]	data	The data item to insert.
[in]	hash_value	The pre-computed hash of the item's key.

Returns

APR_SUCCESS on success.

Definition at line 242 of file napr_hash.c.

References DEBUG_ERR.

napr_hash_str_make()

napr_hash_t * napr_hash_str_make ( apr_pool_t *  pool, apr_size_t  nel, apr_size_t  ffactor  )

extern

Create a hash table optimized for storing C strings as keys.

Parameters

[in]	pool	The pool to allocate the hash table from.
[in]	nel	The desired number of pre-allocated buckets.
[in]	ffactor	The maximum number of collisions for a given key.

Returns

A pointer to the newly created string-keyed hash table.

Definition at line 95 of file napr_hash.c.

References napr_hash_make().

Here is the call graph for this function:

napr_hash_this()

void napr_hash_this	(	napr_hash_index_t *	hi,
		const void **	key,
		apr_size_t *	klen,
		void **	val
	)

Get the current entry's details from the iteration state.

Parameters

[in]	hi	The iteration state.
[out]	key	Pointer to store the key. Can be NULL.
[out]	klen	Pointer to store the key length. Can be NULL.
[out]	val	Pointer to store the value (the data item). Can be NULL.

Definition at line 314 of file napr_hash.c.