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(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        *pprev = next;
  80        if (!is_a_nulls(next))
  81                next->pprev = pprev;
  82}
  83
  84static inline void hlist_nulls_del(struct hlist_nulls_node *n)
  85{
  86        __hlist_nulls_del(n);
  87        n->pprev = LIST_POISON2;
  88}
  89
  90/**
  91 * hlist_nulls_for_each_entry   - iterate over list of given type
  92 * @tpos:       the type * to use as a loop cursor.
  93 * @pos:        the &struct hlist_node to use as a loop cursor.
  94 * @head:       the head for your list.
  95 * @member:     the name of the hlist_node within the struct.
  96 *
  97 */
  98#define hlist_nulls_for_each_entry(tpos, pos, head, member)                    \
  99        for (pos = (head)->first;                                              \
 100             (!is_a_nulls(pos)) &&                                             \
 101                ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
 102             pos = pos->next)
 103
 104/**
 105 * hlist_nulls_for_each_entry_from - iterate over a hlist continuing from current point
 106 * @tpos:       the type * to use as a loop cursor.
 107 * @pos:        the &struct hlist_node to use as a loop cursor.
 108 * @member:     the name of the hlist_node within the struct.
 109 *
 110 */
 111#define hlist_nulls_for_each_entry_from(tpos, pos, member)      \
 112        for (; (!is_a_nulls(pos)) &&                            \
 113                ({ tpos = hlist_nulls_entry(pos, typeof(*tpos), member); 1;}); \
 114             pos = pos->next)
 115
 116#endif
 117