diff --git a/cpp/.traces/string-equal-with-empty b/cpp/.traces/string-equal-with-empty
index c103c72f..3a924504 100644
--- a/cpp/.traces/string-equal-with-empty
+++ b/cpp/.traces/string-equal-with-empty
@@ -22,7 +22,7 @@ after-brace/0: memory-should-contain ...
new/0: routine allocated memory from 1000 to 101000
schedule/0: string-equal-with-empty
run/0: instruction string-equal-with-empty/0
-run/0: run/42 {name: "
+run/0: run/43 {name: "
default-space:address:array:location <- new location:type, 30:literal
x:address:array:character <- new []
y:address:array:character <- new [abcd]
@@ -58,37 +58,37 @@ after-brace/0: new ...
after-brace/0: new ...
after-brace/0: string-equal ...
run/0: instruction run1001/0
-run/0: {name: "default-space", value: 0, type: 2-5-1, properties: ["default-space": "address":"array":"location"]} <- new/41 {name: "location", value: 1, type: 0, properties: ["location": "type"]}, {name: "30", value: 30, type: 0, properties: ["30": "literal"]}
+run/0: {name: "default-space", value: 0, type: 2-5-1, properties: ["default-space": "address":"array":"location"]} <- new/42 {name: "location", value: 1, type: 0, properties: ["location": "type"]}, {name: "30", value: 30, type: 0, properties: ["30": "literal"]}
mem/0: array size is 30
mem/0: new alloc: 1000
run/0: instruction run1001/1
-run/0: {name: "x", value: 1, type: 2-5-4, properties: ["x": "address":"array":"character"]} <- new/41 {name: "", value: 0, type: 0, properties: ["": "literal-string"]}
+run/0: {name: "x", value: 1, type: 2-5-4, properties: ["x": "address":"array":"character"]} <- new/42 {name: "", value: 0, type: 0, properties: ["": "literal-string"]}
mem/0: storing 1031 in location 1002
run/0: instruction run1001/2
-run/0: {name: "y", value: 2, type: 2-5-4, properties: ["y": "address":"array":"character"]} <- new/41 {name: "abcd", value: 0, type: 0, properties: ["abcd": "literal-string"]}
+run/0: {name: "y", value: 2, type: 2-5-4, properties: ["y": "address":"array":"character"]} <- new/42 {name: "abcd", value: 0, type: 0, properties: ["abcd#
#
# Nim's Runtime Library
# (c) Copyright 2015 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## An ``include`` file for the different table implementations.
# hcode for real keys cannot be zero. hcode==0 signifies an empty slot. These
# two procs retain clarity of that encoding without the space cost of an enum.
proc isEmpty(hcode: Hash): bool {.inline.} =
result = hcode == 0
proc isFilled(hcode: Hash): bool {.inline.} =
result = hcode != 0
const
growthFactor = 2
proc mustRehash(length, counter: int): bool {.inline.} =
assert(length > counter)
result = (length * 2 < counter * 3) or (length - counter < 4)
proc nextTry(h, maxHash: Hash): Hash {.inline.} =
result = (h + 1) and maxHash
template rawGetKnownHCImpl() {.dirty.} =
var h: Hash = hc and maxHash(t) # start with real hash value
while isFilled(t.data[h].hcode):
# Compare hc THEN key with boolean short circuit. This makes the common case
# zero ==key's for missing (e.g.inserts) and exactly one ==key for present.
# It does slow down succeeding lookups by one extra Hash cmp&and..usually
# just a few clock cycles, generally worth it for any non-integer-like A.
if t.data[h].hcode == hc and t.data[h].key == key:
return h
h = nextTry(h, maxHash(t))
result = -1 - h # < 0 => MISSING; insert idx = -1 - result
template rawGetImpl() {.dirty.} =
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.
rawGetKnownHCImpl()
template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add
hc = hash(key)
if hc == 0:
hc = 314159265
var h: Hash = hc and maxHash(t)
while isFilled(t.data[h].hcode):
h = nextTry(h, maxHash(t))
result = h
template rawInsertImpl() {.dirty.} =
data[h].key = key
data[h].val = val
data[h].hcode = hc
proc rawGetKnownHC[X, A](t: X, key: A, hc: Hash): int {.inline.} =
rawGetKnownHCImpl()
proc rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline.} =
rawGetDeepImpl()
proc rawGet[X, A](t: X, key: A, hc: var Hash): int {.inline.} =
rawGetImpl()
proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B],
key: A, val: B, hc: Hash, h: Hash) =
rawInsertImpl()
template addImpl(enlarge) {.dirty.} =
if mustRehash(t.dataLen, t.counter): enlarge(t)
var hc: Hash
var j = rawGetDeep(t, key, hc)
rawInsert(t, t.data, key, val, hc, j)
inc(t.counter)
template maybeRehashPutImpl(enlarge) {.oldimmediate, dirty.} =
if mustRehash(t.dataLen, t.counter):
enlarge(t)
index = rawGetKnownHC(t, key, hc)
index = -1 - index # important to transform for mgetOrPutImpl
rawInsert(t, t.data, key, val, hc, index)
inc(t.counter)
template putImpl(enlarge) {.oldimmediate, dirty.} =
var hc: Hash
var index = rawGet(t, key, hc)
if index >= 0: t.data[index].val = val
else: maybeRehashPutImpl(enlarge)
template mgetOrPutImpl(enlarge) {.dirty.} =
var hc: Hash
var index = rawGet(t, key, hc)
if index < 0:
# not present: insert (flipping index)
maybeRehashPutImpl(enlarge)
# either way return modifiable val
result = t.data[index].val
template hasKeyOrPutImpl(enlarge) {.dirty.} =
var hc: Hash
var index = rawGet(t, key, hc)
if index < 0:
result = false
maybeRehashPutImpl(enlarge)
else: result = true
proc default[T](t: typedesc[T]): T {.inline.} = discard
template delImpl() {.dirty.} =
var hc: Hash
var i = rawGet(t, key, hc)
let msk = maxHash(t)
if i >= 0:
t.data[i].hcode = 0
t.data[i].key = default(type(t.data[i].key))
t.data[i].val = default(type(t.data[i].val))
dec(t.counter)
block outer:
while true: # KnuthV3 Algo6.4R adapted for i=i+1 instead of i=i-1
var j = i # The correctness of this depends on (h+1) in nextTry,
var r = j # though may be adaptable to other simple sequences.
t.data[i].hcode = 0 # mark current EMPTY
t.data[i].key = default(type(t.data[i].key))
t.data[i].val = default(type(t.data[i].val))
while true:
i = (i + 1) and msk # increment mod table size
if isEmpty(t.data[i].hcode): # end of collision cluster; So all done
break outer
r = t.data[i].hcode and msk # "home" location of key@i
if not ((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)):
break
when defined(js):
t.data[j] = t.data[i]
else:
shallowCopy(t.data[j], t.data[i]) # data[j] will be marked EMPTY next loop
template clearImpl() {.dirty.} =
for i in 0 .. <t.data.len:
when compiles(t.data[i].hcode): # CountTable records don't contain a hcode
t.data[i].hcode = 0
t.data[i].key = default(type(t.data[i].key))
t.data[i].val = default(type(t.data[i].val))
t.counter = 0
|