gcc/fibonacci_heap.cc

/* Fibonacci heap for GNU compiler.
   Copyright (C) 2016-2022 Free Software Foundation, Inc.
   Contributed by Martin Liska <mliska@suse.cz>

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC 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
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "alloc-pool.h"
#include "fibonacci_heap.h"
#include "selftest.h"

#if CHECKING_P

namespace selftest {

/* Selftests.  */

/* Verify that operations with empty heap work.  */

typedef fibonacci_node <int, int> int_heap_node_t;
typedef fibonacci_heap <int, int> int_heap_t;

static void
test_empty_heap ()
{
  pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));
  int_heap_t *h1 = new int_heap_t (INT_MIN, &allocator);

  ASSERT_TRUE (h1->empty ());
  ASSERT_EQ (0, h1->nodes ());
  ASSERT_EQ (NULL, h1->min ());

  int_heap_t *h2 = new int_heap_t (INT_MIN, &allocator);

  int_heap_t *r = h1->union_with (h2);
  ASSERT_TRUE (r->empty ());
  ASSERT_EQ (0, r->nodes ());
  ASSERT_EQ (NULL, r->min ());

  delete r;
}

#define TEST_HEAP_N 100
#define TEST_CALCULATE_VALUE(i)  ((3 * i) + 10000)

/* Verify heap basic operations.  */

static void
test_basic_heap_operations ()
{
  int values[TEST_HEAP_N];
  int_heap_t *h1 = new int_heap_t (INT_MIN);

  for (unsigned i = 0; i < TEST_HEAP_N; i++)
    {
      values[i] = TEST_CALCULATE_VALUE (i);
      ASSERT_EQ (i, h1->nodes ());
      h1->insert (i, &values[i]);
      ASSERT_EQ (0, h1->min_key ());
      ASSERT_EQ (values[0], *h1->min ());
    }

  for (unsigned i = 0; i < TEST_HEAP_N; i++)
    {
      ASSERT_EQ (TEST_HEAP_N - i, h1->nodes ());
      ASSERT_EQ ((int)i, h1->min_key ());
      ASSERT_EQ (values[i], *h1->min ());

      h1->extract_min ();
    }

  ASSERT_TRUE (h1->empty ());

  delete h1;
}

/* Builds a simple heap with values in interval 0..TEST_HEAP_N-1, where values
   of each key is equal to 3 * key + 10000.  BUFFER is used as a storage
   of values and NODES points to inserted nodes.  */

static int_heap_t *
build_simple_heap (int *buffer, int_heap_node_t **nodes)
{
  int_heap_t *h = new int_heap_t (INT_MIN);

  for (unsigned i = 0; i < TEST_HEAP_N; i++)
    {
      buffer[i] = TEST_CALCULATE_VALUE (i);
      nodes[i] = h->insert (i, &buffer[i]);
    }

  return h;
}

/* Verify that fibonacci_heap::replace_key works.  */

static void
test_replace_key ()
{
  int values[TEST_HEAP_N];
  int_heap_node_t *nodes[TEST_HEAP_N];

  int_heap_t *heap = build_simple_heap (values, nodes);

  int N = 10;
  for (unsigned i = 0; i < (unsigned)N; i++)
    heap->replace_key (nodes[i], 100 * 1000 + i);

  ASSERT_EQ (TEST_HEAP_N, heap->nodes ());
  ASSERT_EQ (N, heap->min_key ());
  ASSERT_EQ (TEST_CALCULATE_VALUE (N), *heap->min ());

  for (int i = 0; i < TEST_HEAP_N - 1; i++)
    heap->extract_min ();

  ASSERT_EQ (1, heap->nodes ());
  ASSERT_EQ (100 * 1000 + N - 1, heap->min_key ());

  delete heap;
}

/* Verify that heap can handle duplicate keys.  */

