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