usr.bin/make/lst.h

   1 /*      $NetBSD: lst.h,v 1.18 2009/01/23 21:58:27 dsl Exp $     */
   2
   3 /*
   4  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
   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. Neither the name of the University nor the names of its contributors
  19  *    may be used to endorse or promote products derived from this software
  20  *    without specific prior written permission.
  21  *
  22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  32  * SUCH DAMAGE.
  33  *
  34  *      from: @(#)lst.h 8.1 (Berkeley) 6/6/93
  35  */
  36
  37 /*
  38  * Copyright (c) 1988, 1989 by Adam de Boor
  39  * Copyright (c) 1989 by Berkeley Softworks
  40  * All rights reserved.
  41  *
  42  * This code is derived from software contributed to Berkeley by
  43  * Adam de Boor.
  44  *
  45  * Redistribution and use in source and binary forms, with or without
  46  * modification, are permitted provided that the following conditions
  47  * are met:
  48  * 1. Redistributions of source code must retain the above copyright
  49  *    notice, this list of conditions and the following disclaimer.
  50  * 2. Redistributions in binary form must reproduce the above copyright
  51  *    notice, this list of conditions and the following disclaimer in the
  52  *    documentation and/or other materials provided with the distribution.
  53  * 3. All advertising materials mentioning features or use of this software
  54  *    must display the following acknowledgement:
  55  *      This product includes software developed by the University of
  56  *      California, Berkeley and its contributors.
  57  * 4. Neither the name of the University nor the names of its contributors
  58  *    may be used to endorse or promote products derived from this software
  59  *    without specific prior written permission.
  60  *
  61  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  62  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  63  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  64  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  65  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  66  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  67  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  68  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  69  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  70  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  71  * SUCH DAMAGE.
  72  *
  73  *      from: @(#)lst.h 8.1 (Berkeley) 6/6/93
  74  */
  75
  76 /*-
  77  * lst.h --
  78  *      Header for using the list library
  79  */
  80 #ifndef _LST_H_
  81 #define _LST_H_
  82
  83 #include        <sys/param.h>
  84 #include        <stdlib.h>
  85
  86 #include        "sprite.h"
  87
  88 /*
  89  * basic typedef. This is what the Lst_ functions handle
  90  */
  91
  92 typedef struct List     *Lst;
  93 typedef struct ListNode *LstNode;
  94
  95 typedef void            *DuplicateProc(void *);
  96 typedef void            FreeProc(void *);
  97
  98 #define LST_CONCNEW     0   /* create new LstNode's when using Lst_Concat */
  99 #define LST_CONCLINK    1   /* relink LstNode's when using Lst_Concat */
 100
 101 /*
 102  * Creation/destruction functions
 103  */
 104 /* Create a new list */
 105 Lst             Lst_Init(Boolean);
 106 /* Duplicate an existing list */
 107 Lst             Lst_Duplicate(Lst, DuplicateProc *);
 108 /* Destroy an old one */
 109 void            Lst_Destroy(Lst, FreeProc *);
 110 /* True if list is empty */
 111 Boolean         Lst_IsEmpty(Lst);
 112
 113 /*
 114  * Functions to modify a list
 115  */
 116 /* Insert an element before another */
 117 ReturnStatus    Lst_InsertBefore(Lst, LstNode, void *);
 118 /* Insert an element after another */
 119 ReturnStatus    Lst_InsertAfter(Lst, LstNode, void *);
 120 /* Place an element at the front of a lst. */
 121 ReturnStatus    Lst_AtFront(Lst, void *);
 122 /* Place an element at the end of a lst. */
 123 ReturnStatus    Lst_AtEnd(Lst, void *);
 124 /* Remove an element */
 125 ReturnStatus    Lst_Remove(Lst, LstNode);
 126 /* Replace a node with a new value */
 127 ReturnStatus    Lst_Replace(LstNode, void *);
 128 /* Concatenate two lists */
 129 ReturnStatus    Lst_Concat(Lst, Lst, int);
 130
 131 /*
 132  * Node-specific functions
 133  */
 134 /* Return first element in list */
 135 LstNode         Lst_First(Lst);
 136 /* Return last element in list */
 137 LstNode         Lst_Last(Lst);
 138 /* Return successor to given element */
 139 LstNode         Lst_Succ(LstNode);
 140 /* Return predecessor to given element */
 141 LstNode         Lst_Prev(LstNode);
 142 /* Get datum from LstNode */
 143 void            *Lst_Datum(LstNode);
 144
 145 /*
 146  * Functions for entire lists
 147  */
 148 /* Find an element in a list */
 149 LstNode         Lst_Find(Lst, const void *, int (*)(const void *, const void *));
 150 /* Find an element starting from somewhere */
 151 LstNode         Lst_FindFrom(Lst, LstNode, const void *,
 152                              int (*cProc)(const void *, const void *));
 153 /*
 154  * See if the given datum is on the list. Returns the LstNode containing
 155  * the datum
 156  */
 157 LstNode         Lst_Member(Lst, void *);
 158 /* Apply a function to all elements of a lst */
 159 int             Lst_ForEach(Lst, int (*)(void *, void *), void *);
 160 /*
 161  * Apply a function to all elements of a lst starting from a certain point.
 162  * If the list is circular, the application will wrap around to the
 163  * beginning of the list again.
 164  */
 165 int             Lst_ForEachFrom(Lst, LstNode, int (*)(void *, void *),
 166                                 void *);
 167 /*
 168  * these functions are for dealing with a list as a table, of sorts.
 169  * An idea of the "current element" is kept and used by all the functions
 170  * between Lst_Open() and Lst_Close().
 171  */
 172 /* Open the list */
 173 ReturnStatus    Lst_Open(Lst);
 174 /* Next element please */
 175 LstNode         Lst_Next(Lst);
 176 /* Done yet? */
 177 Boolean         Lst_IsAtEnd(Lst);
 178 /* Finish table access */
 179 void            Lst_Close(Lst);
 180
 181 /*
 182  * for using the list as a queue
 183  */
 184 /* Place an element at tail of queue */
 185 ReturnStatus    Lst_EnQueue(Lst, void *);
 186 /* Remove an element from head of queue */
 187 void            *Lst_DeQueue(Lst);
 188
 189 #endif /* _LST_H_ */