foundation/org.eclipse.persistence.core/src/main/java/org/eclipse/persistence/internal/sessions/CommitOrderCalculator.java

/*
 * Copyright (c) 1998, 2021 Oracle and/or its affiliates. All rights reserved.
 *
 * This program and the accompanying materials are made available under the
 * terms of the Eclipse Public License v. 2.0 which is available at
 * http://www.eclipse.org/legal/epl-2.0,
 * or the Eclipse Distribution License v. 1.0 which is available at
 * http://www.eclipse.org/org/documents/edl-v10.php.
 *
 * SPDX-License-Identifier: EPL-2.0 OR BSD-3-Clause
 */

// Contributors:
//     Oracle - initial API and implementation from Oracle TopLink
package org.eclipse.persistence.internal.sessions;

import org.eclipse.persistence.descriptors.ClassDescriptor;
import org.eclipse.persistence.internal.helper.DescriptorCompare;

import java.util.*;

/**
 * This class calculates a commit order for a series of classes
 * based on the dependencies between them. It builds up a graph of
 * dependencies (CommitOrderDependencyNodes) then applies topological
 * sort to them to get an ordering.
 * This is a throwaway class, which exists only for the lifetime of
 * the calculation.
 *
 * The algorithm is described in the method comment for orderCommits().
 * This class also includes static methods for quicksort, copied from
 * the standard libraries and adapted for these objects, since that
 * seemed like the easiest way to sort.
 */
public class CommitOrderCalculator {
    protected int currentTime;
    protected Vector<CommitOrderDependencyNode> nodes;
    protected Vector orderedDescriptors;
    protected AbstractSession session;

    public CommitOrderCalculator(AbstractSession session) {
        super();
        this.currentTime = 0;
        this.nodes = new Vector<>(1);
        this.session = session;
    }

    protected void addNode(ClassDescriptor d) {
        nodes.addElement(new CommitOrderDependencyNode(this, d, session));
    }

    public void addNodes(Vector descriptors) {
        Enumeration descriptorsEnum = descriptors.elements();
        while (descriptorsEnum.hasMoreElements()) {
            ClassDescriptor descriptor = (ClassDescriptor)descriptorsEnum.nextElement();
            addNode(descriptor);
        }
    }

    /**
     * Add to each node the dependent nodes
     */
    public void calculateMappingDependencies() {
        for (Enumeration<CommitOrderDependencyNode> e = nodes.elements(); e.hasMoreElements();) {
            CommitOrderDependencyNode node = e.nextElement();
            node.recordMappingDependencies();
        }
    }

    /**
     * Add to each node the dependent nodes
     */
    public void calculateSpecifiedDependencies() {
        for (Enumeration<CommitOrderDependencyNode> e = nodes.elements(); e.hasMoreElements();) {
            CommitOrderDependencyNode node = e.nextElement();
            node.recordSpecifiedDependencies();
        }
    }

    public void depthFirstSearch() {

        /*
         * Traverse the entire graph in breadth-first order. When finished, every node will have a
         * predecessor which indicates the node that came before it in the search
         * It will also have a discovery time (the value of the counter when we first saw it) and
         * finishingTime (the value of the counter after we've visited all the adjacent nodes).
         * See Cormen, Leiserson and Rivest, Section 23.3, page 477 for a full explanation of the algorithm
         */

        //Setup
        for (Enumeration<CommitOrderDependencyNode> e = getNodes().elements(); e.hasMoreElements();) {
            CommitOrderDependencyNode node = e.nextElement();
            node.markNotVisited();
            node.setPredecessor(null);
        }
        currentTime = 0;

        //Execution
        for (Enumeration<CommitOrderDependencyNode> e = getNodes().elements(); e.hasMoreElements();) {
            CommitOrderDependencyNode node = e.nextElement();
            if (node.hasNotBeenVisited()) {
                node.visit();
            }
        }
    }

