src/gallium/auxiliary/util/u_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  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
  32  * OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
  33  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
  34  * OTHER DEALINGS IN THE SOFTWARE.
  35  */
  36
  37
  38 #ifndef _U_SIMPLE_LIST_H_
  39 #define _U_SIMPLE_LIST_H_
  40
  41 /**
  42  * Remove an element from list.
  43  *
  44  * \param elem element to remove.
  45  */
  46 #define remove_from_list(elem)                  \
  47 do {                                            \
  48    (elem)->next->prev = (elem)->prev;           \
  49    (elem)->prev->next = (elem)->next;           \
  50    (elem)->next = elem;                         \
  51    (elem)->prev = elem;                         \
  52 } while (0)
  53
  54 /**
  55  * Insert an element to the list head.
  56  *
  57  * \param list list.
  58  * \param elem element to insert.
  59  */
  60 #define insert_at_head(list, elem)              \
  61 do {                                            \
  62    (elem)->prev = list;                         \
  63    (elem)->next = (list)->next;                 \
  64    (list)->next->prev = elem;                   \
  65    (list)->next = elem;                         \
  66 } while(0)
  67
  68 /**
  69  * Insert an element to the list tail.
  70  *
  71  * \param list list.
  72  * \param elem element to insert.
  73  */
  74 #define insert_at_tail(list, elem)              \
  75 do {                                            \
  76    (elem)->next = list;                         \
  77    (elem)->prev = (list)->prev;                 \
  78    (list)->prev->next = elem;                   \
  79    (list)->prev = elem;                         \
  80 } while(0)
  81
  82 /**
  83  * Move an element to the list head.
  84  *
  85  * \param list list.
  86  * \param elem element to move.
  87  */
  88 #define move_to_head(list, elem)                \
  89 do {                                            \
  90    remove_from_list(elem);                      \
  91    insert_at_head(list, elem);                  \
  92 } while (0)
  93
  94 /**
  95  * Move an element to the list tail.
  96  *
  97  * \param list list.
  98  * \param elem element to move.
  99  */
 100 #define move_to_tail(list, elem)                \
 101 do {                                            \
 102    remove_from_list(elem);                      \
 103    insert_at_tail(list, elem);                  \
 104 } while (0)
 105
 106 /**
 107  * Make a empty list empty.
 108  *
 109  * \param sentinal list (sentinal element).
 110  */
 111 #define make_empty_list(sentinal)               \
 112 do {                                            \
 113    (sentinal)->next = sentinal;                 \
 114    (sentinal)->prev = sentinal;                 \
 115 } while (0)
 116
 117 /**
 118  * Get list first element.
 119  *
 120  * \param list list.
 121  *
 122  * \return pointer to first element.
 123  */
 124 #define first_elem(list)       ((list)->next)
 125
 126 /**
 127  * Get list last element.
 128  *
 129  * \param list list.
 130  *
 131  * \return pointer to last element.
 132  */
 133 #define last_elem(list)        ((list)->prev)
 134
 135 /**
 136  * Get next element.
 137  *
 138  * \param elem element.
 139  *
 140  * \return pointer to next element.
 141  */
 142 #define next_elem(elem)        ((elem)->next)
 143
 144 /**
 145  * Get previous element.
 146  *
 147  * \param elem element.
 148  *
 149  * \return pointer to previous element.
 150  */
 151 #define prev_elem(elem)        ((elem)->prev)
 152
 153 /**
 154  * Test whether element is at end of the list.
 155  *
 156  * \param list list.
 157  * \param elem element.
 158  *
 159  * \return non-zero if element is at end of list, or zero otherwise.
 160  */
 161 #define at_end(list, elem)     ((elem) == (list))
 162
 163 /**
 164  * Test if a list is empty.
 165  *
 166  * \param list list.
 167  *
 168  * \return non-zero if list empty, or zero otherwise.
 169  */
 170 #define is_empty_list(list)    ((list)->next == (list))
 171
 172 /**
 173  * Walk through the elements of a list.
 174  *
 175  * \param ptr pointer to the current element.
 176  * \param list list.
 177  *
 178  * \note It should be followed by a { } block or a single statement, as in a \c
 179  * for loop.
 180  */
 181 #define foreach(ptr, list)     \
 182         for( ptr=(list)->next ;  ptr!=list ;  ptr=(ptr)->next )
 183
 184 /**
 185  * Walk through the elements of a list.
 186  *
 187  * Same as #foreach but lets you unlink the current value during a list
 188  * traversal.  Useful for freeing a list, element by element.
 189  *
 190  * \param ptr pointer to the current element.
 191  * \param t temporary pointer.
 192  * \param list list.
 193  *
 194  * \note It should be followed by a { } block or a single statement, as in a \c
 195  * for loop.
 196  */
 197 #define foreach_s(ptr, t, list)   \
 198         for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next)
 199
 200 #endif /* _U_SIMPLE_LIST_H_ */