Re: How Ada could have prevented the Red Code distributed denial of service attack.

Re: How Ada could have prevented the Red Code distributed denial of service attack.

[Gautier Write-only-address]

> > Windows 98 ... a success of the pointer-to-buffer macro-assemblers.

>Please don't blame assembler for Win98.  And there is nothing wrong
>about using pointers to buffers.  The trouble starts when you misuse
>them.

I don't blame assembler (it is of course necessary in some parts,
and generally carefully programmed), but over-used macro-assembler.
At a certain scale in a project one should have a rich typing, e.g.
arrays - the true ones, with bounds.

G.



_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp

Ada and pointers

[Tony Gair]

>> > Windows 98 ... a success of the pointer-to-buffer macro-assemblers.
> 
>>Please don't blame assembler for Win98.  And there is nothing wrong
>>about using pointers to buffers.  The trouble starts when you misuse
>>them.
> 

Pointers however are non-trivial and all programmers do not write perfect 
code all the time. This is one the reasons that ada is successful I 
believe, because it is possible to have as near as perfect code in a 
re-used package (especally that avl-tree-generic package) then reuse it in 
non-pointer code.



> I don't blame assembler (it is of course necessary in some parts,
> and generally carefully programmed), but over-used macro-assembler.
> At a certain scale in a project one should have a rich typing, e.g.
> arrays - the true ones, with bounds.
> 
> G.
> 

I think Ada is currently the best open source language of code because of 
this factor and information hiding..

Incidently I heard a statement by a colleague ten years ago saying pointers 
are not actually necessary in any construction of code no-matter the 
purpose because it had been mathematically proven so". A very strong 
statement.... has anyone heard of this or was it hot air,

Regards
Tony Gair

Re: Ada and pointers

[Hambut]

Tony Gair <tony@blueyonder.co.uk> wrote in message news:<1ope7.5943$6R6.582900@news1.cableinet.net>...

<snip>

> Incidently I heard a statement by a colleague ten years ago saying pointers 
> are not actually necessary in any construction of code no-matter the 
> purpose because it had been mathematically proven so". A very strong 
> statement.... has anyone heard of this or was it hot air,
> 

Seems a bit too strong.  It strikes me that explicitly getting rid of
pointers (or access types) would just move the problems elsewhere..
you'd still have all the nasty keeping track of references issues,
they'd just be transposed to, say, an array construct.

Re: Ada and pointers

[Jonathan DeSena]

Marin David Condic wrote:

> Well, the statement is true enough because after all, dynamic allocation
> and the things done by pointers are really a kind of fiction. Memory is
> basically one big array that you index with integers, so obviously, a
> non-dynamic/non-pointer solution must exist. Anything you do with pointers
> could be implemented with a one dimensional array and integer indexes -
> because that's what the compiler translates it into.
> 
> However, that doesn't mean that one should avoid access types in all
> cases. Sometimes it is the most natural expression of the solution. Its
> just that you should generally use them sparingly and isolate them as best
> you can. Ada lets you do this rather well. (Some OOP-style programming
> relies heavily on access types so you've got to make design trade offs -
> use the OOP for its benefits at the risk of having lots more pointers
> flying around or avoid/isolate the pointers and implement a solution that
> may not be as extensible.) Access types aren't a "bad" thing - you just
> don't want to be forced into using them at every conceivable turn as you
> must in C/C++.
> 
> MDC
> --

