void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){

    AVTreeNode *t= *tp;

    if(t){

        unsigned int v= cmp(t->elem, key);

        void *ret;

        if(!v){

            if(*next)

                return t->elem;

            else if(t->child[0]||t->child[1]){

                int i= !t->child[0];

                void *next_elem[2];

                av_tree_find(t->child[i], key, cmp, next_elem);

                key= t->elem= next_elem[i];

                v= -i;

            }else{

                *next= t;

                *tp=NULL;

                return NULL;

            }

        }

        ret= av_tree_insert(&t->child[v>>31], key, cmp, next);

        if(!ret){

            int i= (v>>31) ^ !!*next;

            AVTreeNode **child= &t->child[i];

            t->state += 2*i - 1;



            if(!(t->state&1)){

                if(t->state){

                    /* The following code is equivalent to

                    if((*child)->state*2 == -t->state)

                        rotate(child, i^1);

                    rotate(tp, i);



                    with rotate():

                    static void rotate(AVTreeNode **tp, int i){

                        AVTreeNode *t= *tp;



                        *tp= t->child[i];

                        t->child[i]= t->child[i]->child[i^1];

                        (*tp)->child[i^1]= t;

                        i= 4*t->state + 2*(*tp)->state + 12;

                          t  ->state=                     ((0x614586 >> i) & 3)-1;

                        (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1;

                    }

                    but such a rotate function is both bigger and slower

                    */

                    if((*child)->state*2 == -t->state){

                        *tp= (*child)->child[i^1];

                        (*child)->child[i^1]= (*tp)->child[i];

                        (*tp)->child[i]= *child;

                        *child= (*tp)->child[i^1];

                        (*tp)->child[i^1]= t;



                        (*tp)->child[0]->state= -((*tp)->state>0);

                        (*tp)->child[1]->state=   (*tp)->state<0 ;

                        (*tp)->state=0;

                    }else{

                        *tp= *child;

                        *child= (*child)->child[i^1];

                        (*tp)->child[i^1]= t;

                        if((*tp)->state) t->state  = 0;

                        else             t->state>>= 1;

                        (*tp)->state= -t->state;

                    }

                }

            }

            if(!(*tp)->state ^ !!*next)

                return key;

        }

        return ret;

    }else{

        *tp= *next; *next= NULL;

        (*tp)->elem= key;

        return NULL;

    }

}

void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){

    AVTreeNode *t= *tp;

    if(t){

        unsigned int v= cmp(t->elem, key);

        void *ret;

        if(!v){

            if(*next)

                return t->elem;

            else if(t->child[0]||t->child[1]){

                int i= !t->child[0];

                void *next_elem[2];

                av_tree_find(t->child[i], key, cmp, next_elem);

                key= t->elem= next_elem[i];

                v= -i;

            }else{

                *next= t;

                *tp=NULL;

                return NULL;

            }

        }

        ret= av_tree_insert(&t->child[v>>31], key, cmp, next);

        if(!ret){

            int i= (v>>31) ^ !!*next;

            AVTreeNode **child= &t->child[i];

            t->state += 2*i - 1;



            if(!(t->state&1)){

                if(t->state){

                    



































                    if((*child)->state*2 == -t->state){

                        *tp= (*child)->child[i^1];

                        (*child)->child[i^1]= (*tp)->child[i];

                        (*tp)->child[i]= *child;

                        *child= (*tp)->child[i^1];

                        (*tp)->child[i^1]= t;



                        (*tp)->child[0]->state= -((*tp)->state>0);

                        (*tp)->child[1]->state=   (*tp)->state<0 ;

                        (*tp)->state=0;

                    }else{

                        *tp= *child;

                        *child= (*child)->child[i^1];

                        (*tp)->child[i^1]= t;

                        if((*tp)->state) t->state  = 0;

                        else             t->state>>= 1;

                        (*tp)->state= -t->state;

                    }

                }

            }

            if(!(*tp)->state ^ !!*next)

                return key;

        }

        return ret;

    }else{

        *tp= *next; *next= NULL;

        (*tp)->elem= key;

        return NULL;

    }

}

        (*tp)->elem= key;         return NULL;
