diff options
Diffstat (limited to 'lib/system/avltree.nim')
| -rw-r--r-- | lib/system/avltree.nim | 34 |
1 files changed, 20 insertions, 14 deletions
diff --git a/lib/system/avltree.nim b/lib/system/avltree.nim index 6a268b453..8d4b7e897 100644 --- a/lib/system/avltree.nim +++ b/lib/system/avltree.nim @@ -1,6 +1,6 @@ # # -# Nimrod's Runtime Library +# Nim's Runtime Library # (c) Copyright 2012 Andreas Rumpf # # See the file "copying.txt", included in this @@ -9,30 +9,30 @@ # not really an AVL tree anymore, but still balanced ... -template IsBottom(n: PAvlNode): bool = n == bottom +template isBottom(n: PAvlNode): bool = n.link[0] == n proc lowGauge(n: PAvlNode): int = var it = n - while not IsBottom(it): + while not isBottom(it): result = it.key it = it.link[0] - + proc highGauge(n: PAvlNode): int = result = -1 var it = n - while not IsBottom(it): + while not isBottom(it): result = it.upperBound it = it.link[1] -proc find(root: PAvlNode, key: int): PAvlNode = +proc find(root: PAvlNode, key: int): PAvlNode = var it = root - while not IsBottom(it): + while not isBottom(it): if it.key == key: return it it = it.link[ord(it.key <% key)] proc inRange(root: PAvlNode, key: int): PAvlNode = var it = root - while not IsBottom(it): + while not isBottom(it): if it.key <=% key and key <% it.upperBound: return it it = it.link[ord(it.key <% key)] @@ -51,31 +51,37 @@ proc split(t: var PAvlNode) = t.link[0] = temp inc t.level -proc add(a: var TMemRegion, t: var PAvlNode, key, upperBound: int) = - if t == bottom: +proc add(a: var MemRegion, t: var PAvlNode, key, upperBound: int) {.benign.} = + if t.isBottom: t = allocAvlNode(a, key, upperBound) else: if key <% t.key: + when defined(avlcorruption): + if t.link[0] == nil: + cprintf("bug here %p\n", t) add(a, t.link[0], key, upperBound) elif key >% t.key: + when defined(avlcorruption): + if t.link[1] == nil: + cprintf("bug here B %p\n", t) add(a, t.link[1], key, upperBound) else: sysAssert false, "key already exists" skew(t) split(t) -proc del(a: var TMemRegion, t: var PAvlNode, x: int) = - if t == bottom: return +proc del(a: var MemRegion, t: var PAvlNode, x: int) {.benign.} = + if isBottom(t): return a.last = t if x <% t.key: del(a, t.link[0], x) else: a.deleted = t del(a, t.link[1], x) - if t == a.last and a.deleted != bottom and x == a.deleted.key: + if t == a.last and not isBottom(a.deleted) and x == a.deleted.key: a.deleted.key = t.key a.deleted.upperBound = t.upperBound - a.deleted = bottom + a.deleted = getBottom(a) t = t.link[1] deallocAvlNode(a, a.last) elif t.link[0].level < t.level-1 or |