WebSVN – HelenOS-historic – Blame – /kernel/trunk/generic/include/adt/list.h

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

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/include/adt/list.h @ 1780 – Rev 380