/*

 * Copyright (c) 2014, 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.

 *

 */

#ifndef SHARE_VM_UTILITIES_LINKED_LIST_HPP

#define SHARE_VM_UTILITIES_LINKED_LIST_HPP

#include "memory/allocation.hpp"

/*

 * The implementation of a generic linked list, which uses various

 * backing storages, such as C heap, arena and resource, etc.

 */

// An entry in a linked list. It should use the same backing storage

// as the linked list that contains this entry.

template <class E> class LinkedListNode : public ResourceObj {

 private:

  E                       _data;  // embedded content

  LinkedListNode<E>*      _next;  // next entry

 protected:

  LinkedListNode() : _next(NULL) { }

 public:

  LinkedListNode(const E& e): _data(e), _next(NULL) { }

  inline void set_next(LinkedListNode<E>* node) { _next = node; }

  inline LinkedListNode<E> * next() const       { return _next; }

  E*  data() { return &_data; }

  const E* peek() const { return &_data; }

};

// A linked list interface. It does not specify

// any storage type it uses, so all methods involving

// memory allocation or deallocation are pure virtual

template <class E> class LinkedList : public ResourceObj {

 protected:

  LinkedListNode<E>*    _head;

 public:

  LinkedList() : _head(NULL) { }

  inline void set_head(LinkedListNode<E>* h) { _head = h; }

  inline LinkedListNode<E>* head() const     { return _head; }

  inline bool is_empty()           const     { return head() == NULL; }

  inline size_t size() const {

    LinkedListNode<E>* p;

    size_t count = 0;

    for (p = head(); p != NULL; count++, p = p->next());

    return count;

 }

  // Move all entries from specified linked list to this one

  virtual void move(LinkedList<E>* list) = 0;

  // Add an entry to this linked list

  virtual LinkedListNode<E>* add(const E& e) = 0;

  // Add all entries from specified linked list to this one,

  virtual void add(LinkedListNode<E>* node) = 0;

  // Add a linked list to this linked list

  virtual bool  add(const LinkedList<E>* list) = 0;

  // Search entry in the linked list

  virtual LinkedListNode<E>* find_node(const E& e) = 0;

  virtual E* find(const E& e) = 0;

  // Insert entry to the linked list

  virtual LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref) = 0;

  virtual LinkedListNode<E>* insert_after (const E& e, LinkedListNode<E>* ref) = 0;

  // Remove entry from the linked list

  virtual bool               remove(const E& e) = 0;

  virtual bool               remove(LinkedListNode<E>* node) = 0;

  virtual bool               remove_before(LinkedListNode<E>* ref) = 0;

  virtual bool               remove_after(LinkedListNode<E>*  ref) = 0;

  LinkedListNode<E>* unlink_head() {

    LinkedListNode<E>* h = this->head();

    if (h != NULL) {

      this->set_head(h->next());

    }

    return h;

  }

  DEBUG_ONLY(virtual ResourceObj::allocation_type storage_type() = 0;)

};

// A linked list implementation.

// The linked list can be allocated in various type of memory: C heap, arena and resource area, etc.

