#
#
# Nim's Runtime Library
# (c) Copyright 2013 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
# Efficient set of pointers for the GC (and repr)
type
TRefCount = int
TCell {.pure.} = object
refcount: TRefCount # the refcount and some flags
typ: PNimType
when trackAllocationSource:
filename: cstring
line: int
when useCellIds:
id: int
PCell = ptr TCell
PPageDesc = ptr TPageDesc
TBitIndex = range[0..UnitsPerPage-1]
TPageDesc {.final, pure.} = object
next: PPageDesc # all nodes are connected with this pointer
key: ByteAddress # start address at bit 0
bits: array[TBitIndex, int] # a bit vector
PPageDescArray = ptr array[0..1000_000, PPageDesc]
TCellSet {.final, pure.} = object
counter, max: int
head: PPageDesc
data: PPageDescArray
PCellArray = ptr array[0..100_000_000, PCell]
TCellSeq {.final, pure.} = object
len, cap: int
d: PCellArray
# ------------------- cell seq handling ---------------------------------------
proc contains(s: TCellSeq, c: PCell): bool {.inline.} =
for i in 0 .. s.len-1:
if s.d[i] == c: return true
return false
proc add(s: var TCellSeq, c: PCell) {.inline.} =
if s.len >= s.cap:
s.cap = s.cap * 3 div 2
var d = cast[PCellArray](alloc(s.cap * sizeof(PCell)))
copyMem(d, s.d, s.len * sizeof(PCell))
dealloc(s.d)
s.d = d
# XXX: realloc?
s.d[s.len] = c
inc(s.len)
proc init(s: var TCellSeq, cap: int = 1024) =
s.len = 0
s.cap = cap
s.d = cast[PCellArray](alloc0(cap * sizeof(PCell)))
proc deinit(s: var TCellSeq) =
dealloc(s.d)
s.d = nil
s.len = 0
s.cap = 0
# ------------------- cell set handling ---------------------------------------
const
InitCellSetSize = 1024 # must be a power of two!
proc init(s: var TCellSet) =
s.data = cast[PPageDescArray](alloc0(InitCellSetSize * sizeof(PPageDesc)))
s.max = InitCellSetSize-1
s.counter = 0
s.head = nil
proc deinit(s: var TCellSet) =
var it = s.head
while it != nil:
var n = it.next
dealloc(it)
it = n
s.head = nil # play it safe here
dealloc(s.data)
s.data = nil
s.counter = 0
proc nextTry(h, maxHash: int): int {.inline.} =
result = ((5*h) + 1) and maxHash
# For any initial h in range(maxHash), repeating that maxHash times
# generates each int in range(maxHash) exactly once (see any text on
# random-number generation for proof).
proc cellSetGet(t: TCellSet, key: ByteAddress): PPageDesc =
var h = cast[int](key) and t.max
while t.data[h] != nil:
if t.data[h].key == key: return t.data[h]
h = nextTry(h, t.max)
return nil
proc cellSetRawInsert(t: TCellSet, data: PPageDescArray, desc: PPageDesc) =
var h = cast[int](desc.key) and t.max
while data[h] != nil:
sysAssert(data[h] != desc, "CellSetRawInsert 1")
h = nextTry(h, t.max)
sysAssert(data[h] == nil, "CellSetRawInsert 2")
data[h] = desc
proc cellSetEnlarge(t: var TCellSet) =
var oldMax = t.max
t.max = ((t.max+1)*2)-1
var n = cast[PPageDescArray](alloc0((t.max + 1) * sizeof(PPageDesc)))
for i in 0 .. oldMax:
if t.data[i] != nil:
cellSetRawInsert(t, n, t.data[i])
dealloc(t.data)
t.data = n
proc cellSetPut(t: var TCellSet, key: ByteAddress): PPageDesc =
var h = cast[int](key) and t.max
while true:
var x = t.data[h]
if x == nil: break
if x.key == key: return x
h = nextTry(h, t.max)
if ((t.max+1)*2 < t.counter*3) or ((t.max+1)-t.counter < 4):
cellSetEnlarge(t)
inc(t.counter)
h = cast[int](key) and t.max
while t.data[h] != nil: h = nextTry(h, t.max)
sysAssert(t.data[h] == nil, "CellSetPut")
# the new page descriptor goes into result
result = cast[PPageDesc](alloc0(sizeof(TPageDesc)))
result.next = t.head
result.key = key
t.head = result
t.data[h] = result
# ---------- slightly higher level procs --------------------------------------
proc contains(s: TCellSet, cell: PCell): bool =
var u = cast[ByteAddress](cell)
var t = cellSetGet(s, u shr PageShift)
if t != nil:
u = (u %% PageSize) /% MemAlign
result = (t.bits[u shr IntShift] and (1 shl (u and IntMask))) != 0
else:
result = false
proc incl(s: var TCellSet, cell: PCell) {.noinline.} =
var u = cast[ByteAddress](cell)
var t = cellSetPut(s, u shr PageShift)
u = (u %% PageSize) /% MemAlign
t.bits[u shr IntShift] = t.bits[u shr IntShift] or (1 shl (u and IntMask))
proc excl(s: var TCellSet, cell: PCell) =
var u = cast[ByteAddress](cell)
var t = cellSetGet(s, u shr PageShift)
if t != nil:
u = (u %% PageSize) /% MemAlign
t.bits[u shr IntShift] = (t.bits[u shr IntShift] and
not (1 shl (u and IntMask)))
proc containsOrIncl(s: var TCellSet, cell: PCell): bool =
var u = cast[ByteAddress](cell)
var t = cellSetGet(s, u shr PageShift)
if t != nil:
u = (u %% PageSize) /% MemAlign
result = (t.bits[u shr IntShift] and (1 shl (u and IntMask))) != 0
if not result:
t.bits[u shr IntShift] = t.bits[u shr IntShift] or
(1 shl (u and IntMask))
else:
incl(s, cell)
result = false
iterator elements(t: TCellSet): PCell {.inline.} =
# while traversing it is forbidden to add pointers to the tree!
var r = t.head
while r != nil:
var i = 0
while i <= high(r.bits):
var w = r.bits[i] # taking a copy of r.bits[i] here is correct, because
# modifying operations are not allowed during traversation
var j = 0
while w != 0: # test all remaining bits for zero
if (w and 1) != 0: # the bit is set!
yield cast[PCell]((r.key shl PageShift) or
(i shl IntShift +% j) *% MemAlign)
inc(j)
w = w shr 1
inc(i)
r = r.next
iterator elementsExcept(t, s: TCellSet): PCell {.inline.} =
var r = t.head
while r != nil:
let ss = cellSetGet(s, r.key)
var i = 0
while i <= high(r.bits):
var w = r.bits[i]
if ss != nil:
w = w and not ss.bits[i]
var j = 0
while w != 0:
if (w and 1) != 0:
yield cast[PCell]((r.key shl PageShift) or
(i shl IntShift +% j) *% MemAlign)
inc(j)
w = w shr 1
inc(i)
r = r.next