diff options
author | Andreas Rumpf <rumpf_a@web.de> | 2016-11-19 10:46:43 +0100 |
---|---|---|
committer | GitHub <noreply@github.com> | 2016-11-19 10:46:43 +0100 |
commit | 9ca3ae14ab5d4bff1c5016a2919414c720bb82f8 (patch) | |
tree | c3564158cb18391f52ed9f416ce5b1dfec9cf119 /lib | |
parent | 3eba4b510f853c314bbd596873f77ccfcc4f55da (diff) | |
parent | 93a998204c62ce473e125f059250f4a64a10ce0a (diff) | |
download | Nim-9ca3ae14ab5d4bff1c5016a2919414c720bb82f8.tar.gz |
Merge pull request #5036 from flyx/tablesdelfix
Fixes #5035
Diffstat (limited to 'lib')
-rw-r--r-- | lib/pure/collections/tableimpl.nim | 14 | ||||
-rw-r--r-- | lib/pure/collections/tables.nim | 13 |
2 files changed, 13 insertions, 14 deletions
diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim index a3dfd43a1..674fdddd2 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -39,16 +39,22 @@ template rawGetKnownHCImpl() {.dirty.} = h = nextTry(h, maxHash(t)) result = -1 - h # < 0 => MISSING; insert idx = -1 - result -template rawGetImpl() {.dirty.} = +template genHashImpl(key, hc: typed) = hc = hash(key) if hc == 0: # This almost never taken branch should be very predictable. hc = 314159265 # Value doesn't matter; Any non-zero favorite is fine. + +template genHash(key: typed): Hash = + var res: Hash + genHashImpl(key, res) + res + +template rawGetImpl() {.dirty.} = + genHashImpl(key, hc) rawGetKnownHCImpl() template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add - hc = hash(key) - if hc == 0: - hc = 314159265 + genHashImpl(key, hc) var h: Hash = hc and maxHash(t) while isFilled(t.data[h].hcode): h = nextTry(h, maxHash(t)) diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index bee0a41b2..dfd822852 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -224,7 +224,7 @@ template withValue*[A, B](t: var Table[A, B], key: A, iterator allValues*[A, B](t: Table[A, B]; key: A): B = ## iterates over any value in the table `t` that belongs to the given `key`. - var h: Hash = hash(key) and high(t.data) + var h: Hash = genHash(key) and high(t.data) while isFilled(t.data[h].hcode): if t.data[h].key == key: yield t.data[h].val @@ -479,7 +479,7 @@ proc clear*[A, B](t: var OrderedTableRef[A, B]) = ## Resets the table so that is is empty. clear(t[]) -template forAllOrderedPairs(yieldStmt: untyped) {.oldimmediate, dirty.} = +template forAllOrderedPairs(yieldStmt: untyped): typed {.dirty.} = var h = t.first while h >= 0: var nxt = t.data[h].next @@ -674,13 +674,6 @@ proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = ## returns the number of keys in `t`. result = t.counter -template forAllOrderedPairs(yieldStmt: untyped) {.oldimmediate, dirty.} = - var h = t.first - while h >= 0: - var nxt = t.data[h].next - if isFilled(t.data[h].hcode): yieldStmt - h = nxt - iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## iterates over any (key, value) pair in the table `t` in insertion ## order. @@ -786,7 +779,7 @@ proc sort*[A, B](t: OrderedTableRef[A, B], proc del*[A, B](t: var OrderedTable[A, B], key: A) = ## deletes `key` from ordered hash table `t`. O(n) comlexity. var prev = -1 - let hc = hash(key) + let hc = genHash(key) forAllOrderedPairs: if t.data[h].hcode == hc: if t.first == h: |