include/os/linux/spl/sys/list.h

   1 /*
   2  *  Copyright (C) 2007-2010 Lawrence Livermore National Security, LLC.
   3  *  Copyright (C) 2007 The Regents of the University of California.
   4  *  Produced at Lawrence Livermore National Laboratory (cf, DISCLAIMER).
   5  *  Written by Brian Behlendorf <behlendorf1@llnl.gov>.
   6  *  UCRL-CODE-235197
   7  *
   8  *  This file is part of the SPL, Solaris Porting Layer.
   9  *
  10  *  The SPL is free software; you can redistribute it and/or modify it
  11  *  under the terms of the GNU General Public License as published by the
  12  *  Free Software Foundation; either version 2 of the License, or (at your
  13  *  option) any later version.
  14  *
  15  *  The SPL is distributed in the hope that it will be useful, but WITHOUT
  16  *  ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  17  *  FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  18  *  for more details.
  19  *
  20  *  You should have received a copy of the GNU General Public License along
  21  *  with the SPL.  If not, see <http://www.gnu.org/licenses/>.
  22  */
  23
  24 #ifndef _SPL_LIST_H
  25 #define _SPL_LIST_H
  26
  27 #include <sys/types.h>
  28 #include <sys/debug.h>
  29 #include <linux/list.h>
  30
  31 /*
  32  * NOTE: I have implemented the Solaris list API in terms of the native
  33  * linux API.  This has certain advantages in terms of leveraging the linux
  34  * list debugging infrastructure, but it also means that the internals of a
  35  * list differ slightly than on Solaris.  This is not a problem as long as
  36  * all callers stick to the published API.  The two major differences are:
  37  *
  38  * 1) A list_node_t is mapped to a linux list_head struct which changes
  39  *    the name of the list_next/list_prev pointers to next/prev respectively.
  40  *
  41  * 2) A list_node_t which is not attached to a list on Solaris is denoted
  42  *    by having its list_next/list_prev pointers set to NULL.  Under linux
  43  *    the next/prev pointers are set to LIST_POISON1 and LIST_POISON2
  44  *    respectively.  At this moment this only impacts the implementation
  45  *    of the list_link_init() and list_link_active() functions.
  46  */
  47
  48 typedef struct list_head list_node_t;
  49
  50 typedef struct list {
  51         size_t list_size;
  52         size_t list_offset;
  53         list_node_t list_head;
  54 } list_t;
  55
  56 #define list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
  57 #define list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
  58
  59 static inline int
  60 list_is_empty(list_t *list)
  61 {
  62         return (list_empty(&list->list_head));
  63 }
  64
  65 static inline void
  66 list_link_init(list_node_t *node)
  67 {
  68         node->next = LIST_POISON1;
  69         node->prev = LIST_POISON2;
  70 }
  71
  72 static inline void
  73 list_create(list_t *list, size_t size, size_t offset)
  74 {
  75         list->list_size = size;
  76         list->list_offset = offset;
  77         INIT_LIST_HEAD(&list->list_head);
  78 }
  79
  80 static inline void
  81 list_destroy(list_t *list)
  82 {
  83         list_del(&list->list_head);
  84 }
  85
  86 static inline void
  87 list_insert_head(list_t *list, void *object)
  88 {
  89         list_add(list_d2l(list, object), &list->list_head);
  90 }
  91
  92 static inline void
  93 list_insert_tail(list_t *list, void *object)
  94 {
  95         list_add_tail(list_d2l(list, object), &list->list_head);
  96 }
  97
  98 static inline void
  99 list_insert_after(list_t *list, void *object, void *nobject)
 100 {
 101         if (object == NULL)
 102                 list_insert_head(list, nobject);
 103         else
 104                 list_add(list_d2l(list, nobject), list_d2l(list, object));
 105 }
 106
 107 static inline void
 108 list_insert_before(list_t *list, void *object, void *nobject)
 109 {
 110         if (object == NULL)
 111                 list_insert_tail(list, nobject);
 112         else
 113                 list_add_tail(list_d2l(list, nobject), list_d2l(list, object));
 114 }
 115
 116 static inline void
 117 list_remove(list_t *list, void *object)
 118 {
 119         list_del(list_d2l(list, object));
 120 }
 121
 122 static inline void *
 123 list_remove_head(list_t *list)
 124 {
 125         list_node_t *head = list->list_head.next;
 126         if (head == &list->list_head)
 127                 return (NULL);
 128
 129         list_del(head);
 130         return (list_object(list, head));
 131 }
 132
 133 static inline void *
 134 list_remove_tail(list_t *list)
 135 {
 136         list_node_t *tail = list->list_head.prev;
 137         if (tail == &list->list_head)
 138                 return (NULL);
 139
 140         list_del(tail);
 141         return (list_object(list, tail));
 142 }
 143
 144 static inline void *
 145 list_head(list_t *list)
 146 {
 147         if (list_is_empty(list))
 148                 return (NULL);
 149
 150         return (list_object(list, list->list_head.next));
 151 }
 152
 153 static inline void *
 154 list_tail(list_t *list)
 155 {
 156         if (list_is_empty(list))
 157                 return (NULL);
 158
 159         return (list_object(list, list->list_head.prev));
 160 }
 161
 162 static inline void *
 163 list_next(list_t *list, void *object)
 164 {
 165         list_node_t *node = list_d2l(list, object);
 166
 167         if (node->next != &list->list_head)
 168                 return (list_object(list, node->next));
 169
 170         return (NULL);
 171 }
 172
 173 static inline void *
 174 list_prev(list_t *list, void *object)
 175 {
 176         list_node_t *node = list_d2l(list, object);
 177
 178         if (node->prev != &list->list_head)
 179                 return (list_object(list, node->prev));
 180
 181         return (NULL);
 182 }
 183
 184 static inline int
 185 list_link_active(list_node_t *node)
 186 {
 187         EQUIV(node->next == LIST_POISON1, node->prev == LIST_POISON2);
 188         return (node->next != LIST_POISON1);
 189 }
 190
 191 static inline void
 192 spl_list_move_tail(list_t *dst, list_t *src)
 193 {
 194         list_splice_init(&src->list_head, dst->list_head.prev);
 195 }
 196
 197 #define list_move_tail(dst, src)        spl_list_move_tail(dst, src)
 198
 199 static inline void
 200 list_link_replace(list_node_t *old_node, list_node_t *new_node)
 201 {
 202         new_node->next = old_node->next;
 203         new_node->prev = old_node->prev;
 204         old_node->prev->next = new_node;
 205         old_node->next->prev = new_node;
 206         list_link_init(old_node);
 207 }
 208
 209 #endif /* SPL_LIST_H */