Main Page Modules Data Structures File List Data Fields Globals Related Pages

# 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 /*@-boundsread@*/
    00051     b = ht->buckets[hash];
    00052 /*@=boundsread@*/
    00053
    00054     while (b && b->key && ht->eq(b->key, key))
    00055         b = b->next;
    00056     /*@=modunconnomods@*/
    00057
    00058     return b;
    00059 }
    00060
    00061 int hashEqualityString(const void * key1, const void * key2)
    00062 {
    00063     const char *k1 = (const char *)key1;
    00064     const char *k2 = (const char *)key2;
    00065     return strcmp(k1, k2);
    00066 }
    00067
    00068 unsigned int hashFunctionString(const void * string)
    00069 {
    00070     char xorValue = 0;
    00071     char sum = 0;
    00072     short len;
    00073     int i;
    00074     const char * chp = string;
    00075
    00076     len = strlen(string);
    00077 /*@-boundsread@*/
    00078     for (i = 0; i < len; i++, chp++) {
    00079         xorValue ^= *chp;
    00080         sum += *chp;
    00081     }
    00082 /*@=boundsread@*/
    00083
    00084     return ((((unsigned)len) << 16) + (((unsigned)sum) << 8) + xorValue);
    00085 }
    00086
    00087 hashTable htCreate(int numBuckets, int keySize, int freeData,
    00088                 hashFunctionType fn, hashEqualityType eq)
    00089 {
    00090     hashTable ht;
    00091
    00092     ht = xmalloc(sizeof(*ht));
    00093     ht->numBuckets = numBuckets;
    00094     ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
    00095     ht->keySize = keySize;
    00096     ht->freeData = freeData;
    00097     /*@-assignexpose@*/
    00098     ht->fn = fn;
    00099     ht->eq = eq;
    00100     /*@=assignexpose@*/
    00101
    00102     return ht;
    00103 }
    00104
    00105 /*@-boundswrite@*/
    00106 void htAddEntry(hashTable ht, const void * key, const void * data)
    00107 {
    00108     unsigned int hash;
    00109     hashBucket b;
    00110
    00111     hash = ht->fn(key) % ht->numBuckets;
    00112     b = ht->buckets[hash];
    00113
    00114     while (b && b->key && ht->eq(b->key, key))
    00115         b = b->next;
    00116
    00117     /*@-branchstate@*/
    00118     if (b == NULL) {
    00119         b = xmalloc(sizeof(*b));
    00120         if (ht->keySize) {
    00121             char *k = xmalloc(ht->keySize);
    00122             memcpy(k, key, ht->keySize);
    00123             b->key = k;
    00124         } else {
    00125             b->key = key;
    00126         }
    00127         b->dataCount = 0;
    00128         b->next = ht->buckets[hash];
    00129         b->data = NULL;
    00130         ht->buckets[hash] = b;
    00131     }
    00132     /*@=branchstate@*/
    00133
    00134     b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
    00135     b->data[b->dataCount++] = data;
    00136 }
    00137 /*@=boundswrite@*/
    00138
    00139 hashTable htFree(hashTable ht)
    00140 {
    00141     hashBucket b, n;
    00142     int i;
    00143
    00144     for (i = 0; i < ht->numBuckets; i++) {
    00145 /*@-boundsread@*/
    00146         b = ht->buckets[i];
    00147 /*@=boundsread@*/
    00148         if (b == NULL)
    00149             continue;
    00150 /*@-boundswrite@*/
    00151         ht->buckets[i] = NULL;
    00152 /*@=boundswrite@*/
    00153         if (ht->keySize > 0)
    00154             b->key = _free(b->key);
    00155         do {
    00156             n = b->next;
    00157             /*@-branchstate@*/
    00158             if (b->data) {
    00159 /*@-boundswrite@*/
    00160                 if (ht->freeData)
    00161                     *b->data = _free(*b->data);
    00162 /*@=boundswrite@*/
    00163                 b->data = _free(b->data);
    00164             }
    00165             /*@=branchstate@*/
    00166             b = _free(b);
    00167         } while ((b = n) != NULL);
    00168     }
    00169
    00170     ht->buckets = _free(ht->buckets);
    00171     ht = _free(ht);
    00172     return NULL;
    00173 }
    00174
    00175 int htHasEntry(hashTable ht, const void * key)
    00176 {
    00177     hashBucket b;
    00178
    00179     if (!(b = findEntry(ht, key))) return 0; else return 1;
    00180 }
    00181
    00182 int htGetEntry(hashTable ht, const void * key, const void *** data,
    00183                int * dataCount, const void ** tableKey)
    00184 {
    00185     hashBucket b;
    00186
    00187     if ((b = findEntry(ht, key)) == NULL)
    00188         return 1;
    00189
    00190 /*@-boundswrite@*/
    00191     if (data)
    00192         *data = (const void **) b->data;
    00193     if (dataCount)
    00194         *dataCount = b->dataCount;
    00195     if (tableKey)
    00196         *tableKey = b->key;
    00197 /*@=boundswrite@*/
    00198
    00199     return 0;
    00200 }