src/tsort.c

   1 /* tsort.c -- topological sort for vlock, the VT locking program for linux
   2  *
   3  * This program is copyright (C) 2007 Frank Benkstein, and is free
   4  * software which is freely distributable under the terms of the
   5  * GNU General Public License version 2, included as the file COPYING in this
   6  * distribution.  It is NOT public domain software, and any
   7  * redistribution not permitted by the GNU General Public License is
   8  * expressly forbidden without prior written permission from
   9  * the author.
  10  *
  11  */
  12
  13 #include <stdlib.h>
  14 #include <errno.h>
  15
  16 #include "list.h"
  17 #include "util.h"
  18
  19 #include "tsort.h"
  20
  21 /* Get the zeros of the graph, i.e. nodes with no incoming edges. */
  22 static struct list *get_zeros(struct list *nodes, struct list *edges)
  23 {
  24   struct list *zeros = list_copy(nodes);
  25
  26   if (zeros == NULL)
  27     return NULL;
  28
  29   list_for_each(edges, edge_item) {
  30     struct edge *e = edge_item->data;
  31     list_delete(zeros, e->successor);
  32   }
  33
  34   return zeros;
  35 }
  36
  37 /* Check if the given node is a zero. */
  38 static bool is_zero(void *node, struct list *edges)
  39 {
  40   list_for_each(edges, edge_item) {
  41     struct edge *e = edge_item->data;
  42
  43     if (e->successor == node)
  44       return false;
  45   }
  46
  47   return true;
  48 }
  49
  50 /* For the given directed graph, generate a topological sort of the nodes.
  51  *
  52  * Sorts the list and deletes all edges.  If there are circles found in the
  53  * graph or there are edges that have no corresponding nodes the erroneous
  54  * edges are left.
  55  *
  56  * The algorithm is taken from the Wikipedia:
  57  *
  58  * http://en.wikipedia.org/w/index.php?title=Topological_sorting&oldid=153157450#Algorithms
  59  *
  60  */
  61 struct list *tsort(struct list *nodes, struct list *edges)
  62 {
  63   struct list *sorted_nodes = list_new();
  64   /* Retrieve all zeros. */
  65   struct list *zeros;
  66
  67   if (sorted_nodes == NULL)
  68     return NULL;
  69
  70   zeros = get_zeros(nodes, edges);
  71
  72   if (zeros == NULL) {
  73     GUARD_ERRNO(list_free(sorted_nodes));
  74     return NULL;
  75   }
  76
  77   /* While the list of zeros is not empty, take the first zero and remove it
  78    * and ...  */
  79   list_delete_for_each(zeros, zero_item) {
  80     void *zero = zero_item->data;
  81     /* ... add it to the list of sorted nodes. */
  82     if (!list_append(sorted_nodes, zero))
  83       goto error;
  84
  85     /* Then look at each edge ... */
  86     list_for_each_manual(edges, edge_item) {
  87       struct edge *e = edge_item->data;
  88
  89       /* ... that has this zero as its predecessor ... */
  90       if (e->predecessor == zero) {
  91         /* ... and remove it. */
  92         edge_item = list_delete_item(edges, edge_item);
  93
  94         /* If the successor has become a zero now ... */
  95         if (is_zero(e->successor, edges))
  96           /* ... add it to the list of zeros. */
  97           if (!list_append(zeros, e->successor))
  98             goto error;
  99
 100         free(e);
 101       } else {
 102         edge_item = edge_item->next;
 103       }
 104     }
 105   }
 106
 107   /* If all edges were deleted the algorithm was successful. */
 108   if (!list_is_empty(edges)) {
 109     list_free(sorted_nodes);
 110     sorted_nodes = NULL;
 111   }
 112
 113   list_free(zeros);
 114   errno = 0;
 115
 116   return sorted_nodes;;
 117
 118 error:
 119   {
 120     int errsv = errno;
 121     list_free(sorted_nodes);
 122     list_free(zeros);
 123
 124     errno = errsv;
 125     return NULL;
 126   }
 127 }