WebSVN – HelenOS – Diff – /branches/dynload/uspace/lib/libc/include/adt/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/dynload/uspace/lib/libc/include/adt/list.h – Rev 4509 → 4691

Rev 4509		Rev 4691
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	/** Doubly linked list head and link type. */	40	/** Doubly linked list head and link type. */
41	typedef struct link {	41	typedef struct link {
42	struct link prev; /< Pointer to the previous item in the list. /	42	struct link prev; /< Pointer to the previous item in the list. /
43	struct link next; /< Pointer to the next item in the list. /	43	struct link next; /< Pointer to the next item in the list. /
44	} link_t;	44	} link_t;
45		45
46	/** Declare and initialize statically allocated list.	46	/** Declare and initialize statically allocated list.
47	*	47	*
48	* @param name Name of the new statically allocated list.	48	* @param name Name of the new statically allocated list.
49	*/	49	*/
50	#define LIST_INITIALIZE(name) link_t name = { \	50	#define LIST_INITIALIZE(name) link_t name = { \
51	.prev = &name, \	51	.prev = &name, \
52	.next = &name \	52	.next = &name \
53	}	53	}
54		54
55	/** Initialize doubly-linked circular list link	55	/** Initialize doubly-linked circular list link
56	*	56	*
57	* Initialize doubly-linked list link.	57	* Initialize doubly-linked list link.
58	*	58	*
59	* @param link Pointer to link_t structure to be initialized.	59	* @param link Pointer to link_t structure to be initialized.
60	*/	60	*/
61	static inline void link_initialize(link_t *link)	61	static inline void link_initialize(link_t *link)
62	{	62	{
63	link->prev = NULL;	63	link->prev = NULL;
64	link->next = NULL;	64	link->next = NULL;
65	}	65	}
66		66
67	/** Initialize doubly-linked circular list	67	/** Initialize doubly-linked circular list
68	*	68	*
69	* Initialize doubly-linked circular list.	69	* Initialize doubly-linked circular list.
70	*	70	*
71	* @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.
72	*/	72	*/
73	static inline void list_initialize(link_t *head)	73	static inline void list_initialize(link_t *head)
74	{	74	{
75	head->prev = head;	75	head->prev = head;
76	head->next = head;	76	head->next = head;
77	}	77	}
78		78
79	/** Add item to the beginning of doubly-linked circular list	79	/** Add item to the beginning of doubly-linked circular list
80	*	80	*
81	* Add item to the beginning of doubly-linked circular list.	81	* Add item to the beginning of doubly-linked circular list.
82	*	82	*
83	* @param link Pointer to link_t structure to be added.	83	* @param link Pointer to link_t structure to be added.
84	* @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.
85	*/	85	*/
86	static inline void list_prepend(link_t link, link_t head)	86	static inline void list_prepend(link_t link, link_t head)
87	{	87	{
88	link->next = head->next;	88	link->next = head->next;
89	link->prev = head;	89	link->prev = head;
90	head->next->prev = link;	90	head->next->prev = link;
91	head->next = link;	91	head->next = link;
92	}	92	}
93		93
94	/** Add item to the end of doubly-linked circular list	94	/** Add item to the end of doubly-linked circular list
95	*	95	*
96	* Add item to the end of doubly-linked circular list.	96	* Add item to the end of doubly-linked circular list.
97	*	97	*
98	* @param link Pointer to link_t structure to be added.	98	* @param link Pointer to link_t structure to be added.
99	* @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.
100	*/	100	*/
101	static inline void list_append(link_t link, link_t head)	101	static inline void list_append(link_t link, link_t head)
102	{	102	{
103	link->prev = head->prev;	103	link->prev = head->prev;
104	link->next = head;	104	link->next = head;
105	head->prev->next = link;	105	head->prev->next = link;
106	head->prev = link;	106	head->prev = link;
107	}	107	}
108		108
109	/** Insert item before another item in doubly-linked circular list. */	109	/** Insert item before another item in doubly-linked circular list. */
110	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)
111	{	111	{
112	list_append(l, r);	112	list_append(l, r);
113	}	113	}
114		114
115	/** Insert item after another item in doubly-linked circular list. */	115	/** Insert item after another item in doubly-linked circular list. */
116	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)
117	{	117	{
118	list_prepend(l, r);	118	list_prepend(l, r);
119	}	119	}
120		120
121	/** Remove item from doubly-linked circular list	121	/** Remove item from doubly-linked circular list
122	*	122	*
123	* Remove item from doubly-linked circular list.	123	* Remove item from doubly-linked circular list.
124	*	124	*
125	* @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.
126	*/	126	*/
127	static inline void list_remove(link_t *link)	127	static inline void list_remove(link_t *link)
128	{	128	{
129	link->next->prev = link->prev;	129	link->next->prev = link->prev;
130	link->prev->next = link->next;	130	link->prev->next = link->next;
131	link_initialize(link);	131	link_initialize(link);
132	}	132	}
133		133
134	/** Query emptiness of doubly-linked circular list	134	/** Query emptiness of doubly-linked circular list
135	*	135	*
136	* Query emptiness of doubly-linked circular list.	136	* Query emptiness of doubly-linked circular list.
137	*	137	*
138	* @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.
139	*/	139	*/
140	static inline int list_empty(link_t *head)	140	static inline int list_empty(link_t *head)
141	{	141	{
142	return ((head->next == head) ? 1 : 0);	142	return ((head->next == head) ? 1 : 0);
143	}	143	}
144		144
145		145
146	/** Split or concatenate headless doubly-linked circular list	146	/** Split or concatenate headless doubly-linked circular list
147	*	147	*
148	* Split or concatenate headless doubly-linked circular list.	148	* Split or concatenate headless doubly-linked circular list.
149	*	149	*
150	* Note that the algorithm works both directions:	150	* Note that the algorithm works both directions:
151	* concatenates splitted lists and splits concatenated lists.	151	* concatenates splitted lists and splits concatenated lists.
152	*	152	*
153	* @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.
154	* @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.
155	*/	155	*/
156	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)
157	{	157	{
158	part1->prev->next = part2;	158	part1->prev->next = part2;
159	part2->prev->next = part1;	159	part2->prev->next = part1;
160		160
161	link_t *hlp = part1->prev;	161	link_t *hlp = part1->prev;
162		162
163	part1->prev = part2->prev;	163	part1->prev = part2->prev;
164	part2->prev = hlp;	164	part2->prev = hlp;
165	}	165	}
166		166
167		167
168	/** Split headless doubly-linked circular list	168	/** Split headless doubly-linked circular list
169	*	169	*
170	* Split headless doubly-linked circular list.	170	* Split headless doubly-linked circular list.
171	*	171	*
172	* @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.
173	* @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.
174	*/	174	*/
175	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)
176	{	176	{
177	headless_list_split_or_concat(part1, part2);	177	headless_list_split_or_concat(part1, part2);
178	}	178	}
179		179
180	/** Concatenate two headless doubly-linked circular lists	180	/** Concatenate two headless doubly-linked circular lists
181	*	181	*
182	* Concatenate two headless doubly-linked circular lists.	182	* Concatenate two headless doubly-linked circular lists.
183	*	183	*
184	* @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.
185	* @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.
186	*/	186	*/
187	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)
188	{	188	{
189	headless_list_split_or_concat(part1, part2);	189	headless_list_split_or_concat(part1, part2);
190	}	190	}
191		191
192	#define list_get_instance(link, type, member) ((type ) (((void )(link)) - ((void ) &(((type ) NULL)->member))))	192	#define list_get_instance(link, type, member) ((type ) (((void )(link)) - ((void ) &(((type ) NULL)->member))))
193		193
194	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);
195	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);	196	extern unsigned int list_count(const link_t *link);
197		197
198	#endif	198	#endif
199		199
200	/** @}	200	/** @}
201	*/	201	*/
202		202