diff options
Diffstat (limited to 'rod/treetab.nim')
-rw-r--r-- | rod/treetab.nim | 125 |
1 files changed, 0 insertions, 125 deletions
diff --git a/rod/treetab.nim b/rod/treetab.nim deleted file mode 100644 index 797ef5029..000000000 --- a/rod/treetab.nim +++ /dev/null @@ -1,125 +0,0 @@ -# -# -# The Nimrod Compiler -# (c) Copyright 2008 Andreas Rumpf -# -# See the file "copying.txt", included in this -# distribution, for details about the copyright. -# - -# Implements a table from trees to trees. Does structural equavilent checking. - -import - nhashes, ast, astalgo, types - -proc NodeTableGet*(t: TNodeTable, key: PNode): int -proc NodeTablePut*(t: var TNodeTable, key: PNode, val: int) -proc NodeTableTestOrSet*(t: var TNodeTable, key: PNode, val: int): int -# implementation - -proc hashTree(n: PNode): THash = - result = 0 - if n == nil: return - result = ord(n.kind) - case n.kind - of nkEmpty, nkNilLit, nkType: - nil - of nkIdent: - result = concHash(result, n.ident.h) - of nkSym: - result = concHash(result, n.sym.name.h) - of nkCharLit..nkInt64Lit: - if (n.intVal >= low(int)) and (n.intVal <= high(int)): - result = concHash(result, int(n.intVal)) - of nkFloatLit..nkFloat64Lit: - if (n.floatVal >= - 1000000.0) and (n.floatVal <= 1000000.0): - result = concHash(result, toInt(n.floatVal)) - of nkStrLit..nkTripleStrLit: - result = concHash(result, GetHashStr(n.strVal)) - else: - for i in countup(0, sonsLen(n) - 1): - result = concHash(result, hashTree(n.sons[i])) - -proc TreesEquivalent(a, b: PNode): bool = - result = false - if a == b: - result = true - elif (a != nil) and (b != nil) and (a.kind == b.kind): - case a.kind - of nkEmpty, nkNilLit, nkType: result = true - of nkSym: result = a.sym.id == b.sym.id - of nkIdent: result = a.ident.id == b.ident.id - of nkCharLit..nkInt64Lit: result = a.intVal == b.intVal - of nkFloatLit..nkFloat64Lit: result = a.floatVal == b.floatVal - of nkStrLit..nkTripleStrLit: result = a.strVal == b.strVal - else: - if sonsLen(a) == sonsLen(b): - for i in countup(0, sonsLen(a) - 1): - if not TreesEquivalent(a.sons[i], b.sons[i]): return - result = true - if result: result = sameTypeOrNil(a.typ, b.typ) - -proc NodeTableRawGet(t: TNodeTable, k: THash, key: PNode): int = - var h: THash - h = k and high(t.data) - while t.data[h].key != nil: - if (t.data[h].h == k) and TreesEquivalent(t.data[h].key, key): - return h - h = nextTry(h, high(t.data)) - result = - 1 - -proc NodeTableGet(t: TNodeTable, key: PNode): int = - var index: int - index = NodeTableRawGet(t, hashTree(key), key) - if index >= 0: result = t.data[index].val - else: result = low(int) - -proc NodeTableRawInsert(data: var TNodePairSeq, k: THash, key: PNode, val: int) = - var h: THash - h = k and high(data) - while data[h].key != nil: h = nextTry(h, high(data)) - assert(data[h].key == nil) - data[h].h = k - data[h].key = key - data[h].val = val - -proc NodeTablePut(t: var TNodeTable, key: PNode, val: int) = - var - index: int - n: TNodePairSeq - k: THash - k = hashTree(key) - index = NodeTableRawGet(t, k, key) - if index >= 0: - assert(t.data[index].key != nil) - t.data[index].val = val - else: - if mustRehash(len(t.data), t.counter): - newSeq(n, len(t.data) * growthFactor) - for i in countup(0, high(t.data)): - if t.data[i].key != nil: - NodeTableRawInsert(n, t.data[i].h, t.data[i].key, t.data[i].val) - swap(t.data, n) - NodeTableRawInsert(t.data, k, key, val) - inc(t.counter) - -proc NodeTableTestOrSet(t: var TNodeTable, key: PNode, val: int): int = - var - index: int - n: TNodePairSeq - k: THash - k = hashTree(key) - index = NodeTableRawGet(t, k, key) - if index >= 0: - assert(t.data[index].key != nil) - result = t.data[index].val - else: - if mustRehash(len(t.data), t.counter): - newSeq(n, len(t.data) * growthFactor) - for i in countup(0, high(t.data)): - if t.data[i].key != nil: - NodeTableRawInsert(n, t.data[i].h, t.data[i].key, t.data[i].val) - swap(t.data, n) - NodeTableRawInsert(t.data, k, key, val) - result = val - inc(t.counter) |