Return to list.h CVS log

Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / make

Annotation of 43BSDReno/usr.bin/make/list.h, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.