[Moscow.pm] двусвязный список: удаление мусора

[Ruslan Zakirov]

Узнал сегодня новое :) А также решил заблогить:
http://cubloid.blogspot.com/2009/07/proper-double-linked-list.html

В конечном коде есть небольшая недоработка, код ниже. Внимание
конкурс. Нашедшему ошибку полагается пиво или сок (по выбору) в баре
после сентябрьской встречи :)

2009/7/27 Ruslan Zakirov <ruslan.zakirov на gmail.com>:
> И у одного вас желание магии. Можно в DESTROY востанавливать ссылки,
> только если это не глобальный дестрой, а его можно прочекать. Ну и
> навешивать магию или еще что-то делать. Есть попытка создать модуль:
> http://git.shadowcat.co.uk/gitweb/gitweb.cgi?p=p5sagit/Mutually-Assured-Destruction.git;a=summary
>
> У меня получилось следующее:
> use strict;
> use warnings;
> use 5.008;
>
> package List;
> use Scalar::Util qw(weaken isweak);
> use Devel::GlobalDestruction;
>
> 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;
>        weaken $self->{'prev'};
>    }
>    return $self->{'prev'};
> }
>
> sub next {
>    my $self = shift;
>    if ( @_ ) {
>        my $next = $self->{'next'} = shift;
>        $next->{'prev'} = $self;
>        weaken $next->{'prev'};
>    }
>    return $self->{'next'};
> }
>
> 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'};
>    }
> }
>
> package main;
> use Data::Dumper;
>
> my $node;
> {
>    my $head = List->new(v=>1);
>    $head->next( List->new(v=>3)->prev( List->new(v=>2) ) );
>    $node = $head;
> }
> print Dumper( $node );
> $node = $node->next->next;
> print Dumper( $node );
> $node = $node->prev;
> print Dumper( $node );
>
> 2009/7/27 Alexander Alekseev <alex на alemate.ru>:
>>
>>
>> On Mon, 27 Jul 2009, Dmitry E. Oboukhov wrote:
>>
>>>
>>> RZ> weaken вам в руки, только возникает проблема, нужно всегда держать
>>> RZ> ссылку на голову или хвост, в зависимости от направленности списка, а
>>> RZ> иначе будут отваливаться куски.
>>>
>>> эмм... фишка двусвязного списка как раз в том что пофиг накуда у тебя
>>> ссылка. ничего не должно отваливаться
>>> поскольку он всегда закольцован
>>
>> ...
>>>
>>> weaken посмотрю вечерком
>>
>>        Это не фича списка, а фича weaken.
>>
>>> RZ> 2009/7/27 Dmitry E. Oboukhov <unera на debian.org>:
>>>>>
>>>>> package ListItem;
>>>>>
>>>>> sub new
>>>>> {
>>>>>    my ($class, $value) = @_;
>>>>>    my $self = bless { value => $value }, $class;
>>>>>    return $self->{prev} = $self->{next} = $self;
>>>>> }
>>>>>
>>>>> sub append
>>>>> {
>>>>>    my ($self, $add);
>>>>>
>>> $add->>> {next} = $self->{next};
>>> $add->>> {prev} = $self;
>>>>>
>>>>>    $self->{next}{prev} = $add;
>>>>>    $self->{next} = $add;
>>>>>
>>>>>    return $self;
>>>>> }
>>>>>
>>>>>
>>>>> далее собираем список:
>>>>>
>>>>> ...
>>>>>
>>>>> package main;
>>>>> my $list = ListItem->new('value1')
>>>
>>> ->>> append( ListItem->new('value2') )
>>> ->>> append( ListItem->new('value3') )
>>> ->>> append( ListItem->new('value4') )
>>> ->>> append( ListItem->new('value5') )
>>> ->>> append( ListItem->new('value6') );
>>>>>
>>>>> ну и где-то используем
>>>>>
>>>>> имеем во весь рост проблемы со сборкой мусора, поскольку собственно
>>>>> эта сущность представляет собой набор циклических ссылок. Как-нибудь
>>>>> кроме как введением деструктора можно решить проблему со сборкой
>>>>> мусора? понятно что лучше массивы итп но это не подходит по некоторым
>>>>> причинам.
>>>>>
>>>>> как вариант такое:
>>>>>
>>>>> package ListItem;
>>>>> sub new
>>>>> {
>>>>>    my ($class, $value) = @_;
>>>>>    my $self = bless { value => $value }, $class;
>>>>>    $self->set_next($self);
>>>>>    $self->set_prev($self);
>>>>>    $self;
>>>>> }
>>>>>
>>>>> sub set_next
>>>>> {
>>>>>    my ($self, $next) = @_;
>>>>>    $self->{_next} = sub { $next };
>>>>> }
>>>>>
>>>>> sub set_prev
>>>>> {
>>>>>    my ($self, $prev) = @_;
>>>>>    $self->{_prev} = sub { $prev };
>>>>> }
>>>>>
>>>>> sub next { $_[0]{_next}->() }
>>>>> sub prev { $_[0]{_prev}->() }
>>>>>
>>>>> sub append
>>>>> {
>>>>>    my ($self, $add);
>>>>>
>>> $add->>> set_next($self->next);
>>> $add->>> set_prev($self);
>>>>>
>>>>>    $self->next->set_prev($add);
>>>>>    $self->set_next($add);
>>>>>    return $self;
>>>>> }
>>>>>
>>>>> Но как-то кажется неизящным. Очень странно что ссылки в анонимных
>>>>> процедурах сборщик мусора нормально собирает, а в просто объектах
>>>>> нет.
>>>>>
>>>>> PS: сорри за возможные ашипки в коде
>>>>> --
>>>>> ... mpd playing: Metallica - The God That Failed
>>>>>
>>>>> . ''`.                               Dmitry E. Oboukhov
>>>>> : :’  :   email: unera на debian.org jabber://UNera@uvw.ru
>>>>> `. `~’              GPGKey: 1024D / F8E26537 2006-11-21
>>>>>  `- 1B23 D4F8 8EC0 D902 0555  E438 AB8C 00CF F8E2 6537
>>>>>
>>>>> -----BEGIN PGP SIGNATURE-----
>>>>> Version: GnuPG v1.4.9 (GNU/Linux)
>>>>>
>>>>> iEYEAREDAAYFAkptrHkACgkQq4wAz/jiZTc7yACeLqOtBkEvcENar7CK/KUIwg9a
>>>>> nIkAoIrVHzxn6bNG6LVBOLzX+NLkxdPR
>>>>> =J61J
>>>>> -----END PGP SIGNATURE-----
>>>>>
>>>>> --
>>>>> Moscow.pm mailing list
>>>>> moscow-pm на pm.org | http://moscow.pm.org
>>>>>
>>>>>
>>> --
>>> ... mpd playing: Helloween - Ride The Sky
>>>
>>> . ''`.                               Dmitry E. Oboukhov
>>> : :’  :   email: unera на debian.org jabber://UNera@uvw.ru
>>> `. `~’              GPGKey: 1024D / F8E26537 2006-11-21
>>>  `- 1B23 D4F8 8EC0 D902 0555  E438 AB8C 00CF F8E2 6537
>>
>> --
>> Moscow.pm mailing list
>> moscow-pm на pm.org | http://moscow.pm.org
>>
>>
>
>
>
> --
> Best regards, Ruslan.
>



-- 
Best regards, Ruslan.