* Generic Embedded List Nodes @ 2016-06-18 22:52 Warren 2016-06-18 23:40 ` Jeffrey R. Carter ` (4 more replies) 0 siblings, 5 replies; 52+ messages in thread From: Warren @ 2016-06-18 22:52 UTC (permalink / raw) Getting back to Ada after a hiatus, I currently have a need to build a generic package to implement "embedded list node" lists. The advantage is high performance in a server setting to avoid underlying malloc/free calls. 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). This kind of thing is done in the Linux kernel, for example. 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. 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. package Emb_List is type Emb_Node is tagged private; procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node); procedure Unlink(Node: access Emb_Node); private 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; end Emb_List; 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". generic type Object_Type is tagged private; package Emb_List.Nodes is type Node_Type(Obj: access Object_Type) is new Emb_Node; function Object(Node: Node_Type) return Object_Type; end Emb_List.Nodes; 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: type Something_New_Type is tagged record Stuff: Natural; Timeout_Node: Node_Type(some access to this record); ... end record; I am trying to avoid using 'Address for this, since there is likely a way to do this "right". Warren. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-18 22:52 Generic Embedded List Nodes Warren @ 2016-06-18 23:40 ` Jeffrey R. Carter 2016-06-19 2:15 ` Warren 2016-06-19 2:14 ` Jeremiah ` (3 subsequent siblings) 4 siblings, 1 reply; 52+ messages in thread From: Jeffrey R. Carter @ 2016-06-18 23:40 UTC (permalink / raw) On 06/18/2016 03:52 PM, Warren wrote: > > 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). This > kind of thing is done in the Linux kernel, for example. > > 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. Let me make sure I understand this. You have type Emb_Node, and you can string Emb_Nodes together to make a list. You want to make a composite type with an Emb_Node component: type Outer is record ... Node : Emb_Node; ... end record; and declare objects of this type: O1 : Outer; O2 : Outer; type O_Set is array (Positive range <>) of Outer; O_List : O_Set (1 .. 10); type Something is record ... O : Outer; ... end record; S : Something; and then be able to string the Node components of all these Outers together into a list, and then treat that list as a list of Outers. Is that correct? -- Jeff Carter "My legs are gray, my ears are gnarled, my eyes are old and bent." Monty Python's Life of Brian 81 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-18 23:40 ` Jeffrey R. Carter @ 2016-06-19 2:15 ` Warren 2016-06-19 3:04 ` Jeffrey R. Carter 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-19 2:15 UTC (permalink / raw) On Saturday, 18 June 2016 19:40:31 UTC-4, Jeffrey R. Carter wrote: > On 06/18/2016 03:52 PM, Warren wrote: > > > > 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). This > > kind of thing is done in the Linux kernel, for example. > > > > 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. > > Let me make sure I understand this. You have type Emb_Node, and you can string > Emb_Nodes together to make a list. Yes. > You want to make a composite type with an > Emb_Node component: > > type Outer is record > ... > Node : Emb_Node; > ... > end record; Yes. > and declare objects of this type: > > O1 : Outer; > O2 : Outer; Yes. From this point, we add "heads of lists". They can be stand alone, or part of another object (for now let's assume stand alone ): Timeouts: Emb_Node; Timeouts.Insert_Head(O1); Timeouts.Insert_Head(O2); etc. Then if you did: O1.Node.Unlink; the object O1 becomes removed from the linked list it was in (if any). > and then be able to string the Node components of all these Outers together into > a list, and then treat that list as a list of Outers. > > Is that correct? Essentially, yes. With one or more Head nodes, you create one or more lists. Not all of the members need be in any list. Obviously, with only one given embedded node, that node can be a member of at most one list. Of course more lists can be supported by adding additional embedded nodes, but clearly one needs to be careful not to mix them up. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 2:15 ` Warren @ 2016-06-19 3:04 ` Jeffrey R. Carter 0 siblings, 0 replies; 52+ messages in thread From: Jeffrey R. Carter @ 2016-06-19 3:04 UTC (permalink / raw) On 06/18/2016 07:15 PM, Warren wrote: > On Saturday, 18 June 2016 19:40:31 UTC-4, Jeffrey R. Carter wrote: >> >> Let me make sure I understand this. You have type Emb_Node, and you can string >> Emb_Nodes together to make a list. > > Yes. > >> You want to make a composite type with an >> Emb_Node component: > > Yes. > >> and declare objects of this type: > > Yes. > >> and then be able to string the Node components of all these Outers together into >> a list, and then treat that list as a list of Outers. >> >> Is that correct? > > Essentially, yes. That's a terrible idea. It sounds like something that only someone who thinks doing "some offset calculation from the node address back to the owning struct/class" is a good idea would think up. -- Jeff Carter "My legs are gray, my ears are gnarled, my eyes are old and bent." Monty Python's Life of Brian 81 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-18 22:52 Generic Embedded List Nodes Warren 2016-06-18 23:40 ` Jeffrey R. Carter @ 2016-06-19 2:14 ` Jeremiah 2016-06-19 2:21 ` Warren 2016-06-20 6:08 ` Niklas Holsti ` (2 subsequent siblings) 4 siblings, 1 reply; 52+ messages in thread From: Jeremiah @ 2016-06-19 2:14 UTC (permalink / raw) On Saturday, June 18, 2016 at 6:52:06 PM UTC-4, Warren wrote: > Getting back to Ada after a hiatus, I currently have a need to build a > generic package to implement "embedded list node" lists. The advantage > is high performance in a server setting to avoid underlying malloc/free > calls. > > 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). This > kind of thing is done in the Linux kernel, for example. > > 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. > > 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. > > package Emb_List is > > type Emb_Node is tagged private; > > procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node); > procedure Unlink(Node: access Emb_Node); > > private > > 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; > > end Emb_List; > > 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". > > generic > type Object_Type is tagged private; > package Emb_List.Nodes is > > type Node_Type(Obj: access Object_Type) is new Emb_Node; > > function Object(Node: Node_Type) return Object_Type; > > end Emb_List.Nodes; Change Node_Type to: type Node_Type(Obj: access Object_Type) is new Emb_Node with null record; You need an extension, even if it is a null record. > 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: > > type Something_New_Type is tagged > record > Stuff: Natural; > Timeout_Node: Node_Type(some access to this record); > ... > end record; > > I am trying to avoid using 'Address for this, since there is likely a > way to do this "right". > > Warren. Well, I'm only a novice, but the only way I have gotten something like that was to use incomplete types: type Something_New_Type; package SNT_Pkg is new Emb_List.Nodes(Object_Type => Something_New_Type); use SNT_Pkg; type Something_New_Type is tagged limited record Stuff: Natural; Timeout_Node: Node_Type(Something_New_Type'Access); end record; This means, however, that you would need to change Emp_List.Nodes to use incomplete types: generic type Object_Type; package Emb_List.Nodes is type Node_Type(Obj: access Object_Type) is new Emb_Node with null record; end Emb_List.Nodes; However, you would need to rethink your function to return the Object as you cannot return a complete type when using incomplete types. You might be stuck with just using the access value instead or perhaps with some other design changes you can come up with a better solution. Again, I am still learning, so maybe some of the more experienced users can comment. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 2:14 ` Jeremiah @ 2016-06-19 2:21 ` Warren 2016-06-19 2:50 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-19 2:21 UTC (permalink / raw) On Saturday, 18 June 2016 22:14:22 UTC-4, Jeremiah wrote: > On Saturday, June 18, 2016 at 6:52:06 PM UTC-4, Warren wrote: > > Getting back to Ada after a hiatus, I currently have a need to build a > > generic package to implement "embedded list node" lists. The advantage > > is high performance in a server setting to avoid underlying malloc/free > > calls. > > > > 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). This > > kind of thing is done in the Linux kernel, for example. > > > > 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. > > > > 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. > > > > package Emb_List is > > > > type Emb_Node is tagged private; > > > > procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node); > > procedure Unlink(Node: access Emb_Node); > > > > private > > > > 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; > > > > end Emb_List; > > > > 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". > > > > generic > > type Object_Type is tagged private; > > package Emb_List.Nodes is > > > > type Node_Type(Obj: access Object_Type) is new Emb_Node; > > > > function Object(Node: Node_Type) return Object_Type; > > > > end Emb_List.Nodes; > > Change Node_Type to: > type Node_Type(Obj: access Object_Type) is new Emb_Node with null record; > > You need an extension, even if it is a null record. I had clearly forgotten about "with null record". I will try that. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 2:21 ` Warren @ 2016-06-19 2:50 ` Warren 2016-06-19 4:45 ` Simon Wright 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-19 2:50 UTC (permalink / raw) On Saturday, 18 June 2016 22:21:18 UTC-4, Warren wrote: > On Saturday, 18 June 2016 22:14:22 UTC-4, Jeremiah wrote: > > On Saturday, June 18, 2016 at 6:52:06 PM UTC-4, Warren wrote: > > > Getting back to Ada after a hiatus, I currently have a need to build a > > > generic package to implement "embedded list node" lists. The advantage > > > is high performance in a server setting to avoid underlying malloc/free > > > calls. > > > > > > 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). This > > > kind of thing is done in the Linux kernel, for example. > > > > > > 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. > > > > > > 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. > > > > > > package Emb_List is > > > > > > type Emb_Node is tagged private; > > > > > > procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node); > > > procedure Unlink(Node: access Emb_Node); > > > > > > private > > > > > > 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; > > > > > > end Emb_List; > > > > > > 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". > > > > > > generic > > > type Object_Type is tagged private; > > > package Emb_List.Nodes is > > > > > > type Node_Type(Obj: access Object_Type) is new Emb_Node; > > > > > > function Object(Node: Node_Type) return Object_Type; > > > > > > end Emb_List.Nodes; > > > > Change Node_Type to: > > type Node_Type(Obj: access Object_Type) is new Emb_Node with null record; > > > > You need an extension, even if it is a null record. > > I had clearly forgotten about "with null record". I will try that. > > Warren generic type Object_Type is tagged private; package Emb_List.Nodes is type Node_Type(Obj: access Object_Type := Obj'Access) is new Emb_Node with null record; function Object(Node: Node_Type) return Object_Type; end Emb_List.Nodes; The problem with this now is "discriminant "Obj" cannot be used before end of discriminant part". This is intended to allow extension of My_Recd with a Node that knows My_Recd'Access. declare type My_Recd is tagged record Id: Natural := 99; end record; package EMB is new Emb_List.Nodes(Object_Type => My_Recd); Is there another way that I could do this: i.e. determine My_Recd'Access from some list node object, embedded in My_Recd? Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 2:50 ` Warren @ 2016-06-19 4:45 ` Simon Wright 2016-06-19 18:27 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Simon Wright @ 2016-06-19 4:45 UTC (permalink / raw) Warren <ve3wwg@gmail.com> writes: > type Node_Type(Obj: access Object_Type := Obj'Access) is new Emb_Node > with null record; You could try type Node_Type(Discr : access Object_Type := Obj'Access) is new Emb_Node with null record; to avoid the name clash, but there is no Obj here to take 'Access of. The compilable way to write this would be type Node_Type(Obj: access Object_Type) is new Emb_Node with null record; or, better in most cases, type Node_Type(Obj: access Object_Type) is new Emb_Node with null record; ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 4:45 ` Simon Wright @ 2016-06-19 18:27 ` Warren 2016-06-19 19:04 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-19 18:27 UTC (permalink / raw) On Sunday, 19 June 2016 00:45:54 UTC-4, Simon Wright wrote: > Warren <ve3wwg@gmail.com> writes: > > type Node_Type(Obj: access Object_Type) is new Emb_Node > with null record; I've come to the conclusion that my original idea in Ada terms is too half baked. What it will come down to in the end is doing an offset calculation from the Node back to the Object when its access is required (through a function). Even in C/C++ this is a bit of a problem. While there is an offsetof(type,member) macro, this is only usable on non-dynamic types. Calculating an offset of a struct is trivial when you have it allocated. But when the class has a constructor, then you may not want to invoke that overhead only to create one for offset calculations. In Ada for some record Type R.M where R is the record and M is the member, you cannot do R.M'Position when R is just a type. But you can cheat this, similar to how I have done it in C/C++: with System; with Ada.Integer_Text_IO; procedure T is use Ada.Integer_Text_IO; type R_Type is record I : Integer; F : Float; end record; A: System.Address; R: R_Type; for R'Address use A; begin Put(R.I'Position); Put(R.F'Position); end; This never allocates the object, but assumes it already exists at address A. Since the record and its members are never actually used, it is possible to have the compiler do the necessary calculations. This will complain "warning: variable "A" is read but never assigned", however. I suppose a tagged R.Initialize could also establish an 'Access value in all Emb_Node members, using some other procedure call for Emb_Node (perhaps Set_Object). But it is desireable not to have to carry the object reference in the Emb_Node at all. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 18:27 ` Warren @ 2016-06-19 19:04 ` Dmitry A. Kazakov 2016-06-19 20:13 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-19 19:04 UTC (permalink / raw) On 2016-06-19 20:27, Warren wrote: > On Sunday, 19 June 2016 00:45:54 UTC-4, Simon Wright wrote: >> Warren <ve3wwg@gmail.com> writes: >> >> type Node_Type(Obj: access Object_Type) is new Emb_Node >> with null record; > > I've come to the conclusion that my original idea in Ada terms is too half baked. > > What it will come down to in the end is doing an offset calculation > from the Node back to the Object when its access is required (through a > function). > > Even in C/C++ this is a bit of a problem. While there is an > offsetof(type,member) macro, this is only usable on non-dynamic types. > Calculating an offset of a struct is trivial when you have it allocated. > But when the class has a constructor, then you may not want to invoke > that overhead only to create one for offset calculations. > > In Ada for some record Type R.M where R is the record and M is the > member, you cannot do R.M'Position when R is just a type. But you can > cheat this, similar to how I have done it in C/C++: > > with System; > with Ada.Integer_Text_IO; > > procedure T is > use Ada.Integer_Text_IO; > > type R_Type is > record > I : Integer; > F : Float; > end record; > > A: System.Address; > > R: R_Type; > for R'Address use A; > > begin > Put(R.I'Position); > Put(R.F'Position); > end; > > This never allocates the object, but assumes it already exists at > address A.. Since the record and its members are never actually used, it > is possible to have the compiler do the necessary calculations. This > will complain "warning: variable "A" is read but never assigned", however. > > I suppose a tagged R.Initialize could also establish an 'Access value > in all Emb_Node members, using some other procedure call for Emb_Node > (perhaps Set_Object). But it is desireable not to have to carry the > object reference in the Emb_Node at all. Maybe I don't understand the problem, but it seems you want externally linked objects that themselves were of any type. The best way to do it is IMO a custom memory pool. My implementation of linked list uses this approach. http://www.dmitry-kazakov.de/ada/components.htm#Generic_Doubly_Linked_Web The object is allocated in the custom pool, which actually takes memory from another, e.g. standard, pool. But before that adds links just in front of the object. The pool-specific pointer carries the operations Next, Previous etc. Yes, it uses address arithmetic to get to the links, but no record member offsets or other crazy stuff because you deal with pointers to the objects, not the pointers to the list elements. The only problem you must be aware of is that X'Address attribute is broken in Ada when X is an array: X'Address = X (X'First)'Address which if of course not the address of the array. If you are going to instantiate your package with an array type, you must calculate the offset to the array object beginning. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 19:04 ` Dmitry A. Kazakov @ 2016-06-19 20:13 ` Warren 2016-06-19 20:35 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-19 20:13 UTC (permalink / raw) On Sunday, 19 June 2016 15:04:05 UTC-4, Dmitry A. Kazakov wrote: > Maybe I don't understand the problem, but it seems you want externally > linked objects that themselves were of any type. Close, but not quite. I had been toying with the idea that each node point back to the containing object, but I've dropped that clumsy idea now. Now I am back to the original C idea of converting a Node reference back to its containing object through pointer arithmetic (I know: Ada fans gasping). In short, given a Node, I need to get its containing Object. > The best way to do it is IMO a custom memory pool. The problem I have with that is performance. For example deleting a node from a list. procedure Delete ( Brand : List_Identification_Type; Container : in out Web; Element : in out Node ); To delete the node, in the worst case, requires traversing the entire list. My lists can be 30,000+ long. In the embedded node case, I already have direct access to the affected link node. To remove the node from a list I simply say: R.Link_Node.Unlink; and it removes itself out of the doubly linked list (else does nothing if not already in a list). I have considered a memory pool and not ruled it out. Presently I have an generic Object_Of(Node) function working, which makes use of System.Storage_Elements."+" (gasp!) The only drawback is that I need a fake instance of the Object to determine Node'Position at startup. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 20:13 ` Warren @ 2016-06-19 20:35 ` Dmitry A. Kazakov 2016-06-20 2:42 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-19 20:35 UTC (permalink / raw) On 2016-06-19 22:13, Warren wrote: > On Sunday, 19 June 2016 15:04:05 UTC-4, Dmitry A. Kazakov wrote: >> Maybe I don't understand the problem, but it seems you want externally >> linked objects that themselves were of any type. > > Close, but not quite. I had been toying with the idea that each node > point back to the containing object, but I've dropped that clumsy idea now. You don't need that as you can calculate it from the object address. You know the element head size and the alignment of the object (from Allocate). This gives you the offset. >> The best way to do it is IMO a custom memory pool. > > The problem I have with that is performance. For example deleting a > node from a list. > > procedure Delete > ( Brand : List_Identification_Type; > Container : in out Web; > Element : in out Node > ); > > To delete the node, in the worst case, requires traversing the > entire list. My lists can be 30,000+ long. No, doubly-linked list deletion is O(1). > In the embedded node case, I already have direct access to the > affected link node. To remove the node from a list I simply say: > > R.Link_Node.Unlink; The operation Delete has the list head parameter (Container) not for traversing the list, but for modifying the list head if the first element is deleted from the list. If you don't have it, you must maintain a dedicated list head element with no object attached. That is a less safe and clean because it ultimately leads to run-time type checks in the client code. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-19 20:35 ` Dmitry A. Kazakov @ 2016-06-20 2:42 ` Warren 2016-06-20 7:25 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-20 2:42 UTC (permalink / raw) On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov wrote: > On 2016-06-19 22:13, Warren wrote: > > On Sunday, 19 June 2016 15:04:05 UTC-4, Dmitry A. Kazakov wrote: > >> Maybe I don't understand the problem, but it seems you want externally > >> linked objects that themselves were of any type. > > > > Close, but not quite. I had been toying with the idea that each node > > point back to the containing object, but I've dropped that clumsy idea now. > > You don't need that as you can calculate it from the object address. You > know the element head size and the alignment of the object (from > Allocate). This gives you the offset. With the embedded list nodes, the calculation is a little different, but done along the same lines. You take the Node address and subtract to get to the containing object. But this design means you only allocate ONE object for list node and object together. Like I've said in the beginning, I am only considering embedded list nodes for higher performance reasons. The embedded list operations are so simple they can be inlined with virtually no code or performance penalty. > >> The best way to do it is IMO a custom memory pool. > > > > The problem I have with that is performance. For example deleting a > > node from a list. > > > > procedure Delete > > ( Brand : List_Identification_Type; > > Container : in out Web; > > Element : in out Node > > ); > > > > To delete the node, in the worst case, requires traversing the > > entire list. My lists can be 30,000+ long. > > No, doubly-linked list deletion is O(1). Ok you're tracking the link in Element, which is fine. However, your Element also needs a reference to the separately allocated object (which is a problem for me). This requires two allocations instead of one. I only need to insert head, traversal and delete. That's it! > > In the embedded node case, I already have direct access to the > > affected link node. To remove the node from a list I simply say: > > > > R.Link_Node.Unlink; > > The operation Delete has the list head parameter (Container) not for > traversing the list, but for modifying the list head if the first > element is deleted from the list. > If you don't have it, you must maintain a dedicated list head element > with no object attached. That is a less safe and clean because it > ultimately leads to run-time type checks in the client code. I agree with the dedicated list head statement, but not the "less safe" part. You either have container or you have a list head (each represents one list, though yours potentially several). There is nothing to check about a list head- you simply begin there. If you have no "head.next", you have an empty list. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-20 2:42 ` Warren @ 2016-06-20 7:25 ` Dmitry A. Kazakov 2016-06-20 12:26 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-20 7:25 UTC (permalink / raw) On 20/06/2016 04:42, Warren wrote: > On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov wrote: >> No, doubly-linked list deletion is O(1). > > Ok you're tracking the link in Element, which is fine. However, your > Element also needs a reference to the separately allocated object (which > is a problem for me). This requires two allocations instead of one. No, that is the point. The object and the element (links) are in one continuous chunk of memory. I believe this is what you meant under being "embedded" nodes. When an object is allocated, element + object is instead and the address to the object's part is returned back from Allocate. Deallocate takes the object's address, subtracts the offset and deallocates the whole chunk. > I only need to insert head, traversal and delete. That's it! Yes, and the schema above is as effective as it can be. >>> In the embedded node case, I already have direct access to the >>> affected link node. To remove the node from a list I simply say: >>> >>> R.Link_Node.Unlink; >> >> The operation Delete has the list head parameter (Container) not for >> traversing the list, but for modifying the list head if the first >> element is deleted from the list. > >> If you don't have it, you must maintain a dedicated list head element >> with no object attached. That is a less safe and clean because it >> ultimately leads to run-time type checks in the client code. > > I agree with the dedicated list head statement, but not the "less > safe" part. You either have container or you have a list head (each > represents one list, though yours potentially several). > > There is nothing to check about a list head- you simply begin there. > If you have no "head.next", you have an empty list. Not with doubly-linked lists. There is always Next, because the list is circular. When you delete an element from the list you always get two lists. Deletion of a single element is an idempotent operation unless you have a dedicated head or else have the list head pointer corrected. List traversal when the list head is a pointer is performed like this: if Head /= null then This := Head; loop ... -- Do something This := This.Next; exit when This = Head; end loop; end if; -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-20 7:25 ` Dmitry A. Kazakov @ 2016-06-20 12:26 ` Warren 2016-06-20 19:33 ` Niklas Holsti 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-20 12:26 UTC (permalink / raw) On Monday, 20 June 2016 03:25:48 UTC-4, Dmitry A. Kazakov wrote: > On 20/06/2016 04:42, Warren wrote: > > On Sunday, 19 June 2016 16:35:32 UTC-4, Dmitry A. Kazakov wrote: > >> No, doubly-linked list deletion is O(1). > > > > Ok you're tracking the link in Element, which is fine. However, your > > Element also needs a reference to the separately allocated object (which > > is a problem for me). This requires two allocations instead of one. > > No, that is the point. The object and the element (links) are in one > continuous chunk of memory. I believe this is what you meant under being > "embedded" nodes. > > When an object is allocated, element + object is instead and the address > to the object's part is returned back from Allocate. Deallocate takes > the object's address, subtracts the offset and deallocates the whole chunk. > > > I only need to insert head, traversal and delete. That's it! > > Yes, and the schema above is as effective as it can be. > > >>> In the embedded node case, I already have direct access to the > >>> affected link node. To remove the node from a list I simply say: > >>> > >>> R.Link_Node.Unlink; > >> > >> The operation Delete has the list head parameter (Container) not for > >> traversing the list, but for modifying the list head if the first > >> element is deleted from the list. > > > >> If you don't have it, you must maintain a dedicated list head element > >> with no object attached. That is a less safe and clean because it > >> ultimately leads to run-time type checks in the client code. > > > > I agree with the dedicated list head statement, but not the "less > > safe" part. You either have container or you have a list head (each > > represents one list, though yours potentially several). > > > > There is nothing to check about a list head- you simply begin there. > > If you have no "head.next", you have an empty list. > > Not with doubly-linked lists. There is always Next, because the list is > circular. Mine ain't. > When you delete an element from the list you always get two > lists. Deletion of a single element is an idempotent operation unless > you have a dedicated head or else have the list head pointer corrected. In my list, when the last item is removed from the list, Head.Next = Null. Simple. > List traversal when the list head is a pointer is performed like this: > > if Head /= null then > This := Head; > loop > ... -- Do something > This := This.Next; > exit when This = Head; > end loop; > end if; delcare Node: access Emb_Node := Head.Next; begin while Node loop -- do something with node Node := Node.Next; end loop; end; Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-20 12:26 ` Warren @ 2016-06-20 19:33 ` Niklas Holsti 2016-06-21 2:20 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Niklas Holsti @ 2016-06-20 19:33 UTC (permalink / raw) On 16-06-20 15:26 , Warren wrote: > Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread. Before signing off, do please describe your solution. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-20 19:33 ` Niklas Holsti @ 2016-06-21 2:20 ` Warren 2016-06-21 5:52 ` Niklas Holsti 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-21 2:20 UTC (permalink / raw) On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti wrote: > On 16-06-20 15:26 , Warren wrote: > > > Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread. > > Before signing off, do please describe your solution. I thought I had the problem licked using the following generic Object_Of function, but when I whipped up an example, the compile problem returned (or there was pilot error): function Object_Of( Node: access Emb_Node; Member: Natural ) return Object_Type is use System.Storage_Elements; A: constant System.Address := Node.all'Address; B: constant System.Address := A - Storage_Offset(Member); R: Object_Type; for R'Address use B; pragma Import(Convention => Ada, Entity => R); begin return R; end Object_Of; The compiler is complaining with: warning: controlled object "R" must not be overlaid. The test record looks like this: type My_Recd is record ID: Natural; Node: aliased Emb_Node; Name: Unbounded_String; end record; and the Emb_Node looks like this: type Emb_Node is record Next: access Emb_Node; Prev: access Emb_Node; end record; The Node member is one culprit because it has two Access members (which count as members needing initialization). Unbounded_String may be another factor. What is particularly galling about this is that the record already exists, and does NOT need initialization at this point. All I need the compiler do is return it to me based upon its address. Arg! To accomplish this, I may have to resort to invoking a C function. But I don't think that will work either. Not by System.Address at least. More head scratching to follow. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 2:20 ` Warren @ 2016-06-21 5:52 ` Niklas Holsti 2016-06-21 7:15 ` Dmitry A. Kazakov 2016-06-21 10:31 ` Warren 0 siblings, 2 replies; 52+ messages in thread From: Niklas Holsti @ 2016-06-21 5:52 UTC (permalink / raw) On 16-06-21 05:20 , Warren wrote: > On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti wrote: >> On 16-06-20 15:26 , Warren wrote: >> >>> Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread. >> >> Before signing off, do please describe your solution. > > I thought I had the problem licked using the following generic > Object_Of function, but when I whipped up an example, the compile > problem returned (or there was pilot error): > > function Object_Of( > Node: access Emb_Node; > Member: Natural > ) return Object_Type is > use System.Storage_Elements; > > A: constant System.Address := Node.all'Address; > B: constant System.Address := A - Storage_Offset(Member); > R: Object_Type; > for R'Address use B; > pragma Import(Convention => Ada, Entity => R); > begin > return R; > end Object_Of; > > The compiler is complaining with: > > warning: controlled object "R" must not be overlaid. The component My_Recd.Name, of the controlled type Unbounded_String, is making Object_Type also controlled. I well understand that the compiler does not want controlled objects to be overlaid with address clauses. Instead of a function returning Object_Type, you could try returning an access to Object_Type, as produced by an instance of System.Address_To_Access_Conversions. In fact, if I understand your goals, you do not want Object_Of to return a _copy_ of the object containing the Emb_Node, the need is to _find_ that very object. Returning an access value is closer to what you want, I believe. > The test record looks like this: > > type My_Recd is > record > ID: Natural; > Node: aliased Emb_Node; > Name: Unbounded_String; > end record; If you don't get the address arithmetic to work, I believe that a set of mixin-generics could be used to add as many embedded Emb_Nodes to a tagged limited record, with access discriminants pointing to the containing record. This would eliminate the address arithmetic, at the cost of increasing the size of the record by the sizes of the discriminants (not a great deal). -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 5:52 ` Niklas Holsti @ 2016-06-21 7:15 ` Dmitry A. Kazakov 2016-06-21 18:54 ` Niklas Holsti 2016-06-21 10:31 ` Warren 1 sibling, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-21 7:15 UTC (permalink / raw) On 21/06/2016 07:52, Niklas Holsti wrote: > If you don't get the address arithmetic to work, There is a subtle difference between access and X'Address, but otherwise address arithmetic works. E.g. I can instantiate my implementation of linked lists with any type including unconstrained and non-tagged ones. > I believe that a set of > mixin-generics could be used to add as many embedded Emb_Nodes to a > tagged limited record, with access discriminants pointing to the > containing record. Adding links afterwards is even worse than deriving objects from a abstract list node. Any derivation must be used sparingly in Ada which does not have full multiple inheritance. Once you have spent the proper parent type you won't get another one. > This would eliminate the address arithmetic, at the > cost of increasing the size of the record by the sizes of the > discriminants (not a great deal). The advantage of pool-based design is that no address arithmetic is needed for object operations. The list element is access to the object type. Address arithmetic is needed for list operations only. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 7:15 ` Dmitry A. Kazakov @ 2016-06-21 18:54 ` Niklas Holsti 2016-06-21 19:54 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Niklas Holsti @ 2016-06-21 18:54 UTC (permalink / raw) On 16-06-21 10:15 , Dmitry A. Kazakov wrote: > On 21/06/2016 07:52, Niklas Holsti wrote: > >> If you don't get the address arithmetic to work, > > There is a subtle difference between access and X'Address, but otherwise > address arithmetic works. E.g. I can instantiate my implementation of > linked lists with any type including unconstrained and non-tagged ones. > >> I believe that a set of >> mixin-generics could be used to add as many embedded Emb_Nodes to a >> tagged limited record, with access discriminants pointing to the >> containing record. > > Adding links afterwards is even worse than deriving objects from a > abstract list node. Why do you think so? For philosophical or practical reasons? > Any derivation must be used sparingly in Ada which > does not have full multiple inheritance. Once you have spent the proper > parent type you won't get another one. Mixin-generics are a work-around, but can be practical, IMO. On the other hand, it seems the OP is in control of and defines the object types, so embedded link nodes can be added manually without using generics, just by deriving object-specific types with suitable access discriminants from a root "embedded-link-node" type. >> This would eliminate the address arithmetic, at the >> cost of increasing the size of the record by the sizes of the >> discriminants (not a great deal). > > The advantage of pool-based design is that no address arithmetic is > needed for object operations. The list element is access to the object > type. Address arithmetic is needed for list operations only. But your pool-based design restricts objects to be linked into at most one list. The OP said that an object can be placed in two or more lists at the same time, and apparently the number of such lists varies according to the type of the object, depending on the number of embedded list nodes within the object. The pool-based design can no doubt be extended to allow multiple lists, but it then becomes more complex. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 18:54 ` Niklas Holsti @ 2016-06-21 19:54 ` Dmitry A. Kazakov 0 siblings, 0 replies; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-21 19:54 UTC (permalink / raw) On 2016-06-21 20:54, Niklas Holsti wrote: > On 16-06-21 10:15 , Dmitry A. Kazakov wrote: >> On 21/06/2016 07:52, Niklas Holsti wrote: >> >>> If you don't get the address arithmetic to work, >> >> There is a subtle difference between access and X'Address, but otherwise >> address arithmetic works. E.g. I can instantiate my implementation of >> linked lists with any type including unconstrained and non-tagged ones. >> >>> I believe that a set of >>> mixin-generics could be used to add as many embedded Emb_Nodes to a >>> tagged limited record, with access discriminants pointing to the >>> containing record. >> >> Adding links afterwards is even worse than deriving objects from a >> abstract list node. > > Why do you think so? For philosophical or practical reasons? Practical reasons. If you derive from the list element base you cannot have scalar or other non-tagged objects as elements, but you still can have a class of elements. When you add links last, you cannot have a class, that in effect finalizes the list item. > But your pool-based design restricts objects to be linked into at most > one list. The OP said that an object can be placed in two or more lists > at the same time, and apparently the number of such lists varies > according to the type of the object, depending on the number of embedded > list nodes within the object. > > The pool-based design can no doubt be extended to allow multiple lists, > but it then becomes more complex. It is no more complex. In fact my design is multiple lists from the start. Doubly-linked list is a specialization of. BTW, a design based on inheritance requires multiple additive inheritance for lists. Ada does not have this even for interfaces. E.g. type Abstract_List_Item is abstract tagged record Next : not null access Abstract_List_Item'Class := Abstract_List_Item'Access; Previous : not null access Abstract_List_Item'Class := Abstract_List_Item'Access; end record; type My_List_Item is -- This is not Ada! new Abstract_List_Item as List_One or Abstract_List_Item as List_Two with record X : Integer; end record; Members and primitive operations are renamed to resolve name clashes. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 5:52 ` Niklas Holsti 2016-06-21 7:15 ` Dmitry A. Kazakov @ 2016-06-21 10:31 ` Warren 2016-06-21 17:13 ` Jeffrey R. Carter ` (2 more replies) 1 sibling, 3 replies; 52+ messages in thread From: Warren @ 2016-06-21 10:31 UTC (permalink / raw) On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti wrote: > On 16-06-21 05:20 , Warren wrote: > > On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti wrote: > >> On 16-06-20 15:26 , Warren wrote: > >> > >>> Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread. > >> > >> Before signing off, do please describe your solution. > > > > I thought I had the problem licked using the following generic > > Object_Of function, but when I whipped up an example, the compile > > problem returned (or there was pilot error): > > > > function Object_Of( > > Node: access Emb_Node; > > Member: Natural > > ) return Object_Type is > > use System.Storage_Elements; > > > > A: constant System.Address := Node.all'Address; > > B: constant System.Address := A - Storage_Offset(Member); > > R: Object_Type; > > for R'Address use B; > > pragma Import(Convention => Ada, Entity => R); > > begin > > return R; > > end Object_Of; > > > > The compiler is complaining with: > > > > warning: controlled object "R" must not be overlaid. > > The component My_Recd.Name, of the controlled type Unbounded_String, is > making Object_Type also controlled. I well understand that the compiler > does not want controlled objects to be overlaid with address clauses. > > Instead of a function returning Object_Type, you could try returning an > access to Object_Type, as produced by an instance of > System.Address_To_Access_Conversions. In fact, if I understand your > goals, you do not want Object_Of to return a _copy_ of the object > containing the Emb_Node, the need is to _find_ that very object. > Returning an access value is closer to what you want, I believe. That is correct (no copy). The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 10:31 ` Warren @ 2016-06-21 17:13 ` Jeffrey R. Carter 2016-06-21 18:56 ` Niklas Holsti 2016-06-21 21:38 ` Niklas Holsti 2016-06-22 13:01 ` G.B. 2 siblings, 1 reply; 52+ messages in thread From: Jeffrey R. Carter @ 2016-06-21 17:13 UTC (permalink / raw) On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti wrote: > > The component My_Recd.Name, of the controlled type Unbounded_String, is > making Object_Type also controlled. I well understand that the compiler > does not want controlled objects to be overlaid with address clauses. Funny how this application cannot possibly meet its timing requirements if it does any allocation/deallocation, yet can meet its timing requirements using Unbounded_String, which does allocation/deallocation internally. -- Jeff Carter "You couldn't catch clap in a brothel, silly English K...niggets." Monty Python & the Holy Grail 19 ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 17:13 ` Jeffrey R. Carter @ 2016-06-21 18:56 ` Niklas Holsti 2016-06-21 20:13 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Niklas Holsti @ 2016-06-21 18:56 UTC (permalink / raw) On 16-06-21 20:13 , Jeffrey R. Carter wrote: > On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti wrote: >> >> The component My_Recd.Name, of the controlled type Unbounded_String, is >> making Object_Type also controlled. I well understand that the compiler >> does not want controlled objects to be overlaid with address clauses. > > Funny how this application cannot possibly meet its timing requirements if it > does any allocation/deallocation, yet can meet its timing requirements using > Unbounded_String, which does allocation/deallocation internally. Perhaps the Unbounded_Strings are altered very rarely, but the linked-list operations are frequent. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 18:56 ` Niklas Holsti @ 2016-06-21 20:13 ` Warren 0 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-06-21 20:13 UTC (permalink / raw) On Tuesday, 21 June 2016 14:56:06 UTC-4, Niklas Holsti wrote: > On 16-06-21 20:13 , Jeffrey R. Carter wrote: > > On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti wrote: > >> > >> The component My_Recd.Name, of the controlled type Unbounded_String, is > >> making Object_Type also controlled. I well understand that the compiler > >> does not want controlled objects to be overlaid with address clauses. > > > > Funny how this application cannot possibly meet its timing requirements if it > > does any allocation/deallocation, yet can meet its timing requirements using > > Unbounded_String, which does allocation/deallocation internally. > > Perhaps the Unbounded_Strings are altered very rarely, but the > linked-list operations are frequent. I only added the Unbounded_String for an example test program because Niklas wanted to see what I was going to use. So now I'll just leave the group to expend their excess energy on any further debate. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 10:31 ` Warren 2016-06-21 17:13 ` Jeffrey R. Carter @ 2016-06-21 21:38 ` Niklas Holsti 2016-06-23 2:12 ` Warren 2016-06-22 13:01 ` G.B. 2 siblings, 1 reply; 52+ messages in thread From: Niklas Holsti @ 2016-06-21 21:38 UTC (permalink / raw) On 16-06-21 13:31 , Warren wrote: > On Tuesday, 21 June 2016 01:52:51 UTC-4, Niklas Holsti wrote: >> On 16-06-21 05:20 , Warren wrote: >>> On Monday, 20 June 2016 15:33:16 UTC-4, Niklas Holsti wrote: >>>> On 16-06-20 15:26 , Warren wrote: >>>> >>>>> Anyway folks- thanks for your help but I now have a working solution. I'm signing off this thread. >>>> >>>> Before signing off, do please describe your solution. >>> >>> I thought I had the problem licked using the following generic >>> Object_Of function, but when I whipped up an example, the compile >>> problem returned (or there was pilot error): >>> >>> function Object_Of( >>> Node: access Emb_Node; >>> Member: Natural >>> ) return Object_Type is >>> use System.Storage_Elements; >>> >>> A: constant System.Address := Node.all'Address; >>> B: constant System.Address := A - Storage_Offset(Member); >>> R: Object_Type; >>> for R'Address use B; >>> pragma Import(Convention => Ada, Entity => R); >>> begin >>> return R; >>> end Object_Of; >>> >>> The compiler is complaining with: >>> >>> warning: controlled object "R" must not be overlaid. >> >> The component My_Recd.Name, of the controlled type Unbounded_String, is >> making Object_Type also controlled. I well understand that the compiler >> does not want controlled objects to be overlaid with address clauses. >> >> Instead of a function returning Object_Type, you could try returning an >> access to Object_Type, as produced by an instance of >> System.Address_To_Access_Conversions. In fact, if I understand your >> goals, you do not want Object_Of to return a _copy_ of the object >> containing the Emb_Node, the need is to _find_ that very object. >> Returning an access value is closer to what you want, I believe. > > That is correct (no copy). The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain. It now seems to me that the solutions suggested so far are too elaborate, and that a very simple solution exists: an embedded list node is just an ordinary component, derived from a tagged root type which holds the Prev and Next links, with an access discriminant referring to the containing object. The OP asked for a "generic" solution, but IMO a generic would not be simpler than this direct form. Example code follows. Compiled but not tested. package Emb_List is -- The class of "embedded list nodes": type Emb_Node_T is tagged; type Emb_Node_Ref_T is access all Emb_Node_T'Class; type Emb_Node_T is tagged record Prev, Next : Emb_Node_Ref_T; -- Prev and Next are null if the node is not in any list. -- When the node is first in a list, Prev points to the list head. -- When the node is last in a list, Next is null. end record; subtype List_T is Emb_Node_T; -- A list head. -- Next points to the first node in the list. -- Prev is null. procedure Insert_At_Head ( List : access List_T; Node : in Emb_Node_Ref_T); -- Prepends Node at the head of the list. -- Assumes that Node is not in any list, to start with. procedure Delete (Node : in Emb_Node_Ref_T); -- Deletes the Node from the list it lies in, assuming that -- the Node does lie in a list. -- An example type with two embedded list nodes: type Integer_Object_T; type Integer_Emb_Node_T (Obj : access Integer_Object_T) is new Emb_Node_T with null record; type Integer_Object_T is limited record Value : Integer; Node1 : aliased Integer_Emb_Node_T (Integer_Object_T'Access); Node2 : aliased Integer_Emb_Node_T (Integer_Object_T'Access); end record; -- An example object: Int_Obj : Integer_Object_T; -- Two example lists, empty by default: List1, List2 : aliased List_T; end Emb_List; package body Emb_List is procedure Insert_At_Head ( List : access List_T; Node : in Emb_Node_Ref_T) is begin List.Next.Prev := Node; Node.Next := List.Next; List.Next := Node; Node.Prev := Emb_Node_Ref_T (List); end Insert_At_Head; procedure Delete (Node : in Emb_Node_Ref_T) is begin Node.Prev.Next := Node.Next; Node.Next.Prev := Node.Prev; Node.Prev := null; Node.Next := null; end Delete; begin -- Add the example object to the example lists: Insert_At_Head (List1'Access, Int_Obj.Node1'Access); Insert_At_Head (List2'Access, Int_Obj.Node2'Access); -- Delete from List2: Delete (Int_Obj.Node2'Access); end Emb_List; -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 21:38 ` Niklas Holsti @ 2016-06-23 2:12 ` Warren 2016-06-23 8:19 ` Niklas Holsti 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-23 2:12 UTC (permalink / raw) On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti wrote: ... > type Emb_Node_T is tagged; > > type Emb_Node_Ref_T is access all Emb_Node_T'Class; > > type Emb_Node_T is tagged record > Prev, Next : Emb_Node_Ref_T; > -- Prev and Next are null if the node is not in any list. > -- When the node is first in a list, Prev points to the list head. > -- When the node is last in a list, Next is null. > end record; > > subtype List_T is Emb_Node_T; > -- A list head. > -- Next points to the first node in the list. > -- Prev is null. ... The insertion, traversal and deletes are generally no problem. The problem occurs when traversing to access the object. Let's say you have a list of timed out sockets (in pseudo code): node := head.next; while node /= null loop next_node := node.next; -- now access the object holding "node" so that it can be freed node.unlink; Free(node's object); node := node_next; end loop; I keep bumping back into this Ada compiler restriction, which is maddening. It doesn't seem easily fooled. I think the only simple way to do this in Ada, is to allocate a very large array of Access to record values, for each socket (I know what the max # of sockets are). The descriptors start at zero so this works well. The list link nodes can easily save and allow me to retrieve the POSIX socket (fd) number without any compiler restrictions. So when I traverse to a given node, I can pull the fd out of the link node, and know that I have socket 90345, for example. Then I can index to the socket's event record access value in the array. Normally, I already know the fd in the event handler epoll/kqueue, but the lists get traversed for timeouts and deferred closes. So given a timeout node for example, I need to be able to get the object that belongs to it so I can do things like free it etc. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-23 2:12 ` Warren @ 2016-06-23 8:19 ` Niklas Holsti 2016-06-23 12:37 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Niklas Holsti @ 2016-06-23 8:19 UTC (permalink / raw) On 16-06-23 05:12 , Warren wrote: > On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti wrote: > ... >> type Emb_Node_T is tagged; >> >> type Emb_Node_Ref_T is access all Emb_Node_T'Class; >> >> type Emb_Node_T is tagged record >> Prev, Next : Emb_Node_Ref_T; >> -- Prev and Next are null if the node is not in any list. >> -- When the node is first in a list, Prev points to the list head. >> -- When the node is last in a list, Next is null. >> end record; >> >> subtype List_T is Emb_Node_T; >> -- A list head. >> -- Next points to the first node in the list. >> -- Prev is null. > ... > > The insertion, traversal and deletes are generally no problem. The problem > occurs when traversing to access the object. Indeed I left out an example of traversal, sorry. > Let's say you have a list of timed out sockets (in pseudo code): > > node := head.next; > while node /= null loop > next_node := node.next; > -- now access the object holding "node" so that it can be freed > node.unlink; > Free(node's object); > node := node_next; (You surely meant next_node, above.) > end loop; > > I keep bumping back into this Ada compiler restriction, which is > maddening. It doesn't seem easily fooled. That's the reason for having the derived descendants of Emb_Node_T, with the access discriminants. In my example, the discriminant Obj of an embedded Integer_Emb_Node_T points to the enclosing Integer_Object_T. Here is the relevant part of the example; to place it in the context of your example, above, imagine that Integer_Object_T is a potentially "time out socket": type Integer_Object_T; type Integer_Emb_Node_T (Obj : access Integer_Object_T) is new Emb_Node_T with null record; -- (Explanation added:) Obj accesses the Integer_Object_T -- which contains this Integer_Emb_Node_T. type Integer_Object_T is limited record Value : Integer; Node1 : aliased Integer_Emb_Node_T (Integer_Object_T'Access); Node2 : aliased Integer_Emb_Node_T (Integer_Object_T'Access); end record; The Obj pointers are set automatically by the expressions Integer_Object_T'Access, which access the current instance of Integer_Object_T. Here's a procedure to print out the Value components of all Integer_Object_T elements in a list of such elements: procedure Print_Integer_Values (List : in List_T'Class) is Node : Emb_Node_Ref_T := List.Next; begin while Node /= null loop if Node.all in Integer_Emb_Node_T'Class then Ada.Integer_Text_IO.Put ( Integer_Emb_Node_T (Node.all).Obj.Value); end if; Node := Node.Next; end loop; end Print_Values; (Compiled, not tested.) By the way, the solution example I gave assumed that you want heterogeneous lists, in which any list can contain any type of object. That's why the above procedure Print_Integer_Values has to check if the current Node is an Integer_Obj_T before it can use the Obj discriminant to get to the object. If you actually want homogeneous lists, in which any given list contains only elements of one and the same type, which corresponds to the type of the list head, I would drop the root type Emb_Node_T and define each embedded-node type separately from scratch. In this case a generic package to create doubly linked lists of a given type could be useful. If this is your preference, say it and I will make an example for you. > I think the only simple way to do this in Ada, is to allocate > a very large array of Access to record values, for each socket > (I know what the max # of sockets are). The descriptors start at > zero so this works well. That would also work. Your choice, of course. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-23 8:19 ` Niklas Holsti @ 2016-06-23 12:37 ` Warren 2016-06-23 15:36 ` Niklas Holsti 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-23 12:37 UTC (permalink / raw) On Thursday, 23 June 2016 04:19:35 UTC-4, Niklas Holsti wrote: > On 16-06-23 05:12 , Warren wrote: > > On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti wrote: > > ... > >> type Emb_Node_T is tagged; > >> > >> type Emb_Node_Ref_T is access all Emb_Node_T'Class; > >> > >> type Emb_Node_T is tagged record > >> Prev, Next : Emb_Node_Ref_T; > >> -- Prev and Next are null if the node is not in any list. > >> -- When the node is first in a list, Prev points to the list head. > >> -- When the node is last in a list, Next is null. > >> end record; > >> > >> subtype List_T is Emb_Node_T; > >> -- A list head. > >> -- Next points to the first node in the list. > >> -- Prev is null. > > ... > > > > The insertion, traversal and deletes are generally no problem. The problem > > occurs when traversing to access the object. > > Indeed I left out an example of traversal, sorry. No problem. The other issue is that I need to support at least two lists. It gets rather messy when extending the object for each additional list, IMO. I think the large array is going to work best with a list of nodes carrying file descriptors. That's not a general solution but it works where I need it. The array wasn't necessary for the C++ version, but I could have used that there as well. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-23 12:37 ` Warren @ 2016-06-23 15:36 ` Niklas Holsti 2016-06-24 1:55 ` Warren ` (2 more replies) 0 siblings, 3 replies; 52+ messages in thread From: Niklas Holsti @ 2016-06-23 15:36 UTC (permalink / raw) On 16-06-23 15:37 , Warren wrote: > On Thursday, 23 June 2016 04:19:35 UTC-4, Niklas Holsti wrote: >> On 16-06-23 05:12 , Warren wrote: >>> On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti wrote: >>> ... >>>> type Emb_Node_T is tagged; >>>> >>>> type Emb_Node_Ref_T is access all Emb_Node_T'Class; >>>> >>>> type Emb_Node_T is tagged record >>>> Prev, Next : Emb_Node_Ref_T; >>>> -- Prev and Next are null if the node is not in any list. >>>> -- When the node is first in a list, Prev points to the list head. >>>> -- When the node is last in a list, Next is null. >>>> end record; >>>> >>>> subtype List_T is Emb_Node_T; >>>> -- A list head. >>>> -- Next points to the first node in the list. >>>> -- Prev is null. >>> ... >>> >>> The insertion, traversal and deletes are generally no problem. The problem >>> occurs when traversing to access the object. >> >> Indeed I left out an example of traversal, sorry. > > No problem. The other issue is that I need to support at least > two lists. It gets rather messy when extending the object for > each additional list, IMO. My example had two embedded list nodes in the object, so the object could be a member of two lists. You can define as many nodes as you like, in the same record type, at the same time. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-23 15:36 ` Niklas Holsti @ 2016-06-24 1:55 ` Warren 2016-06-24 12:49 ` Warren 2016-06-24 20:25 ` Warren 2 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-06-24 1:55 UTC (permalink / raw) On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti wrote: > On 16-06-23 15:37 , Warren wrote: > > On Thursday, 23 June 2016 04:19:35 UTC-4, Niklas Holsti wrote: > >> On 16-06-23 05:12 , Warren wrote: > >>> On Tuesday, 21 June 2016 17:38:36 UTC-4, Niklas Holsti wrote: > >>> ... > >>>> type Emb_Node_T is tagged; > >>>> > >>>> type Emb_Node_Ref_T is access all Emb_Node_T'Class; > >>>> > >>>> type Emb_Node_T is tagged record > >>>> Prev, Next : Emb_Node_Ref_T; > >>>> -- Prev and Next are null if the node is not in any list. > >>>> -- When the node is first in a list, Prev points to the list head. > >>>> -- When the node is last in a list, Next is null. > >>>> end record; > >>>> > >>>> subtype List_T is Emb_Node_T; > >>>> -- A list head. > >>>> -- Next points to the first node in the list. > >>>> -- Prev is null. > >>> ... > >>> > >>> The insertion, traversal and deletes are generally no problem. The problem > >>> occurs when traversing to access the object. > >> > >> Indeed I left out an example of traversal, sorry. > > > > No problem. The other issue is that I need to support at least > > two lists. It gets rather messy when extending the object for > > each additional list, IMO. > > My example had two embedded list nodes in the object, so the object > could be a member of two lists. You can define as many nodes as you > like, in the same record type, at the same time. Ok, I see now (my eyes get bad by end of day after staring at screens all day). I've been thinking today that by using the file descriptor as an index into a large array (of access to records), I can make this relatively clean in Ada. The array would not only act as a lookup for the event structures, but serve as a cache of such. I never really need to release them. If I did want to reclaim any, I could start at the high end of the array, since those will be used under heaviest use. This is one of the nice features of the Unix kernel- open files always have the lowest available unit numbers assigned. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-23 15:36 ` Niklas Holsti 2016-06-24 1:55 ` Warren @ 2016-06-24 12:49 ` Warren 2016-06-25 5:50 ` Niklas Holsti 2016-06-24 20:25 ` Warren 2 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-24 12:49 UTC (permalink / raw) On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti wrote: > My example had two embedded list nodes in the object, so the object > could be a member of two lists. You can define as many nodes as you > like, in the same record type, at the same time. Sorry, yes I see it now. > type Integer_Object_T; > > type Integer_Emb_Node_T (Obj : access Integer_Object_T) > is new Emb_Node_T with null record; I think when I had tried to do this, I had the chicken and egg problem. But I see you used the forward undefined type mechanism. I may explore this further at some point-- it certainly seems to solve the problem as I laid it out. I just need to find some quiet time. Thanks for the help. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-24 12:49 ` Warren @ 2016-06-25 5:50 ` Niklas Holsti 2016-06-26 1:36 ` Warren 2016-07-01 13:49 ` Warren 0 siblings, 2 replies; 52+ messages in thread From: Niklas Holsti @ 2016-06-25 5:50 UTC (permalink / raw) On 16-06-24 15:49 , Warren wrote: > On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti wrote: >> My example had two embedded list nodes in the object, so the object >> could be a member of two lists. You can define as many nodes as you >> like, in the same record type, at the same time. > > Sorry, yes I see it now. > >> type Integer_Object_T; >> >> type Integer_Emb_Node_T (Obj : access Integer_Object_T) > > is new Emb_Node_T with null record; > > I think when I had tried to do this, I had the chicken and egg problem. > But I see you used the forward undefined type mechanism. I may explore > this further at some point-- it certainly seems to solve the problem > as I laid it out. I just need to find some quiet time. Thanks for the help. You are very welcome, Warren. By the way, for record (so to speak), the procedures "Insert_At_Head" and "Delete" shown in my example each has an error: a possible use of a null reference. The versions below should be better, but they are still not tested. procedure Insert_At_Head ( List : access List_T; Node : in Emb_Node_Ref_T) is begin if List.Next /= null then List.Next.Prev := Node; end if; Node.Next := List.Next; List.Next := Node; Node.Prev := Emb_Node_Ref_T (List); end Insert_At_Head; procedure Delete (Node : in Emb_Node_Ref_T) is begin Node.Prev.Next := Node.Next; if Node.Next /= null then Node.Next.Prev := Node.Prev; end if; Node.Prev := null; Node.Next := null; end Delete; -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-25 5:50 ` Niklas Holsti @ 2016-06-26 1:36 ` Warren 2016-07-01 13:49 ` Warren 1 sibling, 0 replies; 52+ messages in thread From: Warren @ 2016-06-26 1:36 UTC (permalink / raw) On Saturday, 25 June 2016 01:50:41 UTC-4, Niklas Holsti wrote: ... > By the way, for record (so to speak), the procedures "Insert_At_Head" > and "Delete" shown in my example each has an error: a possible use of a > null reference. The versions below should be better, but they are still > not tested. I see google groups finally posted my attempts to reply. At this point, I think my best approach for this project will be to use a large array, since that will act as a cache in addition to a table of event records by file descriptor. Your approach may have application in another project. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-25 5:50 ` Niklas Holsti 2016-06-26 1:36 ` Warren @ 2016-07-01 13:49 ` Warren 2016-07-01 16:28 ` Warren 1 sibling, 1 reply; 52+ messages in thread From: Warren @ 2016-07-01 13:49 UTC (permalink / raw) On Saturday, 25 June 2016 01:50:41 UTC-4, Niklas Holsti wrote: > On 16-06-24 15:49 , Warren wrote: .. > procedure Insert_At_Head ( > List : access List_T; > Node : in Emb_Node_Ref_T) > is > begin > if List.Next /= null then > List.Next.Prev := Node; > end if; > Node.Next := List.Next; > List.Next := Node; > Node.Prev := Emb_Node_Ref_T (List); > end Insert_At_Head; Niklas: I finally got a few minutes to revisit this and worked up a full example based upon yours. I fear that the design is still flawed. I'm using a slightly modified version of this, but basically, the problem occurs at the line: > Node.Prev := Emb_Node_Ref_T (List); with the exception: raised PROGRAM_ERROR : niklas.adb:14 accessibility check failed My example code is located on github here: https://github.com/ve3wwg/ada_embedded_list Maybe there is pilot error somewhere. I'm using: GNATMAKE 6.1.0. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-07-01 13:49 ` Warren @ 2016-07-01 16:28 ` Warren 0 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-07-01 16:28 UTC (permalink / raw) On Friday, 1 July 2016 09:49:19 UTC-4, Warren wrote: > On Saturday, 25 June 2016 01:50:41 UTC-4, Niklas Holsti wrote: > > On 16-06-24 15:49 , Warren wrote: > .. > > procedure Insert_At_Head ( > > List : access List_T; > > Node : in Emb_Node_Ref_T) > > is > > begin > > if List.Next /= null then > > List.Next.Prev := Node; > > end if; > > Node.Next := List.Next; > > List.Next := Node; > > Node.Prev := Emb_Node_Ref_T (List); > > end Insert_At_Head; > > Niklas: I finally got a few minutes to revisit this and worked up a full example based upon yours. I fear that the design is still flawed. I'm using a slightly modified version of this, but basically, the problem occurs at the line: > > > Node.Prev := Emb_Node_Ref_T (List); > > with the exception: > > raised PROGRAM_ERROR : niklas.adb:14 accessibility check failed > > My example code is located on github here: https://github.com/ve3wwg/ada_embedded_list > > Maybe there is pilot error somewhere. I'm using: GNATMAKE 6.1.0. > > Warren Sorry, nevermind. When I allocate the list with: List1: aliased access List_T := new List_T; it is fine. I suppose that the runtime was worried about dangling pointers when it was originally allocated on the stack frame in: List1: aliased List_T; Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-23 15:36 ` Niklas Holsti 2016-06-24 1:55 ` Warren 2016-06-24 12:49 ` Warren @ 2016-06-24 20:25 ` Warren 2 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-06-24 20:25 UTC (permalink / raw) On Thursday, 23 June 2016 11:36:25 UTC-4, Niklas Holsti wrote: ... > My example had two embedded list nodes in the object, so the object > could be a member of two lists. You can define as many nodes as you > like, in the same record type, at the same time. I've tried twice now to post through google groups, but no luck. If this gets through, then know that I see those two lists. I'll reply more in full, if google sorts out the issue soon. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 10:31 ` Warren 2016-06-21 17:13 ` Jeffrey R. Carter 2016-06-21 21:38 ` Niklas Holsti @ 2016-06-22 13:01 ` G.B. 2016-06-23 2:30 ` Warren 2 siblings, 1 reply; 52+ messages in thread From: G.B. @ 2016-06-22 13:01 UTC (permalink / raw) On 21.06.16 12:31, Warren wrote: > The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain. At the risk of being non-C-ish, could you require the outer objects' type to have an operation that delivers its own 'Access, so that when linking the object via its embedded list thing, the latter could call said operation? ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-22 13:01 ` G.B. @ 2016-06-23 2:30 ` Warren 0 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-06-23 2:30 UTC (permalink / raw) On Wednesday, 22 June 2016 09:01:48 UTC-4, G.B. wrote: > On 21.06.16 12:31, Warren wrote: > > The suggestion for System.Address_To_Access_Conversions seems like a potential solution. The only other thing I can do is try to cheat with a C routine returning an address, but GNAT is just as likely to complain. > > At the risk of being non-C-ish, could you require the > outer objects' type to have an operation that delivers > its own 'Access, so that when linking the object via > its embedded list thing, the latter could call said > operation? The issue is that you're starting with a Node_Type of some sort, which is present in the record. GNAT won't let me do anything to compute the start of the record (actually computing it is ok, but won't let me use the record based upon that address). This is so messed up, that I've decided to abandon any semblance of this idea. Lucky for me, I can use a lookup array to do what I need efficiently. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-18 22:52 Generic Embedded List Nodes Warren 2016-06-18 23:40 ` Jeffrey R. Carter 2016-06-19 2:14 ` Jeremiah @ 2016-06-20 6:08 ` Niklas Holsti 2016-06-20 12:20 ` Warren 2016-06-20 19:47 ` Shark8 2016-07-01 19:50 ` brbarkstrom 4 siblings, 1 reply; 52+ messages in thread From: Niklas Holsti @ 2016-06-20 6:08 UTC (permalink / raw) On 16-06-19 01:52 , Warren wrote: > Getting back to Ada after a hiatus, I currently have a need to build a > generic package to implement "embedded list node" lists. The advantage > is high performance in a server setting to avoid underlying malloc/free > calls. > > 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). This > kind of thing is done in the Linux kernel, for example. > > 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. Is there some reason why you cannot derive all the "node" types from a root type that has the link components you need in the Emb_Nodes? Something like this: type Node_T is tagged; type Node_Ref_T is access all Node_T'Class; type Node_T is tagged record Prev, Next : Node_Ref_T; end record; type Integer_Node_T is new Node_T with record Value : Integer; end record; type Float_Node_T is new Node_T with record Value : Float; end record; -- and so on. If you don't derive the list-node types from some common root type (or interface), I don't see how you can traverse a list and do something useful with some or all list elements. Or is it the case that all nodes in any given list are of one and the same type, and you know (somehow) what type they are? Another way to avoid extra heap-allocation/release calls but still have separate objects for the list nodes is to keep your own pool of list nodes, with a free-list. Allocating a new node from such a pool is quite fast and can be inlined. -- Niklas Holsti Tidorum Ltd niklas holsti tidorum fi . @ . ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-20 6:08 ` Niklas Holsti @ 2016-06-20 12:20 ` Warren 0 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-06-20 12:20 UTC (permalink / raw) On Monday, 20 June 2016 02:08:45 UTC-4, Niklas Holsti wrote: > On 16-06-19 01:52 , Warren wrote: > > Getting back to Ada after a hiatus, I currently have a need to build a > > generic package to implement "embedded list node" lists. The advantage > > is high performance in a server setting to avoid underlying malloc/free > > calls. > > > > 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). This > > kind of thing is done in the Linux kernel, for example. > > > > 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. > > Is there some reason why you cannot derive all the "node" types from a > root type that has the link components you need in the Emb_Nodes? > > Something like this: > > type Node_T is tagged; > > type Node_Ref_T is access all Node_T'Class; > > type Node_T is tagged record > Prev, Next : Node_Ref_T; > end record; > > type Integer_Node_T is new Node_T with record > Value : Integer; > end record; > > type Float_Node_T is new Node_T with record > Value : Float; > end record; > > -- and so on. > > If you don't derive the list-node types from some common root type (or > interface), I don't see how you can traverse a list and do something > useful with some or all list elements. Or is it the case that all nodes > in any given list are of one and the same type, and you know (somehow) > what type they are? > > Another way to avoid extra heap-allocation/release calls but still have > separate objects for the list nodes is to keep your own pool of list > nodes, with a free-list. Allocating a new node from such a pool is quite > fast and can be inlined. The idea above works if you only hold one list node. But I use at least two. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-18 22:52 Generic Embedded List Nodes Warren ` (2 preceding siblings ...) 2016-06-20 6:08 ` Niklas Holsti @ 2016-06-20 19:47 ` Shark8 2016-06-21 2:28 ` Warren 2016-07-01 19:50 ` brbarkstrom 4 siblings, 1 reply; 52+ messages in thread From: Shark8 @ 2016-06-20 19:47 UTC (permalink / raw) 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 > generic package to implement "embedded list node" lists. The advantage > is high performance in a server setting to avoid underlying malloc/free > calls. > > 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). This > kind of thing is done in the Linux kernel, for example. > > 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. > > 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. > > package Emb_List is > > type Emb_Node is tagged private; > > procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node); > procedure Unlink(Node: access Emb_Node); > > private > > 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; > > end Emb_List; > > 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". > > generic > type Object_Type is tagged private; > package Emb_List.Nodes is > > type Node_Type(Obj: access Object_Type) is new Emb_Node; > > function Object(Node: Node_Type) return Object_Type; > > end Emb_List.Nodes; > > > 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: > > type Something_New_Type is tagged > record > Stuff: Natural; > Timeout_Node: Node_Type(some access to this record); > ... > end record; > > I am trying to avoid using 'Address for this, since there is likely a > way to do this "right". > > Warren. Hm, have you tried seeing if any Ada.Containers.* fits your needs? You could perhaps use Indefinite_Holder to hold your item or Indefinite_Vector to hold the entire list. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-20 19:47 ` Shark8 @ 2016-06-21 2:28 ` Warren 2016-06-21 7:21 ` Dmitry A. Kazakov 2016-06-23 0:37 ` Randy Brukardt 0 siblings, 2 replies; 52+ messages in thread From: Warren @ 2016-06-21 2:28 UTC (permalink / raw) 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 > > generic package to implement "embedded list node" lists. The advantage > > is high performance in a server setting to avoid underlying malloc/free > > calls. > > > > 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). This > > kind of thing is done in the Linux kernel, for example. > > > > 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. > > > > 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. > > > > package Emb_List is > > > > type Emb_Node is tagged private; > > > > procedure Insert_Head(Head: access Emb_Node; Node: access Emb_Node); > > procedure Unlink(Node: access Emb_Node); > > > > private > > > > 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; > > > > end Emb_List; > > > > 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". > > > > generic > > type Object_Type is tagged private; > > package Emb_List.Nodes is > > > > type Node_Type(Obj: access Object_Type) is new Emb_Node; > > > > function Object(Node: Node_Type) return Object_Type; > > > > end Emb_List.Nodes; > > > > > > 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: > > > > type Something_New_Type is tagged > > record > > Stuff: Natural; > > Timeout_Node: Node_Type(some access to this record); > > ... > > end record; > > > > I am trying to avoid using 'Address for this, since there is likely a > > way to do this "right". > > > > Warren. > > Hm, have you tried seeing if any Ada.Containers.* fits your needs? You could 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 (inspired by the Linux kernel code), and costs almost nothing. The three operations above are inlined and amount to a few pointer related operations. Even a few microseconds of overhead drops your transaction throughput considerably, so using something like Ada containers (or STL in C++) is definitely out for this application. Also any use of malloc/free where possible must be avoided because these are performance killers (even when using jremalloc). Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 2:28 ` Warren @ 2016-06-21 7:21 ` Dmitry A. Kazakov 2016-06-21 10:32 ` Warren 2016-06-23 0:37 ` Randy Brukardt 1 sibling, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-21 7:21 UTC (permalink / raw) On 21/06/2016 04:28, Warren wrote: > Also any use of malloc/free where > possible must be avoided because these are performance killers (even > when using jremalloc). That is no problem, if node life cycle is known a custom pool deploying a FIFO arena in some chunk of memory is used. One should avoid controlled object because killing the arena would not do any finalization. This technique is used in compilers which need a lot of dynamic memory but always know when to free allocated objects. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 7:21 ` Dmitry A. Kazakov @ 2016-06-21 10:32 ` Warren 2016-06-21 11:56 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-21 10:32 UTC (permalink / raw) On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov wrote: > On 21/06/2016 04:28, Warren wrote: > > > Also any use of malloc/free where > > possible must be avoided because these are performance killers (even > > when using jremalloc). > > That is no problem, if node life cycle is known a custom pool deploying > a FIFO arena in some chunk of memory is used. My C++ implementation maintains a pool of objects. But I want to combine Node and Object as one. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 10:32 ` Warren @ 2016-06-21 11:56 ` Dmitry A. Kazakov 2016-06-21 13:39 ` Warren 0 siblings, 1 reply; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-21 11:56 UTC (permalink / raw) On 21/06/2016 12:32, Warren wrote: > On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov wrote: >> On 21/06/2016 04:28, Warren wrote: >> >>> Also any use of malloc/free where >>> possible must be avoided because these are performance killers (even >>> when using jremalloc). >> >> That is no problem, if node life cycle is known a custom pool deploying >> a FIFO arena in some chunk of memory is used. > > My C++ implementation maintains a pool of objects. But I want to > combine Node and Object as one. No problem either. The pool takes care of that. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 11:56 ` Dmitry A. Kazakov @ 2016-06-21 13:39 ` Warren 2016-06-21 14:04 ` Dmitry A. Kazakov 0 siblings, 1 reply; 52+ messages in thread From: Warren @ 2016-06-21 13:39 UTC (permalink / raw) On Tuesday, 21 June 2016 07:57:12 UTC-4, Dmitry A. Kazakov wrote: > On 21/06/2016 12:32, Warren wrote: > > On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov wrote: > >> On 21/06/2016 04:28, Warren wrote: > >> > >>> Also any use of malloc/free where > >>> possible must be avoided because these are performance killers (even > >>> when using jremalloc). > >> > >> That is no problem, if node life cycle is known a custom pool deploying > >> a FIFO arena in some chunk of memory is used. > > > > My C++ implementation maintains a pool of objects. But I want to > > combine Node and Object as one. > > No problem either. The pool takes care of that. That's not completely true- you would have the overhead of TWO pools, instead of one. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 13:39 ` Warren @ 2016-06-21 14:04 ` Dmitry A. Kazakov 0 siblings, 0 replies; 52+ messages in thread From: Dmitry A. Kazakov @ 2016-06-21 14:04 UTC (permalink / raw) On 21/06/2016 15:39, Warren wrote: > On Tuesday, 21 June 2016 07:57:12 UTC-4, Dmitry A. Kazakov wrote: >> On 21/06/2016 12:32, Warren wrote: >>> On Tuesday, 21 June 2016 03:22:11 UTC-4, Dmitry A. Kazakov wrote: >>>> On 21/06/2016 04:28, Warren wrote: >>>> >>>>> Also any use of malloc/free where >>>>> possible must be avoided because these are performance killers (even >>>>> when using jremalloc). >>>> >>>> That is no problem, if node life cycle is known a custom pool deploying >>>> a FIFO arena in some chunk of memory is used. >>> >>> My C++ implementation maintains a pool of objects. But I want to >>> combine Node and Object as one. >> >> No problem either. The pool takes care of that. > > That's not completely true- you would have the overhead of TWO pools, instead of one. No, it is one pool and one single call to allocate the Object_Type. Allocation in FIFO arena pool is a couple of machine instructions. -- Regards, Dmitry A. Kazakov http://www.dmitry-kazakov.de ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-21 2:28 ` Warren 2016-06-21 7:21 ` Dmitry A. Kazakov @ 2016-06-23 0:37 ` Randy Brukardt 2016-06-23 2:25 ` Warren 1 sibling, 1 reply; 52+ messages in thread From: Randy Brukardt @ 2016-06-23 0:37 UTC (permalink / raw) "Warren" <ve3wwg@gmail.com> wrote in message news:6100770a-774c-41a7-b1d9-498f80426835@googlegroups.com... On Monday, 20 June 2016 15:47:12 UTC-4, Shark8 wrote: ... >> Hm, have you tried seeing if any Ada.Containers.* fits your needs? You >> could 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 bounded containers are designed for the purpose of low-overhead operations; in particular, they don't do allocation/deallocation of memory for individual objects. You ought to check out whether those are high enough performance for your purposes before reinventing the wheel... (especially using the check suppression implemented in the latest GNAT versions). (Most programmers, myself included, are terrible at determining what matters for performance of a particular application. The only way to be sure that something is too slow is to try it...) Randy. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-23 0:37 ` Randy Brukardt @ 2016-06-23 2:25 ` Warren 0 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-06-23 2:25 UTC (permalink / raw) On Wednesday, 22 June 2016 20:37:08 UTC-4, Randy Brukardt wrote: ... > The bounded containers are designed for the purpose of low-overhead > operations; in particular, they don't do allocation/deallocation of memory > for individual objects. You ought to check out whether those are high enough > performance for your purposes before reinventing the wheel... (especially > using the check suppression implemented in the latest GNAT versions). I just posted (to Niklas) what will likely be the solution- a large array indexed by socket number. That is prolly the cleanest way I can do this cheap, at the expense of a little bit of memory. > (Most programmers, myself included, are terrible at determining what matters > for performance of a particular application. The only way to be sure that > something is too slow is to try it...) > > Randy. Agreed. In my day job (where we try lots of things), I do benchmarks on the C++ servers I write and maintain. Experience shows that it takes very little to slow down the transaction rate and there are often surprises. Here though, in Ada, I'm just playing around with a version of it as a hobby horse. It would be nice if I could someday compare the Ada version against the C++ version. So I'm just chipping away at this. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-06-18 22:52 Generic Embedded List Nodes Warren ` (3 preceding siblings ...) 2016-06-20 19:47 ` Shark8 @ 2016-07-01 19:50 ` brbarkstrom 2016-07-02 1:55 ` Warren 4 siblings, 1 reply; 52+ messages in thread From: brbarkstrom @ 2016-07-01 19:50 UTC (permalink / raw) Another suggestion is to add a numerical index to each node, as well as some identifier (maybe a string or some other suitable type), and use a hash function to calculate the index from the identifier. Assuming you also use Ada access variable to link the nodes together, this might be a useful way to implement the type of design you seem to have in mind. Linkages in a triply linked list (see Knuth, Vol I index) can be handled this way, so you can have hierarchical structures. Bruce B. ^ permalink raw reply [flat|nested] 52+ messages in thread
* Re: Generic Embedded List Nodes 2016-07-01 19:50 ` brbarkstrom @ 2016-07-02 1:55 ` Warren 0 siblings, 0 replies; 52+ messages in thread From: Warren @ 2016-07-02 1:55 UTC (permalink / raw) On Friday, 1 July 2016 15:50:40 UTC-4, brbar...@gmail.com wrote: > Another suggestion is to add a numerical index to each node, as well as some > identifier (maybe a string or some other suitable type), and use a hash function > to calculate the index from the identifier. Assuming you also use Ada access > variable to link the nodes together, this might be a useful way to implement > the type of design you seem to have in mind. Linkages in a triply linked > list (see Knuth, Vol I index) can be handled this way, so you can have > hierarchical structures. > > Bruce B. I do actually have a numerical index already (as I mentioned before). I can use the socket file descriptor (POSIX) to index an array to directly arrive at a lookup. But where that [fd] approach is clumsy is having to copy that file descriptor into each list node of the same object. Warren ^ permalink raw reply [flat|nested] 52+ messages in thread
end of thread, other threads:[~2016-07-02 1:55 UTC | newest] Thread overview: 52+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2016-06-18 22:52 Generic Embedded List Nodes Warren 2016-06-18 23:40 ` Jeffrey R. Carter 2016-06-19 2:15 ` Warren 2016-06-19 3:04 ` Jeffrey R. Carter 2016-06-19 2:14 ` Jeremiah 2016-06-19 2:21 ` Warren 2016-06-19 2:50 ` Warren 2016-06-19 4:45 ` Simon Wright 2016-06-19 18:27 ` Warren 2016-06-19 19:04 ` Dmitry A. Kazakov 2016-06-19 20:13 ` Warren 2016-06-19 20:35 ` Dmitry A. Kazakov 2016-06-20 2:42 ` Warren 2016-06-20 7:25 ` Dmitry A. Kazakov 2016-06-20 12:26 ` Warren 2016-06-20 19:33 ` Niklas Holsti 2016-06-21 2:20 ` Warren 2016-06-21 5:52 ` Niklas Holsti 2016-06-21 7:15 ` Dmitry A. Kazakov 2016-06-21 18:54 ` Niklas Holsti 2016-06-21 19:54 ` Dmitry A. Kazakov 2016-06-21 10:31 ` Warren 2016-06-21 17:13 ` Jeffrey R. Carter 2016-06-21 18:56 ` Niklas Holsti 2016-06-21 20:13 ` Warren 2016-06-21 21:38 ` Niklas Holsti 2016-06-23 2:12 ` Warren 2016-06-23 8:19 ` Niklas Holsti 2016-06-23 12:37 ` Warren 2016-06-23 15:36 ` Niklas Holsti 2016-06-24 1:55 ` Warren 2016-06-24 12:49 ` Warren 2016-06-25 5:50 ` Niklas Holsti 2016-06-26 1:36 ` Warren 2016-07-01 13:49 ` Warren 2016-07-01 16:28 ` Warren 2016-06-24 20:25 ` Warren 2016-06-22 13:01 ` G.B. 2016-06-23 2:30 ` Warren 2016-06-20 6:08 ` Niklas Holsti 2016-06-20 12:20 ` Warren 2016-06-20 19:47 ` Shark8 2016-06-21 2:28 ` Warren 2016-06-21 7:21 ` Dmitry A. Kazakov 2016-06-21 10:32 ` Warren 2016-06-21 11:56 ` Dmitry A. Kazakov 2016-06-21 13:39 ` Warren 2016-06-21 14:04 ` Dmitry A. Kazakov 2016-06-23 0:37 ` Randy Brukardt 2016-06-23 2:25 ` Warren 2016-07-01 19:50 ` brbarkstrom 2016-07-02 1:55 ` Warren
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox