+static aatree_ptr aatree_copy_links( aatree *tree, aatree_ptr root,
+ aatree_ptr src, aatree_ptr dst )
+{
+ aatree_node *pdst = aatree_get_node( tree, dst ),
+ *psrc = aatree_get_node( tree, src );
+
+ pdst->count = psrc->count;
+ pdst->level = psrc->level;
+ pdst->parent = psrc->parent;
+
+ aatree_link_down( tree, dst, &pdst->left, psrc->left );
+ aatree_link_down( tree, dst, &pdst->right, psrc->right );
+
+ if( pdst->parent != AATREE_PTR_NIL )
+ {
+ aatree_node *parent = aatree_get_node( tree, pdst->parent );
+
+ if( parent->left == src )
+ parent->left = dst;
+ else if( parent->right == src )
+ parent->right = dst;
+ }
+ else
+ return dst;
+
+ return root;
+}
+
+static aatree_ptr aatree_del( aatree *tree, aatree_ptr x )
+{
+ aatree_ptr it = x,
+ up[32];
+
+ int count = 1, dir = 0;
+
+ /* TODO: maybe be a better way to do this, without counting back up */
+ for( aatree_node *s = aatree_get_node( tree, x );
+ s->parent != AATREE_PTR_NIL;
+ count ++ )
+ s = aatree_get_node( tree, s->parent );
+
+ int top=0;
+ while(1)
+ {
+ int index = count - (++top);
+
+ up[ index ] = it;
+ aatree_node *itnode = aatree_get_node( tree, it );
+ if( itnode->parent == AATREE_PTR_NIL )
+ break;
+ else
+ it = itnode->parent;
+ }
+
+ aatree_ptr _ptrswap_src = AATREE_PTR_NIL,
+ _ptrswap_dst = AATREE_PTR_NIL;
+
+ aatree_node *pxnode = aatree_get_node( tree, x );
+ aatree_ptr root = up[ count-1 ];
+ if( pxnode->left == AATREE_PTR_NIL || pxnode->right == AATREE_PTR_NIL )
+ {
+ if( --top != 0 )
+ {
+ aatree_node *pnode = aatree_get_node( tree, up[top-1] ),
+ *parent = aatree_get_node( tree, pxnode->parent );
+
+ aatree_ptr next = pxnode->left == AATREE_PTR_NIL?
+ pxnode->right:
+ pxnode->left;
+
+ if( parent->left == x ) pnode->left = next;
+ else pnode->right = next;
+
+ if( next != AATREE_PTR_NIL )
+ {
+ aatree_node *pnext = aatree_get_node( tree, next );
+ pnext->parent = up[top-1];
+ }
+ }
+ else
+ {
+ if( pxnode->right != AATREE_PTR_NIL ) root = pxnode->right;
+ else if( pxnode->left != AATREE_PTR_NIL ) root = pxnode->left;
+ else return AATREE_PTR_NIL;
+
+ aatree_node *newroot = aatree_get_node( tree, root );
+ newroot->parent = AATREE_PTR_NIL;
+ }
+ }
+ else
+ {
+ aatree_ptr heir = pxnode->right,
+ prev = x;
+
+ aatree_node *pheir = aatree_get_node( tree, heir );
+
+ while( pheir->left != AATREE_PTR_NIL )
+ {
+ up[top++] = prev = heir;
+ heir = pheir->left;
+ pheir = aatree_get_node( tree, heir );
+ }
+
+ _ptrswap_dst = heir;
+ _ptrswap_src = x;
+
+ aatree_node *pprev = aatree_get_node( tree, prev );
+
+ if( prev == x )
+ aatree_link_down( tree, prev, &pprev->right, pheir->right );
+ else
+ aatree_link_down( tree, prev, &pprev->left, pheir->right );
+ }
+
+ /* Tail */
+ while( --top >= 0 )
+ {
+ if( top != 0 )
+ {
+ aatree_node *above = aatree_get_node( tree, up[top-1] );
+ dir = above->right == up[top];
+ }
+
+ aatree_recount( tree, up[top] );
+ aatree_node *pntop = aatree_get_node( tree, up[top] );
+
+ if( !(pntop->left == AATREE_PTR_NIL || pntop->right == AATREE_PTR_NIL) )
+ {
+ aatree_node *pnl = aatree_get_node( tree, pntop->left ),
+ *pnr = aatree_get_node( tree, pntop->right );
+
+ if( pnl->level < pntop->level-1 || pnr->level < pntop->level-1 )
+ {
+ if( pnr->level > --pntop->level )
+ pnr->level = pntop->level;
+
+ up[top] = aatree_skew( tree, up[top] );
+
+ aatree_node *ut = aatree_get_node( tree, up[top] );
+ ut->right = aatree_skew( tree, ut->right );
+
+ aatree_node *utr = aatree_get_node( tree, ut->right );
+ utr->right = aatree_skew( tree, utr->right );
+
+ up[top] = aatree_split( tree, up[top] );
+ ut = aatree_get_node( tree, up[top] );
+
+ ut->right = aatree_split( tree, ut->right );
+ }
+ }
+
+ if( top != 0 )
+ {
+ aatree_node *ut1 = aatree_get_node( tree, up[top-1] );
+
+ if( dir == 1 )
+ aatree_link_down( tree, up[top-1], &ut1->right, up[top] );
+ else
+ aatree_link_down( tree, up[top-1], &ut1->left, up[top] );
+ }
+ else
+ {
+ root = up[top];
+ aatree_get_node( tree, root )->parent = AATREE_PTR_NIL;
+ }
+ }
+
+ /* This is our extension to the original non-recursive delete, so no data
+ * has to be moved */
+ if( _ptrswap_dst != AATREE_PTR_NIL )
+ root = aatree_copy_links( tree, root, _ptrswap_src, _ptrswap_dst );
+
+ return root;
+}