13a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 23a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \file simple_list.h 33a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Simple macros for type-safe, intrusive lists. 43a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 53a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Intended to work with a list sentinal which is created as an empty 63a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * list. Insert & delete are O(1). 73a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 83a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \author 93a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * (C) 1997, Keith Whitwell 103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/* 133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Mesa 3-D graphics library 143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Version: 3.5 153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Copyright (C) 1999-2001 Brian Paul All Rights Reserved. 173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * copy of this software and associated documentation files (the "Software"), 203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * to deal in the Software without restriction, including without limitation 213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Software is furnished to do so, subject to the following conditions: 243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * The above copyright notice and this permission notice shall be included 263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * in all copies or substantial portions of the Software. 273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#ifndef _U_SIMPLE_LIST_H_ 383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define _U_SIMPLE_LIST_H_ 393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Remove an element from list. 423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element to remove. 443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define remove_from_list(elem) \ 463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgdo { \ 473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (elem)->next->prev = (elem)->prev; \ 483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (elem)->prev->next = (elem)->next; \ 49760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org (elem)->next = elem; \ 50760fd893ba809a7a5daa25c2749ff502f7186e83kbr@chromium.org (elem)->prev = elem; \ 513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} while (0) 523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Insert an element to the list head. 553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element to insert. 583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define insert_at_head(list, elem) \ 603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgdo { \ 613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (elem)->prev = list; \ 623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (elem)->next = (list)->next; \ 633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (list)->next->prev = elem; \ 643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (list)->next = elem; \ 653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} while(0) 663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Insert an element to the list tail. 693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element to insert. 723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define insert_at_tail(list, elem) \ 743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgdo { \ 753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (elem)->next = list; \ 763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (elem)->prev = (list)->prev; \ 773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (list)->prev->next = elem; \ 783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (list)->prev = elem; \ 793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} while(0) 803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Move an element to the list head. 833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element to move. 863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define move_to_head(list, elem) \ 883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgdo { \ 893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org remove_from_list(elem); \ 903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org insert_at_head(list, elem); \ 913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} while (0) 923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Move an element to the list tail. 953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element to move. 983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define move_to_tail(list, elem) \ 1003a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgdo { \ 1013a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org remove_from_list(elem); \ 1023a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org insert_at_tail(list, elem); \ 1033a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} while (0) 1043a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1053a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1063a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Make a empty list empty. 1073a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1083a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param sentinal list (sentinal element). 1093a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1103a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define make_empty_list(sentinal) \ 1113a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.orgdo { \ 1123a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (sentinal)->next = sentinal; \ 1133a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org (sentinal)->prev = sentinal; \ 1143a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org} while (0) 1153a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1163a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1173a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Get list first element. 1183a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1193a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 1203a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1213a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \return pointer to first element. 1223a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1233a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define first_elem(list) ((list)->next) 1243a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1253a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1263a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Get list last element. 1273a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1283a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 1293a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1303a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \return pointer to last element. 1313a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1323a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define last_elem(list) ((list)->prev) 1333a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1343a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1353a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Get next element. 1363a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1373a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element. 1383a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1393a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \return pointer to next element. 1403a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1413a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define next_elem(elem) ((elem)->next) 1423a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1433a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1443a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Get previous element. 1453a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1463a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element. 1473a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1483a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \return pointer to previous element. 1493a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1503a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define prev_elem(elem) ((elem)->prev) 1513a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1523a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1533a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Test whether element is at end of the list. 1543a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1553a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 1563a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param elem element. 1573a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1583a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \return non-zero if element is at end of list, or zero otherwise. 1593a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1603a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define at_end(list, elem) ((elem) == (list)) 1613a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1623a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1633a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Test if a list is empty. 1643a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1653a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 1663a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1673a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \return non-zero if list empty, or zero otherwise. 1683a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1693a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define is_empty_list(list) ((list)->next == (list)) 1703a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1713a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1723a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Walk through the elements of a list. 1733a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1743a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param ptr pointer to the current element. 1753a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 1763a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1773a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \note It should be followed by a { } block or a single statement, as in a \c 1783a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * for loop. 1793a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1803a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define foreach(ptr, list) \ 1813a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for( ptr=(list)->next ; ptr!=list ; ptr=(ptr)->next ) 1823a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1833a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org/** 1843a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Walk through the elements of a list. 1853a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1863a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * Same as #foreach but lets you unlink the current value during a list 1873a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * traversal. Useful for freeing a list, element by element. 1883a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1893a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param ptr pointer to the current element. 1903a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param t temporary pointer. 1913a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \param list list. 1923a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * 1933a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * \note It should be followed by a { } block or a single statement, as in a \c 1943a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org * for loop. 1953a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org */ 1963a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#define foreach_s(ptr, t, list) \ 1973a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next) 1983a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org 1993a0db227ffe90888ad760c61a63226988c974e0apatrick@chromium.org#endif /* _U_SIMPLE_LIST_H_ */ 200