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