| 52 | } |
| 53 | |
| 54 | fn encode_tree( |
| 55 | hashes: &[Hash], |
| 56 | intern: &mut impl FnMut(&[u8; 32], &[u8; 64]) -> PristineResult<()>, |
| 57 | ) -> PristineResult<[u8; 32]> { |
| 58 | if hashes.is_empty() { |
| 59 | return Ok(EMPTY); |
| 60 | } |
| 61 | let mut node = [0u8; 64]; |
| 62 | if hashes.len() == 1 { |
| 63 | node[32..].copy_from_slice(hashes[0].as_bytes()); |
| 64 | } else { |
| 65 | let first = hashes.first().unwrap().as_bytes(); |
| 66 | let last = hashes.last().unwrap().as_bytes(); |
| 67 | let byte = first.iter().zip(last).position(|(a, b)| a != b).unwrap(); |
| 68 | let mask = 0x80u8 >> (first[byte] ^ last[byte]).leading_zeros(); |
| 69 | let split = hashes.partition_point(|hash| hash.as_bytes()[byte] & mask == 0); |
| 70 | let left = encode_tree(&hashes[..split], intern)?; |
| 71 | let right = encode_tree(&hashes[split..], intern)?; |
| 72 | node[..32].copy_from_slice(&left); |
| 73 | node[32..].copy_from_slice(&right); |
| 74 | } |
| 75 | let id = node_id(&node); |
| 76 | if id == EMPTY { |
| 77 | return Err(invalid("Git closure node collides with the empty tree")); |
| 78 | } |
| 79 | intern(&id, &node)?; |
| 80 | Ok(id) |
| 81 | } |
| 82 | |
| 83 | pub(crate) fn decode( |
| 84 | bytes: &[u8], |