001 /*
002 * This file is part of the Jikes RVM project (http://jikesrvm.org).
003 *
004 * This file is licensed to You under the Eclipse Public License (EPL);
005 * You may not use this file except in compliance with the License. You
006 * may obtain a copy of the License at
007 *
008 * http://www.opensource.org/licenses/eclipse-1.0.php
009 *
010 * See the COPYRIGHT.txt file distributed with this work for information
011 * regarding copyright ownership.
012 */
013 package org.mmtk.utility;
014
015 import org.mmtk.utility.gcspy.drivers.AbstractDriver;
016
017 import org.mmtk.vm.Lock;
018 import org.mmtk.vm.VM;
019
020 import org.vmmagic.pragma.*;
021 import org.vmmagic.unboxed.*;
022
023 /**
024 * FIXME This class must be re-written as it makes the assumption that
025 * the implementation language (Java) and the language being
026 * implemented are the same. This is true in the case of Jikes RVM,
027 * but it is not true for any VM implementing a language other than
028 * Java.<p>
029 *
030 * Each instance of this class is a doubly-linked list, in which
031 * each item or node is a piece of memory. The first two words of each node
032 * contains the forward and backward links. The third word contains
033 * the treadmill. The remaining portion is the payload.<p>
034 *
035 * The treadmill object itself must not be moved.<p>
036 *
037 * Access to the instances may be synchronized depending on the
038 * constructor argument.
039 */
040 @Uninterruptible public final class DoublyLinkedList implements Constants {
041
042 /****************************************************************************
043 *
044 * Class variables
045 */
046
047 /****************************************************************************
048 *
049 * Instance variables
050 */
051
052 /**
053 *
054 */
055 private Address head;
056 private final Lock lock;
057 private final int logGranularity; // Each node on the treadmill is guaranteed to be a multiple of granularity.
058
059 /****************************************************************************
060 *
061 * Instance Methods
062 */
063
064 /**
065 * Constructor
066 */
067 public DoublyLinkedList(int logGranularity, boolean shared) {
068 head = Address.zero();
069 lock = shared ? VM.newLock("DoublyLinkedList") : null;
070 this.logGranularity = logGranularity;
071
072 // ensure that granularity is big enough for midPayloadToNode to work
073 Word tmp = Word.one().lsh(logGranularity);
074 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(tmp.and(nodeMask).EQ(tmp));
075 }
076
077 // Offsets are relative to the node (not the payload)
078 //
079 private static final Offset PREV_OFFSET = Offset.fromIntSignExtend(0 * BYTES_IN_ADDRESS);
080 private static Offset NEXT_OFFSET = Offset.fromIntSignExtend(1 * BYTES_IN_ADDRESS);
081 private static Offset HEADER_SIZE = Offset.fromIntSignExtend(2 * BYTES_IN_ADDRESS);
082
083 private static final Word nodeMask;
084 static {
085 Word mask = Word.one();
086 while (mask.LE(HEADER_SIZE.plus(MAX_BYTES_PADDING).toWord())) mask = mask.lsh(1);
087 nodeMask = mask.minus(Word.one()).not();
088 }
089
090 @Inline
091 public static int headerSize() {
092 return HEADER_SIZE.toInt();
093 }
094
095 public boolean isNode(Address node) {
096 return node.toWord().rshl(logGranularity).lsh(logGranularity).EQ(node.toWord());
097 }
098
099 @Inline
100 public static Address nodeToPayload(Address node) {
101 return node.plus(HEADER_SIZE);
102 }
103
104 @Inline
105 public static Address midPayloadToNode(Address payload) {
106 // This method words as long as you are less than MAX_BYTES_PADDING into the payload.
107 return payload.toWord().and(nodeMask).toAddress();
108 }
109
110 @Inline
111 public void add(Address node) {
112 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isNode(node));
113 if (lock != null) lock.acquire();
114 node.store(Address.zero(), PREV_OFFSET);
115 node.store(head, NEXT_OFFSET);
116 if (!head.isZero())
117 head.store(node, PREV_OFFSET);
118 head = node;
119 if (lock != null) lock.release();
120 }
121
122 @Inline
123 public void remove(Address node) {
124 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isNode(node));
125 if (lock != null) lock.acquire();
126 Address prev = node.loadAddress(PREV_OFFSET);
127 Address next = node.loadAddress(NEXT_OFFSET);
128 // Splice the node out of the list
129 if (!next.isZero())
130 next.store(prev, PREV_OFFSET);
131 if (prev.isZero())
132 head = next;
133 else
134 prev.store(next, NEXT_OFFSET);
135 // Null out node's reference to the list
136 node.store(Address.zero(), PREV_OFFSET);
137 node.store(Address.zero(), NEXT_OFFSET);
138 if (lock != null) lock.release();
139 }
140
141 @Inline
142 public Address getHead() {
143 return head;
144 }
145
146 @Inline
147 public Address getNext(Address node) {
148 return node.loadAddress(NEXT_OFFSET);
149 }
150
151 @Inline
152 public Address pop() {
153 Address first = head;
154 if (!first.isZero())
155 remove(first);
156 return first;
157 }
158
159 @Inline
160 public boolean isEmpty() {
161 return head.isZero();
162 }
163
164 /**
165 * Return true if a cell is on a given treadmill
166 *
167 * @param node The cell being searched for
168 * @return <code>true</code> if the cell is found on the treadmill
169 */
170 public boolean isMember(Address node) {
171 if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(isNode(node));
172 boolean result = false;
173 if (lock != null) lock.acquire();
174 Address cur = head;
175 while (!cur.isZero()) {
176 if (cur.EQ(node)) {
177 result = true;
178 break;
179 }
180 cur = cur.loadAddress(NEXT_OFFSET);
181 }
182 if (lock != null) lock.release();
183 return result;
184 }
185
186 public void show() {
187 if (lock != null) lock.acquire();
188 Address cur = head;
189 Log.write(cur);
190 while (!cur.isZero()) {
191 cur = cur.loadAddress(NEXT_OFFSET);
192 Log.write(" -> "); Log.write(cur);
193 }
194 Log.writeln();
195 if (lock != null) lock.release();
196 }
197
198
199 /**
200 * Gather data for GCSpy
201 * @param driver the GCSpy space driver
202 */
203 void gcspyGatherData(AbstractDriver driver) {
204 // GCSpy doesn't need a lock (in its stop the world config)
205 Address cur = head;
206 while (!cur.isZero()) {
207 driver.scan(cur);
208 cur = cur.loadAddress(NEXT_OFFSET);
209 }
210 }
211 }