diff options
Diffstat (limited to 'lib/pure/collections/sharedtables.nim')
| -rw-r--r-- | lib/pure/collections/sharedtables.nim | 154 |
1 files changed, 86 insertions, 68 deletions
diff --git a/lib/pure/collections/sharedtables.nim b/lib/pure/collections/sharedtables.nim index 1a6148752..b474ecd31 100644 --- a/lib/pure/collections/sharedtables.nim +++ b/lib/pure/collections/sharedtables.nim @@ -14,10 +14,10 @@ ## ## Unstable API. -import - hashes, math, locks +{.deprecated.} -include "system/inclrtl" +import + std/[hashes, math, locks] type KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B] @@ -32,7 +32,7 @@ template maxHash(t): untyped = t.dataLen-1 include tableimpl template st_maybeRehashPutImpl(enlarge) {.dirty.} = - if mustRehash(t.dataLen, t.counter): + if mustRehash(t): enlarge(t) index = rawGetKnownHC(t, key, hc) index = -1 - index # important to transform for mgetOrPutImpl @@ -62,17 +62,27 @@ template withLock(t, x: untyped) = template withValue*[A, B](t: var SharedTable[A, B], key: A, value, body: untyped) = - ## retrieves the value at ``t[key]``. - ## `value` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## sharedTable.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## # value is threadsafe in block - ## value.name = "username" - ## value.uid = 1000 - ## + ## Retrieves the value at `t[key]`. + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + var table: SharedTable[string, string] + init(table) + + table["a"] = "x" + table["b"] = "y" + table["c"] = "z" + + table.withValue("a", value): + assert value[] == "x" + + table.withValue("b", value): + value[] = "modified" + + table.withValue("b", value): + assert value[] == "modified" + + table.withValue("nonexistent", value): + assert false # not called acquire(t.lock) try: var hc: Hash @@ -86,20 +96,33 @@ template withValue*[A, B](t: var SharedTable[A, B], key: A, template withValue*[A, B](t: var SharedTable[A, B], key: A, value, body1, body2: untyped) = - ## retrieves the value at ``t[key]``. - ## `value` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## sharedTable.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## # value is threadsafe in block - ## value.name = "username" - ## value.uid = 1000 - ## do: - ## # block is executed when ``key`` not in ``t`` - ## raise newException(KeyError, "Key not found") - ## + ## Retrieves the value at `t[key]`. + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + var table: SharedTable[string, string] + init(table) + + table["a"] = "x" + table["b"] = "y" + table["c"] = "z" + + + table.withValue("a", value): + value[] = "m" + + var flag = false + table.withValue("d", value): + discard value + doAssert false + do: # if "d" notin table + flag = true + + if flag: + table["d"] = "n" + + assert table.mget("a") == "m" + assert table.mget("d") == "n" + acquire(t.lock) try: var hc: Hash @@ -114,8 +137,8 @@ template withValue*[A, B](t: var SharedTable[A, B], key: A, 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. + ## 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: Hash var index = rawGet(t, key, hc) @@ -128,44 +151,47 @@ proc mget*[A, B](t: var SharedTable[A, B], key: A): var B = 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 + ## 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``. + ## 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`. + ## Returns true if `key` is in the table, otherwise inserts `value`. 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`` + ## Computes a new mapping for the `key` with the specified `mapper` ## procedure. ## - ## The ``mapper`` takes 3 arguments: + ## The `mapper` takes 3 arguments: ## - ## 1. ``key`` - the current key, if it exists, or the key passed to - ## ``withKey`` otherwise; - ## 2. ``val`` - the current value, if the key exists, or default value + ## 1. `key` - the current key, if it exists, or the key passed to + ## `withKey` otherwise; + ## 2. `val` - the current value, if the key exists, or default value ## of the type otherwise; - ## 3. ``pairExists`` - ``true`` if the key exists, ``false`` otherwise. + ## 3. `pairExists` - `true` if the key exists, `false` otherwise. ## - ## The ``mapper`` can can modify ``val`` and ``pairExists`` values to change + ## The `mapper` can can modify `val` and `pairExists` values to change ## the mapping of the key or delete it from the table. - ## When adding a value, make sure to set ``pairExists`` to ``true`` along - ## with modifying the ``val``. + ## When adding a value, make sure to set `pairExists` to `true` along + ## with modifying the `val`. ## ## The operation is performed atomically and other operations on the table - ## will be blocked while the ``mapper`` is invoked, so it should be short and + ## will be blocked while the `mapper` is invoked, so it should be short and ## simple. ## ## Example usage: ## - ## .. code-block:: nim - ## + ## ```nim ## # If value exists, decrement it. ## # If it becomes zero or less, delete the key ## t.withKey(1'i64) do (k: int64, v: var int, pairExists: var bool): @@ -173,6 +199,7 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, ## dec v ## if v <= 0: ## pairExists = false + ## ``` withLock t: var hc: Hash var index = rawGet(t, key, hc) @@ -181,7 +208,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) @@ -189,30 +216,31 @@ proc withKey*[A, B](t: var SharedTable[A, B], key: A, st_maybeRehashPutImpl(enlarge) proc `[]=`*[A, B](t: var SharedTable[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. + ## 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. + ## Puts a new (key, value)-pair into `t` even if `t[key]` already exists. ## This can introduce duplicate keys into the table! withLock t: addImpl(enlarge) proc del*[A, B](t: var SharedTable[A, B], key: A) = - ## deletes `key` from hash table `t`. + ## Deletes `key` from hash table `t`. + withLock t: + delImpl(tabMakeEmpty, tabCellEmpty, tabCellHash) + +proc len*[A, B](t: var SharedTable[A, B]): int = + ## Number of elements in `t`. withLock t: - delImpl() + result = t.counter -proc init*[A, B](t: var SharedTable[A, B], initialSize = 64) = - ## creates a new hash table that is empty. +proc init*[A, B](t: var SharedTable[A, B], initialSize = 32) = + ## Creates a new hash table that is empty. ## ## This proc must be called before any other usage of `t`. - ## - ## `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) + let initialSize = slotsNeeded(initialSize) t.counter = 0 t.dataLen = initialSize t.data = cast[KeyValuePairSeq[A, B]](allocShared0( @@ -222,13 +250,3 @@ proc init*[A, B](t: var SharedTable[A, B], initialSize = 64) = proc deinitSharedTable*[A, B](t: var SharedTable[A, B]) = deallocShared(t.data) deinitLock t.lock - -proc initSharedTable*[A, B](initialSize = 64): SharedTable[A, B] {.deprecated: - "use 'init' instead".} = - ## This is not posix compliant, may introduce undefined behavior. - assert isPowerOfTwo(initialSize) - result.counter = 0 - result.dataLen = initialSize - result.data = cast[KeyValuePairSeq[A, B]](allocShared0( - sizeof(KeyValuePair[A, B]) * initialSize)) - initLock result.lock |