list.h File Reference

#include "basic.h"
#include "buffer.h"

Include dependency graph for list.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures
struct	hash_element
struct	hash_bucket
struct	hash
struct	hash_iterator

Macros
#define	HASH_KEY_LEN   16

Functions
struct hash *	hash_init (const uint32_t n_buckets, uint64_t(*hash_function)(const void *key, const uint8_t hash_key[HASH_KEY_LEN]), bool(*compare_function)(const void *key1, const void *key2))
void	hash_free (struct hash *hash)
bool	hash_add (struct hash *hash, const void *key, void *value, bool replace)
struct hash_element *	hash_lookup_fast (struct hash *hash, struct hash_bucket *bucket, const void *key, uint64_t hv)
bool	hash_remove_fast (struct hash *hash, struct hash_bucket *bucket, const void *key, uint64_t hv)
void	hash_remove_by_value (struct hash *hash, const void *value)
void	hash_iterator_init_range (struct hash *hash, struct hash_iterator *hi, uint32_t start_bucket, uint32_t end_bucket)
void	hash_iterator_init (struct hash *hash, struct hash_iterator *iter)
struct hash_element *	hash_iterator_next (struct hash_iterator *hi)
void	hash_iterator_delete_element (struct hash_iterator *hi)
void	hash_iterator_free (struct hash_iterator *hi)
static uint64_t	hash_value (const struct hash *hash, const void *key)
static uint32_t	hash_n_elements (const struct hash *hash)
static uint32_t	hash_n_buckets (const struct hash *hash)
static struct hash_bucket *	hash_bucket (struct hash *hash, uint64_t hv)
static void *	hash_lookup (struct hash *hash, const void *key)
static void	hash_add_fast (struct hash *hash, struct hash_bucket *bucket, const void *key, uint64_t hv, void *value)
static bool	hash_remove (struct hash *hash, const void *key)

Macro Definition Documentation

HASH_KEY_LEN

#define HASH_KEY_LEN   16

Definition at line 53 of file list.h.

Referenced by cid_hash_function(), hash_init(), mroute_addr_hash_function(), session_id_hash_function(), and word_hash_function().

Function Documentation

hash_add()

bool hash_add	(	struct hash *	hash,
		const void *	key,
		void *	value,
		bool	replace )

Definition at line 139 of file list.c.

References hash::buckets, hash_add_fast(), hash_lookup_fast(), hash_value(), hash::mask, and hash_element::value.

Referenced by multi_client_connect_real_addr(), multi_create_instance(), multi_process_float(), and test_list().

hash_add_fast()

void hash_add_fast ( struct hash * hash, struct hash_bucket * bucket, const void * key, uint64_t hv, void * value )

inlinestatic

Definition at line 149 of file list.h.

References ALLOC_OBJ, hash_element::hash_value, hash_element::key, hash_bucket::list, hash::n_elements, hash_element::next, and hash_element::value.

Referenced by hash_add(), multi_hash_sid_add(), and multi_learn_addr().

hash_bucket()

struct hash_bucket * hash_bucket ( struct hash * hash, uint64_t hv )

inlinestatic

Definition at line 125 of file list.h.

References hash::buckets, and hash::mask.

Referenced by multi_check_dest_addr_allowed(), multi_get_instance_udp_real(), multi_hash_sid_add(), multi_hash_sid_lookup(), multi_hash_sid_remove(), multi_learn_addr(), and multi_unlearn_addr().

hash_free()

void hash_free

(

struct hash *

hash

)

Definition at line 62 of file list.c.

References hash::buckets, hash_bucket::list, hash::n_buckets, and hash_element::next.

Referenced by multi_uninit(), test_list(), and test_sid_hash_list().

hash_init()

struct hash * hash_init	(	const uint32_t	n_buckets,
		uint64_t(*	hash_function )(const void *key, const uint8_t hash_key[HASH_KEY_LEN]),
		bool(*	compare_function )(const void *key1, const void *key2) )

Definition at line 36 of file list.c.

References adjust_power_of_2(), ALLOC_ARRAY, ALLOC_OBJ_CLEAR, ASSERT, hash::buckets, hash::compare_function, hash::hash_function, hash::hash_key, HASH_KEY_LEN, hash_bucket::list, hash::mask, hash::n_buckets, and prng_bytes().

Referenced by multi_init(), test_list(), and test_sid_hash_list().

hash_iterator_delete_element()

void hash_iterator_delete_element

(

struct hash_iterator *

hi

)

Definition at line 310 of file list.c.

References ASSERT, hash_iterator::bucket_marked, hash_element::key, and hash_iterator::last.

Referenced by check_stale_routes(), hash_remove_by_value(), and multi_reap_range().

hash_iterator_free()

void hash_iterator_free

