tree.c 6.52 KB
Newer Older
Michael Niedermayer's avatar
Michael Niedermayer committed
1 2 3
/*
 * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
 *
4
 * This file is part of Libav.
Michael Niedermayer's avatar
Michael Niedermayer committed
5
 *
6
 * Libav is free software; you can redistribute it and/or
Michael Niedermayer's avatar
Michael Niedermayer committed
7 8 9 10
 * 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.
 *
11
 * Libav is distributed in the hope that it will be useful,
Michael Niedermayer's avatar
Michael Niedermayer committed
12 13 14 15 16
 * 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
17
 * License along with Libav; if not, write to the Free Software
Michael Niedermayer's avatar
Michael Niedermayer committed
18 19 20 21 22 23 24 25 26 27 28 29
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 */

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

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

30 31
const int av_tree_node_size = sizeof(AVTreeNode);

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

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

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

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

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

137
void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)){
138
    if(t){
139 140 141 142
        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);
143
    }
Michael Niedermayer's avatar
Michael Niedermayer committed
144 145 146
}

#ifdef TEST
147 148 149

#include "lfg.h"

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

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

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

187
    av_lfg_init(&prng, 1);
Michael Niedermayer's avatar
Michael Niedermayer committed
188 189

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

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