In my quest to be able to use very large linked lists with the reference counting garbage collector, I made a linked list implementation that uses pointers instead of references:
type
SinglyLinkedRefListNodeObj[T] = tuple
next: ptr SinglyLinkedRefListNodeObj[T]
value: pointer
SinglyLinkedRefListNode[T] = ptr SinglyLinkedRefListNodeObj[T]
SinglyLinkedRefListObj[T] = tuple
head: SinglyLinkedRefListNode[T]
tail: SinglyLinkedRefListNode[T]
SinglyLinkedRefList*[T] = ref SinglyLinkedRefListObj[T]
proc newSinglyLinkedRefListNode[T](value: ref T): SinglyLinkedRefListNode[T] not nil =
let p = alloc0(sizeof(SinglyLinkedRefListNode[T]))
if p != nil:
result = cast[SinglyLinkedRefListNode[T] not nil](p)
else:
raise newException(Exception, "Cannot allocate memory!")
GC_ref(value)
result[] = (next: nil, value: cast[pointer](value))
proc finalizeSinglyLinkedRefList[T](list: SinglyLinkedRefList[T] not nil) =
var current = list.head
while current != nil:
let value = cast[ref T](current.value)
let next = current.next
dealloc(current)
GC_unref(value)
current = next
proc newSinglyLinkedRefList*[T](): SinglyLinkedRefList[T] not nil =
new(result, finalizeSinglyLinkedRefList)
result[] = (head: nil, tail: nil)
proc prepend*[T](list: SinglyLinkedRefList[T] not nil, value: ref T) =
var node = newSinglyLinkedRefListNode[T](value)
when defined(debugReflists):
if node.value == nil:
echo "nil on set"
node.next = list.head
list.head = node
if list.tail == nil:
list.tail = node
iterator items*[T](list: SinglyLinkedRefList[T] not nil): ref T =
var current = list.head
while current != nil:
when defined(debugReflists):
if current.value == nil:
echo "nil on retrieve"
yield cast[ref T](current.value)
current = current.next
proc append*[T](list: SinglyLinkedRefList[T] not nil, value: ref T) =
var node = newSinglyLinkedRefListNode[T](value)
when defined(debugReflists):
if node.value == nil:
echo "nil on set"
if list.tail != nil:
list.tail.next = node
list.tail = node
if list.head == nil:
list.head = node
when isMainModule:
block:
var list = newSinglyLinkedRefList[string]()
for i in countUp(0, 2_000_000):
var iString: ref string
new(iString)
iString[] = "hello world"
list.append(iString)
for iString in list.items:
echo(iString[])
However, when I try to use this, it appears that Nim destroys the value variable in SinglyLinkedRefListNodeObj, because I get this:
Traceback (most recent call last)
reflists.nim(61) reflists
gc.nim(169) asgnRefNoCycle
SIGSEGV: Illegal storage access. (Attempt to read from nil?)
Is this a bug or the intended behavior?
Bug here:
let p = alloc0(sizeof(SinglyLinkedRefListNode[T]))
Change to:
let p = alloc0(sizeof(SinglyLinkedRefListNodeObj[T]))
Better still, use create() instead of alloc0().
OS X Yosemite 10.10.4, computer is a "MacBookPro11,5", CPU is an Intel I7-4870HQ, C compiler is the default system clang.
$ clang --version
Apple LLVM version 7.0.0 (clang-700.0.72)
Target: x86_64-apple-darwin14.4.0
Thread model: posix
$ nim --version
Nim Compiler Version 0.11.2 (2015-05-04) [MacOSX: amd64]
Copyright (c) 2006-2015 by Andreas Rumpf
git hash: 3bef848a2cf60008f23e72571d7c20c0eb9fd728
active boot switches: -d:release