Swift crashes during dealloc

I've made a little linked list, when there's to much nodes in it it crashes during dealloc. (reported: rdar://22189873)


Here is a sample code :

public class ListNode<T> {
    var next: ListNode<T>?
    weak var previous: ListNode<T>?

    let element: T

    init(element: T) {
        self.element = element
    }
}
public struct LinkedList<T> {
    public typealias Element = T
    private var head: ListNode<T>?
    private weak var tail: ListNode<T>?
}
public extension LinkedList {
    public mutating func append(element: Element) {
        let node = ListNode<T>(element: element)
        if head == nil || tail == nil {
            self.head = node
            self.tail = head
        } else {
            let old = tail
            tail = node
            old!.next = tail
            tail!.previous = old
        }
   
    }

    public mutating func removeAll() {
        head = nil
    }
}


That's pretty simple.


Now here is a simple test :

var count = 500_000
var ll = LinkedList<Int>()
for i in 0..<count {
    ll.append(i)
}
ll.removeAll()


It crashes. If count is lower than about 85000 it doesn't crash...

I think it's because it releases nodes recursively once head is set to nil and causes function stack overflow.

What shoul I do ?

Replies

I think it's because it releases nodes recursively once head is set to nil and causes function stack overflow.

It is very likely happening is what you said, as reference count based memory management requires recursive release calls.


What shoul I do ?

One thing you should NOT do is having too much elements in a linked list.


Generally, if recursive releasing causes a problem, you need to implement non-recursive releasing yourself.

I just ran into this myself. Since previous node is a weak ref, you can start from the tail and nil the next node in your deinit to imperatively dealloc rather than let it recursively **** the stack.

Code Block swift
  deinit {
    var cur = tail
    while let node = cur {
      node.next = nil
      cur = cur?.prev
    }
  }