hashtable.h File Reference

#include "env_internal.h"
#include <limits.h>

Go to the source code of this file.

Macros
#define	RANGE_SIGNED_HASH   (LLONG_MAX/2)

Typedefs
typedef struct _CMR_LINEARHASHTABLE_ARRAY	CMR_LINEARHASHTABLE_ARRAY
typedef size_t	CMR_LINEARHASHTABLE_BUCKET
typedef size_t	CMR_LINEARHASHTABLE_HASH
typedef struct _CMR_LISTHASHTABLE	CMR_LISTHASHTABLE
typedef size_t	CMR_LISTHASHTABLE_VALUE
typedef size_t	CMR_LISTHASHTABLE_HASH
typedef size_t	CMR_LISTHASHTABLE_BUCKET
typedef size_t	CMR_LISTHASHTABLE_ENTRY

Functions
static size_t	nextPower2 (size_t x)
	Returns the smallest power of 2 at least as large as x.
CMR_ERROR	CMRlinearhashtableArrayCreate (CMR *cmr, CMR_LINEARHASHTABLE_ARRAY **phashtable, size_t initialSize, size_t initialKeyMemory)
CMR_ERROR	CMRlinearhashtableArrayFree (CMR *cmr, CMR_LINEARHASHTABLE_ARRAY **phashtable)
bool	CMRlinearhashtableArrayFind (CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, CMR_LINEARHASHTABLE_BUCKET *pbucket, CMR_LINEARHASHTABLE_HASH *phash)
const void *	CMRlinearhashtableArrayKey (CMR_LINEARHASHTABLE_ARRAY *hashtable, CMR_LINEARHASHTABLE_BUCKET bucket, size_t *pKeyLength)
const void *	CMRlinearhashtableArrayValue (CMR_LINEARHASHTABLE_ARRAY *hashtable, CMR_LINEARHASHTABLE_BUCKET bucket)
CMR_ERROR	CMRlinearhashtableArrayInsertBucketHash (CMR *cmr, CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, CMR_LINEARHASHTABLE_BUCKET bucket, CMR_LINEARHASHTABLE_HASH hash, const void *value)
CMR_ERROR	CMRlinearhashtableArrayInsert (CMR *cmr, CMR_LINEARHASHTABLE_ARRAY *hashtable, const void *keyArray, size_t keyLength, const void *value)
CMR_ERROR	CMRlisthashtableCreate (CMR *cmr, CMR_LISTHASHTABLE **phashtable, size_t initialNumBuckets, size_t initialMemNodes)
CMR_ERROR	CMRlisthashtableFree (CMR *cmr, CMR_LISTHASHTABLE **phashtable)
CMR_LISTHASHTABLE_ENTRY	CMRlisthashtableFindFirst (CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash)
CMR_LISTHASHTABLE_ENTRY	CMRlisthashtableFindNext (CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash, CMR_LISTHASHTABLE_ENTRY entry)
CMR_LISTHASHTABLE_VALUE	CMRlisthashtableValue (CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
CMR_LISTHASHTABLE_HASH	CMRlisthashtableHash (CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
size_t	CMRlisthashtableNumBuckets (CMR_LISTHASHTABLE *hashtable)
CMR_ERROR	CMRlisthashtableInsert (CMR *cmr, CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_HASH hash, CMR_LISTHASHTABLE_VALUE value, CMR_LISTHASHTABLE_ENTRY *pentry)
	Inserts value with hash into the hash table, even if an entry with the same hash exists.
CMR_ERROR	CMRlisthashtableRemove (CMR *cmr, CMR_LISTHASHTABLE *hashtable, CMR_LISTHASHTABLE_ENTRY entry)
static long long	projectSignedHash (long long value)
	Projects value into the range [-RANGE_SIGNED_HASH, +RANGE_SIGNED_HASH] via a modulo computation.

Macro Definition Documentation

RANGE_SIGNED_HASH

#define RANGE_SIGNED_HASH   (LLONG_MAX/2)

Typedef Documentation

CMR_LINEARHASHTABLE_ARRAY

typedef struct _CMR_LINEARHASHTABLE_ARRAY CMR_LINEARHASHTABLE_ARRAY

CMR_LINEARHASHTABLE_BUCKET

typedef size_t CMR_LINEARHASHTABLE_BUCKET

CMR_LINEARHASHTABLE_HASH

typedef size_t CMR_LINEARHASHTABLE_HASH

CMR_LISTHASHTABLE

typedef struct _CMR_LISTHASHTABLE CMR_LISTHASHTABLE

CMR_LISTHASHTABLE_BUCKET

typedef size_t CMR_LISTHASHTABLE_BUCKET

CMR_LISTHASHTABLE_ENTRY

typedef size_t CMR_LISTHASHTABLE_ENTRY

CMR_LISTHASHTABLE_HASH

typedef size_t CMR_LISTHASHTABLE_HASH

CMR_LISTHASHTABLE_VALUE

typedef size_t CMR_LISTHASHTABLE_VALUE

Function Documentation

CMRlinearhashtableArrayCreate()

CMR_ERROR CMRlinearhashtableArrayCreate	(	CMR *	cmr,
		CMR_LINEARHASHTABLE_ARRAY **	phashtable,
		size_t	initialSize,
		size_t	initialKeyMemory
	)

Parameters

cmr	CMR environment.
phashtable	Pointer for storing the hash table.
initialSize	Initial size of hash table.
initialKeyMemory	Initial memory for keys.

CMRlinearhashtableArrayFind()

bool CMRlinearhashtableArrayFind	(	CMR_LINEARHASHTABLE_ARRAY *	hashtable,
		const void *	keyArray,
		size_t	keyLength,
		CMR_LINEARHASHTABLE_BUCKET *	pbucket,
		CMR_LINEARHASHTABLE_HASH *	phash
	)

Parameters

hashtable	Hash table.
keyArray	First byte of key array.
keyLength	Length of key array in bytes.
pbucket	Pointer for storing the bucket.
phash	Pointer for storing the hash.

CMRlinearhashtableArrayFree()

CMR_ERROR CMRlinearhashtableArrayFree	(	CMR *	cmr,
		CMR_LINEARHASHTABLE_ARRAY **	phashtable
	)

Parameters

cmr	CMR environment.
phashtable	Pointer to the hash table.

CMRlinearhashtableArrayInsert()

CMR_ERROR CMRlinearhashtableArrayInsert	(	CMR *	cmr,
		CMR_LINEARHASHTABLE_ARRAY *	hashtable,
		const void *	keyArray,
		size_t	keyLength,
		const void *	value
	)

Parameters

cmr	CMR environment.
hashtable	Hash table.
keyArray	First byte of key array.
keyLength	Length of key array.
value	Value to be set.

CMRlinearhashtableArrayInsertBucketHash()

CMR_ERROR CMRlinearhashtableArrayInsertBucketHash	(	CMR *	cmr,
		CMR_LINEARHASHTABLE_ARRAY *	hashtable,
		const void *	keyArray,
		size_t	keyLength,
		CMR_LINEARHASHTABLE_BUCKET	bucket,
		CMR_LINEARHASHTABLE_HASH	hash,
		const void *	value
	)

Parameters

cmr	CMR environment.
hashtable	Hash table.
keyArray	First byte of key array.
keyLength	Length of key array.
bucket	Known bucket of key, determined by CMRlinearhashtableArrayFind.
hash	Known hash of key, determined by CMRlinearhashtableArrayFind.
value	Value to be set.

CMRlinearhashtableArrayKey()

const void * CMRlinearhashtableArrayKey	(	CMR_LINEARHASHTABLE_ARRAY *	hashtable,
		CMR_LINEARHASHTABLE_BUCKET	bucket,
		size_t *	pKeyLength
	)

Parameters

hashtable	Hash table.
bucket	Bucket.
pKeyLength	Length of key array.

CMRlinearhashtableArrayValue()

const void * CMRlinearhashtableArrayValue	(	CMR_LINEARHASHTABLE_ARRAY *	hashtable,
		CMR_LINEARHASHTABLE_BUCKET	bucket
	)

Parameters

hashtable	Hash table.
bucket	Bucket.

CMRlisthashtableCreate()

CMR_ERROR CMRlisthashtableCreate	(	CMR *	cmr,
		CMR_LISTHASHTABLE **	phashtable,
		size_t	initialNumBuckets,
		size_t	initialMemNodes
	)

Parameters

cmr	CMR environment.
phashtable	Pointer for storing the hash table.
initialNumBuckets	Initial size of hash table.
initialMemNodes	Initial memory for actual entries..

CMRlisthashtableFindFirst()

CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindFirst	(	CMR_LISTHASHTABLE *	hashtable,
		CMR_LISTHASHTABLE_HASH	hash
	)

Parameters

hashtable	Hash table.
hash	Hash value.

CMRlisthashtableFindNext()

CMR_LISTHASHTABLE_ENTRY CMRlisthashtableFindNext	(	CMR_LISTHASHTABLE *	hashtable,
		CMR_LISTHASHTABLE_HASH	hash,
		CMR_LISTHASHTABLE_ENTRY	entry
	)

Parameters

hashtable	Hash table.
hash	Hash value.
entry	Current entry.

CMRlisthashtableFree()

CMR_ERROR CMRlisthashtableFree	(	CMR *	cmr,
		CMR_LISTHASHTABLE **	phashtable
	)

Parameters

cmr	CMR environment.
phashtable	Pointer to the hash table.

CMRlisthashtableHash()

CMR_LISTHASHTABLE_HASH CMRlisthashtableHash	(	CMR_LISTHASHTABLE *	hashtable,
		CMR_LISTHASHTABLE_ENTRY	entry
	)

Parameters

hashtable	Hash table.
entry	Entry.

CMRlisthashtableInsert()

CMR_ERROR CMRlisthashtableInsert	(	CMR *	cmr,
		CMR_LISTHASHTABLE *	hashtable,
		CMR_LISTHASHTABLE_HASH	hash,
		CMR_LISTHASHTABLE_VALUE	value,
		CMR_LISTHASHTABLE_ENTRY *	pentry
	)

Inserts value with hash into the hash table, even if an entry with the same hash exists.

Parameters

cmr	CMR environment.
hashtable	Hash table.
hash	Hash value.
value	Value to be set.
pentry	Pointer for storing the new entry.

CMRlisthashtableNumBuckets()

size_t CMRlisthashtableNumBuckets

(

CMR_LISTHASHTABLE *

hashtable

)

Parameters

hashtable

Hash table.

CMRlisthashtableRemove()

CMR_ERROR CMRlisthashtableRemove	(	CMR *	cmr,
		CMR_LISTHASHTABLE *	hashtable,
		CMR_LISTHASHTABLE_ENTRY	entry
	)

Parameters

cmr	CMR environment.
hashtable	Hash table.
entry	Entry to be removed.

CMRlisthashtableValue()

CMR_LISTHASHTABLE_VALUE CMRlisthashtableValue	(	CMR_LISTHASHTABLE *	hashtable,
		CMR_LISTHASHTABLE_ENTRY	entry
	)

Parameters

hashtable	Hash table.
entry	Entry.

nextPower2()

static size_t nextPower2 ( size_t  x )

inlinestatic

Returns the smallest power of 2 at least as large as x.

projectSignedHash()

static long long projectSignedHash ( long long  value )

inlinestatic

Projects value into the range [-RANGE_SIGNED_HASH, +RANGE_SIGNED_HASH] via a modulo computation.