Data Structures
struct	m0_hbucket

struct	m0_htable

struct	m0_ht_descr

struct	m0_hlink

Macros
#define	M0_TRACE_SUBSYSTEM M0_TRACE_SUBSYS_LIB

#define	M0_HT_DESCR(name, amb_type, key_field, hash_func, key_eq)

#define	M0_HT_DESCR_DEFINE(name, htname, scope, amb_type, amb_link_field, amb_magic_field, amb_magic, head_magic, key_field, hash_func, key_eq)

#define	M0_HT_DESCR_DECLARE(name, scope) scope const struct m0_ht_descr name ## _ht

#define	M0_HT_DECLARE(name, scope, amb_type, key_type)

#define	M0_HT_DEFINE(name, scope, amb_type, key_type)

#define	m0_hbucket_forall(name, var, bucket, ...)

#define	m0_htable_forall(name, var, htable, ...)

#define	m0_htable_for(name, var, htable)

#define	m0_htable_endfor m0_tl_endfor; }; })

#define	m0_hbucket_for(descr, var, bucket)

#define	m0_hbucket_endfor m0_tlist_endfor; })

#define	m0_hbucket_forall_ol(descr, var, bucket, ...)

Functions
	M0_BOB_DEFINE (static, &htable_bobtype, m0_htable)

static bool	htable_invariant (const struct m0_htable *htable)

static void	hbucket_init (const struct m0_ht_descr d, struct m0_hbucket bucket)

static void	hbucket_fini (const struct m0_ht_descr d, struct m0_hbucket bucket)

static void *	obj_key (const struct m0_ht_descr hd, void obj)

static bool	hbucket_invariant (const struct m0_ht_descr desc, const struct m0_hbucket bucket, const struct m0_htable *htable)

M0_INTERNAL int	m0_htable_init (const struct m0_ht_descr d, struct m0_htable htable, uint64_t bucket_nr)

M0_INTERNAL bool	m0_htable_is_init (const struct m0_htable *htable)

M0_INTERNAL void	m0_htable_add (struct m0_htable htable, void amb)

M0_INTERNAL void	m0_htable_del (struct m0_htable htable, void amb)

M0_INTERNAL void *	m0_htable_lookup (const struct m0_htable htable, const void key)

M0_INTERNAL void	m0_htable_cc_add (struct m0_htable htable, void amb)

M0_INTERNAL void	m0_htable_cc_del (struct m0_htable htable, void amb)

M0_INTERNAL void *	m0_htable_cc_lookup (struct m0_htable htable, const void key)

M0_INTERNAL void	m0_hbucket_lock (struct m0_htable htable, const void key)

M0_INTERNAL void	m0_hbucket_unlock (struct m0_htable htable, const void key)

M0_INTERNAL void	m0_htable_fini (struct m0_htable *htable)

M0_INTERNAL bool	m0_htable_is_empty (const struct m0_htable *htable)

M0_INTERNAL uint64_t	m0_htable_size (const struct m0_htable *htable)

M0_INTERNAL uint64_t	m0_hash (uint64_t x)

Variables
static const struct m0_bob_type	htable_bobtype

Detailed Description

Hash table module provides a simple hash implementation built on top of typed lists.

See also: Typed lists..

Often, lookup for objects stored in simple tlists proves to be expensive owing to lack of any efficient arrangement of objects in tlist. Hash table provides a simple way to distribute objects in hash using a key-value mechanism, which enhances lookup time of objects.

Hash table contains array of hash buckets which contain a simple tlist of ambient objects. Every object is supposed to provide a key, based on which its location in hash table is decided. The caller is supposed to provide a hash function which is used to calculate bucket id in which object will lie.

Hash keys and ambient objects are generic (kept as void *) in hash code so as to support any type of keys and objects.

Users are encouraged to use the type-safe interfaces defined over hash table using macros like M0_HT_DEFINE().

Similar to tlists, hash table is a simple algorithmic module. It does not deal with liveness or concurrency and other such issues. Caller is supposed to control liveness and use proper synchronization primitives to handle concurrency.

