blob: dd5c9fd7a905db74e76920bb5e705f616043f941 [file] [log] [blame]
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +00001/*
Sven Eckelmann64afe352011-01-27 10:38:15 +01002 * Copyright (C) 2006-2011 B.A.T.M.A.N. contributors:
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +00003 *
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#include <linux/list.h>
26
27/* callback to a compare function. should
28 * compare 2 element datas for their keys,
29 * return 0 if same and not 0 if not
30 * same */
Sven Eckelmann747e4222011-05-14 23:14:50 +020031typedef int (*hashdata_compare_cb)(const struct hlist_node *, const void *);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000032
33/* the hashfunction, should return an index
34 * based on the key in the data of the first
35 * argument and the size the second */
Sven Eckelmann747e4222011-05-14 23:14:50 +020036typedef int (*hashdata_choose_cb)(const void *, int);
Marek Lindner7aadf882011-02-18 12:28:09 +000037typedef void (*hashdata_free_cb)(struct hlist_node *, void *);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000038
39struct hashtable_t {
Marek Lindnerfb778ea2011-01-19 20:01:40 +000040 struct hlist_head *table; /* the hashtable itself with the buckets */
41 spinlock_t *list_locks; /* spinlock for each hash list entry */
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000042 int size; /* size of hashtable */
43};
44
45/* allocates and clears the hash */
46struct hashtable_t *hash_new(int size);
47
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000048/* free only the hashtable and the hash itself. */
49void hash_destroy(struct hashtable_t *hash);
50
51/* remove the hash structure. if hashdata_free_cb != NULL, this function will be
52 * called to remove the elements inside of the hash. if you don't remove the
53 * elements, memory might be leaked. */
54static inline void hash_delete(struct hashtable_t *hash,
55 hashdata_free_cb free_cb, void *arg)
56{
57 struct hlist_head *head;
Marek Lindner7aadf882011-02-18 12:28:09 +000058 struct hlist_node *node, *node_tmp;
Marek Lindnerfb778ea2011-01-19 20:01:40 +000059 spinlock_t *list_lock; /* spinlock to protect write access */
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000060 int i;
61
62 for (i = 0; i < hash->size; i++) {
63 head = &hash->table[i];
Marek Lindnerfb778ea2011-01-19 20:01:40 +000064 list_lock = &hash->list_locks[i];
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000065
Marek Lindnerfb778ea2011-01-19 20:01:40 +000066 spin_lock_bh(list_lock);
Marek Lindner7aadf882011-02-18 12:28:09 +000067 hlist_for_each_safe(node, node_tmp, head) {
68 hlist_del_rcu(node);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000069
Marek Lindner7aadf882011-02-18 12:28:09 +000070 if (free_cb)
71 free_cb(node, arg);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000072 }
Marek Lindnerfb778ea2011-01-19 20:01:40 +000073 spin_unlock_bh(list_lock);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000074 }
75
76 hash_destroy(hash);
77}
78
79/* adds data to the hashtable. returns 0 on success, -1 on error */
80static inline int hash_add(struct hashtable_t *hash,
81 hashdata_compare_cb compare,
Marek Lindner7aadf882011-02-18 12:28:09 +000082 hashdata_choose_cb choose,
Sven Eckelmann747e4222011-05-14 23:14:50 +020083 const void *data, struct hlist_node *data_node)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000084{
85 int index;
86 struct hlist_head *head;
Marek Lindner7aadf882011-02-18 12:28:09 +000087 struct hlist_node *node;
Marek Lindnerfb778ea2011-01-19 20:01:40 +000088 spinlock_t *list_lock; /* spinlock to protect write access */
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000089
90 if (!hash)
Marek Lindnerfb778ea2011-01-19 20:01:40 +000091 goto err;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000092
93 index = choose(data, hash->size);
94 head = &hash->table[index];
Marek Lindnerfb778ea2011-01-19 20:01:40 +000095 list_lock = &hash->list_locks[index];
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000096
Marek Lindnerfb778ea2011-01-19 20:01:40 +000097 rcu_read_lock();
Marek Lindner7aadf882011-02-18 12:28:09 +000098 __hlist_for_each_rcu(node, head) {
99 if (!compare(node, data))
100 continue;
101
102 goto err_unlock;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000103 }
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000104 rcu_read_unlock();
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000105
106 /* no duplicate found in list, add new element */
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000107 spin_lock_bh(list_lock);
Marek Lindner7aadf882011-02-18 12:28:09 +0000108 hlist_add_head_rcu(data_node, head);
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000109 spin_unlock_bh(list_lock);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000110
111 return 0;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000112
113err_unlock:
114 rcu_read_unlock();
115err:
116 return -1;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000117}
118
119/* removes data from hash, if found. returns pointer do data on success, so you
120 * can remove the used structure yourself, or NULL on error . data could be the
121 * structure you use with just the key filled, we just need the key for
122 * comparing. */
123static inline void *hash_remove(struct hashtable_t *hash,
124 hashdata_compare_cb compare,
125 hashdata_choose_cb choose, void *data)
126{
127 size_t index;
Marek Lindner7aadf882011-02-18 12:28:09 +0000128 struct hlist_node *node;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000129 struct hlist_head *head;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000130 void *data_save = NULL;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000131
132 index = choose(data, hash->size);
133 head = &hash->table[index];
134
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000135 spin_lock_bh(&hash->list_locks[index]);
Marek Lindner7aadf882011-02-18 12:28:09 +0000136 hlist_for_each(node, head) {
137 if (!compare(node, data))
138 continue;
139
140 data_save = node;
141 hlist_del_rcu(node);
142 break;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000143 }
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000144 spin_unlock_bh(&hash->list_locks[index]);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000145
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000146 return data_save;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000147}
148
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000149#endif /* _NET_BATMAN_ADV_HASH_H_ */