static void
test_duplicate_keys ()
{
  int values[3 * TEST_HEAP_N];
  int_heap_t *heap = new int_heap_t (INT_MIN);

  for (unsigned i = 0; i < 3 * TEST_HEAP_N; i++)
    {
      values[i] = TEST_CALCULATE_VALUE (i);
      heap->insert (i / 3, &values[i]);
    }

  ASSERT_EQ (3 * TEST_HEAP_N, heap->nodes ());
  ASSERT_EQ (0, heap->min_key ());
  ASSERT_EQ (TEST_CALCULATE_VALUE (0), *heap->min ());

  for (unsigned i = 0; i < 9; i++)
    heap->extract_min ();

  for (unsigned i = 0; i < 3; i++)
    {
      ASSERT_EQ (3, heap->min_key ());
      heap->extract_min ();
    }

  delete heap;
}

/* Verify that heap can handle union.  */

static void
test_union ()
{
  int value = 777;
  pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));

  int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
  for (unsigned i = 0; i < 2 * TEST_HEAP_N; i++)
    heap1->insert (i, &value);

  int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
  for (unsigned i = 2 * TEST_HEAP_N; i < 3 * TEST_HEAP_N; i++)
    heap2->insert (i, &value);

  int_heap_t *union_heap = heap1->union_with (heap2);

  for (int i = 0; i < 3 * TEST_HEAP_N; i++)
    {
      ASSERT_EQ (i, union_heap->min_key ());
      union_heap->extract_min ();
    }

  delete union_heap;
}

/* Verify that heap can handle union with a heap having exactly the same
   keys.  */

static void
test_union_of_equal_heaps ()
{
  int value = 777;
  pool_allocator allocator ("fibheap test", sizeof (int_heap_node_t));

  int_heap_t *heap1 = new int_heap_t (INT_MIN, &allocator);
  for (unsigned i = 0; i < TEST_HEAP_N; i++)
    heap1->insert (i, &value);

  int_heap_t *heap2 = new int_heap_t (INT_MIN, &allocator);
  for (unsigned i = 0; i < TEST_HEAP_N; i++)
    heap2->insert (i, &value);

  int_heap_t *union_heap = heap1->union_with (heap2);

  for (int i = 0; i < TEST_HEAP_N; i++)
    for (int j = 0; j < 2; j++)
    {
      ASSERT_EQ (i, union_heap->min_key ());
      union_heap->extract_min ();
    }

  delete union_heap;
}

/* Dummy struct for testing.  */

class heap_key
{
public:
  heap_key (int k): key (k)
  {
  }

  int key;

  bool operator< (const heap_key &other) const
  {
    return key > other.key;
  }

  bool operator== (const heap_key &other) const
  {
    return key == other.key;
  }

  bool operator> (const heap_key &other) const
  {
    return !(*this == other || *this < other);
  }
};

typedef fibonacci_heap<heap_key, int> class_fibonacci_heap_t;

/* Verify that heap can handle a struct as key type.  */

static void
test_struct_key ()
{
  int value = 123456;
  class_fibonacci_heap_t *heap = new class_fibonacci_heap_t (INT_MIN);

  heap->insert (heap_key (1), &value);
  heap->insert (heap_key (10), &value);
  heap->insert (heap_key (100), &value);
  heap->insert (heap_key (1000), &value);

  ASSERT_EQ (1000, heap->min_key ().key);
  ASSERT_EQ (4, heap->nodes ());
  heap->extract_min ();
  heap->extract_min ();
  ASSERT_EQ (10, heap->min_key ().key);
  heap->extract_min ();
  ASSERT_EQ (&value, heap->min ());
  heap->extract_min ();
  ASSERT_TRUE (heap->empty ());

  delete heap;
}

/* Run all of the selftests within this file.  */

void
fibonacci_heap_cc_tests ()
{
  test_empty_heap ();
  test_basic_heap_operations ();
  test_replace_key ();
  test_duplicate_keys ();
  test_union ();
  test_union_of_equal_heaps ();
  test_struct_key ();
}

} // namespace selftest

#endif /* #if CHECKING_P */