Also note that there are some circumstances in which an access type is 
effectively required. Cohen's "Ada as a Second Language" lists several in 
section 8.5 I believe. As an Ada newbie, I have already run across a few of 
these situations, namely: recursive types and variable sized arrays (or to 
paraphrase Cohen, "simulating variable sized arrays." I suppose I could 
have framed the solution differently to avoid these cases, but frankly, I'm 
not exactly sure how.

As an aside, I have had some limited experience with FORTRAN code which 
uses a giant array with many integer index pointers into it. It even has 
its own memory management of this array, of sorts. I must say that trying 
to follow this code is no fun at all, even though it is heavily documented. 
It seems to me, the original coders of many years ago could really have 
used a language like Ada95.

jtd

Re: Ada and pointers

[Marin David Condic]

Well, the statement is true enough because after all, dynamic allocation and
the things done by pointers are really a kind of fiction. Memory is
basically one big array that you index with integers, so obviously, a
non-dynamic/non-pointer solution must exist. Anything you do with pointers
could be implemented with a one dimensional array and integer indexes -
because that's what the compiler translates it into.

However, that doesn't mean that one should avoid access types in all cases.
Sometimes it is the most natural expression of the solution. Its just that
you should generally use them sparingly and isolate them as best you can.
Ada lets you do this rather well. (Some OOP-style programming relies heavily
on access types so you've got to make design trade offs - use the OOP for
its benefits at the risk of having lots more pointers flying around or
avoid/isolate the pointers and implement a solution that may not be as
extensible.) Access types aren't a "bad" thing - you just don't want to be
forced into using them at every conceivable turn as you must in C/C++.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Hambut" <hfrumblefoot@yahoo.com> wrote in message
news:fb75c450.0108150449.11fe4c74@posting.google.com...
> Tony Gair <tony@blueyonder.co.uk> wrote in message
news:<1ope7.5943$6R6.582900@news1.cableinet.net>...
>
> <snip>
>
> > Incidently I heard a statement by a colleague ten years ago saying
pointers
> > are not actually necessary in any construction of code no-matter the
> > purpose because it had been mathematically proven so". A very strong
> > statement.... has anyone heard of this or was it hot air,
> >
>
> Seems a bit too strong.  It strikes me that explicitly getting rid of
> pointers (or access types) would just move the problems elsewhere..
> you'd still have all the nasty keeping track of references issues,
> they'd just be transposed to, say, an array construct.

Re: Ada and pointers

[Ted Dennison]

In article <1ope7.5943$6R6.582900@news1.cableinet.net>, Tony Gair says...
>Incidently I heard a statement by a colleague ten years ago saying pointers 
>are not actually necessary in any construction of code no-matter the 
>purpose because it had been mathematically proven so". A very strong 
>statement.... has anyone heard of this or was it hot air,

Well, it is quite possible to do anything one does with pointers with arrays and
array indexes instead. Fortran coders have been doing this for decades. With a
bit of work, you could even make your own heap and dynamic memory allocation
manager this way. But at some point you get to where you are just using pointers
by another name...

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: Ada and pointers

[James Rogers]

Marin David Condic wrote:
> 
> Well, the statement is true enough because after all, dynamic allocation and
> the things done by pointers are really a kind of fiction. Memory is
> basically one big array that you index with integers, so obviously, a
> non-dynamic/non-pointer solution must exist. Anything you do with pointers
> could be implemented with a one dimensional array and integer indexes -
> because that's what the compiler translates it into.
> 

On many machines memory is one big array. This is not exactly true for
the old Intel machines that use a segmented memory model. In this case
memory is more like an array of arrays than a simple array.

Jim Rogers
Colorado Springs, Colorado USA

Re: Ada and pointers

[Warren W. Gay VE3WWG]

Hambut wrote:
> Tony Gair <tony@blueyonder.co.uk> wrote in message news:<1ope7.5943$6R6.582900@news1.cableinet.net>...
> 
> <snip>
> 
> > Incidently I heard a statement by a colleague ten years ago saying pointers
> > are not actually necessary in any construction of code no-matter the
> > purpose because it had been mathematically proven so". A very strong
> > statement.... has anyone heard of this or was it hot air,
> >
> 
> Seems a bit too strong.  It strikes me that explicitly getting rid of
> pointers (or access types) would just move the problems elsewhere..
> you'd still have all the nasty keeping track of references issues,
> they'd just be transposed to, say, an array construct.

I agree. Whether they be "pointers", "references" or "subscripts", you
can still mis-manage them. Though "smart references" that keep track
of references to an object (as in Java) can improve your success rate ;-)

However, if you must use pointers, then I think that eliminating pointer
arithmetic eleminates an entire class of problems. Having array bounds
checked, compliments this very well.

As someone else pointed out, you can implement heaps in arrays etc. (this
is why "subscripts" can be a problem). If you manage your heap in an array,
the subscript becomes a pointer in effect, which can then allow the 
programmer step on other array elements in that array, thus affecting 
a different form of corruption.

-- 
Warren W. Gay VE3WWG
http://members.home.net/ve3wwg

Re: Ada and pointers

[Marin David Condic]