A good hash function can ensure good distribution of objects throughout the hash table, thus owing to efficient operation of hash.

Consider a scenario with struct bar containing multiple objects of struct foo.

struct bar {
        ...
        // Hash table used to store multiple foo-s.
        struct m0_htable b_foohash;
        ...
};
struct foo {
        // Magic to validate sanity of object.
        uint64_t        f_magic;
        // A uint64_t Key used to find out appropriate bucket.
        uint64_t        f_hash_key;
        ...
        // hash linkage to keep foo structures as part of some list
        // in hash table.
        struct m0_hlink f_link;
};
- Define a hash function which will take care of distributing objects
  throughtout the hash buckets and the key retrieval and key equal
  functions.
  uint64_t hash_func(const struct m0_htable *htable, const void *key)
  {
          const uint64_t *k = key;
          return *k % htable->h_bucket_nr;
  }
  bool hash_key_eq(const void *key1, const void *key2)
  {
          const uint64_t *k1 = key1;
          const uint64_t *k2 = key2;
          return *k1 == *k2;
  }
- Now define hash descriptor like this.
  M0_HT_DESCR_DEFINE(foohash, "Hash of foo structures", static, struct foo,
                     f_link, f_magic, FOO_MAGIC, BAR_MAGIC, f_hash_key,
                     hash_func, hash_key_eq);
  This will take care of defining tlist descriptor internally.
  Similarly,
  M0_HT_DEFINE(foohash, static, struct foo, uint64_t);
  this will take care of defining tlist APIs internally.
- Now initialize the m0_htable like
  m0_htable_init(&foohash_tl, &bar->b_foohash, bucket_nr);
  OR
  foohash_htable_init(&bar->b_foohash, bucket_nr);
  Note that this initializes a struct that you must have previously
  defined yourself.
  For a freestanding m0_htable of type `foohash` do:
  struct m0_htable my_foohash;
  foohash_htable_init(&my_foohash, bucket_nr);
Now, foo objects can be added/removed to/from bar::b_foohash using
APIs like m0_htable_add() and m0_htable_del().
Also, lookup through hash can be done using API like m0_htable_lookup().

Macros like m0_hbucket_forall() and m0_htable_forall() can be used to evaluate a certain expression for all objects in hashbucket/hashtable.

m0_htable_for() and m0_htable_endfor() can be used to have a loop over all objects in hashtable.

Macro Definition Documentation

◆ m0_hbucket_endfor

#define m0_hbucket_endfor m0_tlist_endfor; })

Definition at line 502 of file hash.h.

◆ m0_hbucket_for

#define m0_hbucket_for	(	descr,
		var,
		bucket
	)

Value:

({ \

m0_tlist_for (descr, &bucket->hb_objects, var)

Open ended version of loop over all ambient objects in a given hash bucket. The loop has to be closed using m0_hbucket_endfor;

Definition at line 498 of file hash.h.

◆ m0_hbucket_forall

#define m0_hbucket_forall	(	name,
		var,
		bucket,
		...
	)

Value:

({                                                                          \
        typeof (bucket) __bucket = (bucket);                                \
									    \
	m0_tl_forall(name, var, &__bucket->hb_objects, ({ __VA_ARGS__ ; }));\
})

Iterates over the members of a m0_hbucket and performs given operation for all of them.

Definition at line 454 of file hash.h.

◆ m0_hbucket_forall_ol

#define m0_hbucket_forall_ol	(	descr,
		var,
		bucket,
		...
	)

Value:

({                                                                          \
        typeof(descr) d = descr;                                            \
        m0_hbucket_for (d, var, bucket) {                                   \
                if (!({ __VA_ARGS__; }))                                    \
                        break;                                              \
        } m0_hbucket_endfor;                                                \
        var == NULL;                                                        \
})

A loop which uses open ended version of hash bucket. This can be used for invariant checking.

Definition at line 508 of file hash.h.

◆ M0_HT_DECLARE

#define M0_HT_DECLARE	(	name,
		scope,
		amb_type,
		key_type
	)

Value:

