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