Unbounded array

Unbounded array

[Pawel Kobylarz]

I need a data structure that can contain varying amount of items and
provide fast access
through Index.


List has too long access, map is I think too complicated for just a
range of indexes.
I have not found just unbounded array, so maybe it is even too easy to
mention anywhere
or write a special package for it.


In C language, I can declare an array...

      item_type *item_array;

... allocate it in program...

      item_array = alloc(item_size * amount);

... and later change its size:

      item_array = realloc(item_size * new_amount);


Is there in ADA a way to obtain something like unbouned array?

Pawel Kobylarz

Re: Unbounded array

[Robert Dewar]

In article
<37247AA2.116F5E00@wbkst21.mach.uni-karlsruhe.de>,
  kobylarz@wbkst21.mach.uni-karlsruhe.de wrote:
> Is there in ADA a way to obtain something like unbouned
> array?


Well most certainly you can use EXACTLY the same procedure
you use in C (lookup allocators and the NEW keyword in your
Ada text book).

But if you are using GNAT, also look up GNAT.Table (in file
g-table.ads) which provides exactly the abstraction you are
looking for.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Unbounded array

[Pawel Kobylarz]

Robert Dewar wrote:

> In article
> <37247AA2.116F5E00@wbkst21.mach.uni-karlsruhe.de>,
>   kobylarz@wbkst21.mach.uni-karlsruhe.de wrote:
> > Is there in ADA a way to obtain something like unbouned
> > array?
>
> Well most certainly you can use EXACTLY the same procedure
> you use in C (lookup allocators and the NEW keyword in your
> Ada text book).
>
> But if you are using GNAT, also look up GNAT.Table (in file
> g-table.ads) which provides exactly the abstraction you are
> looking for.
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


Maybe my textbook is incomplete, maybe there was a misunderstanding
because
I gave wrong description of realloc function.

Using new and unchecked_deallocation, I can change the size of array
by allocating new array, copy the objects and deallocate the old one.
This is not efficient.

Realloc function takes two parameters, the actual pointer and new size,
and
it preserves the data already present in the memory block.
Realloc is more efficient than allocate-copy-deallocate,
because it can add a piece of memory without moving existing data
if there is place after the existing block.

In my textbook, I found only operators new and unchecked deallocation,
nothing similar to realloc(). Is there in ADA something like
realloc?

Pawel Kobylarz

Re: Unbounded array

[Matthew Heaney]

Pawel Kobylarz <kobylarz@wbkst21.mach.uni-karlsruhe.de> writes:

> In my textbook, I found only operators new and unchecked deallocation,
> nothing similar to realloc(). Is there in ADA something like
> realloc?

No, but you can just write a binding to C realloc from Ada.  

Re: Unbounded array

[Matthew Heaney]

Pawel Kobylarz <kobylarz@wbkst21.mach.uni-karlsruhe.de> writes:

> Realloc function takes two parameters, the actual pointer and new
> size, and it preserves the data already present in the memory block.
> Realloc is more efficient than allocate-copy-deallocate, because it
> can add a piece of memory without moving existing data if there is
> place after the existing block.

But that isn't guaranteed.  You save the cost of a copy only if there's
an adjacent block large enough to contain the new part of the array.


> In my textbook, I found only operators new and unchecked deallocation,
> nothing similar to realloc(). Is there in ADA something like
> realloc?

No, it is not built in.  However, you could

1) write a binding the C function

2) write your own storage pool that supports a realloc-style operation,
   and bind your access type to that pool; see RM95 13.11

There are open-source implementations of malloc, etc, so you should be
able to use the algorithm to implement an Ada95 version.

Re: Unbounded array

[dennison]

In article <m3g15krlw5.fsf@mheaney.ni.net>,
  Matthew Heaney <matthew_heaney@acm.org> wrote:
