Changeset 173
- Timestamp:
- Mar 9, 2004, 3:00:45 PM (22 years ago)
- Location:
- trunk/archive/pslib/src/Utils
- Files:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
trunk/archive/pslib/src/Utils/hash.c
r145 r173 31 31 * Con/Destruct buckets 32 32 */ 33 static HashBucket *hashBucket New(const char *key,34 void *data,35 HashBucket *next)33 static HashBucket *hashBucketAlloc(const char *key, 34 void *data, 35 HashBucket *next) 36 36 { 37 37 HashBucket *bucket = psAlloc(sizeof(HashBucket)); … … 44 44 } 45 45 46 static void hashBucket Del(46 static void hashBucketFree( 47 47 HashBucket *bucket, // bucket to free 48 void (*item Del)(void *item)) // how to free hashed data;48 void (*itemFree)(void *item)) // how to free hashed data; 49 49 // or NULL 50 50 { … … 56 56 psMemDecrRefCounter(bucket->data); 57 57 58 if (item Del!= NULL) {59 item Del(bucket->data);58 if (itemFree != NULL) { 59 itemFree(bucket->data); 60 60 } 61 61 … … 67 67 * Con/Destruct psHash tables 68 68 */ 69 psHash *psHash New(int nbucket)// initial number of buckets69 psHash *psHashAlloc(int nbucket) // initial number of buckets 70 70 { 71 71 psHash *table = psAlloc(sizeof(psHash)); … … 82 82 } 83 83 84 void psHash Del(psHash *table, // hash table to be freed85 void (*itemDel)(void *item)) // how to free hashed data; or NULL84 void psHashFree(psHash *table, // hash table to be freed 85 void (*itemFree)(void *item)) // how to free hashed data; or NULL 86 86 { 87 87 if (table == NULL) { … … 96 96 while (ptr != NULL) { 97 97 HashBucket *tmp = ptr->next; 98 hashBucket Del(ptr, itemDel);98 hashBucketFree(ptr, itemFree); 99 99 ptr = tmp; 100 100 } … … 108 108 /*****************************************************************************/ 109 109 /* 110 * Here's the routine to do the work of insertion/retrieval .110 * Here's the routine to do the work of insertion/retrieval/removal 111 111 * 112 * We need item Delif the key is already in use and we're inserting112 * We need itemFree if the key is already in use and we're inserting 113 113 * 114 114 * N.b. this is NOT a good hash function! See Knuth for some better ones … … 118 118 const char *key, // key to use 119 119 void *data, // data to insert, 120 // or (if NULL) retrieve 121 void (*itemDel)(void *item)) // how to free hashed data 120 // or (if NULL) retrieve/remove 121 int remove, // remove the item from the list? 122 void (*itemFree)(void *item)) // how to free hashed data 122 123 // or NULL 123 124 { … … 134 135 * We've found the correct hash bucket, now we need to know what to do 135 136 */ 136 if (data == NULL) { // retrieve 137 while (ptr != NULL) { 138 if (strcmp(key, ptr->key) == 0) { // found it! 139 return ptr->data; 140 } 141 142 ptr = ptr->next; 137 if (data == NULL) { // retrieve/remove 138 if (remove) { 139 HashBucket *optr = ptr; 140 while (ptr != NULL) { 141 if (strcmp(key, ptr->key) == 0) { // found it! 142 void *data = ptr->data; 143 optr->next = ptr->next; 144 145 if (ptr == table->buckets[hash]) { 146 table->buckets[hash] = ptr->next; 147 } 148 149 psFree(ptr->key); 150 psFree(ptr); 151 152 return psMemDecrRefCounter(data); // return data 153 } 154 155 optr = ptr; 156 ptr = ptr->next; 157 } 158 } else { 159 while (ptr != NULL) { 160 if (strcmp(key, ptr->key) == 0) { // found it! 161 return ptr->data; 162 } 163 164 ptr = ptr->next; 165 } 143 166 } 144 167 … … 147 170 while (ptr != NULL) { 148 171 if (strcmp(key, ptr->key) == 0) { // found it! 149 if (item Del== NULL) {172 if (itemFree == NULL) { 150 173 return NULL; // can't insert 151 174 } … … 154 177 key); 155 178 156 item Del(psMemDecrRefCounter(ptr->data));179 itemFree(psMemDecrRefCounter(ptr->data)); 157 180 ptr->data = psMemIncrRefCounter(data); 158 181 … … 163 186 * Not found, so insert at the front of the list 164 187 */ 165 table->buckets[hash] = hashBucket New(key, data, table->buckets[hash]);188 table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]); 166 189 167 190 return data; … … 176 199 const char *key, // key to use 177 200 void *data, // data to insert 178 void (*item Del)(void *item))// how to free hashed data;201 void (*itemFree)(void *item)) // how to free hashed data; 179 202 // or NULL 180 203 { 181 return doHashWork(table, key, data, itemDel);204 return doHashWork(table, key, data, 0, itemFree); 182 205 } 183 206 … … 189 212 const char *key) // key to lookup 190 213 { 191 return doHashWork(table, key, NULL, NULL); 214 return doHashWork(table, key, NULL, 0, NULL); 215 } 216 217 /*****************************************************************************/ 218 /* 219 * Remove and return a value from a hash table 220 */ 221 void *psHashRemove(psHash *table, // table to lookup key in 222 const char *key) // key to lookup 223 { 224 return doHashWork(table, key, NULL, 1, NULL); 192 225 } 193 226 … … 196 229 197 230 typedef struct { char *name; } ID; 198 static ID *Id New(const char *name)231 static ID *IdAlloc(const char *name) 199 232 { 200 233 ID *id = psAlloc(sizeof(ID)); … … 204 237 } 205 238 206 static void IdDel(ID *id) { 239 static void IdFree(ID *id) 240 { 207 241 if (psMemGetRefCounter(id) > 1) { 208 242 psMemDecrRefCounter(id); … … 219 253 long memId0 = psMemGetId(); 220 254 221 psHash *hash = psHash New(16);222 223 psHashInsert(hash, "Lynda", Id New("Lee"), (void (*)(void *))IdDel);224 psHashInsert(hash, "Lynda", Id New("Lee"), (void (*)(void *))IdDel);225 psHashInsert(hash, "Robert", Id New("Lupton"), (void (*)(void *))IdDel);226 psHashInsert(hash, "Robert", Id New("the Good"), (void (*)(void *))IdDel);255 psHash *hash = psHashAlloc(16); 256 257 psHashInsert(hash, "Lynda", IdAlloc("Lee"), (void (*)(void *))IdFree); 258 psHashInsert(hash, "Lynda", IdAlloc("Lee"), (void (*)(void *))IdFree); 259 psHashInsert(hash, "Robert", IdAlloc("Lupton"), (void (*)(void *))IdFree); 260 psHashInsert(hash, "Robert", IdAlloc("the Good"), (void (*)(void *))IdFree); 227 261 228 262 char *names[] = {"Robert", "Lynda", "Rowan", NULL}; … … 233 267 } 234 268 235 psHash Del(hash, (void (*)(void *))IdDel);269 psHashFree(hash, (void (*)(void *))IdFree); 236 270 /* 237 271 * Check for memory leaks -
trunk/archive/pslib/src/Utils/psHash.h
r141 r173 4 4 typedef struct HashTable psHash; 5 5 6 psHash *psHash New(int nbucket);// initial number of buckets7 void psHash Del(psHash *table, // hash table to be freed8 void (*itemDel)(void *item)); // how to free hashed data;6 psHash *psHashAlloc(int nbucket); // initial number of buckets 7 void psHashFree(psHash *table, // hash table to be freed 8 void (*itemFree)(void *item)); // how to free hashed data; 9 9 // or NULL 10 10 … … 12 12 const char *key, // key to use 13 13 void *data, // data to insert 14 void (*item Del)(void *item)); // how to free hashed data;14 void (*itemFree)(void *item)); // how to free hashed data; 15 15 // or NULL 16 16 void *psHashLookup(psHash *table, // table to lookup key in 17 17 const char *key); // key to lookup 18 18 19 void *psHashRemove(psHash *table, // table to lookup key in 20 const char *key); // key to lookup 19 21 #endif
Note:
See TracChangeset
for help on using the changeset viewer.
