libpitust 0.1.0

libpitust implements random utility functions I tend to use a lot
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

//! Module `dag_sched` computes a DAG schedule based on a terrible heuristicy
//! algorithm.

use crate::graph::{node_map::NodeMap, postorder::postorder_all, GraphPred, GraphSucc};

struct NodeInfo {
    last_use_count: u32,
    priority: u32,
    num_incomplete_deps: u32,
    outstanding_users: u32,
    max_height: u32,
    peer_max_height: u32,
    issued: bool,
}

pub fn dag_schedule<G: GraphPred + GraphSucc>(graph: G) -> Vec<G::Node> {
    let mut nodes = NodeMap::new_with(graph, |_| NodeInfo {
        last_use_count: 0,
        priority: 0,
        num_incomplete_deps: 0,
        outstanding_users: 0,
        max_height: u32::MAX,
        peer_max_height: u32::MAX,
        issued: false,
    });
    for id in graph.nodes() {
        for depid in graph.pred_of(id) {
            nodes[depid].outstanding_users += 1;
            nodes[id].num_incomplete_deps += 1;
        }
    }

    let order = postorder_all(graph);
    for &id in &order {
        let mut prio = 0;
        let mut extra = 0;
        for succ in graph.succ_of(id) {
            let pprio = nodes[succ].priority;
            if prio == pprio {
                extra += 1;
            } else if prio < pprio {
                extra = 0;
                prio = pprio;
            }
        }
        nodes[id].priority = prio + extra + 1;
    }

    let mut ready = vec![];
    for id in graph.nodes() {
        if nodes[id].num_incomplete_deps == 0 {
            ready.push(id);
        }
    }

    let mut schedule = vec![];
    while ready.len() != 0 {
        // FIXME: compute all of this shit incrementally lmao
        // recompute max height
        for id in graph.nodes() {
            let mut height = 0;
            if !nodes[id].issued {
                for dep in graph.pred_of(id) {
                    let node = &mut nodes[dep];
                    if node.issued {
                        height = height.max(node.max_height);
                    }
                }
            }
            nodes[id].max_height = height + 1;
        }
        // recompute the maximum height of the adjacent nodes
        for id in graph.nodes() {
            let mut peer_max_height = 0;
            if !nodes[id].issued {
                for s in graph.succ_of(id) {
                    if nodes[s].max_height > peer_max_height {
                        peer_max_height = nodes[s].max_height;
                    }
                }
            }
            nodes[id].peer_max_height = peer_max_height + 1;
        }

        ready.sort_by_cached_key(|&id| {
            let last_use_count = nodes[id].last_use_count;
            let priority = nodes[id].priority;
            let max_height = nodes[id].peer_max_height;

            (last_use_count, priority, !max_height)
        });

        let id = ready.pop().unwrap();
        schedule.push(id);
        nodes[id].issued = true;

        for succ in graph.succ_of(id) {
            nodes[succ].num_incomplete_deps -= 1;
            if nodes[succ].num_incomplete_deps == 0 {
                ready.push(succ);
            }
        }
        for dep in graph.pred_of(id) {
            nodes[dep].outstanding_users -= 1;

            if nodes[dep].outstanding_users == 1 {
                for ns in graph.succ_of(dep) {
                    nodes[ns].last_use_count += 1;
                }
            }
        }
        if nodes[id].outstanding_users == 1 {
            for ns in graph.succ_of(id) {
                nodes[ns].last_use_count += 1;
            }
        }
    }

    schedule
}