I have many pointers pointing to different (or same) locations in memory. I want to implement a mechanism that allows us to "fuse" the locations pointed to by a given subset of the pointers.
I am using perl 5.6.1 right now, but I am open to implementations in other languages. I came up with the following dumb implementation in perl:
my $ref1 = \1;
my $ref2 = \2;
print "${$ref1} : ${$ref2}\n"; # <-- prints 1 : 2
fuse(\$ref1, \$ref2); # <-- Make $ref2 point to same location as $ref1
print "${$ref1} : ${$ref2}\n"; # <-- prints 1 : 1 (which is correct)
sub fuse
{
${$_[1]} = ${$_[0]};
}
But this doesn't work as expected when we have to fuse more than once:
my $ref1 = \1;
my $ref2 = \2;
my $ref3 = \3;
print "${$ref1} : ${$ref2} : ${$ref3}\n"; # <-- prints 1 : 2 : 3
fuse(\$ref1, \$ref2); # <-- Make $ref2 point to same location as $ref1
print "${$ref1} : ${$ref2} : ${$ref3}\n"; # <-- prints 1 : 1 : 3 (which is correct)
fuse(\$ref3, \$ref1); # <-- Make $ref1 point to same location as $ref3
print "${$ref1} : ${$ref2} : ${$ref3}\n"; # <-- prints 3 : 1 : 3 ($ref2 is useless now)
sub fuse
{
${$_[1]} = ${$_[0]};
}
In the above example, I want all the three variables $ref1, $ref2, and $ref3 to finally point to a location which contains 3.
Is there a good way to accomplish this "fusing" without manually re-assigning every pointer whose referent we want to change?
Context:
I am trying to simulate a circuit (which has wires). When two nodes are connected by a wire, one of the attributes of both the nodes (let's say voltage) becomes the same. When one of these nodes is connected to a third node (with a wire), the voltages at all the three nodes become the same irrespective of what values they had previously and continues to remain same as long as the connection exists.
My attempts at googling how HDLs implement wires failed (I probably didn't know what to google).
I believe
Which means the following program defines the expected behaviour:
use strict;
use warnings qw( all );
use feature qw( say );
use FindBin qw( $RealBin );
use lib $RealBin;
use Wire qw( );
my $o1 = Wire->new( voltage => 1 );
my $o2 = Wire->new( voltage => 2 );
my $o3 = Wire->new( voltage => 3 );
my $o4 = Wire->new( voltage => 4 );
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4; # 1 2 3 4
$o2->fuse($o1);
$o3->fuse($o4);
$o1->fuse($o3);
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4; # 4 4 4 4
$o1->set_voltage(5);
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4; # 5 5 5 5
$o3->set_voltage(6);
say join " ", map $_->get_voltage(), $o1, $o2, $o3, $o4; # 6 6 6 6
This class achieves that:
package Wire;
use strict;
use warnings qw( all );
sub new {
my ($class, %args) = @_;
my $voltage = $args{voltage} // 0;
my $self = bless({}, $class);
$self->{shared_voltage} = { value => $voltage, backrefs => [] };
push @{ $self->{shared_voltage}{backrefs} }, \( $self->{shared_voltage} );
return $self;
}
sub get_voltage { $_[0]{shared_voltage}{value} }
sub set_voltage { $_[0]{shared_voltage}{value} = $_[1]; }
sub fuse {
my ($self, $new) = @_;
my $old_sv = $self->{shared_voltage}; my $old_sv_br = $old_sv->{backrefs};
my $new_sv = $new->{shared_voltage}; my $new_sv_br = $new_sv->{backrefs};
for my $backref (@$old_sv_br) {
$$backref = $new_sv;
push @$new_sv_br, $backref;
}
}
sub DESTROY {
my ($self) = @_;
@{ $self->{shared_voltage}{backrefs} } =
grep { $_ != \( $self->{shared_voltage} ) }
@{ $self->{shared_voltage}{backrefs} };
}
1;
The result is achieved by storing a list of of references to the fused nodes alongside the shared value. This is the same approach used by Copy-on-Write strings in Perl. The fused structure looks like this:
+-$o1--+ +-Wire----------------+
| Ref -------------->| +-shared_voltage--+ | +-anon hash------+
+------+ +---------->| Reference ------------------>| +-value------+ |
| | +-----------------+ | / / / | | 4 | |
| +---------------------+ | | | | +-backrefs---+ |
| | | | | | Reference -------+
| | | | | +------------+ | |
+-$o2--+ | +-Wire----------------+ | | | +----------------+ |
| Ref -----(-------->| +-shared_voltage--+ | | | | |
+------+ | +-------->| Reference -------+ | | +------------------------+
| | | +-----------------+ | | | |
| | +---------------------+ | | | +-anon array-----+
| | | | +-->| +-0----------+ |
| | | | | | Reference -------------+
+-$o3--+ | | +-Wire----------------+ | | | +-1----------+ | |
| Ref -----(-(------>| +-shared_voltage--+ | | | | | Reference -----------+ |
+------+ | | +------>| Reference ---------+ | | +-2----------+ | | |
| | | | +-----------------+ | | | | Reference ---------+ | |
| | | +---------------------+ | | +-3----------+ | | | |
| | | | | | Reference -------+ | | |
| | | | | +------------+ | | | | |
+-$o4--+ | | | +-Wire----------------+ | +----------------+ | | | |
| Ref -----(-(-(---->| +-shared_voltage--+ | | | | | |
+------+ | | | +---->| Reference -----------+ | | | |
| | | | | +-----------------+ | | | | |
| | | | +---------------------+ | | | |
| | | | | | | |
| | | | | | | |
| | | +--------------------------------------------------------------+ | | |
| | +------------------------------------------------------------------+ | |
| +----------------------------------------------------------------------+ |
+--------------------------------------------------------------------------+
(The order of the backrefs is not accurately represented.)
I think you'll find this much faster in practice than your solution. Like in yours, fusing is O(N). However, getting and setting the voltage is O(1) instead of O(N). And while object destruction is O(N) instead of O(1) in mine, it could be made O(1) by using a hash instead of an array for the backrefs. That said. It's probably practically faster as an array. This is what Perl does for CoW strings. N is the size of the fusing (4 in our test case).