Lines Matching refs:table
3 /*--- A separately-chained hash table. m_hashtable.c ---*/
51 Bool iterOK; // table safe to iterate over?
52 const HChar* name; // name of table (for debugging only)
74 VgHashTable *table = VG_(calloc)("hashtable.Hc.1",
76 table->chains = VG_(calloc)("hashtable.Hc.2", 1, sz);
77 table->n_chains = n_chains;
78 table->n_elements = 0;
79 table->iterOK = True;
80 table->name = name;
82 return table;
85 UInt VG_(HT_count_nodes) ( const VgHashTable *table )
87 return table->n_elements;
90 static void resize ( VgHashTable *table )
94 SizeT old_chains = table->n_chains;
119 "resizing table `%s' from %lu to %lu (total elems %lu)\n",
120 table->name, (UWord)old_chains, (UWord)new_chains,
121 (UWord)table->n_elements );
123 table->n_chains = new_chains;
128 node = table->chains[i];
131 UWord chain = CHAIN_NO(node->key, table);
138 VG_(free)(table->chains);
139 table->chains = chains;
144 void VG_(HT_add_node) ( VgHashTable *table, void* vnode )
147 UWord chain = CHAIN_NO(node->key, table);
148 node->next = table->chains[chain];
149 table->chains[chain] = node;
150 table->n_elements++;
151 if ( (1 * (ULong)table->n_elements) > (1 * (ULong)table->n_chains) ) {
152 resize(table);
155 /* Table has been modified; hence HT_Next should assert. */
156 table->iterOK = False;
159 /* Looks up a VgHashNode by key in the table. Returns NULL if not found. */
160 void* VG_(HT_lookup) ( const VgHashTable *table, UWord key )
162 VgHashNode* curr = table->chains[ CHAIN_NO(key, table) ];
173 /* Looks up a VgHashNode by node in the table. Returns NULL if not found.
175 void* VG_(HT_gen_lookup) ( const VgHashTable *table, const void* node,
179 VgHashNode* curr = table->chains[ CHAIN_NO(hnode->key, table) ]; // GEN!!!
190 /* Removes a VgHashNode from the table. Returns NULL if not found. */
191 void* VG_(HT_remove) ( VgHashTable *table, UWord key )
193 UWord chain = CHAIN_NO(key, table);
194 VgHashNode* curr = table->chains[chain];
195 VgHashNode** prev_next_ptr = &(table->chains[chain]);
197 /* Table has been modified; hence HT_Next should assert. */
198 table->iterOK = False;
203 table->n_elements--;
212 /* Removes a VgHashNode by node from the table. Returns NULL if not found.
214 void* VG_(HT_gen_remove) ( VgHashTable *table, const void* node, HT_Cmp_t cmp )
217 UWord chain = CHAIN_NO(hnode->key, table); // GEN!!!
218 VgHashNode* curr = table->chains[chain];
219 VgHashNode** prev_next_ptr = &(table->chains[chain]);
221 /* Table has been modified; hence HT_Next should assert. */
222 table->iterOK = False;
227 table->n_elements--;
236 void VG_(HT_print_stats) ( const VgHashTable *table, HT_Cmp_t cmp )
256 // but if that happens, the hash table/function is really bad and that
258 for (i = 0; i < table->n_chains; i++) {
260 for (cnode = table->chains[i]; cnode != NULL; cnode = cnode->next) {
265 for (node = table->chains[i]; node != cnode; node = node->next) {
280 for (node = table->chains[i]; node != cnode; node = node->next) {
331 VgHashNode** VG_(HT_to_array) (const VgHashTable *table, /*OUT*/ UInt* n_elems)
337 *n_elems = table->n_elements;
344 for (i = 0; i < table->n_chains; i++) {
345 for (node = table->chains[i]; node != NULL; node = node->next) {
354 void VG_(HT_ResetIter)(VgHashTable *table)
356 vg_assert(table);
357 table->iterNode = NULL;
358 table->iterChain = 0;
359 table->iterOK = True;
362 void* VG_(HT_Next)(VgHashTable *table)
365 vg_assert(table);
368 table whilst iterating over it, which is a bug. */
369 vg_assert(table->iterOK);
371 if (table->iterNode && table->iterNode->next) {
372 table->iterNode = table->iterNode->next;
373 return table->iterNode;
376 for (i = table->iterChain; i < table->n_chains; i++) {
377 if (table->chains[i]) {
378 table->iterNode = table->chains[i];
379 table->iterChain = i + 1; // Next chain to be traversed
380 return table->iterNode;
386 void VG_(HT_destruct)(VgHashTable *table, void(*freenode_fn)(void*))
391 for (i = 0; i < table->n_chains; i++) {
392 for (node = table->chains[i]; node != NULL; node = node_next) {
397 VG_(free)(table->chains);
398 VG_(free)(table);
