IntrusiveQueue

Fields

• Item: stored item schema.
• first: first item or NIL when empty.
• last: last item or NIL when empty.

Requirements

• Each item schema must provide next of schema [Item] Mref.

Ownership and link updates

• The queue stores external items and never destroys them.
• append, prepend, cutFirst, cutIf, cutAllIf, and reverse update the participating next links.
• clear forgets the current first and last items without rewriting stored item links.

Methods

• INIT (--): clears the queue.
• DIE (--): no-op destructor.
• empty? (-- valid): reports whether the queue is empty.
• append (item --): appends one item at the back.
• clear (--): forgets the current first and last items.
• cutAllIf (predicate -- count): removes all items for which predicate reports TRUE.
• cutFirst (--): removes the first item.
• cutIf (predicate -- count): removes the first matching item.
• iter (-- iter): returns forward iteration from first to last.
• popFirst (-- item): returns the first item and removes it.
• prepend (item --): prepends one item at the front.
• reverse (--): reverses the queue in place.
• validate (--): debug-only structure check.

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=" @[email protected] new LF
   "last=" @[email protected] new LF) printList
  @q.reverse
  ("first2=" @[email protected] new LF
   "last2=" @[email protected] new LF
   "popFirst=" @q.popFirst.value new LF
   "first3=" @[email protected] 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

Traversal and validity rules

• iter traverses items from first to last.
• cutIf scans from the front.
• popFirst and cutFirst require one non-empty queue.

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

See also

• IntrusiveDeque: Intrusive doubly linked deque over external items.
• IntrusiveStack: Intrusive singly linked LIFO stack over external items.
• Mref: Minimal Ref type with custom semantics.
• Deque: Double-ended queue data structure.