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