/*

 * Copyright (c) 2001, 2012, 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/shared/allocationStats.hpp"

#include "memory/binaryTreeDictionary.hpp"

#include "runtime/globals.hpp"

#include "utilities/ostream.hpp"

#ifndef SERIALGC

#include "gc_implementation/shared/spaceDecorator.hpp"

#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp"

#endif // SERIALGC

////////////////////////////////////////////////////////////////////////////////

// A binary tree based search structure for free blocks.

// This is currently used in the Concurrent Mark&Sweep implementation.

////////////////////////////////////////////////////////////////////////////////

template <class Chunk>

TreeChunk<Chunk>* TreeChunk<Chunk>::as_TreeChunk(Chunk* fc) {

  // Do some assertion checking here.

  return (TreeChunk<Chunk>*) fc;

}

template <class Chunk>

  TreeChunk<Chunk>* nextTC = (TreeChunk<Chunk>*)next();

  if (prev() != NULL) { // interior list node shouldn'r have tree fields

    guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&

              embedded_list()->right()  == NULL, "should be clear");

  }

  if (nextTC != NULL) {

    guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");

    guarantee(nextTC->size() == size(), "wrong size");

  }

}

template <class Chunk>

TreeList<Chunk>* TreeList<Chunk>::as_TreeList(TreeChunk<Chunk>* tc) {

  // This first free chunk in the list will be the tree list.

  assert(tc->size() >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "Chunk is too small for a TreeChunk");

  TreeList<Chunk>* tl = tc->embedded_list();

  tc->set_list(tl);

#ifdef ASSERT

  tl->set_protecting_lock(NULL);

#endif

  tl->set_hint(0);

  tl->set_size(tc->size());

  tl->link_head(tc);

  tl->link_tail(tc);

  tl->set_count(1);

  tl->init_statistics(true /* split_birth */);

  return tl;

}

template <class Chunk>

TreeList<Chunk>* TreeList<Chunk>::as_TreeList(HeapWord* addr, size_t size) {

  TreeChunk<Chunk>* tc = (TreeChunk<Chunk>*) addr;

  assert(size >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "Chunk is too small for a TreeChunk");

  // The space in the heap will have been mangled initially but

  // is not remangled when a free chunk is returned to the free list

  // (since it is used to maintain the chunk on the free list).

  assert((ZapUnusedHeapArea &&

          SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) &&

          SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) &&

          SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) ||

          (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL),

    "Space should be clear or mangled");

  TreeList<Chunk>* tl = TreeList<Chunk>::as_TreeList(tc);

  return tl;

}

template <class Chunk>

  TreeList<Chunk>* retTL = this;

  Chunk* list = head();

  assert(!list || list != list->next(), "Chunk on list twice");

  assert(tc != NULL, "Chunk being removed is NULL");

  assert(parent() == NULL || this == parent()->left() ||

    this == parent()->right(), "list is inconsistent");

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

  Chunk* prevFC = tc->prev();

  TreeChunk<Chunk>* nextTC = TreeChunk<Chunk>::as_TreeChunk(tc->next());

  assert(list != NULL, "should have at least the target chunk");

  // Is this the first item on the list?

  if (tc == list) {

    // The "getChunk..." functions for a TreeList<Chunk> will not return the

    // first chunk in the list unless it is the last chunk in the list

    // because the first chunk is also acting as the tree node.

    // When coalescing happens, however, the first chunk in the a tree

    // list can be the start of a free range.  Free ranges are removed

    // from the free lists so that they are not available to be

    // allocated when the sweeper yields (giving up the free list lock)

    // to allow mutator activity.  If this chunk is the first in the

    // list and is not the last in the list, do the work to copy the

    // TreeList<Chunk> from the first chunk to the next chunk and update all

    // the TreeList<Chunk> pointers in the chunks in the list.

    if (nextTC == NULL) {

      assert(prevFC == NULL, "Not last chunk in the list");

      set_tail(NULL);

      set_head(NULL);

    } else {

      // copy embedded list.

      nextTC->set_embedded_list(tc->embedded_list());

      retTL = nextTC->embedded_list();

      // Fix the pointer to the list in each chunk in the list.

      // This can be slow for a long list.  Consider having

      // an option that does not allow the first chunk on the

      // list to be coalesced.

      for (TreeChunk<Chunk>* curTC = nextTC; curTC != NULL;

          curTC = TreeChunk<Chunk>::as_TreeChunk(curTC->next())) {

        curTC->set_list(retTL);

      }

      // Fix the parent to point to the new TreeList<Chunk>.

      if (retTL->parent() != NULL) {

        if (this == retTL->parent()->left()) {

        } else {

          assert(this == retTL->parent()->right(), "Parent is incorrect");

        }

      }

      // Fix the children's parent pointers to point to the

      // new list.

      assert(right() == retTL->right(), "Should have been copied");

      if (retTL->right() != NULL) {

      }

      assert(left() == retTL->left(), "Should have been copied");

      if (retTL->left() != NULL) {

      }

      retTL->link_head(nextTC);

    }

  } else {

    if (nextTC == NULL) {

      // Removing chunk at tail of list

      link_tail(prevFC);

    }

    // Chunk is interior to the list

  }

  // Below this point the embeded TreeList<Chunk> being used for the

  // tree node may have changed. Don't use "this"

  // TreeList<Chunk>*.

  // chunk should still be a free chunk (bit set in _prev)

  assert(!retTL->head() || retTL->size() == retTL->head()->size(),

    "Wrong sized chunk in list");

  debug_only(

    tc->set_list(NULL);

    bool prev_found = false;

    bool next_found = false;

    for (Chunk* curFC = retTL->head();

         curFC != NULL; curFC = curFC->next()) {

      assert(curFC != tc, "Chunk is still in list");

      if (curFC == prevFC) {

        prev_found = true;

      }

      if (curFC == nextTC) {

        next_found = true;

      }

    }

    assert(prevFC == NULL || prev_found, "Chunk was lost from list");

    assert(nextTC == NULL || next_found, "Chunk was lost from list");

    assert(retTL->parent() == NULL ||

           retTL == retTL->parent()->left() ||

           retTL == retTL->parent()->right(),

           "list is inconsistent");

  )

  retTL->decrement_count();

  assert(retTL->head() == NULL || retTL->head()->prev() == NULL,

    "list invariant");

  assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,

    "list invariant");

  return retTL;

}