True enough - and I did think about that case. But when you consider it for
a minute and you realize that NNNN(segment) and NNNN(offset) are really no
different than NNNN-NNNN (some integer) - then it is still a one dimensional
array. Not unlike describing "the ones digit" and "the tens digit", etc.

Segment/Offset was invented to enable bringing older architectures forward
into larger address spaces and to possibly conserve some space and/or bus
cycles. Its still just an integer.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"James Rogers" <jimmaureenrogers@worldnet.att.net> wrote in message
news:3B7A9D94.F34F65E@worldnet.att.net...
>
> On many machines memory is one big array. This is not exactly true for
> the old Intel machines that use a segmented memory model. In this case
> memory is more like an array of arrays than a simple array.
>

Re: Ada and pointers

[Hambut]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:<9ldto7$9pg$1@nh.pace.co.uk>...
> Well, the statement is true enough because after all, dynamic allocation and
> the things done by pointers are really a kind of fiction. Memory is
> basically one big array that you index with integers, so obviously, a
> non-dynamic/non-pointer solution must exist. Anything you do with pointers
> could be implemented with a one dimensional array and integer indexes -
> because that's what the compiler translates it into.
> 

Well the statement that pointers can be mimic-ed through other
mechanisms is certainly true enough, and I agree with your other
points but........

I was thinking about the dynamic allocation aspects - if you can't or
don't want to bound the memory used then it becomes difficult to see
how you could work without dynamic memory allocation (which is,
admittedly, not precisely related to pointers - but they provide a
popular way of getting access to dynamically allocated memory).

Of course this is all fairly non-specific, but in terms of a formal
mathematical proof - well (and here's a leap into the unknown coupled
with thinking aloud, so feel free to flame the rest of this...)
wouldn't this mean that you'd somehow have to prove that all
algorithms had bounded memory use?  This seems a hard thing to do (and
I'm not precisely sure this would completely prove that pointers can
be disregarded - for example what about alias-ing capabilities?)

That said I agree that in a practical sense you can probably do
without pointers, albeit with some effort and discomfort.

Cheers,

Hambut

Re: Ada and pointers

[James Rogers]

Marin David Condic wrote:
> 
> True enough - and I did think about that case. But when you consider it for
> a minute and you realize that NNNN(segment) and NNNN(offset) are really no
> different than NNNN-NNNN (some integer) - then it is still a one dimensional
> array. Not unlike describing "the ones digit" and "the tens digit", etc.
> 
> Segment/Offset was invented to enable bringing older architectures forward
> into larger address spaces and to possibly conserve some space and/or bus
> cycles. Its still just an integer.
> 
>> "James Rogers" <jimmaureenrogers@worldnet.att.net> wrote in message
> news:3B7A9D94.F34F65E@worldnet.att.net...
> >
> > On many machines memory is one big array. This is not exactly true for
> > the old Intel machines that use a segmented memory model. In this case
> > memory is more like an array of arrays than a simple array.
> >

Sometimes this is correct. Some systems do have the ability to use
both linear addressing and segment-offset addressing. Some of the
older systems do not have any ability to support linear addressing.
This is one reason the type System.Address is implementation defined.
System.Address also has comparison functions, but is not an aritmetic
type. It does have addition, subtraction, and modulus operations
defined in System.Storage_Elements, but that does not make
System.Address a numeric type.

Note that there is a type called
System.Storage_Elements.Integer_Address.
This type is not a System.Address, but does provide conversion
functions to and from System.Address.

Ada provides, through these types, conversions between linear and
segmented memory models, even if those conversions are not directly
supported by the hardware memory model.

Jim Rogers
Colorado Springs, Colorado USA

Re: Ada and pointers

[Marin David Condic]

I suppose that my logical explanation doesn't necessarily cover the same
territory as mathematical proof. Obviously not all algorithms have bounded
memory use - try to compute Pi to the last digit - you'll run out of memory
before you get there. I'm not sure if thats what you mean.

From just a logical perspective: All computers in the known universe have a
finite quantity of memory. Hence all dynamic allocation, on all known, real
world computers is a fiction built on top of a static allocation that is
determined at computer-build time. So I'd suggest that it stands to reason
that if you have a dynamic algorithm that actually runs and computes a
solution on some real world computer, then there must be a static allocation
solution that will run on that same computer.

