1    	/*
2    	 * Copyright IBM Corporation, 2010
3    	 *  Contributor: Aneesh Kumar K.v  <aneesh.kumar@linux.vnet.ibm.com>
4    	 *
5    	 *
6    	 * This software is a server that implements the NFS protocol.
7    	 *
8    	 * This program is free software; you can redistribute it and/or
9    	 * modify it under the terms of the GNU Lesser General Public
10   	 * License as published by the Free Software Foundation; either
11   	 * version 3 of the License, or (at your option) any later version.
12   	 *
13   	 * This program is distributed in the hope that it will be useful,
14   	 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15   	 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16   	 * Lesser General Public License for more details.
17   	 *
18   	 * You should have received a copy of the GNU Lesser General Public
19   	 * License along with this library; if not, write to the Free Software
20   	 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
21   	 * 02110-1301 USA
22   	 *
23   	 * ---------------------------------------
24   	 *
25   	 *
26   	 */
27   	
28   	#ifndef _GANESHA_LIST_H
29   	#define _GANESHA_LIST_H
30   	
31   	#include <stddef.h>
32   	
33   	struct glist_head {
34   		struct glist_head *next;
35   		struct glist_head *prev;
36   	};
37   	
38   	/*
39   	 * @brief Compare routine that is used by glist_insert_sorted
40   	 *
41   	 * This routine can be defined by the calling function
42   	 * to enable a sorted insert
43   	 *
44   	 * @param struct glist_head *: The first element to compare
45   	 * @param struct glist_head *: The second element to compare
46   	 *
47   	 * @return  negative if the 1st element should appear before the 2nd element
48   	 *          0 if the 1st and 2nd element are equal
49   	 *          positive if the 1st element should appear after the 2nd element
50   	 */
51   	typedef int (*glist_compare) (struct glist_head *, struct glist_head *);
52   	
53   	/**
54   	 * @brief List head initialization
55   	 *
56   	 * These macros and functions are only for list heads,
57   	 * not nodes.  The head always points to something and
58   	 * if the list is empty, it points to itself.
59   	 */
60   	
61   	#define GLIST_HEAD_INIT(name) { &(name), &(name) }
62   	
63   	#define GLIST_HEAD(name) \
64   		struct glist_head name = GLIST_HEAD_INIT(name)
65   	
66   	static inline void glist_init(struct glist_head *head)
67   	{				/* XXX glist_init? */
68   		head->next = head;
69   		head->prev = head;
70   	}
71   	
72   	/* Add the new element between left and right */
73   	static inline void __glist_add(struct glist_head *left,
74   				       struct glist_head *right, struct glist_head *elt)
75   	{
76   		elt->prev = left;
77   		elt->next = right;
78   		left->next = elt;
79   		right->prev = elt;
80   	}
81   	
82   	static inline void glist_add_tail(struct glist_head *head,
83   					  struct glist_head *elt)
84   	{
85   	
86   		__glist_add(head->prev, head, elt);
87   	}
88   	
89   	/* add after the specified entry*/
90   	static inline void glist_add(struct glist_head *head, struct glist_head *elt)
91   	{
92   		__glist_add(head, head->next, elt);
93   	}
94   	
95   	static inline void glist_del(struct glist_head *node)
96   	{
(1) Event deref_parm: Directly dereferencing parameter "node".
97   		struct glist_head *left = node->prev;
98   		struct glist_head *right = node->next;
99   	
100  		if (left != NULL)
101  			left->next = right;
102  		if (right != NULL)
103  			right->prev = left;
104  		node->next = NULL;
105  		node->prev = NULL;
106  	}
107  	
108  	/**
109  	 * @brief Test if the list in this head is empty
110  	 */
111  	static inline int glist_empty(struct glist_head *head)
112  	{
113  		return head->next == head;
114  	}
115  	
116  	/**
117  	 * @brief Test if this node is not on a list.
118  	 *
119  	 * NOT to be confused with glist_empty which is just
120  	 * for heads.  We poison with NULL for disconnected nodes.
121  	 */
122  	
123  	static inline int glist_null(struct glist_head *head)
124  	{
125  		return (head->next == NULL) && (head->prev == NULL);
126  	}
127  	
128  	static inline void glist_add_list_tail(struct glist_head *list,
129  					       struct glist_head *elt)
130  	{
131  		struct glist_head *first = elt->next;
132  		struct glist_head *last = elt->prev;
133  	
134  		if (glist_empty(elt)) {
135  			/* nothing to add */
136  			return;
137  		}
138  	
139  		first->prev = list->prev;
140  		list->prev->next = first;
141  	
142  		last->next = list;
143  		list->prev = last;
144  	}
145  	
146  	/* Move all of src onto the tail of tgt.  Clears src. */
147  	static inline void glist_splice_tail(struct glist_head *tgt,
148  					     struct glist_head *src)
149  	{
150  		if (glist_empty(src))
151  			return;
152  	
153  		src->next->prev = tgt->prev;
154  		tgt->prev->next = src->next;
155  		src->prev->next = tgt;
156  		tgt->prev = src->prev;
157  	
158  		glist_init(src);
159  	}
160  	
161  	static inline void glist_swap_lists(struct glist_head *l1,
162  					    struct glist_head *l2)
163  	{
164  		struct glist_head temp;
165  	
166  		if (glist_empty(l1)) {
167  			/* l1 was empty, so splice tail will accomplish swap. */
168  			glist_splice_tail(l1, l2);
169  			return;
170  		}
171  	
172  		if (glist_empty(l2)) {
173  			/* l2 was empty, so reverse splice tail will accomplish swap. */
174  			glist_splice_tail(l2, l1);
175  			return;
176  		}
177  	
178  		/* Both lists are non-empty */
179  	
180  		/* First swap the list pointers. */
181  		temp = *l1;
182  		*l1 = *l2;
183  		*l2 = temp;
184  	
185  		/* Then fixup first entry in each list prev to point to it's new head */
186  		l1->next->prev = l1;
187  		l2->next->prev = l2;
188  	
189  		/* And fixup the last entry in each list next to point to it's new head
190  		 */
191  		l1->prev->next = l1;
192  		l2->prev->next = l2;
193  	}
194  	
195  	/**
196  	 * @brief Split list list1 into list2 at element.
197  	 *
198  	 * @note list2 is expected to be empty. list1 is expected to be non-empty (i.e.
199  	 * element is NOT list1).
200  	 *
201  	 * @param[in,out] list1    Source list.
202  	 * @param[in,out] list2    Destination list.
203  	 * @param[in,out] element  List element to become first element in list2.
204  	 *
205  	 */
206  	static inline void glist_split(struct glist_head *list1,
207  				       struct glist_head *list2,
208  				       struct glist_head *element)
209  	{
210  		/* Set up list2 to contain element to the end. */
211  		list2->next = element;
212  		list2->prev = list1->prev;
213  	
214  		/* Fixup the last element of list1 to be the last element of list2, even
215  		 * if it was element.
216  		 */
217  		list2->prev->next = list2;
218  	
219  		/* Now fixup list1 even if element was first element of list1. */
220  		list1->prev = element->prev;
221  	
222  		/* Now fixup prev of element, even if element was first element of
223  		 * list1.
224  		 */
225  		element->prev->next = list1;
226  	
227  		/* Now fixup element */
228  		element->prev = list2;
229  	}
230  	
231  	#define glist_for_each(node, head) \
232  		for (node = (head)->next; node != head; node = node->next)
233  	
234  	#define glist_for_each_next(start, node, head)				\
235  		for (node = (start)->next; node != head; node = node->next)
236  	
237  	static inline size_t glist_length(struct glist_head *head)
238  	{
239  		size_t length = 0;
240  		struct glist_head *dummy = NULL;
241  	
242  		glist_for_each(dummy, head) {
243  			++length;
244  		}
245  		return length;
246  	}
247  	
248  	#define container_of(addr, type, member) ({			\
249  		const typeof(((type *) 0)->member) * __mptr = (addr);	\
250  		(type *)((char *) __mptr - offsetof(type, member)); })
251  	
252  	#define glist_first_entry(head, type, member) \
253  		((head)->next != (head) ? \
254  		container_of((head)->next, type, member) : NULL)
255  	
256  	#define glist_last_entry(head, type, member) \
257  		((head)->prev != (head) ? \
258  		container_of((head)->prev, type, member) : NULL)
259  	
260  	#define glist_entry(node, type, member) \
261  		container_of(node, type, member)
262  	
263  	#define glist_for_each_safe(node, noden, head)		\
264  		for (node = (head)->next, noden = node->next;	\
265  		     node != (head);				\
266  		     node = noden, noden = node->next)
267  	
268  	#define glist_for_each_next_safe(start, node, noden, head)	\
269  		for (node = (start)->next, noden = node->next;	\
270  		     node != (head);				\
271  		     node = noden, noden = node->next)
272  	
273  	/* Return the next entry in the list after node if any. */
274  	#define glist_next_entry(head, type, member, node) \
275  		((node)->next != (head) ? \
276  		container_of((node)->next, type, member) : NULL)
277  	
278  	/* Return the previous entry in the list after node if any. */
279  	#define glist_prev_entry(head, type, member, node) \
280  		((node)->prev != (head) ? \
281  		container_of((node)->prev, type, member) : NULL)
282  	
283  	static inline void glist_insert_sorted(struct glist_head *head,
284  					       struct glist_head *elt,
285  					       glist_compare compare)
286  	{
287  		struct glist_head *next = NULL;
288  	
289  		if (glist_empty(head)) {
290  			glist_add_tail(head, elt);
291  			return;
292  		}
293  		glist_for_each(next, head) {
294  			if (compare(next, elt) > 0)
295  				break;
296  		}
297  	
298  		__glist_add(next->prev, next, elt);
299  	}
300  	
301  	#endif				/* _GANESHA_LIST_H */
302