tree.c 6.3 KB
Newer Older
Michael Niedermayer's avatar
Michael Niedermayer committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
/*
 * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
 *
 * This file is part of FFmpeg.
 *
 * FFmpeg is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * FFmpeg is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public
 * License along with FFmpeg; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include "common.h"
#include "log.h"
#include "tree.h"

typedef struct AVTreeNode{
    struct AVTreeNode *child[2];
    void *elem;
    int state;
}AVTreeNode;

31 32
const int av_tree_node_size = sizeof(AVTreeNode);

Michael Niedermayer's avatar
Michael Niedermayer committed
33 34
void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
    if(t){
35
        unsigned int v= cmp(key, t->elem);
Michael Niedermayer's avatar
Michael Niedermayer committed
36
        if(v){
37 38
            if(next) next[v>>31]= t->elem;
            return av_tree_find(t->child[(v>>31)^1], key, cmp, next);
Michael Niedermayer's avatar
Michael Niedermayer committed
39
        }else{
40 41 42 43
            if(next){
                av_tree_find(t->child[0], key, cmp, next);
                av_tree_find(t->child[1], key, cmp, next);
            }
Michael Niedermayer's avatar
Michael Niedermayer committed
44 45 46 47 48 49
            return t->elem;
        }
    }
    return NULL;
}

50
void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
Michael Niedermayer's avatar
Michael Niedermayer committed
51 52 53
    AVTreeNode *t= *tp;
    if(t){
        unsigned int v= cmp(t->elem, key);
54 55 56 57 58 59 60
        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];
Michael Niedermayer's avatar
Michael Niedermayer committed
61
                av_tree_find(t->child[i], key, cmp, next_elem);
62 63 64 65 66 67 68 69
                key= t->elem= next_elem[i];
                v= -i;
            }else{
                *next= t;
                *tp=NULL;
                return NULL;
            }
        }
Michael Niedermayer's avatar
Michael Niedermayer committed
70 71 72 73 74
        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;
75

Michael Niedermayer's avatar
Michael Niedermayer committed
76 77
            if(!(t->state&1)){
                if(t->state){
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95
                    /* 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
                    */
Michael Niedermayer's avatar
Michael Niedermayer committed
96 97 98 99 100 101
                    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;
Michael Niedermayer's avatar
Michael Niedermayer committed
102

Michael Niedermayer's avatar
Michael Niedermayer committed
103 104 105 106 107 108 109 110 111 112
                        (*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;
Michael Niedermayer's avatar
Michael Niedermayer committed
113 114 115
                    }
                }
            }
Michael Niedermayer's avatar
Michael Niedermayer committed
116 117 118 119
            if(!(*tp)->state ^ !!*next)
                return key;
        }
        return ret;
Michael Niedermayer's avatar
Michael Niedermayer committed
120
    }else{
121
        *tp= *next; *next= NULL;
122 123 124 125 126
        if(*tp){
            (*tp)->elem= key;
            return NULL;
        }else
            return key;
Michael Niedermayer's avatar
Michael Niedermayer committed
127 128 129 130 131 132 133 134 135 136 137
    }
}

void av_tree_destroy(AVTreeNode *t){
    av_tree_destroy(t->child[0]);
    av_tree_destroy(t->child[1]);
    av_free(t);
}

#if 0
void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
138 139 140
    int v= f(opaque, t->elem);
    if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
    if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
Michael Niedermayer's avatar
Michael Niedermayer committed
141 142 143 144
}
#endif

#ifdef TEST
Michael Niedermayer's avatar
Michael Niedermayer committed
145
#undef random
Michael Niedermayer's avatar
Michael Niedermayer committed
146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
static int check(AVTreeNode *t){
    if(t){
        int left= check(t->child[0]);
        int right= check(t->child[1]);

        if(left>999 || right>999)
            return 1000;
        if(right - left != t->state)
            return 1000;
        if(t->state>1 || t->state<-1)
            return 1000;
        return FFMAX(left, right)+1;
    }
    return 0;
}

static void print(AVTreeNode *t, int depth){
    int i;
    for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
    if(t){
        av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
        print(t->child[0], depth+1);
        print(t->child[1], depth+1);
    }else
        av_log(NULL, AV_LOG_ERROR, "NULL\n");
}

int cmp(const void *a, const void *b){
    return a-b;
}

Diego Biurrun's avatar
Diego Biurrun committed
177
int main(void){
178
    int i,k;
179
    AVTreeNode *root= NULL, *node=NULL;
Michael Niedermayer's avatar
Michael Niedermayer committed
180 181

    for(i=0; i<10000; i++){
182
        int j= (random()%86294);
Michael Niedermayer's avatar
Michael Niedermayer committed
183 184 185 186 187 188
        if(check(root) > 999){
            av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
        print(root, 0);
            return -1;
        }
        av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
189 190 191 192 193
        if(!node)
            node= av_mallocz(av_tree_node_size);
        av_tree_insert(&root, (void*)(j+1), cmp, &node);

        j= (random()%86294);
194
        {
195
            AVTreeNode *node2=NULL;
196
            av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
197 198 199 200 201
            av_tree_insert(&root, (void*)(j+1), cmp, &node2);
            k= av_tree_find(root, (void*)(j+1), cmp, NULL);
            if(k)
                av_log(NULL, AV_LOG_ERROR, "removial failure %d\n", i);
        }
Michael Niedermayer's avatar
Michael Niedermayer committed
202 203 204 205
    }
    return 0;
}
#endif