Linear probing hashing primitives

Primitives for linear probing hash tables. More...

Collaboration diagram for Linear probing hashing primitives:

Macros
#define	csnip_lphash_Find(N, keytype, k, u, hash, is_empty, is_match, get_key, key, return_loc, return_state)
	Find a slot matching the key or an insertion position. More...
#define	csnip_lphash_Findnext(N, keytype, k, u, hash, is_empty, is_match, get_key, key, loc_prev, ret_loc, ret_state)
	Find the next match. More...
#define	csnip_lphash_Delete(N, keytype, k, u, v, hash, is_empty, get_key, copy, clear, loc)
	Delete an entry in the hash table. More...
#define	csnip_lphash_Nextentry(N, u, is_empty, loc, ret)
	Find the next occupied slot. More...
#define	CSNIP_LPHASH_DECL_FUNCS(scope, prefix, keytype, argl)
	Declare lphash function prototypes. More...
#define	CSNIP_LPHASH_DEF_FUNCS(scope, prefix, argl, N, keytype, k, u, v, hash, is_empty, is_match, get_key, copy, clear)
	Define lphash functions. More...

Detailed Description

These are low level macros aiding for the implementation of hash tables. In most cases, it will be more convenient to use a higher level implementation of hash tables such as the one from lphash_table.h.

Macro Definition Documentation

CSNIP_LPHASH_DECL_FUNCS

#define CSNIP_LPHASH_DECL_FUNCS	(		scope,
			prefix,
			keytype,
			argl
	)

Declares functions for the above macros. See CSNIP_LPHASH_DEF_FUNCS() for further details.

CSNIP_LPHASH_DEF_FUNCS

#define CSNIP_LPHASH_DEF_FUNCS	(		scope,
			prefix,
			argl,
			N,
			keytype,
			k,
			u,
			v,
			hash,
			is_empty,
			is_match,
			get_key,
			copy,
			clear
	)

The functions defined will be (without prefixes):

• findloc, a version of csnip_lphash_Find() wrapped in a function.
• findnextloc, a version of csnip_lphash_Findnext() wrapped in a function.
• deleteloc, a version of csnip_lphash_Delete() wrapped in a function.
• nextentry, a version of csnip_lphash_Nextentry() wrapped in a function.

csnip_lphash_Delete

#define csnip_lphash_Delete	(		N,
			keytype,
			k,
			u,
			v,
			hash,
			is_empty,
			get_key,
			copy,
			clear,
			loc
	)

Parameters

N	table capacity
keytype	key data type
k,u,v	dummy variables
hash	hashing expression
is_empty	empty slot check expression
get_key	slot key retrieval expression
copy	slot copy expression
clear	slot clear expression
loc	the location to delete

csnip_lphash_Find

#define csnip_lphash_Find	(		N,
			keytype,
			k,
			u,
			hash,
			is_empty,
			is_match,
			get_key,
			key,
			return_loc,
			return_state
	)

If there is a slot matching the key, then its location is returned in return_loc, and return_state will be 0.

If there is no such slot, and the table is not full, return_loc contains the appropriate location where a new entry with the given key can be inserted. In this case, return_state will be 1.

Finally, if no slot matching the key is present in the table, and the table is completely full so that no insertion point is present either, the return_state will be 2.

Table description:

Parameters

N	table capacity
keytype	key data type
k,u	dummy variables.
hash	hashing expression.
is_empty	empty slot check expression.
is_match	slot match expression.
get_key	slot key retrieval expression.

Table lookup parameters:

Parameters

[in]	key	key to look up.
[out]	return_loc	lvalue to assign the returned location to.
[out]	return_state	lvalue to return the state. Value Meaning 0 found, return_loc contains the location 1 not found, return_loc contains an insertion location 2 not found and table completely full.

csnip_lphash_Findnext

#define csnip_lphash_Findnext	(		N,
			keytype,
			k,
			u,
			hash,
			is_empty,
			is_match,
			get_key,
			key,
			loc_prev,
			ret_loc,
			ret_state
	)

Find next entry matching the key or an insertion point for the key; loc_prev points to the current match.

Parameters

N	table capacity
keytype	key data type
k,u	dummy variables
hash	hashing expression
is_empty	empty slot check expression
is_match	slot match expression
get_key	slot key retrieval expression
key	key to look up
loc_prev	previous match location
ret_loc	target return location
ret_state	target return state

csnip_lphash_Nextentry

#define csnip_lphash_Nextentry	(		N,
			u,
			is_empty,
			loc,
			ret
	)

This finds the smallest slot index ≥ loc that is empty. The value in ret will be set to the next nonempty slot index or to N if all subsequent slot indices are empty.

Example: The following loop will iterate over all occupied slot indices.

int i = -1;
do {
    csnip_lphash_Nextentry(N, u, is_empty, i + 1, i);
    if (i == N)
        break;
    // Do something with slot i here...
} while(1);