"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.