rpmio/rpmhash.c

Go to the documentation of this file.
00001 
00006 #include "system.h"
00007 #include <rpmhash.h>
00008 #include "debug.h"
00009 
00010 typedef /*@owned@*/ const void * voidptr;
00011 
00012 typedef struct hashBucket_s * hashBucket;
00013 
00016 struct hashBucket_s {
00017     voidptr key;                        
00018 /*@owned@*/ voidptr * data;             
00019     int dataCount;                      
00020 /*@dependent@*/hashBucket next;         
00021 };
00022 
00025 struct hashTable_s {
00026     int numBuckets;                     
00027     int keySize;                        
00028     int freeData;       
00029     hashBucket * buckets;               
00030     hashFunctionType fn;                
00031     hashEqualityType eq;                
00032 };
00033 
00039 /*@unused@*/ static inline /*@null@*/ void *
00040 _free(/*@only@*/ /*@null@*/ const void * p) /*@modifies p@*/
00041 {
00042     if (p != NULL)      free((void *)p);
00043     return NULL;
00044 }
00045 
00052 static /*@shared@*/ /*@null@*/
00053 hashBucket findEntry(hashTable ht, const void * key)
00054         /*@*/
00055 {
00056     uint32_t hash = 0;
00057     hashBucket b;
00058 
00059     /*@-modunconnomods@*/
00060     hash = ht->fn(hash, key, 0) % ht->numBuckets;
00061 /*@-boundsread@*/
00062     b = ht->buckets[hash];
00063 /*@=boundsread@*/
00064 
00065     while (b && b->key && ht->eq(b->key, key))
00066         b = b->next;
00067     /*@=modunconnomods@*/
00068 
00069     return b;
00070 }
00071 
00079 static uint32_t hashFunctionString(uint32_t h, const void * data, size_t size)
00080         /*@*/
00081 {
00082     const char * chp = data;
00083     unsigned char sum = 0;
00084     unsigned char xor = 0;
00085     int i;
00086 
00087     if (size == 0)
00088         size = strlen(chp);
00089 /*@-boundsread@*/
00090     for (i = 0; i < size; i++, chp++) {
00091         xor ^= *chp;
00092         sum += *chp;
00093     }
00094 /*@=boundsread@*/
00095 
00096     h += ((size << 16) + (sum << 8) + xor);
00097 
00098     return h;
00099 }
00100 
00107 static int hashEqualityString(const void * key1, const void * key2)
00108         /*@*/
00109 {
00110     const char *k1 = (const char *)key1;
00111     const char *k2 = (const char *)key2;
00112     return strcmp(k1, k2);
00113 }
00114 
00115 hashTable htCreate(int numBuckets, int keySize, int freeData,
00116                 hashFunctionType fn, hashEqualityType eq)
00117 {
00118     hashTable ht;
00119 
00120     ht = xmalloc(sizeof(*ht));
00121     ht->numBuckets = numBuckets;
00122     ht->buckets = xcalloc(numBuckets, sizeof(*ht->buckets));
00123     ht->keySize = keySize;
00124     ht->freeData = freeData;
00125     /*@-assignexpose@*/
00126     ht->fn = (fn != NULL ? fn : hashFunctionString);
00127     ht->eq = (eq != NULL ? eq : hashEqualityString);
00128     /*@=assignexpose@*/
00129 
00130     return ht;
00131 }
00132 
00133 /*@-boundswrite@*/
00134 void htAddEntry(hashTable ht, const void * key, const void * data)
00135 {
00136     uint32_t hash = 0;
00137     hashBucket b;
00138 
00139     hash = ht->fn(hash, key, 0) % ht->numBuckets;
00140     b = ht->buckets[hash];
00141 
00142     while (b && b->key && ht->eq(b->key, key))
00143         b = b->next;
00144 
00145     /*@-branchstate@*/
00146     if (b == NULL) {
00147         b = xmalloc(sizeof(*b));
00148         if (ht->keySize) {
00149             char *k = xmalloc(ht->keySize);
00150             memcpy(k, key, ht->keySize);
00151             b->key = k;
00152         } else {
00153             b->key = key;
00154         }
00155         b->dataCount = 0;
00156         b->next = ht->buckets[hash];
00157         b->data = NULL;
00158         ht->buckets[hash] = b;
00159     }
00160     /*@=branchstate@*/
00161 
00162     b->data = xrealloc(b->data, sizeof(*b->data) * (b->dataCount + 1));
00163     b->data[b->dataCount++] = data;
00164 }
00165 /*@=boundswrite@*/
00166 
00167 hashTable htFree(hashTable ht)
00168 {
00169     hashBucket b, n;
00170     int i;
00171 
00172     for (i = 0; i < ht->numBuckets; i++) {
00173 /*@-boundsread@*/
00174         b = ht->buckets[i];
00175 /*@=boundsread@*/
00176         if (b == NULL)
00177             continue;
00178 /*@-boundswrite@*/
00179         ht->buckets[i] = NULL;
00180 /*@=boundswrite@*/
00181         if (ht->keySize > 0)
00182             b->key = _free(b->key);
00183         do {
00184             n = b->next;
00185             /*@-branchstate@*/
00186             if (b->data) {
00187 /*@-boundswrite@*/
00188                 if (ht->freeData)
00189                     *b->data = _free(*b->data);
00190 /*@=boundswrite@*/
00191                 b->data = _free(b->data);
00192             }
00193             /*@=branchstate@*/
00194             b = _free(b);
00195         } while ((b = n) != NULL);
00196     }
00197 
00198     ht->buckets = _free(ht->buckets);
00199     ht = _free(ht);
00200     return NULL;
00201 }
00202 
00203 int htHasEntry(hashTable ht, const void * key)
00204 {
00205     hashBucket b;
00206 
00207     if (!(b = findEntry(ht, key))) return 0; else return 1;
00208 }
00209 
00210 int htGetEntry(hashTable ht, const void * key, const void *** data,
00211                int * dataCount, const void ** tableKey)
00212 {
00213     hashBucket b;
00214 
00215     if ((b = findEntry(ht, key)) == NULL)
00216         return 1;
00217 
00218 /*@-boundswrite@*/
00219     if (data)
00220         *data = (const void **) b->data;
00221     if (dataCount)
00222         *dataCount = b->dataCount;
00223     if (tableKey)
00224         *tableKey = b->key;
00225 /*@=boundswrite@*/
00226 
00227     return 0;
00228 }

Generated on Mon Aug 3 15:21:32 2009 for rpm by  doxygen 1.5.1