IntrusiveStack

Fields

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

Requirements

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

Ownership and link updates

• The stack stores external items and never destroys them.
• append, cutLast, cutLastIf, and reverse update the participating prev links.
• clear forgets the current top item without rewriting stored item links.

Methods

• INIT (--): clears the stack.
• DIE (--): no-op destructor.
• empty? (-- valid): reports whether the stack is empty.
• append (item --): pushes one item onto the top.
• clear (--): forgets the current top item.
• cutAllIf (predicate -- count): removes all items for which predicate reports TRUE.
• cutLast (--): removes the top item.
• cutLastIf (predicate -- count): removes the first matching item when scanning from the top.
• popLast (-- item): returns the top item and removes it.
• reverse (--): reverses the stack chain in place.
• reverseIter (-- iter): returns iteration from top to bottom.

Append, reverse, and popLast

"IntrusiveStack" use
"Mref" use
"String" use
"control" use

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

{} Int32 {} [
  s: Node IntrusiveStack;
  n0: Node;
  n1: Node;
  n2: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  @n0 @s.append
  @n1 @s.append
  @n2 @s.append
  ("top=" @[email protected] new LF) printList
  @s.reverse
  ("top2=" @[email protected] new LF
   "popLast=" @s.popLast.value new LF
   "top3=" @[email protected] new LF) printList
  0
] "main" exportFunction

Expected Output

top=30
top2=10
popLast=10
top3=20

cutLastIf and cutAllIf

"IntrusiveStack" use
"Mref" use
"String" use
"control" use

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

{} Int32 {} [
  s: Node IntrusiveStack;
  n0: Node;
  n1: Node;
  n2: Node;
  n3: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  40 @n3.!value
  @n0 @s.append
  @n1 @s.append
  @n2 @s.append
  @n3 @s.append
  c0: [item:; item.value 40 =] @s.cutLastIf;
  c1: [item:; item.value 20 =] @s.cutAllIf;
  it: @s.reverseIter;
  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=30
v1=10
done=FALSE

Traversal and validity rules

• reverseIter traverses items from the top toward the bottom.
• cutLastIf scans from the top.
• popLast and cutLast require one non-empty stack.

Iterator next result schema

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

Empty reverse iterator result

"IntrusiveStack" use
"Mref" use
"control" use

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

{} () {} [
  s: Node IntrusiveStack;
  @s.reverseIter.next printStack swap drop drop
] "main" exportFunction

Expected Output During Compilation

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

Runtime example: reverse iteration order

"IntrusiveStack" use
"Mref" use
"String" use
"control" use

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

{} Int32 {} [
  s: Node IntrusiveStack;
  n0: Node;
  n1: Node;
  n2: Node;
  10 @n0.!value
  20 @n1.!value
  30 @n2.!value
  @n0 @s.append
  @n1 @s.append
  @n2 @s.append
  it: @s.reverseIter;
  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=30
ok1=TRUE
v1=20
ok2=TRUE
v2=10
ok3=FALSE

See also

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