1/*
2 * Copyright (c) 2009, 2011, 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 */
23package org.graalvm.compiler.phases.util;
24
25import org.graalvm.compiler.nodes.AbstractMergeNode;
26
27/**
28 * This class implements a worklist for dealing with blocks. The worklist can operate either as a
29 * stack (i.e. first-in / last-out), or as a sorted list, where blocks can be sorted by a supplied
30 * number. The latter usage lends itself naturally to iterative dataflow analysis problems.
31 */
32public class BlockWorkList {
33
34    AbstractMergeNode[] workList;
35    int[] workListNumbers;
36    int workListIndex;
37
38    /**
39     * Adds a block to this list in an unsorted fashion, like a stack.
40     *
41     * @param block the block to add
42     */
43    public void add(AbstractMergeNode block) {
44        if (workList == null) {
45            // worklist not allocated yet
46            allocate();
47        } else if (workListIndex == workList.length) {
48            // need to grow the worklist
49            grow();
50        }
51        // put the block at the end of the array
52        workList[workListIndex++] = block;
53    }
54
55    /**
56     * Adds a block to this list, sorted by the supplied number. The block with the lowest number is
57     * returned upon subsequent removes.
58     *
59     * @param block the block to add
60     * @param number the number used to sort the block
61     */
62    public void addSorted(AbstractMergeNode block, int number) {
63        if (workList == null) {
64            // worklist not allocated yet
65            allocate();
66        } else if (workListIndex == workList.length) {
67            // need to grow the worklist
68            grow();
69        }
70        // put the block at the end of the array
71        workList[workListIndex] = block;
72        workListNumbers[workListIndex] = number;
73        workListIndex++;
74        int i = workListIndex - 2;
75        // push block towards the beginning of the array
76        for (; i >= 0; i--) {
77            int n = workListNumbers[i];
78            if (n >= number) {
79                break; // already in the right position
80            }
81            workList[i + 1] = workList[i]; // bubble b down by one
82            workList[i] = block;           // and overwrite its place with block
83            workListNumbers[i + 1] = n;    // bubble n down by one
84            workListNumbers[i] = number;   // and overwrite its place with number
85        }
86    }
87
88    /**
89     * Removes the next block from this work list. If the blocks have been added in a sorted order,
90     * then the block with the lowest number is returned. Otherwise, the last block added is
91     * returned.
92     *
93     * @return the next block in the list
94     */
95    public AbstractMergeNode removeFromWorkList() {
96        if (workListIndex != 0) {
97            return workList[--workListIndex];
98        }
99        return null;
100    }
101
102    /**
103     * Checks whether the list is empty.
104     *
105     * @return {@code true} if this list is empty
106     */
107    public boolean isEmpty() {
108        return workListIndex == 0;
109    }
110
111    private void allocate() {
112        workList = new AbstractMergeNode[5];
113        workListNumbers = new int[5];
114    }
115
116    private void grow() {
117        int prevLength = workList.length;
118        AbstractMergeNode[] nworkList = new AbstractMergeNode[prevLength * 3];
119        System.arraycopy(workList, 0, nworkList, 0, prevLength);
120        workList = nworkList;
121
122        int[] nworkListNumbers = new int[prevLength * 3];
123        System.arraycopy(workListNumbers, 0, nworkListNumbers, 0, prevLength);
124        workListNumbers = nworkListNumbers;
125    }
126}
127