Branch data     Line data    Source code

       1                 :            : /* SPDX-License-Identifier: GPL-2.0 */
       2                 :            : #ifndef _LINUX_LIST_NULLS_H
       3                 :            : #define _LINUX_LIST_NULLS_H
       4                 :            : 
       5                 :            : #include <linux/poison.h>
       6                 :            : #include <linux/const.h>
       7                 :            : 
       8                 :            : /*
       9                 :            :  * Special version of lists, where end of list is not a NULL pointer,
      10                 :            :  * but a 'nulls' marker, which can have many different values.
      11                 :            :  * (up to 2^31 different values guaranteed on all platforms)
      12                 :            :  *
      13                 :            :  * In the standard hlist, termination of a list is the NULL pointer.
      14                 :            :  * In this special 'nulls' variant, we use the fact that objects stored in
      15                 :            :  * a list are aligned on a word (4 or 8 bytes alignment).
      16                 :            :  * We therefore use the last significant bit of 'ptr' :
      17                 :            :  * Set to 1 : This is a 'nulls' end-of-list marker (ptr >> 1)
      18                 :            :  * Set to 0 : This is a pointer to some object (ptr)
      19                 :            :  */
      20                 :            : 
      21                 :            : struct hlist_nulls_head {
      22                 :            :         struct hlist_nulls_node *first;
      23                 :            : };
      24                 :            : 
      25                 :            : struct hlist_nulls_node {
      26                 :            :         struct hlist_nulls_node *next, **pprev;
      27                 :            : };
      28                 :            : #define NULLS_MARKER(value) (1UL | (((long)value) << 1))
      29                 :            : #define INIT_HLIST_NULLS_HEAD(ptr, nulls) \
      30                 :            :         ((ptr)->first = (struct hlist_nulls_node *) NULLS_MARKER(nulls))
      31                 :            : 
      32                 :            : #define hlist_nulls_entry(ptr, type, member) container_of(ptr,type,member)
      33                 :            : 
      34                 :            : #define hlist_nulls_entry_safe(ptr, type, member) \
      35                 :            :         ({ typeof(ptr) ____ptr = (ptr); \
      36                 :            :            !is_a_nulls(____ptr) ? hlist_nulls_entry(____ptr, type, member) : NULL; \
      37                 :            :         })
      38                 :            : /**
      39                 :            :  * ptr_is_a_nulls - Test if a ptr is a nulls
      40                 :            :  * @ptr: ptr to be tested
      41                 :            :  *
      42                 :            :  */
      43                 :            : static inline int is_a_nulls(const struct hlist_nulls_node *ptr)
      44                 :            : {
      45                 :          3 :         return ((unsigned long)ptr & 1);
      46                 :            : }
      47                 :            : 
      48                 :            : /**
      49                 :            :  * get_nulls_value - Get the 'nulls' value of the end of chain
      50                 :            :  * @ptr: end of chain
      51                 :            :  *
      52                 :            :  * Should be called only if is_a_nulls(ptr);
      53                 :            :  */
      54                 :            : static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr)
      55                 :            : {
      56                 :          3 :         return ((unsigned long)ptr) >> 1;
      57                 :            : }
      58                 :            : 
      59                 :            : static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)
      60                 :            : {
      61                 :            :         return !h->pprev;
      62                 :            : }
      63                 :            : 
      64                 :            : static inline int hlist_nulls_empty(const struct hlist_nulls_head *h)
      65                 :            : {
      66                 :            :         return is_a_nulls(READ_ONCE(h->first));
      67                 :            : }
      68                 :            : 
      69                 :            : static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
      70                 :            :                                         struct hlist_nulls_head *h)
      71                 :            : {
      72                 :          0 :         struct hlist_nulls_node *first = h->first;
      73                 :            : 
      74                 :          0 :         n->next = first;
      75                 :          0 :         WRITE_ONCE(n->pprev, &h->first);
      76                 :          0 :         h->first = n;
      77                 :          0 :         if (!is_a_nulls(first))
      78                 :          0 :                 WRITE_ONCE(first->pprev, &n->next);
      79                 :            : }
      80                 :            : 
      81                 :            : static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
      82                 :            : {
      83                 :          1 :         struct hlist_nulls_node *next = n->next;
      84                 :          0 :         struct hlist_nulls_node **pprev = n->pprev;
      85                 :            : 
      86                 :          1 :         WRITE_ONCE(*pprev, next);
      87                 :          1 :         if (!is_a_nulls(next))
      88                 :          0 :                 WRITE_ONCE(next->pprev, pprev);
      89                 :            : }
      90                 :            : 
      91                 :            : static inline void hlist_nulls_del(struct hlist_nulls_node *n)
      92                 :            : {
      93                 :            :         __hlist_nulls_del(n);
      94                 :            :         WRITE_ONCE(n->pprev, LIST_POISON2);
      95                 :            : }
      96                 :            : 
      97                 :            : /**
      98                 :            :  * hlist_nulls_for_each_entry   - iterate over list of given type
      99                 :            :  * @tpos:       the type * to use as a loop cursor.
     100                 :            :  * @pos:        the &struct hlist_node to use as a loop cursor.
     101                 :            :  * @head:       the head for your list.
     102                 :            :  * @member:     the name of the hlist_node within the struct.
     103                 :            :  *
     104                 :            :  */
     105                 :            : #define hlist_nulls_for_each_entry(tpos, pos, head, member)                    \
     106                 :            :         for (pos = (head)->first;                                           \
     107                 :            :              (!is_a_nulls(pos)) &&                                             \
     108                 :            :                 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
     109                 :            :              pos = pos->next)
     110                 :            : 
     111                 :            : /**
     112                 :            :  * hlist_nulls_for_each_entry_from - iterate over a hlist continuing from current point
     113                 :            :  * @tpos:       the type * to use as a loop cursor.
     114                 :            :  * @pos:        the &struct hlist_node to use as a loop cursor.
     115                 :            :  * @member:     the name of the hlist_node within the struct.
     116                 :            :  *
     117                 :            :  */
     118                 :            : #define hlist_nulls_for_each_entry_from(tpos, pos, member)      \
     119                 :            :         for (; (!is_a_nulls(pos)) &&                            \
     120                 :            :                 ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
     121                 :            :              pos = pos->next)
     122                 :            : 
     123                 :            : #endif