*/
#include "system.h"
+#include <stdio.h>
#include "debug.h"
#define Bucket JOIN(HASHTYPE,Buket)
/**
*/
struct Bucket_s {
- HTKEYTYPE key; /*!< hash key */
- HTDATATYPE * data; /*!< pointer to hashed data */
- int dataCount; /*!< length of data (0 if unknown) */
Bucket next; /*!< pointer to next item in bucket */
+ HTKEYTYPE key; /*!< hash key */
+#ifdef HTDATATYPE
+ int dataCount; /*!< data entries */
+ HTDATATYPE data[1]; /*!< data - grows by resizing whole bucket */
+#endif
};
/**
*/
struct HASHSTRUCT {
int numBuckets; /*!< number of hash buckets */
- Bucket * buckets; /*!< hash bucket array */
+ Bucket * buckets; /*!< hash bucket array */
hashFunctionType fn; /*!< generate hash value for key */
hashEqualityType eq; /*!< compare hash keys for equality */
hashFreeKey freeKey;
+ int bucketCount; /*!< number of used buckets */
+ int keyCount; /*!< number of keys */
+#ifdef HTDATATYPE
+ int dataCount; /*!< number of data entries */
hashFreeData freeData;
+#endif
};
/**
* Find entry in hash table.
* @param ht pointer to hash table
* @param key pointer to key value
+ * @param keyHash key hash
* @return pointer to hash bucket of key (or NULL)
*/
static
-Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key)
+Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
{
- unsigned int hash;
- Bucket b;
+ unsigned int hash = keyHash % ht->numBuckets;
+ Bucket b = ht->buckets[hash];
- hash = ht->fn(key) % ht->numBuckets;
- b = ht->buckets[hash];
-
- while (b && b->key && ht->eq(b->key, key))
+ while (b && ht->eq(b->key, key))
b = b->next;
return b;
HASHTYPE HASHPREFIX(Create)(int numBuckets,
hashFunctionType fn, hashEqualityType eq,
- hashFreeKey freeKey, hashFreeData freeData)
+ hashFreeKey freeKey
+#ifdef HTDATATYPE
+, hashFreeData freeData
+#endif
+)
{
HASHTYPE ht;
ht->numBuckets = numBuckets;
ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
ht->freeKey = freeKey;
+#ifdef HTDATATYPE
ht->freeData = freeData;
+ ht->dataCount = 0;
+#endif
ht->fn = fn;
ht->eq = eq;
+ ht->bucketCount = ht->keyCount = 0;
return ht;
}
-void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key, HTDATATYPE data)
+static void HASHPREFIX(Resize)(HASHTYPE ht, int numBuckets) {
+ Bucket * buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
+
+ for (int i=0; i<ht->numBuckets; i++) {
+ Bucket b = ht->buckets[i];
+ Bucket nextB;
+ while (b != NULL) {
+ unsigned int hash = ht->fn(b->key) % numBuckets;
+ nextB = b->next;
+ b->next = buckets[hash];
+ buckets[hash] = b;
+ b = nextB;
+ }
+ }
+ free(ht->buckets);
+ ht->buckets = buckets;
+ ht->numBuckets = numBuckets;
+}
+
+unsigned int HASHPREFIX(KeyHash)(HASHTYPE ht, HTKEYTYPE key)
{
- unsigned int hash;
- Bucket b;
+ return ht->fn(key);
+}
- hash = ht->fn(key) % ht->numBuckets;
- b = ht->buckets[hash];
+void HASHPREFIX(AddHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash
+#ifdef HTDATATYPE
+, HTDATATYPE data
+#endif
+)
+{
+ unsigned int hash = keyHash % ht->numBuckets;
+ Bucket b = ht->buckets[hash];
+#ifdef HTDATATYPE
+ Bucket * b_addr = ht->buckets + hash;
+#endif
+
+ if (b == NULL) {
+ ht->bucketCount += 1;
+ }
- while (b && b->key && ht->eq(b->key, key))
+ while (b && ht->eq(b->key, key)) {
+#ifdef HTDATATYPE
+ b_addr = &(b->next);
+#endif
b = b->next;
+ }
if (b == NULL) {
+ ht->keyCount += 1;
b = xmalloc(sizeof(*b));
b->key = key;
- b->dataCount = 0;
+#ifdef HTDATATYPE
+ b->dataCount = 1;
+ b->data[0] = data;
+#endif
b->next = ht->buckets[hash];
- b->data = NULL;
ht->buckets[hash] = b;
}
+#ifdef HTDATATYPE
+ else {
+ // resizing bucket TODO: increase exponentially
+ // Bucket_s already contains space for one dataset
+ b = *b_addr = xrealloc(
+ b, sizeof(*b) + sizeof(b->data[0]) * (b->dataCount));
+ // though increasing dataCount after the resize
+ b->data[b->dataCount++] = data;
+ }
+ ht->dataCount += 1;
+#endif
+ if (ht->keyCount > ht->numBuckets) {
+ HASHPREFIX(Resize)(ht, ht->numBuckets * 2);
+ }
+}
- b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
- b->data[b->dataCount++] = data;
+void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
+#ifdef HTDATATYPE
+, HTDATATYPE data
+#endif
+)
+{
+#ifdef HTDATATYPE
+ HASHPREFIX(AddHEntry)(ht, key, ht->fn(key), data);
+#else
+ HASHPREFIX(AddHEntry)(ht, key, ht->fn(key));
+#endif
}
-HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
+void HASHPREFIX(Empty)( HASHTYPE ht)
{
Bucket b, n;
- int i, j;
+ int i;
+
+ if (ht->bucketCount == 0) return;
for (i = 0; i < ht->numBuckets; i++) {
b = ht->buckets[i];
if (b == NULL)
continue;
ht->buckets[i] = NULL;
- if (ht->freeKey)
- b->key = ht->freeKey(b->key);
do {
n = b->next;
- if (b->data) {
- if (ht->freeData) {
- for (j=0; j < b->dataCount; j++ ) {
+ if (ht->freeKey)
+ b->key = ht->freeKey(b->key);
+#ifdef HTDATATYPE
+ if (ht->freeData) {
+ int j;
+ for (j=0; j < b->dataCount; j++ ) {
b->data[j] = ht->freeData(b->data[j]);
- }
}
- b->data = _free(b->data);
}
+#endif
b = _free(b);
} while ((b = n) != NULL);
}
+ ht->bucketCount = 0;
+ ht->keyCount = 0;
+#ifdef HTDATATYPE
+ ht->dataCount = 0;
+#endif
+}
+HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
+{
+ if (ht==NULL)
+ return ht;
+ HASHPREFIX(Empty)(ht);
ht->buckets = _free(ht->buckets);
ht = _free(ht);
return NULL;
}
-int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
+int HASHPREFIX(HasHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash)
{
Bucket b;
- if (!(b = HASHPREFIX(findEntry)(ht, key))) return 0; else return 1;
+ if (!(b = HASHPREFIX(findEntry)(ht, key, keyHash))) return 0; else return 1;
}
-int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key, HTDATATYPE** data,
- int * dataCount, HTKEYTYPE* tableKey)
+int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
{
- Bucket b;
+ return HASHPREFIX(HasHEntry)(ht, key, ht->fn(key));
+}
- if ((b = HASHPREFIX(findEntry)(ht, key)) == NULL)
- return 0;
+int HASHPREFIX(GetHEntry)(HASHTYPE ht, HTKEYTYPE key, unsigned int keyHash,
+#ifdef HTDATATYPE
+ HTDATATYPE** data, int * dataCount,
+#endif
+ HTKEYTYPE* tableKey)
+{
+ Bucket b;
+ int rc = ((b = HASHPREFIX(findEntry)(ht, key, keyHash)) != NULL);
+#ifdef HTDATATYPE
if (data)
- *data = b->data;
+ *data = rc ? b->data : NULL;
if (dataCount)
- *dataCount = b->dataCount;
- if (tableKey)
+ *dataCount = rc ? b->dataCount : 0;
+#endif
+ if (tableKey && rc)
*tableKey = b->key;
- return 1;
+ return rc;
+}
+
+int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
+#ifdef HTDATATYPE
+ HTDATATYPE** data, int * dataCount,
+#endif
+ HTKEYTYPE* tableKey)
+{
+ return HASHPREFIX(GetHEntry)(ht, key, ht->fn(key),
+#ifdef HTDATATYPE
+ data, dataCount,
+#endif
+ tableKey);
+}
+
+unsigned int HASHPREFIX(NumBuckets)(HASHTYPE ht) {
+ return ht->numBuckets;
+}
+
+unsigned int HASHPREFIX(UsedBuckets)(HASHTYPE ht) {
+ return ht->bucketCount;
}
+unsigned int HASHPREFIX(NumKeys)(HASHTYPE ht) {
+ return ht->keyCount;
+}
+
+#ifdef HTDATATYPE
+unsigned int HASHPREFIX(NumData)(HASHTYPE ht) {
+ return ht->dataCount;
+}
+#endif
+
+
void HASHPREFIX(PrintStats)(HASHTYPE ht) {
int i;
Bucket bucket;
int buckets = 0;
for (bucket=ht->buckets[i]; bucket; bucket=bucket->next){
buckets++;
+#ifdef HTDATATYPE
datacnt += bucket->dataCount;
+#endif
}
if (maxbuckets < buckets) maxbuckets = buckets;
if (buckets) hashcnt++;
projects / platform / upstream / rpm.git / blobdiff