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 * ptr_is_a_nulls - Test if a ptr is a nulls
  34 * @ptr: ptr to be tested
  35 *
  36 */
  37static inline int is_a_nulls(const struct hlist_nulls_node *ptr)
  38{
  39        return ((unsigned long)ptr & 1);
  40}
  41
  42/**
  43 * get_nulls_value - Get the 'nulls' value of the end of chain
  44 * @ptr: end of chain
  45 *
  46 * Should be called only if is_a_nulls(ptr);
  47 */
  48static inline unsigned long get_nulls_value(const struct hlist_nulls_node *ptr)
  49{
  50        return ((unsigned long)ptr) >> 1;
  51}
  52
  53static inline int hlist_nulls_unhashed(const struct hlist_nulls_node *h)
  54{
  55        return !h->pprev;
  56}
  57
  58static inline int hlist_nulls_empty(const struct hlist_nulls_head *h)
  59{
  60        return is_a_nulls(READ_ONCE(h->first));
  61}
  62
  63static inline void hlist_nulls_add_head(struct hlist_nulls_node *n,
  64                                        struct hlist_nulls_head *h)
  65{
  66        struct hlist_nulls_node *first = h->first;
  67
  68        n->next = first;
  69        n->pprev = &h->first;
  70        h->first = n;
  71        if (!is_a_nulls(first))
  72                first->pprev = &n->next;
  73}
  74
  75static inline void __hlist_nulls_del(struct hlist_nulls_node *n)
  76{
  77        struct hlist_nulls_node *next = n->next;
  78        struct hlist_nulls_node **pprev = n->pprev;
  79
  80        WRITE_ONCE(*pprev, next);
  81        if (!is_a_nulls(next))
  82                next->pprev = pprev;
  83}
  84
  85static inline void hlist_nulls_del(struct hlist_nulls_node *n)
  86{
  87        __hlist_nulls_del(n);
  88        n->pprev = LIST_POISON2;
  89}
  90
  91/**
  92 * hlist_nulls_for_each_entry   - iterate over list of given type
  93 * @tpos:       the type * to use as a loop cursor.
  94 * @pos:        the &struct hlist_node to use as a loop cursor.
  95 * @head:       the head for your list.
  96 * @member:     the name of the hlist_node within the struct.
  97 *
  98 */
  99#define hlist_nulls_for_each_entry(tpos, pos, head, member)                    \
 100        for (pos = (head)->first;                                              \
 101             (!is_a_nulls(pos)) &&                                             \
 102                ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
 103             pos = pos->next)
 104
 105/**
 106 * hlist_nulls_for_each_entry_from - iterate over a hlist continuing from current point
 107 * @tpos:       the type * to use as a loop cursor.
 108 * @pos:        the &struct hlist_node to use as a loop cursor.
 109 * @member:     the name of the hlist_node within the struct.
 110 *
 111 */
 112#define hlist_nulls_for_each_entry_from(tpos, pos, member)      \
 113        for (; (!is_a_nulls(pos)) &&                            \
 114                ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
 115             pos = pos->next)
 116
 117#endif
 118