GCQ(3)

📦 version 11.0, in nixpkgs unstable

🎀 GCQ(3) — Generic Circular Queues 🎀

okay so bestie, welcome to GCQ(3) 💖 straight out of the Library Functions Manual, and ngl this one is a whole situation — generic circular queues, the entire header, every macro, no crumbs left behind.

this is part 1 of 2, so don't panic when the page just… ends mid-lore. we're doing NAME and SYNOPSIS here, and the rest is coming. stay with me. 🫶

✨ NAME ✨

okay so every single one of these is the same page — one big happy family, one guest list for the most iconic party in the header file. read it like a call sheet:

  • GCQ_INIT, GCQ_INIT_HEAD, gcq_init, gcq_init_head
  • gcq_q, gcq_hq, gcq_head
  • gcq_remove, gcq_onlist, gcq_empty, gcq_linked
  • gcq_insert_after, gcq_insert_before, gcq_insert_head, gcq_insert_tail
  • gcq_tie, gcq_tie_after, gcq_tie_before
  • gcq_merge, gcq_merge_head, gcq_merge_tail
  • gcq_clear, gcq_remove_all
  • GCQ_ITEM
  • GCQ_GOT_FIRST, GCQ_GOT_LAST, GCQ_GOT_NEXT, GCQ_GOT_PREV
  • GCQ_DEQUEUED_FIRST, GCQ_DEQUEUED_LAST, GCQ_DEQUEUED_NEXT, GCQ_DEQUEUED_PREV
  • GCQ_GOT_FIRST_TYPED, GCQ_GOT_LAST_TYPED, GCQ_GOT_NEXT_TYPED, GCQ_GOT_PREV_TYPED
  • GCQ_DEQUEUED_FIRST_TYPED, GCQ_DEQUEUED_LAST_TYPED, GCQ_DEQUEUED_NEXT_TYPED, GCQ_DEQUEUED_PREV_TYPED
  • GCQ_GOT_FIRST_COND, GCQ_GOT_LAST_COND, GCQ_GOT_NEXT_COND, GCQ_GOT_PREV_COND
  • GCQ_DEQUEUED_FIRST_COND, GCQ_DEQUEUED_LAST_COND, GCQ_DEQUEUED_NEXT_COND, GCQ_DEQUEUED_PREV_COND
  • GCQ_GOT_FIRST_COND_TYPED, GCQ_GOT_LAST_COND_TYPED, GCQ_GOT_NEXT_COND_TYPED, GCQ_GOT_PREV_COND_TYPED
  • GCQ_DEQUEUED_FIRST_COND_TYPED, GCQ_DEQUEUED_LAST_COND_TYPED, GCQ_DEQUEUED_NEXT_COND_TYPED, GCQ_DEQUEUED_PREV_COND_TYPED
  • GCQ_FOREACH, GCQ_FOREACH_REV, GCQ_FOREACH_NVAR, GCQ_FOREACH_NVAR_REV, GCQ_FOREACH_RO, GCQ_FOREACH_RO_REV, GCQ_FOREACH_DEQUEUED, GCQ_FOREACH_DEQUEUED_REV
  • GCQ_FOREACH_TYPED, GCQ_FOREACH_REV_TYPED, GCQ_FOREACH_NVAR_TYPED, GCQ_FOREACH_NVAR_REV_TYPED, GCQ_FOREACH_RO_TYPED, GCQ_FOREACH_RO_REV_TYPED, GCQ_FOREACH_DEQUEUED_TYPED, GCQ_FOREACH_DEQUEUED_REV_TYPED
  • GCQ_FIND, GCQ_FIND_REV, GCQ_FIND_TYPED, GCQ_FIND_REV_TYPED
tiny heads up 🫶 — GCQ_ASSERT does not appear in that NAME list, but it absolutely shows up in the SYNOPSIS below. iykyk. 👀

🌸 SYNOPSIS 🌸

okay so first things first, the door you walk through 🚪 — the include and the two opaque structs:

#include <sys/gcq.h>

struct gcq;
struct gcq_head;

that's it, that's the entry point. <sys/gcq.h>, and both structs are declared for you — no peeking inside. 💅

