tsort.c 4.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163
  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. * We use a slight variation of Kahn's algorithm. The difference is that we add
  14. * a priority. Edges with the highest priority get selected before edges with
  15. * lower priority.
  16. *
  17. * We maintain the initial list of nodes in the order in which they were added.
  18. * Therefore, the first node with inbound edges will always be sorted first.
  19. * E.g., the root frame.
  20. *
  21. * add_node and add_edge can be invoked multiple times with the same
  22. * parameters. In the case of add_node, simply the existing node is returned.
  23. * In the case of add_edge, the new edge's priority is added to the priority of
  24. * the previous edges.
  25. *
  26. * Priority is accumulated in a node until the node is output. If a node has
  27. * the "decay" flag set, it resets the priorities of all other nodes when
  28. * output. E.g., when outputting a vector, all priorities accumulated from
  29. * previous vectors (towards referencing them with ".") lose their effect.
  30. *
  31. * Last but not least, the algorithm is stable: a pre-existing order that
  32. * conflicts neither with the partial order nor the priorities is preserved.
  33. *
  34. * Thus, we have the following sorting criteria, in decreasing importance:
  35. * - the destination if an edge never precedes its origin
  36. * - higher priority comes before lower priority
  37. * - earlier add_node comes before later
  38. */
  39. #include <stdlib.h>
  40. #include <stdio.h>
  41. #include <limits.h>
  42. #include "util.h"
  43. #include "tsort.h"
  44. struct edge {
  45. struct node *to;
  46. int priority; /* edge priority */
  47. struct edge *next;
  48. };
  49. struct node {
  50. void *user;
  51. struct edge *edges; /* outbound edges */
  52. int incoming; /* number of incoming edges */
  53. int priority; /* cumulative node priority */
  54. int decay; /* all node prio. decay after issuing this */
  55. struct node *next;
  56. };
  57. struct tsort {
  58. struct node *nodes;
  59. struct node **next_node;
  60. int n_nodes;
  61. };
  62. void add_edge(struct node *from, struct node *to, int priority)
  63. {
  64. struct edge **edge;
  65. for (edge = &from->edges; *edge; edge = &(*edge)->next)
  66. if ((*edge)->to == to) {
  67. (*edge)->priority += priority;
  68. return;
  69. }
  70. *edge = alloc_type(struct edge);
  71. (*edge)->to = to;
  72. (*edge)->priority = priority;
  73. (*edge)->next = NULL;
  74. to->incoming++;
  75. }
  76. struct node *add_node(struct tsort *tsort, void *user, int decay)
  77. {
  78. struct node *node;
  79. for (node = tsort->nodes; node; node = node->next)
  80. if (node->user == user)
  81. return node;
  82. node = alloc_type(struct node);
  83. node->user = user;
  84. node->edges = NULL;
  85. node->incoming = 0;
  86. node->priority = 0;
  87. node->decay = decay;
  88. node->next = NULL;
  89. *tsort->next_node = node;
  90. tsort->next_node = &node->next;
  91. tsort->n_nodes++;
  92. return node;
  93. }
  94. struct tsort *begin_tsort(void)
  95. {
  96. struct tsort *tsort;
  97. tsort = alloc_type(struct tsort);
  98. tsort->nodes = NULL;
  99. tsort->next_node = &tsort->nodes;
  100. tsort->n_nodes = 0;
  101. return tsort;
  102. }
  103. void **end_tsort(struct tsort *tsort)
  104. {
  105. struct node **walk, **first, *node;
  106. struct edge *edge;
  107. void **res;
  108. int n = 0;
  109. res = alloc_size(sizeof(void *)*(tsort->n_nodes+1));
  110. while (1) {
  111. first = NULL;
  112. for (walk = &tsort->nodes; *walk; walk = &(*walk)->next) {
  113. if ((*walk)->incoming)
  114. continue;
  115. if (!first || (*first)->priority < (*walk)->priority)
  116. first = walk;
  117. }
  118. if (!first)
  119. break;
  120. if ((*first)->decay)
  121. for (node = tsort->nodes; node; node = node->next)
  122. node->priority = 0;
  123. node = *first;
  124. *first = node->next;
  125. res[n++] = node->user;
  126. while (node->edges) {
  127. edge = node->edges;
  128. edge->to->incoming--;
  129. edge->to->priority += edge->priority;
  130. node->edges = edge->next;
  131. free(edge);
  132. }
  133. free(node);
  134. }
  135. if (tsort->nodes) {
  136. fprintf(stderr, "cycle detected in partial order\n");
  137. abort();
  138. }
  139. free(tsort);
  140. res[n] = NULL;
  141. return res;
  142. }