From 21ea8e6913fbfc16192ad3fd157e8e18e559219d Mon Sep 17 00:00:00 2001
From: Araq <rumpf_a@web.de>
Date: Thu, 28 May 2015 12:49:08 +0200
Subject: some progress on making async multithreaded

---
 lib/pure/collections/tableimpl.nim | 132 +++++++++++++++++++++++++++++++++++++
 1 file changed, 132 insertions(+)
 create mode 100644 lib/pure/collections/tableimpl.nim

(limited to 'lib/pure/collections/tableimpl.nim')

diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim
new file mode 100644
index 000000000..5900864fb
--- /dev/null
+++ b/lib/pure/collections/tableimpl.nim
@@ -0,0 +1,132 @@
+#
+#
+#            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: THash): bool {.inline.} =
+  result = hcode == 0
+
+proc isFilled(hcode: THash): 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: THash): THash {.inline.} =
+  result = (h + 1) and maxHash
+
+template rawGetKnownHCImpl() {.dirty.} =
+  var h: THash = 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 THash 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: THash = 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: THash): int {.inline.} =
+  rawGetKnownHCImpl()
+
+proc rawGetDeep[X, A](t: X, key: A, hc: var THash): int {.inline.} =
+  rawGetDeepImpl()
+
+proc rawGet[X, A](t: X, key: A, hc: var THash): int {.inline.} =
+  rawGetImpl()
+
+proc rawInsert[X, A, B](t: var X, data: var KeyValuePairSeq[A, B],
+                     key: A, val: B, hc: THash, h: THash) =
+  rawInsertImpl()
+
+template addImpl(enlarge) {.dirty, immediate.} =
+  if mustRehash(t.dataLen, t.counter): enlarge(t)
+  var hc: THash
+  var j = rawGetDeep(t, key, hc)
+  rawInsert(t, t.data, key, val, hc, j)
+  inc(t.counter)
+
+template maybeRehashPutImpl(enlarge) {.dirty, immediate.} =
+  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) {.dirty, immediate.} =
+  var hc: THash
+  var index = rawGet(t, key, hc)
+  if index >= 0: t.data[index].val = val
+  else: maybeRehashPutImpl(enlarge)
+
+template mgetOrPutImpl(enlarge) {.dirty, immediate.} =
+  var hc: THash
+  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, immediate.} =
+  var hc: THash
+  var index = rawGet(t, key, hc)
+  if index < 0:
+    result = false
+    maybeRehashPutImpl(enlarge)
+  else: result = true
+
+template delImpl() {.dirty, immediate.} =
+  var hc: THash
+  var i = rawGet(t, key, hc)
+  let msk = maxHash(t)
+  if i >= 0:
+    t.data[i].hcode = 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
+        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
+        shallowCopy(t.data[j], t.data[i]) # data[j] will be marked EMPTY next loop
-- 
cgit 1.4.1-2-gfad0