Now maybe we should spend some time figuring out how to trisect an angle? It
beats chasing down C program bugs which is what I have on the agenda for
this afternoon... :-)

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Hambut" <hfrumblefoot@yahoo.com> wrote in message
news:fb75c450.0108151054.74fdfc5@posting.google.com...
>
> Well the statement that pointers can be mimic-ed through other
> mechanisms is certainly true enough, and I agree with your other
> points but........
>
> I was thinking about the dynamic allocation aspects - if you can't or
> don't want to bound the memory used then it becomes difficult to see
> how you could work without dynamic memory allocation (which is,
> admittedly, not precisely related to pointers - but they provide a
> popular way of getting access to dynamically allocated memory).
>
> Of course this is all fairly non-specific, but in terms of a formal
> mathematical proof - well (and here's a leap into the unknown coupled
> with thinking aloud, so feel free to flame the rest of this...)
> wouldn't this mean that you'd somehow have to prove that all
> algorithms had bounded memory use?  This seems a hard thing to do (and
> I'm not precisely sure this would completely prove that pointers can
> be disregarded - for example what about alias-ing capabilities?)
>
> That said I agree that in a practical sense you can probably do
> without pointers, albeit with some effort and discomfort.
>

Re: Ada and pointers

[Marin David Condic]

Well, I wasn't exactly making the claim that all segmented hardware can
address linearly. I was making the claim that for purposes of
conceptualizing memory that all memory could be viewed as a single
dimensional array with an integer index.

Obviously, different hardware architectures are going to treat it
differently, and not all architectures with a segmented address can (at the
hardware level) treat their memory as being linear. But for purposes of
logical thought experiments, you can treat a segmented address space as
linear just by (in your mind) concatenating the segment part and the offset
part. It becomes (in your mind) one big integer.

Clearly, Ada's abstraction of access types from any particular addressing
scheme is a good thing. It looks the same from the software level no matter
what the underlying hardware is like. For example, an architecture with a 32
bit segment and a 32 bit offset can be viewed identically to one with a 64
bit linear address because Ada is going to bookeep both under an access type
(or System.Address) and provide every operation you need for working with
the addresses without your having to know if the memory reference is kept in
one or two parts.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"James Rogers" <jimmaureenrogers@worldnet.att.net> wrote in message
news:3B7AD379.5559D329@worldnet.att.net...
>
> Sometimes this is correct. Some systems do have the ability to use
> both linear addressing and segment-offset addressing. Some of the
> older systems do not have any ability to support linear addressing.
> This is one reason the type System.Address is implementation defined.
> System.Address also has comparison functions, but is not an aritmetic
> type. It does have addition, subtraction, and modulus operations
> defined in System.Storage_Elements, but that does not make
> System.Address a numeric type.
>
> Note that there is a type called
> System.Storage_Elements.Integer_Address.
> This type is not a System.Address, but does provide conversion
> functions to and from System.Address.
>
> Ada provides, through these types, conversions between linear and
> segmented memory models, even if those conversions are not directly
> supported by the hardware memory model.
>

Re: Ada and pointers

[Tony Gair]

> 
>> Well, the statement is true enough because after all, dynamic allocation
>> and the things done by pointers are really a kind of fiction. Memory is
>> basically one big array that you index with integers, so obviously, a
>> non-dynamic/non-pointer solution must exist. Anything you do with
>> pointers could be implemented with a one dimensional array and integer
>> indexes - because that's what the compiler translates it into.
>> 

I find it difiicult to believe that this is obvious in any way.
It also dismisses the point of programmer error, none of us are infallible 
and its when some of us assume we are infallible and source omnipotent that 
our greatest and most widely known screw ups  strike  


