1
/* $NetBSD: lst.h,v 1.18 2009/01/23 21:58:27 dsl Exp $ */
4
* Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
7
* This code is derived from software contributed to Berkeley by
10
* Redistribution and use in source and binary forms, with or without
11
* modification, are permitted provided that the following conditions
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.
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
34
* from: @(#)lst.h 8.1 (Berkeley) 6/6/93
38
* Copyright (c) 1988, 1989 by Adam de Boor
39
* Copyright (c) 1989 by Berkeley Softworks
40
* All rights reserved.
42
* This code is derived from software contributed to Berkeley by
45
* Redistribution and use in source and binary forms, with or without
46
* modification, are permitted provided that the following conditions
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.
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
73
* from: @(#)lst.h 8.1 (Berkeley) 6/6/93
78
* Header for using the list library
83
#include <sys/param.h>
89
* basic typedef. This is what the Lst_ functions handle
92
typedef struct List *Lst;
93
typedef struct ListNode *LstNode;
95
typedef void *DuplicateProc(void *);
96
typedef void FreeProc(void *);
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 */
102
* Creation/destruction functions
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);
114
* Functions to modify a list
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);
132
* Node-specific functions
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);
146
* Functions for entire lists
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 *));
154
* See if the given datum is on the list. Returns the LstNode containing
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 *);
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.
165
int Lst_ForEachFrom(Lst, LstNode, int (*)(void *, void *),
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().
173
ReturnStatus Lst_Open(Lst);
174
/* Next element please */
175
LstNode Lst_Next(Lst);
177
Boolean Lst_IsAtEnd(Lst);
178
/* Finish table access */
182
* for using the list as a queue
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);