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