>> However, that doesn't mean that one should avoid access types in all
>> cases. Sometimes it is the most natural expression of the solution. Its
>> just that you should generally use them sparingly and isolate them as
>> best you can. Ada lets you do this rather well. (Some OOP-style
>> programming relies heavily on access types so you've got to make design
>> trade offs - use the OOP for its benefits at the risk of having lots more
>> pointers flying around or avoid/isolate the pointers and implement a
>> solution that may not be as extensible.) Access types aren't a "bad"
>> thing - you just don't want to be forced into using them at every
>> conceivable turn as you must in C/C++.
>> 
>> MDC
>> --
> 
> Also note that there are some circumstances in which an access type is
> effectively required. Cohen's "Ada as a Second Language" lists several in
> section 8.5 I believe. As an Ada newbie, I have already run across a few
> of these situations, namely: recursive types and variable sized arrays (or
> to paraphrase Cohen, "simulating variable sized arrays." I suppose I could
> have framed the solution differently to avoid these cases, but frankly,
> I'm not exactly sure how.
> 

This could be to make converted c and c++ programmers happy. They get very 
unhappy when they have their pointers removed.

> As an aside, I have had some limited experience with FORTRAN code which
> uses a giant array with many integer index pointers into it. It even has
> its own memory management of this array, of sorts. I must say that trying
> to follow this code is no fun at all, even though it is heavily
> documented. It seems to me, the original coders of many years ago could
> really have used a language like Ada95.
> 
> jtd
> 

Thanks for all the answers.

Re: Ada and pointers

[Hambut]

"Marin David Condic" <dont.bother.mcondic.auntie.spam@[acm.org> wrote in message news:<9lek02$i88$1@nh.pace.co.uk>...
> I suppose that my logical explanation doesn't necessarily cover the same
> territory as mathematical proof. 

Nope - but it's an eminently practical explanation.

> Obviously not all algorithms have bounded
> memory use - try to compute Pi to the last digit - you'll run out of memory
> before you get there. I'm not sure if thats what you mean.

Yep - that's what I mean.  


Now where did I leave that angle I was trisecting? :-)

Re: Ada and pointers

[Marin David Condic]

Why would you find it difficult to believe? I'm not claiming that you can
take any algorithm that uses dynamic memory allocation and/or pointers and
*easily* translate it into an equivalent algorithm using a static array and
indexes. I'm not saying that such a translation wouldn't be prone to all
sorts of error and abuse. I'm also not saying that the equivalent
translation would be at all sound software engineering. What I'm saying is
that it seems obvious that any dynamic allocation/pointer algorithm *must
have* somewhere in the known universe, a parallel algorithm that relies only
on a static array and integer index. Why? Because that's all a computer has
for memory and somehow a compiler finds that equivalent algorithm or it
couldn't possibly build you an image that would execute.

It sounds to me like you think I'm claiming that people should translate
their linked list programs into array implementations - or that trying to do
so would be a good thing. This is not my claim at all.

MDC
--
Marin David Condic
Senior Software Engineer
Pace Micro Technology Americas    www.pacemicro.com
Enabling the digital revolution
e-Mail:    marin.condic@pacemicro.com
Web:      http://www.mcondic.com/


"Tony Gair" <tony@blueyonder.co.uk> wrote in message
news:DBFe7.12766$6R6.1217641@news1.cableinet.net...
>
> >
> >> Well, the statement is true enough because after all, dynamic
allocation
> >> and the things done by pointers are really a kind of fiction. Memory is
> >> basically one big array that you index with integers, so obviously, a
> >> non-dynamic/non-pointer solution must exist. Anything you do with
> >> pointers could be implemented with a one dimensional array and integer
> >> indexes - because that's what the compiler translates it into.
> >>
>
> I find it difiicult to believe that this is obvious in any way.
> It also dismisses the point of programmer error, none of us are infallible
> and its when some of us assume we are infallible and source omnipotent
that
> our greatest and most widely known screw ups  strike
>

Re: Ada and pointers

[Darren New]

> It sounds to me like you think I'm claiming that people should translate
> their linked list programs into array implementations - or that trying to do
> so would be a good thing. This is not my claim at all.

FWIW, in college I used a Lisp interpreter written in Fortran IV.
INTEGER CAR(200000)
INTEGER CDR(200000)

 :-)


As an aside, I have a C library right now that uses lots of linked
lists. Linked lists of messages to send, linked lists of messages
awaiting answers, linked lists of message numbers sent for which no
answer has been received, etc.  Basically, most of these would be better
as arrays where I could add elements to either end or delete elements
from either end or the middle. Is there a better idiom for doing this in
Ada, rather than using access types? 

Basically, I guess I'm asking whether there's an idiom for building
unbounded queues rather than with linked lists using access types?

