core/src/core/org/jnode/vm/Region.java - new-gc-algorithms in JNode

/*
 * $Id$
 *
 * Copyright (C) 2003-2009 JNode.org
 *
 * This library is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published
 * by the Free Software Foundation; either version 2.1 of the License, or
 * (at your option) any later version.
 *
 * This library 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 Lesser General Public 
 * License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with this library; If not, write to the Free Software Foundation, Inc., 
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
package org.jnode.vm;

import org.jnode.system.ResourceOwner;


/**
 * A Region is a single part of an addressspace.
 *
 * @author epr
 */
public abstract class Region {

    /**
     * The owner of this region
     */
    private final ResourceOwner owner;
    /**
     * Reference to next region
     */
    private Region next;

    /**
     * Create a new instance
     *
     * @param owner
     */
    protected Region(ResourceOwner owner) {
        this.owner = owner;
    }

    /**
     * Gets the owner of this region.
     *
     * @return The owner
     */
    public ResourceOwner getOwner() {
        return owner;
    }

    /**
     * Add the given region to the given list of region, such that
     * the list is sorted from low to high starting addresses.
     *
     * @param first
     * @param addition
     * @return The new list
     */
    protected static Region add(Region first, Region addition) {
        if (first == null) {
            return addition;
        }
        if (addition.compareTo(first) < 0) {
            // addition < first
            addition.next = first;
            return addition;
        }
        Region r = first;
        while ((r.next != null) && (r.next.compareTo(addition) <= 0)) {
            r = r.next;
        }
        addition.next = r.next;
        r.next = addition;
        return first;
    }

    /**
     * Remove the given region from the given list and return the new list.
     *
     * @param list
     * @param removal
     * @return The new list
     */
    protected static Region remove(Region list, Region removal) {
        if (list == removal) {
            list = list.next;
            removal.next = null;
            return list;
        } else if (list == null) {
            removal.next = null;
            return null;
        } else {
            Region r = list;
            while ((r.next != null) && (r.next != removal)) {
                r = r.next;
            }
            if (r.next == null) {
                removal.next = null;
                return list;
            } else {
                r.next = removal.next;
                removal.next = null;
                return list;
            }
        }
    }

    /**
     * Is the given testRegion still a free region?
     *
     * @param list
     * @param testRegion
     * @return True if there is no region in the given list that has any overlap
     *         with the given region.
     */
    protected static boolean isFree(Region list, Region testRegion) {
        Region r = list;
        while (r != null) {
            if (r.compareTo(testRegion) == 0) {
                return false;
            }
            r = r.next;
        }
        return true;
    }

    /**
     * Is the given testRegion still a free region?
     *
     * @param list
     * @param testRegion
     * @return True if there is no region in the given list that has any overlap
     *         with the given region.
     */
    protected static Region get(Region list, Region testRegion) {
        Region r = list;
        while (r != null) {
            if (r.compareTo(testRegion) == 0) {
                return r;
            }
            r = r.next;
        }
        return null;
    }

    /**
     * Compare to regions.
     *
     * @param other
     * @return a negative integer, zero, or a positive integer as
     *         this object is less than, equal to, or greater than the
     *         specified region. If the regions overlap, 0 is returned.
     */
    public abstract int compareTo(Region other);

}

1	/*
2	* $Id$
3	*
4	* Copyright (C) 2003-2009 JNode.org
5	*
6	* This library is free software; you can redistribute it and/or modify it
7	* under the terms of the GNU Lesser General Public License as published
8	* by the Free Software Foundation; either version 2.1 of the License, or
9	* (at your option) any later version.
10	*
11	* This library is distributed in the hope that it will be useful, but
12	* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13	* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
14	* License for more details.
15	*
16	* You should have received a copy of the GNU Lesser General Public License
17	* along with this library; If not, write to the Free Software Foundation, Inc.,
18	* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19	*/
20
21	package org.jnode.vm;
22
23	import org.jnode.system.ResourceOwner;
24
25
26	/**
27	* A Region is a single part of an addressspace.
28	*
29	* @author epr
30	*/
31	public abstract class Region {
32
33	/**
34	* The owner of this region
35	*/
36	private final ResourceOwner owner;
37	/**
38	* Reference to next region
39	*/
40	private Region next;
41
42	/**
43	* Create a new instance
44	*
45	* @param owner
46	*/
47	protected Region(ResourceOwner owner) {
48	this.owner = owner;
49	}
50
51	/**
52	* Gets the owner of this region.
53	*
54	* @return The owner
55	*/
56	public ResourceOwner getOwner() {
57	return owner;
58	}
59
60	/**
61	* Add the given region to the given list of region, such that
62	* the list is sorted from low to high starting addresses.
63	*
64	* @param first
65	* @param addition
66	* @return The new list
67	*/
68	protected static Region add(Region first, Region addition) {
69	if (first == null) {
70	return addition;
71	}
72	if (addition.compareTo(first) < 0) {
73	// addition < first
74	addition.next = first;
75	return addition;
76	}
77	Region r = first;
78	while ((r.next != null) && (r.next.compareTo(addition) <= 0)) {
79	r = r.next;
80	}
81	addition.next = r.next;
82	r.next = addition;
83	return first;
84	}
85
86	/**
87	* Remove the given region from the given list and return the new list.
88	*
89	* @param list
90	* @param removal
91	* @return The new list
92	*/
93	protected static Region remove(Region list, Region removal) {
94	if (list == removal) {
95	list = list.next;
96	removal.next = null;
97	return list;
98	} else if (list == null) {
99	removal.next = null;
100	return null;
101	} else {
102	Region r = list;
103	while ((r.next != null) && (r.next != removal)) {
104	r = r.next;
105	}
106	if (r.next == null) {
107	removal.next = null;
108	return list;
109	} else {
110	r.next = removal.next;
111	removal.next = null;
112	return list;
113	}
114	}
115	}
116
117	/**
118	* Is the given testRegion still a free region?
119	*
120	* @param list
121	* @param testRegion
122	* @return True if there is no region in the given list that has any overlap
123	* with the given region.
124	*/
125	protected static boolean isFree(Region list, Region testRegion) {
126	Region r = list;
127	while (r != null) {
128	if (r.compareTo(testRegion) == 0) {
129	return false;
130	}
131	r = r.next;
132	}
133	return true;
134	}
135
136	/**
137	* Is the given testRegion still a free region?
138	*
139	* @param list
140	* @param testRegion
141	* @return True if there is no region in the given list that has any overlap
142	* with the given region.
143	*/
144	protected static Region get(Region list, Region testRegion) {
145	Region r = list;
146	while (r != null) {
147	if (r.compareTo(testRegion) == 0) {
148	return r;
149	}
150	r = r.next;
151	}
152	return null;
153	}
154
155	/**
156	* Compare to regions.
157	*
158	* @param other
159	* @return a negative integer, zero, or a positive integer as
160	* this object is less than, equal to, or greater than the
161	* specified region. If the regions overlap, 0 is returned.
162	*/
163	public abstract int compareTo(Region other);
164
165	}

Gitorious