LXR linux/net/batman-adv/hash.h

   1/* SPDX-License-Identifier: GPL-2.0 */
   2/* Copyright (C) B.A.T.M.A.N. contributors:
   3 *
   4 * Simon Wunderlich, Marek Lindner
   5 */
   6
   7#ifndef _NET_BATMAN_ADV_HASH_H_
   8#define _NET_BATMAN_ADV_HASH_H_
   9
  10#include "main.h"
  11
  12#include <linux/atomic.h>
  13#include <linux/compiler.h>
  14#include <linux/list.h>
  15#include <linux/lockdep.h>
  16#include <linux/rculist.h>
  17#include <linux/spinlock.h>
  18#include <linux/stddef.h>
  19#include <linux/types.h>
  20
  21/* callback to a compare function.  should compare 2 element data for their
  22 * keys
  23 *
  24 * Return: true if same and false if not same
  25 */
  26typedef bool (*batadv_hashdata_compare_cb)(const struct hlist_node *,
  27                                           const void *);
  28
  29/* the hashfunction
  30 *
  31 * Return: an index based on the key in the data of the first argument and the
  32 * size the second
  33 */
  34typedef u32 (*batadv_hashdata_choose_cb)(const void *, u32);
  35typedef void (*batadv_hashdata_free_cb)(struct hlist_node *, void *);
  36
  37/**
  38 * struct batadv_hashtable - Wrapper of simple hlist based hashtable
  39 */
  40struct batadv_hashtable {
  41        /** @table: the hashtable itself with the buckets */
  42        struct hlist_head *table;
  43
  44        /** @list_locks: spinlock for each hash list entry */
  45        spinlock_t *list_locks;
  46
  47        /** @size: size of hashtable */
  48        u32 size;
  49
  50        /** @generation: current (generation) sequence number */
  51        atomic_t generation;
  52};
  53
  54/* allocates and clears the hash */
  55struct batadv_hashtable *batadv_hash_new(u32 size);
  56
  57/* set class key for all locks */
  58void 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. */
  62void 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 */
  75static 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        atomic_inc(&hash->generation);
 107
 108        ret = 0;
 109
 110unlock:
 111        spin_unlock_bh(list_lock);
 112out:
 113        return ret;
 114}
 115
 116/**
 117 * batadv_hash_remove() - Removes data from hash, if found
 118 * @hash: hash table
 119 * @compare: callback to determine if 2 hash elements are identical
 120 * @choose: callback calculating the hash index
 121 * @data: data passed to the aforementioned callbacks as argument
 122 *
 123 * ata could be the structure you use with  just the key filled, we just need
 124 * the key for comparing.
 125 *
 126 * Return: returns pointer do data on success, so you can remove the used
 127 * structure yourself, or NULL on error
 128 */
 129static inline void *batadv_hash_remove(struct batadv_hashtable *hash,
 130                                       batadv_hashdata_compare_cb compare,
 131                                       batadv_hashdata_choose_cb choose,
 132                                       void *data)
 133{
 134        u32 index;
 135        struct hlist_node *node;
 136        struct hlist_head *head;
 137        void *data_save = NULL;
 138
 139        index = choose(data, hash->size);
 140        head = &hash->table[index];
 141
 142        spin_lock_bh(&hash->list_locks[index]);
 143        hlist_for_each(node, head) {
 144                if (!compare(node, data))
 145                        continue;
 146
 147                data_save = node;
 148                hlist_del_rcu(node);
 149                atomic_inc(&hash->generation);
 150                break;
 151        }
 152        spin_unlock_bh(&hash->list_locks[index]);
 153
 154        return data_save;
 155}
 156
 157#endif /* _NET_BATMAN_ADV_HASH_H_ */
 158