template <class Chunk>

  assert(chunk != NULL, "returning NULL chunk");

  assert(chunk->list() == this, "list should be set for chunk");

  assert(tail() != NULL, "The tree list is embedded in the first chunk");

  // which means that the list can never be empty.

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

  Chunk* fc = tail();

  link_tail(chunk);

  assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");

  FreeList<Chunk>::increment_count();

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

}

// Add this chunk at the head of the list.  "At the head of the list"

// is defined to be after the chunk pointer to by head().  This is

// because the TreeList<Chunk> is embedded in the first TreeChunk<Chunk> in the

// list.  See the definition of TreeChunk<Chunk>.

template <class Chunk>

  assert(chunk->list() == this, "list should be set for chunk");

  assert(head() != NULL, "The tree list is embedded in the first chunk");

  assert(chunk != NULL, "returning NULL chunk");

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

  Chunk* fc = head()->next();

  if (fc != NULL) {

  } else {

    assert(tail() == NULL, "List is inconsistent");

    link_tail(chunk);

  }

  assert(!head() || size() == head()->size(), "Wrong sized chunk in list");

  FreeList<Chunk>::increment_count();

  assert(head() == NULL || head()->prev() == NULL, "list invariant");

  assert(tail() == NULL || tail()->next() == NULL, "list invariant");

}

template <class Chunk>

TreeChunk<Chunk>* TreeList<Chunk>::head_as_TreeChunk() {

  assert(head() == NULL || TreeChunk<Chunk>::as_TreeChunk(head())->list() == this,

    "Wrong type of chunk?");

  return TreeChunk<Chunk>::as_TreeChunk(head());

}

template <class Chunk>

TreeChunk<Chunk>* TreeList<Chunk>::first_available() {

  assert(head() != NULL, "The head of the list cannot be NULL");

  Chunk* fc = head()->next();

  TreeChunk<Chunk>* retTC;

  if (fc == NULL) {

    retTC = head_as_TreeChunk();

  } else {

    retTC = TreeChunk<Chunk>::as_TreeChunk(fc);

  }

  assert(retTC->list() == this, "Wrong type of chunk.");

  return retTC;

}

// Returns the block with the largest heap address amongst

// those in the list for this size; potentially slow and expensive,

// use with caution!

template <class Chunk>

TreeChunk<Chunk>* TreeList<Chunk>::largest_address() {

  assert(head() != NULL, "The head of the list cannot be NULL");

  Chunk* fc = head()->next();

  TreeChunk<Chunk>* retTC;

  if (fc == NULL) {

    retTC = head_as_TreeChunk();

  } else {

    // walk down the list and return the one with the highest

    // heap address among chunks of this size.

    Chunk* last = fc;

    while (fc->next() != NULL) {

      if ((HeapWord*)last < (HeapWord*)fc) {

        last = fc;

      }

      fc = fc->next();

    }

    retTC = TreeChunk<Chunk>::as_TreeChunk(last);

  }

  assert(retTC->list() == this, "Wrong type of chunk.");

  return retTC;

}

template <class Chunk>

BinaryTreeDictionary<Chunk>::BinaryTreeDictionary(bool adaptive_freelists, bool splay) :

  _splay(splay), _adaptive_freelists(adaptive_freelists),

template <class Chunk>

BinaryTreeDictionary<Chunk>::BinaryTreeDictionary(MemRegion mr,

                                           bool adaptive_freelists,

                                           bool splay):

  _adaptive_freelists(adaptive_freelists), _splay(splay)

