+ return ($id_map, $root_uid, $root_gid);
+}
+
+sub validate_id_maps {
+ my ($id_map) = @_;
+
+ # $mappings->{$type}->{$side} = [ { line => $line, start => $start, count => $count }, ... ]
+ # $type: either "u" or "g"
+ # $side: either "container" or "host"
+ # $line: index of this mapping in @$id_map
+ # $start, $count: interval of this mapping
+ my $mappings = { u => {}, g => {} };
+ for (my $i = 0; $i < scalar(@$id_map); $i++) {
+ my ($type, $ct_start, $host_start, $count) = $id_map->[$i]->@*;
+ my $sides = $mappings->{$type};
+ push $sides->{host}->@*, { line => $i, start => $host_start, count => $count };
+ push $sides->{container}->@*, { line => $i, start => $ct_start, count => $count };
+ }
+
+ # find the first conflict between two consecutive mappings when sorted by their start id
+ for my $type (qw(u g)) {
+ for my $side (qw(container host)) {
+ my @entries = sort { $a->{start} <=> $b->{start} } $mappings->{$type}->{$side}->@*;
+ for my $idx (1..scalar(@entries) - 1) {
+ my $previous = $entries[$idx - 1];
+ my $current = $entries[$idx];
+ if ($previous->{start} + $previous->{count} > $current->{start}) {
+ my $conflict = $current->{start};
+ my @previous_line = $id_map->[$previous->{line}]->@*;
+ my @current_line = $id_map->[$current->{line}]->@*;
+ die "invalid map entry '@current_line': $side ${type}id $conflict "
+ ."is also mapped by entry '@previous_line'\n";
+ }
+ }
+ }
+ }
+}
+
+sub map_ct_id_to_host {
+ my ($id, $id_map, $id_type) = @_;
+
+ for my $mapping (@$id_map) {
+ my ($type, $ct, $host, $length) = @$mapping;
+
+ next if ($type ne $id_type);
+
+ if ($id >= $ct && $id < ($ct + $length)) {
+ return $host - $ct + $id;
+ }
+ }
+
+ return $id;
+}
+
+sub map_ct_uid_to_host {
+ my ($uid, $id_map) = @_;
+
+ return map_ct_id_to_host($uid, $id_map, 'u');
+}
+
+sub map_ct_gid_to_host {
+ my ($gid, $id_map) = @_;
+
+ return map_ct_id_to_host($gid, $id_map, 'g');