\
M0_TL_DECLARE(name, scope, amb_type);                                        \
                                                                             \
scope int name ## _htable_init(struct m0_htable *htable,                     \
                               uint64_t          bucket_nr);                 \
scope void name ## _htable_add(struct m0_htable *htable, amb_type *amb);     \
scope void name ## _htable_del(struct m0_htable *htable, amb_type *amb);     \
scope amb_type *name ## _htable_lookup(const struct m0_htable *htable,       \
                                       const key_type         *key);         \
scope void name ## _htable_cc_add(struct m0_htable *htable, amb_type *amb);  \
scope void name ## _htable_cc_del(struct m0_htable *htable, amb_type *amb);  \
scope amb_type *name ## _htable_cc_lookup(struct m0_htable *htable,          \
                                          const key_type   *key);            \
scope void name ## _hbucket_lock(struct m0_htable *htable,                   \
                                 const key_type   *key);                     \
scope void name ## _hbucket_unlock(struct m0_htable *htable,                 \
                                   const key_type *key);                     \
scope void name ## _htable_fini(struct m0_htable *htable);                   \
scope bool name ## _htable_is_empty(const struct m0_htable *htable);         \
scope uint64_t name ## _htable_size(const struct m0_htable *htable);

Declares all functions of hash table which accepts ambient type and key type as input.

Definition at line 351 of file hash.h.

◆ M0_HT_DEFINE

#define M0_HT_DEFINE	(	name,
		scope,
		amb_type,
		key_type
	)

Defines all functions of hash table which accepts ambient type and key type as input.

Definition at line 377 of file hash.h.

◆ M0_HT_DESCR

#define M0_HT_DESCR	(	name,
		amb_type,
		key_field,
		hash_func,
		key_eq
	)

Value:

{                                                                       \
        .hd_tldescr    = &name ## _tl,                                  \
        .hd_key_eq     = key_eq,                                        \
        .hd_hash_func  = hash_func,                                     \
        .hd_key_offset = offsetof(amb_type, key_field),                 \
};

Defines a hashtable descriptor.

Definition at line 317 of file hash.h.

◆ M0_HT_DESCR_DECLARE

#define M0_HT_DESCR_DECLARE	(	name,
		scope
	)	scope const struct m0_ht_descr name ## _ht

Declares a hashtable descriptr with given scope.

Definition at line 344 of file hash.h.

◆ M0_HT_DESCR_DEFINE

#define M0_HT_DESCR_DEFINE	(	name,
		htname,
		scope,
		amb_type,
		amb_link_field,
		amb_magic_field,
		amb_magic,
		head_magic,
		key_field,
		hash_func,
		key_eq
	)

Value:

\
M0_BASSERT(sizeof(hash_func(NULL, &M0_FIELD_VALUE(amb_type, key_field))) > 0);\
M0_BASSERT(sizeof(key_eq(&M0_FIELD_VALUE(amb_type, key_field),          \
                         &M0_FIELD_VALUE(amb_type, key_field))) > 0);   \
									\
M0_TL_DESCR_DEFINE(name, htname, scope, amb_type, amb_link_field.hl_link,       \
                   amb_magic_field, amb_magic, head_magic);             \
                                                                        \
scope const struct m0_ht_descr name ## _ht = M0_HT_DESCR(name,          \
                                                         amb_type,      \
                                                         key_field,     \
        (uint64_t (*)(const struct m0_htable *, const void *))hash_func,\
        (bool (*)(const void *, const void *))key_eq)

Defines a hashtable descriptor with given scope.

Definition at line 326 of file hash.h.

◆ m0_htable_endfor

#define m0_htable_endfor m0_tl_endfor; }; })

Definition at line 491 of file hash.h.

◆ m0_htable_for

#define m0_htable_for	(	name,
		var,
		htable
	)

Value:

