[unix-history] / usr.bin / make / list.h

/*
 * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
 * Copyright (c) 1988, 1989 by Adam de Boor
 * Copyright (c) 1989 by Berkeley Softworks
 * All rights reserved.
 *
 * This code is derived from software contributed to Berkeley by
 * Adam de Boor.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *	This product includes software developed by the University of
 *	California, Berkeley and its contributors.
 * 4. Neither the name of the University nor the names of its contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 *
 *	@(#)list.h	5.3 (Berkeley) 6/1/90
 */

/*
 * list.h --
 *
 * Structures, macros, and routines exported by the List module.
 */

#ifndef _LIST
#define _LIST

#ifndef _SPRITE
#include "sprite.h"
#endif _SPRITE

/*
 * This module defines the list abstraction, which enables one to link
 * together arbitrary data structures.  Lists are doubly-linked and
 * circular.  A list contains a header followed by its real members, if
 * any.  (An empty list therefore consists of a single element, the
 * header,  whose nextPtr and prevPtr fields point to itself).  To refer
 * to a list as a whole, the user keeps a pointer to the header; that
 * header is initialized by a call to List_Init(), which creates an empty
 * list given a pointer to a List_Links structure (described below).
 * 
 * The links are contained in a two-element structure called List_Links.
 * A list joins List_Links records (that is, each List_Links structure
 * points to other List_Links structures), but if the List_Links is the
 * first field within a larger structure, then the larger structures are
 * effectively linked together as follows:
 * 
 *	      header
 *	  (List_Links)		   first elt.		    second elt.
 *	-----------------	-----------------	----------------- 
 * ..->	|    nextPtr	| ---->	|  List_Links	| ---->	|  List_Links	|----..
 *	| - - - - - - -	|	|		|	|		| 
 * ..--	|    prevPtr	| <----	|		| <----	|		|<---..
 *	-----------------	- ---  ---  ---	-	- ---  ---  ---	-
 *				|    rest of	|	|    rest of	| 
 *				|   structure	|	|   structure	| 
 *				|		|	|		|
 *				|      ...	|	|      ...	| 
 *				-----------------	----------------- 
 * 
 * It is possible to link structures through List_Links fields that are
 * not at the beginning of the larger structure, but it is then necessary
 * to perform pointer arithmetic to find the beginning of the larger
 * structure, given a pointer to some point within it.
 * 
 * A typical structure might be something like:
 * 
 *      typedef struct {
 *                  List_Links links;
 *                  char ch;
 *                  integer flags;
 *      } EditChar;
 *  
 * Before an element is inserted in a list for the first time, it must
 * be initialized by calling the macro List_InitElement().
 */
\f

/*
 * data structure for lists
 */

typedef struct List_Links {
    struct List_Links *prevPtr;
    struct List_Links *nextPtr;
} List_Links;

/*
 * procedures
 */

void	List_Init();    /* initialize a header to a list */
void    List_Insert();  /* insert an element into a list */
void 	List_Remove();  /* remove an element from a list */
void 	List_Move();    /* move an element elsewhere in a list */
\f
/*
 * ----------------------------------------------------------------------------
 *
 * List_InitElement --
 *
 *      Initialize a list element.  Must be called before an element is first
 *	inserted into a list.
 *
 * ----------------------------------------------------------------------------
 */
#define List_InitElement(elementPtr) \
    (elementPtr)->prevPtr = (List_Links *) NIL; \
    (elementPtr)->nextPtr = (List_Links *) NIL;
    
/*
 * Macros for stepping through or selecting parts of lists
 */

/*
 * ----------------------------------------------------------------------------
 *
 * LIST_FORALL --
 *
 *      Macro to loop through a list and perform an operation on each member.
 *
 *      Usage: LIST_FORALL(headerPtr, itemPtr) {
 *                 / * 
 *                   * operation on itemPtr, which points to successive members
 *                   * of the list
 *                   * 
 *                   * It may be appropriate to first assign
 *                   *          foobarPtr = (Foobar *) itemPtr;
 *                   * to refer to the entire Foobar structure.
 *                   * /
 *             }
 *
 *      Note: itemPtr must be a List_Links pointer variable, and headerPtr
 *      must evaluate to a pointer to a List_Links structure.
 *
 * ----------------------------------------------------------------------------
 */

#define LIST_FORALL(headerPtr, itemPtr) \
        for (itemPtr = List_First(headerPtr); \
             !List_IsAtEnd((headerPtr),itemPtr); \
             itemPtr = List_Next(itemPtr))

/*
 * ----------------------------------------------------------------------------
 *
 * List_IsEmpty --
 *
 *      Macro: Boolean value, TRUE if the given list does not contain any
 *      members.
 *
 *      Usage: if (List_IsEmpty(headerPtr)) ...
 *
 * ----------------------------------------------------------------------------
 */

#define List_IsEmpty(headerPtr) \
        ((headerPtr) == (headerPtr)->nextPtr)

/*
 * ----------------------------------------------------------------------------
 *
 * List_IsAtEnd --
 *
 *      Macro: Boolean value, TRUE if itemPtr is after the end of headerPtr
 *      (i.e., itemPtr is the header of the list).
 *
 *      Usage: if (List_IsAtEnd(headerPtr, itemPtr)) ...
 *
 * ----------------------------------------------------------------------------
 */


