1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
|
#
#
# 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.
include hashcommon
template rawGetDeepImpl() {.dirty.} = # Search algo for unconditional add
genHashImpl(key, hc)
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 rawGetDeep[X, A](t: X, key: A, hc: var Hash): int {.inline.} =
rawGetDeepImpl()
proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B],
key: A, val: B, hc: Hash, h: Hash) =
rawInsertImpl()
template checkIfInitialized() =
when compiles(defaultInitialSize):
if t.dataLen == 0:
initImpl(t, defaultInitialSize)
template addImpl(enlarge) {.dirty.} =
checkIfInitialized()
if mustRehash(t): 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) {.dirty.} =
checkIfInitialized()
if mustRehash(t):
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) {.dirty.} =
checkIfInitialized()
var hc: Hash
var index = rawGet(t, key, hc)
if index >= 0: t.data[index].val = val
else: maybeRehashPutImpl(enlarge)
template mgetOrPutImpl(enlarge) {.dirty.} =
checkIfInitialized()
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.} =
checkIfInitialized()
var hc: Hash
var index = rawGet(t, key, hc)
if index < 0:
result = false
maybeRehashPutImpl(enlarge)
else: result = true
template delImplIdx(t, i) =
let msk = maxHash(t)
if i >= 0:
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:
t.data[j] = move(t.data[i]) # data[j] will be marked EMPTY next loop
template delImpl() {.dirty.} =
var hc: Hash
var i = rawGet(t, key, hc)
delImplIdx(t, i)
template clearImpl() {.dirty.} =
for i in 0 ..< t.dataLen:
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
template ctAnd(a, b): bool =
when a:
when b: true
else: false
else: false
template initImpl(result: typed, size: int) =
when ctAnd(declared(SharedTable), type(result) is SharedTable):
init(result, size)
else:
assert isPowerOfTwo(size)
result.counter = 0
newSeq(result.data, size)
when compiles(result.first):
result.first = -1
result.last = -1
template insertImpl() = # for CountTable
if t.dataLen == 0: initImpl(t, defaultInitialSize)
if mustRehash(t): enlarge(t)
ctRawInsert(t, t.data, key, val)
inc(t.counter)
template getOrDefaultImpl(t, key): untyped =
mixin rawGet
var hc: Hash
var index = rawGet(t, key, hc)
if index >= 0: result = t.data[index].val
template getOrDefaultImpl(t, key, default: untyped): untyped =
mixin rawGet
var hc: Hash
var index = rawGet(t, key, hc)
result = if index >= 0: t.data[index].val else: default
template dollarImpl(): untyped {.dirty.} =
if t.len == 0:
result = "{:}"
else:
result = "{"
for key, val in pairs(t):
if result.len > 1: result.add(", ")
result.addQuoted(key)
result.add(": ")
result.addQuoted(val)
result.add("}")
template equalsImpl(s, t: typed) =
if s.counter == t.counter:
# different insertion orders mean different 'data' seqs, so we have
# to use the slow route here:
for key, val in s:
if not t.hasKey(key): return false
if t.getOrDefault(key) != val: return false
return true
|