IntrusiveQueue

Intrusive singly linked queue over external items. The queue does not own the items.

`IntrusiveQueue`

(Item -- queue) Constructs an empty intrusive singly linked queue for external items.

Each item schema must provide next of schema [Item] Mref.
Returns a new empty container object; Item supplies the item schema and the supplied object is not inserted.
The container stores references to caller-owned items and does not own or destroy them.

Fields

SCHEMA_NAME: static Text naming the generated schema as IntrusiveQueue<ItemSchemaName>.
Item: static NIL reference supplying the item-reference schema.
first: reference to the first item, or NIL when empty; ordinary reads are immutable, while mutable access through a mutable container returns a mutable item reference.
last: reference to the last item, or NIL when empty; ordinary reads are immutable, while mutable access through a mutable container returns a mutable item reference.

Lifetime

INIT clears the endpoint references and does not touch item links. DIE does nothing; destroying the container does not destroy items or rewrite their links.

Ownership and link updates

Insertion and cut require mutable access to a live, non-NIL Item object.
Provide next as an [Item] Mref link referring to the same Item schema and yielding mutable references through mutable item access.
Keep linked items and items an iterator may still visit alive at the same storage address. Duplicate insertion can create a cycle; reuse in another queue can corrupt the old chain. There is no membership check.
A queue uses next; it can share an item's separate prev link with a stack, but two queues or a deque sharing next cannot be mutated independently. The container is movable but not copyable; moving transfers endpoint references and leaves the source empty without relocating items.
Removal repairs retained links but does not clear the removed item's own links. An existing iterator keeps its position and follows current item links; clearing the container does not reset it.

Caller requirements

Use an in-place Item object or mutable Item reference as the schema representative. An immutable representative changes generated item-reference schemas and is not interchangeable with this form.
Predicate has stack effect (item -- cond), receives a mutable Item reference, and must not change intrusive links, membership, move items, or end their lifetimes.
cutFirst and popFirst require a nonempty queue; checked violations report queue is empty.
Nonempty and link-validity requirements are preconditions. Assertion checking reports violations; -ndebug disables runtime assertions.
Known violations of these assertions are rejected at compile time even with DEBUG disabled.

Known issue: removal from a valid container of named local items can fail at compile time with invalid linked list state, even with -ndebug. Affected methods: cutAllIf, cutFirst, cutIf, and popFirst; apply @q dynamic drop immediately before each removal.

Methods

`empty?`

(-- cond) Reports whether the queue has no first item.

Returns TRUE when first is NIL.

`append`

(item --) Links item at the back.

Sets item.next to NIL; links it after last or makes it first when empty.
Detected link inconsistencies report invalid linked list state during assertion checking.

`clear`

(--) Forgets first and last.

It does not rewrite item links or destroy items.

`cutAllIf`

(predicate -- count) Removes every item accepted by predicate and returns the count.

The predicate returns Cond. The method returns an Int32 removal count: it calls the predicate once per item from front to back, the retained items preserve order, and an empty queue returns 0 without calling it.
Neighbor next links and endpoints are repaired as items are removed.

`cutFirst`

(--) Removes the first item.

The removed item is not destroyed.

`cutIf`

(predicate -- count) Removes the first item accepted by predicate and returns 0 or 1.

The predicate returns Cond. The method returns an Int32 removal count: it stops after the first TRUE result and returns 1, or returns 0 if none matches; an empty queue does not call it.

`iter`

(-- iter) Returns a forward iterator from first to last.

next has stack effect (-- item cond). On success, item is a reference to the caller's object, not a copy. Advance the iterator through a mutable view; an immutable container view returns immutable references. Exhaustion returns a NIL item reference and FALSE; do not dereference that result.
An iterator created through a mutable container view permits mutable item access when advanced through a mutable iterator view.

`popFirst`

(-- item) Returns the first item reference and removes it.

Returns a mutable reference to the removed caller-owned item, not a copy; removal does not end its lifetime.

`prepend`

(item --) Links item at the front.

