From: jeltsch@my-deja.com
Subject: Containers with Ada
Date: 2000/11/19
Date: 2000-11-19T00:00:00+00:00 [thread overview]
Message-ID: <8v8pii$dvo$1@nnrp1.deja.com> (raw)
Hello Ada programmers,
I want to write some generic packages for container types - at the moment for
several kinds of lists. At the beginning of this work I thought this wouldn't
be that difficult but now after being faced with a lots of problems I
sometimes wonder if I should go back to C++.
Below I will present some of the difficulties. I would be very pleased if
someone could help me creating problem-oriented packages for containers which
use the advantages of Ada. I hardly can imagine that there are no really good
container implementations in Ada at the moment so there must be a solution.
Now the problems in detail:
1. Copying of large data structures
In my opinion one main problem of Ada is implicit copying of variables. So
it's no good idea to define such a intuitive function like
function Element_At(Current_List : in List; Current_Index : in Index)
return Element;
In this example the list which could contain thousands of elements would
be copied just to get one element out of it. In addition if Element is also
a list the return statement inside Element_At would copy this list.
A first solution could be to define List as limited. But this would be bad
if Element is non-limited because in this case it would make sense to copy
lists and to check them for equality. Moreover Element would have to be
definded as limited to allow lists of lists.
One could also totally avoid "normal" list parameters and use only access
parameters for lists. But that would mean that every list would have to be
aliased and that no constant parameters could be used because acces
parameters cannot be constant.
I took the first solution - defining lists limited and having limited
element types. This has also advantages because lists with other limited
element types become possible. But there are still problems of accessing
list elements as explained in the next section.
2. Complicated use of element access with generic procedures
Accessing a limited element of a limited list which is not visible from
outside the package is as far as I can see only possible in two ways - via
an access value to the element returned by some package subprogram or by a
generic subprogram as explained below. The first way is in my eyes
inacceptable because the access type needed would have to be defined at the
level of the list package instance which would the package user allow to
have "dangling pointers".
The approach I have taken is to define some generic procedures which have a
a procedure as generic parameter. Here are those procedures:
generic
with procedure Edit_Single_Element(Current_Element : in out Element);
procedure Edit_Element(Current_List : in out List;
Current_Index : in Index);
generic
with procedure Read_Single_Element(Current_Element : in out Element);
procedure Read_Element(Current_List : in List;
Current_Index : in Index);
An instance of Edit_Element or Read_Element will call Edit_Single_Element
or Read_Single_Element respectively on the element of Current_List denoted
by Current_Index. That seems to work just fine but it is very complicated
to use. The following example for instance just copies the elements of
Source_List to Dest_List.
for Current_Index in Index range Start .. End loop
declare
procedure Using_Dest_Element(Dest_Element : in out Element) is
procedure Using_Source_Element(Source_Element : in Element) is
begin
Dest_Element := Source_Element;
end Using_Source_Element;
procedure Using_Source_List is
new Read_Element(Using_Source_Element);
begin
Using_Source_List(Source_List, Current_Element);
end Using_Dest_Element;
procedure Using_Dest_List is
new Edit_Element(Using_Dest_Element);
begin
Using_Dest_List(Dest_List, Current_Index)
end;
end loop;
In comparison the same problem with arrays:
for Current_Index in Index range Start .. End loop
Dest_Array(Current_Index) := Source_Array(Current_Index);
end loop;
or just
Dest_Array(Start .. End) := Source_Array(Start .. End);
3. High memory consumption with unconstrained arrays
An easy way to define a type for lists with fixed length would be for
instance
type Element_Array is array(Positive range <>) of Element;
type List(Length : Natural) is record
Elements : Element_Array(1 .. Length);
end record;
With this implementation one could even think of making the whole type
definition public. But one cannot expect that a compiler will generate code
that dynamically allocates memory that is just enough for Elements. As I
can see GNAT doesn't operate with implicit pointers to dynamically
allocated memory but sets the size of List so that it is big enough for
every value for Length. In the above example that means that every List
would (try to) consume about 2 GB of memory on my platform.
4. Limitations with controlled types
Because I cannot use unconstrained arrays like in the above example I use
pointers to arrays (access values). A good implementation should free all
memory consumed by the list when the list ceases to exist. List should
therefore be derived from Limited_Controlled an have a Finalize procedure
which deallocates the element array(s). But controlled types can be only
defined at the library level. So the following example is not possible
which is inacceptable for me:
procedure Act(Limit : in Natural) is
subtype My_Range is Natural range 1 .. Limit;
package My_Lists is new Lists(My_Range);
begin
...
end Act;
Bye, Wolfgang
Sent via Deja.com http://www.deja.com/
Before you buy.
next reply other threads:[~2000-11-19 0:00 UTC|newest]
Thread overview: 25+ messages / expand[flat|nested] mbox.gz Atom feed top
2000-11-19 0:00 jeltsch [this message]
2000-11-19 0:00 ` Containers with Ada Robert Dewar
2000-11-19 0:00 ` Ken Garlington
2000-11-20 0:00 ` Wolfgang Jeltsch
2000-11-20 0:00 ` Wolfgang Jeltsch
2000-11-19 0:00 ` Robert Dewar
2000-11-20 0:00 ` Wolfgang Jeltsch
2000-11-19 0:00 ` Robert Dewar
2000-11-19 0:00 ` Robert Dewar
2000-11-20 4:37 ` Brian Rogoff
2000-11-20 0:00 ` Ted Dennison
2000-11-20 0:00 ` Brian Rogoff
2000-11-20 0:00 ` Marc A. Criley
2000-11-20 0:00 ` Brian Rogoff
2000-11-20 0:00 ` Stephen Leake
2000-11-20 0:00 ` Brian Rogoff
2000-11-21 0:00 ` Warren W. Gay VE3WWG
2000-11-21 0:00 ` Stephen Leake
2000-11-21 0:00 ` Warren W. Gay VE3WWG
2000-11-21 0:00 ` Stephen Leake
2000-11-22 0:00 ` Warren W. Gay VE3WWG
2000-11-22 0:00 ` Containers with Ada (distribution of) Warren W. Gay VE3WWG
[not found] ` <004d01c0567b$cd4e49c0$b0375140@Fudge>
2000-11-25 0:00 ` Does anyone use Anna? Lao Xiao Hai
2000-11-21 0:00 ` Containers with Ada Marc A. Criley
2000-11-20 0:00 ` Wolfgang Jeltsch
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox