/*
 *  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.policy.RawPageSpace;

import org.mmtk.vm.VM;

import org.vmmagic.pragma.*;
import org.vmmagic.unboxed.*;

/**
 * This supports <i>unsynchronized</i> enqueuing and dequeuing of buffers
 * for shared use.  The data can be added to and removed from either end
 * of the deque. This class is based upon the SharedQueue class.  The sorting
 * routines were modified from code written by Narendran Sachindran and
 * Matthew Hertz for GCTk.
 */
@Uninterruptible public abstract class SortSharedDeque extends SharedDeque {


  private static final int BYTES_PUSHED = BYTES_IN_ADDRESS * 5;
  private static final int MAX_STACK_SIZE = BYTES_PUSHED * 64;
  private static final Offset INSERTION_SORT_LIMIT = Offset.fromIntSignExtend(80);

  /***********************************************************************
   *
   * Class variables
   */

  /**
   * Constructor
   *
   * @param rps The space from which the instance should obtain buffers.
   */
  public SortSharedDeque(String name, RawPageSpace rps, int arity) {
    super(name, rps, arity);
    stackBase = AddressArray.create(MAX_STACK_SIZE);
    stackLoc = 0;
  }

  /***********************************************************************
   *
   * Sorting methods, utilities, and instance variables
   */


  /**
   * Return the sorting key for the object passed as a parameter.
   *
   * @param obj The address of the object whose key is wanted
   * @return The value of the sorting key for this object
   */
  protected abstract Word getKey(Address obj);

  private static final Word mask16 = Word.fromIntZeroExtend(0xffff0000);
  private static final Word mask8 = Word.fromIntZeroExtend(0x0000ff00);
  private static final Word mask4 = Word.fromIntZeroExtend(0x000000f0);
  private static final Word mask2 = Word.fromIntZeroExtend(0x0000000c);
  private static final Word mask1 = Word.fromIntZeroExtend(0x00000002);

  /**
   * Find the highest bit that is set in a longword and return a mask
   * with only that bit set.
   *
   * @param addr Value for which the mask needs to be found
   * @return The highest bit set in the parameter
   */
  private static Word getBitMask(Word addr) {
    int shift = 0;
    if (!addr.and(mask16).isZero()) {
      addr = addr.rshl(16);
      shift += 16;
    }
    if (!addr.and(mask8).isZero()) {
      addr = addr.rshl(8);
      shift += 8;
    }
    if (!addr.and(mask4).isZero()) {
      addr = addr.rshl(4);
      shift += 4;
    }
    if (!addr.and(mask2).isZero()) {
      addr = addr.rshl(2);
      shift += 2;
    }
    if (!addr.and(mask1).isZero()) {
      shift += 1;
    }
    return (Word.one().lsh(shift));
  }

  /**
   * Perform insertion sort within an intra-block address range.
   *
   *  @param begin Start address of the range to be sorted
   *  @param end End address of the range to be sorted
   */
  private void insertionSort(Address begin, Address end) {
    Address rPtr = begin.minus(BYTES_IN_ADDRESS);
    Address lPtr;

    while (rPtr.GE(end)) {
      Address rSlot = rPtr.loadAddress();
      Word rKey = getKey(rSlot);
      lPtr = rPtr.plus(BYTES_IN_ADDRESS);
      while (lPtr.LE(begin)) {
        Address lSlot = lPtr.loadAddress();
        Word lKey = getKey(lSlot);
        if (lKey.GT(rKey)) {
          lPtr.minus(BYTES_IN_ADDRESS).store(lSlot);
          lPtr = lPtr.plus(BYTES_IN_ADDRESS);
        } else {
          break;
        }
      }
      lPtr.minus(BYTES_IN_ADDRESS).store(rSlot);
      rPtr = rPtr.minus(BYTES_IN_ADDRESS);
    }
  }

