* Impossible problem? A protected buffer to queue objects of a class-wide type
@ 2007-04-11 11:34 Phil Slater
2007-04-11 12:25 ` Rob Norris
` (4 more replies)
0 siblings, 5 replies; 10+ messages in thread
From: Phil Slater @ 2007-04-11 11:34 UTC (permalink / raw)
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?
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-11 11:34 Impossible problem? A protected buffer to queue objects of a class-wide type Phil Slater
@ 2007-04-11 12:25 ` Rob Norris
2007-04-11 13:02 ` Phil Slater
2007-04-11 13:14 ` Dmitry A. Kazakov
` (3 subsequent siblings)
4 siblings, 1 reply; 10+ messages in thread
From: Rob Norris @ 2007-04-11 12:25 UTC (permalink / raw)
>
>(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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-11 12:25 ` Rob Norris
@ 2007-04-11 13:02 ` Phil Slater
2007-04-12 8:36 ` Stephen Leake
0 siblings, 1 reply; 10+ messages in thread
From: Phil Slater @ 2007-04-11 13:02 UTC (permalink / raw)
"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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-11 11:34 Impossible problem? A protected buffer to queue objects of a class-wide type Phil Slater
2007-04-11 12:25 ` Rob Norris
@ 2007-04-11 13:14 ` Dmitry A. Kazakov
2007-04-11 14:01 ` Jean-Pierre Rosen
` (2 subsequent siblings)
4 siblings, 0 replies; 10+ messages in thread
From: Dmitry A. Kazakov @ 2007-04-11 13:14 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-11 11:34 Impossible problem? A protected buffer to queue objects of a class-wide type Phil Slater
2007-04-11 12:25 ` Rob Norris
2007-04-11 13:14 ` Dmitry A. Kazakov
@ 2007-04-11 14:01 ` Jean-Pierre Rosen
2007-04-11 17:18 ` tmoran
2007-04-13 17:02 ` Matthew Heaney
4 siblings, 0 replies; 10+ messages in thread
From: Jean-Pierre Rosen @ 2007-04-11 14:01 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-11 11:34 Impossible problem? A protected buffer to queue objects of a class-wide type Phil Slater
` (2 preceding siblings ...)
2007-04-11 14:01 ` Jean-Pierre Rosen
@ 2007-04-11 17:18 ` tmoran
2007-04-13 17:02 ` Matthew Heaney
4 siblings, 0 replies; 10+ messages in thread
From: tmoran @ 2007-04-11 17:18 UTC (permalink / raw)
> - 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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-11 13:02 ` Phil Slater
@ 2007-04-12 8:36 ` Stephen Leake
0 siblings, 0 replies; 10+ messages in thread
From: Stephen Leake @ 2007-04-12 8:36 UTC (permalink / raw)
"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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-11 11:34 Impossible problem? A protected buffer to queue objects of a class-wide type Phil Slater
` (3 preceding siblings ...)
2007-04-11 17:18 ` tmoran
@ 2007-04-13 17:02 ` Matthew Heaney
2007-04-13 17:26 ` Matthew Heaney
2007-04-13 17:36 ` Ed Falis
4 siblings, 2 replies; 10+ messages in thread
From: Matthew Heaney @ 2007-04-13 17:02 UTC (permalink / raw)
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
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-13 17:02 ` Matthew Heaney
@ 2007-04-13 17:26 ` Matthew Heaney
2007-04-13 17:36 ` Ed Falis
1 sibling, 0 replies; 10+ messages in thread
From: Matthew Heaney @ 2007-04-13 17:26 UTC (permalink / raw)
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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: Impossible problem? A protected buffer to queue objects of a class-wide type
2007-04-13 17:02 ` Matthew Heaney
2007-04-13 17:26 ` Matthew Heaney
@ 2007-04-13 17:36 ` Ed Falis
1 sibling, 0 replies; 10+ messages in thread
From: Ed Falis @ 2007-04-13 17:36 UTC (permalink / raw)
Very elegant, Matt.
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2007-04-13 17:36 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-04-11 11:34 Impossible problem? A protected buffer to queue objects of a class-wide type Phil Slater
2007-04-11 12:25 ` Rob Norris
2007-04-11 13:02 ` Phil Slater
2007-04-12 8:36 ` Stephen Leake
2007-04-11 13:14 ` Dmitry A. Kazakov
2007-04-11 14:01 ` Jean-Pierre Rosen
2007-04-11 17:18 ` tmoran
2007-04-13 17:02 ` Matthew Heaney
2007-04-13 17:26 ` Matthew Heaney
2007-04-13 17:36 ` Ed Falis
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox