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
48typedef struct list_head list_node_t;
49
50typedef struct list {
51	size_t list_offset;
52	list_node_t list_head;
53} list_t;
54
55#define	list_d2l(a, obj) ((list_node_t *)(((char *)obj) + (a)->list_offset))
56#define	list_object(a, node) ((void *)(((char *)node) - (a)->list_offset))
57
58static inline int
59list_is_empty(list_t *list)
60{
61	return (list_empty(&list->list_head));
62}
63
64static inline void
65list_link_init(list_node_t *node)
66{
67	node->next = LIST_POISON1;
68	node->prev = LIST_POISON2;
69}
70
71static inline void
72list_create(list_t *list, size_t size, size_t offset)
73{
74	(void) size;
75
76	list->list_offset = offset;
77	INIT_LIST_HEAD(&list->list_head);
78}
79
80static inline void
81list_destroy(list_t *list)
82{
83	list_del(&list->list_head);
84}
85
86static inline void
87list_insert_head(list_t *list, void *object)
88{
89	list_add(list_d2l(list, object), &list->list_head);
90}
91
92static inline void
93list_insert_tail(list_t *list, void *object)
94{
95	list_add_tail(list_d2l(list, object), &list->list_head);
96}
97
98static inline void
99list_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
107static inline void
108list_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
116static inline void
117list_remove(list_t *list, void *object)
118{
119	list_del(list_d2l(list, object));
120}
121
122static inline void *
123list_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
133static inline void *
134list_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
144static inline void *
145list_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
153static inline void *
154list_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
162static inline void *
163list_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
173static inline void *
174list_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
184static inline int
185list_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
191static inline void
192spl_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
199static inline void
200list_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 */
210