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  * Consatinate a cyclic list to a list
 110  *
 111  * Appends the sequence of nodes starting with \c tail to the list \c head.
 112  * A "cyclic list" is a list that does not have a sentinal node.  This means
 113  * that the data pointed to by \c tail is an actual node, not a dataless
 114  * sentinal.  Note that if \c tail constist of a single node, this macro
 115  * behaves identically to \c insert_at_tail
 116  *
 117  * \param head Head of the list to be appended to.  This may or may not
 118  *             be a cyclic list.
 119  * \param tail Head of the cyclic list to be appended to \c head.
 120  * \param temp Temporary \c simple_list used by the macro
 121  *
 122  * \sa insert_at_tail
 123  */
 124 #define concat_list_and_cycle(head, tail, temp) \
 125 do {                                            \
 126    (head)->prev->next = (tail);                 \
 127    (tail)->prev->next = (head);                 \
 128    (temp) = (head)->prev;                       \
 129    (head)->prev = (tail)->prev;                 \
 130    (tail)->prev = (temp);                       \
 131 } while (0)
 132
 133 #define concat_list(head, next_list)            \
 134 do {                                            \
 135    (next_list)->next->prev = (head)->prev;      \
 136    (next_list)->prev->next = (head);            \
 137    (head)->prev->next = (next_list)->next;      \
 138    (head)->prev = (next_list)->prev;            \
 139 } while (0)
 140
 141 /**
 142  * Make a empty list empty.
 143  *
 144  * \param sentinal list (sentinal element).
 145  */
 146 #define make_empty_list(sentinal)               \
 147 do {                                            \
 148    (sentinal)->next = sentinal;                 \
 149    (sentinal)->prev = sentinal;                 \
 150 } while (0)
 151
 152 /**
 153  * Get list first element.
 154  *
 155  * \param list list.
 156  *
 157  * \return pointer to first element.
 158  */
 159 #define first_elem(list)       ((list)->next)
 160
 161 /**
 162  * Get list last element.
 163  *
 164  * \param list list.
 165  *
 166  * \return pointer to last element.
 167  */
 168 #define last_elem(list)        ((list)->prev)
 169
 170 /**
 171  * Get next element.
 172  *
 173  * \param elem element.
 174  *
 175  * \return pointer to next element.
 176  */
 177 #define next_elem(elem)        ((elem)->next)
 178
 179 /**
 180  * Get previous element.
 181  *
 182  * \param elem element.
 183  *
 184  * \return pointer to previous element.
 185  */
 186 #define prev_elem(elem)        ((elem)->prev)
 187
 188 /**
 189  * Test whether element is at end of the list.
 190  *
 191  * \param list list.
 192  * \param elem element.
 193  *
 194  * \return non-zero if element is at end of list, or zero otherwise.
 195  */
 196 #define at_end(list, elem)     ((elem) == (list))
 197
 198 /**
 199  * Test if a list is empty.
 200  *
 201  * \param list list.
 202  *
 203  * \return non-zero if list empty, or zero otherwise.
 204  */
 205 #define is_empty_list(list)    ((list)->next == (list))
 206
 207 /**
 208  * Walk through the elements of a list.
 209  *
 210  * \param ptr pointer to the current element.
 211  * \param list list.
 212  *
 213  * \note It should be followed by a { } block or a single statement, as in a \c
 214  * for loop.
 215  */
 216 #define foreach(ptr, list)     \
 217         for( ptr=(list)->next ;  ptr!=list ;  ptr=(ptr)->next )
 218
 219 /**
 220  * Walk through the elements of a list.
 221  *
 222  * Same as #foreach but lets you unlink the current value during a list
 223  * traversal.  Useful for freeing a list, element by element.
 224  *
 225  * \param ptr pointer to the current element.
 226  * \param t temporary pointer.
 227  * \param list list.
 228  *
 229  * \note It should be followed by a { } block or a single statement, as in a \c
 230  * for loop.
 231  */
 232 #define foreach_s(ptr, t, list)   \
 233         for(ptr=(list)->next,t=(ptr)->next; list != ptr; ptr=t, t=(t)->next)
 234
 235 #endif