Linux Kernel  3.7.1
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros Groups Pages
hash.h
Go to the documentation of this file.
1 /* Copyright (C) 2006-2012 B.A.T.M.A.N. contributors:
2  *
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
18  */
19 
20 #ifndef _NET_BATMAN_ADV_HASH_H_
21 #define _NET_BATMAN_ADV_HASH_H_
22 
23 #include <linux/list.h>
24 
25 /* 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  */
28 typedef int (*batadv_hashdata_compare_cb)(const struct hlist_node *,
29  const void *);
30 
31 /* the hashfunction, should return an index
32  * based on the key in the data of the first
33  * argument and the size the second
34  */
35 typedef uint32_t (*batadv_hashdata_choose_cb)(const void *, uint32_t);
36 typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *);
37 
39  struct hlist_head *table; /* the hashtable itself with the buckets */
40  spinlock_t *list_locks; /* spinlock for each hash list entry */
41  uint32_t size; /* size of hashtable */
42 };
43 
44 /* allocates and clears the hash */
46 
47 /* set class key for all locks */
49  struct lock_class_key *key);
50 
51 /* free only the hashtable and the hash itself. */
53 
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
56  * elements, memory might be leaked.
57  */
58 static inline void batadv_hash_delete(struct batadv_hashtable *hash,
60  void *arg)
61 {
62  struct hlist_head *head;
63  struct hlist_node *node, *node_tmp;
64  spinlock_t *list_lock; /* spinlock to protect write access */
65  uint32_t i;
66 
67  for (i = 0; i < hash->size; i++) {
68  head = &hash->table[i];
69  list_lock = &hash->list_locks[i];
70 
71  spin_lock_bh(list_lock);
72  hlist_for_each_safe(node, node_tmp, head) {
73  hlist_del_rcu(node);
74 
75  if (free_cb)
76  free_cb(node, arg);
77  }
78  spin_unlock_bh(list_lock);
79  }
80 
81  batadv_hash_destroy(hash);
82 }
83 
95 static inline int batadv_hash_add(struct batadv_hashtable *hash,
98  const void *data,
99  struct hlist_node *data_node)
100 {
101  uint32_t index;
102  int ret = -1;
103  struct hlist_head *head;
104  struct hlist_node *node;
105  spinlock_t *list_lock; /* spinlock to protect write access */
106 
107  if (!hash)
108  goto out;
109 
110  index = choose(data, hash->size);
111  head = &hash->table[index];
112  list_lock = &hash->list_locks[index];
113 
114  spin_lock_bh(list_lock);
115 
116  hlist_for_each(node, head) {
117  if (!compare(node, data))
118  continue;
119 
120  ret = 1;
121  goto unlock;
122  }
123 
124  /* no duplicate found in list, add new element */
125  hlist_add_head_rcu(data_node, head);
126 
127  ret = 0;
128 
129 unlock:
130  spin_unlock_bh(list_lock);
131 out:
132  return ret;
133 }
134 
135 /* removes data from hash, if found. returns pointer do data on success, so you
136  * can remove the used structure yourself, or NULL on error . data could be the
137  * structure you use with just the key filled, we just need the key for
138  * comparing.
139  */
140 static inline void *batadv_hash_remove(struct batadv_hashtable *hash,
143  void *data)
144 {
145  uint32_t index;
146  struct hlist_node *node;
147  struct hlist_head *head;
148  void *data_save = NULL;
149 
150  index = choose(data, hash->size);
151  head = &hash->table[index];
152 
153  spin_lock_bh(&hash->list_locks[index]);
154  hlist_for_each(node, head) {
155  if (!compare(node, data))
156  continue;
157 
158  data_save = node;
159  hlist_del_rcu(node);
160  break;
161  }
162  spin_unlock_bh(&hash->list_locks[index]);
163 
164  return data_save;
165 }
166 
167 #endif /* _NET_BATMAN_ADV_HASH_H_ */