blob: e05333905afd566117bf1267d6e3ac05596c89c1 [file] [log] [blame]
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +02001/* Copyright (C) 2006-2012 B.A.T.M.A.N. contributors:
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +00002 *
3 * Simon Wunderlich, Marek Lindner
4 *
5 * This program is free software; you can redistribute it and/or
6 * modify it under the terms of version 2 of the GNU General Public
7 * License as published by the Free Software Foundation.
8 *
9 * This program is distributed in the hope that it will be useful, but
10 * WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
17 * 02110-1301, USA
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000018 */
19
20#ifndef _NET_BATMAN_ADV_HASH_H_
21#define _NET_BATMAN_ADV_HASH_H_
22
23#include <linux/list.h>
24
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +020025/* callback to a compare function. should compare 2 element datas for their
26 * keys, return 0 if same and not 0 if not same
27 */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +020028typedef int (*batadv_hashdata_compare_cb)(const struct hlist_node *,
29 const void *);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000030
31/* the hashfunction, should return an index
32 * based on the key in the data of the first
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +020033 * argument and the size the second
34 */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +020035typedef uint32_t (*batadv_hashdata_choose_cb)(const void *, uint32_t);
36typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000037
Sven Eckelmann5bf74e92012-06-05 22:31:28 +020038struct batadv_hashtable {
Marek Lindnerfb778ea2011-01-19 20:01:40 +000039 struct hlist_head *table; /* the hashtable itself with the buckets */
40 spinlock_t *list_locks; /* spinlock for each hash list entry */
Antonio Quartullic90681b2011-10-05 17:05:25 +020041 uint32_t size; /* size of hashtable */
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000042};
43
44/* allocates and clears the hash */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +020045struct batadv_hashtable *batadv_hash_new(uint32_t size);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000046
Sven Eckelmann5d52dad2012-03-29 12:38:20 +020047/* set class key for all locks */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +020048void batadv_hash_set_lock_class(struct batadv_hashtable *hash,
Sven Eckelmann5d52dad2012-03-29 12:38:20 +020049 struct lock_class_key *key);
50
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000051/* free only the hashtable and the hash itself. */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +020052void batadv_hash_destroy(struct batadv_hashtable *hash);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000053
54/* remove the hash structure. if hashdata_free_cb != NULL, this function will be
55 * called to remove the elements inside of the hash. if you don't remove the
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +020056 * elements, memory might be leaked.
57 */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +020058static inline void batadv_hash_delete(struct batadv_hashtable *hash,
59 batadv_hashdata_free_cb free_cb,
60 void *arg)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000061{
62 struct hlist_head *head;
Marek Lindner7aadf882011-02-18 12:28:09 +000063 struct hlist_node *node, *node_tmp;
Marek Lindnerfb778ea2011-01-19 20:01:40 +000064 spinlock_t *list_lock; /* spinlock to protect write access */
Antonio Quartullic90681b2011-10-05 17:05:25 +020065 uint32_t i;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000066
67 for (i = 0; i < hash->size; i++) {
68 head = &hash->table[i];
Marek Lindnerfb778ea2011-01-19 20:01:40 +000069 list_lock = &hash->list_locks[i];
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000070
Marek Lindnerfb778ea2011-01-19 20:01:40 +000071 spin_lock_bh(list_lock);
Marek Lindner7aadf882011-02-18 12:28:09 +000072 hlist_for_each_safe(node, node_tmp, head) {
73 hlist_del_rcu(node);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000074
Marek Lindner7aadf882011-02-18 12:28:09 +000075 if (free_cb)
76 free_cb(node, arg);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000077 }
Marek Lindnerfb778ea2011-01-19 20:01:40 +000078 spin_unlock_bh(list_lock);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000079 }
80
Sven Eckelmann1a8eaf02012-05-12 02:09:32 +020081 batadv_hash_destroy(hash);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +000082}
83
Ben Hutchings2c530402012-07-10 10:55:09 +000084/**
Simon Wunderlich07568d02012-08-30 18:22:27 +020085 * batadv_hash_bytes - hash some bytes and add them to the previous hash
86 * @hash: previous hash value
87 * @data: data to be hashed
88 * @size: number of bytes to be hashed
89 *
90 * Returns the new hash value.
91 */
92static inline uint32_t batadv_hash_bytes(uint32_t hash, void *data,
93 uint32_t size)
94{
95 const unsigned char *key = data;
96 int i;
97
98 for (i = 0; i < size; i++) {
99 hash += key[i];
100 hash += (hash << 10);
101 hash ^= (hash >> 6);
102 }
103 return hash;
104}
105
106/**
Ben Hutchings2c530402012-07-10 10:55:09 +0000107 * batadv_hash_add - adds data to the hashtable
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200108 * @hash: storage hash table
109 * @compare: callback to determine if 2 hash elements are identical
110 * @choose: callback calculating the hash index
111 * @data: data passed to the aforementioned callbacks as argument
112 * @data_node: to be added element
113 *
114 * Returns 0 on success, 1 if the element already is in the hash
115 * and -1 on error.
116 */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +0200117static inline int batadv_hash_add(struct batadv_hashtable *hash,
118 batadv_hashdata_compare_cb compare,
119 batadv_hashdata_choose_cb choose,
Sven Eckelmannc0a55922012-05-12 13:48:55 +0200120 const void *data,
121 struct hlist_node *data_node)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000122{
Antonio Quartullic90681b2011-10-05 17:05:25 +0200123 uint32_t index;
124 int ret = -1;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000125 struct hlist_head *head;
Marek Lindner7aadf882011-02-18 12:28:09 +0000126 struct hlist_node *node;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000127 spinlock_t *list_lock; /* spinlock to protect write access */
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000128
129 if (!hash)
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200130 goto out;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000131
132 index = choose(data, hash->size);
133 head = &hash->table[index];
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000134 list_lock = &hash->list_locks[index];
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000135
Matthias Schiffer75c5a2e2012-05-08 22:31:57 +0200136 spin_lock_bh(list_lock);
137
138 hlist_for_each(node, head) {
Marek Lindner7aadf882011-02-18 12:28:09 +0000139 if (!compare(node, data))
140 continue;
141
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200142 ret = 1;
Matthias Schiffer75c5a2e2012-05-08 22:31:57 +0200143 goto unlock;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000144 }
145
146 /* no duplicate found in list, add new element */
Marek Lindner7aadf882011-02-18 12:28:09 +0000147 hlist_add_head_rcu(data_node, head);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000148
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200149 ret = 0;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000150
Matthias Schiffer75c5a2e2012-05-08 22:31:57 +0200151unlock:
152 spin_unlock_bh(list_lock);
Antonio Quartulli1a1f37d2011-07-10 00:36:36 +0200153out:
154 return ret;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000155}
156
157/* removes data from hash, if found. returns pointer do data on success, so you
158 * can remove the used structure yourself, or NULL on error . data could be the
159 * structure you use with just the key filled, we just need the key for
Sven Eckelmann9cfc7bd2012-05-12 02:09:43 +0200160 * comparing.
161 */
Sven Eckelmann5bf74e92012-06-05 22:31:28 +0200162static inline void *batadv_hash_remove(struct batadv_hashtable *hash,
163 batadv_hashdata_compare_cb compare,
164 batadv_hashdata_choose_cb choose,
165 void *data)
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000166{
Antonio Quartullic90681b2011-10-05 17:05:25 +0200167 uint32_t index;
Marek Lindner7aadf882011-02-18 12:28:09 +0000168 struct hlist_node *node;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000169 struct hlist_head *head;
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000170 void *data_save = NULL;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000171
172 index = choose(data, hash->size);
173 head = &hash->table[index];
174
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000175 spin_lock_bh(&hash->list_locks[index]);
Marek Lindner7aadf882011-02-18 12:28:09 +0000176 hlist_for_each(node, head) {
177 if (!compare(node, data))
178 continue;
179
180 data_save = node;
181 hlist_del_rcu(node);
182 break;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000183 }
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000184 spin_unlock_bh(&hash->list_locks[index]);
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000185
Marek Lindnerfb778ea2011-01-19 20:01:40 +0000186 return data_save;
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000187}
188
Sven Eckelmannc6c8fea2010-12-13 11:19:28 +0000189#endif /* _NET_BATMAN_ADV_HASH_H_ */