WebSVN – HelenOS-historic – Blame – /uspace/trunk/libc/include/libadt/list.h

Rev	Author	Line No.	Line
996	cejka	1	/*
		2	* Copyright (C) 2001-2004 Jakub Jermar
		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
1653	cejka	29	/** @addtogroup libc
		30	* @{
		31	*/
		32	/** @file
		33	*/
		34
996	cejka	35	#ifndef __LIST_H__
		36	#define __LIST_H__
		37
		38	#include<unistd.h>
		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
		115	/** Remove item from doubly-linked circular list
		116	*
		117	* Remove item from doubly-linked circular list.
		118	*
		119	* @param link Pointer to link_t structure to be removed from the list it is contained in.
		120	*/
		121	static inline void list_remove(link_t *link)
		122	{
		123	link->next->prev = link->prev;
		124	link->prev->next = link->next;
		125	link_initialize(link);
		126	}
		127
		128	/** Query emptiness of doubly-linked circular list
		129	*
		130	* Query emptiness of doubly-linked circular list.
		131	*
		132	* @param head Pointer to link_t structure representing head of the list.
		133	*/
		134	static inline int list_empty(link_t *head)
		135	{
		136	return head->next == head ? true : false;
		137	}
		138
		139
		140	/** Split or concatenate headless doubly-linked circular list
		141	*
		142	* Split or concatenate headless doubly-linked circular list.
		143	*
		144	* Note that the algorithm works both directions:
		145	* concatenates splitted lists and splits concatenated lists.
		146	*
		147	* @param part1 Pointer to link_t structure leading the first (half of the headless) list.
		148	* @param part2 Pointer to link_t structure leading the second (half of the headless) list.
		149	*/
		150	static inline void headless_list_split_or_concat(link_t part1, link_t part2)
		151	{
		152	link_t *hlp;
		153
		154	part1->prev->next = part2;
		155	part2->prev->next = part1;
		156	hlp = part1->prev;
		157	part1->prev = part2->prev;
		158	part2->prev = hlp;
		159	}
		160
		161
		162	/** Split headless doubly-linked circular list
		163	*
		164	* Split headless doubly-linked circular list.
		165	*
		166	* @param part1 Pointer to link_t structure leading the first half of the headless list.
		167	* @param part2 Pointer to link_t structure leading the second half of the headless list.
		168	*/
		169	static inline void headless_list_split(link_t part1, link_t part2)
		170	{
		171	headless_list_split_or_concat(part1, part2);
		172	}
		173
		174	/** Concatenate two headless doubly-linked circular lists
		175	*
		176	* Concatenate two headless doubly-linked circular lists.
		177	*
		178	* @param part1 Pointer to link_t structure leading the first headless list.
		179	* @param part2 Pointer to link_t structure leading the second headless list.
		180	*/
		181	static inline void headless_list_concat(link_t part1, link_t part2)
		182	{
		183	headless_list_split_or_concat(part1, part2);
		184	}
		185
999	palkovsky	186	#define list_get_instance(link,type,member) (type )(((char )(link))-((char )&(((type )NULL)->member)))
996	cejka	187
		188	extern int list_member(const link_t link, const link_t head);
		189	extern void list_concat(link_t head1, link_t head2);
		190
		191	#endif
1653	cejka	192
		193
		194	/** @}
		195	*/
		196
		197

Subversion Repositories HelenOS-historic

(root)/uspace/trunk/libc/include/libadt/list.h @ 1711 – Rev 1653