It tends to come up somewhat regularly and I had the need myself. So here it is
a "StableSeq", that is a seq that does not reallocate. The cost is that it's
not convertible to an `openArray`.
type
StableChunk[T] = object
next: ptr StableChunk[T]
len, cap: int
data: UncheckedArray[T]
StableSeq*[T] = object
head, tail: ptr StableChunk[T]
len: int
proc createChunk[T](cap: int): ptr StableChunk[T] =
result = cast[ptr StableChunk[T]](alloc0(sizeof(StableChunk[T]) +
sizeof(T) * cap))
result.cap = cap
proc createStableSeq*[T](cap = 10): StableSeq[T] =
var c = createChunk[T](cap)
StableSeq[T](head: c, tail: c, len: 0)
proc destroy*[T](s: StableSeq[T]) =
var it = s.head
while it != nil:
let next = it.next
dealloc it
it = next
proc append*[T](s: var StableSeq[T]; data: sink T): ptr T =
if s.tail.len >= s.tail.cap:
let oldTail = s.tail
let newCap = oldTail.cap * 3 div 2
assert newCap > 2
s.tail = createChunk[T](newCap)
oldTail.next = s.tail
result = addr s.tail.data[s.tail.len]
result[] = ensureMove data
inc s.tail.len
inc s.len
proc add*[T](s: var StableSeq[T]; data: sink T) =
discard append(s, data)
iterator items*[T](s: StableSeq[T]): lent T =
var it = s.head
while it != nil:
for i in 0 ..< it.len:
yield it.data[i]
it = it.next
proc nav[T](s: StableSeq[T]; i: var int): ptr StableChunk[T] =
var it = s.head
while it != nil:
if i < it.len:
return it
dec i, it.len
it = it.next
return nil
proc `[]`*[T](s: var StableSeq[T]; index: int): var T =
var i = index
let it = nav(s, i)
if it != nil:
return it.data[i]
else:
raise newException(IndexDefect, "index out of bounds")
proc `[]`*[T](s: StableSeq[T]; index: int): lent T =
var i = index
let it = nav(s, i)
if it != nil:
return it.data[i]
else:
raise newException(IndexDefect, "index out of bounds")
proc `[]=`*[T](s: var StableSeq[T]; index: int; elem: sink T) =
var i = index
let it = nav(s, i)
if it != nil:
it.data[i] = elem
else:
raise newException(IndexDefect, "index out of bounds")
when isMainModule:
var s = createStableSeq[int]()
for i in 0 ..< 1000:
discard s.append i
s[998] = 13
for elem in s:
echo elem
destroy s
Run
Here are my questions/remarks:
1. Should this really be named `StableSeq`?
2. Should `=copy` be an `.error` or follow the existing containers and
perform an expensive copy?
3. Should it be named `append`?
4. `nav` should probably use some better algorithm.
