1 #ifndef _LST_H_
2 #define _LST_H_
3
4 /** $MirOS: src/usr.bin/make/lst.h,v 1.3 2007/06/21 14:17:07 tg Exp $ */
5 /* $OpenPackages$ */
6 /* $OpenBSD: lst.h,v 1.26 2007/01/04 17:55:35 espie Exp $ */
7 /* $NetBSD: lst.h,v 1.7 1996/11/06 17:59:12 christos Exp $ */
8
9 /*
10 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
11 * Copyright (c) 1988, 1989 by Adam de Boor
12 * Copyright (c) 1989 by Berkeley Softworks
13 * All rights reserved.
14 *
15 * This code is derived from software contributed to Berkeley by
16 * Adam de Boor.
17 *
18 * Redistribution and use in source and binary forms, with or without
19 * modification, are permitted provided that the following conditions
20 * are met:
21 * 1. Redistributions of source code must retain the above copyright
22 * notice, this list of conditions and the following disclaimer.
23 * 2. Redistributions in binary form must reproduce the above copyright
24 * notice, this list of conditions and the following disclaimer in the
25 * documentation and/or other materials provided with the distribution.
26 * 3. Neither the name of the University nor the names of its contributors
27 * may be used to endorse or promote products derived from this software
28 * without specific prior written permission.
29 *
30 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
31 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
32 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
34 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
35 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
36 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
37 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
38 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
39 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
40 * SUCH DAMAGE.
41 *
42 * from: @(#)lst.h 8.1 (Berkeley) 6/6/93
43 */
44
45 /*-
46 * lst.h --
47 * Header for using the list library
48 */
49
50 /* These data structures are PRIVATE !!!
51 * Here for efficiency, so that some functions can be recoded as inlines,
52 * and so that lst headers don't need dynamic allocation most of the time. */
53 struct ListNode_ {
54 struct ListNode_ *prevPtr; /* previous element in list */
55 struct ListNode_ *nextPtr; /* next in list */
56 void *datum; /* datum associated with this element */
57 };
58
59 #ifndef LIST_TYPE
60 #include "lst_t.h"
61 #endif
62
63 typedef void (*SimpleProc)(void *);
64 typedef int (*FindProc)(const void *, void *);
65 typedef int (*ForEachNodeWhileProc)(LstNode, void *);
66 typedef int (*FindProcConst)(const void *, const void *);
67 typedef void (*ForEachProc)(void *, void *);
68 typedef void *(*DuplicateProc)(void *);
69
70 /*
71 * NOFREE can be used as the freeProc to Lst_Destroy when the elements are
72 * not to be freed.
73 * NOCOPY performs similarly when given as the copyProc to Lst_Duplicate.
74 */
75 #define NOFREE ((SimpleProc) 0)
76 #define NOCOPY ((DuplicateProc) 0)
77
78 /*
79 * Creation/destruction functions
80 */
81 /* Create a new list */
82 #define Lst_Init(l) (l)->firstPtr = (l)->lastPtr = NULL
83 /* Static lists are already okay */
84 #define Static_Lst_Init(l)
85
86 /* Duplicate an existing list */
87 extern Lst Lst_Clone(Lst, Lst, DuplicateProc);
88 /* Destroy an old one */
89 extern void Lst_Destroy(LIST *, SimpleProc);
90 /* True if list is empty */
91 #define Lst_IsEmpty(l) ((l)->firstPtr == NULL)
92
93 /*
94 * Functions to modify a list
95 */
96 /* Insert an element before another */
97 extern void Lst_Insert(Lst, LstNode, void *);
98 extern void Lst_AtFront(Lst, void *);
99 /* Insert an element after another */
100 extern void Lst_Append(Lst, LstNode, void *);
101 extern void Lst_AtEnd(Lst, void *);
102 /* Remove an element */
103 extern void Lst_Remove(Lst, LstNode);
104 /* Replace a node with a new value */
105 extern void Lst_Replace(LstNode, void *);
106 /* Concatenate two lists, destructive. */
107 extern void Lst_ConcatDestroy(Lst, Lst);
108 /* Concatenate two lists, non-destructive. */
109 extern void Lst_Concat(Lst, Lst);
110
111 /*
112 * Node-specific functions
113 */
114 /* Return first element in list */
115 /* Return last element in list */
116 /* Return successor to given element */
117 extern LstNode Lst_Succ(LstNode);
118
119 /*
120 * Functions for entire lists
121 */
122 /* Find an element starting from somewhere */
123 extern LstNode Lst_FindFrom(LstNode, FindProc, void *);
124 /*
125 * See if the given datum is on the list. Returns the LstNode containing
126 * the datum
127 */
128 extern LstNode Lst_Member(Lst, void *);
129 /* Apply a function to elements of a lst starting from a certain point. */
130 extern void Lst_ForEachFrom(LstNode, ForEachProc, void *);
131 extern void Lst_Every(Lst, SimpleProc);
132
133 extern void Lst_ForEachNodeWhile(Lst, ForEachNodeWhileProc, void *);
134
135 extern bool Lst_AddNew(Lst, void *);
136 /*
137 * for using the list as a queue
138 */
139 /* Place an element at tail of queue */
140 #define Lst_EnQueue Lst_AtEnd
141 #define Lst_QueueNew Lst_AddNew
142
143 /*
144 * for using the list as a stack
145 */
146 #define Lst_Push Lst_AtFront
147 #define Lst_Pop Lst_DeQueue
148
149 /* Remove an element from head of queue */
150 extern void * Lst_DeQueue(Lst);
151
152 #define Lst_Datum(ln) ((ln)->datum)
153 #define Lst_First(l) ((l)->firstPtr)
154 #define Lst_Last(l) ((l)->lastPtr)
155 #define Lst_ForEach(l, proc, d) Lst_ForEachFrom(Lst_First(l), proc, d)
156 #define Lst_Find(l, cProc, d) Lst_FindFrom(Lst_First(l), cProc, d)
157 #define Lst_Adv(ln) ((ln)->nextPtr)
158 #define Lst_Rev(ln) ((ln)->prevPtr)
159
160
161 /* Inlines are preferable to macros here because of the type checking. */
162 #ifdef HAS_INLINES
163 static INLINE LstNode
Lst_FindConst(Lst l,FindProcConst cProc,const void * d)164 Lst_FindConst(Lst l, FindProcConst cProc, const void *d)
165 {
166 return Lst_FindFrom(Lst_First(l), (FindProc)cProc, (void *)d);
167 }
168
169 static INLINE LstNode
Lst_FindFromConst(LstNode ln,FindProcConst cProc,const void * d)170 Lst_FindFromConst(LstNode ln, FindProcConst cProc, const void *d)
171 {
172 return Lst_FindFrom(ln, (FindProc)cProc, (void *)d);
173 }
174 #else
175 #define Lst_FindConst(l, cProc, d) \
176 Lst_FindFrom(Lst_First(l), (FindProc)cProc, (void *)d)
177 #define Lst_FindFromConst(ln, cProc, d) \
178 Lst_FindFrom(ln, (FindProc)cProc, (void *)d)
179 #endif
180
181 #endif /* _LST_H_ */
182