epsilon.soag.hash source code

1 module epsilon.soag.hash;
2 
3 import runtime;
4 import SOAG = epsilon.soag.soag;
5 
6 class HashEntry
7 {
8     SOAG.Instruction Instr;
9 }
10 
11 HashEntry[] HashTab;
12 int MaxHashTabIndex;
13 int V4711;
14 int V711;
15 
16 /**
17  * SEM: leert die Hash-Tabelle
18  */
19 void Reset() @nogc nothrow @safe
20 {
21     for (int i = 0; i < MaxHashTabIndex; ++i)
22         HashTab[i] = null;
23 }
24 
25 /**
26  * IN:  maximale Anzahl an Affixparametern in einer Regel
27  * OUT: -
28  * SEM: reserviert Speicher für die Hash-Tabelle und setzt die max. Hash-Adresse
29  */
30 void Init(int MaxAffInRule) @safe
31 in (MaxAffInRule > 0)
32 {
33     import std.conv : to;
34     import std.math : log2;
35 
36     int Exp;
37     int i;
38     // Exp = SHORT(ENTIER(Math.ln(MaxAffInRule) / Math.ln(2)) + 1);
39     Exp = log2(MaxAffInRule).to!int + 1;
40     MaxHashTabIndex = 2;
41     for (i = 2; i <= Exp; ++i)
42         MaxHashTabIndex = MaxHashTabIndex * 2;
43     HashTab = new HashEntry[MaxHashTabIndex];
44     Reset;
45 }
46 
47 /**
48  * IN:  Instruktion aus der Visit-Sequenz, kein NIL !
49  * OUT: Index in der Hash-Tabelle
50  * SEM: Ermittlung Indexes in der Hash-Tabelle
51  */
52 int HashIndex(ref SOAG.Instruction I) @safe
53 {
54     import std.conv : to;
55 
56     int Index;
57     int Index0;
58     int Try;
59     bool found;
60 
61     /**
62      * Fehler im Compiler: kann keine Integerkonstanten > 128 in Multiplikationen verarbeiten
63      * IN:  Instruktion
64      * OUT: -
65      * SEM: Realisierung der Hash-Funktion
66      */
67     int HashFun(ref SOAG.Instruction I)
68     {
69         import std.conv : to;
70 
71         int Index;
72 
73         if (auto visit = cast(SOAG.Visit) I)
74             Index = 100 + V4711 * visit.SymOcc + V711 * visit.VisitNo;
75         else if (auto leave = cast(SOAG.Leave) I)
76             Index = 200 + V4711 * leave.VisitNo;
77         else if (auto call = cast(SOAG.Call) I)
78             Index = 300 + V4711 * call.SymOcc;
79         else
80             Index = 0;
81         return MOD(Index, MaxHashTabIndex).to!int;
82     }
83 
84     Try = 0;
85     Index0 = HashFun(I);
86     Index = Index0;
87     if (HashTab[Index] is null)
88     {
89         found = true;
90     }
91     else
92     {
93         found = SOAG.isEqual(I, HashTab[Index].Instr);
94     }
95     while (!found)
96     {
97         ++Try;
98         Index = MOD(Index0 - Try * (DIV(Index0, 2) * 2 + 1), MaxHashTabIndex).to!int;
99         if (HashTab[Index] is null)
100         {
101             found = true;
102         }
103         else
104         {
105             found = SOAG.isEqual(I, HashTab[Index].Instr);
106         }
107     }
108     return Index;
109 }
110 
111 /**
112  * IN:  Instruktion aus der Visit-Sequenz
113  * OUT: boolscher Wert
114  * SEM: Test, ob die Instruktion schon in der Hash-Tabelle enthalten ist
115  */
116 bool IsIn(SOAG.Instruction I) @safe
117 {
118     if (I is null)
119         return true;
120 
121     const Index = HashIndex(I);
122 
123     return HashTab[Index] !is null;
124 }
125 
126 /**
127  * IN:  Instruktion der Visit-Sequenz
128  * OUT: -
129  * SEM: fügt die Instruktion in die Hash-Tabelle ein
130  */
131 void Enter(SOAG.Instruction I) @safe
132 {
133     if (I !is null)
134     {
135         int Index = HashIndex(I);
136         HashEntry Entry = new HashEntry;
137 
138         Entry.Instr = I;
139         HashTab[Index] = Entry;
140     }
141 }
142 
143 static this() @nogc nothrow @safe
144 {
145     V4711 = 4711;
146     V711 = 711;
147 }