home *** CD-ROM | disk | FTP | other *** search
/ Fresh Fish 4 / FreshFish_May-June1994.bin / bsd / src / make / make-amiga / list.h < prev    next >
C/C++ Source or Header  |  1993-09-23  |  10KB  |  299 lines
  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.  *    @(#)list.h    5.3 (Berkeley) 6/1/90
  39.  */
  40.  
  41. /*
  42.  * list.h --
  43.  *
  44.  * Structures, macros, and routines exported by the List module.
  45.  */
  46.  
  47. #ifndef _LIST
  48. #define _LIST
  49.  
  50. #ifndef _SPRITE
  51. #include "sprite.h"
  52. #endif _SPRITE
  53.  
  54. /*
  55.  * This module defines the list abstraction, which enables one to link
  56.  * together arbitrary data structures.  Lists are doubly-linked and
  57.  * circular.  A list contains a header followed by its real members, if
  58.  * any.  (An empty list therefore consists of a single element, the
  59.  * header,  whose nextPtr and prevPtr fields point to itself).  To refer
  60.  * to a list as a whole, the user keeps a pointer to the header; that
  61.  * header is initialized by a call to List_Init(), which creates an empty
  62.  * list given a pointer to a List_Links structure (described below).
  63.  * 
  64.  * The links are contained in a two-element structure called List_Links.
  65.  * A list joins List_Links records (that is, each List_Links structure
  66.  * points to other List_Links structures), but if the List_Links is the
  67.  * first field within a larger structure, then the larger structures are
  68.  * effectively linked together as follows:
  69.  * 
  70.  *          header
  71.  *      (List_Links)           first elt.            second elt.
  72.  *    -----------------    -----------------    ----------------- 
  73.  * ..->    |    nextPtr    | ---->    |  List_Links    | ---->    |  List_Links    |----..
  74.  *    | - - - - - - -    |    |        |    |        | 
  75.  * ..--    |    prevPtr    | <----    |        | <----    |        |<---..
  76.  *    -----------------    - ---  ---  ---    -    - ---  ---  ---    -
  77.  *                |    rest of    |    |    rest of    | 
  78.  *                |   structure    |    |   structure    | 
  79.  *                |        |    |        |
  80.  *                |      ...    |    |      ...    | 
  81.  *                -----------------    ----------------- 
  82.  * 
  83.  * It is possible to link structures through List_Links fields that are
  84.  * not at the beginning of the larger structure, but it is then necessary
  85.  * to perform pointer arithmetic to find the beginning of the larger
  86.  * structure, given a pointer to some point within it.
  87.  * 
  88.  * A typical structure might be something like:
  89.  * 
  90.  *      typedef struct {
  91.  *                  List_Links links;
  92.  *                  char ch;
  93.  *                  integer flags;
  94.  *      } EditChar;
  95.  *  
  96.  * Before an element is inserted in a list for the first time, it must
  97.  * be initialized by calling the macro List_InitElement().
  98.  */
  99.  
  100.  
  101. /*
  102.  * data structure for lists
  103.  */
  104.  
  105. typedef struct List_Links {
  106.     struct List_Links *prevPtr;
  107.     struct List_Links *nextPtr;
  108. } List_Links;
  109.  
  110. /*
  111.  * procedures
  112.  */
  113.  
  114. void    List_Init();    /* initialize a header to a list */
  115. void    List_Insert();  /* insert an element into a list */
  116. void     List_Remove();  /* remove an element from a list */
  117. void     List_Move();    /* move an element elsewhere in a list */
  118.  
  119. /*
  120.  * ----------------------------------------------------------------------------
  121.  *
  122.  * List_InitElement --
  123.  *
  124.  *      Initialize a list element.  Must be called before an element is first
  125.  *    inserted into a list.
  126.  *
  127.  * ----------------------------------------------------------------------------
  128.  */
  129. #define List_InitElement(elementPtr) \
  130.     (elementPtr)->prevPtr = (List_Links *) NIL; \
  131.     (elementPtr)->nextPtr = (List_Links *) NIL;
  132.     
  133. /*
  134.  * Macros for stepping through or selecting parts of lists
  135.  */
  136.  
  137. /*
  138.  * ----------------------------------------------------------------------------
  139.  *
  140.  * LIST_FORALL --
  141.  *
  142.  *      Macro to loop through a list and perform an operation on each member.
  143.  *
  144.  *      Usage: LIST_FORALL(headerPtr, itemPtr) {
  145.  *                 / * 
  146.  *                   * operation on itemPtr, which points to successive members
  147.  *                   * of the list
  148.  *                   * 
  149.  *                   * It may be appropriate to first assign
  150.  *                   *          foobarPtr = (Foobar *) itemPtr;
  151.  *                   * to refer to the entire Foobar structure.
  152.  *                   * /
  153.  *             }
  154.  *
  155.  *      Note: itemPtr must be a List_Links pointer variable, and headerPtr
  156.  *      must evaluate to a pointer to a List_Links structure.
  157.  *
  158.  * ----------------------------------------------------------------------------
  159.  */
  160.  
  161. #define LIST_FORALL(headerPtr, itemPtr) \
  162.         for (itemPtr = List_First(headerPtr); \
  163.              !List_IsAtEnd((headerPtr),itemPtr); \
  164.              itemPtr = List_Next(itemPtr))
  165.  
  166. /*
  167.  * ----------------------------------------------------------------------------
  168.  *
  169.  * List_IsEmpty --
  170.  *
  171.  *      Macro: Boolean value, TRUE if the given list does not contain any
  172.  *      members.
  173.  *
  174.  *      Usage: if (List_IsEmpty(headerPtr)) ...
  175.  *
  176.  * ----------------------------------------------------------------------------
  177.  */
  178.  
  179. #define List_IsEmpty(headerPtr) \
  180.         ((headerPtr) == (headerPtr)->nextPtr)
  181.  
  182. /*
  183.  * ----------------------------------------------------------------------------
  184.  *
  185.  * List_IsAtEnd --
  186.  *
  187.  *      Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
  188.  *      (i.e., itemPtr is the header of the list).
  189.  *
  190.  *      Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
  191.  *
  192.  * ----------------------------------------------------------------------------
  193.  */
  194.  
  195.  
  196. #define List_IsAtEnd(headerPtr, itemPtr) \
  197.         ((itemPtr) == (headerPtr))
  198.  
  199.  
  200. /*
  201.  * ----------------------------------------------------------------------------
  202.  *
  203.  * List_First --
  204.  *
  205.  *      Macro to return the first member in a list, which is the header if
  206.  *      the list is empty.
  207.  *
  208.  *      Usage: firstPtr = List_First(headerPtr);
  209.  *
  210.  * ----------------------------------------------------------------------------
  211.  */
  212.  
  213. #define List_First(headerPtr) ((headerPtr)->nextPtr)
  214.  
  215. /*
  216.  * ----------------------------------------------------------------------------
  217.  *
  218.  * List_Last --
  219.  *
  220.  *      Macro to return the last member in a list, which is the header if
  221.  *      the list is empty.
  222.  *
  223.  *      Usage: lastPtr = List_Last(headerPtr);
  224.  *
  225.  * ----------------------------------------------------------------------------
  226.  */
  227.  
  228. #define List_Last(headerPtr) ((headerPtr)->prevPtr)
  229.  
  230. /*
  231.  * ----------------------------------------------------------------------------
  232.  *
  233.  * List_Prev --
  234.  *
  235.  *      Macro to return the member preceding the given member in its list.
  236.  *      If the given list member is the first element in the list, List_Prev
  237.  *      returns the list header.
  238.  *
  239.  *