From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,FREEMAIL_FROM
	autolearn=ham autolearn_force=no version=3.4.4
X-Google-Thread: 103376,4fbd260da735f6f4
X-Google-Attributes: gid103376,public
X-Google-Language: ENGLISH,ASCII-7-bit
Path: 
 g2news1.google.com!news4.google.com!out03b.usenetserver.com!news.usenetserver.com!in01.usenetserver.com!news.usenetserver.com!news.tele.dk!news.tele.dk!small.news.tele.dk!lnewsinpeer00.lnd.ops.eu.uu.net!emea.uu.net!peer-uk.news.demon.net!kibo.news.demon.net!news.demon.co.uk!demon!not-for-mail
From: Simon Wright <simon.j.wright@mac.com>
Newsgroups: comp.lang.ada
Subject: Re: Copying string slices before calling subroutines?
Date: Fri, 04 May 2007 23:27:57 +0100
Organization: Pushface
Message-ID: <m2odl02phu.fsf@mac.com>
References: <0hj5339mjmond132qhbn2o01unurs61lbj@4ax.com>
 <1178091967.392381.282510@o5g2000hsb.googlegroups.com>
 <aavi33t9mu7fbv1mt5ovsuec860t00dpsd@4ax.com> <m2slad3cfa.fsf@mac.com>
 <ygemz0l13lk.fsf_-_@hugsarin.dmusyd.edu>
 <5dv3wh6scrh1.2986pbvdw8y2$.dlg@40tude.net>
 <ygeirb90x07.fsf_-_@hugsarin.dmusyd.edu>
 <yged51g2aa9.fsf@hugsarin.dmusyd.edu>
 <4oppvmc6anir.g0mz9mrahmdo.dlg@40tude.net>
 <4akrg4-mot.ln1@newserver.thecreems.com>
NNTP-Posting-Host: pogner.demon.co.uk
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Trace: news.demon.co.uk 1178317677 14179 62.49.19.209 (4 May 2007 22:27:57
 GMT)
X-Complaints-To: abuse@demon.net
NNTP-Posting-Date: Fri, 4 May 2007 22:27:57 +0000 (UTC)
Cancel-Lock: sha1:a/XY/kRNkvWS+RrktyuFWJH0qts=
User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.95 (darwin)
Xref: g2news1.google.com comp.lang.ada:15548
Date: 2007-05-04T23:27:57+01:00
List-Id: <comp.lang.ada>

Jeffrey Creem <jeff@thecreems.com> writes:

>  function Index
>      (Source  : String;
>       Pattern : String;
>       Going   : Direction := Forward;
>       Mapping : Maps.Character_Mapping := Maps.Identity) return Natural
>    is
>       Cur_Index     : Natural;
>       Mapped_Source : String (Source'Range);

There's the problem that I had (in my case Source'Length was >
2_000_000!) calling Index from one of my tasks.

My reworking begins

   function Index
     (Source  : String;
      Pattern : String;
      Going   : Ada.Strings.Direction := Ada.Strings.Forward;
      Mapping : Ada.Strings.Maps.Character_Mapping
        := Ada.Strings.Maps.Identity) return Natural
   is
      Cur_Index       : Natural;
      Potential_Match : Boolean;
      use Ada.Strings;
      use Ada.Strings.Maps;
   begin
      if Pattern = "" then
         raise Pattern_Error;
      end if;

      --  Forwards case

      if Going = Forward then
         for J in 1 .. Source'Length - Pattern'Length + 1 loop
            Cur_Index := Source'First + J - 1;
            Potential_Match := True;
            for K in Pattern'Range loop
               if Pattern (K) /=
                 Value (Mapping, Source (Cur_Index + K - 1)) then
                  Potential_Match := False;
                  exit;
               end if;
            end loop;
            if Potential_Match then
               return Cur_Index;
            end if;
         end loop;

which calls Ada.Strings.Maps.Value rather more often than I suppose it
could. But since the normal case is for the mapping to be the identity
mapping the most useful optimisation would be to check for Identity
and just compare directly.


Someone else was asking whether GNAT copies on the stack before the
call -- I see no evidence of that. I had to provide my own
implementation of this Ada05 routine because my code has to be Ada95,
and it shows no sign of excessive stack use:

   function Index
     (Source : String;
      Pattern : String;
      From : Positive;
      Going : Ada.Strings.Direction := Ada.Strings.Forward;
      Mapping : Ada.Strings.Maps.Character_Mapping
        := Ada.Strings.Maps.Identity)
     return Natural is
      Candidate : String renames Source (From .. Source'Last);
   begin
      return Index (Source => Candidate,
                    Pattern => Pattern,
                    Going => Going,
                    Mapping => Mapping);
   end Index;