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  * $DragonFly: src/usr.bin/make/Attic/list.h,v 1.2 2003/06/17 04:29:29 dillon Exp $
  41  */
  42
  43 /*
  44  * list.h --
  45  *
  46  * Structures, macros, and routines exported by the List module.
  47  */
  48
  49 #ifndef _LIST
  50 #define _LIST
  51
  52 #ifndef _SPRITE
  53 #include "sprite.h"
  54 #endif _SPRITE
  55
  56 /*
  57  * This module defines the list abstraction, which enables one to link
  58  * together arbitrary data structures.  Lists are doubly-linked and
  59  * circular.  A list contains a header followed by its real members, if
  60  * any.  (An empty list therefore consists of a single element, the
  61  * header,  whose nextPtr and prevPtr fields point to itself).  To refer
  62  * to a list as a whole, the user keeps a pointer to the header; that
  63  * header is initialized by a call to List_Init(), which creates an empty
  64  * list given a pointer to a List_Links structure (described below).
  65  *
  66  * The links are contained in a two-element structure called List_Links.
  67  * A list joins List_Links records (that is, each List_Links structure
  68  * points to other List_Links structures), but if the List_Links is the
  69  * first field within a larger structure, then the larger structures are
  70  * effectively linked together as follows:
  71  *
  72  *            header
  73  *        (List_Links)             first elt.               second elt.
  74  *      -----------------       -----------------       -----------------
  75  * ..-> |    nextPtr    | ----> |  List_Links   | ----> |  List_Links   |----..
  76  *      | - - - - - - - |       |               |       |               |
  77  * ..-- |    prevPtr    | <---- |               | <---- |               |<---..
  78  *      -----------------       - ---  ---  --- -       - ---  ---  --- -
  79  *                              |    rest of    |       |    rest of    |
  80  *                              |   structure   |       |   structure   |
  81  *                              |               |       |               |
  82  *                              |      ...      |       |      ...      |
  83  *                              -----------------       -----------------
  84  *
  85  * It is possible to link structures through List_Links fields that are
  86  * not at the beginning of the larger structure, but it is then necessary
  87  * to perform pointer arithmetic to find the beginning of the larger
  88  * structure, given a pointer to some point within it.
  89  *
  90  * A typical structure might be something like:
  91  *
  92  *      typedef struct {
  93  *                  List_Links links;
  94  *                  char ch;
  95  *                  integer flags;
  96  *      } EditChar;
  97  *
  98  * Before an element is inserted in a list for the first time, it must
  99  * be initialized by calling the macro List_InitElement().
 100  */
 101 \f
 102
 103 /*
 104  * data structure for lists
 105  */
 106
 107 typedef struct List_Links {
 108     struct List_Links *prevPtr;
 109     struct List_Links *nextPtr;
 110 } List_Links;
 111
 112 /*
 113  * procedures
 114  */
 115
 116 void    List_Init();    /* initialize a header to a list */
 117 void    List_Insert();  /* insert an element into a list */
 118 void    List_Remove();  /* remove an element from a list */
 119 void    List_Move();    /* move an element elsewhere in a list */
 120 \f
 121 /*
 122  * ----------------------------------------------------------------------------
 123  *
 124  * List_InitElement --
 125  *
 126  *      Initialize a list element.  Must be called before an element is first
 127  *      inserted into a list.
 128  *
 129  * ----------------------------------------------------------------------------
 130  */
 131 #define List_InitElement(elementPtr) \
 132     (elementPtr)->prevPtr = (List_Links *) NIL; \
 133     (elementPtr)->nextPtr = (List_Links *) NIL;
 134
 135 /*
 136  * Macros for stepping through or selecting parts of lists
 137  */
 138
 139 /*
 140  * ----------------------------------------------------------------------------
 141  *
 142  * LIST_FORALL --
 143  *
 144  *      Macro to loop through a list and perform an operation on each member.
 145  *
 146  *      Usage: LIST_FORALL(headerPtr, itemPtr) {
 147  *                 / *
 148  *                   * operation on itemPtr, which points to successive members
 149  *                   * of the list
 150  *                   *
 151  *                   * It may be appropriate to first assign
 152  *                   *          foobarPtr = (Foobar *) itemPtr;
 153  *                   * to refer to the entire Foobar structure.
 154  *                   * /
 155  *             }
 156  *
 157  *      Note: itemPtr must be a List_Links pointer variable, and headerPtr
 158  *      must evaluate to a pointer to a List_Links structure.
 159  *
 160  * ----------------------------------------------------------------------------
 161  */
 162
 163 #define LIST_FORALL(headerPtr, itemPtr) \
 164         for (itemPtr = List_First(headerPtr); \
 165              !List_IsAtEnd((headerPtr),itemPtr); \
 166              itemPtr = List_Next(itemPtr))
 167
 168 /*
 169  * ----------------------------------------------------------------------------
 170  *
 171  * List_IsEmpty --
 172  *
 173  *      Macro: Boolean value, TRUE if the given list does not contain any
 174  *      members.
 175  *
 176  *      Usage: if (List_IsEmpty(headerPtr)) ...
 177  *
 178  * ----------------------------------------------------------------------------
 179  */
 180
 181 #define List_IsEmpty(headerPtr) \
 182         ((headerPtr) == (headerPtr)->nextPtr)
 183
 184 /*
 185  * ----------------------------------------------------------------------------
 186  *
 187  * List_IsAtEnd --
 188  *
 189  *      Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
 190  *      (i.e., itemPtr is the header of the list).
 191  *
 192  *      Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
 193  *
 194  * ----------------------------------------------------------------------------
 195  */
 196
 197
 198 #define List_IsAtEnd(headerPtr, itemPtr) \
 199         ((itemPtr) == (headerPtr))
 200
 201 \f
 202 /*
 203  * ----------------------------------------------------------------------------
 204  *
 205  * List_First --
 206  *
 207  *      Macro to return the first member in a list, which is the header if
 208  *      the list is empty.
 209  *
 210  *      Usage: firstPtr = List_First(headerPtr);
 211  *
 212  * ----------------------------------------------------------------------------
 213  */
 214
 215 #define List_First(headerPtr) ((headerPtr)->nextPtr)
 216
 217 /*
 218  * ----------------------------------------------------------------------------
 219  *
 220  * List_Last --
 221  *
 222  *      Macro to return the last member in a list, which is the header if
 223  *      the list is empty.
 224  *
 225  *      Usage: lastPtr = List_Last(headerPtr);
 226  *
 227  * ----------------------------------------------------------------------------
 228  */
 229
 230 #define List_Last(headerPtr) ((headerPtr)->prevPtr)
 231
 232 /*
 233  * ----------------------------------------------------------------------------
 234  *
 235  * List_Prev --
 236  *
 237  *      Macro to return the member preceding the given member in its list.
 238  *      If the given list member is the first element in the list, List_Prev
 239  *      returns the list header.
 240  *
 241  *      Usage: prevPtr = List_Prev(itemPtr);
 242  *
 243  * ----------------------------------------------------------------------------
 244  */
 245
 246 #define List_Prev(itemPtr) ((itemPtr)->prevPtr)
 247
 248 /*
 249  * ----------------------------------------------------------------------------
 250  *
 251  * List_Next --
 252  *
 253  *      Macro to return the member following the given member in its list.
 254  *      If the given list member is the last element in the list, List_Next
 255  *      returns the list header.
 256  *
 257  *      Usage: nextPtr = List_Next(itemPtr);
 258  *
 259  * ----------------------------------------------------------------------------
 260  */
 261
 262 #define List_Next(itemPtr) ((itemPtr)->nextPtr)
 263
 264 \f
 265 /*
 266  * ----------------------------------------------------------------------------
 267  *      The List_Insert procedure takes two arguments.  The first argument
 268  *      is a pointer to the structure to be inserted into a list, and
 269  *      the second argument is a pointer to the list member after which
 270  *      the new element is to be inserted.  Macros are used to determine
 271  *      which existing member will precede the new one.
 272  *
 273  *      The List_Move procedure takes a destination argument with the same
 274  *      semantics as List_Insert.
 275  *
 276  *      The following macros define where to insert the new element
 277  *      in the list:
 278  *
 279  *      LIST_AFTER(itemPtr)     --      insert after itemPtr
 280  *      LIST_BEFORE(itemPtr)    --      insert before itemPtr
 281  *      LIST_ATFRONT(headerPtr) --      insert at front of list
 282  *      LIST_ATREAR(headerPtr)  --      insert at end of list
 283  *
 284  *      For example,
 285  *
 286  *              List_Insert(itemPtr, LIST_AFTER(otherPtr));
 287  *
 288  *      will insert itemPtr following otherPtr in the list containing otherPtr.
 289  * ----------------------------------------------------------------------------
 290  */
 291
 292 #define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)
 293
 294 #define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)
 295
 296 #define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)
 297
 298 #define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)
 299
 300 #endif /* _LIST */