1 /*===========================================================================
2 *
3 *                            PUBLIC DOMAIN NOTICE
4 *               National Center for Biotechnology Information
5 *
6 *  This software/database is a "United States Government Work" under the
7 *  terms of the United States Copyright Act.  It was written as part of
8 *  the author's official duties as a United States Government employee and
9 *  thus cannot be copyrighted.  This software/database is freely available
10 *  to the public for use. The National Library of Medicine and the U.S.
11 *  Government have not placed any restriction on its use or reproduction.
12 *
13 *  Although all reasonable efforts have been taken to ensure the accuracy
14 *  and reliability of the software and data, the NLM and the U.S.
15 *  Government do not and cannot warrant the performance or results that
16 *  may be obtained by using this software or data. The NLM and the U.S.
17 *  Government disclaim all warranties, express or implied, including
18 *  warranties of performance, merchantability or fitness for any particular
19 *  purpose.
20 *
21 *  Please cite the author in any work or product based on this material.
22 *
23 * ===========================================================================
24 *
25 */
26 
27 #ifndef _h_klib_container_
28 #define _h_klib_container_
29 
30 #ifndef _h_klib_extern_
31 #include <klib/extern.h>
32 #endif
33 
34 #ifndef _h_klib_defs_
35 #include <klib/defs.h>
36 #endif
37 
38 #ifdef __cplusplus
39 extern "C" {
40 #endif
41 
42 
43 /*--------------------------------------------------------------------------
44  * SLNode
45  *  singly linked node
46  */
47 typedef struct SLNode SLNode;
48 struct SLNode
49 {
50     SLNode *next;
51 };
52 
53 /* SLNodeNext
54  *  returns next node
55  */
56 #define SLNodeNext( n ) \
57     ( n ) -> next
58 
59 #if 0
60 /* SLNodeFindNext
61  *  find next element satisfying criteria
62  */
63 KLIB_EXTERN SLNode* CC SLNodeFindNext ( const SLNode *n, bool ( CC * f ) ( const SLNode *n ) );
64 #endif
65 
66 
67 /*--------------------------------------------------------------------------
68  * SLList
69  *  singly linked list
70  */
71 typedef struct SLList SLList;
72 struct SLList
73 {
74     SLNode *head;
75     SLNode *tail;
76 };
77 
78 
79 /* SLListInit
80  *  initialize a singly linked list
81  */
82 #define SLListInit( sl ) \
83     ( void ) ( ( sl ) -> head = ( sl ) -> tail = NULL )
84 
85 /* SLListHead
86  *  returns list head
87  */
88 #define SLListHead( sl ) \
89     ( sl ) -> head
90 
91 /* SLListTail
92  *  returns list tail
93  */
94 #define SLListTail( sl ) \
95     ( sl ) -> tail
96 
97 /* SLListPushHead
98  *  push a single node onto head of list
99  */
100 #define SLListPushHead( sl, n ) \
101     ( void ) ( ( ( sl ) -> tail == NULL ? \
102         ( void ) ( ( sl ) -> tail = ( n ) ) : ( void ) 0 ), \
103         ( n ) -> next = ( sl ) -> head, ( sl ) -> head = ( n ) )
104 
105 /* SLListPushTail
106  *  push a single node onto tail of list
107  */
108 KLIB_EXTERN void CC SLListPushTail ( SLList *sl, SLNode *n );
109 
110 /* SLListPopHead
111  *  pop a single node from head of list
112  */
113 KLIB_EXTERN SLNode* CC SLListPopHead ( SLList *sl );
114 
115 /* SLListPopTail
116  *  pop a single node from tail of list
117  */
118 KLIB_EXTERN SLNode* CC SLListPopTail ( SLList *sl );
119 
120 /* SLListUnlink
121  *  removes a designated node from list
122  */
123 KLIB_EXTERN void CC SLListUnlink ( SLList *sl, SLNode *n );
124 
125 /* SLListForEach
126  *  executes a function on each list element
127  */
128 KLIB_EXTERN void CC SLListForEach ( const SLList *sl,
129     void ( CC * f ) ( SLNode *n, void *data ), void *data );
130 
131 /* SLListDoUntil
132  *  executes a function on each element
133  *  until the function returns true
134  */
135 KLIB_EXTERN bool CC SLListDoUntil ( const SLList *sl,
136     bool ( CC * f ) ( SLNode *n, void *data ), void *data );
137 
138 /* SLListFindFirst
139  *  find first element satisfying criteria
140  */
141 KLIB_EXTERN SLNode* CC SLListFindFirst ( const SLList *sl, bool ( CC * f ) ( const SLNode *n ) );
142 
143 /* SLListWhack
144  *  pops elements from list and
145  *  executes a user provided destructor
146  */
147 KLIB_EXTERN void CC SLListWhack ( SLList *sl, void ( CC * whack ) ( SLNode *n, void *data ), void *data );
148 
149 
150 /*--------------------------------------------------------------------------
151  * DLNode
152  *  doubly linked node
153  */
154 typedef struct DLNode DLNode;
155 struct DLNode
156 {
157     DLNode *next;
158     DLNode *prev;
159 };
160 
161 /* DLNodeNext
162  *  returns next node
163  */
164 #define DLNodeNext( n ) \
165     ( n ) -> next
166 
167 /* DLNodePrev
168  *  returns prev node
169  */
170 #define DLNodePrev( n ) \
171     ( n ) -> prev
172 
173 #if 0
174 /* DLNodeFindNext
175  *  find next element satisfying criteria
176  */
177 KLIB_EXTERN DLNode* CC DLNodeFindNext ( const DLNode *n, bool ( CC * f ) ( const DLNode *n ) );
178 
179 /* DLNodeFindPrev
180  *  find previous element satisfying criteria
181  */
182 KLIB_EXTERN DLNode* CC DLNodeFindPrev ( const DLNode *n, bool ( CC * f ) ( const DLNode *n ) );
183 #endif
184 
185 /*--------------------------------------------------------------------------
186  * DLList
187  *  doubly linked list
188  */
189 typedef struct DLList DLList;
190 struct DLList
191 {
192     DLNode *head;
193     DLNode *tail;
194 };
195 
196 /* DLListInit
197  *  initialize a doubly linked list
198  */
199 #define DLListInit( dl ) \
200     ( void ) ( ( dl ) -> head = ( dl ) -> tail = NULL )
201 
202 /* DLListHead
203  *  returns list head
204  */
205 #define DLListHead( dl ) \
206     ( dl ) -> head
207 
208 /* DLListTail
209  *  returns list tail
210  */
211 #define DLListTail( dl ) \
212     ( dl ) -> tail
213 
214 /* DLListPushHead
215  *  push a single node onto the head of list
216  */
217 KLIB_EXTERN void CC DLListPushHead ( DLList *dl, DLNode *n );
218 
219 /* DLListPushTail
220  *  push a single node onto the tail of list
221  */
222 KLIB_EXTERN void CC DLListPushTail ( DLList *dl, DLNode *n );
223 
224 /* DLListPopHead
225  *  pop a single node from head of list
226  */
227 KLIB_EXTERN DLNode* CC DLListPopHead ( DLList *dl );
228 
229 /* DLListPopTail
230  *  pop a single node from tail of list
231  */
232 KLIB_EXTERN DLNode* CC DLListPopTail ( DLList *dl );
233 
234 /* DLListPrependList
235  *  pushes list contents onto the head of target
236  */
237 KLIB_EXTERN void CC DLListPrependList ( DLList *dl, DLList *l );
238 
239 /* DLListAppendList
240  *  pushes list contents onto the tail of target
241  */
242 KLIB_EXTERN void CC DLListAppendList ( DLList *dl, DLList *l );
243 
244 /* DLListInsertNodeBefore
245  *  inserts node "n" before "which" within list
246  */
247 KLIB_EXTERN void CC DLListInsertNodeBefore ( DLList *dl, DLNode *which, DLNode *n );
248 
249 /* DLListInsertNodeAfter
250  *  inserts node "n" after "which" within list
251  */
252 KLIB_EXTERN void CC DLListInsertNodeAfter ( DLList *dl, DLNode *which, DLNode *n );
253 
254 /* DLListInsertListBefore
255  *  inserts list "l" before "which" within list "dl"
256  */
257 KLIB_EXTERN void CC DLListInsertListBefore ( DLList *dl, DLNode *which, DLList *l );
258 
259 /* DLListInsertListAfter
260  *  inserts list "l" after "which" within list "dl"
261  */
262 KLIB_EXTERN void CC DLListInsertListAfter ( DLList *dl, DLNode *which, DLList *l );
263 
264 /* DLListUnlink
265  *  removes a designated node from list
266  */
267 KLIB_EXTERN void CC DLListUnlink ( DLList *dl, DLNode *n );
268 
269 /* DLListForEach
270  *  executes a function on each list element
271  */
272 KLIB_EXTERN void CC DLListForEach ( const DLList *dl, bool reverse,
273     void ( CC * f ) ( DLNode *n, void *data ), void *data );
274 
275 /* DLListDoUntil
276  *  executes a function on each element
277  *  until the function returns true
278  */
279 KLIB_EXTERN bool CC DLListDoUntil ( const DLList *dl, bool reverse,
280     bool ( CC * f ) ( DLNode *n, void *data ), void *data );
281 
282 /* DLListFindFirst
283  *  find first element satisfying criteria
284  */
285 KLIB_EXTERN DLNode* CC DLListFindFirst ( const DLList *dl, bool ( CC * f ) ( const DLNode *n ) );
286 
287 /* DLListFindLast
288  *  find last element satisfying criteria
289  */
290 KLIB_EXTERN DLNode* CC DLListFindLast ( const DLList *dl, bool ( CC * f ) ( const DLNode *n ) );
291 
292 /* DLListWhack
293  *  pops elements from list and
294  *  executes a user provided destructor
295  */
296 KLIB_EXTERN void CC DLListWhack ( DLList *dl, void ( CC * whack ) ( DLNode *n, void *data ), void *data );
297 
298 
299 /*--------------------------------------------------------------------------
300  * BSTNode
301  *  binary search tree node
302  */
303 typedef struct BSTNode BSTNode;
304 struct BSTNode
305 {
306     BSTNode *par;
307     BSTNode *child [ 2 ];
308 };
309 
310 /* BSTNodeNext
311  *  returns next node
312  */
313 KLIB_EXTERN BSTNode* CC BSTNodeNext ( const BSTNode *n );
314 
315 /* BSTNodePrev
316  *  returns prev node
317  */
318 KLIB_EXTERN BSTNode* CC BSTNodePrev ( const BSTNode *n );
319 
320 /* BSTNodeParent
321  *  returns a parent node if there, NULL otherwise
322  */
323 KLIB_EXTERN BSTNode* CC BSTNodeParent ( const BSTNode *n );
324 
325 /* BSTNodeFindNext
326  *  find next element satisfying criteria
327  */
328 KLIB_EXTERN BSTNode* CC BSTNodeFindNext ( const BSTNode *n, bool ( CC * f ) ( const BSTNode *n ) );
329 
330 /* BSTNodeFindPrev
331  *  find previous element satisfying criteria
332  */
333 KLIB_EXTERN BSTNode* CC BSTNodeFindPrev ( const BSTNode *n, bool ( CC * f ) ( const BSTNode *n ) );
334 
335 
336 /*--------------------------------------------------------------------------
337  * BSTree
338  *  binary search tree
339  */
340 typedef struct BSTree BSTree;
341 struct BSTree
342 {
343     BSTNode *root;
344 };
345 
346 /* BSTreeInit
347  *  initialize tree
348  */
349 #define BSTreeInit( bt ) \
350     ( void ) ( ( bt ) -> root = NULL )
351 
352 /* BSTreeDepth
353  *  returns number of layers in tree
354  *
355  *  if "exact" is true, then the maximum
356  *  depth is returned. otherwise, the depth of
357  *  an arbitrary leaf node is returned
358  */
359 KLIB_EXTERN uint32_t CC BSTreeDepth ( const BSTree *bt, bool exact );
360 
361 /* BSTreeFirst
362  *  returns first node
363  */
364 KLIB_EXTERN BSTNode* CC BSTreeFirst ( const BSTree *bt );
365 
366 /* BSTreeLast
367  *  returns last node
368  */
369 KLIB_EXTERN BSTNode* CC BSTreeLast ( const BSTree *bt );
370 
371 /* BSTreeFind
372  *  find an object within tree
373  *  "cmp" function returns equivalent of "item" - "n"
374  */
375 KLIB_EXTERN BSTNode* CC BSTreeFind ( const BSTree *bt, const void *item,
376     int64_t ( CC * cmp ) ( const void *item, const BSTNode *n ) );
377 
378 /* BSTreeInsert
379  *  insert an object within tree, even if duplicate
380  *  "sort" function returns equivalent of "item" - "n"
381  *
382  *  the treatment of order for items reported as identical
383  *  i.e. sort function returns zero when they are compared,
384  *  is undefined.
385  *
386  *  the current implementation treats '<=' as '<' such
387  *  that all inserts are converted to a '<' or '>' comparison,
388  *  but this should not be relied upon.
389  *
390  *  returns 0 if insert succeeded or an OS error code otherwise.
391  */
392 KLIB_EXTERN rc_t CC BSTreeInsert ( BSTree *bt, BSTNode *item,
393     int64_t ( CC * sort ) ( const BSTNode *item, const BSTNode *n ) );
394 
395 /* BSTreeInsertUnique
396  *  insert an object within tree, but only if unique.
397  *  "sort" function returns equivalent of "item" - "n"
398  *
399  *  returns 0 if insertion succeeded. or an OS error code otherwise.
400  *  if error code is EEXIST, the existing object is returned in "exist".
401  */
402 KLIB_EXTERN rc_t CC BSTreeInsertUnique ( BSTree *bt, BSTNode *item, BSTNode **exist,
403     int64_t ( CC * sort ) ( const BSTNode *item, const BSTNode *n ) );
404 
405 /* BSTreeResort
406  *  an optimized removal and re-insertion of
407  *  all contained elements using another function
408  *
409  *  the treatment of order for items reported as identical
410  *  i.e. sort function returns zero when they are compared,
411  *  is undefined.
412  *
413  *  the current implementation treats '<=' as '<' such
414  *  that all inserts are converted to a '<' or '>' comparison,
415  *  but this should not be relied upon.
416  */
417 KLIB_EXTERN void CC BSTreeResort ( BSTree *bt,
418     int64_t ( CC * resort ) ( const BSTNode *item, const BSTNode *n ) );
419 
420 /* BSTreeUnlink
421  *  removes a node from tree
422  *
423  *  returns true if node was removed from tree
424  *  false if it could not be removed, e.g. was not in tree
425  */
426 KLIB_EXTERN bool CC BSTreeUnlink ( BSTree *bt, BSTNode *n );
427 
428 /* BSTreeForEach
429  *  executes a function on each tree element
430  */
431 KLIB_EXTERN void CC BSTreeForEach ( const BSTree *bt, bool reverse,
432     void ( CC * f ) ( BSTNode *n, void *data ), void *data );
433 
434 /* BSTreeDoUntil
435  *  executes a function on each element
436  *  until the function returns true
437  *
438  *  return values:
439  *    false unless the function returns true
440  */
441 KLIB_EXTERN bool CC BSTreeDoUntil ( const BSTree *bt, bool reverse,
442     bool ( CC * f ) ( BSTNode *n, void *data ), void *data );
443 
444 /* BSTreeWhack
445  *  removes nodes from tree and
446  *  executes a user provided destructor
447  */
448 KLIB_EXTERN void CC BSTreeWhack ( BSTree *bt, void ( CC * whack ) ( BSTNode *n, void *data ), void *data );
449 
450 
451 #ifdef __cplusplus
452 }
453 #endif
454 
455 #endif /* _h_klib_container_ */
456