-- 
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand. dnew@san.rr.com
           When was sliced bread invented?

Re: Ada and pointers

[James Rogers]

Darren New wrote:
> 
> As an aside, I have a C library right now that uses lots of linked
> lists. Linked lists of messages to send, linked lists of messages
> awaiting answers, linked lists of message numbers sent for which no
> answer has been received, etc.  Basically, most of these would be better
> as arrays where I could add elements to either end or delete elements
> from either end or the middle. Is there a better idiom for doing this in
> Ada, rather than using access types?
> 
> Basically, I guess I'm asking whether there's an idiom for building
> unbounded queues rather than with linked lists using access types?
> 

Remember that Ada does not have a concept of an unbounded array.
It does have a concept of an unconstrained array, which is really
quite different.

Every array has an index type. That index type must be a discrete
type. All discrete types have bounded ranges. This means that all
arrays are bounded.

That said, within the index range of an unconstrained array you
can provide some flexibility for queues or other buffer types.
This can be done in the same manner as the C++ (or Java) Vector
class.

The following code is a simple example of an Ada version of a C++
vector. Note that access types are used, but only because that
simplifies dynamic allocation and deallocation.

-- File: Tagged_Vector.ads
--
-- Generic vector for tagged types following C++ rules

generic
	type Element_Type is tagged private;
	with function ">=" (Left, Right : Element_Type) return Boolean;
package Tagged_Vector is
   type Group is array(Positive range <>) of Element_Type;
	type Vector is private;
	function First(Item : in Vector) return Natural;
	function Last(Item : in Vector) return Natural;
	function Size(Item : in Vector) return Natural;
	function Capacity(Item : in Vector) return Natural;
	function Is_Empty(Item : in Vector) return Boolean;
	function Element(Num : in Positive; 
	                 Item : in Vector) return Element_Type;
	procedure Reserve(Num_Items : in Positive;
	                  Item : in out Vector);
	function Front(Item : in Vector) return Element_Type;
	function Back(Item : in Vector) return Element_Type;
	procedure Push_Back(Value : in Element_Type;
	                    Onto  : in out Vector);
	procedure Pop_Back(Value : out Element_Type;
	                   From  : in out Vector);
	procedure Insert(Value  : in Element_Type;
	                 Before : in Positive;
			 Onto   : in out Vector);
	procedure Insert(Value      : in Element_Type;
	                 Num_Copies : in Positive;
			 Before     : in Positive;
			 Onto       : in out Vector);
	procedure Insert(The_Group : in Group;
	                 Before    : in Positive;
			 Onto      : in out Vector);
	procedure Erase(Index : in Positive;
	                From  : in out Vector);
	procedure Erase(First : in Positive;
	                Last  : in Positive;
			From  : in out Vector);
	procedure Resize(Num  : in Positive;
	                 Item : in out Vector);
	function "="(Left, Right : Vector) return Boolean;
	function "<"(Left, Right : Vector) return Boolean;
	
	Vector_Empty_Error : Exception;
private
   type Group_Access is access all Group;
   type Vector is record
	Buffer : Group_Access := new Group(1..20);
	Num_Elements : Natural := 0;
   end record;
end Tagged_Vector; 

