Annotation of src/usr.bin/make/list.h, Revision 1.1
1.1 ! deraadt 1: /* $NetBSD: list.h,v 1.4 1995/06/14 15:19:28 christos Exp $ */
! 2:
! 3: /*
! 4: * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
! 5: * Copyright (c) 1988, 1989 by Adam de Boor
! 6: * Copyright (c) 1989 by Berkeley Softworks
! 7: * All rights reserved.
! 8: *
! 9: * This code is derived from software contributed to Berkeley by
! 10: * Adam de Boor.
! 11: *
! 12: * Redistribution and use in source and binary forms, with or without
! 13: * modification, are permitted provided that the following conditions
! 14: * are met:
! 15: * 1. Redistributions of source code must retain the above copyright
! 16: * notice, this list of conditions and the following disclaimer.
! 17: * 2. Redistributions in binary form must reproduce the above copyright
! 18: * notice, this list of conditions and the following disclaimer in the
! 19: * documentation and/or other materials provided with the distribution.
! 20: * 3. All advertising materials mentioning features or use of this software
! 21: * must display the following acknowledgement:
! 22: * This product includes software developed by the University of
! 23: * California, Berkeley and its contributors.
! 24: * 4. Neither the name of the University nor the names of its contributors
! 25: * may be used to endorse or promote products derived from this software
! 26: * without specific prior written permission.
! 27: *
! 28: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
! 29: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
! 30: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
! 31: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
! 32: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
! 33: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
! 34: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
! 35: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
! 36: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
! 37: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
! 38: * SUCH DAMAGE.
! 39: *
! 40: * from: @(#)list.h 5.3 (Berkeley) 6/1/90
! 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:
! 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:
! 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:
! 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:
! 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 */
![[BACK]](/icons/back.gif){kind=icon}
Return to list.h CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / src / usr.bin / make