ObjectGraph.java revision 12158:0fe2815ffa74 
1/*
2 * Copyright (c) 2016, 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
24package gc.g1.humongousObjects.objectGraphTest;
25
26import java.util.ArrayDeque;
27import java.util.Deque;
28import java.util.HashMap;
29import java.util.List;
30import java.util.Map;
31import java.util.Set;
32import java.util.function.BiConsumer;
33import java.util.function.Consumer;
34import java.util.function.Predicate;
35
36public class ObjectGraph {
37
38    private ObjectGraph() {
39    }
40
41    public enum ReferenceType {
42        NONE,
43        WEAK,
44        SOFT,
45        STRONG;
46    }
47
48    /**
49     * Performs operation on all nodes that are reachable from initial ones
50     *
51     * @param nodes     initial nodes
52     * @param operation operation
53     */
54    public static void propagateTransitiveProperty(Set<Object[]> nodes, Consumer<Object[]> operation) {
55        Deque<Object[]> roots = new ArrayDeque<>();
56        nodes.stream().forEach(roots::push);
57        ObjectGraph.enumerateAndMark(roots, operation);
58    }
59
60    /**
61     * Connects graph's vertexes with single-directed (vertex -> neighbour) link
62     *
63     * @param vertex    who is connected
64     * @param neighbour connected to whom
65     */
66    private static void connectVertexes(Object[] vertex, Object[] neighbour) {
67
68        // check if vertex array is full
69        if (vertex[vertex.length - 1] != null) {
70            throw new Error("Array is full and no connections could be added");
71        }
72        int i = 0;
73        while (vertex[i] != null) {
74            ++i;
75        }
76        vertex[i] = neighbour;
77    }
78
79
80    /**
81     * Builds object graph using description from list of parsed nodes. Graph uses Object[] as nodes, first n elements
82     * of array are links to connected nodes, others are null. Then runs visitors on generated graph
83     *
84     * @param parsedNodes             list of nodes' description
85     * @param visitors                visitors that will visit each node of generated graph
86     * @param humongousAllocationSize size of humongous node
87     * @param simpleAllocationSize    size of simple (non-humongous) node
88     * @return root reference to generated graph
89     */
90    public static Object[] generateObjectNodes(List<TestcaseData.FinalParsedNode> parsedNodes,
91                                               Map<Predicate<TestcaseData.FinalParsedNode>,
92                                                       BiConsumer<TestcaseData.FinalParsedNode, Object[][]>> visitors,
93                                               int humongousAllocationSize, int simpleAllocationSize) {
94
95        Object[][] objectNodes = new Object[parsedNodes.size()][];
96
97        // Allocating nodes on Object[]
98        for (int i = 0; i < parsedNodes.size(); ++i) {
99            objectNodes[i] = new Object[(parsedNodes.get(i).isHumongous ?
100                    humongousAllocationSize : simpleAllocationSize)];
101        }
102
103        // Connecting nodes on allocated on Object[]
104        for (int i = 0; i < parsedNodes.size(); ++i) {
105            for (int j = 0; j < parsedNodes.get(i).getConnectedTo().size(); ++j) {
106                connectVertexes(objectNodes[i], objectNodes[parsedNodes.get(i).getConnectedTo().get(j)]);
107            }
108        }
109
110        // Calling visitors
111        visitors.entrySet()
112                .stream()
113                .forEach(
114                        entry -> parsedNodes.stream()
115                                .filter(parsedNode -> entry.getKey().test(parsedNode))
116                                .forEach(node -> entry.getValue().accept(node, objectNodes))
117                );
118
119        return objectNodes[0];
120    }
121
122    /**
123     * Enumerates graph starting with provided vertexes. All vertexes that are reachable from the provided ones are
124     * marked
125     *
126     * @param markedParents provided vertexes
127     * @param markVertex    lambda which marks vertexes
128     */
129    public static void enumerateAndMark(Deque<Object[]> markedParents,
130                                        Consumer<Object[]> markVertex) {
131        Map<Object[], Boolean> isVisited = new HashMap<>();
132        while (!markedParents.isEmpty()) {
133            Object[] vertex = markedParents.pop();
134            if (vertex == null || isVisited.containsKey(vertex)) {
135                continue;
136            }
137            isVisited.put(vertex, true);
138            markVertex.accept(vertex);
139
140            for (int i = 0; i < vertex.length; ++i) {
141                if (vertex[i] == null) {
142                    break;
143                }
144                markedParents.add((Object[]) vertex[i]);
145            }
146        }
147    }
148
149}
150