  /**
   * Sort objects using radix exchange sort. An explicit stack is
   *  maintained to avoid using recursion.
   */
  public void sort() {
    Address startPtr, startLink, endPtr, endLink;
    Word bitMask;
    if (!head.EQ(HEAD_INITIAL_VALUE)) {
      if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(tail.NE(TAIL_INITIAL_VALUE));
      /* Obtain the bitmask for the first iteration and save the start &
         end pointers and the bitmask on the stack */
      initStack();
      startPtr = popStack();
      while (!startPtr.isZero()) {
        startLink = popStack();
        endPtr = popStack();
        endLink = popStack();
        bitMask = (popStack()).toWord();
        if (startLink.NE(endLink)) {
          partition(startPtr, startLink, endPtr, endLink, bitMask);
        } else if (startPtr.GT(endPtr)) {
          /* Use insertionSort for a limited number of objects within
             a single block */
          if (startPtr.diff(endPtr).sLT(INSERTION_SORT_LIMIT)) {
            insertionSort(startPtr, endPtr);
          } else {
            partition(startPtr, startLink, endPtr, endLink, bitMask);
          }
        }
        // Get the next set of data to sort
        startPtr = popStack();
      }
    }
    checkIfSorted();
  }

  /**
   * Partition the slots in an address range based on the value in
   * a particular bit. Place the start & end addresses of the two
   * partitions & a bitmask per partition (which indicates the highest
   * bit position at which the max & min of a partition differ) on the
   * stack. This works just like the partition in quick sort, except
   * that a bit value is being compared here
   *
   * @param startAddr The start address of the range to be sorted
   * @param startLinkAddr The address where the start block has its next field
   * @param endAddr The end address of the range to be sorted
   * @param endLinkAddr The address where the end block has its next field
   * @param bitMask The mask in which the bit to be commpared is set
   */
  private void partition(Address startAddr, Address startLinkAddr,
                               Address endAddr, Address endLinkAddr,
                               Word bitMask) {
    Address travPtr = endAddr;
    Address travLink = endLinkAddr;
    Address stopPtr = startAddr;
    Address stopLink = startLinkAddr;
    Address travSlot, stopSlot;
    Word travKey, stopKey;
    Word lmax = Word.zero(), rmax = Word.zero();
    Word lmin = Word.max(), rmin = Word.max();

    while (true) {
      /* Compute the address range within the current block to compute. */
      Address endOfBlock = travLink;

      /* Move the left pointer until the right pointer is reached
         or an address with a 0 value in the bit position is found. */
      while (true) {
        travSlot = travPtr.loadAddress();
        travKey = getKey(travSlot);

        /* If we reach the end. */
        if (travPtr.EQ(stopPtr))
          break;
        /* If we found a 0 in bit position, break. */
        if (travKey.and(bitMask).isZero())
          break;
        if (travKey.GT(rmax))
          rmax = travKey;
        if (travKey.LT(rmin))
          rmin = travKey;
        /* Move to the next entry. */
        travPtr = travPtr.plus(BYTES_IN_ADDRESS);
        /* If at end of remset block, move to next block */
        if (travPtr.EQ(endOfBlock)) {
          travLink = getPrev(travPtr);
          endOfBlock = travLink;
          travPtr = bufferStart(endOfBlock);
        }
      }

      /* Store the end of the block. */
      endOfBlock = bufferStart(stopPtr);
      /* Move the right pointer until the left pointer is reached
         or an address with a 1 value in the bit position is found. */
      while (true) {
        stopSlot = stopPtr.loadAddress();
        stopKey = getKey(stopSlot);
        /* Found a 1 in bit position, break. */
        if (!stopKey.and(bitMask).isZero())
          break;
        if (stopKey.GT(lmax))
          lmax = stopKey;
        if (stopKey.LT(lmin))
          lmin = stopKey;
        if (stopPtr.EQ(travPtr))
          break;
        /* Move to the next entry, which may be in the next block. */
        if (stopPtr.EQ(endOfBlock)) {
          stopLink = getNext(stopLink);
          stopPtr = stopLink;
          endOfBlock = bufferStart(stopPtr);
        }
        stopPtr = stopPtr.minus(BYTES_IN_ADDRESS);
      }
      if (stopPtr.EQ(travPtr))
        break;
      /* interchange the values pointed to by the left and right pointers */
      travPtr.store(stopSlot);
      stopPtr.store(travSlot);
    }

    /* If max value is not equal to the min value in the right partition,
       (not all slots are identical) push the right partition on to the stack */
    if (rmax.GT(rmin)) {
      if (travPtr.EQ(bufferStart(travPtr))) {
        stopLink = getNext(travLink);
        stopPtr = stopLink;
      } else {
        stopLink = travLink;
        stopPtr = travPtr;
      }
      pushOnStack(getBitMask(rmax.xor(rmin)).toAddress());
      pushOnStack(endLinkAddr);
      pushOnStack(endAddr);
      pushOnStack(stopLink);
      pushOnStack(stopPtr.minus(BYTES_IN_ADDRESS));
    }
    /* if max value is not equal to the min value in the left partition,
       (not all slots are identical) push the left partition on to the stack */
    if (lmax.GT(lmin)) {
      pushOnStack(getBitMask(lmax.xor(lmin)).toAddress());
      pushOnStack(travLink);
      pushOnStack(travPtr);
      pushOnStack(startLinkAddr);
      pushOnStack(startAddr);
    }
  }

  /*************************************************************************
   *
   * Sorting Stack management routines
   */
  private int stackLoc;
  private AddressArray stackBase;

  /*
   * Allocate memory for the stack and intialize it with the first range
   * to partition
   */
  private void initStack() {
    stackLoc = 0;

    Address endOfBlock = tail;
    Address startPtr = bufferStart(endOfBlock);
    Word min = Word.max();
    Word max = Word.zero();
    // Find the max. and min addresses in the object buffer
    while (endOfBlock.NE(HEAD_INITIAL_VALUE)) {
      startPtr = bufferStart(endOfBlock);
      while (startPtr.LT(endOfBlock)) {
        Address startSlot = startPtr.loadAddress();
        Word startKey = getKey(startSlot);
        if (startKey.GT(max))
          max = startKey;
        if (startKey.LT(min))
          min = startKey;
        startPtr = startPtr.plus(BYTES_IN_ADDRESS);
      }
      endOfBlock = getPrev(startPtr);
    }

    // If max and min are different (not all elements are equal), push the
    // start, end and bitmask values on the stack
    if (max.GT(min)) {
      pushOnStack(getBitMask(max.xor(min)).toAddress());
      pushOnStack(tail);
      pushOnStack(bufferStart(tail));
      pushOnStack(startPtr);
      pushOnStack(startPtr.minus(BYTES_IN_ADDRESS));
    }
  }

  /**
   * Push an address on to the stack
   *
  * @param val The address to be pushed
   */
  private void pushOnStack(Address val) {
    stackBase.set(stackLoc, val);
    stackLoc++;
  }

  /**
   * Pop an address from the stack
   *
   * @return The address at the top of the stack, or 0 if stack is empty
   */
  private Address popStack() {
    if (stackLoc == 0)
      return Address.zero();
    stackLoc--;
    return stackBase.get(stackLoc);
  }

  /**
   * Debug routine, used to check if the object buffer is sorted correctly in
   * decreasing final reference deletion time
 */
  private void checkIfSorted() {
    if (VM.VERIFY_ASSERTIONS) {
      Address buf, end;
      Word prevKey = Word.max();
      end = tail;
      buf = bufferStart(end);
      while (buf.NE(HEAD_INITIAL_VALUE)) {
        // iterate through the block
        while (buf.LT(end)) {
          Address slot = buf.loadAddress();
          Word key = getKey(slot);
          if (VM.VERIFY_ASSERTIONS) VM.assertions._assert(key.LE(prevKey));
          prevKey = key;
          buf = buf.plus(BYTES_IN_ADDRESS);
        }
        end = getPrev(end);
        buf = bufferStart(end);
      }
    }
  }
}