objecttreestatemachine.java

JPC: x86 PC Hardware Emulator. 牛津大学开发的一个纯JAVA的x86系统结构硬件模拟器。

/*
    JPC: A x86 PC Hardware Emulator for a pure Java Virtual Machine
    Release Version 2.0

    A project from the Physics Dept, The University of Oxford

    Copyright (C) 2007 Isis Innovation Limited

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License version 2 as published by
    the Free Software Foundation.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 
    Details (including contact information) can be found at: 

    www.physics.ox.ac.uk/jpc
*/

package org.jpc.emulator.memory.codeblock.cache;

import java.util.*;
import org.jpc.emulator.memory.*;


/**
 * Holds Objects in a tree that is indexed by an integer sequence.
 *
 * @author Mike Moleschi
 */
public class ObjectTreeStateMachine
{
    /** root node of tree */
    private Node root;
    private Node currentNode;
    private Node currentParent;
    private int parentIndex;

    /**
     * Makes a new empty tree
     */
    public ObjectTreeStateMachine()
    {
        clearAllObjects();
        resetTreeState();
    }

    /**
     * Defines a node in the tree.
     */
    public static abstract class Node
    {
        /**
         * Defines at what size a Narrow Node should grow to before it changes
         * itself to a wide node.
         */
        static final int MAX_NARROW_SIZE = 8;
        static final int MAX_WIDE_SIZE = 700;

        protected int useageCount;
        protected Object obj;
        
        Node()
        {
            useageCount = 0;
            this.obj = null;
        }

        Node(Object obj)
        {
            useageCount = 1;
            this.obj = obj;
        }

        /**
         * Return the size of the node (number of children)
         *
         * @return number of children this node indexes
         */
        public abstract int size();

        /**
         * Add a child node to represent an index. (or replace if index is
         * already used) <br/> 
         * Because this may add more children than the structure can handle,
         * the current node may have to replace itself!  A reference to the
         * resulting valid structure is returned. (this could be the same, or
         * it could be a new replacement node)<br/>
         * If the node passed is null, its reference and index will be 
         * cleared.  If that means this node is then emtpy, it will return null
         * so that the parent can remove it.  In this way a dead end path will 
         * be cleared.
         *
         * @param n node to add as child to current node
         * @param index current element of indexing sequence
         * @return a reference to the currently valid node (null if this node is empty)
         */
        public abstract Node setNode(Node n, int index);

        /**
         * Get a child node that represents an index.
         *
         * @param index current element of indexing sequence
         * @return a reference to the child node
         */
        public abstract Node getNode(int index);
   
        /**
         * Get the Object that represents a x86 byte sequence (if it exists).
         *
         * @param index current element of indexing sequence
         * @return a reference to the code obj that represents the x86 sequnce or null if it doesn't exist
         */
        public Object getObject()
        {
            useageCount++;
            return obj;
        }

        /**
         * Sets the Object that represents a x86 byte sequence.
         * (overwrites if already exists).  If obj is null, it will remove any
         * codeobj stored for that sequence and remove any unique parts of 
         * that sequence.
         *
         * @param obj code obj representing the sequence of x86 bytes
         * @param index current element of indexing sequence
         * @return a reference to this node, incase this node transforms itself (return null if there are no node indexes in this node)
         */
        public void setObject(Object obj)
        {
            useageCount = 1;
            this.obj = obj;
        }

        public int getUsageCount()
        {
            return useageCount;
        }

        public Object peekObject()
        {
            return obj;
        }

        /**
         * Allows a visitor to enter the node.  Will call visitNodes in all the
         * node's children.
         *
         * @param visitor visitor for the node
         * @return whether the visitor should continue (if the visitor is complete, allows it to stop)
         * @see ObjectTreeStateMachineVisitor
         */
        public boolean visitNodes(ObjectTreeStateMachineVisitor visitor)
        {
            return visitor.visitNode(this);
        }

        public void print(String indent)
        {
            System.out.println(indent + getClass().getName() + "(" + size() + ")");
        }
    }
    
    public static class WideNode extends Node
    {
        private int valid;
        private Node[] nodes;
        private Hashtable mappedNodes;
        
        /** Create a new wide node */
        WideNode()
        {
            super();
            nodes = new Node[MAX_WIDE_SIZE];
            valid = 0;
            mappedNodes = null;
        }

        public int size()
        {
            if (mappedNodes == null)
                return valid;
            return mappedNodes.size() + valid;
        } 

        public Node setNode(Node n, int index)
        {
            try
            {
                if (nodes[index] == null)
                    valid++;
                nodes[index] = n;
                if (n == null)
                    valid--;
            } 
            catch (ArrayIndexOutOfBoundsException e)
            {
                if (mappedNodes == null)
                    mappedNodes = new Hashtable(0);
                mappedNodes.put(new Integer(index), n);
            }
            return this;
        }

        public Node getNode(int index)
        {
            try
            {
                return nodes[index]; 
            } 
            catch (ArrayIndexOutOfBoundsException e)
            {
                if (mappedNodes != null)
                    return (Node) mappedNodes.get(new Integer(index));
                return null;
            }
        }

        public boolean visitNodes(ObjectTreeStateMachineVisitor visitor)
        {
            if (!super.visitNodes(visitor))
                return false;

            for(int i = 0; i < nodes.length; i++)
            {
                if (nodes[i] == null)
                    continue;
                if (!nodes[i].visitNodes(visitor))
                    return false;
            }
            
            if (mappedNodes != null)
            {
                Enumeration enumer = mappedNodes.keys();
                while (enumer.hasMoreElements())
                {
                    Integer i = (Integer) enumer.nextElement();
                    
                    Node child = (Node) mappedNodes.get(i);
                    if (!((Node) mappedNodes.get(i)).visitNodes(visitor))
                        return false;
                }
            }

            return true;
        }
        
        public void print(String indent)
        {
            super.print(indent);

            for (int i=0; i<nodes.length; i++)
            {   
                if (nodes[i] != null)
                {
                    System.out.print(indent+i);
                    nodes[i].print(indent+" ");
                }
            }

            if (mappedNodes != null)
            {
                Enumeration enumer = mappedNodes.keys();
                System.out.print("[");
                while (enumer.hasMoreElements())
                {
                    Integer i = (Integer) enumer.nextElement();
		    ((Node) mappedNodes.get(i)).print(indent+" ");
                    System.out.print(i + ", ");
                }
                System.out.println("]");
            }
        }
    }

    public static class NarrowNode extends Node
    {
        private Hashtable nodes;
        
        /** Create a new narrow node */
        NarrowNode()
        {
            super();
            nodes = new Hashtable(0);
        }

        public int size()
        {
            return nodes.size();
        }

        public Node setNode(Node n, int index)
        {
            if (n == null)
            {
                nodes.remove(new Integer(index));
                return this;
            }

            nodes.put(new Integer(index), n);
            if (nodes.size() <= MAX_NARROW_SIZE)
                return this;