LXR linux/include/linux/list

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