WebSVN – HelenOS-historic – Diff – /uspace/trunk/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 __LIST_H__
#define __LIST_H__
 
#include<unistd.h>
 
#ifndef true
# define true 1
#endif
#ifndef false
# define false 0
#endif
 
typedef struct link link_t;
 
/** Doubly linked list head and link type. */
struct link {
    link_t *prev;   /**< Pointer to the previous item in the list. */
    link_t *next;   /**< Pointer to the next item in the list. */
};
 
/** 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;
}
 
/** 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 ? true : false;
}
 
 
/** 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)
{
    link_t *hlp;
 
    part1->prev->next = part2;
    part2->prev->next = part1; 
    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 *)(((char *)(link))-((char *)&(((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);
 
#endif
 
 
 /** @}
 */
 
 
 

Subversion Repositories HelenOS-historic

(root)/uspace/trunk/libc/include/libadt/list.h – Rev 1392 → 1653

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