net/batman-adv/hash.h

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