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