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