diff options
Diffstat (limited to 'compiler/btrees.nim')
| -rw-r--r-- | compiler/btrees.nim | 84 |
1 files changed, 14 insertions, 70 deletions
diff --git a/compiler/btrees.nim b/compiler/btrees.nim index 18854d474..3b737b1bc 100644 --- a/compiler/btrees.nim +++ b/compiler/btrees.nim @@ -10,13 +10,16 @@ ## BTree implementation with few features, but good enough for the ## Nim compiler's needs. +when defined(nimPreviewSlimSystem): + import std/assertions + const M = 512 # max children per B-tree node = M-1 # (must be even and greater than 2) Mhalf = M div 2 type - Node[Key, Val] = ref object + Node[Key, Val] {.acyclic.} = ref object entries: int keys: array[M, Key] case isInternal: bool @@ -35,6 +38,7 @@ template less(a, b): bool = cmp(a, b) < 0 template eq(a, b): bool = cmp(a, b) == 0 proc getOrDefault*[Key, Val](b: BTree[Key, Val], key: Key): Val = + result = default(Val) var x = b.root while x.isInternal: for j in 0..<x.entries: @@ -65,7 +69,10 @@ proc copyHalf[Key, Val](h, result: Node[Key, Val]) = result.links[j] = h.links[Mhalf + j] else: for j in 0..<Mhalf: - shallowCopy(result.vals[j], h.vals[Mhalf + j]) + when defined(gcArc) or defined(gcOrc) or defined(gcAtomicArc): + result.vals[j] = move h.vals[Mhalf + j] + else: + shallowCopy(result.vals[j], h.vals[Mhalf + j]) proc split[Key, Val](h: Node[Key, Val]): Node[Key, Val] = ## split node in half @@ -85,7 +92,10 @@ proc insert[Key, Val](h: Node[Key, Val], key: Key, val: Val): Node[Key, Val] = if less(key, h.keys[j]): break inc j for i in countdown(h.entries, j+1): - shallowCopy(h.vals[i], h.vals[i-1]) + when defined(gcArc) or defined(gcOrc) or defined(gcAtomicArc): + h.vals[i] = move h.vals[i-1] + else: + shallowCopy(h.vals[i], h.vals[i-1]) h.vals[j] = val else: var newLink: Node[Key, Val] = nil @@ -135,8 +145,7 @@ proc `$`[Key, Val](b: BTree[Key, Val]): string = result = "" toString(b.root, "", result) -proc hasNext*[Key, Val](b: BTree[Key, Val]; index: int): bool = - result = index < b.entries +proc hasNext*[Key, Val](b: BTree[Key, Val]; index: int): bool = index < b.entries proc countSubTree[Key, Val](it: Node[Key, Val]): int = if it.isInternal: @@ -169,68 +178,3 @@ iterator pairs*[Key, Val](b: BTree[Key, Val]): (Key, Val) = yield (k, v) proc len*[Key, Val](b: BTree[Key, Val]): int {.inline.} = b.entries - -when isMainModule: - - import random, tables - - proc main = - var st = initBTree[string, string]() - st.add("www.cs.princeton.edu", "abc") - st.add("www.princeton.edu", "128.112.128.15") - st.add("www.yale.edu", "130.132.143.21") - st.add("www.simpsons.com", "209.052.165.60") - st.add("www.apple.com", "17.112.152.32") - st.add("www.amazon.com", "207.171.182.16") - st.add("www.ebay.com", "66.135.192.87") - st.add("www.cnn.com", "64.236.16.20") - st.add("www.google.com", "216.239.41.99") - st.add("www.nytimes.com", "199.239.136.200") - st.add("www.microsoft.com", "207.126.99.140") - st.add("www.dell.com", "143.166.224.230") - st.add("www.slashdot.org", "66.35.250.151") - st.add("www.espn.com", "199.181.135.201") - st.add("www.weather.com", "63.111.66.11") - st.add("www.yahoo.com", "216.109.118.65") - - assert st.getOrDefault("www.cs.princeton.edu") == "abc" - assert st.getOrDefault("www.harvardsucks.com") == "" - - assert st.getOrDefault("www.simpsons.com") == "209.052.165.60" - assert st.getOrDefault("www.apple.com") == "17.112.152.32" - assert st.getOrDefault("www.ebay.com") == "66.135.192.87" - assert st.getOrDefault("www.dell.com") == "143.166.224.230" - assert(st.entries == 16) - - for k, v in st: - echo k, ": ", v - - when false: - var b2 = initBTree[string, string]() - const iters = 10_000 - for i in 1..iters: - b2.add($i, $(iters - i)) - for i in 1..iters: - let x = b2.getOrDefault($i) - if x != $(iters - i): - echo "got ", x, ", but expected ", iters - i - echo b2.entries - - when true: - var b2 = initBTree[int, string]() - var t2 = initTable[int, string]() - const iters = 100_000 - for i in 1..iters: - let x = rand(high(int)) - if not t2.hasKey(x): - doAssert b2.getOrDefault(x).len == 0, " what, tree has this element " & $x - t2[x] = $x - b2.add(x, $x) - - doAssert b2.entries == t2.len - echo "unique entries ", b2.entries - for k, v in t2: - doAssert $k == v - doAssert b2.getOrDefault(k) == $k - - main() |