tools/fs_shell/hash.cpp

1 /* Generic hash table
35 	struct		hash_element **table;
51 next_element(hash_table *table, void *element)
54 	return (void *)(*(unsigned long *)NEXT_ADDR(table, element));
75 	t->table = (struct hash_element **)malloc(sizeof(void *) * table_size);
76 	if (t->table == NULL) {
82 		t->table[i] = NULL;
91 	TRACE(("hash_init: created table %p, next_ptr_offset %d, compare_func %p, hash_func %p\n",
99 hash_uninit(struct hash_table *table)
101 	ASSERT(table->num_elements == 0);
103 	free(table->table);
104 	free(table);
111 hash_insert(struct hash_table *table, void *element)
115 	ASSERT(table != NULL && element != NULL);
116 	TRACE(("hash_insert: table 0x%x, element 0x%x\n", table, element));
118 	hash = table->hash_func(element, NULL, table->table_size);
119 	PUT_IN_NEXT(table, element, table->table[hash]);
120 	table->table[hash] = (struct hash_element *)element;
121 	table->num_elements++;
123 	// ToDo: resize hash table if it's grown too much!
130 hash_remove(struct hash_table *table, void *_element)
132 	uint32_t hash = table->hash_func(_element, NULL, table->table_size);
135 	for (element = table->table[hash]; element != NULL;
136 			lastElement = element, element = NEXT(table, element)) {
140 				PUT_IN_NEXT(table, lastElement, NEXT(table, element));
142 				table->table[hash] = (struct hash_element *)NEXT(table, element);
143 			table->num_elements--;
154 hash_remove_current(struct hash_table *table, struct hash_iterator *iterator)
162 	for (element = table->table[index]; index < table->table_size; index++) {
171 					PUT_IN_NEXT(table, lastElement, NEXT(table, element));
173 					table->table[index] = (struct hash_element *)NEXT(table,
177 				table->num_elements--;
181 			element = NEXT(table, element);
188 hash_remove_first(struct hash_table *table, uint32_t *_cookie)
192 	for (index = _cookie ? *_cookie : 0; index < table->table_size; index++) {
193 		void *element = table->table[index];
196 			table->table[index] = (struct hash_element *)NEXT(table, element);
197 			table->num_elements--;
209 hash_find(struct hash_table *table, void *searchedElement)
211 	uint32_t hash = table->hash_func(searchedElement, NULL, table->table_size);
214 	for (element = table->table[hash]; element != NULL; element = NEXT(table, element)) {
224 hash_lookup(struct hash_table *table, const void *key)
226 	uint32_t hash = table->hash_func(NULL, key, table->table_size);
229 	for (element = table->table[hash]; element != NULL; element = NEXT(table, element)) {
230 		if (table->compare_func(element, key) == 0)
239 hash_open(struct hash_table *table, struct hash_iterator *iterator)
247 	hash_rewind(table, iterator);
254 hash_close(struct hash_table *table, struct hash_iterator *iterator, bool freeIterator)
262 hash_rewind(struct hash_table *table, struct hash_iterator *iterator)
270 hash_next(struct hash_table *table, struct hash_iterator *iterator)
277 		for (index = (uint32_t)(iterator->bucket + 1); index < table->table_size; index++) {
278 			if (table->table[index]) {
280 				iterator->current = table->table[index];
285 		iterator->current = NEXT(table, iterator->current);