Impossible problem? A protected buffer to queue objects of a class-wide type

Impossible problem? A protected buffer to queue objects of a class-wide type

[Phil Slater]

I've hit a brick wall. Every strategy I try doesn't work.

I need to write a generic package that exports a protected queue type that 
will act as a buffer for objects of a class-wide type. My strategy is that 
when objects join the queue they are copied onto the heap, and an 
access-to-class-wide value is put onto the queue (could be array-based or 
linked-list-based - I don't mind). To retrieve an item from the queue, an 
access-to-class-wide value is removed from the queue, the heap object it 
designates is copied onto the stack, the heap object is deallocated, then 
the copy is returned.

The crux of the problem goes like this:

(a) for the client code to retrieve an item, it needs to call a function; it 
can't be done through a procedure or entry "out" parameter since I can't 
declare an uninitialised variable of the class-wide type to pass as an 
actual parameter. So the client code needs to do something like this:
    declare
        Next_In_Line : Item'class := My_Buffer.Dequeue;  -- My_Buffer is the 
protected queue

(b) To support this call, Dequeue must be written as a function. As such, it 
cannot change the protected queue. What I need is the "entry" functionality, 
since I want the Dequeue to wait if the queue is empty, and I want the item 
to be removed from the queue as well as retrieved.

(c) In a non-concurrent environment, I would simply write two separate 
operations on the queue: a function Read_Next_Item and a procedure 
Delete_Next_Item, which the client code would call in turn. However, that's 
no good in a concurrent environment - two tasks could both call 
Read_Next_Item before the first has had a chance to call Delete_Next_Item, 
so the same item is read twice and the following item is skipped.

I really do want all the heap operations through the access-to-class-wide 
type to be hidden away in the package - I did consider writing a protected 
buffer with an entry whose out parameter was an access-to-class-wide type, 
but this is highly unsatisfactory as it puts the onus for deallocating heap 
space into the client code - very messy.

I cannot see a way through this problem, and am astounded that a language of 
this calibre seems to have rules that conspire together to make it appear 
impossible. What have I missed? 

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Rob Norris]

>
>(b) To support this call, Dequeue must be written as a function. As such, it 
>cannot change the protected queue. What I need is the "entry" functionality, 
>since I want the Dequeue to wait if the queue is empty, and I want the item 
>to be removed from the queue as well as retrieved.

Quick thought:
Is it possible to pass into the function a reference to the queue?
Then you should be able change the content of the queue as you see fit.

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Phil Slater]

"Rob Norris" <firstname.lastname@baesystems.com> wrote in message 
news:ilkp139uool31fc8opd7b94jpmctvndeg3@4ax.com...
> >
>>(b) To support this call, Dequeue must be written as a function. As such, 
>>it
>>cannot change the protected queue. What I need is the "entry" 
>>functionality,
>>since I want the Dequeue to wait if the queue is empty, and I want the 
>>item
>>to be removed from the queue as well as retrieved.
>
> Quick thought:
> Is it possible to pass into the function a reference to the queue?
> Then you should be able change the content of the queue as you see fit.
>

Maybe I didn't make myself clear. The queue is a protected object. None of 
the three types of protected operation (functions, procedures and entries), 
does what I need. I need the barrier/blocking of an entry, I need write 
access to change the protected data (the queue), but I also need the 
operation to *return* a value (like a function does) so that it can be 
received in calling code by using it to initialise a newly declared variable 
of a class-wide type. 

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Dmitry A. Kazakov]

On Wed, 11 Apr 2007 12:34:15 +0100, Phil Slater wrote:

> I've hit a brick wall. Every strategy I try doesn't work.
> 
> I need to write a generic package that exports a protected queue type that 
> will act as a buffer for objects of a class-wide type. My strategy is that 
> when objects join the queue they are copied onto the heap, and an 
> access-to-class-wide value is put onto the queue (could be array-based or 
> linked-list-based - I don't mind). To retrieve an item from the queue, an 
> access-to-class-wide value is removed from the queue, the heap object it 
> designates is copied onto the stack, the heap object is deallocated, then 
> the copy is returned.

> The crux of the problem goes like this:
> 
> (a) for the client code to retrieve an item, it needs to call a function; it 
> can't be done through a procedure or entry "out" parameter since I can't 
> declare an uninitialised variable of the class-wide type to pass as an 
> actual parameter. So the client code needs to do something like this:
>     declare
>         Next_In_Line : Item'class := My_Buffer.Dequeue;  -- My_Buffer is the 
> protected queue
> 
> (b) To support this call, Dequeue must be written as a function. As such, it 
> cannot change the protected queue. What I need is the "entry" functionality, 
> since I want the Dequeue to wait if the queue is empty, and I want the item 
> to be removed from the queue as well as retrieved.
> 
> (c) In a non-concurrent environment, I would simply write two separate 
> operations on the queue: a function Read_Next_Item and a procedure 
> Delete_Next_Item, which the client code would call in turn. However, that's 
> no good in a concurrent environment - two tasks could both call 
> Read_Next_Item before the first has had a chance to call Delete_Next_Item, 
> so the same item is read twice and the following item is skipped.
> 
> I really do want all the heap operations through the access-to-class-wide 
> type to be hidden away in the package - I did consider writing a protected 
> buffer with an entry whose out parameter was an access-to-class-wide type, 
> but this is highly unsatisfactory as it puts the onus for deallocating heap 
> space into the client code - very messy.
> 
> I cannot see a way through this problem, and am astounded that a language of 
> this calibre seems to have rules that conspire together to make it appear 
> impossible. What have I missed?

There are many ways to solve this.

1. You can wrap My_Buffer into a normal limited type. This will allow you
to have functions returning a class-wide:

   function Get_Next (Buffer : access My_Buffer_Interface)
      return Item'Class;

The implementation of Get_Next will go as follows:

function Get_Next (Buffer : access My_Buffer_Interface)
   return Item'Class is
   procedure Free is new Ada.Unchecked_Deallocation (Item, Item_Ptr);
   Ptr : Item_Ptr;
begin
   Buffer.Implementation.Get_Next (Ptr);
       -- Protected operation which takes pointer out of the buffer
       -- Buffer.Implementation is your protected queue
   declare -- In Ada 2005 it could be done better, I suppose
      This : Item'Class := Ptr.all;
   begin
      Free (Ptr);
      return This;
   end;
end Get_Next;

2. You use smart pointers to Item'Class instead of the items themselves. So
you will marshal only pointers through the queue and not the objects
themselves. This would reduce overhead of item's copying upon marshaling.
Deallocation will be handled by the smart pointer. Provided that items are
not accessed concurrently you will not need to interlock on pointer
dereferencing. Additional advantage is an ability to use limited items. [An
implementation of smart pointers can be found in Simple Components.]

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Jean-Pierre Rosen]

Phil Slater a �crit :
> I've hit a brick wall. Every strategy I try doesn't work.
> 
> I need to write a generic package that exports a protected queue type that 
> will act as a buffer for objects of a class-wide type.
[...]
Interesting question ;-)

It should be solvable by separating the buffer from the protection, i.e. 
keep a protected object just as a lock, and provide operations that take 
the lock, do whatever is needed (possibly with several calls), then 
release the lock. Don't forget to have a "when others" exception handler 
to release the lock in case of an unexpected exception.

This should be quite easy to do if the buffer is the package (i.e. an 
abstract state machine). If you need to make the buffer an abstract data 
type, you'll have to put the protected object as a component of the record.

-- 
---------------------------------------------------------
            J-P. Rosen (rosen@adalog.fr)
Visit Adalog's web site at http://www.adalog.fr

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[tmoran]

>  - I did consider writing a protected buffer with an entry whose out
> parameter was an access-to-class-wide type, but this is highly
> unsatisfactory as it puts the onus for deallocating heap space into the
> client code - very messy.

1. You need to use an entry with an out parameter that's an access type.
2. You don't want the user to have to deal with access types and
   deallocation.
