rpmio/rpmhash.c File Reference

Hash table implemenation. More...

#include "system.h"
#include <rpmiotypes.h>
#include <rpmio.h>
#include <rpmhash.h>
#include "debug.h"

Include dependency graph for rpmhash.c:

Go to the source code of this file.

Data Structures
struct	hashBucket_s
struct	hashTable_s
Typedefs
typedef const void *	voidptr
typedef struct hashBucket_s *	hashBucket
Functions
static hashBucket	findEntry (hashTable ht, const void *key)
	Find entry in hash table.
int	hashEqualityString (const void *key1, const void *key2)
	Compare two hash table entries for equality.
rpmuint32_t	hashFunctionString (rpmuint32_t h, const void *data, size_t size)
	Return hash value of a string.
void	htAddEntry (hashTable ht, const void *key, const void *data)
	Add item to hash table.
int	htHasEntry (hashTable ht, const void *key)
	Check for key in hash table.
int	htGetEntry (hashTable ht, const void *key, const void *data, int *dataCount, const void *tableKey)
	Retrieve item from hash table.
const void **	htGetKeys (hashTable ht)
	Retrieve keys from hash table.
static void	htFini (void *_ht)
static hashTable	htGetPool (rpmioPool pool)
hashTable	htCreate (int numBuckets, size_t keySize, int freeData, hashFunctionType fn, hashEqualityType eq)
	Create hash table.
Variables
int	_ht_debug = 0
rpmioPool	_htPool

---

Detailed Description

Hash table implemenation.

Definition in file rpmhash.c.

---

Typedef Documentation

typedef struct hashBucket_s* hashBucket

Definition at line 17 of file rpmhash.c.

typedef const void* voidptr

Definition at line 15 of file rpmhash.c.

---

Function Documentation

static hashBucket findEntry	(	hashTable	ht,
		const void *	key
	)		[static]

Find entry in hash table.

Parameters:

ht	pointer to hash table
key	pointer to key value

Returns:

pointer to hash bucket of key (or NULL)

Definition at line 53 of file rpmhash.c.

References hashTable_s::buckets, hashTable_s::eq, hashTable_s::fn, hashBucket_s::key, hashBucket_s::next, and hashTable_s::numBuckets.

Referenced by htGetEntry(), and htHasEntry().

int hashEqualityString	(	const void *	key1,
		const void *	key2
	)

Compare two hash table entries for equality.

Parameters:

key1	entry 1
key2	entry 2

Returns:

0 if entries are equal

Definition at line 70 of file rpmhash.c.

Referenced by htCreate().

rpmuint32_t hashFunctionString	(	rpmuint32_t	h,
		const void *	data,
		size_t	size
	)

Return hash value of a string.

Parameters:

h	hash initial value
data	data on which to calculate hash value
size	size of data in bytes (0 will use strlen(data))

Returns:

hash value

Definition at line 77 of file rpmhash.c.

Referenced by Fstat(), ftpLstat(), ftpStat(), htCreate(), rpmmiGrowBasename(), rpmtsCheckInstalledFiles(), and rpmxarStat().

void htAddEntry	(	hashTable	ht,
		const void *	key,
		const void *	data
	)

Add item to hash table.

Parameters:

ht	pointer to hash table
key	pointer to key
data	pointer to data value

Definition at line 144 of file rpmhash.c.

References hashTable_s::buckets, hashBucket_s::data, hashBucket_s::dataCount, hashTable_s::eq, hashTable_s::fn, hashBucket_s::key, hashTable_s::keySize, hashBucket_s::next, hashTable_s::numBuckets, xmalloc(), and xrealloc().

Referenced by doLookup(), fpLookupSubdir(), and rpmtsAddFingerprints().

hashTable htCreate	(	int	numBuckets,
		size_t	keySize,
		int	freeData,
		hashFunctionType	fn,
		hashEqualityType	eq
	)

Create hash table.

If keySize > 0, the key is duplicated within the table (which costs memory, but may be useful anyway.

Parameters:

numBuckets	number of hash buckets
keySize	size of key (0 if unknown)
freeData	Should data be freed when table is destroyed?
fn	function to generate hash key (NULL for default)
eq	function to compare keys for equality (NULL for default)

Returns:

pointer to initialized hash table

Definition at line 269 of file rpmhash.c.

References hashTable_s::buckets, hashTable_s::eq, hashTable_s::fn, hashTable_s::freeData, hashEqualityString(), hashFunctionString(), htGetPool(), htLink(), hashTable_s::keySize, hashTable_s::numBuckets, and xcalloc().

Referenced by fpCacheCreate(), rpmtsAddFingerprints(), and rpmtsPrepare().

static void htFini

(

void *

_ht

)

[static]

Definition at line 223 of file rpmhash.c.

References _free(), hashTable_s::buckets, hashBucket_s::data, hashTable_s::freeData, hashBucket_s::key, hashTable_s::keySize, hashBucket_s::next, and hashTable_s::numBuckets.

Referenced by htGetPool().

int htGetEntry	(	hashTable	ht,
		const void *	key,
		const void *	data,
		int *	dataCount,
		const void *	tableKey
	)

Retrieve item from hash table.

Parameters:

ht	pointer to hash table
key	pointer to key value

Return values:

*data	data value from bucket
*dataCount	data value size from bucket
*tableKey	key value from bucket (may be NULL)

Returns:

0 on success, 1 if the item is not found.

Definition at line 181 of file rpmhash.c.

References hashBucket_s::data, hashBucket_s::dataCount, findEntry(), and hashBucket_s::key.

Referenced by cacheContainsDirectory(), fpLookupSubdir(), handleOverlappedFiles(), and rpmtsCheckInstalledFiles().

const void** htGetKeys

(

hashTable

ht

)

Retrieve keys from hash table.

Parameters:

ht	pointer to hash table

Returns:

array of key values terminated by a NULL pointer

Definition at line 199 of file rpmhash.c.

References hashTable_s::buckets, hashBucket_s::data, hashBucket_s::key, hashBucket_s::next, hashTable_s::numBuckets, and xcalloc().

static hashTable htGetPool

(

rpmioPool

pool

)

[static]

Definition at line 255 of file rpmhash.c.

References _ht_debug, _htPool, htFini(), rpmioGetPool(), and rpmioNewPool().

Referenced by htCreate().

int htHasEntry	(	hashTable	ht,
		const void *	key
	)

Check for key in hash table.

Parameters:

ht	pointer to hash table
key	pointer to key value

Returns:

1 if the key is present, 0 otherwise

Definition at line 174 of file rpmhash.c.

References findEntry().

---

Variable Documentation

int _ht_debug = 0

Definition at line 13 of file rpmhash.c.

Referenced by htGetPool().

rpmioPool _htPool

Definition at line 253 of file rpmhash.c.

Referenced by htGetPool(), and rpmioClean().