1/* 2 * Copyright (C) 2006-2010 B.A.T.M.A.N. contributors: 3 * 4 * Simon Wunderlich, Marek Lindner 5 * 6 * This program is free software; you can redistribute it and/or 7 * modify it under the terms of version 2 of the GNU General Public 8 * License as published by the Free Software Foundation. 9 * 10 * This program is distributed in the hope that it will be useful, but 11 * WITHOUT ANY WARRANTY; without even the implied warranty of 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 13 * General Public License for more details. 14 * 15 * You should have received a copy of the GNU General Public License 16 * along with this program; if not, write to the Free Software 17 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 18 * 02110-1301, USA 19 * 20 */ 21 22#ifndef _NET_BATMAN_ADV_HASH_H_ 23#define _NET_BATMAN_ADV_HASH_H_ 24 25#define HASHIT(name) struct hash_it_t name = { \ 26 .index = -1, .bucket = NULL, \ 27 .prev_bucket = NULL, \ 28 .first_bucket = NULL } 29 30 31typedef int (*hashdata_compare_cb)(void *, void *); 32typedef int (*hashdata_choose_cb)(void *, int); 33typedef void (*hashdata_free_cb)(void *); 34 35struct element_t { 36 void *data; /* pointer to the data */ 37 struct element_t *next; /* overflow bucket pointer */ 38}; 39 40struct hash_it_t { 41 int index; 42 struct element_t *bucket; 43 struct element_t *prev_bucket; 44 struct element_t **first_bucket; 45}; 46 47struct hashtable_t { 48 struct element_t **table; /* the hashtable itself, with the buckets */ 49 int elements; /* number of elements registered */ 50 int size; /* size of hashtable */ 51 hashdata_compare_cb compare;/* callback to a compare function. should 52 * compare 2 element datas for their keys, 53 * return 0 if same and not 0 if not 54 * same */ 55 hashdata_choose_cb choose; /* the hashfunction, should return an index 56 * based on the key in the data of the first 57 * argument and the size the second */ 58}; 59 60/* allocates and clears the hash */ 61struct hashtable_t *hash_new(int size, hashdata_compare_cb compare, 62 hashdata_choose_cb choose); 63 64/* remove bucket (this might be used in hash_iterate() if you already found the 65 * bucket you want to delete and don't need the overhead to find it again with 66 * hash_remove(). But usually, you don't want to use this function, as it 67 * fiddles with hash-internals. */ 68void *hash_remove_bucket(struct hashtable_t *hash, struct hash_it_t *hash_it_t); 69 70/* remove the hash structure. if hashdata_free_cb != NULL, this function will be 71 * called to remove the elements inside of the hash. if you don't remove the 72 * elements, memory might be leaked. */ 73void hash_delete(struct hashtable_t *hash, hashdata_free_cb free_cb); 74 75/* free only the hashtable and the hash itself. */ 76void hash_destroy(struct hashtable_t *hash); 77 78/* adds data to the hashtable. returns 0 on success, -1 on error */ 79int hash_add(struct hashtable_t *hash, void *data); 80 81/* removes data from hash, if found. returns pointer do data on success, so you 82 * can remove the used structure yourself, or NULL on error . data could be the 83 * structure you use with just the key filled, we just need the key for 84 * comparing. */ 85void *hash_remove(struct hashtable_t *hash, void *data); 86 87/* finds data, based on the key in keydata. returns the found data on success, 88 * or NULL on error */ 89void *hash_find(struct hashtable_t *hash, void *keydata); 90 91/* resize the hash, returns the pointer to the new hash or NULL on 92 * error. removes the old hash on success */ 93struct hashtable_t *hash_resize(struct hashtable_t *hash, int size); 94 95/* iterate though the hash. first element is selected with iter_in NULL. use 96 * the returned iterator to access the elements until hash_it_t returns NULL. */ 97struct hash_it_t *hash_iterate(struct hashtable_t *hash, 98 struct hash_it_t *iter_in); 99 100#endif /* _NET_BATMAN_ADV_HASH_H_ */ 101