-- File : Tagged_Vector.adb
   with Ada.Unchecked_Deallocation;

   package body Tagged_Vector is
      procedure Free is new Ada.Unchecked_Deallocation(
                        Object => Group,
                        Name =>Group_Access);
   
      function First(Item : in Vector) return Natural is
      begin
         if Item.Num_Elements > 0 then
            return 1;
         else
            return 0;
         end if;
      end First;
   
      function Last(Item : in Vector) return Natural is
      begin
         return Item.Num_Elements;
      end Last;
   
      function Size(Item : in Vector) return Natural is
      begin
         return Item.Num_Elements;
      end Size;
   
      function Capacity(Item : in Vector) return Natural is
      begin
         if Item.Buffer /= null then
            return Item.Buffer.all'Last;
         else
            return 0;
         end if;
      end Capacity;
   
      function Is_Empty(Item : in Vector) return Boolean is
      begin
         return Item.Num_Elements = 0;
      end Is_Empty;
   
      function Element(Num : in Positive;
                       Item : in Vector) return Element_Type is
      begin
         if Num <= Item.Num_Elements then
            return Item.Buffer.all(Num);
         else
            return Item.Buffer.all(Item.Num_Elements);
         end if;
      end Element;
   
      procedure Reserve(Num_Items : in Positive;
                        Item : in out Vector) is
         Temp : Group_Access;
      begin
         if Num_Items > Item.Buffer.all'Last then
            Temp := new Group(1..(2 * Num_Items));
         -- Copy Elements to new buffer
            Temp.all(1..Item.Num_Elements) :=
                Item.Buffer.all(1..Item.Num_Elements);
            Free(Item.Buffer);
         end if;
         Item.Buffer := Temp;
      end Reserve;
   
      function Front(Item : in Vector) return Element_Type is
      begin
         if Item.Num_Elements = 0 then
            raise Vector_Empty_Error;
         end if;
         return Item.Buffer.all(1);
      end Front;
   
      function Back(Item : in Vector) return Element_Type is
      begin
         if Item.Num_Elements = 0 then
            raise Vector_Empty_Error;
         end if;
         return Item.Buffer.all(Item.Num_Elements);
      end Back;
   
      procedure Push_Back(Value : in Element_Type;
                          Onto  : in out Vector) is
         Temp : Group_Access;
      begin
         if Onto.Num_Elements = Onto.Buffer.All'Last then
            Temp := new Group(1..(2 * Onto.Num_Elements));
            Temp.all(1..Onto.Num_Elements) := 
               Onto.Buffer.all(1..Onto.Num_Elements);
            Free(Onto.Buffer);
            Onto.Buffer := Temp;
         end if;
         Onto.Num_Elements := Onto.Num_Elements + 1;
         Onto.Buffer.all(Onto.Num_Elements) := Value;
      end Push_Back;
   
      procedure Pop_Back(Value : out Element_Type;
                         From  : in out Vector) is
      begin
         if From.Num_Elements = 0 then
            raise Vector_Empty_Error;
         end if;
         Value := From.Buffer.all(From.Num_Elements);
         From.Num_Elements := From.Num_Elements - 1;
      end Pop_Back;
   
      procedure Insert(Value : in Element_Type;
                       Before : in Positive;
                       Onto   : in out Vector) is
         Temp : Group_Access;
         new_Pos : Positive;
      begin
         if Onto.Num_Elements = Onto.Buffer.All'Last then
            Temp := new Group(1..(2 * Onto.Num_Elements));
            Temp.all(1..Onto.Num_Elements) := 
               Onto.Buffer.all(1..Onto.Num_elements);
            Free(Onto.Buffer);
            Onto.Buffer := Temp;
         end if;
         if Before <= Onto.Num_Elements then
            for num in reverse Before..Onto.Num_Elements loop
               Onto.Buffer.all(Num + 1) := Onto.Buffer.All(Num);
            end loop;
            New_Pos := Before;
         else
            New_Pos := Onto.Num_Elements + 1;
         end if;
         Onto.Buffer.All(New_Pos) := Value;
         Onto.Num_Elements := Onto.Num_Elements + 1;
      end Insert;
   
      procedure Insert(Value      : in Element_Type;
                       Num_Copies : in Positive;
                       Before     : in Positive;
                       Onto       : in out Vector) is
      begin
         for copy in 1..Num_Copies loop
            Insert(Value => Value, Before => Before, Onto => Onto);
         end loop;
      end Insert;
   
      procedure Insert(The_Group : in Group;
                       Before    : in Positive;
                       Onto      : in out Vector) is
      begin
         for Index in reverse The_Group'Range loop
            Insert(Value  => The_Group(Index),
                   Before => Before,
                   Onto   => Onto);
         end loop;
      end Insert;
   
      procedure Erase(Index : in Positive;
                      From  : in out Vector) is
      begin
         if Index <= From.Num_Elements then
            for num in Index + 1..From.Num_Elements loop
               From.Buffer.all(Num - 1) := From.Buffer.all(Num);
            end loop;
            From.Num_Elements := From.Num_Elements - 1;
         end if;
      end Erase;
   
      procedure Erase(First : in Positive;
                      Last  : in Positive;
                      From  : in out Vector) is
         Final : Positive;
      begin
         if Last >= First then
            if Last > From.Num_Elements then
               Final := From.Num_Elements;
            else
               Final := Last;
            end if;
            for num in First..Final loop
               Erase(Index => First, From => From);
            end loop;
         end if;
      end Erase;
   
      procedure Resize(Num : in Positive;
                       Item : in out Vector) is
         Temp : Group_Access;
      begin
         if Num >= (2 * Item.Num_Elements) then
            Temp := new Group(1..Num);
            for index in 1..Item.Num_Elements loop
               Temp.all(index) := Item.Buffer.all(Index);
            end loop;
            Free(Item.Buffer);
            Item.Buffer := Temp;
         end if;
      end Resize;
   
      function "="(Left, Right : in Vector) return Boolean is
         Result : Boolean;
      begin
         if Left.Num_Elements = Right.Num_Elements then
            Result := True;
            for index in 1..Left.Num_Elements loop
               if Left.Buffer.all(index) /= Right.Buffer.all(Index) then
                  Result := False;
               end if;
               exit when Result = False;
            end loop;
         else
            Result := False;
         end if;
         return Result;
      end "=";
   
      function "<"(Left, Right : in Vector) return Boolean is
         Result : Boolean;
      begin
         if Left.Num_Elements <= Right.Num_Elements then
            Result := True;
            for index in 1..Left.Num_Elements loop
               if Left.Buffer.all(Index) >= Right.Buffer.all(Index) then
                  Result := False;
               end if;
               exit when Result = False;
            end loop;
         else
            Result := False;
         end if;
         return Result;
      end "<";
   end Tagged_Vector;
