rpm
4.5
|
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 }