rpm  4.5
Data Structures | Typedefs | Functions
rpmhash.c File Reference

Hash table implemenation. More...

#include "system.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_shashBucket
 

Functions

static void * _free (const void *p)
 Wrapper to free(3), hides const compilation noise, permit NULL, return NULL.
 
static hashBucket findEntry (hashTable ht, const void *key)
 Find entry in hash table.
 
static uint32_t hashFunctionString (uint32_t h, const void *data, size_t size)
 Return hash value of a string.
 
static int hashEqualityString (const void *key1, const void *key2)
 Compare two hash table entries for equality.
 
hashTable htCreate (int numBuckets, int keySize, int freeData, hashFunctionType fn, hashEqualityType eq)
 Create hash table.
 
void htAddEntry (hashTable ht, const void *key, const void *data)
 Add item to hash table.
 
hashTable htFree (hashTable ht)
 Destroy 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.
 

Detailed Description

Hash table implemenation.

Definition in file rpmhash.c.

Typedef Documentation

typedef struct hashBucket_s* hashBucket

Definition at line 12 of file rpmhash.c.

typedef const void* voidptr

Definition at line 10 of file rpmhash.c.

Function Documentation

static void* _free ( const void *  p)
inlinestatic

Wrapper to free(3), hides const compilation noise, permit NULL, return NULL.

Parameters
pmemory to free
Return values
NULLalways

Definition at line 40 of file rpmhash.c.

Referenced by htFree().

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

Find entry in hash table.

Parameters
htpointer to hash table
keypointer 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().

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

Compare two hash table entries for equality.

Parameters
key1entry 1
key2entry 2
Returns
0 if entries are equal

Definition at line 107 of file rpmhash.c.

Referenced by htCreate().

static uint32_t hashFunctionString ( uint32_t  h,
const void *  data,
size_t  size 
)
static

Return hash value of a string.

Parameters
hhash initial value
datadata on which to calculate hash value
sizesize of data in bytes
Returns
hash value

Definition at line 79 of file rpmhash.c.

Referenced by htCreate().

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

Add item to hash table.

Parameters
htpointer to hash table
keypointer to key
datapointer to data value

Definition at line 134 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(), and rpmtsRun().

hashTable htCreate ( int  numBuckets,
int  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
numBucketsnumber of hash buckets
keySizesize of key (0 if unknown)
freeDataShould data be freed when table is destroyed?
fnfunction to generate hash key (NULL for default)
eqfunction to compare keys for equality (NULL for default)
Returns
pointer to initialized hash table

Definition at line 115 of file rpmhash.c.

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

Referenced by fpCacheCreate(), and rpmtsRun().

hashTable htFree ( hashTable  ht)

Destroy hash table.

Parameters
htpointer to hash table
Returns
NULL always

Definition at line 167 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 fpCacheFree(), and rpmtsRun().

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

Retrieve item from hash table.

Parameters
htpointer to hash table
keypointer to key value
Return values
dataaddress to store data value from bucket
dataCountaddress to store data value size from bucket
tableKeyaddress to store key value from bucket (may be NULL)
Returns
0 on success, 1 if the item is not found.

Definition at line 210 of file rpmhash.c.

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

Referenced by cacheContainsDirectory(), and handleOverlappedFiles().

int htHasEntry ( hashTable  ht,
const void *  key 
)

Check for key in hash table.

Parameters
htpointer to hash table
keypointer to key value
Returns
1 if the key is present, 0 otherwise

Definition at line 203 of file rpmhash.c.

References findEntry().