/*

 * Copyright 2001-2008 Sun Microsystems, Inc.  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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

# include "incls/_precompiled.incl"

# include "incls/_binaryTreeDictionary.cpp.incl"

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

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

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

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

TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) {

  // Do some assertion checking here.

  return (TreeChunk*) fc;

}

void TreeChunk::verifyTreeChunkList() const {

  TreeChunk* nextTC = (TreeChunk*)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");

    nextTC->verifyTreeChunkList();

  }

}

TreeList* TreeList::as_TreeList(TreeChunk* tc) {

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

  assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");

  TreeList* 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();

  tl->setParent(NULL);

  tl->setLeft(NULL);

  tl->setRight(NULL);

  return tl;

}

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

  TreeChunk* tc = (TreeChunk*) addr;

  assert(size >= sizeof(TreeChunk), "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");

  tc->setSize(size);

  tc->linkPrev(NULL);

  tc->linkNext(NULL);

  TreeList* tl = TreeList::as_TreeList(tc);

  return tl;

}

TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {

  TreeList* retTL = this;

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

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

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

  FreeChunk* prevFC = tc->prev();

  TreeChunk* nextTC = TreeChunk::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 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 from the first chunk to the next chunk and update all

    // the TreeList 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* curTC = nextTC; curTC != NULL;

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

        curTC->set_list(retTL);

      }

      // Fix the parent to point to the new TreeList.

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

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

          retTL->parent()->setLeft(retTL);

        } else {

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

          retTL->parent()->setRight(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()->setParent(retTL);

      }

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

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

        retTL->left()->setParent(retTL);

      }

      retTL->link_head(nextTC);

      assert(nextTC->isFree(), "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->linkAfter(nextTC);

  }

  // Below this point the embeded TreeList being used for the

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

  // TreeList*.

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

    tc->linkNext(NULL);

    tc->set_list(NULL);

    bool prev_found = false;

    bool next_found = false;

    for (FreeChunk* 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(tc->isFree(), "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;

}

void TreeList::returnChunkAtTail(TreeChunk* 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(!verifyChunkInFreeLists(chunk), "Double entry");

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

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

  FreeChunk* fc = tail();

  fc->linkAfter(chunk);

  link_tail(chunk);

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

  increment_count();

  debug_only(increment_returnedBytes_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

// because the TreeList is embedded in the first TreeChunk in the

// list.  See the definition of TreeChunk.

void TreeList::returnChunkAtHead(TreeChunk* 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(!verifyChunkInFreeLists(chunk), "Double entry");

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

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

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

  if (fc != NULL) {

    chunk->linkAfter(fc);

  } else {

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

    link_tail(chunk);

  }

  head()->linkAfter(chunk);

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

  increment_count();

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

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

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

}

TreeChunk* TreeList::head_as_TreeChunk() {

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

    "Wrong type of chunk?");

  return TreeChunk::as_TreeChunk(head());

}

TreeChunk* TreeList::first_available() {

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

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

  TreeChunk* retTC;

  if (fc == NULL) {

    retTC = head_as_TreeChunk();

  } else {

    retTC = TreeChunk::as_TreeChunk(fc);

  }

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

  return retTC;

}

BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay):

  _splay(splay)

{

  assert(mr.byte_size() > 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");

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

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

}

void BinaryTreeDictionary::inc_totalSize(size_t inc) {

  _totalSize = _totalSize + inc;

}

void BinaryTreeDictionary::dec_totalSize(size_t dec) {

  _totalSize = _totalSize - dec;

}

void BinaryTreeDictionary::reset(MemRegion mr) {

  assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");

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

  set_totalSize(mr.word_size());

  set_totalFreeBlocks(1);

}

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

  MemRegion mr(addr, heap_word_size(byte_size));

  reset(mr);

}

void BinaryTreeDictionary::reset() {

  set_root(NULL);

  set_totalSize(0);

  set_totalFreeBlocks(0);

}

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

TreeChunk*

BinaryTreeDictionary::getChunkFromTree(size_t size, Dither dither, bool splay)

{

  TreeList *curTL, *prevTL;

  TreeChunk* retTC = NULL;

  assert(size >= MIN_TREE_CHUNK_SIZE, "minimum chunk size");

  if (FLSVerifyDictionary) {

    verifyTree();

  }

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

    if (UseCMSAdaptiveFreeLists) {

      // 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* hintTL = curTL;

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

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

            "hint points in the wrong direction");

          hintTL = findList(hintTL->hint());

          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 interrim 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) {

      semiSplayStep(curTL);

    }

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

    removeChunkFromTree(retTC);

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

  }

  if (FLSVerifyDictionary) {

    verify();

  }

  return retTC;

}

TreeList* BinaryTreeDictionary::findList(size_t size) const {

  TreeList* 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;

}

bool BinaryTreeDictionary::verifyChunkInFreeLists(FreeChunk* tc) const {

  size_t size = tc->size();

  TreeList* tl = findList(size);

  if (tl == NULL) {

    return false;

  } else {

    return tl->verifyChunkInFreeLists(tc);

  }

}

FreeChunk* BinaryTreeDictionary::findLargestDict() const {

  TreeList *curTL = root();

  if (curTL != NULL) {

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

    return curTL->first_available();

  } else {

    return NULL;

  }

}

// Remove the current chunk from the tree.  If it is not the last

// chunk in a list on a tree node, just unlink it.

// If it is the last chunk in the list (the next link is NULL),

// remove the node and repair the tree.

TreeChunk*

BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) {

  assert(tc != NULL, "Should not call with a NULL chunk");

  assert(tc->isFree(), "Header is not marked correctly");

  TreeList *newTL, *parentTL;

  TreeChunk* retTC;

  TreeList* tl = tc->list();

  debug_only(

    bool removing_only_chunk = false;

    if (tl == _root) {

      if ((_root->left() == NULL) && (_root->right() == NULL)) {

        if (_root->count() == 1) {

          assert(_root->head() == tc, "Should only be this one chunk");

          removing_only_chunk = true;

        }

      }

    }

  )

  assert(tl != NULL, "List should be set");

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

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

  bool complicatedSplice = false;

  retTC = tc;

  // Removing this chunk can have the side effect of changing the node

  // (TreeList*) in the tree.  If the node is the root, update it.

  TreeList* replacementTL = tl->removeChunkReplaceIfNeeded(tc);

  assert(tc->isFree(), "Chunk should still be free");

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

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

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

         "list is inconsistent");

  if (tl == root()) {

    assert(replacementTL->parent() == NULL, "Incorrectly replacing root");

    set_root(replacementTL);

  }

  debug_only(

    if (tl != replacementTL) {

      assert(replacementTL->head() != NULL,

        "If the tree list was replaced, it should not be a NULL list");

      TreeList* rhl = replacementTL->head_as_TreeChunk()->list();

      TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list();

      assert(rhl == replacementTL, "Broken head");

      assert(rtl == replacementTL, "Broken tail");

      assert(replacementTL->size() == tc->size(),  "Broken size");

    }

  )

  // Does the tree need to be repaired?

  if (replacementTL->count() == 0) {

    assert(replacementTL->head() == NULL &&

           replacementTL->tail() == NULL, "list count is incorrect");

    // Find the replacement node for the (soon to be empty) node being removed.

    // if we have a single (or no) child, splice child in our stead

    if (replacementTL->left() == NULL) {

      // left is NULL so pick right.  right may also be NULL.

      newTL = replacementTL->right();

      debug_only(replacementTL->clearRight();)

    } else if (replacementTL->right() == NULL) {

      // right is NULL

      newTL = replacementTL->left();

      debug_only(replacementTL->clearLeft();)

    } else {  // we have both children, so, by patriarchal convention,

              // my replacement is least node in right sub-tree

      complicatedSplice = true;

      newTL = removeTreeMinimum(replacementTL->right());

      assert(newTL != NULL && newTL->left() == NULL &&

             newTL->right() == NULL, "sub-tree minimum exists");

    }

    // newTL is the replacement for the (soon to be empty) node.

    // newTL may be NULL.

    // should verify; we just cleanly excised our replacement

    if (FLSVerifyDictionary) {

      verifyTree();

    }

    // first make newTL my parent's child

    if ((parentTL = replacementTL->parent()) == NULL) {