1f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 2f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \file simple_list.h 3f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Simple macros for type-safe, intrusive lists. 4f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 5f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Intended to work with a list sentinal which is created as an empty 6f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * list. Insert & delete are O(1). 7f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 8f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \author 9f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * (C) 1997, Keith Whitwell 10f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 11f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 12f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/* 13f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Mesa 3-D graphics library 14f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Version: 3.5 15f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 16f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Copyright (C) 1999-2001 Brian Paul All Rights Reserved. 17f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 18f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Permission is hereby granted, free of charge, to any person obtaining a 19f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * copy of this software and associated documentation files (the "Software"), 20f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * to deal in the Software without restriction, including without limitation 21f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * the rights to use, copy, modify, merge, publish, distribute, sublicense, 22f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * and/or sell copies of the Software, and to permit persons to whom the 23f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Software is furnished to do so, subject to the following conditions: 24f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 25f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * The above copyright notice and this permission notice shall be included 26f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * in all copies or substantial portions of the Software. 27f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 28f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS 29f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 30f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 31f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * BRIAN PAUL BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN 32f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 33f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 34f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 35f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 36f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 37f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifndef _SIMPLE_LIST_H 38f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define _SIMPLE_LIST_H 39f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 40f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifdef __cplusplus 41f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgextern "C" { 42f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 43f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 44f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgstruct simple_node { 45f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct simple_node *next; 46f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org struct simple_node *prev; 47f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org}; 48f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 49f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 50f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Remove an element from list. 51f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 52f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element to remove. 53f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 54f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define remove_from_list(elem) \ 55f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgdo { \ 56f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (elem)->next->prev = (elem)->prev; \ 57f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (elem)->prev->next = (elem)->next; \ 58f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} while (0) 59f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 60f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 61f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Insert an element to the list head. 62f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 63f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 64f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element to insert. 65f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 66f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define insert_at_head(list, elem) \ 67f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgdo { \ 68f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (elem)->prev = list; \ 69f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (elem)->next = (list)->next; \ 70f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (list)->next->prev = elem; \ 71f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (list)->next = elem; \ 72f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} while(0) 73f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 74f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 75f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Insert an element to the list tail. 76f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 77f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 78f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element to insert. 79f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 80f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define insert_at_tail(list, elem) \ 81f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgdo { \ 82f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (elem)->next = list; \ 83f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (elem)->prev = (list)->prev; \ 84f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (list)->prev->next = elem; \ 85f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (list)->prev = elem; \ 86f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} while(0) 87f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 88f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 89f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Move an element to the list head. 90f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 91f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 92f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element to move. 93f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 94f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define move_to_head(list, elem) \ 95f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgdo { \ 96f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org remove_from_list(elem); \ 97f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insert_at_head(list, elem); \ 98f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} while (0) 99f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 100f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 101f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Move an element to the list tail. 102f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 103f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 104f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element to move. 105f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 106f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define move_to_tail(list, elem) \ 107f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgdo { \ 108f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org remove_from_list(elem); \ 109f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org insert_at_tail(list, elem); \ 110f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} while (0) 111f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 112f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 113f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Make a empty list empty. 114f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 115f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param sentinal list (sentinal element). 116f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 117f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define make_empty_list(sentinal) \ 118f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.orgdo { \ 119f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (sentinal)->next = sentinal; \ 120f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org (sentinal)->prev = sentinal; \ 121f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} while (0) 122f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 123f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 124f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Get list first element. 125f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 126f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 127f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 128f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return pointer to first element. 129f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 130f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define first_elem(list) ((list)->next) 131f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 132f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 133f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Get list last element. 134f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 135f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 136f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 137f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return pointer to last element. 138f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 139f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define last_elem(list) ((list)->prev) 140f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 141f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 142f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Get next element. 143f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 144f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element. 145f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 146f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return pointer to next element. 147f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 148f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define next_elem(elem) ((elem)->next) 149f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 150f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 151f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Get previous element. 152f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 153f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element. 154f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 155f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return pointer to previous element. 156f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 157f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define prev_elem(elem) ((elem)->prev) 158f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 159f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 160f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Test whether element is at end of the list. 161f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 162f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 163f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param elem element. 164f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 165f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return non-zero if element is at end of list, or zero otherwise. 166f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 167f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define at_end(list, elem) ((elem) == (list)) 168f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 169f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 170f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Test if a list is empty. 171f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 172f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 173f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 174f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \return non-zero if list empty, or zero otherwise. 175f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 176f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define is_empty_list(list) ((list)->next == (list)) 177f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 178f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 179f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Walk through the elements of a list. 180f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 181f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param ptr pointer to the current element. 182f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 183f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 184f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \note It should be followed by a { } block or a single statement, as in a \c 185f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * for loop. 186f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 187f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define foreach(ptr, list) \ 188f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for( ptr=(list)->next ; ptr!=list ; ptr=(ptr)->next ) 189f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 190f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org/** 191f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Walk through the elements of a list. 192f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 193f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * Same as #foreach but lets you unlink the current value during a list 194f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * traversal. Useful for freeing a list, element by element. 195f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 196f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param ptr pointer to the current element. 197f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param t temporary pointer. 198f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \param list list. 199f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * 200f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * \note It should be followed by a { } block or a single statement, as in a \c 201f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org * for loop. 202f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org */ 203f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#define foreach_s(ptr, t, list) \ 204f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next) 205f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 206f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#ifdef __cplusplus 207f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org} 208f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 209f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org 210f2ba7591b1407a7ee9209f842c50696914dc2dedkbr@chromium.org#endif 211