WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/include/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.
 */
 
#ifndef __LIST_H__
#define __LIST_H__
 
#include <arch/types.h>
#include <typedefs.h>
 
/** 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 bool 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 *)(((__u8*)(link))-((__u8*)&(((type *)NULL)->member)))
 
extern bool 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)/kernel/trunk/generic/include/list.h – Rev 534 → 624

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