← Back to branch summary

~medibuntu-maintainers/mplayer/medibuntu.precise

« back to all changes in this revision

Viewing changes to ffmpeg/libavutil/tree.c

  • Committer: Package Import Robot
  • Author(s): Reinhard Tartler
  • Date: 2012-01-12 22:23:28 UTC
  • mfrom: (0.4.7 sid)
  • mto: This revision was merged to the branch mainline in revision 76.
  • Revision ID: package-import@ubuntu.com-20120112222328-8jqdyodym3p84ygu
Tags: 2:1.0~rc4.dfsg1+svn34540-1
* New upstream snapshot
* upload to unstable

Show diffs side-by-side

added added

removed removed

Lines of Context:
ffmpeg/libavutil/tree.c
21
21
#include "log.h"
22
22
#include "tree.h"
23
23
 
24
 
typedef struct AVTreeNode{
 
24
typedef struct AVTreeNode {
25
25
    struct AVTreeNode *child[2];
26
26
    void *elem;
27
27
    int state;
28
 
}AVTreeNode;
 
28
} AVTreeNode;
29
29
 
30
30
const int av_tree_node_size = sizeof(AVTreeNode);
31
31
 
32
 
void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
33
 
    if(t){
34
 
        unsigned int v= cmp(key, t->elem);
35
 
        if(v){
36
 
            if(next) next[v>>31]= t->elem;
37
 
            return av_tree_find(t->child[(v>>31)^1], key, cmp, next);
38
 
        }else{
39
 
            if(next){
 
32
void *av_tree_find(const AVTreeNode *t, void *key,
 
33
                   int (*cmp)(void *key, const void *b), void *next[2])
 
34
{
 
35
    if (t) {
 
36
        unsigned int v = cmp(key, t->elem);
 
37
        if (v) {
 
38
            if (next) next[v >> 31] = t->elem;
 
39
            return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next);
 
40
        } else {
 
41
            if (next) {
40
42
                av_tree_find(t->child[0], key, cmp, next);
41
43
                av_tree_find(t->child[1], key, cmp, next);
42
44
            }
46
48
    return NULL;
47
49
}
48
50
 
49
 
void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
50
 
    AVTreeNode *t= *tp;
51
 
    if(t){
52
 
        unsigned int v= cmp(t->elem, key);
 
51
void *av_tree_insert(AVTreeNode **tp, void *key,
 
52
                     int (*cmp)(void *key, const void *b), AVTreeNode **next)
 
53
{
 
54
    AVTreeNode *t = *tp;
 
55
    if (t) {
 
56
        unsigned int v = cmp(t->elem, key);
53
57
        void *ret;
54
 
        if(!v){
55
 
            if(*next)
 
58
        if (!v) {
 
59
            if (*next)
56
60
                return t->elem;
57
 
            else if(t->child[0]||t->child[1]){
58
 
                int i= !t->child[0];
 
61
            else if (t->child[0] || t->child[1]) {
 
62
                int i = !t->child[0];
59
63
                void *next_elem[2];
60
64
                av_tree_find(t->child[i], key, cmp, next_elem);
61
 
                key= t->elem= next_elem[i];
62
 
                v= -i;
63
 
            }else{
64
 
                *next= t;
65
 
                *tp=NULL;
 
65
                key = t->elem = next_elem[i];
 
66
                v = -i;
 
67
            } else {
 
68
                *next = t;
 
69
                *tp = NULL;
66
70
                return NULL;
67
71
            }
68
72
        }
69
 
        ret= av_tree_insert(&t->child[v>>31], key, cmp, next);
70
 
        if(!ret){
71
 
            int i= (v>>31) ^ !!*next;
72
 
            AVTreeNode **child= &t->child[i];
73
 
            t->state += 2*i - 1;
 
73
        ret = av_tree_insert(&t->child[v >> 31], key, cmp, next);
 
74
        if (!ret) {
 
75
            int i = (v >> 31) ^ !!*next;
 
76
            AVTreeNode **child = &t->child[i];
 
77
            t->state += 2 * i - 1;
74
78
 
75
 
            if(!(t->state&1)){
76
 
                if(t->state){
 
79
            if (!(t->state & 1)) {
 
80
                if (t->state) {
77
81
                    /* The following code is equivalent to
78
82
                    if((*child)->state*2 == -t->state)
79
83
                        rotate(child, i^1);
80
84
                    rotate(tp, i);
81
85
 
82
86
                    with rotate():
83
 
                    static void rotate(AVTreeNode **tp, int i){
 
87
                    static void rotate(AVTreeNode **tp, int i) {
84
88
                        AVTreeNode *t= *tp;
85
89
 
86
90
                        *tp= t->child[i];
92
96
                    }
93
97
                    but such a rotate function is both bigger and slower
94
98
                    */
95
 
                    if((*child)->state*2 == -t->state){
96
 
                        *tp= (*child)->child[i^1];
97
 
                        (*child)->child[i^1]= (*tp)->child[i];
98
 
                        (*tp)->child[i]= *child;
99
 
                        *child= (*tp)->child[i^1];
100
 
                        (*tp)->child[i^1]= t;
 
99
                    if (( *child )->state * 2 == -t->state) {
 
100
                        *tp                    = (*child)->child[i ^ 1];
 
101
                        (*child)->child[i ^ 1] = (*tp)->child[i];
 
102
                        (*tp)->child[i]        = *child;
 
103
                        *child                 = ( *tp )->child[i ^ 1];
 
104
                        (*tp)->child[i ^ 1]    = t;
101
105
 
102
 
                        (*tp)->child[0]->state= -((*tp)->state>0);
103
 
                        (*tp)->child[1]->state=   (*tp)->state<0 ;
104
 
                        (*tp)->state=0;
105
 
                    }else{
106
 
                        *tp= *child;
107
 
                        *child= (*child)->child[i^1];
108
 
                        (*tp)->child[i^1]= t;
109
 
                        if((*tp)->state) t->state  = 0;
110
 
                        else             t->state>>= 1;
111
 
                        (*tp)->state= -t->state;
 
106
                        (*tp)->child[0]->state = -((*tp)->state > 0);
 
107
                        (*tp)->child[1]->state =   (*tp)->state < 0;
 
108
                        (*tp)->state           = 0;
 
109
                    } else {
 
110
                        *tp                    = *child;
 
111
                        *child                 = (*child)->child[i ^ 1];
 
112
                        (*tp)->child[i ^ 1]    = t;
 
113
                        if ((*tp)->state) t->state = 0;
 
114
                        else              t->state >>= 1;
 
115
                        (*tp)->state           = -t->state;
112
116
                    }
113
117
                }
114
118
            }
115
 
            if(!(*tp)->state ^ !!*next)
 
119
            if (!(*tp)->state ^ !!*next)
116
120
                return key;
117
121
        }
118
122
        return ret;
119
 
    }else{
120
 
        *tp= *next; *next= NULL;
121
 
        if(*tp){
122
 
            (*tp)->elem= key;
 
123
    } else {
 
124
        *tp   = *next;
 
125
        *next = NULL;
 
126
        if (*tp) {
 
127
            (*tp)->elem = key;
123
128
            return NULL;
124
 
        }else
 
129
        } else
125
130
            return key;
126
131
    }
127
132
}
128
133
 
129
 
void av_tree_destroy(AVTreeNode *t){
130
 
    if(t){
 
134
void av_tree_destroy(AVTreeNode *t)
 
135
{
 
136
    if (t) {
131
137
        av_tree_destroy(t->child[0]);
132
138
        av_tree_destroy(t->child[1]);
133
139
        av_free(t);
134
140
    }
135
141
}
136
142
 
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
 
        int v= cmp ? cmp(opaque, t->elem) : 0;
140
 
        if(v>=0) av_tree_enumerate(t->child[0], opaque, cmp, enu);
141
 
        if(v==0) enu(opaque, t->elem);
142
 
        if(v<=0) av_tree_enumerate(t->child[1], opaque, cmp, enu);
 
143
void av_tree_enumerate(AVTreeNode *t, void *opaque,
 
144
                       int (*cmp)(void *opaque, void *elem),
 
145
                       int (*enu)(void *opaque, void *elem))
 
146
{
 
147
    if (t) {
 
148
        int v = cmp ? cmp(opaque, t->elem) : 0;
 
149
        if (v >= 0)
 
150
            av_tree_enumerate(t->child[0], opaque, cmp, enu);
 
151
        if (v == 0)
 
152
            enu(opaque, t->elem);
 
153
        if (v <= 0)
 
154
            av_tree_enumerate(t->child[1], opaque, cmp, enu);
143
155
    }
144
156
}
145
157
 
147
159
 
148
160
#include "lfg.h"
149
161
 
150
 
static int check(AVTreeNode *t){
151
 
    if(t){
152
 
        int left= check(t->child[0]);
153
 
        int right= check(t->child[1]);
 
162
static int check(AVTreeNode *t)
 
163
{
 
164
    if (t) {
 
165
        int left  = check(t->child[0]);
 
166
        int right = check(t->child[1]);
154
167
 
155
 
        if(left>999 || right>999)
156
 
            return 1000;
157
 
        if(right - left != t->state)
158
 
            return 1000;
159
 
        if(t->state>1 || t->state<-1)
160
 
            return 1000;
161
 
        return FFMAX(left, right)+1;
 
168
        if (left>999 || right>999)
 
169
            return 1000;
 
170
        if (right - left != t->state)
 
171
            return 1000;
 
172
        if (t->state>1 || t->state<-1)
 
173
            return 1000;
 
174
        return FFMAX(left, right) + 1;
162
175
    }
163
176
    return 0;
164
177
}
165
178
 
166
 
static void print(AVTreeNode *t, int depth){
 
179
static void print(AVTreeNode *t, int depth)
 
180
{
167
181
    int i;
168
 
    for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
169
 
    if(t){
 
182
    for (i = 0; i < depth * 4; i++) av_log(NULL, AV_LOG_ERROR, " ");
 
183
    if (t) {
170
184
        av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
171
 
        print(t->child[0], depth+1);
172
 
        print(t->child[1], depth+1);
173
 
    }else
 
185
        print(t->child[0], depth + 1);
 
186
        print(t->child[1], depth + 1);
 
187
    } else
174
188
        av_log(NULL, AV_LOG_ERROR, "NULL\n");
175
189
}
176
190
 
177
 
static int cmp(void *a, const void *b){
178
 
    return (uint8_t*)a-(const uint8_t*)b;
 
191
static int cmp(void *a, const void *b)
 
192
{
 
193
    return (uint8_t *) a - (const uint8_t *) b;
179
194
}
180
195
 
181
 
int main(void){
 
196
int main (void)
 
197
{
182
198
    int i;
183
199
    void *k;
184
 
    AVTreeNode *root= NULL, *node=NULL;
 
200
    AVTreeNode *root = NULL, *node = NULL;
185
201
    AVLFG prng;
186
202
 
187
203
    av_lfg_init(&prng, 1);
188
204
 
189
 
    for(i=0; i<10000; i++){
 
205
    for (i = 0; i < 10000; i++) {
190
206
        int j = av_lfg_get(&prng) % 86294;
191
 
        if(check(root) > 999){
 
207
        if (check(root) > 999) {
192
208
            av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
193
209
        print(root, 0);
194
210
            return -1;
195
211
        }
196
212
        av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
197
 
        if(!node)
198
 
            node= av_mallocz(av_tree_node_size);
199
 
        av_tree_insert(&root, (void*)(j+1), cmp, &node);
 
213
        if (!node)
 
214
            node = av_mallocz(av_tree_node_size);
 
215
        av_tree_insert(&root, (void *) (j + 1), cmp, &node);
200
216
 
201
217
        j = av_lfg_get(&prng) % 86294;
202
218
        {
203
 
            AVTreeNode *node2=NULL;
 
219
            AVTreeNode *node2 = NULL;
204
220
            av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
205
 
            av_tree_insert(&root, (void*)(j+1), cmp, &node2);
206
 
            k= av_tree_find(root, (void*)(j+1), cmp, NULL);
207
 
            if(k)
 
221
            av_tree_insert(&root, (void *) (j + 1), cmp, &node2);
 
222
            k = av_tree_find(root, (void *) (j + 1), cmp, NULL);
 
223
            if (k)
208
224
                av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
209
225
        }
210
226
    }