diff options
author | Oszkar Semerath <Oszkar Semerath@DESKTOP-DNR7JQ7> | 2021-07-25 01:25:51 +0200 |
---|---|---|
committer | Oszkar Semerath <Oszkar Semerath@DESKTOP-DNR7JQ7> | 2021-07-25 01:25:51 +0200 |
commit | d85c3b6209557dc3a02a6969ca79b2bc37fecf09 (patch) | |
tree | 8e04fe7c59d511f40582b1dfa00392f696cca11b /Solvers/VIATRA-Solver | |
parent | parametric testing and permutaters (diff) | |
download | VIATRA-Generator-d85c3b6209557dc3a02a6969ca79b2bc37fecf09.tar.gz VIATRA-Generator-d85c3b6209557dc3a02a6969ca79b2bc37fecf09.tar.zst VIATRA-Generator-d85c3b6209557dc3a02a6969ca79b2bc37fecf09.zip |
hash code fix and test environment reorganization
Diffstat (limited to 'Solvers/VIATRA-Solver')
7 files changed, 179 insertions, 203 deletions
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java index 229aee74..19b0720d 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/ImmutableNode.java | |||
@@ -110,10 +110,8 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | |||
110 | else if((nodeMap & bitposition) != 0) { | 110 | else if((nodeMap & bitposition) != 0) { |
111 | int keyIndex = content.length-1-index(nodeMap, bitposition); | 111 | int keyIndex = content.length-1-index(nodeMap, bitposition); |
112 | ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex]; | 112 | ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex]; |
113 | int newHash = depth%numberOfFactors == 0? | ||
114 | hashProvider.getHash(key, hashDepth(depth)) : | ||
115 | hash; | ||
116 | int newDepth = depth+1; | 113 | int newDepth = depth+1; |
114 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
117 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); | 115 | return subNode.getValue(key, hashProvider, defaultValue, newHash, newDepth); |
118 | } | 116 | } |
119 | // the key is not stored at all | 117 | // the key is not stored at all |
@@ -160,8 +158,8 @@ public class ImmutableNode<KEY, VALUE> extends Node<KEY, VALUE> { | |||
160 | 158 | ||
161 | int keyIndex = content.length-1-index(dataMap, bitposition); | 159 | int keyIndex = content.length-1-index(dataMap, bitposition); |
162 | ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex]; | 160 | ImmutableNode<KEY,VALUE> subNode = (ImmutableNode<KEY,VALUE>) content[keyIndex]; |
163 | int newHash = newHash(hashProvider, key, selectedHashFragment, depth); | ||
164 | int newDepth = depth+1; | 161 | int newDepth = depth+1; |
162 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
165 | Node<KEY,VALUE> newsubNode = subNode.putValue(key, value, hashProvider, defaultValue, newHash, newDepth); | 163 | Node<KEY,VALUE> newsubNode = subNode.putValue(key, value, hashProvider, defaultValue, newHash, newDepth); |
166 | 164 | ||
167 | if(subNode == newsubNode) { | 165 | if(subNode == newsubNode) { |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java index 6e177d9f..4d216785 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/MutableNode.java | |||
@@ -26,6 +26,7 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
26 | MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>(); | 26 | MutableNode<KEY, VALUE> res = new MutableNode<KEY, VALUE>(); |
27 | res.content[2*fragment] = key; | 27 | res.content[2*fragment] = key; |
28 | res.content[2*fragment+1] = value; | 28 | res.content[2*fragment+1] = value; |
29 | res.updateHash(); | ||
29 | return res; | 30 | return res; |
30 | } | 31 | } |
31 | } | 32 | } |
@@ -49,25 +50,25 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
49 | nodeUsed++; | 50 | nodeUsed++; |
50 | } | 51 | } |
51 | } | 52 | } |
52 | updateHash(); | 53 | this.cachedHash = node.hashCode(); |
53 | } | 54 | } |
54 | 55 | ||
55 | @SuppressWarnings("unchecked") | 56 | @SuppressWarnings("unchecked") |
56 | @Override | 57 | @Override |
57 | public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { | 58 | public VALUE getValue(KEY key, ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int hash, int depth) { |
58 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | 59 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); |
59 | KEY keyCandidate = (KEY) content[2*selectedHashFragment]; | 60 | KEY keyCandidate = (KEY) this.content[2*selectedHashFragment]; |
60 | if(keyCandidate != null) { | 61 | if(keyCandidate != null) { |
61 | if(hashProvider.equals(keyCandidate, key)) { | 62 | if(hashProvider.equals(keyCandidate, key)) { |
62 | return (VALUE) content[2*selectedHashFragment+1]; | 63 | return (VALUE) this.content[2*selectedHashFragment+1]; |
63 | } else { | 64 | } else { |
64 | return defaultValue; | 65 | return defaultValue; |
65 | } | 66 | } |
66 | } else { | 67 | } else { |
67 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; | 68 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; |
68 | if(nodeCandidate != null) { | 69 | if(nodeCandidate != null) { |
69 | int newHash = newHash(hashProvider, key, hash, depth); | ||
70 | int newDepth = depth+1; | 70 | int newDepth = depth+1; |
71 | int newHash = newHash(hashProvider, key, hash, newDepth); | ||
71 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); | 72 | return nodeCandidate.getValue(key, hashProvider, defaultValue, newHash, newDepth); |
72 | } else { | 73 | } else { |
73 | return defaultValue; | 74 | return defaultValue; |
@@ -81,38 +82,6 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
81 | } | 82 | } |
82 | return false; | 83 | return false; |
83 | } | 84 | } |
84 | |||
85 | private MutableNode<KEY,VALUE> createNewNode( | ||
86 | ContinousHashProvider<? super KEY> hashProvider, | ||
87 | KEY key1, VALUE value1, int oldHash1, | ||
88 | KEY key2, VALUE value2, int oldHash2, | ||
89 | int newdepth) | ||
90 | { | ||
91 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); | ||
92 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | ||
93 | int newFragment1 = hashFragment(newHash1, newdepth); | ||
94 | int newFragment2 = hashFragment(newHash2, newdepth); | ||
95 | |||
96 | MutableNode<KEY,VALUE> subNode = new MutableNode<KEY,VALUE>(); | ||
97 | if(newFragment1 != newFragment2) { | ||
98 | subNode.content[newFragment1*2]=key1; | ||
99 | subNode.content[newFragment1*2+1]=value1; | ||
100 | |||
101 | subNode.content[newFragment2*2]=key2; | ||
102 | subNode.content[newFragment2*2+1]=value2; | ||
103 | subNode.updateHash(); | ||
104 | return subNode; | ||
105 | } else { | ||
106 | MutableNode<KEY,VALUE> subSubNode = createNewNode( | ||
107 | hashProvider, | ||
108 | key1, value1, newHash1, | ||
109 | key2, value2, newHash2, | ||
110 | newdepth+1); | ||
111 | subNode.content[newFragment1*2+1] = subSubNode; | ||
112 | subNode.updateHash(); | ||
113 | return subNode; | ||
114 | } | ||
115 | } | ||
116 | 85 | ||
117 | @SuppressWarnings("unchecked") | 86 | @SuppressWarnings("unchecked") |
118 | @Override | 87 | @Override |
@@ -120,28 +89,34 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
120 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); | 89 | int selectedHashFragment = hashFragment(hash,shiftDepth(depth)); |
121 | KEY keyCandidate = (KEY) content[2*selectedHashFragment]; | 90 | KEY keyCandidate = (KEY) content[2*selectedHashFragment]; |
122 | if(keyCandidate != null) { | 91 | if(keyCandidate != null) { |
92 | // If has key | ||
123 | if(hashProvider.equals(keyCandidate,key)) { | 93 | if(hashProvider.equals(keyCandidate,key)) { |
124 | // Update entry | 94 | // The key is equals to an existing key -> update entry |
125 | if(value == defaultValue) { | 95 | if(value == defaultValue) { |
126 | return removeEntry(selectedHashFragment); | 96 | return removeEntry(selectedHashFragment); |
127 | } else { | 97 | } else { |
128 | return updateValue(value,selectedHashFragment); | 98 | return updateValue(value,selectedHashFragment); |
129 | } | 99 | } |
130 | } else { | 100 | } else { |
101 | // The key is not equivalent to an existing key on the same hash bin | ||
102 | // -> split entry if it is necessary | ||
131 | if(value == defaultValue) { | 103 | if(value == defaultValue) { |
132 | // dont need to add new node | 104 | // Value is default -> do not need to add new node |
133 | return this; | 105 | return this; |
134 | } else { | 106 | } else { |
135 | // Split entry: data -> node | 107 | // Value is not default -> Split entry data to a new node |
136 | return moveDown(key, value, hashProvider, hash, depth, selectedHashFragment, keyCandidate); | 108 | return moveDownAndSplit(hashProvider, key, value, keyCandidate, hash, depth, selectedHashFragment); |
137 | } | 109 | } |
138 | } | 110 | } |
139 | } else { | 111 | } else { |
112 | // If it does not have key, check for value | ||
140 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; | 113 | Node<KEY,VALUE> nodeCandidate = (Node<KEY,VALUE>) content[2*selectedHashFragment+1]; |
141 | if(nodeCandidate != null) { | 114 | if(nodeCandidate != null) { |
115 | // If it has value, it is a subnode -> upate that | ||
142 | Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, newHash(hashProvider, key, hash, depth+1), depth+1); | 116 | Node<KEY, VALUE> newNode = nodeCandidate.putValue(key, value, hashProvider, defaultValue, newHash(hashProvider, key, hash, depth+1), depth+1); |
143 | return updateSubNode(selectedHashFragment,newNode); | 117 | return updateSubNode(selectedHashFragment,newNode); |
144 | } else { | 118 | } else { |
119 | // If it does not have value, put it in the empty place | ||
145 | if(value == defaultValue) { | 120 | if(value == defaultValue) { |
146 | // dont need to add new key-value pair | 121 | // dont need to add new key-value pair |
147 | return this; | 122 | return this; |
@@ -152,6 +127,8 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
152 | } | 127 | } |
153 | } | 128 | } |
154 | } | 129 | } |
130 | |||
131 | |||
155 | 132 | ||
156 | private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) { | 133 | private Node<KEY, VALUE> addEntry(KEY key, VALUE value, int selectedHashFragment) { |
157 | content[2*selectedHashFragment] = key; | 134 | content[2*selectedHashFragment] = key; |
@@ -189,24 +166,60 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
189 | } | 166 | } |
190 | 167 | ||
191 | @SuppressWarnings("unchecked") | 168 | @SuppressWarnings("unchecked") |
192 | private Node<KEY, VALUE> moveDown( | 169 | private Node<KEY, VALUE> moveDownAndSplit( |
193 | KEY key, VALUE value, | 170 | ContinousHashProvider<? super KEY> hashProvider, |
194 | ContinousHashProvider<? super KEY> hashProvider, int hash, | 171 | KEY newKey, VALUE newValue, KEY previousKey, |
195 | int depth, int selectedHashFragment, KEY keyCandidate) { | 172 | int hashOfNewKey, int depth, int selectedHashFragmentOfCurrentDepth) |
196 | KEY previousKey = keyCandidate; | 173 | { |
197 | VALUE previousValue = (VALUE) content[2*selectedHashFragment+1]; | 174 | VALUE previousValue = (VALUE) content[2*selectedHashFragmentOfCurrentDepth+1]; |
198 | 175 | ||
199 | MutableNode<KEY,VALUE> subNode = createNewNode( | 176 | //final int newHash = newHash(hashProvider, newKey, hashOfNewKey, newDepth); |
177 | MutableNode<KEY,VALUE> newSubNode = newNodeWithTwoEntries( | ||
200 | hashProvider, | 178 | hashProvider, |
201 | previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), | 179 | previousKey, previousValue, hashProvider.getHash(previousKey, hashDepth(depth)), |
202 | key, value, hash, | 180 | newKey, newValue, hashOfNewKey, |
203 | depth+1); | 181 | depth+1); |
204 | 182 | ||
205 | content[2*selectedHashFragment] = null; | 183 | content[2*selectedHashFragmentOfCurrentDepth] = null; |
206 | content[2*selectedHashFragment+1] = subNode; | 184 | content[2*selectedHashFragmentOfCurrentDepth+1] = newSubNode; |
207 | updateHash(); | 185 | updateHash(); |
208 | return this; | 186 | return this; |
209 | } | 187 | } |
188 | private MutableNode<KEY,VALUE> newNodeWithTwoEntries( | ||
189 | ContinousHashProvider<? super KEY> hashProvider, | ||
190 | KEY key1, VALUE value1, int oldHash1, | ||
191 | KEY key2, VALUE value2, int oldHash2, | ||
192 | int newdepth) | ||
193 | { | ||
194 | // final int depthLimit = 4000; | ||
195 | // if(newdepth>depthLimit) { | ||
196 | // final int newHashes = 4000/numberOfFactors; | ||
197 | // throw new IllegalArgumentException( | ||
198 | // "Continuous hash was same " + newHashes + " times for non-equivalent objects " + key1 + " and " + key2 +"."); | ||
199 | // } | ||
200 | int newHash1 = newHash(hashProvider, key1, oldHash1, newdepth); | ||
201 | int newHash2 = newHash(hashProvider, key2, oldHash2, newdepth); | ||
202 | int newFragment1 = hashFragment(newHash1, shiftDepth(newdepth)); | ||
203 | int newFragment2 = hashFragment(newHash2, shiftDepth(newdepth)); | ||
204 | |||
205 | MutableNode<KEY,VALUE> subNode = new MutableNode<KEY,VALUE>(); | ||
206 | if(newFragment1 != newFragment2) { | ||
207 | subNode.content[newFragment1*2]=key1; | ||
208 | subNode.content[newFragment1*2+1]=value1; | ||
209 | |||
210 | subNode.content[newFragment2*2]=key2; | ||
211 | subNode.content[newFragment2*2+1]=value2; | ||
212 | } else { | ||
213 | MutableNode<KEY,VALUE> subSubNode = newNodeWithTwoEntries( | ||
214 | hashProvider, | ||
215 | key1, value1, newHash1, | ||
216 | key2, value2, newHash2, | ||
217 | newdepth+1); | ||
218 | subNode.content[newFragment1*2+1] = subSubNode; | ||
219 | } | ||
220 | subNode.updateHash(); | ||
221 | return subNode; | ||
222 | } | ||
210 | 223 | ||
211 | Node<KEY, VALUE> removeEntry(int selectedHashFragment) { | 224 | Node<KEY, VALUE> removeEntry(int selectedHashFragment) { |
212 | content[2*selectedHashFragment] = null; | 225 | content[2*selectedHashFragment] = null; |
@@ -334,6 +347,40 @@ public class MutableNode<KEY,VALUE> extends Node<KEY,VALUE> { | |||
334 | } | 347 | } |
335 | } | 348 | } |
336 | } | 349 | } |
350 | @SuppressWarnings({"unchecked"}) | ||
351 | @Override | ||
352 | public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) { | ||
353 | for(int i = 0; i<factor; i++) { | ||
354 | if(this.content[2*i] != null) { | ||
355 | KEY key = (KEY) this.content[2*i]; | ||
356 | VALUE value = (VALUE) this.content[2*i+1]; | ||
357 | |||
358 | if(value == defaultValue) { | ||
359 | throw new IllegalStateException("Node contains default value!"); | ||
360 | } | ||
361 | int hashCode = hashProvider.getHash(key, hashDepth(depth)); | ||
362 | int shiftDepth = shiftDepth(depth); | ||
363 | int selectedHashFragment = hashFragment(hashCode, shiftDepth); | ||
364 | if(i != selectedHashFragment) { | ||
365 | throw new IllegalStateException( | ||
366 | "Key "+key+" with hash code "+hashCode+" is in bad place! Fragment=" + selectedHashFragment +", Place="+i); | ||
367 | } | ||
368 | } | ||
369 | } | ||
370 | for(int i = 0; i<factor; i++) { | ||
371 | if(this.content[2*i+1] != null && this.content[2*i] == null) { | ||
372 | Node<KEY,VALUE> subNode = (Node<KEY, VALUE>) this.content[2*i+1]; | ||
373 | subNode.checkIntegrity(hashProvider, defaultValue, depth+1); | ||
374 | } | ||
375 | } | ||
376 | int oldHash = this.cachedHash; | ||
377 | updateHash(); | ||
378 | int newHash = this.cachedHash; | ||
379 | if(oldHash != newHash) { | ||
380 | throw new IllegalStateException("Hash code was not up to date! (old="+oldHash+",new="+newHash+")"); | ||
381 | } | ||
382 | } | ||
383 | |||
337 | 384 | ||
338 | protected void updateHash() { | 385 | protected void updateHash() { |
339 | final int prime = 31; | 386 | final int prime = 31; |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java index 7d547dce..d83c86b7 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/Node.java | |||
@@ -74,5 +74,6 @@ public abstract class Node<KEY,VALUE>{ | |||
74 | prettyPrint(stringBuilder, 0, -1); | 74 | prettyPrint(stringBuilder, 0, -1); |
75 | return stringBuilder.toString(); | 75 | return stringBuilder.toString(); |
76 | } | 76 | } |
77 | public void checkIntegrity(ContinousHashProvider<? super KEY> hashProvider, VALUE defaultValue, int depth) {} | ||
77 | 78 | ||
78 | } | 79 | } |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java index e32fa94b..fd5c9b41 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/src/org/eclipse/viatra/solver/data/map/internal/VersionedMapImpl.java | |||
@@ -2,7 +2,6 @@ package org.eclipse.viatra.solver.data.map.internal; | |||
2 | 2 | ||
3 | import java.util.Iterator; | 3 | import java.util.Iterator; |
4 | import java.util.Map; | 4 | import java.util.Map; |
5 | import java.util.WeakHashMap; | ||
6 | 5 | ||
7 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; | 6 | import org.eclipse.viatra.solver.data.map.ContinousHashProvider; |
8 | import org.eclipse.viatra.solver.data.map.Cursor; | 7 | import org.eclipse.viatra.solver.data.map.Cursor; |
@@ -142,4 +141,9 @@ public class VersionedMapImpl<KEY,VALUE> implements VersionedMap<KEY,VALUE>{ | |||
142 | System.out.println("empty tree"); | 141 | System.out.println("empty tree"); |
143 | } | 142 | } |
144 | } | 143 | } |
144 | public void checkIntegrity() { | ||
145 | if(this.root != null) { | ||
146 | this.root.checkIntegrity(hashProvider, defaultValue, 0); | ||
147 | } | ||
148 | } | ||
145 | } | 149 | } |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java index 1dcf7a63..11e1c1a7 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/MapTestEnvironment.java | |||
@@ -11,6 +11,41 @@ import java.util.TreeMap; | |||
11 | import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; | 11 | import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; |
12 | 12 | ||
13 | public class MapTestEnvironment<KEY,VALUE> { | 13 | public class MapTestEnvironment<KEY,VALUE> { |
14 | public static String[] prepareValues(int maxValue) { | ||
15 | String[] values = new String[maxValue]; | ||
16 | values[0] = "DEFAULT"; | ||
17 | for(int i = 1; i<values.length; i++) { | ||
18 | values[i] = "VAL"+i; | ||
19 | } | ||
20 | return values; | ||
21 | } | ||
22 | |||
23 | //private static final int maxPrime = 2147483629; | ||
24 | public static ContinousHashProvider<Integer> prepareHashProvider(final boolean evil) { | ||
25 | ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() { | ||
26 | |||
27 | @Override | ||
28 | public int getHash(Integer key, int index) { | ||
29 | if(evil && index < 100 && index < key/3) { | ||
30 | return 7; | ||
31 | } | ||
32 | int result = 1; | ||
33 | final int prime = 31; | ||
34 | |||
35 | result = prime*result + key; | ||
36 | result = prime*result + index; | ||
37 | |||
38 | return result; | ||
39 | } | ||
40 | |||
41 | @Override | ||
42 | public boolean equals(Integer key1, Integer key2) { | ||
43 | return key1.equals(key2); | ||
44 | } | ||
45 | }; | ||
46 | return chp; | ||
47 | } | ||
48 | |||
14 | VersionedMapImpl<KEY, VALUE> sut; | 49 | VersionedMapImpl<KEY, VALUE> sut; |
15 | Map<KEY,VALUE> oracle = new HashMap<KEY, VALUE>(); | 50 | Map<KEY,VALUE> oracle = new HashMap<KEY, VALUE>(); |
16 | 51 | ||
@@ -28,6 +63,14 @@ public class MapTestEnvironment<KEY,VALUE> { | |||
28 | } | 63 | } |
29 | 64 | ||
30 | public void checkEquivalence(String title) { | 65 | public void checkEquivalence(String title) { |
66 | // 0. Checking integrity | ||
67 | try { | ||
68 | sut.checkIntegrity(); | ||
69 | } catch(IllegalStateException e) { | ||
70 | fail(title + ": " + e.getMessage()); | ||
71 | } | ||
72 | |||
73 | |||
31 | // 1. Checking: if Reference contains <key,value> pair, then SUT contains <key,value> pair. | 74 | // 1. Checking: if Reference contains <key,value> pair, then SUT contains <key,value> pair. |
32 | // Tests get functions | 75 | // Tests get functions |
33 | for(Entry<KEY, VALUE> entry : oracle.entrySet()) { | 76 | for(Entry<KEY, VALUE> entry : oracle.entrySet()) { |
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java index cf3b8d5e..4e6e46e3 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest1Mutable.java | |||
@@ -12,9 +12,9 @@ import org.junit.jupiter.params.provider.MethodSource; | |||
12 | 12 | ||
13 | public class SmokeTest1Mutable { | 13 | public class SmokeTest1Mutable { |
14 | 14 | ||
15 | private void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue) { | 15 | private void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, boolean evilHash) { |
16 | String[] values = prepareValues(maxValue); | 16 | String[] values = MapTestEnvironment.prepareValues(maxValue); |
17 | ContinousHashProvider<Integer> chp = prepareHashProvider(); | 17 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); |
18 | 18 | ||
19 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 19 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); |
20 | VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap(); | 20 | VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap(); |
@@ -25,36 +25,6 @@ public class SmokeTest1Mutable { | |||
25 | iterativeRandomPuts(scenario, steps, maxKey, values, e, r); | 25 | iterativeRandomPuts(scenario, steps, maxKey, values, e, r); |
26 | } | 26 | } |
27 | 27 | ||
28 | |||
29 | |||
30 | private String[] prepareValues(int maxValue) { | ||
31 | String[] values = new String[maxValue]; | ||
32 | values[0] = "DEFAULT"; | ||
33 | for(int i = 1; i<values.length; i++) { | ||
34 | values[i] = "VAL"+i; | ||
35 | } | ||
36 | return values; | ||
37 | } | ||
38 | private ContinousHashProvider<Integer> prepareHashProvider() { | ||
39 | ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() { | ||
40 | |||
41 | @Override | ||
42 | public int getHash(Integer key, int index) { | ||
43 | int result = 1; | ||
44 | final int prime = 31; | ||
45 | result = prime*result + key; | ||
46 | result = prime*result + index; | ||
47 | return result; | ||
48 | } | ||
49 | |||
50 | @Override | ||
51 | public boolean equals(Integer key1, Integer key2) { | ||
52 | return key1.equals(key2); | ||
53 | } | ||
54 | }; | ||
55 | return chp; | ||
56 | } | ||
57 | |||
58 | void iterativeRandomPuts( | 28 | void iterativeRandomPuts( |
59 | String scenario, | 29 | String scenario, |
60 | int steps, | 30 | int steps, |
@@ -89,10 +59,10 @@ public class SmokeTest1Mutable { | |||
89 | } | 59 | } |
90 | } | 60 | } |
91 | 61 | ||
92 | @ParameterizedTest(name = "Mutable Smoke {index}/{0} Steps={1} Keys={2} Values={3} seed={4}") | 62 | @ParameterizedTest(name = "Mutable Smoke {index}/{0} Steps={1} Keys={2} Values={3} seed={4}, evil-hash={5}") |
93 | @MethodSource | 63 | @MethodSource |
94 | void parametrizedSmoke(int test, int steps, int noKeys, int noValues, int seed) { | 64 | void parametrizedSmoke(int test, int steps, int noKeys, int noValues, int seed, boolean evilHash) { |
95 | runSmokeTest("Smoke"+test+"S"+steps+"K"+noKeys+"V"+noValues+"s"+seed,seed,steps,noKeys,noValues); | 65 | runSmokeTest("SmokeS"+steps+"K"+noKeys+"V"+noValues+"s"+seed+"H"+(evilHash?"Evil":"Normal"),seed,steps,noKeys,noValues,evilHash); |
96 | } | 66 | } |
97 | 67 | ||
98 | private static Stream<Arguments> parametrizedSmoke(){ | 68 | private static Stream<Arguments> parametrizedSmoke(){ |
@@ -100,7 +70,8 @@ public class SmokeTest1Mutable { | |||
100 | new Object[] {1000,32*32*32*32}, | 70 | new Object[] {1000,32*32*32*32}, |
101 | new Object[] {3,32, 32*32, 32*32*32*32}, | 71 | new Object[] {3,32, 32*32, 32*32*32*32}, |
102 | new Object[] {2,3}, | 72 | new Object[] {2,3}, |
103 | new Object[] {1,2,3} | 73 | new Object[] {1,2,3}, |
74 | new Object[] {false,true} | ||
104 | ); | 75 | ); |
105 | } | 76 | } |
106 | 77 | ||
diff --git a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java index 337725a6..fa57f2d3 100644 --- a/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java +++ b/Solvers/VIATRA-Solver/org.eclipse.viatra.solver.data/tests/org/eclipse/viatra/solver/data/map/SmokeTest2Commit.java | |||
@@ -3,14 +3,17 @@ package org.eclipse.viatra.solver.data.map; | |||
3 | import static org.junit.Assert.fail; | 3 | import static org.junit.Assert.fail; |
4 | 4 | ||
5 | import java.util.Random; | 5 | import java.util.Random; |
6 | import java.util.stream.Stream; | ||
6 | 7 | ||
7 | import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; | 8 | import org.eclipse.viatra.solver.data.map.internal.VersionedMapImpl; |
8 | import org.junit.jupiter.api.Test; | 9 | import org.junit.jupiter.params.ParameterizedTest; |
10 | import org.junit.jupiter.params.provider.Arguments; | ||
11 | import org.junit.jupiter.params.provider.MethodSource; | ||
9 | 12 | ||
10 | public class SmokeTest2Commit { | 13 | public class SmokeTest2Commit { |
11 | private void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency) { | 14 | private void runSmokeTest(String scenario, int seed, int steps, int maxKey, int maxValue, int commitFrequency, boolean evilHash) { |
12 | String[] values = prepareValues(maxValue); | 15 | String[] values = MapTestEnvironment.prepareValues(maxValue); |
13 | ContinousHashProvider<Integer> chp = prepareHashProvider(); | 16 | ContinousHashProvider<Integer> chp = MapTestEnvironment.prepareHashProvider(evilHash); |
14 | 17 | ||
15 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); | 18 | VersionedMapStore<Integer, String> store = new VersionedMapStoreImpl<Integer, String>(chp, values[0]); |
16 | VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap(); | 19 | VersionedMapImpl<Integer, String> sut = (VersionedMapImpl<Integer, String>) store.createMap(); |
@@ -20,36 +23,6 @@ public class SmokeTest2Commit { | |||
20 | 23 | ||
21 | iterativeRandomPutsAndCommits(scenario, steps, maxKey, values, e, r, commitFrequency); | 24 | iterativeRandomPutsAndCommits(scenario, steps, maxKey, values, e, r, commitFrequency); |
22 | } | 25 | } |
23 | |||
24 | |||
25 | |||
26 | private String[] prepareValues(int maxValue) { | ||
27 | String[] values = new String[maxValue]; | ||
28 | values[0] = "DEFAULT"; | ||
29 | for(int i = 1; i<values.length; i++) { | ||
30 | values[i] = "VAL"+i; | ||
31 | } | ||
32 | return values; | ||
33 | } | ||
34 | private ContinousHashProvider<Integer> prepareHashProvider() { | ||
35 | ContinousHashProvider<Integer> chp = new ContinousHashProvider<Integer>() { | ||
36 | |||
37 | @Override | ||
38 | public int getHash(Integer key, int index) { | ||
39 | int result = 1; | ||
40 | final int prime = 31; | ||
41 | result = prime*result + key; | ||
42 | result = prime*result + index; | ||
43 | return result; | ||
44 | } | ||
45 | |||
46 | @Override | ||
47 | public boolean equals(Integer key1, Integer key2) { | ||
48 | return key1.equals(key2); | ||
49 | } | ||
50 | }; | ||
51 | return chp; | ||
52 | } | ||
53 | 26 | ||
54 | void iterativeRandomPutsAndCommits( | 27 | void iterativeRandomPutsAndCommits( |
55 | String scenario, | 28 | String scenario, |
@@ -84,88 +57,27 @@ public class SmokeTest2Commit { | |||
84 | } | 57 | } |
85 | if(index%10000==0) System.out.println(scenario+":"+index+" finished"); | 58 | if(index%10000==0) System.out.println(scenario+":"+index+" finished"); |
86 | if(index%commitFrequency == 0) { | 59 | if(index%commitFrequency == 0) { |
87 | long version = e.sut.commit(); | 60 | e.sut.commit(); |
88 | System.out.println(scenario+":"+index+": Commit! " + version); | 61 | //System.out.println(scenario+":"+index+": Commit! version=" + version); |
89 | } | 62 | } |
90 | } | 63 | } |
91 | } | 64 | } |
92 | 65 | ||
93 | // Mini smoke frequent commints | ||
94 | @Test | ||
95 | void MiniSmokeFrequentK3V2v1() { | ||
96 | runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 2, 1); | ||
97 | } | ||
98 | @Test | ||
99 | void MiniSmokeFrequentK3V2v2() { | ||
100 | runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 2, 1); | ||
101 | } | ||
102 | @Test | ||
103 | void MiniSmokeFrequentK3V2v3() { | ||
104 | runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 2, 1); | ||
105 | } | ||
106 | @Test | ||
107 | void MiniSmokeFrequentK3V3v1() { | ||
108 | runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 3, 1); | ||
109 | } | ||
110 | @Test | ||
111 | void MiniSmokeFrequentK3V3v2() { | ||
112 | runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 3, 1); | ||
113 | } | ||
114 | @Test | ||
115 | void MiniSmokeFrequentK3V3v3() { | ||
116 | runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 3, 1); | ||
117 | } | ||
118 | // Mini smoke rare commits | ||
119 | @Test | ||
120 | void MiniSmokeRareK3V2v1() { | ||
121 | runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 2, 100); | ||
122 | } | ||
123 | @Test | ||
124 | void MiniSmokeRareK3V2v2() { | ||
125 | runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 2, 100); | ||
126 | } | ||
127 | @Test | ||
128 | void MiniSmokeKRare3V2v3() { | ||
129 | runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 2, 100); | ||
130 | } | ||
131 | @Test | ||
132 | void MiniSmokeRareK3V3v1() { | ||
133 | runSmokeTest("MiniSmokeK3V2v1",0, 1000, 3, 3, 100); | ||
134 | } | ||
135 | @Test | ||
136 | void MiniSmokeRareK3V3v2() { | ||
137 | runSmokeTest("MiniSmokeK3V2v2",1, 1000, 3, 3, 100); | ||
138 | } | ||
139 | @Test | ||
140 | void MiniSmokeRareK3V3v3() { | ||
141 | runSmokeTest("MiniSmokeK3V2v3",3, 1000, 3, 3, 100); | ||
142 | } | ||
143 | 66 | ||
144 | // Medium smoke | 67 | @ParameterizedTest(name = "Immutable Smoke {index}/{0} Steps={1} Keys={2} Values={3} commit frequency={4} seed={5}") |
145 | @Test | 68 | @MethodSource |
146 | void MediumSmokeK3V2v1() { | 69 | void parametrizedSmoke(int tests, int steps, int noKeys, int noValues, int commitFrequency, int seed, boolean evilHash) { |
147 | runSmokeTest("MediumSmokeK3V2v1",1, 1000, 32, 2, 10); | 70 | runSmokeTest("SmokeCommitS"+steps+"K"+noKeys+"V"+noValues+"s"+seed,seed,steps,noKeys,noValues,commitFrequency,evilHash); |
148 | } | ||
149 | @Test | ||
150 | void MediumSmokeK3V2v2() { | ||
151 | runSmokeTest("MediumSmokeK3V2v2",2, 1000, 32, 2, 10); | ||
152 | } | ||
153 | @Test | ||
154 | void MediumSmokeK3V2v3() { | ||
155 | runSmokeTest("MediumSmokeK3V2v3",3, 1000, 32, 2, 10); | ||
156 | } | 71 | } |
157 | 72 | ||
158 | //Large Smoke | 73 | private static Stream<Arguments> parametrizedSmoke(){ |
159 | @Test | 74 | return TestPermuter.permutationWithSize( |
160 | void SmokeLargeRareCommit() { | 75 | new Object[] {1000,32*32*32*32}, |
161 | runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2, 100); | 76 | new Object[] {3,32, 32*32}, |
162 | } | 77 | new Object[] {2,3}, |
163 | @Test | 78 | new Object[] {1,10,100}, |
164 | void SmokeLargeNormalCommit() { | 79 | new Object[] {1,2,3}, |
165 | runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2, 10); | 80 | new Object[] {false,true} |
166 | } | 81 | ); |
167 | @Test | ||
168 | void SmokeLargeFrequentCommit() { | ||
169 | runSmokeTest("SmokeLarge",0, 32*32*32*32, 32*32-1, 2, 1); | ||
170 | } | 82 | } |
171 | } | 83 | } |