diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/pure/collections/hashtables.nim | 153 | ||||
| -rwxr-xr-x | lib/pure/strtabs.nim | 25 | ||||
| -rwxr-xr-x | lib/system.nim | 2 | ||||
| -rwxr-xr-x | lib/system/hti.nim | 4 | ||||
| -rwxr-xr-x | lib/system/repr.nim | 14 |
5 files changed, 157 insertions, 41 deletions
diff --git a/lib/pure/collections/hashtables.nim b/lib/pure/collections/hashtables.nim index 9562d3a6a..29ba6bf6f 100644 --- a/lib/pure/collections/hashtables.nim +++ b/lib/pure/collections/hashtables.nim @@ -23,21 +23,21 @@ type PHashTable*[A, B] = ref THashTable[A, B] ## use this type to declare tables -proc len*[A, B](t: PHashTable[A, B]): int = +proc len*[A, B](t: THashTable[A, B]): int = ## returns the number of keys in `t`. result = t.counter -iterator pairs*[A, B](t: PHashTable[A, B]): tuple[key: A, val: B] = +iterator pairs*[A, B](t: THashTable[A, B]): tuple[key: A, val: B] = ## iterates over any (key, value) pair in the table `t`. for h in 0..high(t.data): if t.data[h].slot == seFilled: yield (t.data[h].key, t.data[h].val) -iterator keys*[A, B](t: PHashTable[A, B]): A = +iterator keys*[A, B](t: THashTable[A, B]): A = ## iterates over any key in the table `t`. for h in 0..high(t.data): if t.data[h].slot == seFilled: yield t.data[h].key -iterator values*[A, B](t: PHashTable[A, B]): B = +iterator values*[A, B](t: THashTable[A, B]): B = ## iterates over any value in the table `t`. for h in 0..high(t.data): if t.data[h].slot == seFilled: yield t.data[h].val @@ -52,7 +52,7 @@ proc mustRehash(length, counter: int): bool {.inline.} = proc nextTry(h, maxHash: THash): THash {.inline.} = result = ((5 * h) + 1) and maxHash -proc RawGet[A, B](t: PHashTable[A, B], key: A): int = +template rawGetImpl() = var h: THash = hash(key) and high(t.data) # start with real hash value while t.data[h].slot != seEmpty: if t.data[h].key == key and t.data[h].slot == seFilled: @@ -60,7 +60,18 @@ proc RawGet[A, B](t: PHashTable[A, B], key: A): int = h = nextTry(h, high(t.data)) result = -1 -proc `[]`*[A, B](t: PHashTable[A, B], key: A): B = +template rawInsertImpl() = + var h: THash = hash(key) and high(data) + while data[h].slot == seFilled: + h = nextTry(h, high(data)) + data[h].key = key + data[h].val = val + data[h].slot = seFilled + +proc RawGet[A, B](t: THashTable[A, B], key: A): int = + rawGetImpl() + +proc `[]`*[A, B](t: THashTable[A, B], key: A): B = ## retrieves the value at ``t[key]``. If `key` is not in `t`, ## default empty value for the type `B` is returned ## and no exception is raised. One can check with ``hasKey`` whether the key @@ -68,28 +79,22 @@ proc `[]`*[A, B](t: PHashTable[A, B], key: A): B = var index = RawGet(t, key) if index >= 0: result = t.data[index].val -proc hasKey*[A, B](t: PHashTable[A, B], key: A): bool = +proc hasKey*[A, B](t: THashTable[A, B], key: A): bool = ## returns true iff `key` is in the table `t`. result = rawGet(t, key) >= 0 -proc RawInsert[A, B](t: PHashTable[A, B], data: var TKeyValuePairSeq[A, B], +proc RawInsert[A, B](t: var THashTable[A, B], data: var TKeyValuePairSeq[A, B], key: A, val: B) = - var h: THash = hash(key) and high(data) - while data[h].slot == seFilled: - h = nextTry(h, high(data)) - data[h].key = key - data[h].val = val - data[h].slot = seFilled + rawInsertImpl() -proc Enlarge[A, B](t: PHashTable[A, B]) = +proc Enlarge[A, B](t: var THashTable[A, B]) = var n: TKeyValuePairSeq[A, B] newSeq(n, len(t.data) * growthFactor) for i in countup(0, high(t.data)): if t.data[i].slot == seFilled: RawInsert(t, n, t.data[i].key, t.data[i].val) swap(t.data, n) -proc `[]=`*[A, B](t: PHashTable[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. +template PutImpl() = var index = RawGet(t, key) if index >= 0: t.data[index].val = val @@ -98,23 +103,25 @@ proc `[]=`*[A, B](t: PHashTable[A, B], key: A, val: B) = RawInsert(t, t.data, key, val) inc(t.counter) -proc del*[A, B](t: PHashTable[A, B], key: A) = +proc `[]=`*[A, B](t: var THashTable[A, B], key: A, val: B) = + ## puts a (key, value)-pair into `t`. + putImpl() + +proc del*[A, B](t: var THashTable[A, B], key: A) = ## deletes `key` from hash table `t`. var index = RawGet(t, key) if index >= 0: t.data[index].slot = seDeleted dec(t.counter) -proc newHashTable*[A, B](initialSize = 64): PHashTable[A, B] = +proc initHashTable*[A, B](initialSize = 64): THashTable[A, B] = ## creates a new string table that is empty. `initialSize` needs to be ## a power of two. assert isPowerOfTwo(initialSize) - new(result) result.counter = 0 newSeq(result.data, initialSize) -proc `$`*[A, B](t: PHashTable[A, B]): string = - ## The `$` operator for string tables. +template dollarImpl(): stmt = if t.len == 0: result = "{:}" else: @@ -126,6 +133,108 @@ proc `$`*[A, B](t: PHashTable[A, B]): string = result.add($val) result.add("}") +proc `$`*[A, B](t: THashTable[A, B]): string = + ## The `$` operator for string tables. + dollarImpl() + +# ------------------------------ ordered table ------------------------------ + +type + TOrderedKeyValuePair[A, B] = tuple[ + slot: TSlotEnum, next: int, key: A, val: B] + TOrderedKeyValuePairSeq[A, B] = seq[TOrderedKeyValuePair[A, B]] + TOrderedHashTable*[A, B] {.final.} = object + data: TOrderedKeyValuePairSeq[A, B] + counter, first, last: int + +proc len*[A, B](t: TOrderedHashTable[A, B]): int {.inline.} = + ## returns the number of keys in `t`. + result = t.counter + +template forAllOrderedPairs(yieldStmt: stmt) = + var i = t.first + while i >= 0: + var nxt = t.data[i].next + if t.data[h].slot == seFilled: yieldStmt + i = nxt + +iterator pairs*[A, B](t: TOrderedHashTable[A, B]): tuple[key: A, val: B] = + ## iterates over any (key, value) pair in the table `t` in insertion + ## order. + forAllOrderedPairs: + yield (t.data[h].key, t.data[h].val) + +iterator keys*[A, B](t: TOrderedHashTable[A, B]): A = + ## iterates over any key in the table `t` in insertion order. + forAllOrderedPairs: + yield t.data[h].key + +iterator values*[A, B](t: TOrderedHashTable[A, B]): B = + ## iterates over any value in the table `t` in insertion order. + forAllOrderedPairs: + yield t.data[h].val + +proc RawGet[A, B](t: TOrderedHashTable[A, B], key: A): int = + rawGetImpl() + +proc `[]`*[A, B](t: TOrderedHashTable[A, B], key: A): B = + ## retrieves the value at ``t[key]``. If `key` is not in `t`, + ## default empty value for the type `B` is returned + ## and no exception is raised. One can check with ``hasKey`` whether the key + ## exists. + var index = RawGet(t, key) + if index >= 0: result = t.data[index].val + +proc hasKey*[A, B](t: TOrderedHashTable[A, B], key: A): bool = + ## returns true iff `key` is in the table `t`. + result = rawGet(t, key) >= 0 + +proc RawInsert[A, B](t: TOrderedHashTable[A, B], + data: var TOrderedKeyValuePairSeq[A, B], + key: A, val: B) = + rawInsertImpl() + data[h].next = -1 + if first < 0: first = h + if last >= 0: data[last].next = h + lastEntry = h + +proc Enlarge[A, B](t: TOrderedHashTable[A, B]) = + var n: TOrderedKeyValuePairSeq[A, B] + newSeq(n, len(t.data) * growthFactor) + forAllOrderedPairs: + RawInsert(t, n, t.data[h].key, t.data[h].val) + swap(t.data, n) + +proc `[]=`*[A, B](t: TOrderedHashTable[A, B], key: A, val: B) = + ## puts a (key, value)-pair into `t`. + var index = RawGet(t, key) + if index >= 0: + t.data[index].val = val + else: + if mustRehash(len(t.data), t.counter): Enlarge(t) + RawInsert(t, t.data, key, val) + inc(t.counter) + +proc del*[A, B](t: TOrderedHashTable[A, B], key: A) = + ## deletes `key` from hash table `t`. + var index = RawGet(t, key) + if index >= 0: + t.data[index].slot = seDeleted + dec(t.counter) + +proc initHashTable*[A, B](initialSize = 64): TOrderedHashTable[A, B] = + ## creates a new string table that is empty. `initialSize` needs to be + ## a power of two. + assert isPowerOfTwo(initialSize) + result.counter = 0 + result.first = -1 + result.last = -1 + newSeq(result.data, initialSize) + +proc `$`*[A, B](t: TOrderedHashTable[A, B]): string = + ## The `$` operator for hash tables. + dollarImpl() + # ------------------------------ count tables ------------------------------- const diff --git a/lib/pure/strtabs.nim b/lib/pure/strtabs.nim index f88560304..78f489615 100755 --- a/lib/pure/strtabs.nim +++ b/lib/pure/strtabs.nim @@ -142,19 +142,18 @@ proc newStringTable*(mode: TStringTableMode): PStringTable {. result.counter = 0 newSeq(result.data, startSize) -when false: - proc newStringTable(keyValuePairs: openarray[string], - mode = modeCaseSensitive): PStringTable {. - rtl, extern: "nst$1WithPairs".} = - ## creates a new string table with given key value pairs. - ## Example:: - ## var mytab = newStringTable("key1", "val1", "key2", "val2", - ## modeCaseInsensitive) - result = newStringTable(mode) - var i = 0 - while i < high(keyValuePairs): - result[keyValuePairs[i]] = keyValuePairs[i + 1] - inc(i, 2) +proc newStringTable*(keyValuePairs: openarray[string], + mode: TStringTableMode): PStringTable {. + rtl, extern: "nst$1WithPairs".} = + ## creates a new string table with given key value pairs. + ## Example:: + ## var mytab = newStringTable("key1", "val1", "key2", "val2", + ## modeCaseInsensitive) + result = newStringTable(mode) + var i = 0 + while i < high(keyValuePairs): + result[keyValuePairs[i]] = keyValuePairs[i + 1] + inc(i, 2) proc newStringTable*(keyValuePairs: openarray[tuple[key, val: string]], mode: TStringTableMode = modeCaseSensitive): PStringTable {. diff --git a/lib/system.nim b/lib/system.nim index 815d14fa4..bacb4325a 100755 --- a/lib/system.nim +++ b/lib/system.nim @@ -1349,7 +1349,7 @@ template accumulateResult*(iter: expr) = # we have to compute this here before turning it off in except.nim anyway ... const nimrodStackTrace = compileOption("stacktrace") -{.push checks: off, line_dir: off, debugger: off.} +{.push checks: off, line_dir: off, debugger: off.} # obviously we cannot generate checking operations here :-) # because it would yield into an endless recursion # however, stack-traces are available for most parts diff --git a/lib/system/hti.nim b/lib/system/hti.nim index 3343000ae..d22109061 100755 --- a/lib/system/hti.nim +++ b/lib/system/hti.nim @@ -45,7 +45,9 @@ type # This should be he same as ast.TTypeKind TNimTypeFlag = enum ntfNoRefs = 0, # type contains no tyRef, tySequence, tyString - ntfAcyclic = 1 # type cannot form a cycle + ntfAcyclic = 1, # type cannot form a cycle + ntfEnumHole = 2 # enum has holes and thus `$` for them needs the slow + # version TNimType {.compilerproc, final.} = object size: int kind: TNimKind diff --git a/lib/system/repr.nim b/lib/system/repr.nim index a70989cad..87588421f 100755 --- a/lib/system/repr.nim +++ b/lib/system/repr.nim @@ -1,7 +1,7 @@ # # # Nimrod's Runtime Library -# (c) Copyright 2010 Andreas Rumpf +# (c) Copyright 2011 Andreas Rumpf # # See the file "copying.txt", included in this # distribution, for details about the copyright. @@ -53,10 +53,16 @@ proc reprChar(x: char): string {.compilerRtl.} = add result, "\'" proc reprEnum(e: int, typ: PNimType): string {.compilerRtl.} = - if e <% typ.node.len: # BUGFIX - result = $typ.node.sons[e].name + if ntfEnumHole notin typ.flags: + if e <% typ.node.len: + return $typ.node.sons[e].name else: - result = $e & " (invalid data!)" + # ugh we need a slow linear search: + var n = typ.node + var s = n.sons + for i in 0 .. n.len-1: + if s[i].offset == e: return $s[i].name + result = $e & " (invalid data!)" type pbyteArray = ptr array[0.. 0xffff, byte] |