    /* Support for quicksort */
    /*
     * Implement the doCompare method.
     */
    private static int doCompare(Object o1, Object o2) {
        // I don't care if they're equal, and I want to sort largest first.
        int first;

        // I don't care if they're equal, and I want to sort largest first.
        int second;
        first = ((CommitOrderDependencyNode)o1).getFinishingTime();
        second = ((CommitOrderDependencyNode)o2).getFinishingTime();
        if (first == second) {
            return new DescriptorCompare().compare(
                    ((CommitOrderDependencyNode)o1).getDescriptor(),
                    ((CommitOrderDependencyNode)o2).getDescriptor());
        }

        if (first > second) {
            return 1;
        } else {
            return -1;
        }
    }

    public int getNextTime() {
        int result = currentTime;
        currentTime++;
        return result;
    }

    public Vector<CommitOrderDependencyNode> getNodes() {
        return nodes;
    }

    /**
     * Return the constraint ordered classes.
     */
    public Vector getOrderedClasses() {
        Vector orderedClasses = org.eclipse.persistence.internal.helper.NonSynchronizedVector.newInstance(getOrderedDescriptors().size());
        for (Enumeration orderedDescriptorsEnum = getOrderedDescriptors().elements();
                 orderedDescriptorsEnum.hasMoreElements();) {
            orderedClasses.addElement(((ClassDescriptor)orderedDescriptorsEnum.nextElement()).getJavaClass());
        }

        return orderedClasses;
    }

    /**
     * Return the constraint ordered descriptors.
     */
    public Vector getOrderedDescriptors() {
        return orderedDescriptors;
    }

    public CommitOrderDependencyNode nodeFor(Class c) {
        for (Enumeration<CommitOrderDependencyNode> e = nodes.elements(); e.hasMoreElements();) {
            CommitOrderDependencyNode n = e.nextElement();
            if (n.getDescriptor().getJavaClass() == c) {
                return n;
            }
        }
        return null;
    }

    public CommitOrderDependencyNode nodeFor(ClassDescriptor d) {
        for (Enumeration<CommitOrderDependencyNode> e = nodes.elements(); e.hasMoreElements();) {
            CommitOrderDependencyNode n = e.nextElement();
            if (n.getDescriptor() == d) {
                return n;
            }
        }
        return null;
    }

    /**
     * Calculate the commit order.
     * Do a depth first search on the graph, skipping nodes that we have
     * already visited or are in the process of visiting. Keep a counter
     * and note when we first encounter a node and when we finish visiting
     * it. Once we've visited everything, sort nodes by finishing time
     */
    public void orderCommits() {
        depthFirstSearch();

        CommitOrderDependencyNode[] nodeArray = new CommitOrderDependencyNode[nodes.size()];
        nodes.copyInto(nodeArray);

        quicksort(nodeArray);
        Vector result = new Vector(nodes.size());
        for (int i = 0; i < nodes.size(); i++) {
            CommitOrderDependencyNode node = nodeArray[i];
            result.addElement(node.getDescriptor());
        }
        this.orderedDescriptors = result;
    }

    /**
     * Perform a sort using the specified comparator object.
     */
    private static void quicksort(Object[] arr) {
        quicksort(arr, 0, arr.length - 1);
    }

    /**
     * quicksort the array of objects.
     *
     * @param arr - an array of objects
     * @param left - the start index - from where to begin sorting
     * @param right - the last index.
     */
    private static void quicksort(Object[] arr, int left, int right) {
        int i;
        int last;

        if (left >= right) {/* do nothing if array contains fewer than two */
            return;/* two elements */
        }
        swap(arr, left, (left + right) / 2);
        last = left;
        for (i = left + 1; i <= right; i++) {
            if (doCompare(arr[i], arr[left]) < 0) {
                swap(arr, ++last, i);
            }
        }
        swap(arr, left, last);
        quicksort(arr, left, last - 1);
        quicksort(arr, last + 1, right);
    }

    private static void swap(Object[] arr, int i, int j) {
        Object tmp;

        tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}