({                                                                          \
        uint64_t __cnt;                                                     \
        typeof (htable) ht = (htable);                                      \
                                                                            \
        for (__cnt = 0; __cnt < ht->h_bucket_nr; ++__cnt) {                 \
                m0_tl_for(name, &ht->h_buckets[__cnt].hb_objects, var)

An open ended version of loop over all objects in all hash buckets in a m0_htable. This loop has to be closed using m0_htable_endfor macro.

Definition at line 483 of file hash.h.

◆ m0_htable_forall

#define m0_htable_forall	(	name,
		var,
		htable,
		...
	)

Value:

({                                                                          \
        uint64_t cnt;                                                       \
        typeof (htable) ht = (htable);                                      \
                                                                            \
        for (cnt = 0; cnt < ht->h_bucket_nr; ++cnt)     {                   \
                if (!(m0_hbucket_forall(name, var, &ht->h_buckets[cnt],     \
                                         ({ __VA_ARGS__ ; }))))             \
                        break;                                              \
        }                                                                   \
        cnt == ht->h_bucket_nr;                                             \
})

Iterates over all hashbuckets and invokes m0_hbucket_forall() for all buckets.

Definition at line 465 of file hash.h.

◆ M0_TRACE_SUBSYSTEM

#define M0_TRACE_SUBSYSTEM M0_TRACE_SUBSYS_LIB

Definition at line 35 of file hash.c.

Function Documentation

◆ hbucket_fini()

static void hbucket_fini	(	const struct m0_ht_descr *	d,
		struct m0_hbucket *	bucket
	)

static

Definition at line 60 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hbucket_init()

static void hbucket_init	(	const struct m0_ht_descr *	d,
		struct m0_hbucket *	bucket
	)

static

Definition at line 50 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ hbucket_invariant()

static bool hbucket_invariant	(	const struct m0_ht_descr *	desc,
		const struct m0_hbucket *	bucket,
		const struct m0_htable *	htable
	)

static

Definition at line 75 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ htable_invariant()

static bool htable_invariant ( const struct m0_htable * htable )

static

Definition at line 92 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ M0_BOB_DEFINE()

M0_BOB_DEFINE	(	static	,
		&	htable_bobtype,
		m0_htable
	)

◆ m0_hash()

M0_INTERNAL uint64_t m0_hash ( uint64_t x )

Hash based on multiplicative cache.

Definition at line 279 of file hash.c.

Here is the caller graph for this function:

◆ m0_hbucket_lock()

M0_INTERNAL void m0_hbucket_lock	(	struct m0_htable *	htable,
		const void *	key
	)

Locks the bucket to which the key belongs.

Definition at line 215 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ m0_hbucket_unlock()

M0_INTERNAL void m0_hbucket_unlock	(	struct m0_htable *	htable,
		const void *	key
	)

Unlocks the bucket to which the key belongs.

Definition at line 226 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ m0_htable_add()

M0_INTERNAL void m0_htable_add	(	struct m0_htable *	htable,
		void *	amb
	)

Adds an object to hash table. The key must be set in object at specified location in order to identify the bucket.

Precondition: htable != NULL && amb != NULL && htable->h_buckets != NULL.

Definition at line 132 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ m0_htable_cc_add()

M0_INTERNAL void m0_htable_cc_add	(	struct m0_htable *	htable,
		void *	amb
	)

Concurrent version of m0_htable_add.

Definition at line 182 of file hash.c.

Here is the call graph for this function:

◆ m0_htable_cc_del()

M0_INTERNAL void m0_htable_cc_del	(	struct m0_htable *	htable,
		void *	amb
	)

Concurrent version of m0_htable_del.

Definition at line 192 of file hash.c.

Here is the call graph for this function:

◆ m0_htable_cc_lookup()

M0_INTERNAL void * m0_htable_cc_lookup	(	struct m0_htable *	htable,
		const void *	key
	)

Concurrent version of m0_htable_lookup.

Definition at line 202 of file hash.c.

Here is the call graph for this function:

◆ m0_htable_del()

M0_INTERNAL void m0_htable_del	(	struct m0_htable *	htable,
		void *	amb
	)

Removes an object from hash table. The key must be set in object at specified location in order to identify the bucket.

Precondition: htable != NULL && amb != NULL && htable->h_buckets != NULL.

Definition at line 150 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ m0_htable_fini()

M0_INTERNAL void m0_htable_fini ( struct m0_htable * htable )

Finalizes a struct m0_htable.

Precondition: htable != NULL && htable->h_magic == M0_LIB_HASHLIST_MAGIC && htable->h_buckets != NULL.

Postcondition: htable->buckets == NULL && htable->bucket_nr == 0.

Definition at line 237 of file hash.c.

Here is the call graph for this function:

◆ m0_htable_init()

M0_INTERNAL int m0_htable_init	(	const struct m0_ht_descr *	d,
		struct m0_htable *	htable,
		uint64_t	bucket_nr
	)

Initializes a hashtable.

Parameters

bucket_nr	Number of buckets that will be housed in this m0_htable.
d	tlist descriptor used for tlist in hash buckets.

Precondition: htable != NULL && bucket_nr > 0 && d != NULL.

Postcondition: htable->h_magic == M0_LIB_HASHLIST_MAGIC && htable->h_bucket_nr > 0 && htable->h_buckets != NULL.

Definition at line 103 of file hash.c.

Here is the call graph for this function:

◆ m0_htable_is_empty()

M0_INTERNAL bool m0_htable_is_empty ( const struct m0_htable * htable )

Returns if m0_htable contains any objects.

Definition at line 252 of file hash.c.

Here is the call graph for this function:

◆ m0_htable_is_init()

M0_INTERNAL bool m0_htable_is_init ( const struct m0_htable * htable )

Definition at line 127 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ m0_htable_lookup()

M0_INTERNAL void * m0_htable_lookup	(	const struct m0_htable *	htable,
		const void *	key
	)

Looks up if given object is present in hash table based on input key. Returns ambient object on successful lookup, returns NULL otherwise.

Precondition: d != NULL && key != NULL && htable != NULL && htable->h_buckets != NULL.

Definition at line 162 of file hash.c.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ m0_htable_size()

M0_INTERNAL uint64_t m0_htable_size ( const struct m0_htable * htable )

Returns number of objects stored within m0_htable.

Definition at line 266 of file hash.c.

Here is the call graph for this function:

◆ obj_key()

static void* obj_key	(	const struct m0_ht_descr *	hd,
		void *	obj
	)

static

Definition at line 70 of file hash.c.

Here is the caller graph for this function:

Variable Documentation

◆ htable_bobtype

static const struct m0_bob_type htable_bobtype

static

Initial value:

= {
        .bt_name         = "hashtable",
        .bt_magix_offset = offsetof(struct m0_htable, h_magic),
        .bt_magix        = M0_LIB_HASHLIST_MAGIC,
        .bt_check        = NULL,
}

Definition at line 38 of file hash.c.

Data Structures

Macros

Functions

Variables

Detailed Description

Macro Definition Documentation

◆ m0_hbucket_endfor

◆ m0_hbucket_for

◆ m0_hbucket_forall

◆ m0_hbucket_forall_ol

◆ M0_HT_DECLARE

◆ M0_HT_DEFINE

◆ M0_HT_DESCR

◆ M0_HT_DESCR_DECLARE

◆ M0_HT_DESCR_DEFINE

◆ m0_htable_endfor

◆ m0_htable_for

◆ m0_htable_forall

◆ M0_TRACE_SUBSYSTEM

Function Documentation

◆ hbucket_fini()

◆ hbucket_init()

◆ hbucket_invariant()

◆ htable_invariant()

◆ M0_BOB_DEFINE()

◆ m0_hash()

◆ m0_hbucket_lock()

◆ m0_hbucket_unlock()

◆ m0_htable_add()

◆ m0_htable_cc_add()

◆ m0_htable_cc_del()

◆ m0_htable_cc_lookup()

◆ m0_htable_del()

◆ m0_htable_fini()

◆ m0_htable_init()

◆ m0_htable_is_empty()

◆ m0_htable_is_init()

◆ m0_htable_lookup()

◆ m0_htable_size()

◆ obj_key()

Variable Documentation

◆ htable_bobtype