🧚 the init girlies

GCQ_INIT(name);

GCQ_INIT_HEAD(name);

static inline void
gcq_init(struct gcq *q);

static inline void
gcq_init_head(struct gcq_head *head);

two macros that take a name, and two static inline functions that return void: gcq_init wants a struct gcq *q, gcq_init_head wants a struct gcq_head *head. all four slay. ⭐

🦋 the getters

static inline struct gcq *
gcq_q(struct gcq_head *head);

static inline struct gcq *
gcq_hq(struct gcq_head *head);

static inline struct gcq_head *
gcq_head(struct gcq *q);

look at the shapes bestie 🔍 — gcq_q and gcq_hq both take a struct gcq_head *head and hand you back a struct gcq *. then gcq_head does the lil flip: takes struct gcq *q, gives you struct gcq_head *. symmetrical, iconic, no notes. 👑

💜 state check + remove

static inline struct gcq *
gcq_remove(struct gcq *q);

static inline bool
gcq_onlist(struct gcq *q);

static inline bool
gcq_empty(struct gcq_head *head);

static inline bool
gcq_linked(struct gcq *prev, struct gcq *next);

gcq_remove takes struct gcq *q and returns a struct gcq *. the other three are all bool besties — and gcq_linked is the only one here taking two args, struct gcq *prev and struct gcq *next. 🍓

🌈 inserting (the placement era)

static inline void
gcq_insert_after(struct gcq *on, struct gcq *off);

static inline void
gcq_insert_before(struct gcq *on, struct gcq *off);

static inline void
gcq_insert_head(struct gcq_head *head, struct gcq *q);

static inline void
gcq_insert_tail(struct gcq_head *head, struct gcq *q);

all void, all static inline ✨. _after and _before take on and off; _head and _tail take a struct gcq_head *head plus a struct gcq *q. literally the whole placement squad. 🎀

🎯 tie + merge

static inline void
gcq_tie(struct gcq *dst, struct gcq *src);

static inline void
gcq_tie_after(struct gcq *dst, struct gcq *src);

static inline void
gcq_tie_before(struct gcq *dst, struct gcq *src);

three tie girlies, all void, all taking dst and src as struct gcq *. consistent queen behavior. 💅

static inline void
gcq_merge(struct gcq *dst, struct gcq *src);

static inline void
gcq_merge_tail(struct gcq_head *dst, struct gcq_head *src);

static inline void
gcq_merge_head(struct gcq_head *dst, struct gcq_head *src);

and the merges 🫶 — gcq_merge works on struct gcq *dst / struct gcq *src, while gcq_merge_tail and gcq_merge_head upgrade to struct gcq_head *dst / struct gcq_head *src. note the synopsis order is gcq_merge, gcq_merge_tail, gcq_merge_head — that's the order, don't come for me. 😭

🧹 clear

static inline void
gcq_clear(struct gcq *q);

static inline void
gcq_remove_all(struct gcq_head *head);

both void. gcq_clear takes struct gcq *q, gcq_remove_all takes struct gcq_head *head. cleanup era. 🌸

💖 GCQ_ITEM

type *
GCQ_ITEM(q, type, name);

this one returns a type * and takes three things: q, type, name. that's the whole signature, no cap. 🔥

👑 GOT / DEQUEUED (the originals)

bool
GCQ_GOT_FIRST(var, head);

bool
GCQ_GOT_LAST(var, head);

bool
GCQ_GOT_NEXT(var, current, head, start);

bool
GCQ_GOT_PREV(var, current, head, start);

bool
GCQ_DEQUEUED_FIRST(var, head);

bool
GCQ_DEQUEUED_LAST(var, head);

bool
GCQ_DEQUEUED_NEXT(var, current, head, start);

bool
GCQ_DEQUEUED_PREV(var, current, head, start);

eight of them, every single one returns bool ✅. the _FIRST and _LAST ones take var, head; the _NEXT and _PREV ones add current and start — so var, current, head, start. that's the pattern, memorize it, it comes back. 💀

🌟 GOT / DEQUEUED — TYPED

