/*

 * 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.

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

  // Do some assertion checking here.

}

  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");

    nextTC->verify_tree_chunk_list();

  }

}

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

  tc->set_list(tl);

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

  tl->link_head(tc);

  tl->link_tail(tc);

  tl->set_count(1);

  return tl;

}

}

  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(tc->is_free(), "Header is not marked correctly");

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

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

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

  // Is this the first item on the list?

  if (tc == list) {

    // 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

    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.

        curTC->set_list(retTL);

      }

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

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

          retTL->parent()->set_left(retTL);

        } else {

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

          retTL->parent()->set_right(retTL);

        }

      }

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

      // new list.

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

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

        retTL->right()->set_parent(retTL);

      }

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

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

        retTL->left()->set_parent(retTL);

      }

      retTL->link_head(nextTC);

      assert(nextTC->is_free(), "Should be a free chunk");

    }

  } else {

    if (nextTC == NULL) {

      // Removing chunk at tail of list

      link_tail(prevFC);

    }

    // Chunk is interior to the list

    prevFC->link_after(nextTC);

  }

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

  // 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->link_prev(NULL);

    tc->link_next(NULL);

    tc->set_list(NULL);

    bool prev_found = false;

    bool next_found = false;

         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(tc->is_free(), "Should still be a free chunk");

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

    "list invariant");

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

    "list invariant");

  return retTL;

}

  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(!verify_chunk_in_free_list(chunk), "Double entry");

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

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

  fc->link_after(chunk);

  link_tail(chunk);

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

  debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)

  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

  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(!verify_chunk_in_free_list(chunk), "Double entry");

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

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

  if (fc != NULL) {

    chunk->link_after(fc);

  } else {

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

    link_tail(chunk);

  }

  head()->link_after(chunk);

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

  debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)

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

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

}

}

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

  if (fc == NULL) {

    retTC = head_as_TreeChunk();

  } else {

  }

  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!

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

  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.

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

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

        last = fc;

      }

      fc = fc->next();

    }

  }

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

  return retTC;

}

  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");

  assert(total_size() == root()->size(), "reset check failed");

  assert(total_free_blocks() == 1, "reset check failed");

}

  _total_size = _total_size + inc;

}

  _total_size = _total_size - dec;

}

  set_total_size(mr.word_size());

  set_total_free_blocks(1);

}

  MemRegion mr(addr, heap_word_size(byte_size));

  reset(mr);

}

  set_root(NULL);

  set_total_size(0);

  set_total_free_blocks(0);

}

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

{

  if (FLSVerifyDictionary) {

    verify_tree();

  }

  // 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

    // 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");

    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");

    remove_chunk_from_tree(retTC);

    assert(retTC->is_free(), "Header is not marked correctly");

  }

  if (FLSVerifyDictionary) {

    verify();

  }

  return retTC;

}

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

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

      break;