1/*
2 * Copyright 2002-2008, Haiku Inc. All rights reserved.
3 * Distributed under the terms of the MIT License.
4 *
5 * Copyright 2001-2002, Travis Geiselbrecht. All rights reserved.
6 * Distributed under the terms of the NewOS License.
7 */
8#ifndef _KERNEL_UTIL_KHASH_H
9#define _KERNEL_UTIL_KHASH_H
10
11
12#include <SupportDefs.h>
13
14// The use of offsetof() on non-PODs is invalid. Since many structs use
15// templated members (i.e. DoublyLinkedList) which makes them non-PODs we
16// can't use offsetof() anymore. This macro does the same, but requires an
17// instance of the object in question.
18#define offset_of_member(OBJECT, MEMBER) \
19	((size_t)((char*)&OBJECT.MEMBER - (char*)&OBJECT))
20
21// can be allocated on the stack
22typedef struct hash_iterator {
23	void *current;
24	int bucket;
25} hash_iterator;
26
27typedef struct hash_table hash_table;
28
29#ifdef __cplusplus
30extern "C" {
31#endif
32
33struct hash_table *hash_init(uint32 table_size, int next_ptr_offset,
34	int compare_func(void *element, const void *key),
35	uint32 hash_func(void *element, const void *key, uint32 range));
36int hash_uninit(struct hash_table *table);
37status_t hash_insert(struct hash_table *table, void *_element);
38status_t hash_insert_grow(struct hash_table *table, void *_element);
39status_t hash_remove(struct hash_table *table, void *_element);
40void hash_remove_current(struct hash_table *table, struct hash_iterator *iterator);
41void *hash_remove_first(struct hash_table *table, uint32 *_cookie);
42void *hash_find(struct hash_table *table, void *e);
43void *hash_lookup(struct hash_table *table, const void *key);
44struct hash_iterator *hash_open(struct hash_table *table, struct hash_iterator *i);
45void hash_close(struct hash_table *table, struct hash_iterator *i, bool free_iterator);
46void *hash_next(struct hash_table *table, struct hash_iterator *i);
47void hash_rewind(struct hash_table *table, struct hash_iterator *i);
48uint32 hash_count_elements(struct hash_table *table);
49uint32 hash_count_used_slots(struct hash_table *table);
50void hash_dump_table(struct hash_table* table);
51
52/* function pointers must look like this:
53 *
54 * uint32 hash_func(void *e, const void *key, uint32 range);
55 *		hash function should calculate hash on either e or key,
56 *		depending on which one is not NULL - they also need
57 *		to make sure the returned value is within range.
58 * int compare_func(void *e, const void *key);
59 *		compare function should compare the element with
60 *		the key, returning 0 if equal, other if not
61 */
62
63uint32 hash_hash_string(const char *str);
64
65#ifdef __cplusplus
66}
67#endif
68
69#endif	/* _KERNEL_UTIL_KHASH_H */
70