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

Generated at Thu Sep 6 11:32:32 2001 for rpm by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001