Main Page   Modules   Compound List   File List   Compound Members   File Members   Related Pages  

lib/hash.c

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

Generated at Mon May 21 08:53:39 2001 for rpm by doxygen1.2.6 written by Dimitri van Heesch, © 1997-2001