usr.bin/make/list.h

   1 /*
   2  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
   3  * Copyright (c) 1988, 1989 by Adam de Boor
   4  * Copyright (c) 1989 by Berkeley Softworks
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to Berkeley by
   8  * Adam de Boor.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  * 3. All advertising materials mentioning features or use of this software
  19  *    must display the following acknowledgement:
  20  *      This product includes software developed by the University of
  21  *      California, Berkeley and its contributors.
  22  * 4. Neither the name of the University nor the names of its contributors
  23  *    may be used to endorse or promote products derived from this software
  24  *    without specific prior written permission.
  25  *
  26  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  27  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  28  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  29  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  30  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  31  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  32  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  33  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  35  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  36  * SUCH DAMAGE.
  37  *
  38  *      from: @(#)list.h        8.1 (Berkeley) 6/6/93
  39  * $FreeBSD: src/usr.bin/make/list.h,v 1.8 1999/08/28 01:03:32 peter Exp $
  40  */
  41
  42 /*
  43  * list.h --
  44  *
  45  * Structures, macros, and routines exported by the List module.
  46  */
  47
  48 #ifndef _LIST
  49 #define _LIST
  50
  51 #ifndef _SPRITE
  52 #include "sprite.h"
  53 #endif _SPRITE
  54
  55 /*
  56  * This module defines the list abstraction, which enables one to link
  57  * together arbitrary data structures.  Lists are doubly-linked and
  58  * circular.  A list contains a header followed by its real members, if
  59  * any.  (An empty list therefore consists of a single element, the
  60  * header,  whose nextPtr and prevPtr fields point to itself).  To refer
  61  * to a list as a whole, the user keeps a pointer to the header; that
  62  * header is initialized by a call to List_Init(), which creates an empty
  63  * list given a pointer to a List_Links structure (described below).
  64  *
  65  * The links are contained in a two-element structure called List_Links.
  66  * A list joins List_Links records (that is, each List_Links structure
  67  * points to other List_Links structures), but if the List_Links is the
  68  * first field within a larger structure, then the larger structures are
  69  * effectively linked together as follows:
  70  *
  71  *            header
  72  *        (List_Links)             first elt.               second elt.
  73  *      -----------------       -----------------       -----------------
  74  * ..-> |    nextPtr    | ----> |  List_Links   | ----> |  List_Links   |----..
  75  *      | - - - - - - - |       |               |       |               |
  76  * ..-- |    prevPtr    | <---- |               | <---- |               |<---..
  77  *      -----------------       - ---  ---  --- -       - ---  ---  --- -
  78  *                              |    rest of    |       |    rest of    |
  79  *                              |   structure   |       |   structure   |
  80  *                              |               |       |               |
  81  *                              |      ...      |       |      ...      |
  82  *                              -----------------       -----------------
  83  *
  84  * It is possible to link structures through List_Links fields that are
  85  * not at the beginning of the larger structure, but it is then necessary
  86  * to perform pointer arithmetic to find the beginning of the larger
  87  * structure, given a pointer to some point within it.
  88  *
  89  * A typical structure might be something like:
  90  *
  91  *      typedef struct {
  92  *                  List_Links links;
  93  *                  char ch;
  94  *                  integer flags;
  95  *      } EditChar;
  96  *
  97  * Before an element is inserted in a list for the first time, it must
  98  * be initialized by calling the macro List_InitElement().
  99  */
 100 \f
 101
 102 /*
 103  * data structure for lists
 104  */
 105
 106 typedef struct List_Links {
 107     struct List_Links *prevPtr;
 108     struct List_Links *nextPtr;
 109 } List_Links;
 110
 111 /*
 112  * procedures
 113  */
 114
 115 void    List_Init();    /* initialize a header to a list */
 116 void    List_Insert();  /* insert an element into a list */
 117 void    List_Remove();  /* remove an element from a list */
 118 void    List_Move();    /* move an element elsewhere in a list */
 119 \f
 120 /*
 121  * ----------------------------------------------------------------------------
 122  *
 123  * List_InitElement --
 124  *
 125  *      Initialize a list element.  Must be called before an element is first
 126  *      inserted into a list.
 127  *
 128  * ----------------------------------------------------------------------------
 129  */
 130 #define List_InitElement(elementPtr) \
 131     (elementPtr)->prevPtr = (List_Links *) NIL; \
 132     (elementPtr)->nextPtr = (List_Links *) NIL;
 133
 134 /*
 135  * Macros for stepping through or selecting parts of lists
 136  */
 137
 138 /*
 139  * ----------------------------------------------------------------------------
 140  *
 141  * LIST_FORALL --
 142  *
 143  *      Macro to loop through a list and perform an operation on each member.
 144  *
 145  *      Usage: LIST_FORALL(headerPtr, itemPtr) {
 146  *                 / *
 147  *                   * operation on itemPtr, which points to successive members
 148  *                   * of the list
 149  *                   *
 150  *                   * It may be appropriate to first assign
 151  *                   *          foobarPtr = (Foobar *) itemPtr;
 152  *                   * to refer to the entire Foobar structure.
 153  *                   * /
 154  *             }
 155  *
 156  *      Note: itemPtr must be a List_Links pointer variable, and headerPtr
 157  *      must evaluate to a pointer to a List_Links structure.
 158  *
 159  * ----------------------------------------------------------------------------
 160  */
 161
 162 #define LIST_FORALL(headerPtr, itemPtr) \
 163         for (itemPtr = List_First(headerPtr); \
 164              !List_IsAtEnd((headerPtr),itemPtr); \
 165              itemPtr = List_Next(itemPtr))
 166
 167 /*
 168  * ----------------------------------------------------------------------------
 169  *
 170  * List_IsEmpty --
 171  *
 172  *      Macro: Boolean value, TRUE if the given list does not contain any
 173  *      members.
 174  *
 175  *      Usage: if (List_IsEmpty(headerPtr)) ...
 176  *
 177  * ----------------------------------------------------------------------------
 178  */
 179
 180 #define List_IsEmpty(headerPtr) \
 181         ((headerPtr) == (headerPtr)->nextPtr)
 182
 183 /*
 184  * ----------------------------------------------------------------------------
 185  *
 186  * List_IsAtEnd --
 187  *
 188  *      Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
 189  *      (i.e., itemPtr is the header of the list).
 190  *
 191  *      Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
 192  *
 193  * ----------------------------------------------------------------------------
 194  */
 195
 196
 197 #define List_IsAtEnd(headerPtr, itemPtr) \
 198         ((itemPtr) == (headerPtr))
 199
 200 \f
 201 /*
 202  * ----------------------------------------------------------------------------
 203  *
 204  * List_First --
 205  *
 206  *      Macro to return the first member in a list, which is the header if
 207  *      the list is empty.
 208  *
 209  *      Usage: firstPtr = List_First(headerPtr);
 210  *
 211  * ----------------------------------------------------------------------------
 212  */
 213
 214 #define List_First(headerPtr) ((headerPtr)->nextPtr)
 215
 216 /*
 217  * ----------------------------------------------------------------------------
 218  *
 219  * List_Last --
 220  *
 221  *      Macro to return the last member in a list, which is the header if
 222  *      the list is empty.
 223  *
 224  *      Usage: lastPtr = List_Last(headerPtr);
 225  *
 226  * ----------------------------------------------------------------------------
 227  */
 228
 229 #define List_Last(headerPtr) ((headerPtr)->prevPtr)
 230
 231 /*
 232  * ----------------------------------------------------------------------------
 233  *
 234  * List_Prev --
 235  *
 236  *      Macro to return the member preceding the given member in its list.
 237  *      If the given list member is the first element in the list, List_Prev
 238  *      returns the list header.
 239  *
 240  *      Usage: prevPtr = List_Prev(itemPtr);
 241  *
 242  * ----------------------------------------------------------------------------
 243  */
 244
 245 #define List_Prev(itemPtr) ((itemPtr)->prevPtr)
 246
 247 /*
 248  * ----------------------------------------------------------------------------
 249  *
 250  * List_Next --
 251  *
 252  *      Macro to return the member following the given member in its list.
 253  *      If the given list member is the last element in the list, List_Next
 254  *      returns the list header.
 255  *
 256  *      Usage: nextPtr = List_Next(itemPtr);
 257  *
 258  * ----------------------------------------------------------------------------
 259  */
 260
 261 #define List_Next(itemPtr) ((itemPtr)->nextPtr)
 262
 263 \f
 264 /*
 265  * ----------------------------------------------------------------------------
 266  *      The List_Insert procedure takes two arguments.  The first argument
 267  *      is a pointer to the structure to be inserted into a list, and
 268  *      the second argument is a pointer to the list member after which
 269  *      the new element is to be inserted.  Macros are used to determine
 270  *      which existing member will precede the new one.
 271  *
 272  *      The List_Move procedure takes a destination argument with the same
 273  *      semantics as List_Insert.
 274  *
 275  *      The following macros define where to insert the new element
 276  *      in the list:
 277  *
 278  *      LIST_AFTER(itemPtr)     --      insert after itemPtr
 279  *      LIST_BEFORE(itemPtr)    --      insert before itemPtr
 280  *      LIST_ATFRONT(headerPtr) --      insert at front of list
 281  *      LIST_ATREAR(headerPtr)  --      insert at end of list
 282  *
 283  *      For example,
 284  *
 285  *              List_Insert(itemPtr, LIST_AFTER(otherPtr));
 286  *
 287  *      will insert itemPtr following otherPtr in the list containing otherPtr.
 288  * ----------------------------------------------------------------------------
 289  */
 290
 291 #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)
 292
 293 #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)
 294
 295 #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)
 296
 297 #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)
 298
 299 #endif /* _LIST */