src/tsort.h

   1 /* tsort.h -- header file for topological sort for vlock,
   2  *            the VT locking program for linux
   3  *
   4  * This program is copyright (C) 2007 Frank Benkstein, and is free
   5  * software which is freely distributable under the terms of the
   6  * GNU General Public License version 2, included as the file COPYING in this
   7  * distribution.  It is NOT public domain software, and any
   8  * redistribution not permitted by the GNU General Public License is
   9  * expressly forbidden without prior written permission from
  10  * the author.
  11  *
  12  */
  13
  14 #include <stdbool.h>
  15 #include <glib.h>
  16
  17 /* An edge of the graph, specifying that predecessor must come before
  18  * successor. */
  19 struct edge
  20 {
  21   void *predecessor;
  22   void *successor;
  23 };
  24
  25 static inline struct edge *make_edge(void *p, void *s)
  26 {
  27   struct edge *e = g_malloc(sizeof *e);
  28
  29   e->predecessor = p;
  30   e->successor = s;
  31
  32   return e;
  33 }
  34
  35 /* For the given directed graph, generate a topological sort of the nodes.
  36  *
  37  * Sorts the list and deletes all edges.  If there are circles found in the
  38  * graph or there are edges that have no corresponding nodes NULL is returned
  39  * and the erroneous edges are left. */
  40 /* XXX: sort the list in place and return a boolean for success */
  41 GList *tsort(GList *nodes, GList **edges);