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=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.28.154.151 with SMTP id c145mr107419wme.3.1466476087520; Mon, 20 Jun 2016 19:28:07 -0700 (PDT) X-Received: by 10.157.11.173 with SMTP id 42mr241789oth.10.1466476087366; Mon, 20 Jun 2016 19:28:07 -0700 (PDT) Path: eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!goblin1!goblin.stu.neva.ru!w10no4770429lbo.0!news-out.google.com!di11ni13391lbb.1!nntp.google.com!oe3no6570016lbb.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Mon, 20 Jun 2016 19:28:07 -0700 (PDT) In-Reply-To: <4da8ad8e-f6b4-46b3-b81d-b255c030a45c@googlegroups.com> Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=216.121.226.25; posting-account=ENgozAkAAACH-stq5yXctoDQeZQP2E6J NNTP-Posting-Host: 216.121.226.25 References: <66c14298-c62d-4f4b-b0c0-e969454f9334@googlegroups.com> <4da8ad8e-f6b4-46b3-b81d-b255c030a45c@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: <6100770a-774c-41a7-b1d9-498f80426835@googlegroups.com> Subject: Re: Generic Embedded List Nodes From: Warren Injection-Date: Tue, 21 Jun 2016 02:28:07 +0000 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Xref: news.eternal-september.org comp.lang.ada:30848 Date: 2016-06-20T19:28:07-07:00 List-Id: On Monday, 20 June 2016 15:47:12 UTC-4, Shark8 wrote: > On Saturday, June 18, 2016 at 4:52:06 PM UTC-6, Warren wrote: > > Getting back to Ada after a hiatus, I currently have a need to build a= =20 > > generic package to implement "embedded list node" lists. The advantage= =20 > > is high performance in a server setting to avoid underlying malloc/free > > calls. > >=20 > > The idea is that the list node resides within the structure/tagged type= , > > and acts as a doubly linked list node when in a list. The Emb_Node can > > be used as a list head when itself (or as part of another structure). T= his > > kind of thing is done in the Linux kernel, for example. > > =20 > > The Emb_Node and its operations are trivial. The problem occurs when > > you traverse a linked list of Emb_Nodes (or its derived type). With > > a given node, I need to then access the object that _contains_ it. In > > C/C++ you do some offset calculation from the node address back to > > the owning struct/class. > >=20 > > My idea (in Ada) was to save some kind of access value in a type > > derived from Emb_List. But that is where the trouble starts. > >=20 > > package Emb_List is > > =20 > > type Emb_Node is tagged private; > > =20 > > procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node); > > procedure Unlink(Node: access Emb_Node); > >=20 > > private > >=20 > > type Emb_Node is tagged > > record > > Next: access Emb_Node; -- Ptr to next node in list (if any= ) > > Prev: access Emb_Node; -- Ptr to prev node in list (if any= ) > > end record; > > =20 > > end Emb_List; > > =20 > > The generic extension (below) was intended to hold the reference to the > > containing object, which is where the trouble starts. I was hoping this > > would work, but running into "missing full declaration for private > > extension". > >=20 > > generic > > type Object_Type is tagged private; > > package Emb_List.Nodes is > >=20 > > type Node_Type(Obj: access Object_Type) is new Emb_Node; > > =20 > > function Object(Node: Node_Type) return Object_Type; > > =20 > > end Emb_List.Nodes; > >=20 > >=20 > > The other end of the challenge will be to have the Node_Type save the > > owning object access value at the time it is created: > >=20 > > type Something_New_Type is tagged > > record > > Stuff: Natural; > > Timeout_Node: Node_Type(some access to this record); > > ... > > end record; > > =20 > > I am trying to avoid using 'Address for this, since there is likely a > > way to do this "right". > >=20 > > Warren. >=20 > Hm, have you tried seeing if any Ada.Containers.* fits your needs? You co= uld perhaps use Indefinite_Holder to hold your item or Indefinite_Vector to= hold the entire list. If you read upstream, I am looking for an _extremely_ high performance set = of operations, requiring only: - insert head - traverse (head to tail only) - delete from list The implementation I have used on a C++ server works extremely well (inspir= ed by the Linux kernel code), and costs almost nothing. The three operation= s above are inlined and amount to a few pointer related operations.=20 Even a few microseconds of overhead drops your transaction throughput consi= derably, so using something like Ada containers (or STL in C++) is definite= ly out for this application. Also any use of malloc/free where possible mus= t be avoided because these are performance killers (even when using jremall= oc). Warren