FreeBSD/Linux Kernel Cross Reference
sys/compat/linuxkpi/common/include/linux/hashtable.h

     /*-
      * SPDX-License-Identifier: BSD-2-Clause
      *
      * Copyright (c) 2022 NVIDIA corporation & affiliates.
      *
      * Redistribution and use in source and binary forms, with or without
      * modification, are permitted provided that the following conditions
      * are met:
      * 1. Redistributions of source code must retain the above copyright
     *    notice unmodified, this list of conditions, and the following
     *    disclaimer.
     * 2. Redistributions in binary form must reproduce the above copyright
     *    notice, this list of conditions and the following disclaimer in the
     *    documentation and/or other materials provided with the distribution.
     *
     * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     *
     * $FreeBSD$
     */
    
    #ifndef _LINUXKPI_LINUX_HASHTABLE_H
    #define _LINUXKPI_LINUX_HASHTABLE_H
    
    #include <sys/param.h>
    #include <sys/systm.h>
    
    #include <linux/hash.h>
    #include <linux/kernel.h>
    #include <linux/list.h>
    #include <linux/log2.h>
    #include <linux/rcupdate.h>
    #include <linux/rculist.h>
    
    #include <ck_queue.h>
    
    struct lkpi_hash_entry {
            CK_LIST_ENTRY(lkpi_hash_entry) entry;
    };
    
    struct lkpi_hash_head {
            CK_LIST_HEAD(, lkpi_hash_entry) head;
    };
    
    #define DEFINE_HASHTABLE(name, bits) \
            struct lkpi_hash_head name[1UL << (bits)]
    
    #define DEFINE_READ_MOSTLY_HASHTABLE(name, bits) \
            struct lkpi_hash_head name[1UL << (bits)] __read_mostly
    
    #define DECLARE_HASHTABLE(name, bits) \
            struct lkpi_hash_head name[1UL << (bits)]
    
    #define HASH_SIZE(name) ARRAY_SIZE(name)
    #define HASH_BITS(name) ilog2(HASH_SIZE(name))
    
    #define hash_min(...) \
            hash_long(__VA_ARGS__)
    
    static inline void
    __hash_init(struct lkpi_hash_head *ht, unsigned long size)
    {
            unsigned long x;
    
            for (x = 0; x != size; x++)
                    CK_LIST_INIT(&ht[x].head);
    }
    
    #define hash_init(ht) \
            __hash_init(ht, HASH_SIZE(ht))
    
    #define hash_add(...) \
            hash_add_rcu(__VA_ARGS__)
    
    static inline void
    __hash_node_type_assert(struct hlist_node *node)
    {
            /*
             * Unfortunately Linux doesn't have an own type for the hash
             * table node entries. The purpose of this function is simply
             * to check the type of the passed argument.
             */
            CTASSERT(sizeof(struct lkpi_hash_entry) == sizeof(*node));
    }
    
    #define hash_add_rcu(ht, node, key) do {                                \
            struct lkpi_hash_head *__head = &(ht)[hash_min(key, HASH_BITS(ht))]; \
            __hash_node_type_assert(node); \
            KASSERT(((struct lkpi_hash_entry *)(node))->entry.cle_prev == NULL, \
                ("node is already on list or was not zeroed")); \
            CK_LIST_INSERT_HEAD(&__head->head, \
               (struct lkpi_hash_entry *)(node), entry); \
   } while (0)
   
   static inline bool
   hash_hashed(struct hlist_node *node)
   {
           return (((struct lkpi_hash_entry *)node)->entry.cle_prev != NULL);
   }
   
   static inline bool
   __hash_empty(struct lkpi_hash_head *ht, unsigned long size)
   {
           unsigned long x;
   
           for (x = 0; x != size; x++) {
                   if (!CK_LIST_EMPTY(&ht[x].head))
                           return (false);
           }
           return (true);
   }
   
   #define hash_empty(ht) \
           __hash_empty(ht, HASH_SIZE(ht))
   
   #define hash_del(...) \
           hash_del_rcu(__VA_ARGS__)
   
   static inline void
   hash_del_rcu(struct hlist_node *node)
   {
           CK_LIST_REMOVE((struct lkpi_hash_entry *)node, entry);
           memset(node, 0, sizeof(*node));
   }
   
   #define __hash_first(ht, type, member) ({ \
           const struct lkpi_hash_entry *__first = CK_LIST_FIRST(&(ht)->head); \
           __hash_node_type_assert(&((type *)0)->member); \
           (__first != NULL ? container_of((const void *)__first, type, member) : NULL); \
   })
   
   #define __hash_next(obj, type, member) ({ \
           const struct lkpi_hash_entry *__next = \
               CK_LIST_NEXT((struct lkpi_hash_entry *)&(obj)->member, entry); \
           __hash_node_type_assert(&(obj)->member); \
           (__next != NULL ? container_of((const void *)__next, type, member) : NULL); \
   })
   
   #define hash_for_each(...) \
           hash_for_each_rcu(__VA_ARGS__)
   
   #define hash_for_each_rcu(name, bkt, obj, member) \
           for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \
                  (bkt) != HASH_SIZE(name); (bkt)++) \
                   for ((obj) = __hash_first(&(name)[bkt], \
                           __typeof(*(obj)), member); \
                        (obj) != NULL; \
                        (obj) = __hash_next(obj, \
                           __typeof(*(obj)), member))
   
   #define hash_for_each_safe(name, bkt, tmp, obj, member) \
           for ((bkt) = 0, (obj) = NULL; (obj) == NULL && \
                  (bkt) != HASH_SIZE(name); (bkt)++) \
                   for ((obj) = __hash_first(&(name)[bkt], \
                           __typeof(*(obj)), member); \
                        (obj) != NULL && ((tmp) = &__hash_next(obj, \
                           __typeof(*(obj)), member)->member, 1); \
                        (obj) = container_of(tmp, __typeof(*(obj)), member))
   
   #define hash_for_each_possible(...) \
           hash_for_each_possible_rcu(__VA_ARGS__)
   
   #define hash_for_each_possible_rcu_notrace(...) \
           hash_for_each_possible_rcu(__VA_ARGS__)
   
   #define hash_for_each_possible_rcu(name, obj, member, key) \
           for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \
                   __typeof(*(obj)), member); \
                (obj) != NULL; \
                (obj) = __hash_next(obj, __typeof(*(obj)), member))
   
   #define hash_for_each_possible_safe(name, obj, tmp, member, key) \
           for ((obj) = __hash_first(&(name)[hash_min(key, HASH_BITS(name))], \
                   __typeof(*(obj)), member); \
                (obj) != NULL && ((tmp) = &__hash_next(obj, \
                   __typeof(*(obj)), member)->member, 1); \
                (obj) = container_of(tmp, __typeof(*(obj)), member))
   
   #endif                                  /* _LINUXKPI_LINUX_HASHTABLE_H */

Cache object: 4b105a0af5ba772fee5891eab7459f11