Accept topic changes from servers that do not send topic-set timestamps (fixes SF...
[ircu2.10.12-pk.git] / libs / dbprim / doc / man / man3 / dbprim_link.3
1 .TH "Linked lists" 3 "6 Mar 2003" "dbprim" \" -*- nroff -*-
2 .ad l
3 .nh
4 .SH NAME
5 Linked lists \- Operations for linked lists. 
6 More...
7 .SS "Defines"
8
9 .in +1c
10 .ti -1c
11 .RI "#define \fBLINK_HEAD_INIT\fP(extra)"
12 .br
13 .RI "\fILinked list head static initializer.\fP"
14 .ti -1c
15 .RI "#define \fBll_verify\fP(list)"
16 .br
17 .RI "\fILinked list head verification macro.\fP"
18 .ti -1c
19 .RI "#define \fBll_count\fP(list)"
20 .br
21 .RI "\fILinked list count.\fP"
22 .ti -1c
23 .RI "#define \fBll_first\fP(list)"
24 .br
25 .RI "\fIFirst element in linked list.\fP"
26 .ti -1c
27 .RI "#define \fBll_last\fP(list)"
28 .br
29 .RI "\fILast element in a linked list.\fP"
30 .ti -1c
31 .RI "#define \fBll_extra\fP(list)"
32 .br
33 .RI "\fIExtra pointer data in a linked list.\fP"
34 .ti -1c
35 .RI "#define \fBLINK_ELEM_INIT\fP(obj)"
36 .br
37 .RI "\fILinked list element static initializer.\fP"
38 .ti -1c
39 .RI "#define \fBle_verify\fP(element)"
40 .br
41 .RI "\fILinked list element verification macro.\fP"
42 .ti -1c
43 .RI "#define \fBle_next\fP(elem)"
44 .br
45 .RI "\fILinked list element next pointer.\fP"
46 .ti -1c
47 .RI "#define \fBle_prev\fP(elem)"
48 .br
49 .RI "\fILinked list element previous pointer.\fP"
50 .ti -1c
51 .RI "#define \fBle_object\fP(elem)"
52 .br
53 .RI "\fILinked list element object pointer.\fP"
54 .ti -1c
55 .RI "#define \fBle_head\fP(elem)"
56 .br
57 .RI "\fILinked list element head pointer.\fP"
58 .ti -1c
59 .RI "#define \fBle_flags\fP(elem)"
60 .br
61 .RI "\fILinked list element flags.\fP"
62 .in -1c
63 .SS "Typedefs"
64
65 .in +1c
66 .ti -1c
67 .RI "typedef struct _link_head_s \fBlink_head_t\fP"
68 .br
69 .RI "\fILinked list head.\fP"
70 .ti -1c
71 .RI "typedef struct _link_elem_s \fBlink_elem_t\fP"
72 .br
73 .RI "\fILinked list element.\fP"
74 .ti -1c
75 .RI "typedef unsigned long (* \fBlink_iter_t\fP )(\fBlink_head_t\fP *, \fBlink_elem_t\fP *, void *)"
76 .br
77 .RI "\fILinked list iteration callback.\fP"
78 .ti -1c
79 .RI "typedef unsigned long (* \fBlink_comp_t\fP )(\fBdb_key_t\fP *, void *)"
80 .br
81 .RI "\fILinked list comparison callback.\fP"
82 .ti -1c
83 .RI "typedef enum \fB_link_loc_e\fP \fBlink_loc_t\fP"
84 .br
85 .RI "\fILinked list location.\fP"
86 .in -1c
87 .SS "Enumerations"
88
89 .in +1c
90 .ti -1c
91 .RI "enum \fB_link_loc_e\fP { \fBLINK_LOC_HEAD\fP, \fBLINK_LOC_TAIL\fP, \fBLINK_LOC_BEFORE\fP, \fBLINK_LOC_AFTER\fP }"
92 .br
93 .RI "\fILinked list location.\fP"
94 .in -1c
95 .SS "Functions"
96
97 .in +1c
98 .ti -1c
99 .RI "unsigned long \fBll_init\fP (\fBlink_head_t\fP *list, void *extra)"
100 .br
101 .RI "\fIDynamically initialize a linked list head.\fP"
102 .ti -1c
103 .RI "unsigned long \fBll_add\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP *new, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP *elem)"
104 .br
105 .RI "\fIAdd an element to a linked list.\fP"
106 .ti -1c
107 .RI "unsigned long \fBll_move\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP *new, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP *elem)"
108 .br
109 .RI "\fIMove an element within a linked list.\fP"
110 .ti -1c
111 .RI "unsigned long \fBll_remove\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP *elem)"
112 .br
113 .RI "\fIRemove an element from a linked list.\fP"
114 .ti -1c
115 .RI "unsigned long \fBll_find\fP (\fBlink_head_t\fP *list, \fBlink_elem_t\fP **elem_p, \fBlink_comp_t\fP comp_func, \fBlink_elem_t\fP *start, \fBdb_key_t\fP *key)"
116 .br
117 .RI "\fIFind an element in a linked list.\fP"
118 .ti -1c
119 .RI "unsigned long \fBll_iter\fP (\fBlink_head_t\fP *list, \fBlink_iter_t\fP iter_func, void *extra)"
120 .br
121 .RI "\fIIterate over each entry in a linked list.\fP"
122 .ti -1c
123 .RI "unsigned long \fBll_flush\fP (\fBlink_head_t\fP *list, \fBlink_iter_t\fP flush_func, void *extra)"
124 .br
125 .RI "\fIFlush a linked list.\fP"
126 .ti -1c
127 .RI "unsigned long \fBle_init\fP (\fBlink_elem_t\fP *elem, void *object)"
128 .br
129 .RI "\fIDynamically initialize a linked list element.\fP"
130 .in -1c
131 .SH "DETAILED DESCRIPTION"
132 .PP 
133 Linked lists are a very basic data structure used in building databases. This library provides a simple yet powerful implementation of generic linked lists, based on two caller-allocated structures. The \fBlink_head_t\fP structure describes the head of a linked list and contains information regarding the number of elements in the linked list as well as pointers referencing the first and last elements in the list. The \fBlink_elem_t\fP structure describes a specific element in the linked list and contains pointers referencing the next and previous elements in the list, as well as a pointer to the object, a pointer to the head of the linked list, and a set of user-specified flags.
134 .PP
135 Elements may be added at any arbitrary location in the linked list with \fBll_add\fP(); moved to any other arbitrary location in the linked list with \fBll_move\fP(), or removed from the list with \fBll_remove\fP(). In addition, the user may search the list using a user-defined comparison function with \fBll_find\fP(); iterate over every element in the list with \fBll_iter\fP(); or remove all items from the list with \fBll_flush\fP(), optionally executing a user-specified clean-up function. 
136 .SH "DEFINE DOCUMENTATION"
137 .PP 
138 .SS "#define LINK_ELEM_INIT(obj)"
139 .PP
140 .PP
141  This macro statically initializes a \fBlink_elem_t\fP.
142 .PP
143 \fBParameters: \fP
144 .in +1c
145 .TP
146 \fB\fIobj\fP\fP
147 A pointer to \fCvoid\fP representing the object associated with the element. 
148 .SS "#define LINK_HEAD_INIT(extra)"
149 .PP
150 .PP
151  This macro statically initializes a \fBlink_head_t\fP.
152 .PP
153 \fBParameters: \fP
154 .in +1c
155 .TP
156 \fB\fIextra\fP\fP
157 Extra pointer data that should be associated with the list head. 
158 .SS "#define le_flags(elem)"
159 .PP
160 .PP
161  This macro retrieves a set of user-defined flags associated with the element. It may be used as an lvalue to set those flags.
162 .PP
163 \fBParameters: \fP
164 .in +1c
165 .TP
166 \fB\fIelem\fP\fP
167 A pointer to a \fBlink_elem_t\fP.
168 .PP
169 \fBReturns: \fP
170 .in +1c
171 An \fCunsigned long\fP containing the flags associated with the element. 
172 .SS "#define le_head(elem)"
173 .PP
174 .PP
175  This macro retrieves a pointer to the head of the linked list that the element is in.
176 .PP
177 \fBParameters: \fP
178 .in +1c
179 .TP
180 \fB\fIelem\fP\fP
181 A pointer to a \fBlink_elem_t\fP.
182 .PP
183 \fBReturns: \fP
184 .in +1c
185 A pointer to a \fBlink_head_t\fP representing the head of the linked list the element is in. 
186 .SS "#define le_next(elem)"
187 .PP
188 .PP
189  This macro retrieves a pointer to the next element in the linked list.
190 .PP
191 \fBParameters: \fP
192 .in +1c
193 .TP
194 \fB\fIelem\fP\fP
195 A pointer to a \fBlink_elem_t\fP.
196 .PP
197 \fBReturns: \fP
198 .in +1c
199 A pointer to a \fBlink_elem_t\fP representing the next element in the linked list. 
200 .SS "#define le_object(elem)"
201 .PP
202 .PP
203  This macro retrieves a pointer to the object represented by the element. It may be used as an lvalue to change the object pointed to. Care should be taken when using this feature.
204 .PP
205 \fBParameters: \fP
206 .in +1c
207 .TP
208 \fB\fIelem\fP\fP
209 A pointer to a \fBlink_elem_t\fP.
210 .PP
211 \fBReturns: \fP
212 .in +1c
213 A pointer to \fCvoid\fP representing the object associated with the linked list element. 
214 .SS "#define le_prev(elem)"
215 .PP
216 .PP
217  This macro retrieves a pointer to the previous element in the linked list.
218 .PP
219 \fBParameters: \fP
220 .in +1c
221 .TP
222 \fB\fIelem\fP\fP
223 A pointer to a \fBlink_elem_t\fP.
224 .PP
225 \fBReturns: \fP
226 .in +1c
227 A pointer to a \fBlink_elem_t\fP representing the previous element in the linked list. 
228 .SS "#define le_verify(element)"
229 .PP
230 .PP
231  This macro verifies that a given pointer actually does point to a linked list element.
232 .PP
233 \fBParameters: \fP
234 .in +1c
235 .TP
236 \fB\fIelement\fP\fP
237 A pointer to a \fBlink_elem_t\fP.
238 .PP
239 \fBReturns: \fP
240 .in +1c
241 Boolean true if \fCelement\fP is a valid linked list element or false otherwise. 
242 .SS "#define ll_count(list)"
243 .PP
244 .PP
245  This macro retrieves the number of elements in a linked list.
246 .PP
247 \fBParameters: \fP
248 .in +1c
249 .TP
250 \fB\fIlist\fP\fP
251 A pointer to a \fBlink_head_t\fP.
252 .PP
253 \fBReturns: \fP
254 .in +1c
255 An \fCunsigned long\fP containing a count of the number of elements in the linked list. 
256 .SS "#define ll_extra(list)"
257 .PP
258 .PP
259  This macro retrieves the extra pointer data associated with a particular linked list.
260 .PP
261 \fBParameters: \fP
262 .in +1c
263 .TP
264 \fB\fIlist\fP\fP
265 A pointer to a \fBlink_head_t\fP.
266 .PP
267 \fBReturns: \fP
268 .in +1c
269 A pointer to \fCvoid\fP. 
270 .SS "#define ll_first(list)"
271 .PP
272 .PP
273  This macro retrieves the first element in a linked list.
274 .PP
275 \fBParameters: \fP
276 .in +1c
277 .TP
278 \fB\fIlist\fP\fP
279 A pointer to a \fBlink_head_t\fP.
280 .PP
281 \fBReturns: \fP
282 .in +1c
283 A pointer to a \fBlink_elem_t\fP. 
284 .SS "#define ll_last(list)"
285 .PP
286 .PP
287  This macro retrieves the last element in a linked list.
288 .PP
289 \fBParameters: \fP
290 .in +1c
291 .TP
292 \fB\fIlist\fP\fP
293 A pointer to a \fBlink_head_t\fP.
294 .PP
295 \fBReturns: \fP
296 .in +1c
297 A pointer to a \fBlink_elem_t\fP. 
298 .SS "#define ll_verify(list)"
299 .PP
300 .PP
301  This macro verifies that a given pointer actually does point to a linked list head.
302 .PP
303 \fBParameters: \fP
304 .in +1c
305 .TP
306 \fB\fIlist\fP\fP
307 A pointer to a \fBlink_head_t\fP.
308 .PP
309 \fBReturns: \fP
310 .in +1c
311 Boolean true if \fClist\fP is a valid linked list head or false otherwise. 
312 .SH "TYPEDEF DOCUMENTATION"
313 .PP 
314 .SS "typedef unsigned long(* link_comp_t)(\fBdb_key_t\fP *, void *)"
315 .PP
316 .PP
317  This function pointer references a callback used by \fBll_find\fP(). It should return 0 if the entry passed as the second argument matches the key passed as the first argument. 
318 .SS "typedef struct _link_elem_s link_elem_t"
319 .PP
320 .PP
321  This structure represents a single element of a linked list. 
322 .SS "typedef struct _link_head_s link_head_t"
323 .PP
324 .PP
325  This structure is the head of all linked lists maintained by this library. 
326 .SS "typedef unsigned long(* link_iter_t)(\fBlink_head_t\fP *, \fBlink_elem_t\fP *, void *)"
327 .PP
328 .PP
329  This function pointer references a callback used by \fBll_iter\fP() and \fBll_flush\fP(). It should return 0 for success. A non-zero return value will terminate the operation and will become the return value of the \fBll_iter\fP() or \fBll_flush\fP() call. 
330 .SS "typedef enum \fB_link_loc_e\fP link_loc_t"
331 .PP
332 .PP
333  See the documentation for the enumeration \fB_link_loc_e\fP. 
334 .SH "ENUMERATION TYPE DOCUMENTATION"
335 .PP 
336 .SS "enum _link_loc_e"
337 .PP
338 .PP
339  This enumeration is used to specify where an element in a linked list should be placed. It should be referenced by the typedef \fBlink_loc_t\fP. 
340 .PP
341 \fBEnumeration values:\fP
342 .in +1c
343 .TP
344 \fB\fILINK_LOC_HEAD\fP \fP
345 Element should be inserted at head of list. 
346 .TP
347 \fB\fILINK_LOC_TAIL\fP \fP
348 Element should be inserted at tail of list. 
349 .TP
350 \fB\fILINK_LOC_BEFORE\fP \fP
351 Element should be inserted before specified element. 
352 .TP
353 \fB\fILINK_LOC_AFTER\fP \fP
354 Element should be inserted after specified element. 
355 .SH "FUNCTION DOCUMENTATION"
356 .PP 
357 .SS "unsigned long le_init (\fBlink_elem_t\fP * elem, void * object)"
358 .PP
359 .PP
360  This function dynamically initializes a linked list element.
361 .PP
362 \fBParameters: \fP
363 .in +1c
364 .TP
365 \fB\fIelem\fP\fP
366 A pointer to a \fBlink_elem_t\fP to be initialized. 
367 .TP
368 \fB\fIobject\fP\fP
369 A pointer to \fCvoid\fP used to represent the object associated with the element. May not be \fCNULL\fP.
370 .PP
371 \fBReturn values: \fP
372 .in +1c
373 .TP
374 \fB\fIDB_ERR_BADARGS\fP\fP
375 A \fCNULL\fP pointer was passed for \fCelem\fP or \fCobject\fP. 
376 .SS "unsigned long ll_add (\fBlink_head_t\fP * list, \fBlink_elem_t\fP * new, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP * elem)"
377 .PP
378 .PP
379  This function adds a given element to a specified linked list in the specified location.
380 .PP
381 \fBParameters: \fP
382 .in +1c
383 .TP
384 \fB\fIlist\fP\fP
385 A pointer to a \fBlink_head_t\fP. 
386 .TP
387 \fB\fInew\fP\fP
388 A pointer to the \fBlink_elem_t\fP to be added to the linked list. 
389 .TP
390 \fB\fIloc\fP\fP
391 A \fBlink_loc_t\fP indicating where the entry should be added. 
392 .TP
393 \fB\fIelem\fP\fP
394 A pointer to a \fBlink_elem_t\fP describing another element in the list if \fCloc\fP is \fBLINK_LOC_BEFORE\fP or \fBLINK_LOC_AFTER\fP.
395 .PP
396 \fBReturn values: \fP
397 .in +1c
398 .TP
399 \fB\fIDB_ERR_BADARGS\fP\fP
400 An argument was invalid. 
401 .TP
402 \fB\fIDB_ERR_BUSY\fP\fP
403 The element is already in a list. 
404 .TP
405 \fB\fIDB_ERR_WRONGTABLE\fP\fP
406 \fCelem\fP is in a different list. 
407 .TP
408 \fB\fIDB_ERR_UNUSED\fP\fP
409 \fCelem\fP is not in any list. 
410 .SS "unsigned long ll_find (\fBlink_head_t\fP * list, \fBlink_elem_t\fP ** elem_p, \fBlink_comp_t\fP comp_func, \fBlink_elem_t\fP * start, \fBdb_key_t\fP * key)"
411 .PP
412 .PP
413  This function iterates through a linked list looking for an element that matches the given \fCkey\fP.
414 .PP
415 \fBParameters: \fP
416 .in +1c
417 .TP
418 \fB\fIlist\fP\fP
419 A pointer to a \fBlink_head_t\fP. 
420 .TP
421 \fB\fIelem_p\fP\fP
422 A pointer to a pointer to a \fBlink_elem_t\fP. This is a result parameter. \fCNULL\fP is an invalid value. 
423 .TP
424 \fB\fIcomp_func\fP\fP
425 A pointer to a comparison function used to compare the key to a particular element. See the documentation for \fBlink_comp_t\fP for more information. 
426 .TP
427 \fB\fIstart\fP\fP
428 A pointer to a \fBlink_elem_t\fP describing where in the linked list to start. If \fCNULL\fP is passed, the beginning of the list will be assumed. 
429 .TP
430 \fB\fIkey\fP\fP
431 A key to search for.
432 .PP
433 \fBReturn values: \fP
434 .in +1c
435 .TP
436 \fB\fIDB_ERR_BADARGS\fP\fP
437 An argument was invalid. 
438 .TP
439 \fB\fIDB_ERR_WRONGTABLE\fP\fP
440 \fCstart\fP is not in this linked list. 
441 .TP
442 \fB\fIDB_ERR_NOENTRY\fP\fP
443 No matching entry was found. 
444 .SS "unsigned long ll_flush (\fBlink_head_t\fP * list, \fBlink_iter_t\fP flush_func, void * extra)"
445 .PP
446 .PP
447  This function flushes a linked list--that is, it removes each element from the list. If a \fCflush_func\fP is specified, it will be called on the entry after it has been removed from the list, and may safely call \fCfree()\fP.
448 .PP
449 \fBParameters: \fP
450 .in +1c
451 .TP
452 \fB\fIlist\fP\fP
453 A pointer to a \fBlink_head_t\fP. 
454 .TP
455 \fB\fIflush_func\fP\fP
456 A pointer to a callback function used to perform user-specified actions on an element after removing it from the list. May be \fCNULL\fP. See the documentation for \fBlink_iter_t\fP for more information. 
457 .TP
458 \fB\fIextra\fP\fP
459 A \fCvoid\fP pointer that will be passed to \fCflush_func\fP.
460 .PP
461 \fBReturn values: \fP
462 .in +1c
463 .TP
464 \fB\fIDB_ERR_BADARGS\fP\fP
465 An argument was invalid. 
466 .SS "unsigned long ll_init (\fBlink_head_t\fP * list, void * extra)"
467 .PP
468 .PP
469  This function dynamically initializes a linked list head.
470 .PP
471 \fBParameters: \fP
472 .in +1c
473 .TP
474 \fB\fIlist\fP\fP
475 A pointer to a \fBlink_head_t\fP to be initialized. 
476 .TP
477 \fB\fIextra\fP\fP
478 A pointer to \fCvoid\fP containing extra pointer data associated with the linked list.
479 .PP
480 \fBReturn values: \fP
481 .in +1c
482 .TP
483 \fB\fIDB_ERR_BADARGS\fP\fP
484 A \fCNULL\fP pointer was passed for \fClist\fP. 
485 .SS "unsigned long ll_iter (\fBlink_head_t\fP * list, \fBlink_iter_t\fP iter_func, void * extra)"
486 .PP
487 .PP
488  This function iterates over a linked list, executing the given \fCiter_func\fP for each entry.
489 .PP
490 \fBParameters: \fP
491 .in +1c
492 .TP
493 \fB\fIlist\fP\fP
494 A pointer to a \fBlink_head_t\fP. 
495 .TP
496 \fB\fIiter_func\fP\fP
497 A pointer to a callback function used to perform user-specified actions on an element in a linked list. \fCNULL\fP is an invalid value. See the documentation for \fBlink_iter_t\fP for more information. 
498 .TP
499 \fB\fIextra\fP\fP
500 A \fCvoid\fP pointer that will be passed to \fCiter_func\fP.
501 .PP
502 \fBReturn values: \fP
503 .in +1c
504 .TP
505 \fB\fIDB_ERR_BADARGS\fP\fP
506 An argument was invalid. 
507 .SS "unsigned long ll_move (\fBlink_head_t\fP * list, \fBlink_elem_t\fP * elem, \fBlink_loc_t\fP loc, \fBlink_elem_t\fP * elem2)"
508 .PP
509 .PP
510  This function moves a specified element within the linked list.
511 .PP
512 \fBParameters: \fP
513 .in +1c
514 .TP
515 \fB\fIlist\fP\fP
516 A pointer to a \fBlink_head_t\fP. 
517 .TP
518 \fB\fIelem\fP\fP
519 A pointer to the \fBlink_elem_t\fP describing the element to be moved. 
520 .TP
521 \fB\fIloc\fP\fP
522 A \fBlink_loc_t\fP indicating where the entry should be moved to. 
523 .TP
524 \fB\fIelem2\fP\fP
525 A pointer to a \fBlink_elem_t\fP describing another element in the list if \fCloc\fP is \fBLINK_LOC_BEFORE\fP or \fBLINK_LOC_AFTER\fP.
526 .PP
527 \fBReturn values: \fP
528 .in +1c
529 .TP
530 \fB\fIDB_ERR_BADARGS\fP\fP
531 An argument was invalid. 
532 .TP
533 \fB\fIDB_ERR_BUSY\fP\fP
534 \fCelem\fP and \fCelem2\fP are the same element. 
535 .TP
536 \fB\fIDB_ERR_WRONGTABLE\fP\fP
537 \fCelem\fP or \fCelem2\fP are in a different list. 
538 .TP
539 \fB\fIDB_ERR_UNUSED\fP\fP
540 \fCelem\fP or \fCelem2\fP are not in any list. 
541 .SS "unsigned long ll_remove (\fBlink_head_t\fP * list, \fBlink_elem_t\fP * elem)"
542 .PP
543 .PP
544  This function removes a specified element from a linked list.
545 .PP
546 \fBParameters: \fP
547 .in +1c
548 .TP
549 \fB\fIlist\fP\fP
550 A pointer to a \fBlink_head_t\fP. 
551 .TP
552 \fB\fIelem\fP\fP
553 A pointer to the \fBlink_elem_t\fP describing the element to be removed.
554 .PP
555 \fBReturn values: \fP
556 .in +1c
557 .TP
558 \fB\fIDB_ERR_BADARGS\fP\fP
559 An argument was invalid. 
560 .TP
561 \fB\fIDB_ERR_UNUSED\fP\fP
562 \fCelem\fP is not in a linked list. 
563 .TP
564 \fB\fIDB_ERR_WRONGTABLE\fP\fP
565 \fCelem\fP is not in this linked list.