1 /* $Id$ */
2 /*
3 * Copyright (C) 2008-2011 Teluu Inc. (http://www.teluu.com)
4 * Copyright (C) 2003-2008 Benny Prijono <benny@prijono.org>
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20 #ifndef __PJ_LIST_H__
21 #define __PJ_LIST_H__
22
23 /**
24 * @file list.h
25 * @brief Linked List data structure.
26 */
27
28 #include <pj/types.h>
29
30 PJ_BEGIN_DECL
31
32 /*
33 * @defgroup PJ_DS Data Structure.
34 */
35
36 /**
37 * @defgroup PJ_LIST Linked List
38 * @ingroup PJ_DS
39 * @{
40 *
41 * List in PJLIB is implemented as doubly-linked list, and it won't require
42 * dynamic memory allocation (just as all PJLIB data structures). The list here
43 * should be viewed more like a low level C list instead of high level C++ list
44 * (which normally are easier to use but require dynamic memory allocations),
45 * therefore all caveats with C list apply here too (such as you can NOT put
46 * a node in more than one lists).
47 *
48 * \section pj_list_example_sec Examples
49 *
50 * See below for examples on how to manipulate linked list:
51 * - @ref page_pjlib_samples_list_c
52 * - @ref page_pjlib_list_test
53 */
54
55
56 /**
57 * Use this macro in the start of the structure declaration to declare that
58 * the structure can be used in the linked list operation. This macro simply
59 * declares additional member @a prev and @a next to the structure.
60 * @hideinitializer
61 */
62 #define PJ_DECL_LIST_MEMBER(type) \
63 /** List @a prev. */ \
64 type *prev; \
65 /** List @a next. */ \
66 type *next
67
68
69 /**
70 * This structure describes generic list node and list. The owner of this list
71 * must initialize the 'value' member to an appropriate value (typically the
72 * owner itself).
73 */
74 struct pj_list
75 {
76 PJ_DECL_LIST_MEMBER(void);
77 } PJ_ATTR_MAY_ALIAS; /* may_alias avoids warning with gcc-4.4 -Wall -O2 */
78
79
80 /**
81 * Initialize the list.
82 * Initially, the list will have no member, and function pj_list_empty() will
83 * always return nonzero (which indicates TRUE) for the newly initialized
84 * list.
85 *
86 * @param node The list head.
87 */
pj_list_init(pj_list_type * node)88 PJ_INLINE(void) pj_list_init(pj_list_type * node)
89 {
90 ((pj_list*)node)->next = ((pj_list*)node)->prev = node;
91 }
92
93
94 /**
95 * Check that the list is empty.
96 *
97 * @param node The list head.
98 *
99 * @return Non-zero if the list is empty, or zero if it is not empty.
100 *
101 */
pj_list_empty(const pj_list_type * node)102 PJ_INLINE(int) pj_list_empty(const pj_list_type * node)
103 {
104 return ((pj_list*)node)->next == node;
105 }
106
107
108 /**
109 * Insert the node to the list before the specified element position.
110 *
111 * @param pos The element to which the node will be inserted before.
112 * @param node The element to be inserted.
113 *
114 * @return void.
115 */
116 PJ_IDECL(void) pj_list_insert_before(pj_list_type *pos, pj_list_type *node);
117
118
119 /**
120 * Insert the node to the back of the list. This is just an alias for
121 * #pj_list_insert_before().
122 *
123 * @param list The list.
124 * @param node The element to be inserted.
125 */
pj_list_push_back(pj_list_type * list,pj_list_type * node)126 PJ_INLINE(void) pj_list_push_back(pj_list_type *list, pj_list_type *node)
127 {
128 pj_list_insert_before(list, node);
129 }
130
131
132 /**
133 * Inserts all nodes in \a nodes to the target list.
134 *
135 * @param lst The target list.
136 * @param nodes Nodes list.
137 */
138 PJ_IDECL(void) pj_list_insert_nodes_before(pj_list_type *lst,
139 pj_list_type *nodes);
140
141 /**
142 * Insert a node to the list after the specified element position.
143 *
144 * @param pos The element in the list which will precede the inserted
145 * element.
146 * @param node The element to be inserted after the position element.
147 *
148 * @return void.
149 */
150 PJ_IDECL(void) pj_list_insert_after(pj_list_type *pos, pj_list_type *node);
151
152
153 /**
154 * Insert the node to the front of the list. This is just an alias for
155 * #pj_list_insert_after().
156 *
157 * @param list The list.
158 * @param node The element to be inserted.
159 */
pj_list_push_front(pj_list_type * list,pj_list_type * node)160 PJ_INLINE(void) pj_list_push_front(pj_list_type *list, pj_list_type *node)
161 {
162 pj_list_insert_after(list, node);
163 }
164
165
166 /**
167 * Insert all nodes in \a nodes to the target list.
168 *
169 * @param lst The target list.
170 * @param nodes Nodes list.
171 */
172 PJ_IDECL(void) pj_list_insert_nodes_after(pj_list_type *lst,
173 pj_list_type *nodes);
174
175
176 /**
177 * Remove elements from the source list, and insert them to the destination
178 * list. The elements of the source list will occupy the
179 * front elements of the target list. Note that the node pointed by \a list2
180 * itself is not considered as a node, but rather as the list descriptor, so
181 * it will not be inserted to the \a list1. The elements to be inserted starts
182 * at \a list2->next. If \a list2 is to be included in the operation, use
183 * \a pj_list_insert_nodes_before.
184 *
185 * @param list1 The destination list.
186 * @param list2 The source list.
187 *
188 * @return void.
189 */
190 PJ_IDECL(void) pj_list_merge_first(pj_list_type *list1, pj_list_type *list2);
191
192
193 /**
194 * Remove elements from the second list argument, and insert them to the list
195 * in the first argument. The elements from the second list will be appended
196 * to the first list. Note that the node pointed by \a list2
197 * itself is not considered as a node, but rather as the list descriptor, so
198 * it will not be inserted to the \a list1. The elements to be inserted starts
199 * at \a list2->next. If \a list2 is to be included in the operation, use
200 * \a pj_list_insert_nodes_before.
201 *
202 * @param list1 The element in the list which will precede the inserted
203 * element.
204 * @param list2 The element in the list to be inserted.
205 *
206 * @return void.
207 */
208 PJ_IDECL(void) pj_list_merge_last( pj_list_type *list1, pj_list_type *list2);
209
210
211 /**
212 * Erase the node from the list it currently belongs.
213 *
214 * @param node The element to be erased.
215 */
216 PJ_IDECL(void) pj_list_erase(pj_list_type *node);
217
218
219 /**
220 * Find node in the list.
221 *
222 * @param list The list head.
223 * @param node The node element to be searched.
224 *
225 * @return The node itself if it is found in the list, or NULL if it is not
226 * found in the list.
227 */
228 PJ_IDECL(pj_list_type*) pj_list_find_node(pj_list_type *list,
229 pj_list_type *node);
230
231
232 /**
233 * Search the list for the specified value, using the specified comparison
234 * function. This function iterates on nodes in the list, started with the
235 * first node, and call the user supplied comparison function until the
236 * comparison function returns ZERO.
237 *
238 * @param list The list head.
239 * @param value The user defined value to be passed in the comparison
240 * function
241 * @param comp The comparison function, which should return ZERO to
242 * indicate that the searched value is found.
243 *
244 * @return The first node that matched, or NULL if it is not found.
245 */
246 PJ_IDECL(pj_list_type*) pj_list_search(pj_list_type *list, void *value,
247 int (*comp)(void *value,
248 const pj_list_type *node)
249 );
250
251
252 /**
253 * Traverse the list to get the number of elements in the list.
254 *
255 * @param list The list head.
256 *
257 * @return Number of elements.
258 */
259 PJ_IDECL(pj_size_t) pj_list_size(const pj_list_type *list);
260
261
262 /**
263 * @}
264 */
265
266 #if PJ_FUNCTIONS_ARE_INLINED
267 # include "list_i.h"
268 #endif
269
270 PJ_END_DECL
271
272 #endif /* __PJ_LIST_H__ */
273
274