16dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 26dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \file simple_list.h 36dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Simple macros for type-safe, intrusive lists. 46dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 56dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Intended to work with a list sentinal which is created as an empty 66dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * list. Insert & delete are O(1). 76dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 86dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \author 96dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * (C) 1997, Keith Whitwell 106dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 11afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 12afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg/* 13afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Mesa 3-D graphics library 1422144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * Version: 3.5 1522144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 1622144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * Copyright (C) 1999-2001 Brian Paul All Rights Reserved. 1722144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 18afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Permission is hereby granted, free of charge, to any person obtaining a 19afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * copy of this software and associated documentation files (the "Software"), 20afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * to deal in the Software without restriction, including without limitation 21afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * the rights to use, copy, modify, merge, publish, distribute, sublicense, 22afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * and/or sell copies of the Software, and to permit persons to whom the 23afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * Software is furnished to do so, subject to the following conditions: 2422144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 25afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * The above copyright notice and this permission notice shall be included 26afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * in all copies or substantial portions of the Software. 2722144ab7552f0799bcfca506bf4ffa7f70a06649Gareth Hughes * 28afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 29afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 31afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 32afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 33afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 34afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 35afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 36afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 37afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#ifndef _SIMPLE_LIST_H 38afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define _SIMPLE_LIST_H 39afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 4063e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca#ifdef __cplusplus 4163e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonsecaextern "C" { 4263e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca#endif 4363e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca 44f5a22721c5731c7a4c20f86d9925d9e58324c7a5Ian Romanickstruct simple_node { 45f5a22721c5731c7a4c20f86d9925d9e58324c7a5Ian Romanick struct simple_node *next; 46f5a22721c5731c7a4c20f86d9925d9e58324c7a5Ian Romanick struct simple_node *prev; 47f5a22721c5731c7a4c20f86d9925d9e58324c7a5Ian Romanick}; 48f5a22721c5731c7a4c20f86d9925d9e58324c7a5Ian Romanick 496dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 506dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Remove an element from list. 516dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 526dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element to remove. 536dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 54afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define remove_from_list(elem) \ 55afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgdo { \ 56afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (elem)->next->prev = (elem)->prev; \ 57afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (elem)->prev->next = (elem)->next; \ 58afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} while (0) 59afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 606dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 616dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Insert an element to the list head. 626dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 636dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 646dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element to insert. 656dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 66afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define insert_at_head(list, elem) \ 67afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgdo { \ 68afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (elem)->prev = list; \ 69afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (elem)->next = (list)->next; \ 70afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (list)->next->prev = elem; \ 71afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (list)->next = elem; \ 72afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} while(0) 73afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 746dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 756dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Insert an element to the list tail. 766dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 776dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 786dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element to insert. 796dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 80afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define insert_at_tail(list, elem) \ 81afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgdo { \ 82afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (elem)->next = list; \ 83afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (elem)->prev = (list)->prev; \ 84afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (list)->prev->next = elem; \ 85afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (list)->prev = elem; \ 86afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} while(0) 87afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 886dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 896dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Move an element to the list head. 906dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 916dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 926dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element to move. 936dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 94afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define move_to_head(list, elem) \ 95afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgdo { \ 96afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg remove_from_list(elem); \ 97afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg insert_at_head(list, elem); \ 98afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} while (0) 99afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 1006dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1016dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Move an element to the list tail. 1026dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1036dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 1046dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element to move. 1056dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 106afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define move_to_tail(list, elem) \ 107afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgdo { \ 108afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg remove_from_list(elem); \ 109afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg insert_at_tail(list, elem); \ 110afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} while (0) 111afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 1126dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1136dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Make a empty list empty. 1146dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1156dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param sentinal list (sentinal element). 1166dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 117afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define make_empty_list(sentinal) \ 118afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtgdo { \ 119afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (sentinal)->next = sentinal; \ 120afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg (sentinal)->prev = sentinal; \ 121afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg} while (0) 122afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 1236dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1246dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Get list first element. 1256dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1266dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 1276dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1286dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return pointer to first element. 1296dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 130afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define first_elem(list) ((list)->next) 1316dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell 1326dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1336dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Get list last element. 1346dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1356dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 1366dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1376dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return pointer to last element. 1386dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 139afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define last_elem(list) ((list)->prev) 1406dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell 1416dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1426dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Get next element. 1436dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1446dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element. 1456dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1466dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return pointer to next element. 1476dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 148afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define next_elem(elem) ((elem)->next) 1496dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell 1506dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1516dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Get previous element. 1526dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1536dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element. 1546dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1556dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return pointer to previous element. 1566dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 157afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define prev_elem(elem) ((elem)->prev) 1586dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell 1596dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1606dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Test whether element is at end of the list. 1616dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1626dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 1636dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param elem element. 1646dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1656dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return non-zero if element is at end of list, or zero otherwise. 1666dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 167afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define at_end(list, elem) ((elem) == (list)) 1686dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell 1696dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1706dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Test if a list is empty. 1716dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1726dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 1736dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1746dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \return non-zero if list empty, or zero otherwise. 1756dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 176afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define is_empty_list(list) ((list)->next == (list)) 177afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 1786dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1796dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Walk through the elements of a list. 1806dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1816dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param ptr pointer to the current element. 1826dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 1836dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1846dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \note It should be followed by a { } block or a single statement, as in a \c 1856dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * for loop. 1866dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell */ 187afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define foreach(ptr, list) \ 188afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg for( ptr=(list)->next ; ptr!=list ; ptr=(ptr)->next ) 189afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 1906dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell/** 1916dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Walk through the elements of a list. 1926dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1936dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * Same as #foreach but lets you unlink the current value during a list 1946dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * traversal. Useful for freeing a list, element by element. 1956dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 1966dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param ptr pointer to the current element. 1976dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param t temporary pointer. 1986dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \param list list. 1996dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * 2006dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * \note It should be followed by a { } block or a single statement, as in a \c 2016dc85575000127630489b407c50a4b3ea87c9acbKeith Whitwell * for loop. 202afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg */ 203afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#define foreach_s(ptr, t, list) \ 204afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next) 205afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg 20663e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca#ifdef __cplusplus 20763e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca} 20863e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca#endif 20963e7a4c6e5bf51d8090046ebc5adcb4207448565José Fonseca 210afb833d4e89c312460a4ab9ed6a7a8ca4ebbfe1cjtg#endif 211