-------------------------------------------

You will notice that using a Tagged_Vector as a resizable array has some
real costs. For instance, inserting or erasing elements causes massive
copy operations. There is also the cost of enlarging the array, which
also requires massive copying.

I created this version using the SGI definition of the C++ Standard
Template Library. It therefore satisfies all the behavior requirements
stated by the SGI definition.

Jim Rogers
Colorado Springs, Colorado USA

Re: Ada and pointers

[Darren New]

> You will notice that using a Tagged_Vector as a resizable array has some
> real costs. For instance, inserting or erasing elements causes massive
> copy operations. There is also the cost of enlarging the array, which
> also requires massive copying.

Cool! Thanks! I actually expect changes in the middle to be rare, and
only on small arrays, so this will probably be good for me. I'll need to
study it more, to learn more Ada. :-)

The other possibility is to encapsulate all the linked-list stuff
nicely, giving nice semantic-oriented interfaces, which is more of a
pain in C than it's worth in my case. 

-- 
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand. dnew@san.rr.com
           When was sliced bread invented?

Re: Ada and pointers

[Ted Dennison]

In article <3B7BFB59.5BBAF07F@san.rr.com>, Darren New says...
>
>The other possibility is to encapsulate all the linked-list stuff
>nicely, giving nice semantic-oriented interfaces, which is more of a
>pain in C than it's worth in my case. 

If you want to do that, you should probably look at the Ada booch components
(although for a lot of people, its easier to write a limited array-based queue
themselves than it is to find and figure out how to instantiate the proper booch
component).

---
T.E.D.    homepage   - http://www.telepath.com/dennison/Ted/TED.html
          home email - mailto:dennison@telepath.com

Re: Ada and pointers

[Darren New]

Ted Dennison wrote:
> 
> In article <3B7BFB59.5BBAF07F@san.rr.com>, Darren New says...
> >
> >The other possibility is to encapsulate all the linked-list stuff
> >nicely, giving nice semantic-oriented interfaces, which is more of a
> >pain in C than it's worth in my case.
> 
> If you want to do that, you should probably look at the Ada booch components
> (although for a lot of people, its easier to write a limited array-based queue
> themselves than it is to find and figure out how to instantiate the proper booch
> component).

Actually, I meant it would be easy to encapsulate the linked-list stuff
in a semantically meaningful set of packages in Ada, whereas in C with
its poor namespace control and lack of generics and etc, it's just not
worth the effort.

Certainly, a routine to find the first item on the list whose X field is
less than the value Y is a lot easier to encapsulate in a general way in
Ada than C.

-- 
Darren New / Senior MTS & Free Radical / Invisible Worlds Inc.
San Diego, CA, USA (PST). Cryptokeys on demand. dnew@san.rr.com
           When was sliced bread invented?