Self-allocated doubly-linked list for Terra.
Written by Cosmin Apreutesei. Public domain.
Implemented using a dynarray and a freelist, which means that the location
of the links in memory is not stable between inserts unless the list is
preallocated and doesn't grow. Indices are stable though and can be used
to retrieve the same link after any number of mutations.
local L = list(T,[size_t=int]) create a list type
var list = list(T,[size_t]) create a list object
list:init() initialize (for struct members)
list:clear() remove items, keep the memory
list:free() free (items are not freed!)
list:setcapacity(size) -> ok? set capacity with error checking
list.capacity (write/only) set capacity
list.min_capacity (write/only) grow capacity
list:link(i) -> &e link at index
e.item -> &t link's payload (element)
e.next -> i (read/only) next link's index
e.prev -> i (read/only) prev link's index
list.first -> i (read/write) index of first link
list.last -> i (read/write) index of last link
for i,&e in list do ... end iterate links (remove() works inside)
for i,&e in list:backwards() do ... end iterate backwards (remove() works inside)
list:insert_before(i[,v]) -> i insert v before i
list:insert_after(i[,v]) -> i insert v after i
list:remove(i) remove link
list:move_before(di,i) move link at i before link at di
list:move_after(di,i) move link at i after link at di
See the source code for more info.