1.\" $NetBSD: gcq.3,v 1.3 2009/05/27 19:23:28 wiz Exp $ 2.\" 3.\" Not (c) 2007 Matthew Orgass 4.\" This file is public domain, meaning anyone can make any use of part or all 5.\" of this file including copying into other works without credit. Any use, 6.\" modified or not, is solely the responsibility of the user. If this file 7.\" is part of a collection then use in the collection is governed by the 8.\" terms of the collection. 9.\" 10.Dd May 1, 2007 11.Dt GCQ 3 12.Os 13.Sh NAME 14.Nm GCQ_INIT , 15.Nm GCQ_INIT_HEAD , 16.Nm gcq_init , 17.Nm gcq_init_head , 18.Nm gcq_q , 19.Nm gcq_hq , 20.Nm gcq_head , 21.Nm gcq_remove , 22.Nm gcq_onlist , 23.Nm gcq_empty , 24.Nm gcq_linked , 25.Nm gcq_insert_after , 26.Nm gcq_insert_before , 27.Nm gcq_insert_head , 28.Nm gcq_insert_tail , 29.Nm gcq_tie , 30.Nm gcq_tie_after , 31.Nm gcq_tie_before , 32.Nm gcq_merge , 33.Nm gcq_merge_head , 34.Nm gcq_merge_tail , 35.Nm gcq_clear , 36.Nm gcq_remove_all , 37.Nm GCQ_ITEM , 38.Nm GCQ_GOT_FIRST , 39.Nm GCQ_GOT_LAST , 40.Nm GCQ_GOT_NEXT , 41.Nm GCQ_GOT_PREV , 42.Nm GCQ_DEQUEUED_FIRST , 43.Nm GCQ_DEQUEUED_LAST , 44.Nm GCQ_DEQUEUED_NEXT , 45.Nm GCQ_DEQUEUED_PREV , 46.Nm GCQ_GOT_FIRST_TYPED , 47.Nm GCQ_GOT_LAST_TYPED , 48.Nm GCQ_GOT_NEXT_TYPED , 49.Nm GCQ_GOT_PREV_TYPED , 50.Nm GCQ_DEQUEUED_FIRST_TYPED , 51.Nm GCQ_DEQUEUED_LAST_TYPED , 52.Nm GCQ_DEQUEUED_NEXT_TYPED , 53.Nm GCQ_DEQUEUED_PREV_TYPED , 54.Nm GCQ_GOT_FIRST_COND , 55.Nm GCQ_GOT_LAST_COND , 56.Nm GCQ_GOT_NEXT_COND , 57.Nm GCQ_GOT_PREV_COND , 58.Nm GCQ_DEQUEUED_FIRST_COND , 59.Nm GCQ_DEQUEUED_LAST_COND , 60.Nm GCQ_DEQUEUED_NEXT_COND , 61.Nm GCQ_DEQUEUED_PREV_COND , 62.Nm GCQ_GOT_FIRST_COND_TYPED , 63.Nm GCQ_GOT_LAST_COND_TYPED , 64.Nm GCQ_GOT_NEXT_COND_TYPED , 65.Nm GCQ_GOT_PREV_COND_TYPED , 66.Nm GCQ_DEQUEUED_FIRST_COND_TYPED , 67.Nm GCQ_DEQUEUED_LAST_COND_TYPED , 68.Nm GCQ_DEQUEUED_NEXT_COND_TYPED , 69.Nm GCQ_DEQUEUED_PREV_COND_TYPED , 70.Nm GCQ_FOREACH , 71.Nm GCQ_FOREACH_REV , 72.Nm GCQ_FOREACH_NVAR , 73.Nm GCQ_FOREACH_NVAR_REV , 74.Nm GCQ_FOREACH_RO , 75.Nm GCQ_FOREACH_RO_REV , 76.Nm GCQ_FOREACH_DEQUEUED , 77.Nm GCQ_FOREACH_DEQUEUED_REV , 78.Nm GCQ_FOREACH_TYPED , 79.Nm GCQ_FOREACH_REV_TYPED , 80.Nm GCQ_FOREACH_NVAR_TYPED , 81.Nm GCQ_FOREACH_NVAR_REV_TYPED , 82.Nm GCQ_FOREACH_RO_TYPED , 83.Nm GCQ_FOREACH_RO_REV_TYPED , 84.Nm GCQ_FOREACH_DEQUEUED_TYPED , 85.Nm GCQ_FOREACH_DEQUEUED_REV_TYPED , 86.Nm GCQ_FIND , 87.Nm GCQ_FIND_REV , 88.Nm GCQ_FIND_TYPED , 89.Nm GCQ_FIND_REV_TYPED 90.Nd "Generic Circular Queues" 91.Sh SYNOPSIS 92.In sys/gcq.h 93.Pp 94.Vt struct gcq ; 95.Vt struct gcq_head ; 96.Pp 97.Fn GCQ_INIT name 98.Fn GCQ_INIT_HEAD name 99.Pp 100.Ft static inline void 101.Fn gcq_init "struct gcq *q" 102.Ft static inline void 103.Fn gcq_init_head "struct gcq_head *head" 104.Ft static inline struct gcq * 105.Fn gcq_q "struct gcq_head *head" 106.Ft static inline struct gcq * 107.Fn gcq_hq "struct gcq_head *head" 108.Ft static inline struct gcq_head * 109.Fn gcq_head "struct gcq *q" 110.Ft static inline struct gcq * 111.Fn gcq_remove "struct gcq *q" 112.Ft static inline bool 113.Fn gcq_onlist "struct gcq *q" 114.Ft static inline bool 115.Fn gcq_empty "struct gcq_head *head" 116.Ft static inline bool 117.Fn gcq_linked "struct gcq *prev" "struct gcq *next" 118.Ft static inline void 119.Fn gcq_insert_after "struct gcq *on" "struct gcq *off" 120.Ft static inline void 121.Fn gcq_insert_before "struct gcq *on" "struct gcq *off" 122.Ft static inline void 123.Fn gcq_insert_head "struct gcq_head *head" "struct gcq *q" 124.Ft static inline void 125.Fn gcq_insert_tail "struct gcq_head *head" "struct gcq *q" 126.Ft static inline void 127.Fn gcq_tie "struct gcq *dst" "struct gcq *src" 128.Ft static inline void 129.Fn gcq_tie_after "struct gcq *dst" "struct gcq *src" 130.Ft static inline void 131.Fn gcq_tie_before "struct gcq *dst" "struct gcq *src" 132.Ft static inline void 133.Fn gcq_merge "struct gcq *dst" "struct gcq *src" 134.Ft static inline void 135.Fn gcq_merge_tail "struct gcq_head *dst" "struct gcq_head *src" 136.Ft static inline void 137.Fn gcq_merge_head "struct gcq_head *dst" "struct gcq_head *src" 138.Ft static inline void 139.Fn gcq_clear "struct gcq *q" 140.Ft static inline void 141.Fn gcq_remove_all "struct gcq_head *head" 142.Pp 143.Ft type * 144.Fn GCQ_ITEM q type name 145.Ft bool 146.Fn GCQ_GOT_FIRST var head 147.Ft bool 148.Fn GCQ_GOT_LAST var head 149.Ft bool 150.Fn GCQ_GOT_NEXT var current head start 151.Ft bool 152.Fn GCQ_GOT_PREV var current head start 153.Ft bool 154.Fn GCQ_DEQUEUED_FIRST var head 155.Ft bool 156.Fn GCQ_DEQUEUED_LAST var head 157.Ft bool 158.Fn GCQ_DEQUEUED_NEXT var current head start 159.Ft bool 160.Fn GCQ_DEQUEUED_PREV var current head start 161.Ft bool 162.Fn GCQ_GOT_FIRST_TYPED tvar head type name 163.Ft bool 164.Fn GCQ_GOT_LAST_TYPED tvar head type name 165.Ft bool 166.Fn GCQ_GOT_NEXT_TYPED tvar current head start type name 167.Ft bool 168.Fn GCQ_GOT_PREV_TYPED tvar current head start type name 169.Ft bool 170.Fn GCQ_DEQUEUED_FIRST_TYPED tvar head type name 171.Ft bool 172.Fn GCQ_DEQUEUED_LAST_TYPED tvar head type name 173.Ft bool 174.Fn GCQ_DEQUEUED_NEXT_TYPED tvar current head start type name 175.Ft bool 176.Fn GCQ_DEQUEUED_PREV_TYPED tvar current head start type name 177.Ft bool 178.Fn GCQ_GOT_FIRST_COND var head cond 179.Ft bool 180.Fn GCQ_GOT_LAST_COND var head cond 181.Ft bool 182.Fn GCQ_GOT_NEXT_COND var current head start cond 183.Ft bool 184.Fn GCQ_GOT_PREV_COND var current head start cond 185.Ft bool 186.Fn GCQ_DEQUEUED_FIRST_COND var head cond 187.Ft bool 188.Fn GCQ_DEQUEUED_LAST_COND var head cond 189.Ft bool 190.Fn GCQ_DEQUEUED_NEXT_COND var current head start cond 191.Ft bool 192.Fn GCQ_DEQUEUED_PREV_COND var current head start cond 193.Ft bool 194.Fn GCQ_GOT_FIRST_COND_TYPED tvar head type name cond 195.Ft bool 196.Fn GCQ_GOT_LAST_COND_TYPED tvar head type name cond 197.Ft bool 198.Fn GCQ_GOT_NEXT_COND_TYPED tvar current head start type name cond 199.Ft bool 200.Fn GCQ_GOT_PREV_COND_TYPED tvar current head start type name cond 201.Ft bool 202.Fn GCQ_DEQUEUED_FIRST_COND_TYPED tvar head type name cond 203.Ft bool 204.Fn GCQ_DEQUEUED_LAST_COND_TYPED tvar head type name cond 205.Ft bool 206.Fn GCQ_DEQUEUED_NEXT_COND_TYPED tvar current head start type name cond 207.Ft bool 208.Fn GCQ_DEQUEUED_PREV_COND_TYPED tvar current head start type name cond 209.Fn GCQ_FOREACH var head 210.Fn GCQ_FOREACH_REV var head 211.Fn GCQ_FOREACH_NVAR var nvar head 212.Fn GCQ_FOREACH_NVAR_REV var nvar head 213.Fn GCQ_FOREACH_RO var nvar head 214.Fn GCQ_FOREACH_RO_REV var nvar head 215.Fn GCQ_FOREACH_DEQUEUED var nvar head 216.Fn GCQ_FOREACH_DEQUEUED_REV var nvar head 217.Fn GCQ_FOREACH_TYPED var head tvar type name 218.Fn GCQ_FOREACH_REV_TYPED var head tvar type name 219.Fn GCQ_FOREACH_NVAR_TYPED var nvar head tvar type name 220.Fn GCQ_FOREACH_NVAR_REV_TYPED var nvar head tvar type name 221.Fn GCQ_FOREACH_RO_TYPED var nvar head tvar type name 222.Fn GCQ_FOREACH_RO_REV_TYPED var nvar head tvar type name 223.Fn GCQ_FOREACH_DEQUEUED_TYPED var nvar head tvar type name 224.Fn GCQ_FOREACH_DEQUEUED_REV_TYPED var nvar head tvar type name 225.Fn GCQ_FIND var head cond 226.Fn GCQ_FIND_REV var head cond 227.Fn GCQ_FIND_TYPED var head tvar type name cond 228.Fn GCQ_FIND_REV_TYPED var head tvar type name cond 229.Fn GCQ_ASSERT cond 230.Sh DESCRIPTION 231The generic circular queue is a doubly linked list designed for efficient 232merge operations and unconditional removal. 233All basic operations can be performed with or without use of a separate head, 234allowing easy replacement of any pointers where efficient removal is desired. 235The meaning of the data type will not change; direct use and defined 236operations can be mixed when convenient. 237The basic type is: 238.Bd -literal -offset indent 239struct gcq { 240 struct gcq *q_next; 241 struct gcq *q_prev; 242}; 243.Ed 244.Pp 245The structure must first be initialized such that the 246.Va q_next 247and 248.Va q_prev 249members point to the beginning of the 250.Vt struct gcq . 251This can be done with 252.Fn gcq_init 253and 254.Fn gcq_init_head 255or with constant initializers 256.Fn GCQ_INIT 257and 258.Fn GCQ_INIT_HEAD . 259A 260.Vt struct gcq 261should 262.Em never 263be given 264.Dv NULL 265values. 266.Pp 267The structure containing the 268.Vt struct gcq 269can be retrieved by pointer arithmetic in the 270.Fn GCQ_ITEM 271macro. 272List traversal normally requires knowledge of the list head to safely 273retrieve list items. 274.Pp 275Capitalized operation names are macros and should be assumed to cause multiple 276evaluation of arguments. 277.Li TYPED 278variants of macros set a typed pointer variable instead of or in addition to 279.Vt struct gcq * 280arguments. 281Additional type specific inlines and macros around some GCQ operations can be 282useful. 283.Pp 284A few assertions are provided when 285.Dv DIAGNOSTIC 286is defined in the kernel or 287.Dv _DIAGNOSTIC 288is defined in userland. 289If 290.Dv GCQ_USE_ASSERT 291is defined prior to header inclusions 292then 293.Fn assert 294will be used for assertions and 295.Dv NDEBUG 296can be used to turn them off. 297.Fn GCQ_ASSERT 298is a wrapper around the used assertion function. 299None of the operations accept 300.Dv NULL 301arguments, however this is not tested by assertion. 302.Pp 303The head is separately named for type checking but contains only a 304.Vt struct gcq , 305a pointer to which can be retrieved via 306.Fn gcq_hq . 307The reverse operation is performed by 308.Fn gcq_head , 309turning the supplied 310.Vt struct gcq * 311into 312.Vt struct gcq_head * . 313.Fn gcq_q 314returns its 315.Vt struct gcq * 316argument and is used for type checking in 317.Fn GCQ_ITEM . 318There are no functions for retrieving the raw 319.Va q_prev 320and 321.Va q_next 322pointers as these are usually clearer when used directly (if at all). 323.Pp 324.Fn gcq_remove 325returns the element removed and is always a valid operation after 326initialization. 327.Fn gcq_onlist 328returns 329.Dv false 330if the structure links to itself and 331.Dv true 332otherwise. 333.Fn gcq_empty 334is the negation of this operation performed on a head. 335.Fn gcq_linked 336tests if 337.Li "prev-\*[Gt]q_next == next \*[Am]\*[Am] next-\*[Gt]q_prev == prev" . 338.Pp 339.Fn gcq_tie 340ties 341.Va src 342after 343.Va dst 344such that that if the old lists are DST, DST2 and SRC, SRC2, the new list is 345DST, SRC, SRC2, DST2. 346If 347.Va dst 348and 349.Va src 350are on the same list then any elements between but not including 351.Va dst 352and 353.Va src 354are cut from the list. 355If 356.Li dst == src 357then the result is the same as 358.Fn gcq_remove . 359.Fn gcq_tie 360is equivalent to 361.Fn gcq_tie_after 362except that the latter must only be used with arguments on separate lists or 363not on lists and asserts that 364.Li "src != dst \*[Am]\*[Am] dst-\*[Gt]q_prev != src" . 365.Fn gcq_tie_before 366performs the same operation on 367.Li dst-\*[Gt]q_prev . 368.Pp 369.Fn gcq_merge 370moves any elements on list 371.Va src 372(but not 373.Va src 374itself) to list 375.Va dst . 376It is normally used with two heads via 377.Fn gcq_merge_head 378or 379.Fn gcq_merge_tail . 380If 381.Dv GCQ_UNCONDITIONAL_MERGE 382is defined prior to header inclusion then the merge operations will always 383perform a tie then remove 384.Va src 385from the new list, which may reduce code size slightly. 386.Pp 387.Fn gcq_clear 388initializes all elements currently linked with 389.Va q 390and is normally used with a head as 391.Fn gcq_remove_all . 392.Pp 393.Fn gcq_insert_after 394and 395.Fn gcq_insert_before 396are slightly optimized versions of 397.Fn gcq_tie 398for the case where 399.Va off 400is not on a list and include assertions to this effect, which are also useful 401to detect missing initialization. 402.Fn gcq_insert_head 403and 404.Fn gcq_insert_tail 405are the same operations applied to a head. 406.Pp 407.Fn GCQ_GOT_FIRST 408and 409.Fn GCQ_GOT_LAST 410set 411.Va var 412to a pointer to the first or last 413.Vt struct gcq 414in the list 415or 416.Dv NULL 417if the list is empty and return 418.Dv false 419if empty and 420.Dv true 421otherwise. 422The boolean return is to emphasise that it is not normally safe and useful to 423directly pass the raw first/next/etc. pointer to another function. 424The macros are written such that the 425.Dv NULL 426values will be optimized out if not otherwise used. 427.Li DEQUEUED 428variants also remove the member from the list. 429.Li COND 430variants take an additional condition that is evaluated when the macro would 431otherwise return 432.Dv true . 433If the condition is false 434.Va var 435or 436.Va tvar 437is set to 438.Dv NULL 439and no dequeue is performed. 440.Pp 441.Fn GCQ_GOT_NEXT 442and variants take pointers to the current position, list head, and starting 443point as arguments. 444The list head will be skipped when it is reached unless it is equal to the 445starting point; upon reaching the starting point 446.Va var 447will be set to 448.Dv NULL 449and the macro will return 450.Dv false . 451The next and prev macros also assert that 452.Va current 453is on the list unless it is equal to 454.Va start . 455These macros are the only provided method for iterating through the list from 456an arbitrary point. 457Traversal macros are only provided for list heads, however 458.Fn gcq_head 459can be used to treat any item as a head. 460.Pp 461Foreach variants contain an embedded 462.Li for 463statement for iterating over a list. 464Those containing 465.Li REV 466use the 467.Va q_prev 468pointer for traversal, others use 469.Va q_next . 470The plain 471.Fn GCQ_FOREACH 472uses a single variable. 473.Li NVAR 474variants save the next pointer at the top of the loop so that the current 475element can be removed without adjusting 476.Va var . 477This is useful when 478.Va var 479is passed to a function that might remove it but will not otherwise modify 480the list. 481When the head is reached both 482.Va var 483and 484.Va nvar 485elements are left pointing to the list head. 486.Li FOREACH 487asserts that 488.Va var , 489and 490.Li NVAR 491asserts that 492.Va nvar 493does not point to itself when starting the next loop. 494This assertion takes place after the variable is tested against the head so 495it is safe to remove all elements from the list. 496.Li RO 497variants also set 498.Va nvar 499but assert that the two variables are linked at the end of each iteration. 500This is useful when calling a function that is not supposed to remove the 501element passed. 502.Li DEQUEUED 503variants are like 504.Li NVAR 505but remove each element before the code block is executed. 506.Li TYPED 507variants are equivalent to the untyped versions except that they take three 508extra arguments: a typed pointer, the type name, and the member name of the 509.Vt struct gcq 510used in this list. 511.Va tvar 512is set to 513.Dv NULL 514when the head is reached. 515.Pp 516.Fn GCQ_FIND 517is a foreach loop that does nothing except break when the supplied condition 518is true. 519.Li REV 520and 521.Li TYPED 522variants are available. 523.\" .Sh EXAMPLES 524.Sh SEE ALSO 525.Xr gcc 1 , 526.Xr _DIAGASSERT 3 , 527.Xr assert 3 , 528.Xr queue 3 , 529.Xr KASSERT 9 530.Sh HISTORY 531GCQ appeared in 532.Nx 5.0 . 533