std/sharedtables

  Source   Edit

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.

Unstable API.

Types

SharedTable[A; B] = object
  data: KeyValuePairSeq[A, B]
  counter, dataLen: int
  lock: Lock
generic hash SharedTable   Source   Edit

Procs

proc rightSize(count: Natural): int {.inline,
                                      deprecated: "Deprecated since 1.4.0",
                                      ...raises: [], tags: [].}
Deprecated: Deprecated since 1.4.0

It is not needed anymore because picking the correct size is done internally.

Returns the value of initialSize to support count items.

If more items are expected to be added, simply add that expected extra amount to the parameter before calling this.

  Source   Edit
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.   Source   Edit
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.   Source   Edit
proc hasKeyOrPut[A, B](t: var SharedTable[A, B]; key: A; val: B): bool
Returns true if key is in the table, otherwise inserts value.   Source   Edit
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 procedure.

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 of the type otherwise;
  3. pairExists - true if the key exists, false otherwise.

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.

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 simple.

Example usage:

# 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):
  if pairExists:
    dec v
    if v <= 0:
      pairExists = false
  Source   Edit
proc `[]=`[A, B](t: var SharedTable[A, B]; key: A; val: B)
Puts a (key, value)-pair into t.   Source   Edit
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. This can introduce duplicate keys into the table!   Source   Edit
proc del[A, B](t: var SharedTable[A, B]; key: A)
Deletes key from hash table t.   Source   Edit
proc len[A, B](t: var SharedTable[A, B]): int
Number of elements in t.   Source   Edit
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.

  Source   Edit
proc deinitSharedTable[A, B](t: var SharedTable[A, B])
  Source   Edit

Templates

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.

Example:

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
  Source   Edit
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.

Example:

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"
  Source   Edit