~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/net/batman-adv/hash.h

Version: ~ [ linux-6.2-rc3 ] ~ [ linux-6.1.5 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.87 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.162 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.228 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.269 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.302 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.8.17 ] ~ [ linux-4.7.10 ] ~ [ linux-4.6.7 ] ~ [ linux-4.5.7 ] ~ [ linux-4.4.302 ] ~ [ linux-4.3.6 ] ~ [ linux-4.2.8 ] ~ [ linux-4.1.52 ] ~ [ linux-4.0.9 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

  1 /* Copyright (C) 2006-2017  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, see <http://www.gnu.org/licenses/>.
 16  */
 17 
 18 #ifndef _NET_BATMAN_ADV_HASH_H_
 19 #define _NET_BATMAN_ADV_HASH_H_
 20 
 21 #include "main.h"
 22 
 23 #include <linux/compiler.h>
 24 #include <linux/list.h>
 25 #include <linux/rculist.h>
 26 #include <linux/spinlock.h>
 27 #include <linux/stddef.h>
 28 #include <linux/types.h>
 29 
 30 struct lock_class_key;
 31 
 32 /* callback to a compare function.  should compare 2 element datas for their
 33  * keys
 34  *
 35  * Return: true if same and false if not same
 36  */
 37 typedef bool (*batadv_hashdata_compare_cb)(const struct hlist_node *,
 38                                            const void *);
 39 
 40 /* the hashfunction
 41  *
 42  * Return: an index based on the key in the data of the first argument and the
 43  * size the second
 44  */
 45 typedef u32 (*batadv_hashdata_choose_cb)(const void *, u32);
 46 typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *);
 47 
 48 struct batadv_hashtable {
 49         struct hlist_head *table;   /* the hashtable itself with the buckets */
 50         spinlock_t *list_locks;     /* spinlock for each hash list entry */
 51         u32 size;                   /* size of hashtable */
 52 };
 53 
 54 /* allocates and clears the hash */
 55 struct batadv_hashtable *batadv_hash_new(u32 size);
 56 
 57 /* set class key for all locks */
 58 void batadv_hash_set_lock_class(struct batadv_hashtable *hash,
 59                                 struct lock_class_key *key);
 60 
 61 /* free only the hashtable and the hash itself. */
 62 void batadv_hash_destroy(struct batadv_hashtable *hash);
 63 
 64 /**
 65  *      batadv_hash_add - adds data to the hashtable
 66  *      @hash: storage hash table
 67  *      @compare: callback to determine if 2 hash elements are identical
 68  *      @choose: callback calculating the hash index
 69  *      @data: data passed to the aforementioned callbacks as argument
 70  *      @data_node: to be added element
 71  *
 72  *      Return: 0 on success, 1 if the element already is in the hash
 73  *      and -1 on error.
 74  */
 75 static inline int batadv_hash_add(struct batadv_hashtable *hash,
 76                                   batadv_hashdata_compare_cb compare,
 77                                   batadv_hashdata_choose_cb choose,
 78                                   const void *data,
 79                                   struct hlist_node *data_node)
 80 {
 81         u32 index;
 82         int ret = -1;
 83         struct hlist_head *head;
 84         struct hlist_node *node;
 85         spinlock_t *list_lock; /* spinlock to protect write access */
 86 
 87         if (!hash)
 88                 goto out;
 89 
 90         index = choose(data, hash->size);
 91         head = &hash->table[index];
 92         list_lock = &hash->list_locks[index];
 93 
 94         spin_lock_bh(list_lock);
 95 
 96         hlist_for_each(node, head) {
 97                 if (!compare(node, data))
 98                         continue;
 99 
100                 ret = 1;
101                 goto unlock;
102         }
103 
104         /* no duplicate found in list, add new element */
105         hlist_add_head_rcu(data_node, head);
106 
107         ret = 0;
108 
109 unlock:
110         spin_unlock_bh(list_lock);
111 out:
112         return ret;
113 }
114 
115 /* removes data from hash, if found. data could be the structure you use with
116  * just the key filled, we just need the key for comparing.
117  *
118  * Return: returns pointer do data on success, so you can remove the used
119  * structure yourself, or NULL on error
120  */
121 static inline void *batadv_hash_remove(struct batadv_hashtable *hash,
122                                        batadv_hashdata_compare_cb compare,
123                                        batadv_hashdata_choose_cb choose,
124                                        void *data)
125 {
126         u32 index;
127         struct hlist_node *node;
128         struct hlist_head *head;
129         void *data_save = NULL;
130 
131         index = choose(data, hash->size);
132         head = &hash->table[index];
133 
134         spin_lock_bh(&hash->list_locks[index]);
135         hlist_for_each(node, head) {
136                 if (!compare(node, data))
137                         continue;
138 
139                 data_save = node;
140                 hlist_del_rcu(node);
141                 break;
142         }
143         spin_unlock_bh(&hash->list_locks[index]);
144 
145         return data_save;
146 }
147 
148 #endif /* _NET_BATMAN_ADV_HASH_H_ */
149 

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp