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=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD, FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4 X-Google-Thread: 103376,a65bb7bde679ed1d X-Google-NewGroupId: yes X-Google-Attributes: gida07f3367d7,domainid0,public,usenet X-Google-Language: ENGLISH,ASCII-7-bit Received: by 10.68.35.68 with SMTP id f4mr3385338pbj.5.1322646668405; Wed, 30 Nov 2011 01:51:08 -0800 (PST) Path: lh20ni43382pbb.0!nntp.google.com!news2.google.com!news.glorb.com!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail From: Natasha Kerensikova Newsgroups: comp.lang.ada Subject: Re: Ann: Natools.Chunked_Strings, beta 1 Date: Wed, 30 Nov 2011 09:51:01 +0000 (UTC) Organization: A noiseless patient Spider Message-ID: References: <4ed4fc37$0$2537$ba4acef3@reader.news.orange.fr> <4ed5119e$0$7619$9b4e6d93@newsspool1.arcor-online.net> Mime-Version: 1.0 Injection-Date: Wed, 30 Nov 2011 09:51:01 +0000 (UTC) Injection-Info: mx04.eternal-september.org; posting-host="Mda950WjNwNLAFOE7yJXQw"; logging-data="13936"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/4Ici7QM+SOUhddRbiqI91" User-Agent: slrn/0.9.9p1 (FreeBSD) Cancel-Lock: sha1:vdADhvM8LS+NuKi6maDNPFW7xCA= Xref: news2.google.com comp.lang.ada:14742 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Date: 2011-11-30T09:51:01+00:00 List-Id: On 2011-11-29, Georg Bauhaus wrote: > The package GNAT.Spitbol.Patterns uses Unbounded_String extensively. > Last time I checked it seemed possible to replace the dependence > on Ada.Strings.Unbounded with one on a compatible package. > The very first definition in GNAT.Spitbol is > > subtype VString is Ada.Strings.Unbounded.Unbounded_String; > > It should be sufficient to change this definition and > > Nul : VString renames Ada.Strings.Unbounded.Null_Unbounded_String; > > to use your strings, in local copies of the sources of the > GNAT.Spitbol hierarchy. Also To_Unbounded_String has to be replaced by To_Chunked_String, but this is also conveniently renamed at the same place. > Of particular interest might be, I think, anything that can improve > replacement in objects of type Unbounded_String. It seems we are talking about the transformation of Prefix & Old & Suffix into Prefix & Replacement & Suffix, with Old'Length /= Replacement'Length. In that case, Chunked_String is probably not an improvement over Unbounded_String, since in both cases the whole Suffix has to be moved, so they should be of similar speed with a slight advantage for Unbounded_String because the contiguous memory is more cache-friendly. However it seems to be the kind of use-cases for which ropes were designed. So it leads to the question, is there already an Ada implementation of ropes somewhere? Assuming there isn't, I wouldn't mind starting one. It seems to be an interesting toy problem. When thinking about it, the first tricky part I identified is dealing with reference-counted object in a thread-safe way (the original paper assumed a garbage collector). It will probably involve writing tree algorithms from scratch (to efficiently preserve the rope invariant when rebalancing or rotating), so I will end up with accesses to reference counted nodes. I guess using a protected type for nodes will take care of the thread safety, but I will need to somehow indicate whether I'm dereferencing the access for reading or for read/write. I might be an interesting concurrency exercise, but I don't really know how to properly test it. Thanks for your interest, Natasha