# rpmdb/rpmhash.c

Go to the documentation of this file.

    00001
    00006 #include "system.h"
    00007 #include <rpmlib.h>
    00008 #include "rpmhash.h"
    00009 #include "debug.h"
    00010
    00011 typedef /*@owned@*/ const void * voidptr;
    00012
    00013 typedef struct hashBucket_s * hashBucket;
    00014
    00017 struct hashBucket_s {
    00018     voidptr key;
    00019 /*@owned@*/ voidptr * data;
    00020     int dataCount;
    00021 /*@dependent@*/hashBucket next;
    00022 };
    00023
    00026 struct hashTable_s {
    00027     int numBuckets;
    00028     int keySize;
    00029     int freeData;
    00030     hashBucket * buckets;
    00031     hashFunctionType fn;
    00032     hashEqualityType eq;
    00033 };
    00034
    00041 static /*@shared@*/ /*@null@*/
    00042 hashBucket findEntry(hashTable ht, const void * key)
    00043         /*@*/
    00044 {
    00045     unsigned int hash;
    00046     hashBucket b;
    00047
    00048     /*@-modunconnomods@*/
    00049     hash = ht->fn(key) % ht->numBuckets;
    00050     b = ht->buckets[hash];
    00051
    00052     while (b && b->key && ht->eq(b->key, key))
    00053         b = b->next;
    00054     /*@=modunconnomods@*/
    00055
    00056     return b;
    00057 }
    00058
    00059 int hashEqualityString(const void * key1, const void * key2)
    00060 {
    00061     const char *k1 = (const char *)key1;
    00062     const char *k2 = (const char *)key2;
    00063     return strcmp(k1, k2);
    00064 }
    00065
    00066 unsigned int hashFunctionString(const void * string)
    00067 {
    00068     char xorValue = 0;
    00069     char sum = 0;
    00070     short len;
    00071     int i;
    00072     const char * chp = string;
    00073
    00074     len = strlen(string);
    00075     for (i = 0; i < len; i++, chp++) {
    00076         xorValue ^= *chp;
    00077         sum += *chp;
    00078     }
    00079
    00080     return ((((unsigned)len) << 16) + (((unsigned)sum) << 8) + xorValue);
    00081 }
    00082
    00083 hashTable htCreate(int numBuckets, int keySize, int freeData,
    00084                 hashFunctionType fn, hashEqualityType eq)
    00085 {
    00086     hashTable ht;
    00087
    00088     ht = xmalloc(sizeof(*ht));
    00089     ht->numBuckets = numBuckets;
    00090     ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
    00091     ht->keySize = keySize;
    00092     ht->freeData = freeData;
    00093     /*@-assignexpose@*/
    00094     ht->fn = fn;
    00095     ht->eq = eq;
    00096     /*@=assignexpose@*/
    00097
    00098     return ht;
    00099 }
    00100
    00101 void htAddEntry(hashTable ht, const void * key, const void * data)
    00102 {
    00103     unsigned int hash;
    00104     hashBucket b;
    00105
    00106     hash = ht->fn(key) % ht->numBuckets;
    00107     b = ht->buckets[hash];
    00108
    00109     while (b && b->key && ht->eq(b->key, key))
    00110         b = b->next;
    00111
    00112     /*@-branchstate@*/
    00113     if (b == NULL) {
    00114         b = xmalloc(sizeof(*b));
    00115         if (ht->keySize) {
    00116             char *k = xmalloc(ht->keySize);
    00117             memcpy(k, key, ht->keySize);
    00118             b->key = k;
    00119         } else {
    00120             b->key = key;
    00121         }
    00122         b->dataCount = 0;
    00123         b->next = ht->buckets[hash];
    00124         b->data = NULL;
    00125         ht->buckets[hash] = b;
    00126     }
    00127     /*@=branchstate@*/
    00128
    00129     b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
    00130     b->data[b->dataCount++] = data;
    00131 }
    00132
    00133 void htFree(hashTable ht)
    00134 {
    00135     hashBucket b, n;
    00136     int i;
    00137
    00138     for (i = 0; i < ht->numBuckets; i++) {
    00139         b = ht->buckets[i];
    00140         if (b == NULL)
    00141             continue;
    00142         ht->buckets[i] = NULL;
    00143         if (ht->keySize > 0)
    00144             b->key = _free(b->key);
    00145         do {
    00146             n = b->next;
    00147             /*@-branchstate@*/
    00148             if (b->data) {
    00149                 if (ht->freeData)
    00150                     *b->data = _free(*b->data);
    00151                 b->data = _free(b->data);
    00152             }
    00153             /*@=branchstate@*/
    00154             b = _free(b);
    00155         } while ((b = n) != NULL);
    00156     }
    00157
    00158     ht->buckets = _free(ht->buckets);
    00159     ht = _free(ht);
    00160 }
    00161
    00162 int htHasEntry(hashTable ht, const void * key)
    00163 {
    00164     hashBucket b;
    00165
    00166     if (!(b = findEntry(ht, key))) return 0; else return 1;
    00167 }
    00168
    00169 int htGetEntry(hashTable ht, const void * key, const void *** data,
    00170                int * dataCount, const void ** tableKey)
    00171 {
    00172     hashBucket b;
    00173
    00174     if ((b = findEntry(ht, key)) == NULL)
    00175         return 1;
    00176
    00177     if (data)
    00178         *data = (const void **) b->data;
    00179     if (dataCount)
    00180         *dataCount = b->dataCount;
    00181     if (tableKey)
    00182         *tableKey = b->key;
    00183
    00184     return 0;
    00185 }