| 249 | /////////////////////////////////////////// |
| 250 | |
| 251 | int32_t topological_sort(sort_dependency_t *dependencies, int32_t count, int32_t *ref_order) { |
| 252 | // Topological sort, Depth-first algorithm: |
| 253 | // https://en.wikipedia.org/wiki/Topological_sorting |
| 254 | |
| 255 | uint8_t *marks = sk_malloc_t(uint8_t, count); |
| 256 | int32_t sorted_curr = count-1; |
| 257 | memset(marks, 0, sizeof(uint8_t) * count); |
| 258 | |
| 259 | while (sorted_curr > 0) { |
| 260 | for (int32_t i = 0; i < count; i++) { |
| 261 | if (marks[i] != 0) |
| 262 | continue; |
| 263 | int result = topological_sort_visit(dependencies, count, i, marks, &sorted_curr, ref_order); |
| 264 | // If we found a cyclic dependency, ditch out! |
| 265 | if (result != 0) { |
| 266 | sk_free(marks); |
| 267 | return result; |
| 268 | } |
| 269 | } |
| 270 | } |
| 271 | |
| 272 | sk_free(marks); |
| 273 | return 0; |
| 274 | } |
| 275 | |
| 276 | /////////////////////////////////////////// |
| 277 |
no test coverage detected