WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/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 genericadt
 * @{
 */
/** @file
 */
 
#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/adt/list.h – Rev 788 → 1702

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