Sets item.next to the old first and updates last when the queue was empty.

`reverse`

(--) Reverses the queue in place.

Rewrites next links and swaps first and last; an empty queue is unchanged.

`validate`

(--) Checks the forward chain in debug builds.

When DEBUG is TRUE, follows next to NIL and checks that the final item is last. A mismatched last endpoint reports invalid linked list state; cycles are not detected and can loop indefinitely. When DEBUG is FALSE, it does nothing.

Append, prepend, reverse, and popFirst

"IntrusiveQueue" use
"Mref"           use
"String"         use
"control"        use

Node: [{
  value: Int32;
  next: [Node] Mref;
}];

{} Int32 {} [
  q: Node IntrusiveQueue;
  n0: Node;
  n1: Node;
  n2: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  @n1 @q.append
  @n2 @q.append
  @n0 @q.prepend
  ("first=" @q.@first.value new LF
    "last=" @q.@last.value new LF) printList
  @q.reverse
  ("first2=" @q.@first.value new LF
    "last2=" @q.@last.value new LF
    "popFirst=" @q.popFirst.value new LF
    "first3=" @q.@first.value new LF) printList
  0
] "main" exportFunction

Expected Output

first=10
last=30
first2=30
last2=10
popFirst=30
first3=20

cutIf and cutAllIf

"IntrusiveQueue" use
"Mref"           use
"String"         use
"control"        use

Node: [{
  value: Int32;
  next: [Node] Mref;
}];

{} Int32 {} [
  q: Node IntrusiveQueue;
  n0: Node;
  n1: Node;
  n2: Node;
  n3: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  40 @n3.!value
  @n0 @q.append
  @n1 @q.append
  @n2 @q.append
  @n3 @q.append
  c0: [item:; item.value 20 =] @q.cutIf;
  c1: [item:; item.value 40 =] @q.cutAllIf;
  it: @q.iter;
  item0: ok0: @it.next;;
  item1: ok1: @it.next;;
  item2: ok2: @it.next;;
  ("c0=" c0 LF
    "c1=" c1 LF
    "v0=" item0.value new LF
    "v1=" item1.value new LF
    "done=" ok2 LF) printList
  0
] "main" exportFunction

Expected Output

c0=1
c1=1
v0=10
v1=30
done=FALSE

Iterator next result schema

The queue iterator returns one item and one success condition from next.

Empty iterator result

"IntrusiveQueue" use
"Mref"           use
"control"        use

Node: [{
  value: Int32;
  next: [Node] Mref;
}];

{} () {} [
  q: Node IntrusiveQueue;
  @q.iter.next printStack swap drop drop
] "main" exportFunction

Expected Output During Compilation

{
  value: Int32;
  next: Mref;
} NIL
FALSE

Runtime example: iteration order

"IntrusiveQueue" use
"Mref"           use
"String"         use
"control"        use

Node: [{
  value: Int32;
  next: [Node] Mref;
}];

{} Int32 {} [
  q: Node IntrusiveQueue;
  n0: Node;
  n1: Node;
  n2: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  @n0 @q.append
  @n1 @q.append
  @n2 @q.append
  it: @q.iter;
  item0: ok0: @it.next;;
  item1: ok1: @it.next;;
  item2: ok2: @it.next;;
  item3: ok3: @it.next;;
  ("ok0=" ok0 LF
    "v0=" item0.value new LF
    "ok1=" ok1 LF
    "v1=" item1.value new LF
    "ok2=" ok2 LF
    "v2=" item2.value new LF
    "ok3=" ok3 LF) printList
  0
] "main" exportFunction

Expected Output

ok0=TRUE
v0=10
ok1=TRUE
v1=20
ok2=TRUE
v2=30
ok3=FALSE

IntrusiveQueue

Fields

Lifetime

Ownership and link updates

Caller requirements

Methods

Append, prepend, reverse, and popFirst

Expected Output

cutIf and cutAllIf

Expected Output

Iterator next result schema

Empty iterator result

Expected Output During Compilation

Runtime example: iteration order

Expected Output

See also