net/batman-adv/hash.h

0001 /* SPDX-License-Identifier: GPL-2.0 */
0002 /* Copyright (C) B.A.T.M.A.N. contributors:
0003  *
0004  * Simon Wunderlich, Marek Lindner
0005  */
0006
0007 #ifndef _NET_BATMAN_ADV_HASH_H_
0008 #define _NET_BATMAN_ADV_HASH_H_
0009
0010 #include "main.h"
0011
0012 #include <linux/atomic.h>
0013 #include <linux/compiler.h>
0014 #include <linux/list.h>
0015 #include <linux/lockdep.h>
0016 #include <linux/rculist.h>
0017 #include <linux/spinlock.h>
0018 #include <linux/stddef.h>
0019 #include <linux/types.h>
0020
0021 /* callback to a compare function.  should compare 2 element data for their
0022  * keys
0023  *
0024  * Return: true if same and false if not same
0025  */
0026 typedef bool (*batadv_hashdata_compare_cb)(const struct hlist_node *,
0027                        const void *);
0028
0029 /* the hashfunction
0030  *
0031  * Return: an index based on the key in the data of the first argument and the
0032  * size the second
0033  */
0034 typedef u32 (*batadv_hashdata_choose_cb)(const void *, u32);
0035 typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *);
0036
0037 /**
0038  * struct batadv_hashtable - Wrapper of simple hlist based hashtable
0039  */
0040 struct batadv_hashtable {
0041     /** @table: the hashtable itself with the buckets */
0042     struct hlist_head *table;
0043
0044     /** @list_locks: spinlock for each hash list entry */
0045     spinlock_t *list_locks;
0046
0047     /** @size: size of hashtable */
0048     u32 size;
0049
0050     /** @generation: current (generation) sequence number */
0051     atomic_t generation;
0052 };
0053
0054 /* allocates and clears the hash */
0055 struct batadv_hashtable *batadv_hash_new(u32 size);
0056
0057 /* set class key for all locks */
0058 void batadv_hash_set_lock_class(struct batadv_hashtable *hash,
0059                 struct lock_class_key *key);
0060
0061 /* free only the hashtable and the hash itself. */
0062 void batadv_hash_destroy(struct batadv_hashtable *hash);
0063
0064 /**
0065  *  batadv_hash_add() - adds data to the hashtable
0066  *  @hash: storage hash table
0067  *  @compare: callback to determine if 2 hash elements are identical
0068  *  @choose: callback calculating the hash index
0069  *  @data: data passed to the aforementioned callbacks as argument
0070  *  @data_node: to be added element
0071  *
0072  *  Return: 0 on success, 1 if the element already is in the hash
0073  *  and -1 on error.
0074  */
0075 static inline int batadv_hash_add(struct batadv_hashtable *hash,
0076                   batadv_hashdata_compare_cb compare,
0077                   batadv_hashdata_choose_cb choose,
0078                   const void *data,
0079                   struct hlist_node *data_node)
0080 {
0081     u32 index;
0082     int ret = -1;
0083     struct hlist_head *head;
0084     struct hlist_node *node;
0085     spinlock_t *list_lock; /* spinlock to protect write access */
0086
0087     if (!hash)
0088         goto out;
0089
0090     index = choose(data, hash->size);
0091     head = &hash->table[index];
0092     list_lock = &hash->list_locks[index];
0093
0094     spin_lock_bh(list_lock);
0095
0096     hlist_for_each(node, head) {
0097         if (!compare(node, data))
0098             continue;
0099
0100         ret = 1;
0101         goto unlock;
0102     }
0103
0104     /* no duplicate found in list, add new element */
0105     hlist_add_head_rcu(data_node, head);
0106     atomic_inc(&hash->generation);
0107
0108     ret = 0;
0109
0110 unlock:
0111     spin_unlock_bh(list_lock);
0112 out:
0113     return ret;
0114 }
0115
0116 /**
0117  * batadv_hash_remove() - Removes data from hash, if found
0118  * @hash: hash table
0119  * @compare: callback to determine if 2 hash elements are identical
0120  * @choose: callback calculating the hash index
0121  * @data: data passed to the aforementioned callbacks as argument
0122  *
0123  * ata could be the structure you use with  just the key filled, we just need
0124  * the key for comparing.
0125  *
0126  * Return: returns pointer do data on success, so you can remove the used
0127  * structure yourself, or NULL on error
0128  */
0129 static inline void *batadv_hash_remove(struct batadv_hashtable *hash,
0130                        batadv_hashdata_compare_cb compare,
0131                        batadv_hashdata_choose_cb choose,
0132                        void *data)
0133 {
0134     u32 index;
0135     struct hlist_node *node;
0136     struct hlist_head *head;
0137     void *data_save = NULL;
0138
0139     index = choose(data, hash->size);
0140     head = &hash->table[index];
0141
0142     spin_lock_bh(&hash->list_locks[index]);
0143     hlist_for_each(node, head) {
0144         if (!compare(node, data))
0145             continue;
0146
0147         data_save = node;
0148         hlist_del_rcu(node);
0149         atomic_inc(&hash->generation);
0150         break;
0151     }
0152     spin_unlock_bh(&hash->list_locks[index]);
0153
0154     return data_save;
0155 }
0156
0157 #endif /* _NET_BATMAN_ADV_HASH_H_ */