bool
GCQ_GOT_FIRST_TYPED(tvar, head, type, name);

bool
GCQ_GOT_LAST_TYPED(tvar, head, type, name);

bool
GCQ_GOT_NEXT_TYPED(tvar, current, head, start, type, name);

bool
GCQ_GOT_PREV_TYPED(tvar, current, head, start, type, name);

bool
GCQ_DEQUEUED_FIRST_TYPED(tvar, head, type, name);

bool
GCQ_DEQUEUED_LAST_TYPED(tvar, head, type, name);

bool
GCQ_DEQUEUED_NEXT_TYPED(tvar, current, head, start, type, name);

bool
GCQ_DEQUEUED_PREV_TYPED(tvar, current, head, start, type, name);

same eight, still bool, but now it's tvar instead of var and you're passing type, name on the end. the _NEXT / _PREV cuties: tvar, current, head, start, type, name. she's thorough. 🧚

🍓 GOT / DEQUEUED — COND

bool
GCQ_GOT_FIRST_COND(var, head, cond);

bool
GCQ_GOT_LAST_COND(var, head, cond);

bool
GCQ_GOT_NEXT_COND(var, current, head, start, cond);

bool
GCQ_GOT_PREV_COND(var, current, head, start, cond);

bool
GCQ_DEQUEUED_FIRST_COND(var, head, cond);

bool
GCQ_DEQUEUED_LAST_COND(var, head, cond);

bool
GCQ_DEQUEUED_NEXT_COND(var, current, head, start, cond);

bool
GCQ_DEQUEUED_PREV_COND(var, current, head, start, cond);

eight more, all bool, and now there's a cond at the end of every single argument list. _FIRST / _LAST: var, head, cond. _NEXT / _PREV: var, current, head, start, cond. cond girlies rise 🫶

🎀 GOT / DEQUEUED — COND_TYPED (the final form)

bool
GCQ_GOT_FIRST_COND_TYPED(tvar, head, type, name, cond);

bool
GCQ_GOT_LAST_COND_TYPED(tvar, head, type, name, cond);

bool
GCQ_GOT_NEXT_COND_TYPED(tvar, current, head, start, type, name, cond);

bool
GCQ_GOT_PREV_COND_TYPED(tvar, current, head, start, type, name, cond);

bool
GCQ_DEQUEUED_FIRST_COND_TYPED(tvar, head, type, name, cond);

bool
GCQ_DEQUEUED_LAST_COND_TYPED(tvar, head, type, name, cond);

bool
GCQ_DEQUEUED_NEXT_COND_TYPED(tvar, current, head, start, type, name,
    cond);

bool
GCQ_DEQUEUED_PREV_COND_TYPED(tvar, current, head, start, type, name,
    cond);

the fully loaded ones 😭 every arg from every previous batch, in one signature: tvar + type + name + cond, and the _NEXT / _PREV versions also carry current and start. still bool. still iconic. 🏆

💫 FOREACH (the family)

GCQ_FOREACH(var, head);

GCQ_FOREACH_REV(var, head);

GCQ_FOREACH_NVAR(var, nvar, head);

GCQ_FOREACH_NVAR_REV(var, nvar, head);

GCQ_FOREACH_RO(var, nvar, head);

GCQ_FOREACH_RO_REV(var, nvar, head);

GCQ_FOREACH_DEQUEUED(var, nvar, head);

GCQ_FOREACH_DEQUEUED_REV(var, nvar, head);

eight of these 🦋 — no return type listed, they're macros and they say so. the plain ones take var, head, the rest take var, nvar, head, and half of them are _REV for the reverse girlies. ⭐

🌸 FOREACH — TYPED

GCQ_FOREACH_TYPED(var, head, tvar, type, name);

GCQ_FOREACH_REV_TYPED(var, head, tvar, type, name);

GCQ_FOREACH_NVAR_TYPED(var, nvar, head, tvar, type, name);

GCQ_FOREACH_NVAR_REV_TYPED(var, nvar, head, tvar, type, name);

GCQ_FOREACH_RO_TYPED(var, nvar, head, tvar, type, name);

