rollup.odin (3189B)
1 package main 2 3 import "scan" 4 5 /* 6 Directory totals maintained across passes. 7 8 Recomputing from scratch costs the whole tree every time, which is what made the 9 simulated UI's frames climb from 14 ms to 50. Totals are never cleared here; each node 10 is charged once and stays charged. 11 12 Which nodes those are is read off the tree rather than told: a reader says a node is 13 settled, and `charged` remembers whether this has acted on it yet. That keeps the 14 arithmetic the same whichever reader ran, and a node whose ancestors have not arrived 15 is simply left unmarked and reached again next pass. 16 */ 17 Rollup :: struct { 18 totals: [dynamic]u64, 19 charged: [dynamic]u64, // one bit per node 20 pending: int, // settled nodes still waiting on an ancestor, as of the last pass 21 } 22 23 rollup_destroy :: proc(r: ^Rollup) { 24 delete(r.totals) 25 delete(r.charged) 26 r^ = {} 27 } 28 29 // Forget every total, for a reader that has restated what it already said. 30 rollup_restate :: proc(r: ^Rollup) { 31 for i in 0 ..< len(r.totals) { 32 r.totals[i] = 0 33 } 34 for i in 0 ..< len(r.charged) { 35 r.charged[i] = 0 36 } 37 r.pending = 0 38 } 39 40 // Charge every settled node not charged already. 41 rollup_advance :: proc(r: ^Rollup, t: ^scan.Tree) { 42 count := int(scan.slots(t)) 43 if count > len(r.totals) { 44 resize(&r.totals, count) 45 } 46 if words := (count + 63) / 64; words > len(r.charged) { 47 resize(&r.charged, words) 48 } 49 r.pending = 0 50 for i in 0 ..< u32(count) { 51 if marked(r.charged[:], i) { 52 continue 53 } 54 f := scan.node_flags(scan.node(t, i)) 55 if .Used not_in f || .Settled not_in f { 56 continue 57 } 58 if charge(r, t, i) { 59 mark(r.charged[:], i) 60 } else { 61 r.pending += 1 62 } 63 } 64 } 65 66 /* 67 Charge a node to every ancestor at once, or to none of them. 68 69 Stopping halfway would mean resuming from the middle once the rest of the chain 70 arrives, which needs a record per node of how far it got. Waiting costs a re-walk 71 instead, and the chain is a handful of links. 72 73 Every node on the way up must be settled, not merely present: an unsettled one is 74 rooted at itself for now and would look like the top of the tree. Returning false 75 leaves it uncharged, which is the whole of what has to be remembered about it. 76 */ 77 @(private) 78 charge :: proc(r: ^Rollup, t: ^scan.Tree, i: u32) -> bool { 79 n := scan.node(t, i) 80 flags := scan.node_flags(n) 81 if .Extra_Name in flags { 82 return true // another name for a file already charged 83 } 84 chain: [64]u32 85 depth := 0 86 cur := i 87 for depth < len(chain) { 88 c := scan.node(t, cur) 89 if .Settled not_in scan.node_flags(c) { 90 return false 91 } 92 // A root, an orphan, or a parent that leaves the tree: the chain ends here. 93 // The batch roll-up and path rebuilding both stop on the same conditions, and 94 // this is the one that runs while a reader is still filling slots in. 95 if c.parent == cur || c.parent >= u32(len(r.totals)) { 96 break 97 } 98 chain[depth] = c.parent 99 depth += 1 100 cur = c.parent 101 } 102 if .Directory in flags { 103 r.totals[i] += n.disk 104 } 105 for j in 0 ..< depth { 106 r.totals[chain[j]] += n.disk 107 } 108 return true 109 } 110 111 @(private) 112 marked :: proc(b: []u64, i: u32) -> bool { 113 return b[i >> 6] & (1 << uint(i & 63)) != 0 114 } 115 116 @(private) 117 mark :: proc(b: []u64, i: u32) { 118 b[i >> 6] |= 1 << uint(i & 63) 119 }