LXR linux/include/linux/list

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