3 ms·

Something 's not right. Still too complex. Ah. Lists are recursive. Their treatment should be recursive as well. Let's see… void remove_if(node ** head, r

Something 's not right. Still too complex. Ah. Lists are recursive. Their treatment should be recursive as well. Let's see… void remove_if(node ** head, remove_fn rm) { node * entry = *head; if (rm(entry)) { *head = entry->next; free(entry); } else head = &entry->next; remove_if(head, rm); } Ahh, much better: Now we can refactor: void remove_head(node ** head) { node * entry = *head; *head = entry->next; free(entry); } void remove_if(node ** head, remove_fn rm) { if (rm(*head)) remove_head(head) else head = &entry->next; remove_if(head, rm); } I'm sure GCC will be able to optimize away the tail call. Edit: oops, I forgot to test for empty lists, which was implicit in the for loop I set out to remove…

JoachimSchipper 14y ago
Tail calls are considered very bad style, for good reason. gcc can indeed optimize them away, at a sufficiently high level of optimization; but it's not very nice to write code that, e.g., runs out of stack space only when compiled for debugging.
- AngryParsley 14y ago
  "...very bad style"? That's quite an overstatement. You can enable individual optimizations with gcc. Just add `-foptimize-sibling-calls` to the debug CFLAGS and you're set. Tada! Straightforward code and debug-ability.
  - greenyoda 14y ago
    But that would be making your code dependent on a particular feature of a particular compiler. If you then want to port your code to Windows (lots of open-source code runs there too), you'll have to deal with the problem again there. If you wrote the code with an explicit loop, it would just work everywhere.
- betterunix 14y ago
  On the other hand, for a linked list, recursion follows immediately from the definition of the list, while iteration does not. I would rather have my debugger allocate a large stack or compile the code so that TCO was enabled even when I was debugging than have to deal with implementations that do not clearly follow from a high-level design.
scscsc 14y ago
Lists are recursive, right. Better than double pointer indirection is to have the function return the new head. Note that the following code is not functional, but returning the new head makes it cleaner. node *remove_if(node *head, remove_fn rm) { if (rm(head)) { return remove_if(head->next); } head->next = remove_if(head->next); return head; } A good use of this technique (returning pointers to the resulting node) is the following code which very cleanly implements AVL trees in C (from http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-... -- scroll to the end (sorry, main article in Romanian)): #define max(a, b) ((a) > (b) ? (a) : (b)) #define geth(n) (n->h = 1 + max(n->l->h, n->r->h)) struct node { int key, h; struct node *l, *r; } *R, *NIL; typedef struct node node; void init(void) { R = NIL = (node *) malloc(sizeof(node)); NIL->key = NIL->h = 0, NIL->l = NIL->r = NULL; } node* rotleft(node *n) { node *t = n->l; n->l = t->r, t->r = n, geth(n), geth(t); return t; } node* rotright(node *n) { node *t = n->r; n->r = t->l, t->l = n, geth(n), geth(t); return t; } node* balance(node *n) { geth(n); if (n->l->h > n->r->h + 1) { if (n->l->r->h > n->l->l->h) n->l = rotright(n->l); n = rotleft(n); } else if (n->r->h > n->l->h + 1) { if (n->r->l->h > n->r->r->h) n->r = rotleft(n->r); n = rotright(n); } return n; } node* insert(node *n, int key) { if (n == NIL) { n = (node *) malloc(sizeof(node)); n->key = key, n->h = 1, n->l = n->r = NIL; return n; } if (key < n->key) n->l = insert(n->l, key); else n->r = insert(n->r, key); return balance(n); } node* erase(node *n, int key) { node *t; if (n == NIL) return n; if (n->key == key) { if (n->l == NIL || n->r == NIL) { t = n->l == NIL ? n->r : n->l; free(n); return t; } else { for (t = n->r; t->l != NIL; t = t->l); n->key = t->key, n->r = erase(n->r, t->key); return balance(n); } } if (key < n->key) n->l = erase(n->l, key); else n->r = erase(n->r, key); return balance(n); } int search(node *n, int key) { if (n == NIL) return 0; if (n->key == key) return 1; if (key < n->key) return search(n->l, key); else return search(n->r, key); }

JoachimSchipper 14y ago

Tail calls are considered very bad style, for good reason. gcc can indeed optimize them away, at a sufficiently high level of optimization; but it's not very nice to write code that, e.g., runs out of stack space only when compiled for debugging.

AngryParsley 14y ago
"...very bad style"? That's quite an overstatement. You can enable individual optimizations with gcc. Just add `-foptimize-sibling-calls` to the debug CFLAGS and you're set. Tada! Straightforward code and debug-ability.
- greenyoda 14y ago
  But that would be making your code dependent on a particular feature of a particular compiler. If you then want to port your code to Windows (lots of open-source code runs there too), you'll have to deal with the problem again there. If you wrote the code with an explicit loop, it would just work everywhere.
betterunix 14y ago
On the other hand, for a linked list, recursion follows immediately from the definition of the list, while iteration does not. I would rather have my debugger allocate a large stack or compile the code so that TCO was enabled even when I was debugging than have to deal with implementations that do not clearly follow from a high-level design.

scscsc 14y ago

Lists are recursive, right. Better than double pointer indirection is to have the function return the new head. Note that the following code is not functional, but returning the new head makes it cleaner. node *remove_if(node *head, remove_fn rm) { if (rm(head)) { return remove_if(head->next); } head->next = remove_if(head->next); return head; } A good use of this technique (returning pointers to the resulting node) is the following code which very cleanly implements AVL trees in C (from http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-numai http://infoarena.ro/multe-smenuri-de-programare-in-cc-si-nu-... -- scroll to the end (sorry, main article in Romanian)): #define max(a, b) ((a) > (b) ? (a) : (b)) #define geth(n) (n->h = 1 + max(n->l->h, n->r->h)) struct node { int key, h; struct node *l, *r; } *R, *NIL; typedef struct node node; void init(void) { R = NIL = (node *) malloc(sizeof(node)); NIL->key = NIL->h = 0, NIL->l = NIL->r = NULL; } node* rotleft(node *n) { node *t = n->l; n->l = t->r, t->r = n, geth(n), geth(t); return t; } node* rotright(node *n) { node *t = n->r; n->r = t->l, t->l = n, geth(n), geth(t); return t; } node* balance(node *n) { geth(n); if (n->l->h > n->r->h + 1) { if (n->l->r->h > n->l->l->h) n->l = rotright(n->l); n = rotleft(n); } else if (n->r->h > n->l->h + 1) { if (n->r->l->h > n->r->r->h) n->r = rotleft(n->r); n = rotright(n); } return n; } node* insert(node *n, int key) { if (n == NIL) { n = (node *) malloc(sizeof(node)); n->key = key, n->h = 1, n->l = n->r = NIL; return n; } if (key < n->key) n->l = insert(n->l, key); else n->r = insert(n->r, key); return balance(n); } node* erase(node *n, int key) { node *t; if (n == NIL) return n; if (n->key == key) { if (n->l == NIL || n->r == NIL) { t = n->l == NIL ? n->r : n->l; free(n); return t; } else { for (t = n->r; t->l != NIL; t = t->l); n->key = t->key, n->r = erase(n->r, t->key); return balance(n); } } if (key < n->key) n->l = erase(n->l, key); else n->r = erase(n->r, key); return balance(n); } int search(node *n, int key) { if (n == NIL) return 0; if (n->key == key) return 1; if (key < n->key) return search(n->l, key); else return search(n->r, key); }