GCQ_FOREACH_RO_REV_TYPED(var, nvar, head, tvar, type, name);

GCQ_FOREACH_DEQUEUED_TYPED(var, nvar, head, tvar, type, name);

GCQ_FOREACH_DEQUEUED_REV_TYPED(var, nvar, head, tvar, type, name);

same eight vibes, now with tvar, type and name tagging along 💜 — _TYPED and _REV_TYPED take var, head, tvar, type, name, and everything else takes var, nvar, head, tvar, type, name. big fan of consistency honestly. 👑

🔥 FIND

GCQ_FIND(var, head, cond);

GCQ_FIND_REV(var, head, cond);

GCQ_FIND_TYPED(var, head, tvar, type, name, cond);

GCQ_FIND_REV_TYPED(var, head, tvar, type, name, cond);

the finders 🔍 — GCQ_FIND and GCQ_FIND_REV take var, head, cond; the _TYPED versions take var, head, tvar, type, name, cond. all four, all here, all accounted for. ✨

🎯 AND FINALLY

GCQ_ASSERT(cond);

yup — GCQ_ASSERT takes cond, and it's sitting right at the bottom of the synopsis like the last person to leave the group chat. 🙈

that's the whole NAME + SYNOPSIS situation bestie, every single symbol accounted for, not one macro left behind 💖 — the rest of the page is still coming, so don't close the tab on me yet 👀

💖 DESCRIPTION 💖

okay so picture this: the generic circular queue is a doubly linked list that was literally designed for efficient merge operations and unconditional removal. like, that's its whole brand. ✨

the slayest part? all the basic operations can be performed with or without a separate head, which means you can easily swap out any pointers wherever you want efficient removal. and the meaning of the data type will not change — you can mix direct use and defined operations whenever it's convenient, no cap. 🫶

the basic type is giving:

struct gcq {
        struct gcq *q_next;
        struct gcq *q_prev;
};

you must initialize the structure first, so that the q_next and q_prev members point to the beginning of the struct gcq. two ways to do it, bestie: gcq_init() and gcq_init_head(), or the constant initializers GCQ_INIT() and GCQ_INIT_HEAD(). and listen — a struct gcq should never be given NULL values. ever. 🙈

the structure containing the struct gcq can be retrieved by pointer arithmetic in the GCQ_ITEM() macro. list traversal normally requires knowing the list head to safely retrieve list items, iykyk.

🎀 the macro tea 🎀

Capitalized operation names are macros and you should assume they cause multiple evaluation of arguments. yes, that kind of energy. 💅

TYPED variants of macros set a typed pointer variable instead of — or in addition to — struct gcq * arguments. and honestly, additional type specific inlines and macros around some GCQ operations can be super useful.

a few assertions are provided when DIAGNOSTIC is defined in the kernel or _DIAGNOSTIC is defined in userland. if GCQ_USE_ASSERT is defined prior to header inclusions then assert() will be used for assertions, and NDEBUG can be used to turn them off. GCQ_ASSERT() is a wrapper around whichever assertion function is being used. ⭐

⚠️ real talk: none of the operations accept NULL arguments, however this is not tested by assertion. so like… don't. pls. 😭

💜 the head situation 💜

the head is separately named for type checking but contains only a struct gcq — a pointer to which can be retrieved via gcq_hq(). the reverse operation is performed by gcq_head(), turning the supplied struct gcq * into struct gcq_head *. gcq_q() returns its struct gcq * argument and is used for type checking in GCQ_ITEM().

there are no functions for retrieving the raw q_prev and q_next pointers — as these are usually clearer when used directly (if at all). iconic behavior honestly. 👑

🦋 the operations 🦋

  • gcq_remove() — returns the element removed, and it's always a valid operation after initialization. 💅
  • gcq_onlist() — returns false if the structure links to itself, and true otherwise.
  • gcq_empty() — the negation of this operation performed on a head.
  • gcq_linked() — tests if prev->q_next == next && next->q_prev == prev.

✨ gcq_tie() and friends ✨

gcq_tie() ties src after dst such that if the old lists are DST, DST2 and SRC, SRC2, the new list is DST, SRC, SRC2, DST2. the way that works is genuinely so satisfying. 🧚

