1 /*
2 * Copyright (c) 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24
25 package org.graalvm.compiler.graph.test;
26
27 import static org.graalvm.compiler.nodeinfo.NodeCycles.CYCLES_IGNORED;
28 import static org.graalvm.compiler.nodeinfo.NodeSize.SIZE_IGNORED;
29
30 import java.util.ConcurrentModificationException;
31 import java.util.Iterator;
32 import java.util.NoSuchElementException;
33
34 import org.graalvm.compiler.api.test.Graal;
35 import org.graalvm.compiler.graph.Graph;
36 import org.graalvm.compiler.graph.Node;
37 import org.graalvm.compiler.graph.NodeBitMap;
38 import org.graalvm.compiler.graph.NodeClass;
39 import org.graalvm.compiler.nodeinfo.NodeInfo;
40 import org.graalvm.compiler.options.OptionValues;
41 import org.junit.Assert;
42 import org.junit.Before;
43 import org.junit.Test;
44
45 public class NodeBitMapTest extends GraphTest {
46
47 @NodeInfo(cycles = CYCLES_IGNORED, size = SIZE_IGNORED)
48 static final class TestNode extends Node {
49 public static final NodeClass<TestNode> TYPE = NodeClass.create(TestNode.class);
50
51 protected TestNode() {
52 super(TYPE);
53 }
54 }
55
56 private Graph graph;
57 private TestNode[] nodes = new TestNode[100];
58 private NodeBitMap map;
59
60 @Before
61 public void before() {
62 // Need to initialize HotSpotGraalRuntime before any Node class is initialized.
63 Graal.getRuntime();
64
65 OptionValues options = getOptions();
66 graph = new Graph(options, getDebug(options));
67 for (int i = 0; i < nodes.length; i++) {
68 nodes[i] = graph.add(new TestNode());
69 }
70 map = graph.createNodeBitMap();
71 }
72
73 @Test
74 public void iterateEmpty() {
75 for (Node n : map) {
76 Assert.fail("no elements expected: " + n);
77 }
78 }
79
80 @Test
81 public void iterateMarkedNodes() {
82 map.mark(nodes[99]);
83 map.mark(nodes[0]);
84 map.mark(nodes[7]);
85 map.mark(nodes[1]);
86 map.mark(nodes[53]);
87
88 Iterator<Node> iter = map.iterator();
89 Assert.assertTrue(iter.hasNext());
90 Assert.assertEquals(nodes[0], iter.next());
91 Assert.assertTrue(iter.hasNext());
92 Assert.assertEquals(nodes[1], iter.next());
93 Assert.assertTrue(iter.hasNext());
94 Assert.assertEquals(nodes[7], iter.next());
95 Assert.assertTrue(iter.hasNext());
96 Assert.assertEquals(nodes[53], iter.next());
97 Assert.assertTrue(iter.hasNext());
98 Assert.assertEquals(nodes[99], iter.next());
99 Assert.assertFalse(iter.hasNext());
100 }
101
102 @Test
103 public void deleteNodeWhileIterating() {
104 map.mark(nodes[99]);
105 map.mark(nodes[0]);
106 map.mark(nodes[7]);
107 map.mark(nodes[1]);
108 map.mark(nodes[53]);
109
110 Iterator<Node> iter = map.iterator();
111 Assert.assertTrue(iter.hasNext());
112 Assert.assertEquals(nodes[0], iter.next());
113 Assert.assertTrue(iter.hasNext());
114 Assert.assertEquals(nodes[1], iter.next());
115 nodes[7].markDeleted();
116 nodes[53].markDeleted();
117 Assert.assertTrue(iter.hasNext());
118 Assert.assertEquals(nodes[99], iter.next());
119 Assert.assertFalse(iter.hasNext());
120 }
121
122 @Test
123 public void deleteAllNodesBeforeIterating() {
124 for (int i = 0; i < nodes.length; i++) {
125 map.mark(nodes[i]);
126 nodes[i].markDeleted();
127 }
128
129 Iterator<Node> iter = map.iterator();
130 Assert.assertFalse(iter.hasNext());
131 }
132
133 @Test
134 public void multipleHasNextInvocations() {
135 map.mark(nodes[7]);
136
137 Iterator<Node> iter = map.iterator();
138 Assert.assertTrue(iter.hasNext());
139 Assert.assertTrue(iter.hasNext());
140 Assert.assertEquals(nodes[7], iter.next());
141 Assert.assertFalse(iter.hasNext());
142 }
143
144 @Test(expected = NoSuchElementException.class)
145 public void noSuchElement() {
146 map.iterator().next();
147 }
148
149 @Test(expected = ConcurrentModificationException.class)
150 public void concurrentModification() {
151 map.mark(nodes[7]);
152
153 map.mark(nodes[99]);
154 map.mark(nodes[0]);
155 map.mark(nodes[7]);
156 map.mark(nodes[1]);
157 map.mark(nodes[53]);
158
159 Iterator<Node> iter = map.iterator();
160 Assert.assertTrue(iter.hasNext());
161 Assert.assertEquals(nodes[0], iter.next());
162 Assert.assertTrue(iter.hasNext());
163 Assert.assertEquals(nodes[1], iter.next());
164 Assert.assertTrue(iter.hasNext());
165 nodes[7].markDeleted();
166 iter.next();
167 }
168
169 @Test
170 public void nextWithoutHasNext() {
171 map.mark(nodes[99]);
172 map.mark(nodes[0]);
173 map.mark(nodes[7]);
174 map.mark(nodes[1]);
175 map.mark(nodes[53]);
176
177 Iterator<Node> iter = map.iterator();
178 Assert.assertEquals(nodes[0], iter.next());
179 Assert.assertEquals(nodes[1], iter.next());
180 Assert.assertEquals(nodes[7], iter.next());
181 Assert.assertEquals(nodes[53], iter.next());
182 Assert.assertEquals(nodes[99], iter.next());
183 Assert.assertFalse(iter.hasNext());
184 }
185
186 @Test
187 public void markWhileIterating() {
188 map.mark(nodes[0]);
189
190 Iterator<Node> iter = map.iterator();
191 Assert.assertTrue(iter.hasNext());
192 Assert.assertEquals(nodes[0], iter.next());
193 map.mark(nodes[7]);
194 Assert.assertTrue(iter.hasNext());
195 map.mark(nodes[1]);
196 Assert.assertEquals(nodes[7], iter.next());
197 map.mark(nodes[99]);
198 map.mark(nodes[53]);
199 Assert.assertTrue(iter.hasNext());
200 Assert.assertEquals(nodes[53], iter.next());
201 Assert.assertTrue(iter.hasNext());
202 Assert.assertEquals(nodes[99], iter.next());
203 Assert.assertFalse(iter.hasNext());
204 }
205 }