Root/
Source at commit eebb79ff6d635978e25ed4500b464d9f6ce360f5 created 13 years 5 months ago. By Xiangfu Liu, clean up the Build-Depends. | |
---|---|
1 | /* |
2 | * tsort.c - Topological sort |
3 | * |
4 | * Written 2010 by Werner Almesberger |
5 | * Copyright 2010 by Werner Almesberger |
6 | * |
7 | * This program is free software; you can redistribute it and/or modify |
8 | * it under the terms of the GNU General Public License as published by |
9 | * the Free Software Foundation; either version 2 of the License, or |
10 | * (at your option) any later version. |
11 | */ |
12 | |
13 | /* |
14 | * We use a slight variation of Kahn's algorithm. The difference is that we add |
15 | * a priority. Edges with the highest priority get selected before edges with |
16 | * lower priority. |
17 | * |
18 | * We maintain the initial list of nodes in the order in which they were added. |
19 | * Therefore, the first node with inbound edges will always be sorted first. |
20 | * E.g., the root frame. |
21 | * |
22 | * add_node and add_edge can be invoked multiple times with the same |
23 | * parameters. In the case of add_node, simply the existing node is returned. |
24 | * In the case of add_edge, the new edge's priority is added to the priority of |
25 | * the previous edges. |
26 | * |
27 | * Priority is accumulated in a node until the node is output. If a node has |
28 | * the "decay" flag set, it resets the priorities of all other nodes when |
29 | * output. E.g., when outputting a vector, all priorities accumulated from |
30 | * previous vectors (towards referencing them with ".") lose their effect. |
31 | * |
32 | * Last but not least, the algorithm is stable: a pre-existing order that |
33 | * conflicts neither with the partial order nor the priorities is preserved. |
34 | * |
35 | * Thus, we have the following sorting criteria, in decreasing importance: |
36 | * - the destination if an edge never precedes its origin |
37 | * - higher priority comes before lower priority |
38 | * - earlier add_node comes before later |
39 | */ |
40 | |
41 | |
42 | #include <stdlib.h> |
43 | #include <stdio.h> |
44 | #include <limits.h> |
45 | |
46 | #include "util.h" |
47 | #include "tsort.h" |
48 | |
49 | |
50 | struct edge { |
51 | struct node *to; |
52 | int priority; /* edge priority */ |
53 | struct edge *next; |
54 | }; |
55 | |
56 | struct node { |
57 | void *user; |
58 | struct edge *edges; /* outbound edges */ |
59 | int incoming; /* number of incoming edges */ |
60 | int priority; /* cumulative node priority */ |
61 | int decay; /* all node prio. decay after issuing this */ |
62 | struct node *next; |
63 | }; |
64 | |
65 | struct tsort { |
66 | struct node *nodes; |
67 | struct node **next_node; |
68 | int n_nodes; |
69 | }; |
70 | |
71 | |
72 | void add_edge(struct node *from, struct node *to, int priority) |
73 | { |
74 | struct edge **edge; |
75 | |
76 | for (edge = &from->edges; *edge; edge = &(*edge)->next) |
77 | if ((*edge)->to == to) { |
78 | (*edge)->priority += priority; |
79 | return; |
80 | } |
81 | *edge = alloc_type(struct edge); |
82 | (*edge)->to = to; |
83 | (*edge)->priority = priority; |
84 | (*edge)->next = NULL; |
85 | to->incoming++; |
86 | } |
87 | |
88 | |
89 | struct node *add_node(struct tsort *tsort, void *user, int decay) |
90 | { |
91 | struct node *node; |
92 | |
93 | for (node = tsort->nodes; node; node = node->next) |
94 | if (node->user == user) |
95 | return node; |
96 | node = alloc_type(struct node); |
97 | node->user = user; |
98 | node->edges = NULL; |
99 | node->incoming = 0; |
100 | node->priority = 0; |
101 | node->decay = decay; |
102 | node->next = NULL; |
103 | *tsort->next_node = node; |
104 | tsort->next_node = &node->next; |
105 | tsort->n_nodes++; |
106 | return node; |
107 | } |
108 | |
109 | |
110 | struct tsort *begin_tsort(void) |
111 | { |
112 | struct tsort *tsort; |
113 | |
114 | tsort = alloc_type(struct tsort); |
115 | tsort->nodes = NULL; |
116 | tsort->next_node = &tsort->nodes; |
117 | tsort->n_nodes = 0; |
118 | return tsort; |
119 | } |
120 | |
121 | |
122 | void **end_tsort(struct tsort *tsort) |
123 | { |
124 | struct node **walk, **first, *node; |
125 | struct edge *edge; |
126 | void **res; |
127 | int n = 0; |
128 | |
129 | res = alloc_size(sizeof(void *)*(tsort->n_nodes+1)); |
130 | while (1) { |
131 | first = NULL; |
132 | for (walk = &tsort->nodes; *walk; walk = &(*walk)->next) { |
133 | if ((*walk)->incoming) |
134 | continue; |
135 | if (!first || (*first)->priority < (*walk)->priority) |
136 | first = walk; |
137 | } |
138 | if (!first) |
139 | break; |
140 | if ((*first)->decay) |
141 | for (node = tsort->nodes; node; node = node->next) |
142 | node->priority = 0; |
143 | node = *first; |
144 | *first = node->next; |
145 | res[n++] = node->user; |
146 | while (node->edges) { |
147 | edge = node->edges; |
148 | edge->to->incoming--; |
149 | edge->to->priority += edge->priority; |
150 | node->edges = edge->next; |
151 | free(edge); |
152 | } |
153 | free(node); |
154 | } |
155 | if (tsort->nodes) { |
156 | fprintf(stderr, "cycle detected in partial order\n"); |
157 | abort(); |
158 | } |
159 | free(tsort); |
160 | res[n] = NULL; |
161 | return res; |
162 | } |
163 |
Branches:
master