← Back to branch summary

~ubuntu-branches/ubuntu/natty/vlock/natty

« back to all changes in this revision

Viewing changes to src/tsort.c

  • Committer: Bazaar Package Importer
  • Author(s): Alexander Wirt
  • Date: 2008-06-17 17:13:25 UTC
  • mfrom: (1.1.2 upstream) (3.1.1 lenny)
  • Revision ID: james.westby@ubuntu.com-20080617171325-ic8yy6tol0165i96
Tags: 2.2.2-3
* Don't try to chgrp to "vlock" during build time (Closes: #486665)
* Bump standards version (No changes)

Show diffs side-by-side

added added

removed removed

Lines of Context:
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
}