if dst and src are on the same list then any elements between — but not including — dst and src are cut from the list. and if dst == src then the result is the same as gcq_remove().

gcq_tie() is equivalent to gcq_tie_after() — except that the latter must only be used with arguments on separate lists or not on lists, and it asserts that src != dst && dst->q_prev != src. gcq_tie_before() performs the same operation on dst->q_prev.

🔥 merging 🔥

gcq_merge() moves any elements on list src (but not src itself) to list dst. it's normally used with two heads via gcq_merge_head() or gcq_merge_tail().

if GCQ_UNCONDITIONAL_MERGE is defined prior to header inclusion then the merge operations will always perform a tie then remove src from the new list, which may reduce code size slightly. little optimization moment. 💀

🌸 clearing 🌸

gcq_clear() initializes all elements currently linked with q and is normally used with a head as gcq_remove_all().

🎀 inserting 🎀

gcq_insert_after() and gcq_insert_before() are slightly optimized versions of gcq_tie() for the case where off is not on a list, and they include assertions to this effect — which are also genuinely useful to detect missing initialization. gcq_insert_head() and gcq_insert_tail() are the same operations applied to a head. 🫶

🌈 GCQ_GOT_* macros 🌈

GCQ_GOT_FIRST() and GCQ_GOT_LAST() set var to a pointer to the first or last struct gcq in the list — or NULL if the list is empty — and return false if empty and true otherwise.

the boolean return is there to emphasise that it is not normally safe and useful to directly pass the raw first/next/etc. pointer to another function. the macros are written such that the NULL values will be optimized out if not otherwise used. ⭐

DEQUEUED variants also remove the member from the list. COND variants take an additional condition that is evaluated when the macro would otherwise return true — and if the condition is false, var or tvar is set to NULL and no dequeue is performed.

💜 GCQ_GOT_NEXT() and variants 💜

these take pointers to the current position, list head, and starting point as arguments. the list head will be skipped when it is reached unless it is equal to the starting point; upon reaching the starting point var will be set to NULL and the macro will return false.

the next and prev macros also assert that current is on the list unless it is equal to start. these macros are the only provided method for iterating through the list from an arbitrary point. traversal macros are only provided for list heads, however gcq_head() can be used to treat any item as a head. main character energy fr fr. 👑

💅 Foreach variants 💅

Foreach variants contain an embedded for statement for iterating over a list. those containing REV use the q_prev pointer for traversal, others use q_next.

  • the plain GCQ_FOREACH() uses a single variable.
  • NVAR variants save the next pointer at the top of the loop so that the current element can be removed without adjusting var. this is useful when var is passed to a function that might remove it but will not otherwise modify the list.
  • when the head is reached, both var and nvar elements are left pointing to the list head.
  • FOREACH asserts that var — and NVAR asserts that nvar — does not point to itself when starting the next loop. this assertion takes place after the variable is tested against the head, so it is safe to remove all elements from the list. slay. ✨
  • RO variants also set nvar but assert that the two variables are linked at the end of each iteration. this is useful when calling a function that is not supposed to remove the element passed.
  • DEQUEUED variants are like NVAR but remove each element before the code block is executed.
  • TYPED variants are equivalent to the untyped versions except that they take three extra arguments: a typed pointer, the type name, and the member name of the struct gcq used in this list. tvar is set to NULL when the head is reached.

🦋 GCQ_FIND() 🦋

GCQ_FIND() is a foreach loop that does nothing except break when the supplied condition is true. REV and TYPED variants are available. it's giving lowkey genius. 💖

🌟 SEE ALSO 🌟

gcc(1), _DIAGASSERT(3), assert(3), queue(3), KASSERT(9)

🎀 HISTORY 🎀

GCQ appeared in NetBSD 5.0. a legend was born. 👑

and that's the whole vibe check, bestie — this page came from Debian, dated May 1, 2007, and it's the GCQ(3) era. go forth and manage your circular queues with confidence. literally obsessed with you for reading all of this. 💖✨🎀

📦 where this page comes from