[Rpm-maint] [PATCH 1/4] Handles case insensitive filesystems.
Giulio Eulisse
Giulio.Eulisse at cern.ch
Tue Apr 20 09:41:58 UTC 2010
* rpmhash.H and rpmhash.C renamed to `rpmhash_big.H` and `rpmhash_big.C` to
avoid confusion with `rpmhash.h` and `rpmhash.c` on platforms which have a
case insensitive filesystems (i.e. Macosx).
---
lib/depends.c | 4 +
lib/fprint.c | 4 +
lib/fprint.h | 4 +
lib/rpmal.c | 8 +-
lib/rpmhash.H | 104 ---------------------------
lib/rpmhash.h | 22 ++++++
lib/rpmhash_big.C | 207 +++++++++++++++++++++++++++++++++++++++++++++++++++++
lib/rpmhash_big.H | 104 +++++++++++++++++++++++++++
lib/transaction.c | 4 +
9 files changed, 345 insertions(+), 116 deletions(-)
delete mode 100644 lib/rpmhash.H
create mode 100644 lib/rpmhash.h
create mode 100644 lib/rpmhash_big.C
create mode 100644 lib/rpmhash_big.H
-------------- next part --------------
diff --git a/lib/depends.c b/lib/depends.c
index ef55adb..dd566f1 100644
--- a/lib/depends.c
+++ b/lib/depends.c
@@ -33,8 +33,8 @@ static rpmds rpmlibP = NULL;
#define HASHTYPE depCache
#define HTKEYTYPE const char *
#define HTDATATYPE int
-#include "lib/rpmhash.H"
-#include "lib/rpmhash.C"
+#include "lib/rpmhash_big.H"
+#include "lib/rpmhash_big.C"
/**
* Compare removed package instances (qsort/bsearch).
diff --git a/lib/fprint.c b/lib/fprint.c
index c04c8af..8c4d5b4 100644
--- a/lib/fprint.c
+++ b/lib/fprint.c
@@ -14,7 +14,7 @@
#include <libgen.h>
/* Create new hash table type rpmFpEntryHash */
-#include "lib/rpmhash.C"
+#include "lib/rpmhash_big.C"
#undef HASHTYPE
#undef HTKEYTYPE
@@ -22,7 +22,7 @@
#define HASHTYPE rpmFpEntryHash
#define HTKEYTYPE const char *
#define HTDATATYPE const struct fprintCacheEntry_s *
-#include "lib/rpmhash.C"
+#include "lib/rpmhash_big.C"
fingerPrintCache fpCacheCreate(int sizeHint)
{
diff --git a/lib/fprint.h b/lib/fprint.h
index 4ac7dad..65e0cbe 100644
--- a/lib/fprint.h
+++ b/lib/fprint.h
@@ -35,7 +35,7 @@ const char * baseName; /*!< file base name */
#define HASHTYPE rpmFpEntryHash
#define HTKEYTYPE const char *
#define HTDATATYPE const struct fprintCacheEntry_s *
-#include "lib/rpmhash.H"
+#include "lib/rpmhash_big.H"
/**
* Finger print cache entry.
@@ -70,7 +70,7 @@ struct rpmffi_s {
#define HASHTYPE rpmFpHash
#define HTKEYTYPE const fingerPrint *
#define HTDATATYPE struct rpmffi_s
-#include "lib/rpmhash.H"
+#include "lib/rpmhash_big.H"
/** */
#define FP_ENTRY_EQUAL(a, b) (((a)->dev == (b)->dev) && ((a)->ino == (b)->ino))
diff --git a/lib/rpmal.c b/lib/rpmal.c
index b320ca1..f2cb99b 100644
--- a/lib/rpmal.c
+++ b/lib/rpmal.c
@@ -62,8 +62,8 @@ struct fileIndexEntry_s {
#define HASHTYPE rpmalProvidesHash
#define HTKEYTYPE const char *
#define HTDATATYPE struct availableIndexEntry_s
-#include "lib/rpmhash.H"
-#include "lib/rpmhash.C"
+#include "lib/rpmhash_big.H"
+#include "lib/rpmhash_big.C"
#undef HASHTYPE
#undef HTKEYTYPE
@@ -71,8 +71,8 @@ struct fileIndexEntry_s {
#define HASHTYPE rpmalFileHash
#define HTKEYTYPE struct fileNameEntry_s
#define HTDATATYPE struct fileIndexEntry_s
-#include "lib/rpmhash.H"
-#include "lib/rpmhash.C"
+#include "lib/rpmhash_big.H"
+#include "lib/rpmhash_big.C"
diff --git a/lib/rpmhash.H b/lib/rpmhash.H
deleted file mode 100644
index e6fcd29..0000000
--- a/lib/rpmhash.H
+++ /dev/null
@@ -1,104 +0,0 @@
-/**
- * \file lib/rpmhash.h
- * Hash table implemenation.
- */
-
-#include <string.h>
-// Hackery to make sure that macros get expanded
-#define __JOIN(a,b) a##b
-#define JOIN(a,b) __JOIN(a,b)
-#define HASHPREFIX(name) JOIN(HASHTYPE,name)
-#define HASHSTRUCT JOIN(HASHTYPE,_s)
-
-typedef struct HASHSTRUCT * HASHTYPE;
-
-/* function pointer types to deal with the datatypes the hash works with */
-
-#define hashFunctionType JOIN(HASHTYPE,HashFunctionType)
-#define hashEqualityType JOIN(HASHTYPE,HashEqualityType)
-#define hashFreeKey JOIN(HASHTYPE,FreeKey)
-
-typedef unsigned int (*hashFunctionType) (HTKEYTYPE string);
-typedef int (*hashEqualityType) (HTKEYTYPE key1, HTKEYTYPE key2);
-typedef HTKEYTYPE (*hashFreeKey) (HTKEYTYPE);
-
-#ifdef HTDATATYPE
-#define hashFreeData JOIN(HASHTYPE,FreeData)
-typedef HTDATATYPE (*hashFreeData) (HTDATATYPE);
-#endif
-
-/**
- * Create hash table.
- * If keySize > 0, the key is duplicated within the table (which costs
- * memory, but may be useful anyway.
- * @param numBuckets number of hash buckets
- * @param fn function to generate hash value for key
- * @param eq function to compare hash keys for equality
- * @param freeKey function to free the keys or NULL
- * @param freeData function to free the data or NULL
- * @return pointer to initialized hash table
- */
-RPM_GNUC_INTERNAL
-HASHTYPE HASHPREFIX(Create)(int numBuckets,
- hashFunctionType fn, hashEqualityType eq,
- hashFreeKey freeKey
-#ifdef HTDATATYPE
-, hashFreeData freeData
-#endif
-);
-
-/**
- * Destroy hash table.
- * @param ht pointer to hash table
- * @return NULL always
- */
-RPM_GNUC_INTERNAL
-HASHTYPE HASHPREFIX(Free)( HASHTYPE ht);
-
-/**
- * Add item to hash table.
- * @param ht pointer to hash table
- * @param key key
- * @param data data value
- */
-RPM_GNUC_INTERNAL
-void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
-#ifdef HTDATATYPE
-, HTDATATYPE data
-#endif
-);
-
-#ifdef HTDATATYPE
-
-/**
- * Retrieve item from hash table.
- * @param ht pointer to hash table
- * @param key key value
- * @retval data address to store data value from bucket
- * @retval dataCount address to store data value size from bucket
- * @retval tableKey address to store key value from bucket (may be NULL)
- * @return 1 on success, 0 if the item is not found.
- */
-RPM_GNUC_INTERNAL
-int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
- HTDATATYPE** data,
- int * dataCount,
- HTKEYTYPE* tableKey);
-#endif
-
-/**
- * Check for key in hash table.
- * @param ht pointer to hash table
- * @param key key value
- * @return 1 if the key is present, 0 otherwise
- */
-RPM_GNUC_INTERNAL
-int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key);
-
-/**
- * Print statistics about the hash to stderr
- * This is for debugging only
- * @param ht pointer to hash table
- */
-RPM_GNUC_INTERNAL
-void HASHPREFIX(PrintStats)(HASHTYPE ht);
diff --git a/lib/rpmhash.h b/lib/rpmhash.h
new file mode 100644
index 0000000..57cc290
--- /dev/null
+++ b/lib/rpmhash.h
@@ -0,0 +1,22 @@
+#ifndef H_RPMHASH
+#define H_RPMHASH
+
+#include "rpm/rpmutil.h"
+
+/**
+ * \file lib/rpmhash.h
+ * Hash table implemenation.
+ */
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+RPM_GNUC_INTERNAL
+unsigned int hashFunctionString(const char * string);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lib/rpmhash_big.C b/lib/rpmhash_big.C
new file mode 100644
index 0000000..79a82b0
--- /dev/null
+++ b/lib/rpmhash_big.C
@@ -0,0 +1,207 @@
+/**
+ * \file lib/rpmhash.c
+ * Hash table implemenation
+ */
+
+#include "system.h"
+#include "debug.h"
+
+#define Bucket JOIN(HASHTYPE,Buket)
+#define Bucket_s JOIN(HASHTYPE,Buket_s)
+
+typedef struct Bucket_s * Bucket;
+
+/**
+ */
+struct Bucket_s {
+ 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 */
+ hashFunctionType fn; /*!< generate hash value for key */
+ hashEqualityType eq; /*!< compare hash keys for equality */
+ hashFreeKey freeKey;
+#ifdef HTDATATYPE
+ hashFreeData freeData;
+#endif
+};
+
+/**
+ * Find entry in hash table.
+ * @param ht pointer to hash table
+ * @param key pointer to key value
+ * @return pointer to hash bucket of key (or NULL)
+ */
+static
+Bucket HASHPREFIX(findEntry)(HASHTYPE ht, HTKEYTYPE key)
+{
+ unsigned int hash;
+ Bucket b;
+
+ hash = ht->fn(key) % ht->numBuckets;
+ b = ht->buckets[hash];
+
+ while (b && ht->eq(b->key, key))
+ b = b->next;
+
+ return b;
+}
+
+HASHTYPE HASHPREFIX(Create)(int numBuckets,
+ hashFunctionType fn, hashEqualityType eq,
+ hashFreeKey freeKey
+#ifdef HTDATATYPE
+, hashFreeData freeData
+#endif
+)
+{
+ HASHTYPE ht;
+
+ ht = xmalloc(sizeof(*ht));
+ ht->numBuckets = numBuckets;
+ ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
+ ht->freeKey = freeKey;
+#ifdef HTDATATYPE
+ ht->freeData = freeData;
+#endif
+ ht->fn = fn;
+ ht->eq = eq;
+ return ht;
+}
+
+void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
+#ifdef HTDATATYPE
+, HTDATATYPE data
+#endif
+)
+{
+ unsigned int hash;
+ Bucket b;
+ Bucket * b_addr;
+
+ hash = ht->fn(key) % ht->numBuckets;
+ b = ht->buckets[hash];
+ b_addr = ht->buckets + hash;
+
+ while (b && ht->eq(b->key, key)) {
+ b_addr = &(b->next);
+ b = b->next;
+ }
+
+ if (b == NULL) {
+ b = xmalloc(sizeof(*b));
+ b->key = key;
+#ifdef HTDATATYPE
+ b->dataCount = 1;
+ b->data[0] = data;
+#endif
+ b->next = ht->buckets[hash];
+ 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;
+ }
+#endif
+}
+
+HASHTYPE HASHPREFIX(Free)(HASHTYPE ht)
+{
+ Bucket b, n;
+ int i;
+ if (ht==NULL)
+ return ht;
+ for (i = 0; i < ht->numBuckets; i++) {
+ b = ht->buckets[i];
+ if (b == NULL)
+ continue;
+ ht->buckets[i] = NULL;
+
+ do {
+ n = b->next;
+ 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]);
+ }
+ }
+#endif
+ b = _free(b);
+ } while ((b = n) != NULL);
+ }
+
+ ht->buckets = _free(ht->buckets);
+ ht = _free(ht);
+
+ return NULL;
+}
+
+int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key)
+{
+ Bucket b;
+
+ if (!(b = HASHPREFIX(findEntry)(ht, key))) return 0; else return 1;
+}
+
+#ifdef HTDATATYPE
+
+int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key, HTDATATYPE** data,
+ int * dataCount, HTKEYTYPE* tableKey)
+{
+ Bucket b;
+ int rc = ((b = HASHPREFIX(findEntry)(ht, key)) != NULL);
+
+ if (data)
+ *data = rc ? b->data : NULL;
+ if (dataCount)
+ *dataCount = rc ? b->dataCount : 0;
+ if (tableKey && rc)
+ *tableKey = b->key;
+
+ return rc;
+}
+
+void HASHPREFIX(PrintStats)(HASHTYPE ht) {
+ int i;
+ Bucket bucket;
+
+ int hashcnt=0, bucketcnt=0, datacnt=0;
+ int maxbuckets=0;
+
+ for (i=0; i<ht->numBuckets; i++) {
+ 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++;
+ bucketcnt += buckets;
+ }
+ fprintf(stderr, "Hashsize: %i\n", ht->numBuckets);
+ fprintf(stderr, "Hashbuckets: %i\n", hashcnt);
+ fprintf(stderr, "Keys: %i\n", bucketcnt);
+ fprintf(stderr, "Values: %i\n", datacnt);
+ fprintf(stderr, "Max Keys/Bucket: %i\n", maxbuckets);
+}
+
+#endif
diff --git a/lib/rpmhash_big.H b/lib/rpmhash_big.H
new file mode 100644
index 0000000..e6fcd29
--- /dev/null
+++ b/lib/rpmhash_big.H
@@ -0,0 +1,104 @@
+/**
+ * \file lib/rpmhash.h
+ * Hash table implemenation.
+ */
+
+#include <string.h>
+// Hackery to make sure that macros get expanded
+#define __JOIN(a,b) a##b
+#define JOIN(a,b) __JOIN(a,b)
+#define HASHPREFIX(name) JOIN(HASHTYPE,name)
+#define HASHSTRUCT JOIN(HASHTYPE,_s)
+
+typedef struct HASHSTRUCT * HASHTYPE;
+
+/* function pointer types to deal with the datatypes the hash works with */
+
+#define hashFunctionType JOIN(HASHTYPE,HashFunctionType)
+#define hashEqualityType JOIN(HASHTYPE,HashEqualityType)
+#define hashFreeKey JOIN(HASHTYPE,FreeKey)
+
+typedef unsigned int (*hashFunctionType) (HTKEYTYPE string);
+typedef int (*hashEqualityType) (HTKEYTYPE key1, HTKEYTYPE key2);
+typedef HTKEYTYPE (*hashFreeKey) (HTKEYTYPE);
+
+#ifdef HTDATATYPE
+#define hashFreeData JOIN(HASHTYPE,FreeData)
+typedef HTDATATYPE (*hashFreeData) (HTDATATYPE);
+#endif
+
+/**
+ * Create hash table.
+ * If keySize > 0, the key is duplicated within the table (which costs
+ * memory, but may be useful anyway.
+ * @param numBuckets number of hash buckets
+ * @param fn function to generate hash value for key
+ * @param eq function to compare hash keys for equality
+ * @param freeKey function to free the keys or NULL
+ * @param freeData function to free the data or NULL
+ * @return pointer to initialized hash table
+ */
+RPM_GNUC_INTERNAL
+HASHTYPE HASHPREFIX(Create)(int numBuckets,
+ hashFunctionType fn, hashEqualityType eq,
+ hashFreeKey freeKey
+#ifdef HTDATATYPE
+, hashFreeData freeData
+#endif
+);
+
+/**
+ * Destroy hash table.
+ * @param ht pointer to hash table
+ * @return NULL always
+ */
+RPM_GNUC_INTERNAL
+HASHTYPE HASHPREFIX(Free)( HASHTYPE ht);
+
+/**
+ * Add item to hash table.
+ * @param ht pointer to hash table
+ * @param key key
+ * @param data data value
+ */
+RPM_GNUC_INTERNAL
+void HASHPREFIX(AddEntry)(HASHTYPE ht, HTKEYTYPE key
+#ifdef HTDATATYPE
+, HTDATATYPE data
+#endif
+);
+
+#ifdef HTDATATYPE
+
+/**
+ * Retrieve item from hash table.
+ * @param ht pointer to hash table
+ * @param key key value
+ * @retval data address to store data value from bucket
+ * @retval dataCount address to store data value size from bucket
+ * @retval tableKey address to store key value from bucket (may be NULL)
+ * @return 1 on success, 0 if the item is not found.
+ */
+RPM_GNUC_INTERNAL
+int HASHPREFIX(GetEntry)(HASHTYPE ht, HTKEYTYPE key,
+ HTDATATYPE** data,
+ int * dataCount,
+ HTKEYTYPE* tableKey);
+#endif
+
+/**
+ * Check for key in hash table.
+ * @param ht pointer to hash table
+ * @param key key value
+ * @return 1 if the key is present, 0 otherwise
+ */
+RPM_GNUC_INTERNAL
+int HASHPREFIX(HasEntry)(HASHTYPE ht, HTKEYTYPE key);
+
+/**
+ * Print statistics about the hash to stderr
+ * This is for debugging only
+ * @param ht pointer to hash table
+ */
+RPM_GNUC_INTERNAL
+void HASHPREFIX(PrintStats)(HASHTYPE ht);
diff --git a/lib/transaction.c b/lib/transaction.c
index e4f282b..3d81d80 100644
--- a/lib/transaction.c
+++ b/lib/transaction.c
@@ -830,8 +830,8 @@ static void skipInstallFiles(const rpmts ts, rpmte p)
#define HASHTYPE rpmStringSet
#define HTKEYTYPE const char *
-#include "lib/rpmhash.H"
-#include "lib/rpmhash.C"
+#include "lib/rpmhash_big.H"
+#include "lib/rpmhash_big.C"
/* Get a rpmdbMatchIterator containing all files in
* the rpmdb that share the basename with one from
More information about the Rpm-maint
mailing list