for (i = ei; i < 3 && n->elems[i+1]; i++)
for (i = ei; i < 2 && n->elems[i+1]; i++)
void del234(tree234 *t, void *e) {    node234 *n;    int ei = -1;    n = t->root;    LOG(("deleting %p from tree %p\n", e, t));    while (1) {	while (n) {	    int c;	    int ki;	    node234 *sub;	    LOG(("  node %p: %p [%p] %p [%p] %p [%p] %p\n",		 n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],		 n->kids[2], n->elems[2], n->kids[3]));		    if ((c = t->cmp(e, n->elems[0])) < 0) {		ki = 0;	    } else if (c == 0) {		ei = 0; break;	    } else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0) {		ki = 1;	    } else if (c == 0) {		ei = 1; break;	    } else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0) {		ki = 2;	    } else if (c == 0) {		ei = 2; break;	    } else {		ki = 3;	    }	    /*	     * Recurse down to subtree ki. If it has only one element,	     * we have to do some transformation to start with.	     */	    LOG(("  moving to subtree %d\n", ki));	    sub = n->kids[ki];	    if (!sub->elems[1]) {		LOG(("  subtree has only one element!\n", ki));		if (ki > 0 && n->kids[ki-1]->elems[1]) {		    /*		     * Case 3a, left-handed variant. Child ki has		     * only one element, but child ki-1 has two or		     * more. So we need to move a subtree from ki-1		     * to ki.		     * 		     *                . C .                     . B .		     *               /     \     ->            /     \		     * [more] a A b B c   d D e      [more] a A b   c C d D e		     */		    node234 *sib = n->kids[ki-1];		    int lastelem = (sib->elems[2] ? 2 :				    sib->elems[1] ? 1 : 0);		    sub->kids[2] = sub->kids[1];		    sub->elems[1] = sub->elems[0];		    sub->kids[1] = sub->kids[0];		    sub->elems[0] = n->elems[ki-1];		    sub->kids[0] = sib->kids[lastelem+1];		    n->elems[ki-1] = sib->elems[lastelem];		    sib->kids[lastelem+1] = NULL;		    sib->elems[lastelem] = NULL;		    LOG(("  case 3a left\n"));		} else if (ki < 3 && n->kids[ki+1] &&			   n->kids[ki+1]->elems[1]) {		    /*		     * Case 3a, right-handed variant. ki has only		     * one element but ki+1 has two or more. Move a		     * subtree from ki+1 to ki.		     * 		     *      . B .                             . C .		     *     /     \                ->         /     \		     *  a A b   c C d D e [more]      a A b B c   d D e [more]		     */		    node234 *sib = n->kids[ki+1];		    int j;		    sub->elems[1] = n->elems[ki];		    sub->kids[2] = sib->kids[0];		    n->elems[ki] = sib->elems[0];		    sib->kids[0] = sib->kids[1];		    for (j = 0; j < 2 && sib->elems[j+1]; j++) {			sib->kids[j+1] = sib->kids[j+2];			sib->elems[j] = sib->elems[j+1];		    }		    sib->kids[j+1] = NULL;		    sib->elems[j] = NULL;		    LOG(("  case 3a right\n"));		} else {		    /*		     * Case 3b. ki has only one element, and has no		     * neighbour with more than one. So pick a		     * neighbour and merge it with ki, taking an		     * element down from n to go in the middle.		     *		     *      . B .                .		     *     /     \     ->        |		     *  a A b   c C d      a A b B c C d		     * 		     * (Since at all points we have avoided		     * descending to a node with only one element,		     * we can be sure that n is not reduced to		     * nothingness by this move, _unless_ it was		     * the very first node, ie the root of the		     * tree. In that case we remove the now-empty		     * root and replace it with its single large		     * child as shown.)		     */		    node234 *sib;		    int j;		    if (ki > 0)			ki--;		    sib = n->kids[ki];		    sub = n->kids[ki+1];		    sub->kids[3] = sub->kids[1];		    sub->elems[2] = sub->elems[0];		    sub->kids[2] = sub->kids[0];		    sub->elems[1] = n->elems[ki];		    sub->kids[1] = sib->kids[1];		    sub->elems[0] = sib->elems[0];		    sub->kids[0] = sib->kids[0];		    sfree(sib);		    /*		     * That's built the big node in sub. Now we		     * need to remove the reference to sib in n.		     */		    for (j = ki; j < 3 && n->kids[j+1]; j++) {			n->kids[j] = n->kids[j+1];			n->elems[j] = j<2 ? n->elems[j+1] : NULL;		    }		    n->kids[j] = NULL;		    if (j < 3) n->elems[j] = NULL;		    LOG(("  case 3b\n"));		    if (!n->elems[0]) {			/*			 * The root is empty and needs to be			 * removed.			 */			LOG(("  shifting root!\n"));			t->root = sub;			sub->parent = NULL;			sfree(n);		    }		}	    }	    n = sub;	}	if (ei==-1)	    return;		       /* nothing to do; `already removed' */	/*	 * Treat special case: this is the one remaining item in	 * the tree. n is the tree root (no parent), has one	 * element (no elems[1]), and has no kids (no kids[0]).	 */	if (!n->parent && !n->elems[1] && !n->kids[0]) {	    LOG(("  removed last element in tree\n"));	    sfree(n);	    t->root = NULL;	    return;	}	/*	 * Now we have the element we want, as n->elems[ei], and we	 * have also arranged for that element not to be the only	 * one in its node. So...	 */	if (!n->kids[0] && n->elems[1]) {	    /*	     * Case 1. n is a leaf node with more than one element,	     * so it's _really easy_. Just delete the thing and	     * we're done.	     */	    int i;	    LOG(("  case 1\n"));	    for (i = ei; i < 3 && n->elems[i+1]; i++)		n->elems[i] = n->elems[i+1];	    n->elems[i] = NULL;	    return;		       /* finished! */	} else if (n->kids[ei]->elems[1]) {	    /*	     * Case 2a. n is an internal node, and the root of the	     * subtree to the left of e has more than one element.	     * So find the predecessor p to e (ie the largest node	     * in that subtree), place it where e currently is, and	     * then start the deletion process over again on the	     * subtree with p as target.	     */	    node234 *m = n->kids[ei];	    void *target;	    LOG(("  case 2a\n"));	    while (m->kids[0]) {		m = (m->kids[3] ? m->kids[3] :		     m->kids[2] ? m->kids[2] :		     m->kids[1] ? m->kids[1] : m->kids[0]);		     	    }	    target = (m->elems[2] ? m->elems[2] :		      m->elems[1] ? m->elems[1] : m->elems[0]);	    n->elems[ei] = target;	    n = n->kids[ei];	    e = target;	} else if (n->kids[ei+1]->elems[1]) {	    /*	     * Case 2b, symmetric to 2a but s/left/right/ and	     * s/predecessor/successor/. (And s/largest/smallest/).	     */	    node234 *m = n->kids[ei+1];	    void *target;	    LOG(("  case 2b\n"));	    while (m->kids[0]) {		m = m->kids[0];	    }	    target = m->elems[0];	    n->elems[ei] = target;	    n = n->kids[ei+1];	    e = target;	} else {	    /*	     * Case 2c. n is an internal node, and the subtrees to	     * the left and right of e both have only one element.	     * So combine the two subnodes into a single big node	     * with their own elements on the left and right and e	     * in the middle, then restart the deletion process on	     * that subtree, with e still as target.	     */	    node234 *a = n->kids[ei], *b = n->kids[ei+1];	    int j;	    LOG(("  case 2c\n"));	    a->elems[1] = n->elems[ei];	    a->kids[2] = b->kids[0];	    a->elems[2] = b->elems[0];	    a->kids[3] = b->kids[1];	    sfree(b);	    /*	     * That's built the big node in a, and destroyed b. Now	     * remove the reference to b (and e) in n.	     */	    for (j = ei; j < 2 && n->elems[j+1]; j++) {		n->elems[j] = n->elems[j+1];		n->kids[j+1] = n->kids[j+2];	    }	    n->elems[j] = NULL;	    n->kids[j+1] = NULL;	    /*	     * Now go round the deletion process again, with n	     * pointing at the new big node and e still the same.	     */	    n = a;	}    }}