1 /*
   2  * Copyright (c) 2011, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22 
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "unittest.hpp"
  27 #include "utilities/linkedlist.hpp"
  28 
  29 class Integer : public StackObj {
  30  private:
  31   int _value;
  32  public:
  33 
  34   Integer(int i) : _value(i) {
  35   }
  36 
  37   int value() const {
  38     return _value;
  39   }
  40 
  41   bool equals(const Integer& i) const {
  42     return _value == i.value();
  43   }
  44 
  45   static int compare(const Integer& i1, const Integer& i2) {
  46     return i1.value() - i2.value();
  47   }
  48 };
  49 
  50 static void check_list_values(const int* expected, const LinkedList<Integer>* list) {
  51   LinkedListNode<Integer>* head = list->head();
  52   int index = 0;
  53   while (head != NULL) {
  54     ASSERT_EQ(head->peek()->value(), expected[index])
  55             << "Unexpected value at index " << index;
  56     head = head->next();
  57     index++;
  58   }
  59 }
  60 
  61 const Integer one(1), two(2), three(3), four(4), five(5), six(6);
  62 
  63 // Test regular linked list
  64 TEST(LinkedList, simple) {
  65   LinkedListImpl<Integer, ResourceObj::C_HEAP, mtTest> ll;
  66 
  67   ASSERT_TRUE(ll.is_empty()) << "Start with empty list";
  68 
  69   ll.add(six);
  70   ASSERT_TRUE(!ll.is_empty()) << "Should not be empty";
  71 
  72   Integer* i = ll.find(six);
  73   ASSERT_NE(i, (Integer*) NULL) << "Should find it";
  74   ASSERT_EQ(i->value(), six.value()) << "Should be 6";
  75 
  76   i = ll.find(three);
  77   ASSERT_EQ(i, (Integer*) NULL) << "Not in the list";
  78 
  79   LinkedListNode<Integer>* node = ll.find_node(six);
  80   ASSERT_NE(node, (LinkedListNode<Integer>*) NULL) << "6 is in the list";
  81 
  82   ll.insert_after(three, node);
  83   ll.insert_before(one, node);
  84   int expected[3] = {1, 6, 3};
  85   check_list_values(expected, &ll);
  86 }
  87 
  88 // Test sorted linked list
  89 TEST(SortedLinkedList, simple) {
  90   LinkedListImpl<Integer, ResourceObj::C_HEAP, mtTest> ll;
  91   ll.add(one);
  92   ll.add(six);
  93   ll.add(three);
  94   ll.add(two);
  95   ll.add(four);
  96   ll.add(five);
  97 
  98   SortedLinkedList<Integer, Integer::compare, ResourceObj::C_HEAP, mtTest> sl;
  99   ASSERT_TRUE(sl.is_empty()) << "Start with empty list";
 100 
 101   size_t ll_size = ll.size();
 102   sl.move(&ll);
 103   size_t sl_size = sl.size();
 104 
 105   ASSERT_EQ(ll_size, sl_size) << "Should be the same size";
 106   ASSERT_TRUE(ll.is_empty()) << "No more entries";
 107 
 108   // sorted result
 109   int sorted_result[] = {1, 2, 3, 4, 5, 6};
 110   check_list_values(sorted_result, &sl);
 111   if (HasFatalFailure()) {
 112     return;
 113   }
 114 
 115   LinkedListNode<Integer>* node = sl.find_node(four);
 116   ASSERT_NE(node, (LinkedListNode<Integer>*) NULL) << "4 is in the list";
 117   sl.remove_before(node);
 118   sl.remove_after(node);
 119   int remains[] = {1, 2, 4, 6};
 120   check_list_values(remains, &sl);
 121 }