IntrusiveStack

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

`IntrusiveStack`

(Item -- stack) Constructs an empty intrusive LIFO stack for external items.

Each item schema must provide prev 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 IntrusiveStack<ItemSchemaName>.
Item: static NIL reference supplying the item-reference schema.
last: reference to the top 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 reference 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 prev 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 stack can corrupt the old chain. There is no membership check.
A stack uses prev; it can share an item's separate next link with a queue, but two stacks or a deque sharing prev cannot be mutated independently. The container is movable but not copyable; moving transfers the endpoint reference 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.
cutLast and popLast require a nonempty stack; checked violations report stack 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.

Methods

`empty?`

(-- cond) Reports whether the stack has no top item.

Returns TRUE when last is NIL.

`append`

(item --) Pushes item onto the top.

Sets item.prev to the old last and makes item the new last.

`clear`

(--) Forgets the top item.

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 top to bottom, the retained items preserve order, and an empty stack returns 0 without calling it.
Neighbor prev links and the last endpoint are repaired as items are removed.

`cutLast`

(--) Removes the top item.

The removed item is not destroyed.

`cutLastIf`

(predicate -- count) Removes the first item accepted by predicate when scanning from the top.

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 stack does not call it.

`popLast`

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

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

`reverse`

(--) Reverses the stack chain in place.

Rewrites prev links and changes last to the former bottom; an empty stack is unchanged.

`reverseIter`

(-- iter) Returns an iterator from top to bottom.

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.

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=" @s.@last.value new LF) printList
  @s.reverse
  ("top2=" @s.@last.value new LF
    "popLast=" @s.popLast.value new LF
    "top3=" @s.@last.value 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

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

IntrusiveStack

Fields

Lifetime

Ownership and link updates

Caller requirements

Methods

Append, reverse, and popLast

Expected Output

cutLastIf and cutAllIf

Expected Output

Iterator next result schema

Empty reverse iterator result

Expected Output During Compilation

Runtime example: reverse iteration order

Expected Output

See also