Yes. Linked lists are both possible and easy, with your "store" and "reference" pointer idea, provided there is a standard (ie. inbuilt) "procedure" to swap two "store" pointers. I think that's all you need to overcome the problem with linked lists.
Also, note that if either or both "store" pointers has any "reference" pointers associated with it, these "reference" pointers must still point at the same objects after the "store" pointer swap, as they did prior to the swap.
Finally, some suggestions on nomenclature and syntax ...
1. I wonder if the words "store" and "reference" are complementary? How about "primary" and "secondary" instead? Or something else? This is subjective, but I'm not sure if the word "store" would "read" very well in the following suggested syntax (looks too much like a verb;-) :
2. Syntax suggestion : Type pointer1 = ^integer; {a standard pointer} pointer2 = primary ^integer; {a "store" pointer} pointer3 = secondary ^integer; {a "reference" pointer}
Joe.
-----Original Message----- From: Markus Gerwinski [SMTP:markus@gerwinski.de] Sent: Wednesday, February 20, 2002 2:53 AM To: da Silva, Joe Cc: 'gpc@gnu.de' Subject: Re: pointers (was: gcc-3+)
Hi folks,
da Silva, Joe wrote:
All you need is a standard (ie. inbuilt) procedure/statement that can swap two store pointers ... I think.
You mean, for linked lists?
Bye
Markus
da Silva, Joe wrote:
Yes. Linked lists are both possible and easy, with your "store" and "reference" pointer idea, provided there is a standard (ie. inbuilt) "procedure" to swap two "store" pointers. I think that's all you need to overcome the problem with linked lists.
Sorry, but to me it seems a way to solve this particular situation that occurs with simple linked lists (as you described in a previous mail) where you have an exact overview what is going on (and therefore don't need the whole concept at all -- *because* you know exactly what's going on, and could just do things correctly with normal pointers). Avoiding memory leaks with simple links lists is not exactly a difficult problem. So you add a second concept (swapping) to solve the problems caused by the first concept (store/reference) pointers, both with extra effort on behalf on the programmer and with no advantage that I can see.
AFAIK, nobody has addressed some more complex situations yet (like trees/graphs that point to each other in complex ways, and are allocated and deallocated in alomost arbitrary order) and described how this concept would improve (and not worsen) the situation.
Maybe I'm just playing devil's advocate here, but I really don't see any advantage of the concept yet (except maybe in rather special situations such as those that Markus has in mind with his collections IIUIC) ...
Frank
Hi folks,
Frank Heckenbach wrote:
Yes. Linked lists are both possible and easy, with your "store" and "reference" pointer idea, provided there is a standard (ie. inbuilt) "procedure" to swap two "store" pointers. I think that's all you need to overcome the problem with linked lists.
Sorry, but to me it seems a way to solve this particular situation that occurs with simple linked lists (as you described in a previous mail) where you have an exact overview what is going on (and therefore don't need the whole concept at all -- *because* you know exactly what's going on, and could just do things correctly with normal pointers).
I agree with Frank here -- the swap routine would just be a difficult solution for a self-made problem. For linked lists, a "normal" pointer without restrictions is probably the best solution.
Maybe I'm just playing devil's advocate here, but I really don't see any advantage of the concept yet (except maybe in rather special situations such as those that Markus has in mind with his collections IIUIC) ...
They're quite common situations, at least in object-oriented programming: You often have some object stored in, e.g., a list, referenced from three other lists with other sorting criteria, plus two trees sorting the object into different hierarchies, plus a hashtable of completely other objects referencing the first one in a bunch of associations etc. etc. etc.. Keeping the overview of who is when allowed to destroy which object often becomes an act of complex logics. It is either a quite common pattern to keep track of your "stores" and "references". (A most common example are existence- dependent or -independent associations in UML.) My suggestion was to make this pattern an inherent part of the compiler.
Bye
Markus
Markus Gerwinski wrote:
Maybe I'm just playing devil's advocate here, but I really don't see any advantage of the concept yet (except maybe in rather special situations such as those that Markus has in mind with his collections IIUIC) ...
They're quite common situations, at least in object-oriented programming: You often have some object stored in, e.g., a list, referenced from three other lists with other sorting criteria, plus two trees sorting the object into different hierarchies, plus a hashtable of completely other objects referencing the first one in a bunch of associations etc. etc. etc.. Keeping the overview of who is when allowed to destroy which object often becomes an act of complex logics. It is either a quite common pattern to keep track of your "stores" and "references". (A most common example are existence- dependent or -independent associations in UML.) My suggestion was to make this pattern an inherent part of the compiler.
So IIUIC the special pattern in "your" usage is that one kind of lists only contains "store" pointers and other lists contain only "reference" pointers? (Otherwise, you wouldn't be able to even declare the lists if the pointers were distinguished syntactically, AFAICS.)
Well, I think that is a rather special pattern. In most of my code (and even more so in GCC/GPC), many "objects" contain a wild mix of original ("store") and copied ("reference") pointers.
BTW, I just noticed an analogy, namely to file systems: While normal pointers are like hard links, your reference pointers are like symlinks. I'm not sure, though, what this means to this discussion. ;-) -- But perhaps the analogy is not so good, since symlinks remain in existence if you remove the target, and if you create a new target under the same name, they point to this one.
Frank
"da Silva, Joe" wrote:
Yes. Linked lists are both possible and easy, with your "store" and "reference" pointer idea, provided there is a standard (ie. inbuilt) "procedure" to swap two "store" pointers. I think that's all you need to overcome the problem with linked lists.
You are turning very simple fast operations into slow horrors. For example look at the code to reverse a singly linked list NIL terminated. It is extremely fast, normally consisting of four assignments per position and often used. This would turn into three procedure calls and whatever associated code is involved. Here is C code for list reversal:
/* ======================================================= */ /* believed necessary and sufficient for NULL terminations */ /* Reverse a singly linked list. Reentrant (pure) code */ nodeptr revlist(nodeptr root) { nodeptr curr, nxt;
if (root) { /* non-empty list */ nxt = root->next; root->next = NULL; /* terminate new list */ while ((curr = nxt)) { /* walk onward */ nxt = curr->next; /* save for walk */ curr->next = root; /* relink */ root = curr; /* save for next relink */ } } /* else empty list is its own reverse; */ return root; } /* revlist */
This can be executed entirely in registers on most machines. Compiled with gcc -O2:
00000000 <_revlist>: /* ======================================================= */ /* believed necessary and sufficient for NULL terminations */ /* Reverse a singly linked list. Reentrant (pure) code */ nodeptr revlist(nodeptr root) { 0: 55 push %ebp 1: 89 e5 mov %esp,%ebp 3: 8b 45 08 mov 0x8(%ebp),%eax nodeptr curr, nxt;
if (root) { /* non-empty list */ 6: 85 c0 test %eax,%eax 8: 74 16 je 20 <_revlist+0x20> nxt = root->next; a: 8b 10 mov (%eax),%edx root->next = NULL; /* terminate new list */ c: c7 00 00 00 00 00 movl $0x0,(%eax) while ((curr = nxt)) { /* walk onward */ 12: eb 06 jmp 1a <_revlist+0x1a> nxt = curr->next; /* save for walk */ 14: 8b 12 mov (%edx),%edx curr->next = root; /* relink */ 16: 89 01 mov %eax,(%ecx) root = curr; /* save for next relink */ 18: 89 c8 mov %ecx,%eax } 1a: 89 d1 mov %edx,%ecx 1c: 85 d2 test %edx,%edx 1e: 75 f4 jne 14 <_revlist+0x14> } /* else empty list is its own reverse; */ return root; 20: 89 ec mov %ebp,%esp 22: 5d pop %ebp 23: c3 ret
(I couldn't have done better myself <g> 12 bytes in the loop)
This is not gpc's crying need - it lacks run-time checking entirely, which leads to many more errors than does failure to handle new/dispose correctly.
Hi folks,
da Silva, Joe wrote:
- I wonder if the words "store" and "reference" are complementary?
Is complementarity a demand here? Clear distinction's sufficient, I think...
How about "primary" and "secondary" instead? Or something else? This is subjective, but I'm not sure if the word "store" would "read" very well in the following suggested syntax (looks too much like a verb;-) :
Agreed, but IMO "primary" and "secondary" are too general words to really describe the use of the pointers. What about "stored" and "referenced"?
type pointer = ^integer; pointer2 = stored ^integer; pointer3 = referenced ^integer;
Cheers
Markus
-
CBFalconer -
da Silva, Joe -
Frank Heckenbach -
Markus Gerwinski