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

[Dmitry E. Oboukhov]

RZ> weaken вам в руки, только возникает проблема, нужно всегда держать
RZ> ссылку на голову или хвост, в зависимости от направленности списка, а
RZ> иначе будут отваливаться куски.

эмм... фишка двусвязного списка как раз в том что пофиг накуда у тебя
ссылка. ничего не должно отваливаться
поскольку он всегда закольцован

один элемент next и prev указывают на него же
два элемента
 1 next -> 2
 2 next -> 1
 
 1 prev -> 2
 2 prev -> 1

три элемента
 1 next -> 2
 2 next -> 3
 3 next -> 1
 
 1 prev -> 3
 2 prev -> 1
 3 prev -> 2

и так далее.
откуда бы не начали, вернемся в итоге туда откуда начали (и это
условие окончания цикла).

иногда выделяют указатель на голову (тогда циклы проще), иногда нет
зависит от реализации. 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
----------- следущая часть -----------
A non-text attachment was scrubbed...
Name: отсутствует
Type: application/pgp-signature
Size: 197 bytes
Desc: Digital signature
URL: <http://mail.pm.org/pipermail/moscow-pm/attachments/20090727/60bffdd5/attachment-0001.bin>