template <class E, ResourceObj::allocation_type T = ResourceObj::C_HEAP,

  MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL>

  class LinkedListImpl : public LinkedList<E> {

 protected:

  Arena*                 _arena;

 public:

  LinkedListImpl() :  _arena(NULL) { }

  LinkedListImpl(Arena* a) : _arena(a) { }

  virtual ~LinkedListImpl() {

    clear();

  }

  virtual void clear() {

    LinkedListNode<E>* p = this->head();

    this->set_head(NULL);

    while (p != NULL) {

      LinkedListNode<E>* to_delete = p;

      p = p->next();

      delete_node(to_delete);

    }

  }

  // Add an entry to the linked list

  virtual LinkedListNode<E>* add(const E& e)  {

    LinkedListNode<E>* node = this->new_node(e);

    if (node != NULL) {

      this->add(node);

    }

    return node;

  }

  virtual void add(LinkedListNode<E>* node) {

    assert(node != NULL, "NULL pointer");

    node->set_next(this->head());

    this->set_head(node);

  }

  // Move a linked list to this linked list, both have to be allocated on the same

  // storage type.

  virtual void move(LinkedList<E>* list) {

    assert(list->storage_type() == this->storage_type(), "Different storage type");

    LinkedListNode<E>* node = this->head();

    while (node != NULL && node->next() != NULL) {

      node = node->next();

    }

    if (node == NULL) {

      this->set_head(list->head());

    } else {

      node->set_next(list->head());

    }

    // All entries are moved

    list->set_head(NULL);

  }

  virtual bool add(const LinkedList<E>* list) {

    LinkedListNode<E>* node = list->head();

    while (node != NULL) {

      if (this->add(*node->peek()) == NULL) {

        return false;

      }

      node = node->next();

    }

    return true;

  }

  virtual LinkedListNode<E>* find_node(const E& e) {

    LinkedListNode<E>* p = this->head();

    while (p != NULL && !p->peek()->equals(e)) {

      p = p->next();

    }

    return p;

  }

  E* find(const E& e) {

    LinkedListNode<E>* node = find_node(e);

    return (node == NULL) ? NULL : node->data();

  }

  // Add an entry in front of the reference entry

  LinkedListNode<E>* insert_before(const E& e, LinkedListNode<E>* ref_node) {

    LinkedListNode<E>* node = this->new_node(e);

    if (node == NULL) return NULL;

    if (ref_node == this->head()) {

      node->set_next(ref_node);

      this->set_head(node);

    } else {

      LinkedListNode<E>* p = this->head();

      while (p != NULL && p->next() != ref_node) {

        p = p->next();

      }

      assert(p != NULL, "ref_node not in the list");

      node->set_next(ref_node);

      p->set_next(node);

    }

    return node;

  }

   // Add an entry behind the reference entry

   LinkedListNode<E>* insert_after(const E& e, LinkedListNode<E>* ref_node) {

     LinkedListNode<E>* node = this->new_node(e);

     if (node == NULL) return NULL;

     node->set_next(ref_node->next());

     ref_node->set_next(node);

     return node;

   }

   // Remove an entry from the linked list.

   // Return true if the entry is successfully removed

   virtual bool remove(const E& e) {

     LinkedListNode<E>* tmp = this->head();

     LinkedListNode<E>* prev = NULL;

     while (tmp != NULL) {

       if (tmp->peek()->equals(e)) {

         return remove_after(prev);

       }

       prev = tmp;

       tmp = tmp->next();

     }

     return false;

  }

  // Remove the node after the reference entry

  virtual bool remove_after(LinkedListNode<E>* prev) {

    LinkedListNode<E>* to_delete;

    if (prev == NULL) {

      to_delete = this->unlink_head();

    } else {

      to_delete = prev->next();

      if (to_delete != NULL) {

        prev->set_next(to_delete->next());

      }

    }

    if (to_delete != NULL) {

      delete_node(to_delete);

      return true;

    }

    return false;

  }

  virtual bool remove(LinkedListNode<E>* node) {

    LinkedListNode<E>* p = this->head();

    if (p == node) {

      this->set_head(p->next());

      delete_node(node);

      return true;

    }

    while (p != NULL && p->next() != node) {

      p = p->next();

    }

    if (p != NULL) {

      p->set_next(node->next());

      delete_node(node);

      return true;

    } else {

      return false;

    }

  }

  virtual bool remove_before(LinkedListNode<E>* ref) {

    assert(ref != NULL, "NULL pointer");

    LinkedListNode<E>* p = this->head();

    LinkedListNode<E>* to_delete = NULL; // to be deleted

    LinkedListNode<E>* prev = NULL;      // node before the node to be deleted

    while (p != NULL && p != ref) {

      prev = to_delete;

      to_delete = p;

      p = p->next();

    }

    if (p == NULL || to_delete == NULL) return false;

    assert(to_delete->next() == ref, "Wrong node to delete");

    assert(prev == NULL || prev->next() == to_delete,

      "Sanity check");

    if (prev == NULL) {

      assert(to_delete == this->head(), "Must be head");

      this->set_head(to_delete->next());

    } else {

      prev->set_next(to_delete->next());

    }

    delete_node(to_delete);

    return true;

  }

  DEBUG_ONLY(ResourceObj::allocation_type storage_type() { return T; })

 protected:

  // Create new linked list node object in specified storage

  LinkedListNode<E>* new_node(const E& e) const {

     switch(T) {

       case ResourceObj::ARENA: {

         assert(_arena != NULL, "Arena not set");

         return new(_arena) LinkedListNode<E>(e);

       }

       case ResourceObj::RESOURCE_AREA:

       case ResourceObj::C_HEAP: {

         if (alloc_failmode == AllocFailStrategy::RETURN_NULL) {

           return new(std::nothrow, T, F) LinkedListNode<E>(e);

         } else {

           return new(T, F) LinkedListNode<E>(e);

         }

       }

       default:

         ShouldNotReachHere();

     }

     return NULL;

  }

  // Delete linked list node object

  void delete_node(LinkedListNode<E>* node) {

    if (T == ResourceObj::C_HEAP) {

      delete node;

    }

  }

};

