2 * List Abstract Data Type
3 * Copyright (C) 1997 Kaz Kylheku <kaz@ashi.footprints.net>
5 * Free Software License:
7 * All rights are reserved by the author, with the following exceptions:
8 * Permission is granted to freely reproduce and distribute this software,
9 * possibly in exchange for a fee, provided that this copyright notice appears
10 * intact. Permission is also granted to adapt this software to produce
11 * derivative works, as long as the modified versions carry this copyright
12 * notice and additional notices stating that the work has been modified.
13 * This source code may be translated into executable form and incorporated
14 * into proprietary software; there is no requirement for such software to
15 * contain a copyright notice related to this source.
17 * $Id: list.h,v 1.19 1999/11/14 20:46:19 kaz Exp $
18 * $Name: kazlib_1_20 $
22 * Modified by Johannes Lehtinen in 2006-2007.
23 * Included the definition of CP_HIDDEN macro and used it in declarations and
24 * definitions to hide Kazlib symbols when building a shared C-Pluff library.
30 #include "../libcpluff/cpluffdef.h"
34 #ifdef KAZLIB_SIDEEFFECT_DEBUG
36 #define LIST_SFX_CHECK(E) SFX_CHECK(E)
38 #define LIST_SFX_CHECK(E) (E)
42 * Blurb for inclusion into C++ translation units
49 typedef unsigned long listcount_t;
50 #define LISTCOUNT_T_MAX ULONG_MAX
52 typedef struct lnode_t
54 #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
55 struct lnode_t *list_next;
56 struct lnode_t *list_prev;
63 typedef struct lnodepool_t
65 #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
66 struct lnode_t *list_pool;
67 struct lnode_t *list_free;
68 listcount_t list_size;
76 #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
78 listcount_t list_nodecount;
79 listcount_t list_maxcount;
85 CP_HIDDEN lnode_t *lnode_create(void *);
86 CP_HIDDEN lnode_t *lnode_init(lnode_t *, void *);
87 CP_HIDDEN void lnode_destroy(lnode_t *);
88 CP_HIDDEN void lnode_put(lnode_t *, void *);
89 CP_HIDDEN void *lnode_get(lnode_t *);
90 CP_HIDDEN int lnode_is_in_a_list(lnode_t *);
92 #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
93 #define lnode_put(N, D) ((N)->list_data = (D))
94 #define lnode_get(N) ((N)->list_data)
97 CP_HIDDEN lnodepool_t *lnode_pool_init(lnodepool_t *, lnode_t *, listcount_t);
98 CP_HIDDEN lnodepool_t *lnode_pool_create(listcount_t);
99 CP_HIDDEN void lnode_pool_destroy(lnodepool_t *);
100 CP_HIDDEN lnode_t *lnode_borrow(lnodepool_t *, void *);
101 CP_HIDDEN void lnode_return(lnodepool_t *, lnode_t *);
102 CP_HIDDEN int lnode_pool_isempty(lnodepool_t *);
103 CP_HIDDEN int lnode_pool_isfrom(lnodepool_t *, lnode_t *);
105 CP_HIDDEN list_t *list_init(list_t *, listcount_t);
106 CP_HIDDEN list_t *list_create(listcount_t);
107 CP_HIDDEN void list_destroy(list_t *);
108 CP_HIDDEN void list_destroy_nodes(list_t *);
109 CP_HIDDEN void list_return_nodes(list_t *, lnodepool_t *);
111 CP_HIDDEN listcount_t list_count(list_t *);
112 CP_HIDDEN int list_isempty(list_t *);
113 CP_HIDDEN int list_isfull(list_t *);
114 CP_HIDDEN int list_contains(list_t *, lnode_t *);
116 CP_HIDDEN void list_append(list_t *, lnode_t *);
117 CP_HIDDEN void list_prepend(list_t *, lnode_t *);
118 CP_HIDDEN void list_ins_before(list_t *, lnode_t *, lnode_t *);
119 CP_HIDDEN void list_ins_after(list_t *, lnode_t *, lnode_t *);
121 CP_HIDDEN lnode_t *list_first(list_t *);
122 CP_HIDDEN lnode_t *list_last(list_t *);
123 CP_HIDDEN lnode_t *list_next(list_t *, lnode_t *);
124 CP_HIDDEN lnode_t *list_prev(list_t *, lnode_t *);
126 CP_HIDDEN lnode_t *list_del_first(list_t *);
127 CP_HIDDEN lnode_t *list_del_last(list_t *);
128 CP_HIDDEN lnode_t *list_delete(list_t *, lnode_t *);
130 CP_HIDDEN void list_process(list_t *, void *, void (*)(list_t *, lnode_t *, void *));
132 CP_HIDDEN int list_verify(list_t *);
134 #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
135 #define lnode_pool_isempty(P) ((P)->list_free == 0)
136 #define list_count(L) ((L)->list_nodecount)
137 #define list_isempty(L) ((L)->list_nodecount == 0)
138 #define list_isfull(L) (LIST_SFX_CHECK(L)->list_nodecount == (L)->list_maxcount)
139 #define list_next(L, N) (LIST_SFX_CHECK(N)->list_next == &(L)->list_nilnode ? NULL : (N)->list_next)
140 #define list_prev(L, N) (LIST_SFX_CHECK(N)->list_prev == &(L)->list_nilnode ? NULL : (N)->list_prev)
141 #define list_first(L) list_next(LIST_SFX_CHECK(L), &(L)->list_nilnode)
142 #define list_last(L) list_prev(LIST_SFX_CHECK(L), &(L)->list_nilnode)
145 #if defined(LIST_IMPLEMENTATION) || !defined(KAZLIB_OPAQUE_DEBUG)
146 #define list_append(L, N) list_ins_before(LIST_SFX_CHECK(L), N, &(L)->list_nilnode)
147 #define list_prepend(L, N) list_ins_after(LIST_SFX_CHECK(L), N, &(L)->list_nilnode)
148 #define list_del_first(L) list_delete(LIST_SFX_CHECK(L), list_first(L))
149 #define list_del_last(L) list_delete(LIST_SFX_CHECK(L), list_last(L))
152 /* destination list on the left, source on the right */
154 CP_HIDDEN void list_extract(list_t *, list_t *, lnode_t *, lnode_t *);
155 CP_HIDDEN void list_transfer(list_t *, list_t *, lnode_t *first);
156 CP_HIDDEN void list_merge(list_t *, list_t *, int (const void *, const void *));
157 CP_HIDDEN void list_sort(list_t *, int (const void *, const void *));
158 CP_HIDDEN lnode_t *list_find(list_t *, const void *, int (const void *, const void *));
159 CP_HIDDEN int list_is_sorted(list_t *, int (const void *, const void *));