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 }

Generated on Wed Mar 8 22:44:25 2006 for rpm by  doxygen 1.4.6