void *FUNC_0(AVTreeNode **VAR_0, void *VAR_3, int (*VAR_2)(void *VAR_3, const void *VAR_3), AVTreeNode **VAR_4){

    AVTreeNode *t= *VAR_0;

    if(t){

        unsigned int VAR_5= VAR_2(t->elem, VAR_3);

        void *VAR_6;

        if(!VAR_5){

            if(*VAR_4)

                return t->elem;

            else if(t->child[0]||t->child[1]){

                int VAR_9= !t->child[0];

                void *VAR_8[2];

                av_tree_find(t->child[VAR_9], VAR_3, VAR_2, VAR_8);

                VAR_3= t->elem= VAR_8[VAR_9];

                VAR_5= -VAR_9;

            }else{

                *VAR_4= t;

                *VAR_0=NULL;

                return NULL;

            }

        }

        VAR_6= FUNC_0(&t->child[VAR_5>>31], VAR_3, VAR_2, VAR_4);

        if(!VAR_6){

            int VAR_9= (VAR_5>>31) ^ !!*VAR_4;

            AVTreeNode **child= &t->child[VAR_9];

            t->state += 2*VAR_9 - 1;



            if(!(t->state&1)){

                if(t->state){

                    



































                    if((*child)->state*2 == -t->state){

                        *VAR_0= (*child)->child[VAR_9^1];

                        (*child)->child[VAR_9^1]= (*VAR_0)->child[VAR_9];

                        (*VAR_0)->child[VAR_9]= *child;

                        *child= (*VAR_0)->child[VAR_9^1];

                        (*VAR_0)->child[VAR_9^1]= t;



                        (*VAR_0)->child[0]->state= -((*VAR_0)->state>0);

                        (*VAR_0)->child[1]->state=   (*VAR_0)->state<0 ;

                        (*VAR_0)->state=0;

                    }else{

                        *VAR_0= *child;

                        *child= (*child)->child[VAR_9^1];

                        (*VAR_0)->child[VAR_9^1]= t;

                        if((*VAR_0)->state) t->state  = 0;

                        else             t->state>>= 1;

                        (*VAR_0)->state= -t->state;

                    }

                }

            }

            if(!(*VAR_0)->state ^ !!*VAR_4)

                return VAR_3;

        }

        return VAR_6;

    }else{

        *VAR_0= *VAR_4; *VAR_4= NULL;

        (*VAR_0)->elem= VAR_3;

        return NULL;

    }

}

void *FUNC_0(AVTreeNode **VAR_0, void *VAR_3, int (*VAR_2)(void *VAR_3, const void *VAR_3), AVTreeNode **VAR_4){ AVTreeNode *t= *VAR_0; if(t){ unsigned int VAR_5= VAR_2(t->elem, VAR_3); void *VAR_6; if(!VAR_5){ if(*VAR_4)
return t->elem; else if(t->child[0]||t->child[1]){ int VAR_9= !t->child[0]; void *VAR_8[2]; av_tree_find(t->child[VAR_9], VAR_3, VAR_2, VAR_8); VAR_3= t->elem= VAR_8[VAR_9]; VAR_5= -VAR_9; }else{ *VAR_4= t; *VAR_0=NULL; return NULL; } } VAR_6= FUNC_0(&t->child[VAR_5>>31], VAR_3, VAR_2, VAR_4); if(!VAR_6){ int VAR_9= (VAR_5>>31) ^ !!*VAR_4; AVTreeNode **child= &t->child[VAR_9]; t->state += 2*VAR_9 - 1; if(!(t->state&1)){ if(t->state){ if((*child)->state*2 == -t->state){ *VAR_0= (*child)->child[VAR_9^1]; (*child)->child[VAR_9^1]= (*VAR_0)->child[VAR_9]; (*VAR_0)->child[VAR_9]= *child; *child= (*VAR_0)->child[VAR_9^1]; (*VAR_0)->child[VAR_9^1]= t; (*VAR_0)->child[0]->state= -((*VAR_0)->state>0); (*VAR_0)->child[1]->state=   (*VAR_0)->state<0 ; (*VAR_0)->state=0; }else{ *VAR_0= *child; *child= (*child)->child[VAR_9^1]; (*VAR_0)->child[VAR_9^1]= t; if((*VAR_0)->state) t->state  = 0; else             t->state>>= 1; (*VAR_0)->state= -t->state; } } } if(!(*VAR_0)->state ^ !!*VAR_4)
return VAR_3; } return VAR_6; }else{ *VAR_0= *VAR_4; *VAR_4= NULL; (*VAR_0)->elem= VAR_3; return NULL; } }