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 */
013package org.mmtk.utility.deque;
014
015import static org.mmtk.utility.Constants.*;
016
017import org.vmmagic.unboxed.*;
018import 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 {
027
028  /****************************************************************************
029   *
030   * Protected instance methods
031   *
032   * protected int enqueued;
033   */
034
035  /**
036   * @param buf the buffer's address
037   * @return the buffer's offset
038   */
039  @Inline
040  protected final Offset bufferOffset(Address buf) {
041    return buf.toWord().and(BUFFER_MASK).toOffset();
042  }
043  @Inline
044  protected final Address bufferStart(Address buf) {
045    return buf.toWord().and(BUFFER_MASK.not()).toAddress();
046  }
047  @Inline
048  protected final Address bufferEnd(Address buf) {
049    return bufferStart(buf).plus(USABLE_BUFFER_BYTES);
050  }
051  @Inline
052  protected final Address bufferFirst(Address buf) {
053    return bufferStart(buf);
054  }
055  @Inline
056  protected final Address bufferLast(Address buf, int arity) {
057    return bufferStart(buf).plus(bufferLastOffset(arity));
058  }
059  @Inline
060  protected final Address bufferLast(Address buf) {
061    return bufferLast(buf, 1);
062  }
063  @Inline
064  protected final Offset bufferLastOffset(int arity) {
065    return Offset.fromIntZeroExtend(USABLE_BUFFER_BYTES - BYTES_IN_ADDRESS -
066        (USABLE_BUFFER_BYTES % (arity << LOG_BYTES_IN_ADDRESS)));
067  }
068
069  /****************************************************************************
070   *
071   * Private and protected static final fields (aka constants)
072   */
073
074  /**
075   *
076   */
077  protected static final int LOG_PAGES_PER_BUFFER = 0;
078  protected static final int PAGES_PER_BUFFER = 1 << LOG_PAGES_PER_BUFFER;
079  private static final int LOG_BUFFER_SIZE = (LOG_BYTES_IN_PAGE + LOG_PAGES_PER_BUFFER);
080  protected static final int BUFFER_SIZE = 1 << LOG_BUFFER_SIZE;
081  protected static final Word BUFFER_MASK = Word.one().lsh(LOG_BUFFER_SIZE).minus(Word.one());
082  protected static final int NEXT_FIELD_OFFSET = BYTES_IN_ADDRESS;
083  protected static final int META_DATA_SIZE = 2 * BYTES_IN_ADDRESS;
084  protected static final int USABLE_BUFFER_BYTES = BUFFER_SIZE - META_DATA_SIZE;
085  protected static final Address TAIL_INITIAL_VALUE = Address.zero();
086  protected static final Address HEAD_INITIAL_VALUE = Address.zero();
087}