[Moscow.pm] двусвязный список: удаление мусора
Ruslan Zakirov
ruslan.zakirov на gmail.com
Пн Июл 27 07:22:29 PDT 2009
Привет,
Я еще помню немного теорию. То что закольцованно, то называется
кольцом, а не списком. Оба бывают одно-связными или двух-связными.
Двух - это когда у вас есть связь на оба соседних элемента, а
одно-связный - это ссылка только следующий элемент.
Если мы говорим об одно-связных списках, то тут в любых языках нужно
хранить ссылку на голову и ничего не поделаешь, даже в перл:
i
1->2->3
У всех элементов счетчик ссылок равен 1. И при потери внешней ссылки
на первый элемент все высвобождается.
Если говорить о кольце односвязном, то тут уже получается цикл:
i
1->2->3->1
У первого элемента счетчик равен двум и после потери ссылки получаем
утечку, как кстати и во многих других языках.
Аналогично и с другими структурами, нужно какую-то ссылку ослабить, но
тогда возвращаемся к одно-связной структуре, которая участвует в
управлении освобождением элементов и дополнительными ссылками, которые
живут, пока жива структура.
Еще решение - явный вызов разрушения. Что-то типа функции free,
которая отстрелит ссылки и вызовет free на этих объектах.
Есть еще вариант захачить ядро и сделать парные ослабленные ссылки, но
это скорее всего будет медленно.
2009/7/27 Dmitry E. Oboukhov <unera на debian.org>:
>
> 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
>
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.9 (GNU/Linux)
>
> iEYEAREDAAYFAkptssIACgkQq4wAz/jiZTcxmgCg2eJii7wJqEqH1CcoxC8MN9IG
> FGkAnjKPIHc6M4A4GioFSEEJ2tgXB2+w
> =46q2
> -----END PGP SIGNATURE-----
>
> --
> Moscow.pm mailing list
> moscow-pm на pm.org | http://moscow.pm.org
>
>
--
Best regards, Ruslan.
Подробная информация о списке рассылки Moscow-pm