Changeset e1da7ec in mainline
 Timestamp:
 20100417T01:24:17Z (12 years ago)
 Branches:
 lfn, master
 Children:
 ab108be4
 Parents:
 3292623
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

uspace/lib/c/generic/adt/hash_table.c
r3292623 re1da7ec 42 42 #include <malloc.h> 43 43 #include <assert.h> 44 #include <stdio.h>45 44 #include <str.h> 46 45 47 46 /** Create chained hash table. 48 47 * 49 * @param h Hash table structure. Will be initialized by this call. 50 * @param m Number of hash table buckets. 51 * @param max_keys Maximal number of keys needed to identify an item. 52 * @param op Hash table operations structure. 53 * @return True on success 48 * @param h Hash table structure. Will be initialized by this call. 49 * @param m Number of hash table buckets. 50 * @param max_keys Maximal number of keys needed to identify an item. 51 * @param op Hash table operations structure. 52 * 53 * @return True on success 54 * 54 55 */ 55 56 int hash_table_create(hash_table_t *h, hash_count_t m, hash_count_t max_keys, 56 57 hash_table_operations_t *op) 57 58 { 58 hash_count_t i;59 60 59 assert(h); 61 60 assert(op && op>hash && op>compare); … … 63 62 64 63 h>entry = malloc(m * sizeof(link_t)); 65 if (!h>entry) { 66 printf("cannot allocate memory for hash table\n"); 64 if (!h>entry) 67 65 return false; 68 }66 69 67 memset((void *) h>entry, 0, m * sizeof(link_t)); 70 68 69 hash_count_t i; 71 70 for (i = 0; i < m; i++) 72 71 list_initialize(&h>entry[i]); … … 75 74 h>max_keys = max_keys; 76 75 h>op = op; 76 77 77 return true; 78 78 } … … 80 80 /** Destroy a hash table instance. 81 81 * 82 * @param h Hash table to be destroyed. 82 * @param h Hash table to be destroyed. 83 * 83 84 */ 84 85 void hash_table_destroy(hash_table_t *h) … … 86 87 assert(h); 87 88 assert(h>entry); 89 88 90 free(h>entry); 89 91 } … … 91 93 /** Insert item into a hash table. 92 94 * 93 * @param h 94 * @param key 95 * @param item 95 * @param h Hash table. 96 * @param key Array of all keys necessary to compute hash index. 97 * @param item Item to be inserted into the hash table. 96 98 */ 97 99 void hash_table_insert(hash_table_t *h, unsigned long key[], link_t *item) 98 100 { 99 hash_index_t chain;100 101 101 assert(item); 102 102 assert(h && h>op && h>op>hash && h>op>compare); 103 104 chain = h>op>hash(key);103 104 hash_index_t chain = h>op>hash(key); 105 105 assert(chain < h>entries); 106 106 … … 110 110 /** Search hash table for an item matching keys. 111 111 * 112 * @param h Hash table. 113 * @param key Array of all keys needed to compute hash index. 114 * 115 * @return Matching item on success, NULL if there is no such item. 112 * @param h Hash table. 113 * @param key Array of all keys needed to compute hash index. 114 * 115 * @return Matching item on success, NULL if there is no such item. 116 * 116 117 */ 117 118 link_t *hash_table_find(hash_table_t *h, unsigned long key[]) 118 119 { 120 assert(h && h>op && h>op>hash && h>op>compare); 121 122 hash_index_t chain = h>op>hash(key); 123 assert(chain < h>entries); 124 119 125 link_t *cur; 120 hash_index_t chain;121 122 assert(h && h>op && h>op>hash && h>op>compare);123 124 chain = h>op>hash(key);125 assert(chain < h>entries);126 127 126 for (cur = h>entry[chain].next; cur != &h>entry[chain]; 128 127 cur = cur>next) { … … 142 141 * For each removed item, h>remove_callback() is called. 143 142 * 144 * @param h Hash table. 145 * @param key Array of keys that will be compared against items of 146 * the hash table. 147 * @param keys Number of keys in the 'key' array. 143 * @param h Hash table. 144 * @param key Array of keys that will be compared against items of 145 * the hash table. 146 * @param keys Number of keys in the 'key' array. 147 * 148 148 */ 149 149 void hash_table_remove(hash_table_t *h, unsigned long key[], hash_count_t keys) 150 150 { 151 hash_index_t chain;152 link_t *cur;153 154 151 assert(h && h>op && h>op>hash && h>op>compare && 155 152 h>op>remove_callback); 156 153 assert(keys <= h>max_keys); 157 154 155 link_t *cur; 156 158 157 if (keys == h>max_keys) { 159 160 158 /* 161 159 * All keys are known, hash_table_find() can be used to find the 162 160 * entry. 163 161 */ 164 162 165 163 cur = hash_table_find(h, key); 166 164 if (cur) { … … 168 166 h>op>remove_callback(cur); 169 167 } 168 170 169 return; 171 170 } … … 175 174 * Any partially matching entries are to be removed. 176 175 */ 176 hash_index_t chain; 177 177 for (chain = 0; chain < h>entries; chain++) { 178 178 for (cur = h>entry[chain].next; cur != &h>entry[chain]; … … 195 195 /** Apply fucntion to all items in hash table. 196 196 * 197 * @param h 198 * @param f 199 * @param arg 200 * /201 void 202 hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg)197 * @param h Hash table. 198 * @param f Function to be applied. 199 * @param arg Argument to be passed to the function. 200 * 201 */ 202 void hash_table_apply(hash_table_t *h, void (*f)(link_t *, void *), void *arg) 203 203 { 204 204 hash_index_t bucket; 205 205 link_t *cur; 206 206 207 207 for (bucket = 0; bucket < h>entries; bucket++) { 208 208 for (cur = h>entry[bucket].next; cur != &h>entry[bucket];
Note: See TracChangeset
for help on using the changeset viewer.