diff options
Diffstat (limited to 'lib/pure/collections')
| -rw-r--r-- | lib/pure/collections/sharedstrings.nim | 154 | ||||
| -rw-r--r-- | lib/pure/collections/sharedtables.nim | 105 | ||||
| -rw-r--r-- | lib/pure/collections/tableimpl.nim | 132 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 217 |
4 files changed, 440 insertions, 168 deletions
diff --git a/lib/pure/collections/sharedstrings.nim b/lib/pure/collections/sharedstrings.nim new file mode 100644 index 000000000..10ab30767 --- /dev/null +++ b/lib/pure/collections/sharedstrings.nim @@ -0,0 +1,154 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2015 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Shared string support for Nim. + +const ArrayDummySize = when defined(cpu16): 10_000 else: 100_000_000 + +type + UncheckedCharArray {.unchecked.} = array[0..ArrayDummySize, char] + +type + Buffer = ptr object + refcount: int + capacity, realLen: int + data: UncheckedCharArray + + SharedString* = object ## A string that can be shared. Slicing is O(1). + buffer: Buffer + first, len: int + +proc decRef(b: Buffer) {.inline.} = + if atomicDec(b.refcount) <= 0: + deallocShared(b) + +proc incRef(b: Buffer) {.inline.} = + atomicInc(b.refcount) + +{.experimental.} + +proc `=destroy`*(s: SharedString) = + #echo "destroyed" + if not s.buffer.isNil: + decRef(s.buffer) + +when false: + proc `=`*(dest: var SharedString; src: SharedString) = + incRef(src.buffer) + if not dest.buffer.isNil: + decRef(dest.buffer) + dest.buffer = src.buffer + dest.first = src.first + dest.len = src.len + +proc len*(s: SharedString): int = s.len + +proc `[]`*(s: SharedString; i: Natural): char = + if i < s.len: result = s.buffer.data[i+s.first] + else: raise newException(IndexError, "index out of bounds") + +proc `[]=`*(s: var SharedString; i: Natural; value: char) = + if i < s.len: s.buffer.data[i+s.first] = value + else: raise newException(IndexError, "index out of bounds") + +proc `[]`*(s: SharedString; ab: Slice[int]): SharedString = + #incRef(src.buffer) + if ab.a < s.len: + result.buffer = s.buffer + result.first = ab.a + result.len = min(s.len, ab.b - ab.a + 1) + # else: produce empty string ;-) + +proc newBuffer(cap, len: int): Buffer = + assert cap >= len + result = cast[Buffer](allocShared0(sizeof(int)*3 + cap)) + result.refcount = 0 + result.capacity = cap + result.realLen = len + +proc newSharedString*(len: Natural): SharedString = + if len != 0: + # optimization: Don't have an underlying buffer when 'len == 0' + result.buffer = newBuffer(len, len) + result.first = 0 + result.len = len + +proc newSharedString*(s: string): SharedString = + let len = s.len + if len != 0: + # optimization: Don't have an underlying buffer when 'len == 0' + result.buffer = newBuffer(len, len) + copyMem(addr result.buffer.data[0], cstring(s), s.len) + result.first = 0 + result.len = len + +when declared(atomicLoadN): + template load(x): expr = atomicLoadN(addr x, ATOMIC_SEQ_CST) +else: + # XXX Fixme + template load(x): expr = x + +proc add*(s: var SharedString; t: cstring; len: Natural) = + if len == 0: return + let newLen = s.len + len + if s.buffer.isNil: + s.buffer = newBuffer(len, len) + copyMem(addr s.buffer.data[0], t, len) + s.len = len + elif newLen >= s.buffer.capacity or s.first != 0 or + s.len != s.buffer.realLen or load(s.buffer.refcount) > 1: + let oldBuf = s.buffer + s.buffer = newBuffer(max(s.buffer.capacity * 3 div 2, newLen), newLen) + copyMem(addr s.buffer.data[0], addr oldBuf.data[s.first], s.len) + copyMem(addr s.buffer.data[s.len], t, len) + decRef(oldBuf) + else: + copyMem(addr s.buffer.data[s.len], t, len) + s.buffer.realLen += len + s.len += len + +proc add*(s: var SharedString; t: string) = + s.add(t.cstring, t.len) + +proc rawData*(s: var SharedString): pointer = + if s.buffer.isNil: result = nil + else: result = addr s.buffer.data[s.first] + +proc add*(s: var SharedString; t: SharedString) = + if t.buffer.isNil: return + s.add(cast[cstring](addr s.buffer.data[s.first]), t.len) + +proc `$`*(s: SharedString): string = + result = newString(s.len) + if s.len > 0: + copyMem(addr result[0], addr s.buffer.data[s.first], s.len) + +proc `==`*(s: SharedString; t: string): bool = + if s.buffer.isNil: result = t.len == 0 + else: result = t.len == s.len and equalMem(addr s.buffer.data[s.first], + cstring(t), t.len) + +proc `==`*(s, t: SharedString): bool = + if s.buffer.isNil: result = t.len == 0 + else: result = t.len == s.len and equalMem(addr s.buffer.data[s.first], + addr t.buffer.data[t.first], t.len) + +iterator items*(s: SharedString): char = + let buf = s.buffer.data + let x = s.first + if buf != nil: + for i in 0..<s.len: + yield buf[i+x] + +import hashes + +proc hash*(s: SharedString): THash = + var h: THash = 0 + for x in s: h = h !& x.hash + result = !$h diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim new file mode 100644 index 000000000..2abc314d7 --- /dev/null +++ b/lib/pure/collections/sharedtables.nim @@ -0,0 +1,105 @@ +# +# +# Nim's Runtime Library +# (c) Copyright 2015 Andreas Rumpf +# +# See the file "copying.txt", included in this +# distribution, for details about the copyright. +# + +## Shared table support for Nim. Use plain old non GC'ed keys and values or +## you'll be in trouble. Uses a single lock to protect the table, lockfree +## implementations welcome but if lock contention is so high that you need a +## lockfree hash table, you're doing it wrong. + +import + hashes, math, locks + +type + KeyValuePair[A, B] = tuple[hcode: THash, key: A, val: B] + KeyValuePairSeq[A, B] = ptr array[10_000_000, KeyValuePair[A, B]] + SharedTable* [A, B] = object ## generic hash SharedTable + data: KeyValuePairSeq[A, B] + counter, dataLen: int + lock: TLock + +template maxHash(t): expr = t.dataLen-1 + +include tableimpl + +proc enlarge[A, B](t: var SharedTable[A, B]) = + let oldSize = t.dataLen + let size = oldSize * growthFactor + var n = cast[KeyValuePairSeq[A, B]](allocShared0( + sizeof(KeyValuePair[A, B]) * size)) + t.dataLen = size + swap(t.data, n) + for i in 0..<oldSize: + if isFilled(n[i].hcode): + var j = -1 - rawGetKnownHC(t, n[i].key, n[i].hcode) + rawInsert(t, t.data, n[i].key, n[i].val, n[i].hcode, j) + deallocShared(n) + +template withLock(t, x: untyped) = + acquire(t.lock) + x + release(t.lock) + +proc mget*[A, B](t: var SharedTable[A, B], key: A): var B = + ## retrieves the value at ``t[key]``. The value can be modified. + ## If `key` is not in `t`, the ``KeyError`` exception is raised. + withLock t: + var hc: THash + var index = rawGet(t, key, hc) + let hasKey = index >= 0 + if hasKey: result = t.data[index].val + if not hasKey: + when compiles($key): + raise newException(KeyError, "key not found: " & $key) + else: + raise newException(KeyError, "key not found") + +proc mgetOrPut*[A, B](t: var SharedTable[A, B], key: A, val: B): var B = + ## retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## returning a value which can be modified. **Note**: This is inherently + ## unsafe in the context of multi-threading since it returns a pointer + ## to ``B``. + withLock t: + mgetOrPutImpl(enlarge) + +proc hasKeyOrPut*[A, B](t: var SharedTable[A, B], key: A, val: B): bool = + ## returns true iff `key` is in the table, otherwise inserts `value`. + withLock t: + hasKeyOrPutImpl(enlarge) + +proc `[]=`*[A, B](t: var SharedTable[A, B], key: A, val: B) = + ## puts a (key, value)-pair into `t`. + withLock t: + putImpl(enlarge) + +proc add*[A, B](t: var SharedTable[A, B], key: A, val: B) = + ## puts a new (key, value)-pair into `t` even if ``t[key]`` already exists. + withLock t: + addImpl(enlarge) + +proc del*[A, B](t: var SharedTable[A, B], key: A) = + ## deletes `key` from hash table `t`. + withLock t: + delImpl() + +proc initSharedTable*[A, B](initialSize=64): SharedTable[A, B] = + ## creates a new hash table that is empty. + ## + ## `initialSize` needs to be a power of two. If you need to accept runtime + ## values for this you could use the ``nextPowerOfTwo`` proc from the + ## `math <math.html>`_ module or the ``rightSize`` proc from this module. + assert isPowerOfTwo(initialSize) + result.counter = 0 + result.dataLen = initialSize + result.data = cast[KeyValuePairSeq[A, B]](allocShared0( + sizeof(KeyValuePair[A, B]) * initialSize)) + initLock result.lock + +proc deinitSharedTable*[A, B](t: var SharedTable[A, B]) = + deallocShared(t.data) + deinitLock t.lock 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 diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index a9357ce67..c802d0221 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -68,65 +68,20 @@ import hashes, math -{.pragma: myShallow.} - type KeyValuePair[A, B] = tuple[hcode: THash, key: A, val: B] KeyValuePairSeq[A, B] = seq[KeyValuePair[A, B]] - Table* {.myShallow.}[A, B] = object ## generic hash table + Table*[A, B] = object ## generic hash table data: KeyValuePairSeq[A, B] counter: int TableRef*[A,B] = ref Table[A, B] {.deprecated: [TTable: Table, PTable: TableRef].} -when not defined(nimhygiene): - {.pragma: dirty.} - -# 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 - -proc len*[A, B](t: Table[A, B]): int = - ## returns the number of keys in `t`. - result = t.counter - -iterator pairs*[A, B](t: Table[A, B]): (A, B) = - ## iterates over any (key, value) pair in the table `t`. - for h in 0..high(t.data): - if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) - -iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = - ## iterates over any (key, value) pair in the table `t`. The values - ## can be modified. - for h in 0..high(t.data): - if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) - -iterator keys*[A, B](t: Table[A, B]): A = - ## iterates over any key in the table `t`. - for h in 0..high(t.data): - if isFilled(t.data[h].hcode): yield t.data[h].key - -iterator values*[A, B](t: Table[A, B]): B = - ## iterates over any value in the table `t`. - for h in 0..high(t.data): - if isFilled(t.data[h].hcode): yield t.data[h].val - -iterator mvalues*[A, B](t: var Table[A, B]): var B = - ## iterates over any value in the table `t`. The values can be modified. - for h in 0..high(t.data): - if isFilled(t.data[h].hcode): yield t.data[h].val - -const - growthFactor = 2 +template maxHash(t): expr {.immediate.} = high(t.data) +template dataLen(t): expr = len(t.data) -proc mustRehash(length, counter: int): bool {.inline.} = - assert(length > counter) - result = (length * 2 < counter * 3) or (length - counter < 4) +include tableimpl proc rightSize*(count: Natural): int {.inline.} = ## Return the value of `initialSize` to support `count` items. @@ -137,49 +92,9 @@ proc rightSize*(count: Natural): int {.inline.} = ## Internally, we want mustRehash(rightSize(x), x) == false. result = nextPowerOfTwo(count * 3 div 2 + 4) -proc nextTry(h, maxHash: THash): THash {.inline.} = - result = (h + 1) and maxHash - -template rawGetKnownHCImpl() {.dirty.} = - var h: THash = hc and high(t.data) # 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, high(t.data)) - 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 high(t.data) - while isFilled(t.data[h].hcode): - h = nextTry(h, high(t.data)) - result = h - -template rawInsertImpl() {.dirty.} = - data[h].key = key - data[h].val = val - data[h].hcode = hc - -proc rawGetKnownHC[A, B](t: Table[A, B], key: A, hc: THash): int {.inline.} = - rawGetKnownHCImpl() - -proc rawGetDeep[A, B](t: Table[A, B], key: A, hc: var THash): int {.inline.} = - rawGetDeepImpl() - -proc rawGet[A, B](t: Table[A, B], key: A, hc: var THash): int {.inline.} = - rawGetImpl() +proc len*[A, B](t: Table[A, B]): int = + ## returns the number of keys in `t`. + result = t.counter proc `[]`*[A, B](t: Table[A, B], key: A): B = ## retrieves the value at ``t[key]``. If `key` is not in `t`, @@ -215,9 +130,35 @@ proc hasKey*[A, B](t: Table[A, B], key: A): bool = var hc: THash result = rawGet(t, key, hc) >= 0 -proc rawInsert[A, B](t: var Table[A, B], data: var KeyValuePairSeq[A, B], - key: A, val: B, hc: THash, h: THash) = - rawInsertImpl() +iterator pairs*[A, B](t: Table[A, B]): (A, B) = + ## iterates over any (key, value) pair in the table `t`. + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) + +iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = + ## iterates over any (key, value) pair in the table `t`. The values + ## can be modified. + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) + +iterator keys*[A, B](t: Table[A, B]): A = + ## iterates over any key in the table `t`. + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield t.data[h].key + +iterator values*[A, B](t: Table[A, B]): B = + ## iterates over any value in the table `t`. + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield t.data[h].val + +iterator mvalues*[A, B](t: var Table[A, B]): var B = + ## iterates over any value in the table `t`. The values can be modified. + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield t.data[h].val + +proc del*[A, B](t: var Table[A, B], key: A) = + ## deletes `key` from hash table `t`. + delImpl() proc enlarge[A, B](t: var Table[A, B]) = var n: KeyValuePairSeq[A, B] @@ -228,81 +169,26 @@ proc enlarge[A, B](t: var Table[A, B]) = var j = -1 - rawGetKnownHC(t, n[i].key, n[i].hcode) rawInsert(t, t.data, n[i].key, n[i].val, n[i].hcode, j) -template addImpl() {.dirty.} = - if mustRehash(len(t.data), 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() {.dirty.} = - if mustRehash(len(t.data), 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() {.dirty.} = - var hc: THash - var index = rawGet(t, key, hc) - if index >= 0: t.data[index].val = val - else: maybeRehashPutImpl() - -template mgetOrPutImpl() {.dirty.} = - var hc: THash - var index = rawGet(t, key, hc) - if index < 0: maybeRehashPutImpl() # not present: insert (flipping index) - result = t.data[index].val # either way return modifiable val - -template hasKeyOrPutImpl() {.dirty.} = - var hc: THash - var index = rawGet(t, key, hc) - if index < 0: - result = false - maybeRehashPutImpl() - else: result = true - proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = ## retrieves value at ``t[key]`` or puts ``val`` if not present, either way ## returning a value which can be modified. - mgetOrPutImpl() + mgetOrPutImpl(enlarge) proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = ## returns true iff `key` is in the table, otherwise inserts `value`. - hasKeyOrPutImpl() + hasKeyOrPutImpl(enlarge) proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) = ## puts a (key, value)-pair into `t`. - putImpl() + putImpl(enlarge) proc add*[A, B](t: var Table[A, B], key: A, val: B) = ## puts a new (key, value)-pair into `t` even if ``t[key]`` already exists. - addImpl() - -template doWhile(a: expr, b: stmt): stmt = - while true: - b - if not a: break + addImpl(enlarge) -proc del*[A, B](t: var Table[A, B], key: A) = - ## deletes `key` from hash table `t`. - var hc: THash - var i = rawGet(t, key, hc) - let msk = high(t.data) - if i >= 0: - t.data[i].hcode = 0 - dec(t.counter) - 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 - doWhile ((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)): - i = (i + 1) and msk # increment mod table size - if isEmpty(t.data[i].hcode): # end of collision cluster; So all done - return - r = t.data[i].hcode and msk # "home" location of key@i - shallowCopy(t.data[j], t.data[i]) # data[j] will be marked EMPTY next loop +proc len*[A, B](t: TableRef[A, B]): int = + ## returns the number of keys in `t`. + result = t.counter proc initTable*[A, B](initialSize=64): Table[A, B] = ## creates a new hash table that is empty. @@ -356,10 +242,6 @@ proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = for item in collection: result[index(item)] = item -proc len*[A, B](t: TableRef[A, B]): int = - ## returns the number of keys in `t`. - result = t.counter - iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## iterates over any (key, value) pair in the table `t`. for h in 0..high(t.data): @@ -454,8 +336,7 @@ type OrderedKeyValuePair[A, B] = tuple[ hcode: THash, next: int, key: A, val: B] OrderedKeyValuePairSeq[A, B] = seq[OrderedKeyValuePair[A, B]] - OrderedTable* {. - myShallow.}[A, B] = object ## table that remembers insertion order + OrderedTable* [A, B] = object ## table that remembers insertion order data: OrderedKeyValuePairSeq[A, B] counter, first, last: int OrderedTableRef*[A, B] = ref OrderedTable[A, B] @@ -557,20 +438,20 @@ proc enlarge[A, B](t: var OrderedTable[A, B]) = proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: B) = ## puts a (key, value)-pair into `t`. - putImpl() + putImpl(enlarge) proc add*[A, B](t: var OrderedTable[A, B], key: A, val: B) = ## puts a new (key, value)-pair into `t` even if ``t[key]`` already exists. - addImpl() + addImpl(enlarge) proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = ## retrieves value at ``t[key]`` or puts ``value`` if not present, either way ## returning a value which can be modified. - mgetOrPutImpl() + mgetOrPutImpl(enlarge) proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = ## returns true iff `key` is in the table, otherwise inserts `value`. - hasKeyOrPutImpl() + hasKeyOrPutImpl(enlarge) proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = ## creates a new ordered hash table that is empty. @@ -741,7 +622,7 @@ proc sort*[A, B](t: OrderedTableRef[A, B], # ------------------------------ count tables ------------------------------- type - CountTable* {.myShallow.}[ + CountTable* [ A] = object ## table that counts the number of each key data: seq[tuple[key: A, val: int]] counter: int |