WebSVN – HelenOS – Diff – /branches/dd/uspace/lib/libc/include/libadt/list.h


/*
 * Copyright (c) 2001-2004 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
/** @addtogroup libc
 * @{
 */
/** @file
 */
 
#ifndef LIBC_LIST_H_
#define LIBC_LIST_H_
 
#include <unistd.h>
 
 
 
 
 
 
 
 
 
 
/** Doubly linked list head and link type. */
typedef struct link {
    struct link *prev;  /**< Pointer to the previous item in the list. */
    struct link *next;  /**< Pointer to the next item in the list. */
} link_t;
 
/** Declare and initialize statically allocated list.
 *
 * @param name Name of the new statically allocated list.
 */
#define LIST_INITIALIZE(name)  link_t name = { \
    .prev = &name, \
    .next = &name \
}
 
/** Initialize doubly-linked circular list link
 *
 * Initialize doubly-linked list link.
 *
 * @param link Pointer to link_t structure to be initialized.
 */
static inline void link_initialize(link_t *link)
{
    link->prev = NULL;
    link->next = NULL;
}
 
/** Initialize doubly-linked circular list
 *
 * Initialize doubly-linked circular list.
 *
 * @param head Pointer to link_t structure representing head of the list.
 */
static inline void list_initialize(link_t *head)
{
    head->prev = head;
    head->next = head;
}
 
/** Add item to the beginning of doubly-linked circular list
 *
 * Add item to the beginning of doubly-linked circular list.
 *
 * @param link Pointer to link_t structure to be added.
 * @param head Pointer to link_t structure representing head of the list.
 */
static inline void list_prepend(link_t *link, link_t *head)
{
    link->next = head->next;
    link->prev = head;
    head->next->prev = link;
    head->next = link;
}
 
/** Add item to the end of doubly-linked circular list
 *
 * Add item to the end of doubly-linked circular list.
 *
 * @param link Pointer to link_t structure to be added.
 * @param head Pointer to link_t structure representing head of the list.
 */
static inline void list_append(link_t *link, link_t *head)
{
    link->prev = head->prev;
    link->next = head;
    head->prev->next = link;
    head->prev = link;
}
 
/** Insert item before another item in doubly-linked circular list. */
static inline void list_insert_before(link_t *l, link_t *r)
{
    list_append(l, r);
}
 
/** Insert item after another item in doubly-linked circular list. */
static inline void list_insert_after(link_t *r, link_t *l)
{
    list_prepend(l, r);
}
 
/** Remove item from doubly-linked circular list
 *
 * Remove item from doubly-linked circular list.
 *
 * @param link Pointer to link_t structure to be removed from the list it is contained in.
 */
static inline void list_remove(link_t *link)
{
    link->next->prev = link->prev;
    link->prev->next = link->next;
    link_initialize(link);
}
 
/** Query emptiness of doubly-linked circular list
 *
 * Query emptiness of doubly-linked circular list.
 *
 * @param head Pointer to link_t structure representing head of the list.
 */
static inline int list_empty(link_t *head)
{
    return ((head->next == head) ? 1 : 0);
}
 
 
/** Split or concatenate headless doubly-linked circular list
 *
 * Split or concatenate headless doubly-linked circular list.
 *
 * Note that the algorithm works both directions:
 * concatenates splitted lists and splits concatenated lists.
 *
 * @param part1 Pointer to link_t structure leading the first (half of the headless) list.
 * @param part2 Pointer to link_t structure leading the second (half of the headless) list.
 */
static inline void headless_list_split_or_concat(link_t *part1, link_t *part2)
{
 
 
    part1->prev->next = part2;
    part2->prev->next = part1;
   
    link_t *hlp = part1->prev;
   
    part1->prev = part2->prev;
    part2->prev = hlp;
}
 
 
/** Split headless doubly-linked circular list
 *
 * Split headless doubly-linked circular list.
 *
 * @param part1 Pointer to link_t structure leading the first half of the headless list.
 * @param part2 Pointer to link_t structure leading the second half of the headless list.
 */
