• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • File List
  • Globals

libavutil/tree.c

Go to the documentation of this file.
00001 /*
00002  * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at>
00003  *
00004  * This file is part of FFmpeg.
00005  *
00006  * FFmpeg is free software; you can redistribute it and/or
00007  * modify it under the terms of the GNU Lesser General Public
00008  * License as published by the Free Software Foundation; either
00009  * version 2.1 of the License, or (at your option) any later version.
00010  *
00011  * FFmpeg is distributed in the hope that it will be useful,
00012  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00013  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014  * Lesser General Public License for more details.
00015  *
00016  * You should have received a copy of the GNU Lesser General Public
00017  * License along with FFmpeg; if not, write to the Free Software
00018  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
00019  */
00020 
00021 #include "common.h"
00022 #include "log.h"
00023 #include "tree.h"
00024 
00025 typedef struct AVTreeNode{
00026     struct AVTreeNode *child[2];
00027     void *elem;
00028     int state;
00029 }AVTreeNode;
00030 
00031 const int av_tree_node_size = sizeof(AVTreeNode);
00032 
00033 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
00034     if(t){
00035         unsigned int v= cmp(key, t->elem);
00036         if(v){
00037             if(next) next[v>>31]= t->elem;
00038             return av_tree_find(t->child[(v>>31)^1], key, cmp, next);
00039         }else{
00040             if(next){
00041                 av_tree_find(t->child[0], key, cmp, next);
00042                 av_tree_find(t->child[1], key, cmp, next);
00043             }
00044             return t->elem;
00045         }
00046     }
00047     return NULL;
00048 }
00049 
00050 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
00051     AVTreeNode *t= *tp;
00052     if(t){
00053         unsigned int v= cmp(t->elem, key);
00054         void *ret;
00055         if(!v){
00056             if(*next)
00057                 return t->elem;
00058             else if(t->child[0]||t->child[1]){
00059                 int i= !t->child[0];
00060                 void *next_elem[2];
00061                 av_tree_find(t->child[i], key, cmp, next_elem);
00062                 key= t->elem= next_elem[i];
00063                 v= -i;
00064             }else{
00065                 *next= t;
00066                 *tp=NULL;
00067                 return NULL;
00068             }
00069         }
00070         ret= av_tree_insert(&t->child[v>>31], key, cmp, next);
00071         if(!ret){
00072             int i= (v>>31) ^ !!*next;
00073             AVTreeNode **child= &t->child[i];
00074             t->state += 2*i - 1;
00075 
00076             if(!(t->state&1)){
00077                 if(t->state){
00078                     /* The following code is equivalent to
00079                     if((*child)->state*2 == -t->state)
00080                         rotate(child, i^1);
00081                     rotate(tp, i);
00082 
00083                     with rotate():
00084                     static void rotate(AVTreeNode **tp, int i){
00085                         AVTreeNode *t= *tp;
00086 
00087                         *tp= t->child[i];
00088                         t->child[i]= t->child[i]->child[i^1];
00089                         (*tp)->child[i^1]= t;
00090                         i= 4*t->state + 2*(*tp)->state + 12;
00091                           t  ->state=                     ((0x614586 >> i) & 3)-1;
00092                         (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1;
00093                     }
00094                     but such a rotate function is both bigger and slower
00095                     */
00096                     if((*child)->state*2 == -t->state){
00097                         *tp= (*child)->child[i^1];
00098                         (*child)->child[i^1]= (*tp)->child[i];
00099                         (*tp)->child[i]= *child;
00100                         *child= (*tp)->child[i^1];
00101                         (*tp)->child[i^1]= t;
00102 
00103                         (*tp)->child[0]->state= -((*tp)->state>0);
00104                         (*tp)->child[1]->state=   (*tp)->state<0 ;
00105                         (*tp)->state=0;
00106                     }else{
00107                         *tp= *child;
00108                         *child= (*child)->child[i^1];
00109                         (*tp)->child[i^1]= t;
00110                         if((*tp)->state) t->state  = 0;
00111                         else             t->state>>= 1;
00112                         (*tp)->state= -t->state;
00113                     }
00114                 }
00115             }
00116             if(!(*tp)->state ^ !!*next)
00117                 return key;
00118         }
00119         return ret;
00120     }else{
00121         *tp= *next; *next= NULL;
00122         if(*tp){
00123             (*tp)->elem= key;
00124             return NULL;
00125         }else
00126             return key;
00127     }
00128 }
00129 
00130 void av_tree_destroy(AVTreeNode *t){
00131     if(t){
00132         av_tree_destroy(t->child[0]);
00133         av_tree_destroy(t->child[1]);
00134         av_free(t);
00135     }
00136 }
00137 
00138 #if 0
00139 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
00140     int v= f(opaque, t->elem);
00141     if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
00142     if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
00143 }
00144 #endif
00145 
00146 #ifdef TEST
00147 #undef random
00148 static int check(AVTreeNode *t){
00149     if(t){
00150         int left= check(t->child[0]);
00151         int right= check(t->child[1]);
00152 
00153         if(left>999 || right>999)
00154             return 1000;
00155         if(right - left != t->state)
00156             return 1000;
00157         if(t->state>1 || t->state<-1)
00158             return 1000;
00159         return FFMAX(left, right)+1;
00160     }
00161     return 0;
00162 }
00163 
00164 static void print(AVTreeNode *t, int depth){
00165     int i;
00166     for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
00167     if(t){
00168         av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
00169         print(t->child[0], depth+1);
00170         print(t->child[1], depth+1);
00171     }else
00172         av_log(NULL, AV_LOG_ERROR, "NULL\n");
00173 }
00174 
00175 int cmp(const void *a, const void *b){
00176     return a-b;
00177 }
00178 
00179 int main(void){
00180     int i,k;
00181     AVTreeNode *root= NULL, *node=NULL;
00182 
00183     for(i=0; i<10000; i++){
00184         int j= (random()%86294);
00185         if(check(root) > 999){
00186             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
00187         print(root, 0);
00188             return -1;
00189         }
00190         av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
00191         if(!node)
00192             node= av_mallocz(av_tree_node_size);
00193         av_tree_insert(&root, (void*)(j+1), cmp, &node);
00194 
00195         j= (random()%86294);
00196         {
00197             AVTreeNode *node2=NULL;
00198             av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
00199             av_tree_insert(&root, (void*)(j+1), cmp, &node2);
00200             k= av_tree_find(root, (void*)(j+1), cmp, NULL);
00201             if(k)
00202                 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
00203         }
00204     }
00205     return 0;
00206 }
00207 #endif

Generated on Sat Feb 16 2013 09:23:15 for ffmpeg by  doxygen 1.7.1