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 @Inline
036 protected final Offset bufferOffset(Address buf) {
037 return buf.toWord().and(BUFFER_MASK).toOffset();
038 }
039 @Inline
040 protected final Address bufferStart(Address buf) {
041 return buf.toWord().and(BUFFER_MASK.not()).toAddress();
042 }
043 @Inline
044 protected final Address bufferEnd(Address buf) {
045 return bufferStart(buf).plus(USABLE_BUFFER_BYTES);
046 }
047 @Inline
048 protected final Address bufferFirst(Address buf) {
049 return bufferStart(buf);
050 }
051 @Inline
052 protected final Address bufferLast(Address buf, int arity) {
053 return bufferStart(buf).plus(bufferLastOffset(arity));
054 }
055 @Inline
056 protected final Address bufferLast(Address buf) {
057 return bufferLast(buf, 1);
058 }
059 @Inline
060 protected final Offset bufferLastOffset(int arity) {
061 return Offset.fromIntZeroExtend(USABLE_BUFFER_BYTES - BYTES_IN_ADDRESS -
062 (USABLE_BUFFER_BYTES % (arity << LOG_BYTES_IN_ADDRESS)));
063 }
064
065 /****************************************************************************
066 *
067 * Private and protected static final fields (aka constants)
068 */
069 protected static final int LOG_PAGES_PER_BUFFER = 0;
070 protected static final int PAGES_PER_BUFFER = 1 << LOG_PAGES_PER_BUFFER;
071 private static final int LOG_BUFFER_SIZE = (LOG_BYTES_IN_PAGE + LOG_PAGES_PER_BUFFER);
072 protected static final int BUFFER_SIZE = 1 << LOG_BUFFER_SIZE;
073 protected static final Word BUFFER_MASK = Word.one().lsh(LOG_BUFFER_SIZE).minus(Word.one());
074 protected static final int NEXT_FIELD_OFFSET = BYTES_IN_ADDRESS;
075 protected static final int META_DATA_SIZE = 2 * BYTES_IN_ADDRESS;
076 protected static final int USABLE_BUFFER_BYTES = BUFFER_SIZE - META_DATA_SIZE;
077 protected static final Address TAIL_INITIAL_VALUE = Address.zero();
078 protected static final Address HEAD_INITIAL_VALUE = Address.zero();
079 }