diff options
| -rw-r--r-- | changelog.md | 1 | ||||
| -rw-r--r-- | lib/pure/collections/sharedtables.nim | 8 | ||||
| -rw-r--r-- | lib/pure/collections/tableimpl.nim | 23 | ||||
| -rw-r--r-- | lib/pure/collections/tables.nim | 52 |
4 files changed, 42 insertions, 42 deletions
diff --git a/changelog.md b/changelog.md index 93c0797d3..d9eaa5823 100644 --- a/changelog.md +++ b/changelog.md @@ -140,6 +140,7 @@ - Tables, HashSets, SharedTables and deques don't require anymore that the passed initial size must be a power of two - this is done internally. Proc `rightSize` for Tables and HashSets is deprecated, as it is not needed anymore. + `CountTable.inc` takes `val: int` again not `val: Positive`; I.e. it can "count down" again. - Removed deprecated symbols from `macros` module, deprecated as far back as `0.15`. diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim index cbd922db7..af498d70d 100644 --- a/lib/pure/collections/sharedtables.nim +++ b/lib/pure/collections/sharedtables.nim @@ -138,6 +138,10 @@ proc hasKeyOrPut*[A, B](t: var SharedTable[A, B], key: A, val: B): bool = withLock t: hasKeyOrPutImpl(enlarge) +template tabMakeEmpty(i) = t.data[i].hcode = 0 +template tabCellEmpty(i) = isEmpty(t.data[i].hcode) +template tabCellHash(i) = t.data[i].hcode + proc withKey*[A, B](t: var SharedTable[A, B], key: A, mapper: proc(key: A, val: var B, pairExists: var bool)) = ## Computes a new mapping for the ``key`` with the specified ``mapper`` @@ -179,7 +183,7 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, if pairExists: mapper(t.data[index].key, t.data[index].val, pairExists) if not pairExists: - delImplIdx(t, index) + delImplIdx(t, index, tabMakeEmpty, tabCellEmpty, tabCellHash) else: var val: B mapper(key, val, pairExists) @@ -200,7 +204,7 @@ proc add*[A, B](t: var SharedTable[A, B], key: A, val: B) = proc del*[A, B](t: var SharedTable[A, B], key: A) = ## deletes `key` from hash table `t`. withLock t: - delImpl() + delImpl(tabMakeEmpty, tabCellEmpty, tabCellHash) proc len*[A, B](t: var SharedTable[A, B]): int = ## number of elements in `t` diff --git a/lib/pure/collections/tableimpl.nim b/lib/pure/collections/tableimpl.nim index b9d7c70d9..ec2806200 100644 --- a/lib/pure/collections/tableimpl.nim +++ b/lib/pure/collections/tableimpl.nim @@ -78,22 +78,22 @@ template hasKeyOrPutImpl(enlarge) {.dirty.} = maybeRehashPutImpl(enlarge) else: result = true -template delImplIdx(t, i) = +template delImplIdx(t, i, makeEmpty, cellEmpty, cellHash) = 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 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 + makeEmpty(i) # 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 + if cellEmpty(i): # end of collision cluster; So all done break outer - r = t.data[i].hcode and msk # "home" location of key@i + r = cellHash(i) and msk # initial probe index for key@slot i if not ((i >= r and r > j) or (r > j and j > i) or (j > i and i >= r)): break when defined(js): @@ -101,10 +101,19 @@ template delImplIdx(t, i) = else: t.data[j] = move(t.data[i]) # data[j] will be marked EMPTY next loop -template delImpl() {.dirty.} = +template delImpl(makeEmpty, cellEmpty, cellHash) {.dirty.} = var hc: Hash var i = rawGet(t, key, hc) - delImplIdx(t, i) + delImplIdx(t, i, makeEmpty, cellEmpty, cellHash) + +template delImplNoHCode(makeEmpty, cellEmpty, cellHash) {.dirty.} = + if t.dataLen > 0: + var i: Hash = hash(key) and maxHash(t) + while not cellEmpty(i): + if t.data[i].key == key: + delImplIdx(t, i, makeEmpty, cellEmpty, cellHash) + break + i = nextTry(i, maxHash(t)) template clearImpl() {.dirty.} = for i in 0 ..< t.dataLen: diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index b1354eec3..3aa3af4e9 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -494,6 +494,10 @@ proc add*[A, B](t: var Table[A, B], key: A, val: B) {.deprecated: ## (key, value) pair in the table without introducing duplicates. addImpl(enlarge) +template tabMakeEmpty(i) = t.data[i].hcode = 0 +template tabCellEmpty(i) = isEmpty(t.data[i].hcode) +template tabCellHash(i) = t.data[i].hcode + proc del*[A, B](t: var Table[A, B], key: A) = ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. ## @@ -507,7 +511,7 @@ proc del*[A, B](t: var Table[A, B], key: A) = a.del('z') doAssert a == {'b': 9, 'c': 13}.toTable - delImpl() + delImpl(tabMakeEmpty, tabCellEmpty, tabCellHash) proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool = ## Deletes the ``key`` from the table. @@ -535,7 +539,7 @@ proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool = result = index >= 0 if result: val = move(t.data[index].val) - delImplIdx(t, index) + delImplIdx(t, index, tabMakeEmpty, tabCellEmpty, tabCellHash) proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool {.inline.} = ## Alias for: @@ -2199,19 +2203,6 @@ proc enlarge[A](t: var CountTable[A]) = if t.data[i].val != 0: ctRawInsert(t, n, move t.data[i].key, move t.data[i].val) swap(t.data, n) -proc remove[A](t: var CountTable[A], key: A) = - var n: seq[tuple[key: A, val: int]] - newSeq(n, len(t.data)) - var removed: bool - for i in countup(0, high(t.data)): - if t.data[i].val != 0: - if t.data[i].key != key: - ctRawInsert(t, n, move t.data[i].key, move t.data[i].val) - else: - removed = true - swap(t.data, n) - if removed: dec(t.counter) - proc rawGet[A](t: CountTable[A], key: A): int = if t.data.len == 0: return -1 @@ -2225,7 +2216,7 @@ template ctget(t, key, default: untyped): untyped = var index = rawGet(t, key) result = if index >= 0: t.data[index].val else: default -proc inc*[A](t: var CountTable[A], key: A, val: Positive = 1) +proc inc*[A](t: var CountTable[A], key: A, val = 1) # ---------------------------------------------------------------------- @@ -2262,6 +2253,10 @@ proc `[]`*[A](t: CountTable[A], key: A): int = assert(not t.isSorted, "CountTable must not be used after sorting") ctget(t, key, 0) +template cntMakeEmpty(i) = t.data[i].val = 0 +template cntCellEmpty(i) = t.data[i].val == 0 +template cntCellHash(i) = hash(t.data[i].key) + proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = ## Inserts a ``(key, value)`` pair into ``t``. ## @@ -2272,7 +2267,7 @@ proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = assert(not t.isSorted, "CountTable must not be used after sorting") assert val >= 0 if val == 0: - t.remove(key) + delImplNoHCode(cntMakeEmpty, cntCellEmpty, cntCellHash) else: let h = rawGet(t, key) if h >= 0: @@ -2280,11 +2275,8 @@ proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = else: insertImpl() -proc inc*[A](t: var CountTable[A], key: A, val: Positive = 1) = +proc inc*[A](t: var CountTable[A], key: A, val = 1) = ## Increments ``t[key]`` by ``val`` (default: 1). - ## - ## ``val`` must be a positive number. If you need to decrement a value, - ## use a regular ``Table`` instead. runnableExamples: var a = toCountTable("aab") a.inc('a') @@ -2295,9 +2287,11 @@ proc inc*[A](t: var CountTable[A], key: A, val: Positive = 1) = var index = rawGet(t, key) if index >= 0: inc(t.data[index].val, val) - if t.data[index].val == 0: dec(t.counter) + if t.data[index].val == 0: + delImplIdx(t, index, cntMakeEmpty, cntCellEmpty, cntCellHash) else: - insertImpl() + if val != 0: + insertImpl() proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) @@ -2358,8 +2352,6 @@ proc len*[A](t: CountTable[A]): int = proc del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} = ## Deletes ``key`` from table ``t``. Does nothing if the key does not exist. ## - ## O(n) complexity. - ## ## See also: ## * `pop proc<#pop,CountTable[A],A,int>`_ ## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table @@ -2372,7 +2364,7 @@ proc del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} = a.del('c') assert a == toCountTable("aa") - remove(t, key) + delImplNoHCode(cntMakeEmpty, cntCellEmpty, cntCellHash) proc pop*[A](t: var CountTable[A], key: A, val: var int): bool {.since: (1, 1).} = ## Deletes the ``key`` from the table. @@ -2380,8 +2372,6 @@ proc pop*[A](t: var CountTable[A], key: A, val: var int): bool {.since: (1, 1).} ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is ## unchanged. ## - ## O(n) complexity. - ## ## See also: ## * `del proc<#del,CountTable[A],A>`_ ## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table @@ -2398,7 +2388,7 @@ proc pop*[A](t: var CountTable[A], key: A, val: var int): bool {.since: (1, 1).} result = index >= 0 if result: val = move(t.data[index].val) - remove(t, key) + delImplIdx(t, index, cntMakeEmpty, cntCellEmpty, cntCellHash) proc clear*[A](t: var CountTable[A]) = ## Resets the table so that it is empty. @@ -2686,8 +2676,6 @@ proc len*[A](t: CountTableRef[A]): int = proc del*[A](t: CountTableRef[A], key: A) {.since: (1, 1).} = ## Deletes ``key`` from table ``t``. Does nothing if the key does not exist. ## - ## O(n) complexity. - ## ## See also: ## * `pop proc<#pop,CountTableRef[A],A,int>`_ ## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table @@ -2699,8 +2687,6 @@ proc pop*[A](t: CountTableRef[A], key: A, val: var int): bool {.since: (1, 1).} ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is ## unchanged. ## - ## O(n) complexity. - ## ## See also: ## * `del proc<#del,CountTableRef[A],A>`_ ## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table |