src/mesa/main/simple_list.h

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