WebSVN – HelenOS – Blame – //trunk/uspace/lib/libc/include/adt/list.h

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

Subversion Repositories HelenOS

(root)//trunk/uspace/lib/libc/include/adt/list.h – Rev 4509