blob: 4768717f07f9f850ccefd681fa75c93c4d09363a [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 */
Antonio Quartullic90681b2011-10-05 17:05:25 +020036typedef uint32_t (*hashdata_choose_cb)(const void *, uint32_t);
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 */
Antonio Quartullic90681b2011-10-05 17:05:25 +020042 uint32_t size; /* size of hashtable */
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000043};
44
45/* allocates and clears the hash */
Antonio Quartullic90681b2011-10-05 17:05:25 +020046struct hashtable_t *hash_new(uint32_t size);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000047
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 */
Antonio Quartullic90681b2011-10-05 17:05:25 +020060 uint32_t i;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000061
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
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +020079/**
80 * hash_add - adds data to the hashtable
81 * @hash: storage hash table
82 * @compare: callback to determine if 2 hash elements are identical
83 * @choose: callback calculating the hash index
84 * @data: data passed to the aforementioned callbacks as argument
85 * @data_node: to be added element
86 *
87 * Returns 0 on success, 1 if the element already is in the hash
88 * and -1 on error.
89 */
90
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000091static inline int hash_add(struct hashtable_t *hash,
92 hashdata_compare_cb compare,
Marek Lindner7aadf882011-02-18 12:28:09 +000093 hashdata_choose_cb choose,
Sven Eckelmann747e4222011-05-14 23:14:50 +020094 const void *data, struct hlist_node *data_node)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000095{
Antonio Quartullic90681b2011-10-05 17:05:25 +020096 uint32_t index;
97 int ret = -1;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000098 struct hlist_head *head;
Marek Lindner7aadf882011-02-18 12:28:09 +000099 struct hlist_node *node;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000100 spinlock_t *list_lock; /* spinlock to protect write access */
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000101
102 if (!hash)
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200103 goto out;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000104
105 index = choose(data, hash->size);
106 head = &hash->table[index];
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000107 list_lock = &hash->list_locks[index];
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000108
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000109 rcu_read_lock();
Marek Lindner7aadf882011-02-18 12:28:09 +0000110 __hlist_for_each_rcu(node, head) {
111 if (!compare(node, data))
112 continue;
113
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200114 ret = 1;
Marek Lindner7aadf882011-02-18 12:28:09 +0000115 goto err_unlock;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000116 }
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000117 rcu_read_unlock();
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000118
119 /* no duplicate found in list, add new element */
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000120 spin_lock_bh(list_lock);
Marek Lindner7aadf882011-02-18 12:28:09 +0000121 hlist_add_head_rcu(data_node, head);
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000122 spin_unlock_bh(list_lock);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000123
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200124 ret = 0;
125 goto out;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000126
127err_unlock:
128 rcu_read_unlock();
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200129out:
130 return ret;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000131}
132
133/* removes data from hash, if found. returns pointer do data on success, so you
134 * can remove the used structure yourself, or NULL on error . data could be the
135 * structure you use with just the key filled, we just need the key for
136 * comparing. */
137static inline void *hash_remove(struct hashtable_t *hash,
138 hashdata_compare_cb compare,
139 hashdata_choose_cb choose, void *data)
140{
Antonio Quartullic90681b2011-10-05 17:05:25 +0200141 uint32_t index;
Marek Lindner7aadf882011-02-18 12:28:09 +0000142 struct hlist_node *node;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000143 struct hlist_head *head;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000144 void *data_save = NULL;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000145
146 index = choose(data, hash->size);
147 head = &hash->table[index];
148
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000149 spin_lock_bh(&hash->list_locks[index]);
Marek Lindner7aadf882011-02-18 12:28:09 +0000150 hlist_for_each(node, head) {
151 if (!compare(node, data))
152 continue;
153
154 data_save = node;
155 hlist_del_rcu(node);
156 break;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000157 }
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000158 spin_unlock_bh(&hash->list_locks[index]);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000159
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000160 return data_save;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000161}
162
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000163#endif /* _NET_BATMAN_ADV_HASH_H_ */