Chunks of finalized

Chunks of finalized

[Richard A. O'Keefe]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2693 bytes --]


Let's consider a stack, that might grow very large, or might be quite
small.  This is not an actual application, it's just the context for
what I want to understand.

One way to implement a stack like that is as a linked list of arrays,
plus a counter:

    type Stack_Chunk is array (0 .. Chunk_Size - 1) of Stack_Element;

    type Stack_Node;
    type Stack_Link is access Stack_Node;
    type Stack_Node is
       record
          Data: Stack_Chunk;
          Next: Stack_Link;
       end record;

    type Stack is
       record
          Count: Natural;
          List : Stack_Link;
          Spare: Stack_Link;
       end record;

Why the Spare?  Because a well known thing about implementing a stack
this way is that if you keep on pushing and popping just at the boundary
of a chunk, you can spend an awful lot of time allocating and freeing.
By keeping just one spare chunk, you can eliminate that problem.

The problem is, what if the stack elements are derived from
Ada.Finalization.Controlled?

The lifetime of an object contains at least the following steps:

    1. allocate raw storage
    2. initialise
    3. use
    4. finalise
    5. release raw storage.

In this stack example, if Chunk_Size is 10 and Count is 25, we might
have 3 records in the List and 1 Spare, for a total of 40 Stack_Elements
that have been _allocated_, but only 25 of which are _in use_.

I have some old Pascal code, using an intricate and rather fragile set
of M4 macros, that provided generic code doing this sort of thing.  In
that code, my framework ensured there were operations
	T$make(X)	convert raw storage to a valid T
	T$free(X)	convert a valid T back to raw storage
	T$reset(X)	make a valid T empty (release resources as far
			as possible while leaving the object valid)
for each type.  When a chunk is allocated, I'd call T$make() on the
elements.  When a chunk is freed, I'd call T$free() on the elements
first.  And when an element is popped from the stack, I'd call T$reset()
on the element.  (Obviously integer$reset and integer$free expanded to
nothing.)

I've been trying to figure out how to do this in Ada, and I don't think
I can.  If one is trying to implement a generic container data structure,
there is nothing one can do to tell the elements 'stay alive but forget
everything', except include such an operation as one of the generic
parameters.

What have I missed?

How is it that people using the Booch components don't find this
a problem?  (I haven't understood anything in the current Booch-95
components as doing this.)

-- 
John �neas Byron O'Keefe; 1921/02/04-1997/09/27; TLG,TLTA,BBTNOTL.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: Chunks of finalized

[Stephen Leake]

Richard A. O'Keefe wrote:
> =

>     type Stack_Chunk is array (0 .. Chunk_Size - 1) of Stack_Element;
> =

>     type Stack_Node;
>     type Stack_Link is access Stack_Node;
>     type Stack_Node is
>        record
>           Data: Stack_Chunk;
>           Next: Stack_Link;
>        end record;
> =

>     type Stack is
>        record
>           Count: Natural;
>           List : Stack_Link;
>           Spare: Stack_Link;
>        end record;
> =

> The problem is, what if the stack elements are derived from
> Ada.Finalization.Controlled?

I don't see why this is an issue at all.

> The lifetime of an object contains at least the following steps:
> =

>     1. allocate raw storage
>     2. initialise
>     3. use
>     4. finalise
>     5. release raw storage.
> =

> In this stack example, if Chunk_Size is 10 and Count is 25, we might
> have 3 records in the List and 1 Spare, for a total of 40 > Stack_Eleme=
nts
> that have been _allocated_, but only 25 of which are _in use_.

Do you want to call Finalize on the elements that have been Popped? =

 =

> I've been trying to figure out how to do this in Ada, and I don't > thi=
nk
> I can.  If one is trying to implement a generic container data > struct=
ure,
> there is nothing one can do to tell the elements 'stay alive but > forg=
et
> everything', except include such an operation as one of the generic
> parameters.

I'm not clear what you mean by "forget everything", but it seems like
you want to call Finalize on the stack elements. The issue is how to get
the stack container to do this. One way would be to deallocate, which
you are trying to avoid. Another way is to assign another object to the
stack slot, which will be done by the next Push. The only other way is
to explicitly call Finalize. If your container is a generic that takes a
type Stack_Element_Type, then make it also take an operation
Finalize_Stack_Element, which is called by Pop (_after_ copying :), and
can be null for non-controlled elements. This seems to be what you are
suggesting.

Another question is why you need to call Finalize when the item is
popped, rather than waiting until the item is overwritten or
deallocated. The item will never be used in any way, so even if it
contains dangling pointers, you are safe. =

 =

> What have I missed?

Nothing, as far as I can see.
 =

> How is it that people using the Booch components don't find this
> a problem?  (I haven't understood anything in the current Booch-95
> components as doing this.)

I haven't read the Booch components in enough detail to address this. =


> =

> --
> John =C6neas Byron O'Keefe; 1921/02/04-1997/09/27; TLG,TLTA,BBTNOTL.
> Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

-- =

- Stephe

Re: Chunks of finalized

[Robert A Duff]

In article <3434F45A.37ED@gsfc.nasa.gov>,
Stephen Leake  <Stephen.Leake@gsfc.nasa.gov> wrote:
>Do you want to call Finalize on the elements that have been Popped? =

That's presumably the issue.  These elements might be hanging on to some
expensive resource, and he wants to free that resource as soon as
possible -- not waiting for a whole chunk to be deallocated.

>... Another way is to assign another object to the
>stack slot, which will be done by the next Push.

Aha!  Thank you.

Why wait until the next Push (which might be a long time, or never)?
Inside the generic, you could declare:

    type Stack_Element_Holder(Present: Boolean := False) is
        record
            case Present is
                when False => null;
                when True => The_Element: Stack_Element_Type;
            end case;
        end record;

And then build the stack out of arrays of these things.  Then, whenever
you Pop, assign a "Stack_Element_Holder'(Present => False)" into the
vacated slot.  I think this achieves what the original poster wanted --
it will call Finalize on The_Element (if its controlled), and it will
also call Finalize on all controlled subcomponents of The_Element.  And
there's no need to pass in an extra finalization operation, nor to
handle subcomponents by hand.  It costs an extra Boolean component for
every stack element, though.

- Bob

Re: Chunks of finalized

[Tucker Taft]

Robert A Duff (bobduff@world.std.com) wrote:

: ...
: Why wait until the next Push (which might be a long time, or never)?
: Inside the generic, you could declare:

:     type Stack_Element_Holder(Present: Boolean := False) is
:         record
:             case Present is
:                 when False => null;
:                 when True => The_Element: Stack_Element_Type;
:             end case;
:         end record;

: And then build the stack out of arrays of these things.  Then, whenever
: you Pop, assign a "Stack_Element_Holder'(Present => False)" into the
: vacated slot.  I think this achieves what the original poster wanted --
: it will call Finalize on The_Element (if its controlled), and it will
: also call Finalize on all controlled subcomponents of The_Element.  And
: there's no need to pass in an extra finalization operation, nor to
: handle subcomponents by hand.  It costs an extra Boolean component for
: every stack element, though.

It might be easier to just take an extra generic IN parameter,
an "Empty_Value" of the Stack_Element_Type.  This value could be
used to initialize and reinitialize the stack elements.

: - Bob

--
-Tucker Taft   stt@inmet.com   http://www.inmet.com/~stt/
Intermetrics, Inc.  Burlington, MA  USA

Re: Chunks of finalized

[Richard A. O'Keefe]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 711 bytes --]


Thank you to all the people who offered suggestions.

stt@houdini.camb.inmet.com (Tucker Taft) writes:

>It might be easier to just take an extra generic IN parameter,
>an "Empty_Value" of the Stack_Element_Type.  This value could be
>used to initialize and reinitialize the stack elements.

All things considered, this is probably the neatest answer, in that
it works whether the element type is controlled or not.  It's clumsy,
because the same Empty_Value should work for all sorts of containers,
so it's unhelpful redundancy to have to keep on spelling it out.

-- 
John �neas Byron O'Keefe; 1921/02/04-1997/09/27; TLG,TLTA,BBTNOTL.
Richard A. O'Keefe; http://www.cs.rmit.edu.au/%7Eok; RMIT Comp.Sci.

Re: Chunks of finalized

[Robert A Duff]

In article <6129sn$n91$1@goanna.cs.rmit.edu.au>,
Richard A. O'Keefe <ok@goanna.cs.rmit.edu.au> wrote:
>Let's consider a stack, that might grow very large, or might be quite
>small.  This is not an actual application, it's just the context for
>what I want to understand.

By the way, wouldn't a simpler stack implementation illustrate your
question just as well?  A record containing an array of elements, and an
index of the top of the stack.  The issue is that you want to finalize
an element when the Top pointer is decremented, right?

You can call Finalize explicitly, if you like.  And Finalize operations
should normally be implemented in such a way that they work properly
when you finalize things twice.

However, there's no way to explicitly say "finalize this thing,
including all its subcomponents".  This happens when you leave a
procedure, or when you Unchecked_Deallocate, but you can't do it
explicitly.  If you made it an array of access-to-whatever, then you
could Unchecked_Deallocate each component when necessary.  But
unfortunately I don't see any way to invoke finalization (including
subcomponents) other than that.

Does that answer your question?

- Bob

Re: Chunks of finalized

[Matthew Heaney]

In article <6129sn$n91$1@goanna.cs.rmit.edu.au>, ok@goanna.cs.rmit.edu.au
(Richard A. O'Keefe) wrote:


>I've been trying to figure out how to do this in Ada, and I don't think
>I can.  If one is trying to implement a generic container data structure,
>there is nothing one can do to tell the elements 'stay alive but forget
>everything', except include such an operation as one of the generic
>parameters.
>
>What have I missed?

The stack element will get finalized the next time you push an element onto
the stack.  If you want it to happen sooner, I'd import an Finalization
operator.  My stack hierarchy looks something like this

generic
   type Stack_Item is private;
package Stacks_G is

   type Root_Stack is abstract tagged null record;

   procedure Push (Item : in Stack_Item; On : in out Root_Stack);

   procedure Pop (Stack : in out Root_Stack);

   function Top (Stack : Root_Stack) return Stack_Item;

end;

Now let's say there's a bounded stack implementation:

generic
   Max : Positive;
package Stacks_G.Bounded_G is

   type Bounded_Stack is new Root_Stack with private;

   <ops here>

private

   subtype Top_Range is Positive range 0 .. Max;

   subtype Item_Array_Range is Top_Range range 1 .. Max;

   type Item_Array is array (Item_Array_Range) of Stack_Item;

   type Bounded_Stack is
      new Root_Stack with
         record
            Items : Item_Array;
            Top     : Top_Range := 0;
         end record;

end Stacks_G.Bounded_G;

Now, let's say you're a stack user with a special need, to have a stack
item you need finalized right away, as soon as it's popped from the stack. 
So we just subclass off the bounded stack:

generic
   with procedure Finalize (Item : in out Stack_Item);
package Stacks_G.Bounded_G.Finalizable_G is

   type Finalizable_Stack is new Bounded_Stack with null record;

   -- Override Pop
   procedure Pop (Stack : in out Finalizable_Stack);

end;

package body Stacks_G.Bounded_G.Finalizable_G is

   procedure Pop (Stack : in out Finalizable_Stack) is
   begin
      <check preconditions>
      Finalize (Stack.Items (Stack.Top));
      Pop (Bounded_Stack (Stack));
   end;

end;

Another way is to import a dummy item:

generic
   Dummy_Item : in Stack_Item;
package Stacks_G.Bounded_G.Finalizable_G is

   type Finalizable_Stack is ...

and in the body

   procedure Pop (Stack : in out Finalizable_Stack) is
   begin
      <check pre>
      Stack.Items (Stack.Top) := Dummy_Item;
      Pop (Bounded_Stack (Stack));
   end;

The latter formulation would be suitable if there isn't a Finalization
operation, but there is a constant that's a null version:

   type AVL_Set is new Root_Set with private;
   Empty_Set : constant AVL_Set;

(Though in this case there's probably a Clear operation too).

You could use Bob's idea too, implementing the stack array component as a
discriminant record:

   procedure Pop (Stack : in out Bounded_Stack) is
   begin
      begin
          Stack.Items (Stack.Top) := (Available => False);
      exception
         when Constraint_Error => raise Stack_Empty;
      end;

       Stack.Top := Stack.Top - 1;
   end Pop;

His discriminated record solution asks the user to do the least (you don't
need import anything), but as he pointed out, there is a space penalty.

--------------------------------------------------------------------
Matthew Heaney
Software Development Consultant
<mailto:matthew_heaney@acm.org>
(818) 985-1271