// Sorted linked list. The linked list maintains sorting order specified by the comparison

// function

template <class E, int (*FUNC)(const E&, const E&),

  ResourceObj::allocation_type T = ResourceObj::C_HEAP,

  MEMFLAGS F = mtNMT, AllocFailType alloc_failmode = AllocFailStrategy::RETURN_NULL>

  class SortedLinkedList : public LinkedListImpl<E, T, F, alloc_failmode> {

 public:

  SortedLinkedList() { }

  SortedLinkedList(Arena* a) : LinkedListImpl<E, T, F, alloc_failmode>(a) { }

  virtual LinkedListNode<E>* add(const E& e) {

    return LinkedListImpl<E, T, F, alloc_failmode>::add(e);

  }

  virtual void move(LinkedList<E>* list) {

    assert(list->storage_type() == this->storage_type(), "Different storage type");

    LinkedListNode<E>* node;

    while ((node = list->unlink_head()) != NULL) {

      this->add(node);

    }

    assert(list->is_empty(), "All entries are moved");

  }

  virtual void add(LinkedListNode<E>* node) {

    assert(node != NULL, "NULL pointer");

    LinkedListNode<E>* tmp = this->head();

    LinkedListNode<E>* prev = NULL;

    int cmp_val;

    while (tmp != NULL) {

      cmp_val = FUNC(*tmp->peek(), *node->peek());

      if (cmp_val >= 0) {

        break;

      }

      prev = tmp;

      tmp = tmp->next();

    }

    if (prev != NULL) {

      node->set_next(prev->next());

      prev->set_next(node);

    } else {

      node->set_next(this->head());

      this->set_head(node);

    }

  }

  virtual bool add(const LinkedList<E>* list) {

    return LinkedListImpl<E, T, F, alloc_failmode>::add(list);

  }

  virtual LinkedListNode<E>* find_node(const E& e) {

    LinkedListNode<E>* p = this->head();

    while (p != NULL) {

      int comp_val = FUNC(*p->peek(), e);

      if (comp_val == 0) {

        return p;

      } else if (comp_val > 0) {

        return NULL;

      }

      p = p->next();

    }

    return NULL;

  }

};

// Iterates all entries in the list

template <class E> class LinkedListIterator : public StackObj {

 private:

  LinkedListNode<E>* _p;

  bool               _is_empty;

 public:

  LinkedListIterator(LinkedListNode<E>* head) : _p(head) {

    _is_empty = (head == NULL);

  }

  bool is_empty() const { return _is_empty; }

  const E* next() {

    if (_p == NULL) return NULL;

    const E* e = _p->peek();

    _p = _p->next();

    return e;

  }

};

#endif