Therefore you have to put some code between the user and the entry call.
3. You want the user to call a function that returns a class-wide type.
Therefore that in-between code should be a function that calls the
entry, copies the object from the heap to a temporary, deallocates the
heap space, and does a "return" of the temporary.
  For consistency, you probably want to hide the protected object in a
private type so the user never calls it directly, but all user calls
are to regular procedures or functions.

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Stephen Leake]

"Phil Slater" <phil.slater@baesystems.com> writes:

> "Rob Norris" <firstname.lastname@baesystems.com> wrote in message 
> news:ilkp139uool31fc8opd7b94jpmctvndeg3@4ax.com...
>> >
>>>(b) To support this call, Dequeue must be written as a function. As such, 
>>>it
>>>cannot change the protected queue. What I need is the "entry" 
>>>functionality,
>>>since I want the Dequeue to wait if the queue is empty, and I want the 
>>>item
>>>to be removed from the queue as well as retrieved.
>>
>> Quick thought:
>> Is it possible to pass into the function a reference to the queue?
>> Then you should be able change the content of the queue as you see fit.
>>
>
> Maybe I didn't make myself clear. The queue is a protected object. 

Instead of making the queue itself a protected object, use a separate
protected object as a lock for the queue.

That is not quite as safe, but it will work.

> None of the three types of protected operation (functions,
> procedures and entries), does what I need. I need the
> barrier/blocking of an entry, I need write access to change the
> protected data (the queue), but I also need the operation to
> *return* a value (like a function does) so that it can be received
> in calling code by using it to initialise a newly declared variable
> of a class-wide type.

You could have a function take an access type, and allocate the user
object in the protected call. But you may have reasons for not wanting
to do that.

-- 
-- Stephe

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Matthew Heaney]

On Apr 11, 6:34 am, "Phil Slater" <phil.sla...@baesystems.com> wrote:
> I've hit a brick wall. Every strategy I try doesn't work.

Won't the code below work?


> I need to write a generic package that exports a protected queue type that
> will act as a buffer for objects of a class-wide type.

That's fine.  You can declare the generic formal type as indefinite,
to make the package more general.

Note that I have used an Ada05 feature, extended return statement, to
return the class-wide object as the result of a function.  Is Ada05 is
not an option for you let me know and we'll figure something else out.


> My strategy is that
> when objects join the queue they are copied onto the heap,

Yes, that's what the solution below does.


> and an
> access-to-class-wide value is put onto the queue (could be array-based or
> linked-list-based - I don't mind).

I have created an internal buffer, implemented using the doubly-linked
list standard container, instantiated with an access type as the
generic actual.


> To retrieve an item from the queue, an
> access-to-class-wide value is removed from the queue, the heap object it
> designates is copied onto the stack, the heap object is deallocated, then
> the copy is returned.

Yes, the example below does that.


> The crux of the problem goes like this:
>
> (a) for the client code to retrieve an item, it needs to call a function; it
> can't be done through a procedure or entry "out" parameter since I can't
> declare an uninitialised variable of the class-wide type to pass as an
> actual parameter. So the client code needs to do something like this:
>     declare
>         Next_In_Line : Item'class := My_Buffer.Dequeue;  -- My_Buffer is the
> protected queue

The problem you're having is mixing layers of abstraction.  The queue
type below does indeed have a Deque function, and there is a
proctected object, but the protected object itself is an
implementation detail of the queue abstract data type.



> (b) To support this call, Dequeue must be written as a function. As such, it
> cannot change the protected queue. What I need is the "entry" functionality,
> since I want the Dequeue to wait if the queue is empty, and I want the item
> to be removed from the queue as well as retrieved.

Yes, you can do that, but you need two separate steps: the first step
is to use an entry (with a barrier) to remove the front item from the
queue's internal buffer (that's the protected object part), and then
return the value you removed from the internal buffer to the caller,
via a function (that's the abstract data type part).

In the example below I have used an extended return, since the return
type is indefinite.


> I cannot see a way through this problem, and am astounded that a language of
> this calibre seems to have rules that conspire together to make it appear
> impossible. What have I missed?

Use the Source, Luke!

--STX
private with Ada.Containers.Doubly_Linked_Lists;

generic
   type ET (<>) is private;

package Queues is

   type QT is limited private;

   function Deque (Q : not null access QT) return ET;

   procedure Enque (Q : in out QT; E : ET);

private

   type ET_Access is access ET;

   use Ada.Containers;
   package ET_Lists is new Doubly_Linked_Lists (ET_Access);

   protected type BT is
      entry Get (Obj : out ET_Access);
      procedure Put (Obj : ET_Access);
   private
      L : ET_Lists.List;
   end BT;

   type QT is limited record
     B : BT;
   end record;

end Queues;


with Ada.Unchecked_Deallocation;

package body Queues is

   procedure Free is new Ada.Unchecked_Deallocation (ET, ET_Access);

   protected body BT is

      entry Get (Obj : out ET_Access) when not L.Is_Empty is
      begin
         Obj := L.First_Element;
         L.Delete_First;
      end;

      procedure Put (Obj : ET_Access) is
      begin
         L.Append (Obj);
      end;

   end BT;

   function Deque (Q : not null access QT) return ET is
      Obj : ET_Access;

   begin
      Q.B.Get (Obj);

      return E : ET := Obj.all do
        Free (Obj);
      end return;
   end Deque;


   procedure Enque (Q : in out QT; E : ET) is
   begin
      Q.B.Put (ET_Access'(new ET'(E)));
   end;