{

  assert(mr.word_size() >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "minimum chunk size");

  reset(mr);

  assert(root()->left() == NULL, "reset check failed");

  assert(root()->right() == NULL, "reset check failed");

  assert(root()->head()->next() == NULL, "reset check failed");

  assert(root()->head()->prev() == NULL, "reset check failed");

}

template <class Chunk>

}

template <class Chunk>

}

template <class Chunk>

void BinaryTreeDictionary<Chunk>::reset(MemRegion mr) {

  assert(mr.word_size() >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "minimum chunk size");

  set_root(TreeList<Chunk>::as_TreeList(mr.start(), mr.word_size()));

}

template <class Chunk>

void BinaryTreeDictionary<Chunk>::reset(HeapWord* addr, size_t byte_size) {

  MemRegion mr(addr, heap_word_size(byte_size));

  reset(mr);

}

template <class Chunk>

void BinaryTreeDictionary<Chunk>::reset() {

  set_root(NULL);

}

// Get a free block of size at least size from tree, or NULL.

// If a splay step is requested, the removal algorithm (only) incorporates

// a splay step as follows:

// . the search proceeds down the tree looking for a possible

//   match. At the (closest) matching location, an appropriate splay step is applied

//   (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned

//   if available, and if it's the last chunk, the node is deleted. A deteleted

//   node is replaced in place by its tree successor.

template <class Chunk>

TreeChunk<Chunk>*

{

  TreeList<Chunk> *curTL, *prevTL;

  TreeChunk<Chunk>* retTC = NULL;

  assert(size >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "minimum chunk size");

  if (FLSVerifyDictionary) {

  }

  // starting at the root, work downwards trying to find match.

  // Remember the last node of size too great or too small.

  for (prevTL = curTL = root(); curTL != NULL;) {

    if (curTL->size() == size) {        // exact match

      break;

    }

    prevTL = curTL;

    if (curTL->size() < size) {        // proceed to right sub-tree

      curTL = curTL->right();

    } else {                           // proceed to left sub-tree

      assert(curTL->size() > size, "size inconsistency");

      curTL = curTL->left();

    }

  }

  if (curTL == NULL) { // couldn't find exact match

    if (dither == FreeBlockDictionary<Chunk>::exactly) return NULL;

    // try and find the next larger size by walking back up the search path

    for (curTL = prevTL; curTL != NULL;) {

      if (curTL->size() >= size) break;

      else curTL = curTL->parent();

    }

    assert(curTL == NULL || curTL->count() > 0,

      "An empty list should not be in the tree");

  }

  if (curTL != NULL) {

    assert(curTL->size() >= size, "size inconsistency");

    if (adaptive_freelists()) {

      // A candidate chunk has been found.  If it is already under

      // populated, get a chunk associated with the hint for this

      // chunk.

      if (curTL->surplus() <= 0) {

        /* Use the hint to find a size with a surplus, and reset the hint. */

        TreeList<Chunk>* hintTL = curTL;

        while (hintTL->hint() != 0) {

          assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(),

            "hint points in the wrong direction");

          assert(curTL != hintTL, "Infinite loop");

          if (hintTL == NULL ||

              hintTL == curTL /* Should not happen but protect against it */ ) {

            // No useful hint.  Set the hint to NULL and go on.

            curTL->set_hint(0);

            break;

          }

          assert(hintTL->size() > size, "hint is inconsistent");

          if (hintTL->surplus() > 0) {

            // The hint led to a list that has a surplus.  Use it.

            // Set the hint for the candidate to an overpopulated

            // size.

            curTL->set_hint(hintTL->size());

            // Change the candidate.

            curTL = hintTL;

            break;

          }

          // The evm code reset the hint of the candidate as

          // at an interim point.  Why?  Seems like this leaves

          // the hint pointing to a list that didn't work.

          // curTL->set_hint(hintTL->size());

        }

      }

    }

    // don't waste time splaying if chunk's singleton

    if (splay && curTL->head()->next() != NULL) {

    }

    retTC = curTL->first_available();

    assert((retTC != NULL) && (curTL->count() > 0),

      "A list in the binary tree should not be NULL");

    assert(retTC->size() >= size,

      "A chunk of the wrong size was found");

  }

  if (FLSVerifyDictionary) {

    verify();

  }

  return retTC;

}

template <class Chunk>

  TreeList<Chunk>* curTL;

  for (curTL = root(); curTL != NULL;) {

    if (curTL->size() == size) {        // exact match

      break;

    }

    if (curTL->size() < size) {        // proceed to right sub-tree

      curTL = curTL->right();

    } else {                           // proceed to left sub-tree

      assert(curTL->size() > size, "size inconsistency");

      curTL = curTL->left();

    }

  }

  return curTL;

}

template <class Chunk>

  size_t size = tc->size();

  if (tl == NULL) {

    return false;

  } else {

  }

}

template <class Chunk>

  TreeList<Chunk> *curTL = root();

  if (curTL != NULL) {

    while(curTL->right() != NULL) curTL = curTL->right();

    return curTL->largest_address();

  } else {