With one of my friends at the university we used to compete for a shorter/nicer implementation of each data structure in the algorithms class we were taking, and after using pointers-to-pointers in some previous cases (linked lists, binary search trees etc.) and each time ending up with an implementation I really liked, I tried to implement AVL trees[1] the same way, for example an AVL rotation would be done by a call like this:<p><pre><code> avl_tree_rotate(avl, &t->left->right->left, &t->left->right, &t->left, t->left->right);
</code></pre>
Where avl_tree_rotate looked like this (avl_tree_update just recomputes the height after left or right branch height changes):<p><pre><code> static void avl_tree_rotate(avl avl, V **from, V **to, V **parent, V *child) {
if(*from) (*from)->parent = *to ? (*to)->parent : NULL;
if(*to) (*to)->parent = *from ? (*from)->parent : NULL;
avl_tree_swap(avl, from, to);
child->parent = (*parent)->parent;
if(!((*parent)->parent))
avl->root = child;
else if((*parent)->parent->left == *parent)
(*parent)->parent->left = child;
else if((*parent)->parent->right == *parent)
(*parent)->parent->right = child;
(*parent)->parent = child;
*from = *parent;
avl_tree_update(avl, *parent);
avl_tree_update(avl, child);
}
</code></pre>
It was one of nicer programming workouts I ever got (the whole class was a great experience and I think every professional programmer should go through implementing all the basic data structures and algorithms in plain C one time), but I never managed to get deletion right, despite spending quite some hours on it, it just went beyond my head. Not that it matters for linked lists, and in this case I made it deliberately harder on myself, but I think the moral of the story is that when you are too clever with implementation details, you might run out of your cleverness when starting to deal with the actual problem domain.<p>[1] <a href="http://en.wikipedia.org/wiki/AVL_tree" rel="nofollow">http://en.wikipedia.org/wiki/AVL_tree</a>