suckless/dwm - Unnamed repository; edit this file 'description' to name the repository.

diff options

Diffstat (limited to 'dwm.1')

-rw-r--r--

1 files changed, 2 insertions, 2 deletions

discard """ output: ''' start tradix.nim false false false false false false false false false false 128 1 2 3 4 255 17 45 19000 4294967288 ''' """ # implements and tests an efficient radix tree ## another method to store an efficient array of pointers: ## We use a radix tree with node compression. ## There are two node kinds: echo "start tradix.nim" const BitsPerUnit = 8*sizeof(int) type TRadixNodeKind = enum rnLinear, rnFull, rnLeafBits, rnLeafLinear PRadixNode = ptr TRadixNode TRadixNode {.pure, inheritable.} = object kind: TRadixNodeKind TRadixNodeLinear = object of TRadixNode len: uint8 keys: array[0..31, uint8] vals: array[0..31, PRadixNode] TRadixNodeFull = object of TRadixNode b: array[0..255, PRadixNode] TRadixNodeLeafBits = object of TRadixNode b: array[0..7, int] TRadixNodeLeafLinear = object of TRadixNode len: uint8 keys: array[0..31, uint8] var root: PRadixNode proc searchInner(r: PRadixNode, a: int): PRadixNode = case r.kind of rnLinear: var x = cast[ptr TRadixNodeLinear](r) for i in 0..int(x.len)-1: if int(x.keys[i]) == a: return x.vals[i] of rnFull: var x = cast[ptr TRadixNodeFull](r) return x.b[a] else: assert(false) proc testBit(w, i: int): bool {.inline.} = result = (w and (1 shl (i %% BitsPerUnit))) != 0 proc setBit(w: var int, i: int) {.inline.} = w = w or (1 shl (i %% BitsPerUnit)) proc resetBit(w: var int, i: int) {.inline.} = w = w and not (1 shl (i %% BitsPerUnit)) proc testOrSetBit(w: var int, i: int): bool {.inline.} = var x = (1 shl (i %% BitsPerUnit)) if (w and x) != 0: return true w = w or x proc searchLeaf(r: PRadixNode, a: int): bool = case r.kind of rnLeafBits: var x = cast[ptr TRadixNodeLeafBits](r) return testBit(x.b[a /% BitsPerUnit], a) of rnLeafLinear: var x = cast[ptr TRadixNodeLeafLinear](r) for i in 0..int(x.len)-1: if int(x.keys[i]) == a: return true else: assert(false) proc exclLeaf(r: PRadixNode, a: int) = case r.kind of rnLeafBits: var x = cast[ptr TRadixNodeLeafBits](r) resetBit(x.b[a /% BitsPerUnit], a) of rnLeafLinear: var x = cast[ptr TRadixNodeLeafLinear](r) var L = int(x.len) for i in 0..L-1: if int(x.keys[i]) == a: x.keys[i] = x.keys[L-1] dec(x.len) return else: assert(false) proc contains*(r: PRadixNode, a: ByteAddress): bool = if r == nil: return false var x = searchInner(r, a shr 24 and 0xff) if x == nil: return false x = searchInner(x, a shr 16 and 0xff) if x == nil: return false x = searchInner(x, a shr 8 and 0xff) if x == nil: return false return searchLeaf(x, a and 0xff) proc excl*(r: PRadixNode, a: ByteAddress): bool = if r == nil: return false var x = searchInner(r, a shr 24 and 0xff) if x == nil: return false x = searchInner(x, a shr 16 and 0xff) if x == nil: return false x = searchInner(x, a shr 8 and 0xff) if x == nil: return false exclLeaf(x, a and 0xff) proc addLeaf(r: var PRadixNode, a: int): bool = if r == nil: # a linear node: var x = cast[ptr TRadixNodeLinear](alloc0(sizeof(TRadixNodeLinear))) x.kind = rnLeafLinear x.len = 1'u8 x.keys[0] = uint8(a) r = x return false # not already in set case r.kind of rnLeafBits: var x = cast[ptr TRadixNodeLeafBits](r) return testOrSetBit(x.b[a /% BitsPerUnit], a) of rnLeafLinear: var x = cast[ptr TRadixNodeLeafLinear](r) var L = int(x.len) for i in 0..L-1: if int(x.keys[i]) == a: return true if L <= high(x.keys): x.keys[L] = uint8(a) inc(x.len) else: # transform into a full node: var y = cast[ptr TRadixNodeLeafBits](alloc0(sizeof(TRadixNodeLeafBits))) y.kind = rnLeafBits for i in 0..int(x.len)-1: var u = int(x.keys[i]) setBit(y.b[u /% BitsPerUnit], u) setBit(y.b[a /% BitsPerUnit], a) dealloc(r) r = y else: assert(false) proc addInner(r: var PRadixNode, a: int, d: int): bool = if d == 0: return addLeaf(r, a and 0xff) var k = a shr d and 0xff if r == nil: # a linear node: var x = cast[ptr TRadixNodeLinear](alloc0(sizeof(TRadixNodeLinear))) x.kind = rnLinear x.len = 1'u8 x.keys[0] = uint8(k) r = x return addInner(x.vals[0], a, d-8) case r.kind of rnLinear: var x = cast[ptr TRadixNodeLinear](r) var L = int(x.len) for i in 0..L-1: if int(x.keys[i]) == k: # already exists return addInner(x.vals[i], a, d-8) if L <= high(x.keys): x.keys[L] = uint8(k) inc(x.len) return addInner(x.vals[L], a, d-8) else: # transform into a full node: var y = cast[ptr TRadixNodeFull](alloc0(sizeof(TRadixNodeFull))) y.kind = rnFull for i in 0..L-1: y.b[int(x.keys[i])] = x.vals[i] dealloc(r) r = y return addInner(y.b[k], a, d-8) of rnFull: var x = cast[ptr TRadixNodeFull](r) return addInner(x.b[k], a, d-8) else: assert(false) proc incl*(r: var PRadixNode, a: ByteAddress) {.inline.} = discard addInner(r, a, 24) proc testOrIncl*(r: var PRadixNode, a: ByteAddress): bool {.inline.} = return addInner(r, a, 24) iterator innerElements(r: PRadixNode): tuple[prefix: int, n: PRadixNode] = if r != nil: case r.kind of rnFull: var r = cast[ptr TRadixNodeFull](r) for i in 0..high(r.b): if r.b[i] != nil: yield (i, r.b[i]) of rnLinear: var r = cast[ptr TRadixNodeLinear](r) for i in 0..int(r.len)-1: yield (int(r.keys[i]), r.vals[i]) else: assert(false) iterator leafElements(r: PRadixNode): int = if r != nil: case r.kind of rnLeafBits: var r = cast[ptr TRadixNodeLeafBits](r) # iterate over any bit: for i in 0..high(r.b): if r.b[i] != 0: # test all bits for zero for j in 0..BitsPerUnit-1: if testBit(r.b[i], j): yield i*BitsPerUnit+j of rnLeafLinear: var r = cast[ptr TRadixNodeLeafLinear](r) for i in 0..int(r.len)-1: yield int(r.keys[i]) else: assert(false) iterator elements*(r: PRadixNode): ByteAddress {.inline.} = for p1, n1 in innerElements(r): for p2, n2 in innerElements(n1): for p3, n3 in innerElements(n2): for p4 in leafElements(n3): yield p1 shl 24 or p2 shl 16 or p3 shl 8 or p4 proc main() = const numbers = [128, 1, 2, 3, 4, 255, 17, -8, 45, 19_000] var r: PRadixNode = nil for x in items(numbers): echo testOrIncl(r, x) for x in elements(r): # ByteAddress being defined as a signed integer cases trouble # exactly here echo(cast[uint](x)) main()


context:
space:
mode: