/*
 * Copyright (c) 2013, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#include "precompiled.hpp"
#include "gc_implementation/g1/g1PreserveMarkQueue.hpp"
#include "memory/allocation.hpp"
#include "memory/allocation.inline.hpp"
#include "oops/oopsHierarchy.hpp"

class G1PreserveMarkChunk {
  const size_t _capacity;
  size_t _write_index;
  size_t _read_index;
  G1PreserveMarkQueueEntry* _data;

 public:
  G1PreserveMarkChunk(size_t capacity) : _capacity(capacity), _write_index(0), _read_index(0), _next(NULL) {
    _data = NEW_C_HEAP_ARRAY(G1PreserveMarkQueueEntry, _capacity, mtGC);
  }

  ~G1PreserveMarkChunk() {
    FREE_C_HEAP_ARRAY(G1PreserveMarkQueueEntry, _data, mtGC);
  }

  bool has_data() {
    return _write_index > _read_index;
  }

  bool is_full() {
    assert(_write_index <= _capacity, "written too far");
    return _write_index == _capacity;
  }

  void append(const G1PreserveMarkQueueEntry& entry) {
    assert(!is_full(), "overflow");
    _data[_write_index++] = entry;
  }

  G1PreserveMarkQueueEntry remove_first() {
    assert(has_data(), "empty");
    return _data[_read_index++];
  }

  G1PreserveMarkChunk* _next;
};

bool G1PreserveMarkQueue::has_data() {
  return _current_read_chunk != NULL && _current_read_chunk->has_data();
}

void G1PreserveMarkQueue::append(const oop& obj, const markOop& mark) {
  G1PreserveMarkQueueEntry entry = {obj, mark};
  if (_current_write_chunk == NULL) {
    assert(_current_read_chunk == NULL, "must be");
    _current_write_chunk = new G1PreserveMarkChunk(new_chunk_capacity());
    _current_read_chunk = _current_write_chunk;
  } else if (_current_write_chunk->is_full()) {
    G1PreserveMarkChunk* new_chunk = new G1PreserveMarkChunk(new_chunk_capacity());
    _current_write_chunk->_next = new_chunk;
    _current_write_chunk = new_chunk;
  }

  assert(!_current_write_chunk->is_full(), "full");

  _current_write_chunk->append(entry);
}

G1PreserveMarkQueueEntry G1PreserveMarkQueue::remove_first() {
  assert(has_data(), "empty");
  G1PreserveMarkQueueEntry entry = _current_read_chunk->remove_first();

  if (!_current_read_chunk->has_data()) {
    G1PreserveMarkChunk* old_chunk = _current_read_chunk;
    _current_read_chunk = old_chunk->_next;

    if (old_chunk == _current_write_chunk) {
      assert(_current_read_chunk == NULL, "we are deleting the last chunk");
      _current_write_chunk = NULL;
    }

    delete old_chunk;
  }

  return entry;
}

/////////////// Unit tests ///////////////

#ifndef PRODUCT

void g1PreserveMarkChunkTests() {
  const int chunk_size = 5;

  G1PreserveMarkChunk* chunk = new G1PreserveMarkChunk(chunk_size);

  assert(!chunk->is_full(), "");
  assert(!chunk->has_data(), "");

  for (int i = 0; i < chunk_size; i++) {
    G1PreserveMarkQueueEntry entry = {(oop)i, (markOop)(chunk_size - i)};
    chunk->append(entry);
  }

  assert(chunk->is_full(), "");
  assert(chunk->has_data(), "");

  for (int i = 0; i < chunk_size; i++) {
    assert(chunk->has_data(), "");
    G1PreserveMarkQueueEntry entry = chunk->remove_first();
    assert((oop)i == entry.obj, "");
    assert((markOop)(chunk_size - i) == entry.mark, "");
  }

  assert(chunk->is_full(), "");
  assert(!chunk->has_data(), "");

  delete chunk;
}

void G1PreserveMarkQueue::verify_empty() {
  assert(_current_write_chunk == NULL, "_current_write_chunk not null");
  assert(_current_read_chunk == NULL, "_current_read_chunk not null");
}

void g1PreserveMarkQueueUse(G1PreserveMarkQueue& queue) {
  assert(!queue.has_data(), "");

  const int num_entries = 51;
  for (int i = 0; i < num_entries; i++) {
    queue.append((oop)i, (markOop)(num_entries - i));
  }

  assert(queue.has_data(), "");

  for (int i = 0; i < num_entries; i++) {
    assert(queue.has_data(), "");
    G1PreserveMarkQueueEntry entry = queue.remove_first();
    assert((oop)i == entry.obj, err_msg("wrong data (" PTR_FORMAT ") at index %d", (oopDesc*)(entry.obj), i));
    assert((markOop)(num_entries - i) == entry.mark, err_msg("wrong data (" PTR_FORMAT ") at index %d", entry.mark, i));
  }

  assert(!queue.has_data(), "");

  queue.verify_empty();
}

void g1PreserveMarkQueueTestOneUse() {
  G1PreserveMarkQueue queue(5, 10);
  g1PreserveMarkQueueUse(queue);
}


void g1PreserveMarkQueueTestMultiUse() {
  G1PreserveMarkQueue queue(5, 10);
  g1PreserveMarkQueueUse(queue);
  g1PreserveMarkQueueUse(queue);
  g1PreserveMarkQueueUse(queue);
}

void g1PreserveMarkQueueTests() {
  g1PreserveMarkQueueTestOneUse();
  g1PreserveMarkQueueTestMultiUse();
}

#endif