tests/test_tsort.c

   1 #include <stdlib.h>
   2
   3 #include <glib.h>
   4
   5 #include <CUnit/CUnit.h>
   6
   7 #include "tsort.h"
   8
   9 #include "test_tsort.h"
  10
  11 #define A ((void *)1)
  12 #define B ((void *)2)
  13 #define C ((void *)3)
  14 #define D ((void *)4)
  15 #define E ((void *)5)
  16 #define F ((void *)6)
  17 #define G ((void *)7)
  18 #define H ((void *)8)
  19
  20 GList *get_test_list(void)
  21 {
  22   GList *list = NULL;
  23
  24   list = g_list_prepend(list, A);
  25   list = g_list_prepend(list, B);
  26   list = g_list_prepend(list, C);
  27   list = g_list_prepend(list, D);
  28   list = g_list_prepend(list, E);
  29   list = g_list_prepend(list, F);
  30   list = g_list_prepend(list, G);
  31   list = g_list_prepend(list, H);
  32
  33   return list;
  34 }
  35
  36 GList *get_test_edges(void)
  37 {
  38   GList *edges = NULL;
  39
  40   /* Edges:
  41    *
  42    *  E
  43    *  |
  44    *  B C D   H
  45    *   \|/    |
  46    *    A   F G
  47    */
  48   edges = g_list_append(edges, make_edge(A, B));
  49   edges = g_list_append(edges, make_edge(A, C));
  50   edges = g_list_append(edges, make_edge(A, D));
  51   edges = g_list_append(edges, make_edge(B, E));
  52   edges = g_list_append(edges, make_edge(G, H));
  53
  54   return edges;
  55 }
  56
  57 GList *get_faulty_test_edges(void)
  58 {
  59   GList *edges = NULL;
  60
  61   /* Edges:
  62    *
  63    *  F
  64    *  |
  65    *  E
  66    *  |
  67    *  B C D   H
  68    *   \|/    |
  69    *    A     G
  70    *    |
  71    *    F
  72    *
  73    */
  74
  75   edges = g_list_append(edges, make_edge(A, B));
  76   edges = g_list_append(edges, make_edge(A, C));
  77   edges = g_list_append(edges, make_edge(A, D));
  78   edges = g_list_append(edges, make_edge(B, E));
  79   edges = g_list_append(edges, make_edge(E, F));
  80   edges = g_list_append(edges, make_edge(F, A));
  81   edges = g_list_append(edges, make_edge(G, H));
  82
  83   return edges;
  84 }
  85
  86 void test_tsort_succeed(void)
  87 {
  88   GList *list = get_test_list();
  89   GList *edges = get_test_edges();
  90   GList *sorted_list = tsort(list, &edges);
  91
  92   CU_ASSERT_PTR_NULL(edges);
  93
  94   CU_ASSERT_PTR_NOT_NULL(sorted_list);
  95
  96   CU_ASSERT_EQUAL(g_list_length(list), g_list_length(sorted_list));
  97
  98   /* Check that all items from the original list are in the sorted list. */
  99   for (GList *item = list; item != NULL; item = g_list_next(item))
 100     CU_ASSERT_PTR_NOT_NULL(g_list_find(sorted_list, item->data));
 101
 102   /* Check that all items are in the order that is given by the edges. */
 103   edges = get_test_edges();
 104
 105   while (edges != NULL) {
 106     struct edge *e = edges->data;
 107     CU_ASSERT(g_list_index(sorted_list, e->predecessor) < g_list_index(sorted_list, e->successor));
 108     free(e);
 109     edges = g_list_delete_link(edges, edges);
 110   }
 111
 112   g_list_free(sorted_list);
 113   g_list_free(list);
 114 }
 115
 116 void test_tsort_fail(void)
 117 {
 118   GList *list = get_test_list();
 119   GList *edges = get_faulty_test_edges();
 120   GList *sorted_list = tsort(list, &edges);
 121
 122   CU_ASSERT_PTR_NULL(sorted_list);
 123
 124   CU_ASSERT(edges != NULL);
 125
 126   while (edges != NULL) {
 127     free(edges->data);
 128     edges = g_list_delete_link(edges, edges);
 129   }
 130
 131   g_list_free(list);
 132 }
 133
 134 CU_TestInfo tsort_tests[] = {
 135   { "test_tsort_succeed", test_tsort_succeed },
 136   { "test_tsort_fail", test_tsort_fail },
 137   CU_TEST_INFO_NULL,
 138 };