(

struct hash_iterator *

hi

)

Definition at line 272 of file list.c.

References hash_iterator_unlock().

Referenced by check_stale_routes(), hash_lookup_by_value(), hash_remove_by_value(), management_check_bytecount_server(), multi_print_status(), multi_reap_range(), and test_list().

hash_iterator_init()

void hash_iterator_init	(	struct hash *	hash,
		struct hash_iterator *	iter )

Definition at line 236 of file list.c.

References hash_iterator_init_range(), and hash::n_buckets.

Referenced by hash_lookup_by_value(), hash_remove_by_value(), management_check_bytecount_server(), and multi_print_status().

hash_iterator_init_range()

void hash_iterator_init_range	(	struct hash *	hash,
		struct hash_iterator *	hi,
		uint32_t	start_bucket,
		uint32_t	end_bucket )

Definition at line 215 of file list.c.

References ASSERT, hash_iterator::bucket, hash_iterator::bucket_index, hash_iterator::bucket_index_end, hash_iterator::bucket_index_start, hash_iterator::bucket_marked, hash_iterator::elem, hash_iterator::hash, hash_iterator::last, and hash::n_buckets.

Referenced by check_stale_routes(), hash_iterator_init(), multi_reap_range(), and test_list().

hash_iterator_next()

struct hash_element * hash_iterator_next

(

struct hash_iterator *

hi

)

Definition at line 278 of file list.c.

References hash_iterator::bucket_index, hash_iterator::bucket_index_end, hash::buckets, hash_iterator::elem, hash_iterator::hash, hash_iterator_advance(), hash_iterator_lock(), hash_iterator_unlock(), and hash_bucket::list.

Referenced by check_stale_routes(), hash_lookup_by_value(), hash_remove_by_value(), management_check_bytecount_server(), multi_print_status(), multi_reap_range(), and test_list().

hash_lookup()

void * hash_lookup ( struct hash * hash, const void * key )

inlinestatic

Definition at line 131 of file list.h.

References hash::buckets, hash_lookup_fast(), hash_value(), hash::mask, and hash_element::value.

Referenced by lookup_by_cid(), multi_get_instance_by_virtual_addr(), and test_list().

hash_lookup_fast()

struct hash_element * hash_lookup_fast	(	struct hash *	hash,
		struct hash_bucket *	bucket,
		const void *	key,
		uint64_t	hv )

Definition at line 81 of file list.c.

References hash::compare_function, hash_element::hash_value, hash_element::key, hash_bucket::list, and hash_element::next.

Referenced by hash_add(), hash_lookup(), multi_check_dest_addr_allowed(), multi_get_instance_udp_real(), multi_hash_sid_lookup(), multi_hash_sid_remove(), multi_learn_addr(), and multi_unlearn_addr().

hash_n_buckets()

uint32_t hash_n_buckets ( const struct hash * hash )

inlinestatic

Definition at line 119 of file list.h.

References hash::n_buckets.

Referenced by check_stale_routes(), multi_reap_all(), multi_reap_process_dowork(), and test_list().

hash_n_elements()

uint32_t hash_n_elements ( const struct hash * hash )

inlinestatic

Definition at line 113 of file list.h.

References hash::n_elements.

Referenced by multi_print_status(), and test_list().

hash_remove()

bool hash_remove ( struct hash * hash, const void * key )

inlinestatic

Definition at line 164 of file list.h.

References hash::buckets, hash_remove_fast(), hash_value(), and hash::mask.

Referenced by multi_close_instance(), multi_process_float(), and test_list().

hash_remove_by_value()

void hash_remove_by_value	(	struct hash *	hash,
		const void *	value )

Definition at line 167 of file list.c.

References hash_iterator_delete_element(), hash_iterator_free(), hash_iterator_init(), hash_iterator_next(), and hash_element::value.

Referenced by multi_unlearn_addr(), and test_list().

hash_remove_fast()

bool hash_remove_fast	(	struct hash *	hash,
		struct hash_bucket *	bucket,
		const void *	key,
		uint64_t	hv )

Definition at line 109 of file list.c.

References hash::compare_function, hash_element::hash_value, hash_element::key, hash_bucket::list, hash::n_elements, and hash_element::next.

Referenced by hash_remove(), and multi_hash_sid_remove().

hash_value()

uint64_t hash_value ( const struct hash * hash, const void * key )

inlinestatic

Definition at line 107 of file list.h.

References hash::hash_function, and hash::hash_key.

Referenced by hash_add(), hash_lookup(), hash_remove(), multi_check_dest_addr_allowed(), multi_get_instance_udp_real(), multi_hash_sid_add(), multi_hash_sid_lookup(), multi_hash_sid_remove(), multi_learn_addr(), and multi_unlearn_addr().