path: root/ntfsprogs/list.h (plain)
blob: 4db45d4ee589714a7c9972558184633855218dbd

1	/*
2	* list.h - Linked list implementation. Part of the Linux-NTFS project.
3	*
4	* Copyright (c) 2000-2002 Anton Altaparmakov and others
5	*
6	* This program/include file is free software; you can redistribute it and/or
7	* modify it under the terms of the GNU General Public License as published
8	* by the Free Software Foundation; either version 2 of the License, or
9	* (at your option) any later version.
10	*
11	* This program/include file is distributed in the hope that it will be
12	* useful, but WITHOUT ANY WARRANTY; without even the implied warranty
13	* of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14	* GNU General Public License for more details.
15	*
16	* You should have received a copy of the GNU General Public License
17	* along with this program (in the main directory of the Linux-NTFS
18	* distribution in the file COPYING); if not, write to the Free Software
19	* Foundation,Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20	*/
21
22	#ifndef _NTFS_LIST_H
23	#define _NTFS_LIST_H
24
25	/**
26	* struct ntfs_list_head - Simple doubly linked list implementation.
27	*
28	* Copied from Linux kernel 2.4.2-ac18 into Linux-NTFS (with minor
29	* modifications). - AIA
30	*
31	* Some of the internal functions ("__xxx") are useful when
32	* manipulating whole lists rather than single entries, as
33	* sometimes we already know the next/prev entries and we can
34	* generate better code by using them directly rather than
35	* using the generic single-entry routines.
36	*/
37	struct ntfs_list_head {
38	struct ntfs_list_head *next, *prev;
39	};
40
41	#define NTFS_LIST_HEAD_INIT(name) { &(name), &(name) }
42
43	#define NTFS_LIST_HEAD(name) \
44	struct ntfs_list_head name = NTFS_LIST_HEAD_INIT(name)
45
46	#define NTFS_INIT_LIST_HEAD(ptr) do { \
47	(ptr)->next = (ptr); (ptr)->prev = (ptr); \
48	} while (0)
49
50	/**
51	* __ntfs_list_add - Insert a new entry between two known consecutive entries.
52	* @new:
53	* @prev:
54	* @next:
55	*
56	* This is only for internal list manipulation where we know the prev/next
57	* entries already!
58	*/
59	static __inline__ void __ntfs_list_add(struct ntfs_list_head * new,
60	struct ntfs_list_head * prev, struct ntfs_list_head * next)
61	{
62	next->prev = new;
63	new->next = next;
64	new->prev = prev;
65	prev->next = new;
66	}
67
68	/**
69	* ntfs_list_add - add a new entry
70	* @new: new entry to be added
71	* @head: list head to add it after
72	*
73	* Insert a new entry after the specified head.
74	* This is good for implementing stacks.
75	*/
76	static __inline__ void ntfs_list_add(struct ntfs_list_head *new,
77	struct ntfs_list_head *head)
78	{
79	__ntfs_list_add(new, head, head->next);
80	}
81
82	/**
83	* ntfs_list_add_tail - add a new entry
84	* @new: new entry to be added
85	* @head: list head to add it before
86	*
87	* Insert a new entry before the specified head.
88	* This is useful for implementing queues.
89	*/
90	static __inline__ void ntfs_list_add_tail(struct ntfs_list_head *new,
91	struct ntfs_list_head *head)
92	{
93	__ntfs_list_add(new, head->prev, head);
94	}
95
96	/**
97	* __ntfs_list_del -
98	* @prev:
99	* @next:
100	*
101	* Delete a list entry by making the prev/next entries point to each other.
102	*
103	* This is only for internal list manipulation where we know the prev/next
104	* entries already!
105	*/
106	static __inline__ void __ntfs_list_del(struct ntfs_list_head * prev,
107	struct ntfs_list_head * next)
108	{
109	next->prev = prev;
110	prev->next = next;
111	}
112
113	/**
114	* ntfs_list_del - deletes entry from list.
115	* @entry: the element to delete from the list.
116	*
117	* Note: ntfs_list_empty on entry does not return true after this, the entry is
118	* in an undefined state.
119	*/
120	static __inline__ void ntfs_list_del(struct ntfs_list_head *entry)
121	{
122	__ntfs_list_del(entry->prev, entry->next);
123	}
124
125	/**
126	* ntfs_list_del_init - deletes entry from list and reinitialize it.
127	* @entry: the element to delete from the list.
128	*/
129	static __inline__ void ntfs_list_del_init(struct ntfs_list_head *entry)
130	{
131	__ntfs_list_del(entry->prev, entry->next);
132	NTFS_INIT_LIST_HEAD(entry);
133	}
134
135	/**
136	* ntfs_list_empty - tests whether a list is empty
137	* @head: the list to test.
138	*/
139	static __inline__ int ntfs_list_empty(struct ntfs_list_head *head)
140	{
141	return head->next == head;
142	}
143
144	/**
145	* ntfs_list_splice - join two lists
146	* @list: the new list to add.
147	* @head: the place to add it in the first list.
148	*/
149	static __inline__ void ntfs_list_splice(struct ntfs_list_head *list,
150	struct ntfs_list_head *head)
151	{
152	struct ntfs_list_head *first = list->next;
153
154	if (first != list) {
155	struct ntfs_list_head *last = list->prev;
156	struct ntfs_list_head *at = head->next;
157
158	first->prev = head;
159	head->next = first;
160
161	last->next = at;
162	at->prev = last;
163	}
164	}
165
166	/**
167	* ntfs_list_entry - get the struct for this entry
168	* @ptr: the &struct ntfs_list_head pointer.
169	* @type: the type of the struct this is embedded in.
170	* @member: the name of the list_struct within the struct.
171	*/
172	#define ntfs_list_entry(ptr, type, member) \
173	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
174
175	/**
176	* ntfs_list_for_each - iterate over a list
177	* @pos: the &struct ntfs_list_head to use as a loop counter.
178	* @head: the head for your list.
179	*/
180	#define ntfs_list_for_each(pos, head) \
181	for (pos = (head)->next; pos != (head); pos = pos->next)
182
183	/**
184	* ntfs_list_for_each_safe - iterate over a list safe against removal of list entry
185	* @pos: the &struct ntfs_list_head to use as a loop counter.
186	* @n: another &struct ntfs_list_head to use as temporary storage
187	* @head: the head for your list.
188	*/
189	#define ntfs_list_for_each_safe(pos, n, head) \
190	for (pos = (head)->next, n = pos->next; pos != (head); \
191	pos = n, n = pos->next)
192
193	#endif /* defined _NTFS_LIST_H */
194
195