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.deque;
014
015 import org.mmtk.utility.Constants;
016
017 import org.vmmagic.unboxed.*;
018 import org.vmmagic.pragma.*;
019
020 /**
021 * Class that defines a doubly-linked double-ended queue (deque). The
022 * double-linking increases the space demands slightly, but makes it far
023 * more efficient to dequeue buffers and, for example, enables sorting of
024 * its contents.
025 */
026 @Uninterruptible class Deque implements Constants {
027
028 /****************************************************************************
029 *
030 * Protected instance methods
031 *
032 * protected int enqueued;
033 */
034
035 /**
036 *
037 */
038 @Inline
039 protected final Offset bufferOffset(Address buf) {
040 return buf.toWord().and(BUFFER_MASK).toOffset();
041 }
042 @Inline
043 protected final Address bufferStart(Address buf) {
044 return buf.toWord().and(BUFFER_MASK.not()).toAddress();
045 }
046 @Inline
047 protected final Address bufferEnd(Address buf) {
048 return bufferStart(buf).plus(USABLE_BUFFER_BYTES);
049 }
050 @Inline
051 protected final Address bufferFirst(Address buf) {
052 return bufferStart(buf);
053 }
054 @Inline
055 protected final Address bufferLast(Address buf, int arity) {
056 return bufferStart(buf).plus(bufferLastOffset(arity));
057 }
058 @Inline
059 protected final Address bufferLast(Address buf) {
060 return bufferLast(buf, 1);
061 }
062 @Inline
063 protected final Offset bufferLastOffset(int arity) {
064 return Offset.fromIntZeroExtend(USABLE_BUFFER_BYTES - BYTES_IN_ADDRESS -
065 (USABLE_BUFFER_BYTES % (arity << LOG_BYTES_IN_ADDRESS)));
066 }
067
068 /****************************************************************************
069 *
070 * Private and protected static final fields (aka constants)
071 */
072
073 /**
074 *
075 */
076 protected static final int LOG_PAGES_PER_BUFFER = 0;
077 protected static final int PAGES_PER_BUFFER = 1 << LOG_PAGES_PER_BUFFER;
078 private static final int LOG_BUFFER_SIZE = (LOG_BYTES_IN_PAGE + LOG_PAGES_PER_BUFFER);
079 protected static final int BUFFER_SIZE = 1 << LOG_BUFFER_SIZE;
080 protected static final Word BUFFER_MASK = Word.one().lsh(LOG_BUFFER_SIZE).minus(Word.one());
081 protected static final int NEXT_FIELD_OFFSET = BYTES_IN_ADDRESS;
082 protected static final int META_DATA_SIZE = 2 * BYTES_IN_ADDRESS;
083 protected static final int USABLE_BUFFER_BYTES = BUFFER_SIZE - META_DATA_SIZE;
084 protected static final Address TAIL_INITIAL_VALUE = Address.zero();
085 protected static final Address HEAD_INITIAL_VALUE = Address.zero();
086 }