Re: Doubly linked list.

[Simon Wright <simon@pogner.demon.co.uk>]

"news.oxy.com" <Vladimir_Olensky@oxy.com> writes:

> Have a look at the ADA95 implementation of the Booch components
>  http://www.pogner.demon.co.uk/components/bc/ ).
> Everything is already at hand (including all types of  linked lists). Just
> use it. Also this is very good example of ADA95 programming.

Thanks for that, Vladimir! (from me and the team)

One small point, which I'm not sure how to address; the BCs have a
perhaps surprising take on manipulating lists.

The following comment is a direct transliteration of the C++ words
(and it shows in places!  "member function" indeed ..):

  -- Unreachable items are those that belong to a list or a sublist whose
  -- head is not designated by any alias. For example, consider the list (A
  -- B C), with the head of the list designated by L1. L1 initially points
  -- to the head of the list, at item A. Invoking the member function Tail
  -- on L1 now causes L1 to point to item B. Because A is now considered
  -- unreachable, the storage associated with item A is reclaimed; the
  -- predecessor of B is now null. Similarly, consider the list (D E F),
  -- with the head of the list designated by both L1 and L2. Both L1 and L2
  -- are aliases that initially point to the head of the list at item
  -- D. Invoking the member function Tail on L1 now causes L1 to point to
  -- item E; L2 is unaffected. Suppose we now invoke the member function
  -- clear on L2. The semantics of this operation are such that only
  -- unreachable items are reclaimed. Thus, the storage associated with
  -- item D is reclaimed, because it is no longer reachable; L2 is now
  -- null, and the predecessor of E is now null. Items E and F are not
  -- reclaimed, because they are reachable through L1.

I think this is not in fact that far from a Lisp approach, but at
least one user has been bitten by it (not helped by there being an
effor which meant that parts of the list were sometimes reachable when
they shouldn't have been).

STk> (define foo '(a b c))
STk> (define bar foo)
STk> (set! foo (cdr foo))
STk> foo
(b c)
STk> bar
(a b c)

Of course, there's no easy equivalent of the doubly-linked list ..