static inline void headless_list_split(link_t *part1, link_t *part2)
{
    headless_list_split_or_concat(part1, part2);
}
 
/** Concatenate two headless doubly-linked circular lists
 *
 * Concatenate two headless doubly-linked circular lists.
 *
 * @param part1 Pointer to link_t structure leading the first headless list.
 * @param part2 Pointer to link_t structure leading the second headless list.
 */
static inline void headless_list_concat(link_t *part1, link_t *part2)
{
    headless_list_split_or_concat(part1, part2);
}
 
#define list_get_instance(link, type, member)  ((type *) (((void *)(link)) - ((void *) &(((type *) NULL)->member))))
 
extern int list_member(const link_t *link, const link_t *head);
extern void list_concat(link_t *head1, link_t *head2);
extern unsigned int list_count(const link_t *link);
 
#endif
 
/** @}
 */
 

Subversion Repositories HelenOS

(root)/branches/dd/uspace/lib/libc/include/libadt/list.h – Rev 3022 → 4420

Rev 3022		Rev 4420
1	/*	1	/*
2	* Copyright (c) 2001-2004 Jakub Jermar	2	* Copyright (c) 2001-2004 Jakub Jermar
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	/** @addtogroup libc	29	/** @addtogroup libc
30	* @{	30	* @{
31	*/	31	*/
32	/** @file	32	/** @file
33	*/	33	*/
34		34
35	#ifndef LIBC_LIST_H_	35	#ifndef LIBC_LIST_H_
36	#define LIBC_LIST_H_	36	#define LIBC_LIST_H_
37		37
38	#include <unistd.h>	38	#include <unistd.h>
39		39
40	#ifndef true	-
41	# define true 1	-
42	#endif	-
43	#ifndef false	-
44	# define false 0	-
45	#endif	-
46		-
47	typedef struct link link_t;	-
48		-
49	/** Doubly linked list head and link type. */	40	/** Doubly linked list head and link type. */
50	struct link {	41	typedef struct link {
51	link_t prev; /< Pointer to the previous item in the list. /	42	struct link prev; /< Pointer to the previous item in the list. /
52	link_t next; /< Pointer to the next item in the list. /	43	struct link next; /< Pointer to the next item in the list. /
53	};	44	} link_t;
54		45
55	/** Declare and initialize statically allocated list.	46	/** Declare and initialize statically allocated list.
56	*	47	*
57	* @param name Name of the new statically allocated list.	48	* @param name Name of the new statically allocated list.
58	*/	49	*/
59	#define LIST_INITIALIZE(name) link_t name = { .prev = &name, .next = &name }	50	#define LIST_INITIALIZE(name) link_t name = { \
-		51	.prev = &name, \
-		52	.next = &name \
-		53	}
60		54
61	/** Initialize doubly-linked circular list link	55	/** Initialize doubly-linked circular list link
62	*	56	*
63	* Initialize doubly-linked list link.	57	* Initialize doubly-linked list link.
64	*	58	*
65	* @param link Pointer to link_t structure to be initialized.	59	* @param link Pointer to link_t structure to be initialized.
66	*/	60	*/
67	static inline void link_initialize(link_t *link)	61	static inline void link_initialize(link_t *link)
68	{	62	{
69	link->prev = NULL;	63	link->prev = NULL;
70	link->next = NULL;	64	link->next = NULL;
71	}	65	}
72		66
73	/** Initialize doubly-linked circular list	67	/** Initialize doubly-linked circular list
74	*	68	*
75	* Initialize doubly-linked circular list.	69	* Initialize doubly-linked circular list.
76	*	70	*
77	* @param head Pointer to link_t structure representing head of the list.	71	* @param head Pointer to link_t structure representing head of the list.
78	*/	72	*/
79	static inline void list_initialize(link_t *head)	73	static inline void list_initialize(link_t *head)
80	{	74	{
81	head->prev = head;	75	head->prev = head;
82	head->next = head;	76	head->next = head;
83	}	77	}
84		78
85	/** Add item to the beginning of doubly-linked circular list	79	/** Add item to the beginning of doubly-linked circular list
86	*	80	*
87	* Add item to the beginning of doubly-linked circular list.	81	* Add item to the beginning of doubly-linked circular list.
88	*	82	*
89	* @param link Pointer to link_t structure to be added.	83	* @param link Pointer to link_t structure to be added.
90	* @param head Pointer to link_t structure representing head of the list.	84	* @param head Pointer to link_t structure representing head of the list.
91	*/	85	*/
92	static inline void list_prepend(link_t link, link_t head)	86	static inline void list_prepend(link_t link, link_t head)
93	{	87	{
94	link->next = head->next;	88	link->next = head->next;
95	link->prev = head;	89	link->prev = head;
96	head->next->prev = link;	90	head->next->prev = link;
97	head->next = link;	91	head->next = link;
98	}	92	}
99		93
100	/** Add item to the end of doubly-linked circular list	94	/** Add item to the end of doubly-linked circular list
101	*	95	*
102	* Add item to the end of doubly-linked circular list.	96	* Add item to the end of doubly-linked circular list.
103	*	97	*
104	* @param link Pointer to link_t structure to be added.	98	* @param link Pointer to link_t structure to be added.
105	* @param head Pointer to link_t structure representing head of the list.	99	* @param head Pointer to link_t structure representing head of the list.
106	*/	100	*/
107	static inline void list_append(link_t link, link_t head)	101	static inline void list_append(link_t link, link_t head)
108	{	102	{
109	link->prev = head->prev;	103	link->prev = head->prev;
110	link->next = head;	104	link->next = head;
111	head->prev->next = link;	105	head->prev->next = link;
112	head->prev = link;	106	head->prev = link;
113	}	107	}
114		108
115	/** Insert item before another item in doubly-linked circular list. */	109	/** Insert item before another item in doubly-linked circular list. */
116	static inline void list_insert_before(link_t l, link_t r)	110	static inline void list_insert_before(link_t l, link_t r)
117	{	111	{
118	list_append(l, r);	112	list_append(l, r);
119	}	113	}
120		114
121	/** Insert item after another item in doubly-linked circular list. */	115	/** Insert item after another item in doubly-linked circular list. */
122	static inline void list_insert_after(link_t r, link_t l)	116	static inline void list_insert_after(link_t r, link_t l)
123	{	117	{
124	list_prepend(l, r);	118	list_prepend(l, r);
125	}	119	}
126		120
127	/** Remove item from doubly-linked circular list	121	/** Remove item from doubly-linked circular list
128	*	122	*
129	* Remove item from doubly-linked circular list.	123	* Remove item from doubly-linked circular list.
130	*	124	*
131	* @param link Pointer to link_t structure to be removed from the list it is contained in.	125	* @param link Pointer to link_t structure to be removed from the list it is contained in.
132	*/	126	*/
133	static inline void list_remove(link_t *link)	127	static inline void list_remove(link_t *link)
134	{	128	{
135	link->next->prev = link->prev;	129	link->next->prev = link->prev;
136	link->prev->next = link->next;	130	link->prev->next = link->next;
137	link_initialize(link);	131	link_initialize(link);
138	}	132	}
139		133
140	/** Query emptiness of doubly-linked circular list	134	/** Query emptiness of doubly-linked circular list
141	*	135	*
142	* Query emptiness of doubly-linked circular list.	136	* Query emptiness of doubly-linked circular list.
143	*	137	*
144	* @param head Pointer to link_t structure representing head of the list.	138	* @param head Pointer to link_t structure representing head of the list.
145	*/	139	*/
146	static inline int list_empty(link_t *head)	140	static inline int list_empty(link_t *head)
147	{	141	{
148	return head->next == head ? true : false;	142	return ((head->next == head) ? 1 : 0);
149	}	143	}
150		144
151		145
152	/** Split or concatenate headless doubly-linked circular list	146	/** Split or concatenate headless doubly-linked circular list
153	*	147	*
154	* Split or concatenate headless doubly-linked circular list.	148	* Split or concatenate headless doubly-linked circular list.
155	*	149	*
156	* Note that the algorithm works both directions:	150	* Note that the algorithm works both directions:
157	* concatenates splitted lists and splits concatenated lists.	151	* concatenates splitted lists and splits concatenated lists.
158	*	152	*
159	* @param part1 Pointer to link_t structure leading the first (half of the headless) list.	153	* @param part1 Pointer to link_t structure leading the first (half of the headless) list.
160	* @param part2 Pointer to link_t structure leading the second (half of the headless) list.	154	* @param part2 Pointer to link_t structure leading the second (half of the headless) list.
161	*/	155	*/
162	static inline void headless_list_split_or_concat(link_t part1, link_t part2)	156	static inline void headless_list_split_or_concat(link_t part1, link_t part2)
163	{	157	{
164	link_t *hlp;	-
165		-
166	part1->prev->next = part2;	158	part1->prev->next = part2;
167	part2->prev->next = part1;	159	part2->prev->next = part1;
-		160
168	hlp = part1->prev;	161	link_t *hlp = part1->prev;
-		162
169	part1->prev = part2->prev;	163	part1->prev = part2->prev;
170	part2->prev = hlp;	164	part2->prev = hlp;
171	}	165	}
172		166
173		167
174	/** Split headless doubly-linked circular list	168	/** Split headless doubly-linked circular list
175	*	169	*
176	* Split headless doubly-linked circular list.	170	* Split headless doubly-linked circular list.
177	*	171	*
178	* @param part1 Pointer to link_t structure leading the first half of the headless list.	172	* @param part1 Pointer to link_t structure leading the first half of the headless list.
179	* @param part2 Pointer to link_t structure leading the second half of the headless list.	173	* @param part2 Pointer to link_t structure leading the second half of the headless list.
180	*/	174	*/
181	static inline void headless_list_split(link_t part1, link_t part2)	175	static inline void headless_list_split(link_t part1, link_t part2)
182	{	176	{
183	headless_list_split_or_concat(part1, part2);	177	headless_list_split_or_concat(part1, part2);
184	}	178	}
185		179
186	/** Concatenate two headless doubly-linked circular lists	180	/** Concatenate two headless doubly-linked circular lists
187	*	181	*
188	* Concatenate two headless doubly-linked circular lists.	182	* Concatenate two headless doubly-linked circular lists.
189	*	183	*
190	* @param part1 Pointer to link_t structure leading the first headless list.	184	* @param part1 Pointer to link_t structure leading the first headless list.
191	* @param part2 Pointer to link_t structure leading the second headless list.	185	* @param part2 Pointer to link_t structure leading the second headless list.
192	*/	186	*/
193	static inline void headless_list_concat(link_t part1, link_t part2)	187	static inline void headless_list_concat(link_t part1, link_t part2)
194	{	188	{
195	headless_list_split_or_concat(part1, part2);	189	headless_list_split_or_concat(part1, part2);
196	}	190	}
197		191
198	#define list_get_instance(link,type,member) (type )(((char )(link))-((char )&(((type )NULL)->member)))	192	#define list_get_instance(link, type, member) ((type ) (((void )(link)) - ((void ) &(((type ) NULL)->member))))
199		193
200	extern int list_member(const link_t link, const link_t head);	194	extern int list_member(const link_t link, const link_t head);
201	extern void list_concat(link_t head1, link_t head2);	195	extern void list_concat(link_t head1, link_t head2);
-		196	extern unsigned int list_count(const link_t *link);
202		197
203	#endif	198	#endif
204		199
205	/** @}	200	/** @}
206	*/	201	*/
207		202