tree.c 6.56 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
    }
}

void av_tree_destroy(AVTreeNode *t){
131
    if(t){
Aurelien Jacobs's avatar
Aurelien Jacobs committed
132 133 134
        av_tree_destroy(t->child[0]);
        av_tree_destroy(t->child[1]);
        av_free(t);
135
    }
Michael Niedermayer's avatar
Michael Niedermayer committed
136 137 138
}

#if 0
139
void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)){
140
    if(t){
141 142 143 144
        int v= cmp ? cmp(opaque, t->elem) : 0;
        if(v>=0) av_tree_enumerate(t->child[0], opaque, cmp, enu);
        if(v==0) enu(opaque, t->elem);
        if(v<=0) av_tree_enumerate(t->child[1], opaque, cmp, enu);
145
    }
Michael Niedermayer's avatar
Michael Niedermayer committed
146 147 148 149
}
#endif

#ifdef TEST
150 151 152

#include "lfg.h"

Michael Niedermayer's avatar
Michael Niedermayer committed
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172
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){
173
        av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
Michael Niedermayer's avatar
Michael Niedermayer committed
174 175 176 177 178 179
        print(t->child[0], depth+1);
        print(t->child[1], depth+1);
    }else
        av_log(NULL, AV_LOG_ERROR, "NULL\n");
}

180 181
static int cmp(void *a, const void *b){
    return (uint8_t*)a-(const uint8_t*)b;
Michael Niedermayer's avatar
Michael Niedermayer committed
182 183
}

Diego Biurrun's avatar
Diego Biurrun committed
184
int main(void){
185 186
    int i;
    void *k;
187
    AVTreeNode *root= NULL, *node=NULL;
188
    AVLFG prng;
189

190
    av_lfg_init(&prng, 1);
Michael Niedermayer's avatar
Michael Niedermayer committed
191 192

    for(i=0; i<10000; i++){
193
        int j = av_lfg_get(&prng) % 86294;
Michael Niedermayer's avatar
Michael Niedermayer committed
194 195 196 197 198 199
        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);
200 201 202 203
        if(!node)
            node= av_mallocz(av_tree_node_size);
        av_tree_insert(&root, (void*)(j+1), cmp, &node);

204
        j = av_lfg_get(&prng) % 86294;
205
        {
206
            AVTreeNode *node2=NULL;
207
            av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
208 209 210
            av_tree_insert(&root, (void*)(j+1), cmp, &node2);
            k= av_tree_find(root, (void*)(j+1), cmp, NULL);
            if(k)
211
                av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
212
        }
Michael Niedermayer's avatar
Michael Niedermayer committed
213 214 215 216
    }
    return 0;
}
#endif