#define List_IsAtEnd(headerPtr, itemPtr) \
        ((itemPtr) == (headerPtr))

\f
/*
 * ----------------------------------------------------------------------------
 *
 * List_First --
 *
 *      Macro to return the first member in a list, which is the header if
 *      the list is empty.
 *
 *      Usage: firstPtr = List_First(headerPtr);
 *
 * ----------------------------------------------------------------------------
 */

#define List_First(headerPtr) ((headerPtr)->nextPtr)

/*
 * ----------------------------------------------------------------------------
 *
 * List_Last --
 *
 *      Macro to return the last member in a list, which is the header if
 *      the list is empty.
 *
 *      Usage: lastPtr = List_Last(headerPtr);
 *
 * ----------------------------------------------------------------------------
 */

#define List_Last(headerPtr) ((headerPtr)->prevPtr)

/*
 * ----------------------------------------------------------------------------
 *
 * List_Prev --
 *
 *      Macro to return the member preceding the given member in its list.
 *      If the given list member is the first element in the list, List_Prev
 *      returns the list header.
 *
 *      Usage: prevPtr = List_Prev(itemPtr);
 *
 * ----------------------------------------------------------------------------
 */

#define List_Prev(itemPtr) ((itemPtr)->prevPtr)

/*
 * ----------------------------------------------------------------------------
 *
 * List_Next --
 *
 *      Macro to return the member following the given member in its list.
 *      If the given list member is the last element in the list, List_Next
 *      returns the list header.
 *
 *      Usage: nextPtr = List_Next(itemPtr);
 *
 * ----------------------------------------------------------------------------
 */

#define List_Next(itemPtr) ((itemPtr)->nextPtr)

\f
/*
 * ----------------------------------------------------------------------------
 *      The List_Insert procedure takes two arguments.  The first argument
 *      is a pointer to the structure to be inserted into a list, and
 *      the second argument is a pointer to the list member after which
 *      the new element is to be inserted.  Macros are used to determine
 *      which existing member will precede the new one.
 *
 *      The List_Move procedure takes a destination argument with the same
 *      semantics as List_Insert.
 *
 *      The following macros define where to insert the new element
 *      in the list:
 *
 *      LIST_AFTER(itemPtr)     --      insert after itemPtr
 *      LIST_BEFORE(itemPtr)    --      insert before itemPtr
 *      LIST_ATFRONT(headerPtr) --      insert at front of list
 *      LIST_ATREAR(headerPtr)  --      insert at end of list
 *
 *      For example, 
 *
 *              List_Insert(itemPtr, LIST_AFTER(otherPtr));
 *
 *      will insert itemPtr following otherPtr in the list containing otherPtr.
 * ----------------------------------------------------------------------------
 */

#define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)

#define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)

#define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)

#define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)

#endif _LIST
Commit	Line	Data
15637ed4 RG	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	\f
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	\f
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	\f
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	* Usage: prevPtr = List_Prev(itemPtr);
240	*
241	* ----------------------------------------------------------------------------
242	*/
243
244	#define List_Prev(itemPtr) ((itemPtr)->prevPtr)
245
246	/*
247	* ----------------------------------------------------------------------------
248	*
249	* List_Next --
250	*
251	* Macro to return the member following the given member in its list.
252	* If the given list member is the last element in the list, List_Next
253	* returns the list header.
254	*
255	* Usage: nextPtr = List_Next(itemPtr);
256	*
257	* ----------------------------------------------------------------------------
258	*/
259
260	#define List_Next(itemPtr) ((itemPtr)->nextPtr)
261
262	\f
263	/*
264	* ----------------------------------------------------------------------------
265	* The List_Insert procedure takes two arguments. The first argument
266	* is a pointer to the structure to be inserted into a list, and
267	* the second argument is a pointer to the list member after which
268	* the new element is to be inserted. Macros are used to determine
269	* which existing member will precede the new one.
270	*
271	* The List_Move procedure takes a destination argument with the same
272	* semantics as List_Insert.
273	*
274	* The following macros define where to insert the new element
275	* in the list:
276	*
277	* LIST_AFTER(itemPtr) -- insert after itemPtr
278	* LIST_BEFORE(itemPtr) -- insert before itemPtr
279	* LIST_ATFRONT(headerPtr) -- insert at front of list
280	* LIST_ATREAR(headerPtr) -- insert at end of list
281	*
282	* For example,
283	*
284	* List_Insert(itemPtr, LIST_AFTER(otherPtr));
285	*
286	* will insert itemPtr following otherPtr in the list containing otherPtr.
287	* ----------------------------------------------------------------------------
288	*/
289
290	#define LIST_AFTER(itemPtr) ((List_Links *) itemPtr)
291
292	#define LIST_BEFORE(itemPtr) (((List_Links *) itemPtr)->prevPtr)
293
294	#define LIST_ATFRONT(headerPtr) ((List_Links *) headerPtr)
295
296	#define LIST_ATREAR(headerPtr) (((List_Links *) headerPtr)->prevPtr)
297
298	#endif _LIST