diff options
Diffstat (limited to 'contrib/ffmpeg/libavutil/tree.c')
| -rw-r--r-- | contrib/ffmpeg/libavutil/tree.c | 203 |
1 files changed, 0 insertions, 203 deletions
diff --git a/contrib/ffmpeg/libavutil/tree.c b/contrib/ffmpeg/libavutil/tree.c deleted file mode 100644 index cb442ff4b..000000000 --- a/contrib/ffmpeg/libavutil/tree.c +++ /dev/null @@ -1,203 +0,0 @@ -/* - * 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; - -const int av_tree_node_size = sizeof(AVTreeNode); - -void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ - if(t){ - unsigned int v= cmp(key, t->elem); - if(v){ - if(next) next[v>>31]= t->elem; - return av_tree_find(t->child[(v>>31)^1], key, cmp, next); - }else{ - if(next){ - av_tree_find(t->child[0], key, cmp, next); - av_tree_find(t->child[1], key, cmp, next); - } - return t->elem; - } - } - 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){ - /* 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_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)){ - 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); -} -#endif - -#ifdef TEST -#undef random -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; -} - -int main(void){ - int i,k; - AVTreeNode *root= NULL, *node=NULL; - - for(i=0; i<10000; i++){ - int j= (random()%86294); - 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); - if(!node) - node= av_mallocz(av_tree_node_size); - av_tree_insert(&root, (void*)(j+1), cmp, &node); - - j= (random()%86294); - k= av_tree_find(root, (void*)(j+1), cmp, NULL); - if(k){ - AVTreeNode *node2=NULL; - av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); - 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); - } - } - return 0; -} -#endif |