Proper double linked list

Double linked list is well known structure. Each element refereces prev and next element in the chain:

    use strict;
    use warnings;

    package List;

    sub new {
        my $proto = shift;
        my $self = bless {@_}, ref($proto) || $proto;
    }

    sub prev {
        my $self = shift;
        if ( @_ ) {
            my $prev = $self->{'prev'} = shift;
            $prev->{'next'} = $self;
        }
        return $self->{'prev'};
    }

    sub next {
        my $self = shift;
        if ( @_ ) {
            my $next = $self->{'next'} = shift;
            $next->{'prev'} = $self;
        }
        return $self->{'next'};
    }

    package main;

    my $head = List->new(v=>1);
    $head->next( List->new(v=>3)->prev( List->new(v=>2) ) );

Clean and simple. If you experienced in perl you should know that such thing leaks memory. Each element has at least one reference all the time from neighbor, so perl's garbage collector never sees that structure can be collected. It's called refernce cycle, google for it. As well, you may know that weaken from Scalar::Util module can help you solve this:

    use Scalar::Util qw(weaken);

    sub prev {
        my $self = shift;
        if ( @_ ) {
            my $prev = $self->{'prev'} = shift;
            $prev->{'next'} = $self;
            weaken $self->{'prev'};
        }
        return $self->{'prev'};
    }

    # similar thing for next

So we weak one group of references, in our example prev links. It's a win and loose. Yes, perl frees elements before exit, no more memory leaks, it's our win. But, there is always but, you can not leave point to the first element out of the scope or otherwise some elements can be freed without your wish. For a while I thought that it's impossible to solve this problem, but recent hacking, reading on perl internalsand a question on a mailing list ding a bell. After a short discussion on #p5p irc channel with Matt Trout, solution has been found. Actually there it's all been there and Matt even has module started that may help make it all easier, but here we're going to look at guts.

DESTROY method called on destroy we all know that, but a few people know that we can prevent actual destroy by incrementing reference counter on the object. One woe - you shouldn't do it during global destruction, but there is module to check when we're called:

    use Devel::GlobalDestruction;

    sub DESTROY {
        return if in_global_destruction;
        do_something_a_little_tricky();
    }

What we can do with this? We have two links: from the current element to next and from that next back to the current. One of them is weak and on destroy we can swap them if the element that is going to be destroyed is referenced by a weak link. It's easier in code than in my words:

    sub DESTROY {
        return if in_global_destruction();

        my $self = shift;
        if ( $self->{'next'} && isweak $self->{'next'}{'prev'} ) {
            $self->{'next'}{'prev'} = $self;
            weaken $self->{'next'};
        }
        if ( $self->{'prev'} && isweak $self->{'prev'}{'next'} ) {
            $self->{'prev'}{'next'} = $self;
            weaken $self->{'prev'};
        }
    }

That's it, now you can forget about heads of the Lists, pass around any element you like. isweak is also part of Scalar::Util module. Good luck with cool lists and other linked structures. Matt is looking for help with his module. You always can find user mst on irc.perl.org to chat about this.