> Pawel Kobylarz <kobylarz@wbkst21.mach.uni-karlsruhe.de> writes:
>
> > Realloc function takes two parameters, the actual pointer and new
> > size, and it preserves the data already present in the memory block.
> > Realloc is more efficient than allocate-copy-deallocate, because it
> > can add a piece of memory without moving existing data if there is
> > place after the existing block.
>
> But that isn't guaranteed.  You save the cost of a copy only if there's
> an adjacent block large enough to contain the new part of the array.

I wouldn't be suprised if it didn't *always* do the copy on some platforms.
If if it does try to extend, unless the malloc algorithm is specificly
optimized to leave holes for realloc, most of the time its probably going to
have to copy anyway.

> > In my textbook, I found only operators new and unchecked deallocation,
> > nothing similar to realloc(). Is there in ADA something like
> > realloc?
>
> No, it is not built in.  However, you could
>
> 1) write a binding the C function

It should be noted that if you do this, you should also write bindings to
malloc or calloc and free, and you should use those calls rather than Ada's
"new" and Unchecked_Deallocation. "new" is not guaranteed to be a straight
call to malloc, so you could seriously hose things by trying to mix Ada and C
allocations and deallocations.

>
> 2) write your own storage pool that supports a realloc-style operation,
>    and bind your access type to that pool; see RM95 13.11

That's probably the *best* solution. But of course it is also the most work
and trickiest to implement correctly.

Of course there's a third possibility:

 3) Write a "Realloc (Ptr : in out ..." for your specific access type and do
the "new", copy, and "Unchecked_Deallocation" in its body. If all Pawel was
looking for was the convienence of doing that in one operation, this is
probably the best way.

--
T.E.D.

-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own    

Re: Unbounded array

[Pawel Kobylarz]

Robert Dewar wrote:

> In article
> <37247AA2.116F5E00@wbkst21.mach.uni-karlsruhe.de>,
>   kobylarz@wbkst21.mach.uni-karlsruhe.de wrote:
> > Is there in ADA a way to obtain something like unbouned
> > array?
>
> Well most certainly you can use EXACTLY the same procedure
> you use in C (lookup allocators and the NEW keyword in your
> Ada text book).
>
> But if you are using GNAT, also look up GNAT.Table (in file
> g-table.ads) which provides exactly the abstraction you are
> looking for.
>
> -----------== Posted via Deja News, The Discussion Network ==----------
> http://www.dejanews.com/       Search, Read, Discuss, or Start Your Own


The GNAT.table does not seem to work correctly, and there is also
something strange in the
definition.


Let's suppose I want to enlarge the table. Here are two definitions from
the
g-table.ads file:


   procedure Set_Last (New_Val : Table_Index_Type);
   pragma Inline (Set_Last);
   --  This procedure sets Last to the indicated value. If necessary the
   --  table is reallocated to accomodate the new value (i.e. on return
   --  the allocated table has an upper bound of at least Last). If
Set_Last
   --  reduces the size of the table, then logically entries are removed
   --  from the table. If Set_Last increases the size of the table, then
   --  new entries are logically added to the table.

   procedure Increment_Last;
   pragma Inline (Increment_Last);
   --  Adds 1 to Last (same as Set_Last (Last + 1).




The strange thing is that the functions does not take object as a
parameter.
They cannot be called like
                   table'Increment_Last;
            or
                   table.Increment_Last;
            or
                   Increment_Last(table);
there are compilation erros.

However, line like:
                          Increment_Last;
does compile!
The question is: if I have two object of that class and want to resize one
of them,
how should I call it?

I was also curious what is the effect of the function. I wrote


type My_Type is
  record
     ...
   end record;

subtype My_Idx_Type is Integer;

package t_mytype is new Gnat.Table(My_Type, My_Idx_Type, 1, 1, 10);
table : t_mytype.Table_Ptr;

begin
      loop
          Put_Line("before...");
          Increment_Last;
          Put_Line("after!");
     end loop
end;




and I obtained
        before...
        after!
        before...
and the program hanged in this place.

Seemingly the function does not work and I cannot even imagine, how can it
work without
taking object as a parameter.
Any suggestions?

Pawel Kobylarz