| /* |
| * This file is part of the Jikes RVM project (http://jikesrvm.org). |
| * |
| * This file is licensed to You under the Eclipse Public License (EPL); |
| * You may not use this file except in compliance with the License. You |
| * may obtain a copy of the License at |
| * |
| * http://www.opensource.org/licenses/eclipse-1.0.php |
| * |
| * See the COPYRIGHT.txt file distributed with this work for information |
| * regarding copyright ownership. |
| */ |
| package org.mmtk.utility.deque; |
| |
| import org.mmtk.utility.Constants; |
| |
| import org.vmmagic.unboxed.*; |
| import org.vmmagic.pragma.*; |
| |
| /** |
| * Class that defines a doubly-linked double-ended queue (deque). The |
| * double-linking increases the space demands slightly, but makes it far |
| * more efficient to dequeue buffers and, for example, enables sorting of |
| * its contents. |
| */ |
| @Uninterruptible class Deque implements Constants { |
| |
| /**************************************************************************** |
| * |
| * Protected instance methods |
| * |
| * protected int enqueued; |
| */ |
| |
| @Inline |
| protected final Offset bufferOffset(Address buf) { |
| return buf.toWord().and(BUFFER_MASK).toOffset(); |
| } |
| @Inline |
| protected final Address bufferStart(Address buf) { |
| return buf.toWord().and(BUFFER_MASK.not()).toAddress(); |
| } |
| @Inline |
| protected final Address bufferEnd(Address buf) { |
| return bufferStart(buf).plus(USABLE_BUFFER_BYTES); |
| } |
| @Inline |
| protected final Address bufferFirst(Address buf) { |
| return bufferStart(buf); |
| } |
| @Inline |
| protected final Address bufferLast(Address buf, int arity) { |
| return bufferStart(buf).plus(bufferLastOffset(arity)); |
| } |
| @Inline |
| protected final Address bufferLast(Address buf) { |
| return bufferLast(buf, 1); |
| } |
| @Inline |
| protected final Offset bufferLastOffset(int arity) { |
| return Offset.fromIntZeroExtend(USABLE_BUFFER_BYTES - BYTES_IN_ADDRESS - |
| (USABLE_BUFFER_BYTES % (arity << LOG_BYTES_IN_ADDRESS))); |
| } |
| |
| /**************************************************************************** |
| * |
| * Private and protected static final fields (aka constants) |
| */ |
| protected static final int LOG_PAGES_PER_BUFFER = 0; |
| protected static final int PAGES_PER_BUFFER = 1 << LOG_PAGES_PER_BUFFER; |
| private static final int LOG_BUFFER_SIZE = (LOG_BYTES_IN_PAGE + LOG_PAGES_PER_BUFFER); |
| protected static final int BUFFER_SIZE = 1 << LOG_BUFFER_SIZE; |
| protected static final Word BUFFER_MASK = Word.one().lsh(LOG_BUFFER_SIZE).minus(Word.one()); |
| protected static final int NEXT_FIELD_OFFSET = BYTES_IN_ADDRESS; |
| protected static final int META_DATA_SIZE = 2 * BYTES_IN_ADDRESS; |
| protected static final int USABLE_BUFFER_BYTES = BUFFER_SIZE - META_DATA_SIZE; |
| protected static final Address TAIL_INITIAL_VALUE = Address.zero(); |
| protected static final Address HEAD_INITIAL_VALUE = Address.zero(); |
| } |