end Queues;


Regards,
Matt

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Matthew Heaney]

On Apr 13, 1:02 pm, "Matthew Heaney" <mhea...@on2.com> wrote:
> On Apr 11, 6:34 am, "Phil Slater" <phil.sla...@baesystems.com> wrote:
>
> > I've hit a brick wall. Every strategy I try doesn't work.

I probably should have pointed out that I my previous post, the Deque
function is implemented this way:

  function Deque (Q : not null access QT) return ET;

This will necessitate declaring queue objects as aliased, and then
using taking the 'Access of the object:

declare
  Q : aliased QT;
begin
  ...
  declare
     E : ET := Deque (Q'Access);
  begin
    ...
  end;
...
end;


If you don't like the syntactic overhead, there are a couple of things
you can do.  First is to declare the queue type as tagged:

  type QT is tagged limited private;

Ada05 allows you do use distinguished-receiver syntax, and will do an
implicit dereference is the object is aliased (or implicitly aliased),
e.g.

declare
  Q : aliased QT;  -- QT is tagged; explicitly aliased
begin
  ...
  declare
     E : ET := Q.Deque;
  begin
    ...
  end;
...
end;

--or--

procedure Op (Q : in out QT) is  -- implicitly aliased
begin
  ...
  declare
     E : ET := Q.Deque;
  begin
    ...
  end;
...
end Op;


So taggedness is one option.  Another option is to use the Rosen
Trick, which allows a function to modify its parameter, if it's a by-
reference type.  (Types whose full view is limited qualify, so we're
eligible.)  That allows us to declare the deque function like this:

  function Deque (Q : QT) return ET;

In the implementation of the QT, we simply need to add another
component:

private

  type HT (Q : not null access QT) is limited null record;
 ...
  type QT is limited record
     H : HT (QT'Access);
     B : BT;
  end record;

end Queues;

Now we just need to make a small change to the implementation of our
deque function:

   function Deque (Q : QT) return ET is
      Obj : ET_Access;

   begin
      Q.H.Q.B.Get (Obj);  -- manipulate buffer via handle (Rosen
Trick)

      return E : ET := Obj.all do
        Free (Obj);
      end return;
   end Deque;

Here I didn't bother making the queue type tagged, but if you like
distinguished-receiver syntax, then you can do that too.

Regards,
Matt

P.S. I'll be giving a tutorial in Geneva at the end of June, to
discuss these sorts of techniques.

Re: Impossible problem? A protected buffer to queue objects of a class-wide type

[Ed Falis]

Very elegant, Matt.