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

Subversion Repositories HelenOS

(root)/trunk/uspace/lib/libc/include/libadt/list.h – Rev 2879