• 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 "log.h"
00022 #include "tree.h"
00023 
00024 typedef struct AVTreeNode{
00025     struct AVTreeNode *child[2];
00026     void *elem;
00027     int state;
00028 }AVTreeNode;
00029 
00030 const int av_tree_node_size = sizeof(AVTreeNode);
00031 
00032 void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){
00033     if(t){
00034         unsigned int v= cmp(key, t->elem);
00035         if(v){
00036             if(next) next[v>>31]= t->elem;
00037             return av_tree_find(t->child[(v>>31)^1], key, cmp, next);
00038         }else{
00039             if(next){
00040                 av_tree_find(t->child[0], key, cmp, next);
00041                 av_tree_find(t->child[1], key, cmp, next);
00042             }
00043             return t->elem;
00044         }
00045     }
00046     return NULL;
00047 }
00048 
00049 void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){
00050     AVTreeNode *t= *tp;
00051     if(t){
00052         unsigned int v= cmp(t->elem, key);
00053         void *ret;
00054         if(!v){
00055             if(*next)
00056                 return t->elem;
00057             else if(t->child[0]||t->child[1]){
00058                 int i= !t->child[0];
00059                 void *next_elem[2];
00060                 av_tree_find(t->child[i], key, cmp, next_elem);
00061                 key= t->elem= next_elem[i];
00062                 v= -i;
00063             }else{
00064                 *next= t;
00065                 *tp=NULL;
00066                 return NULL;
00067             }
00068         }
00069         ret= av_tree_insert(&t->child[v>>31], key, cmp, next);
00070         if(!ret){
00071             int i= (v>>31) ^ !!*next;
00072             AVTreeNode **child= &t->child[i];
00073             t->state += 2*i - 1;
00074 
00075             if(!(t->state&1)){
00076                 if(t->state){
00077                     /* The following code is equivalent to
00078                     if((*child)->state*2 == -t->state)
00079                         rotate(child, i^1);
00080                     rotate(tp, i);
00081 
00082                     with rotate():
00083                     static void rotate(AVTreeNode **tp, int i){
00084                         AVTreeNode *t= *tp;
00085 
00086                         *tp= t->child[i];
00087                         t->child[i]= t->child[i]->child[i^1];
00088                         (*tp)->child[i^1]= t;
00089                         i= 4*t->state + 2*(*tp)->state + 12;
00090                           t  ->state=                     ((0x614586 >> i) & 3)-1;
00091                         (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1;
00092                     }
00093                     but such a rotate function is both bigger and slower
00094                     */
00095                     if((*child)->state*2 == -t->state){
00096                         *tp= (*child)->child[i^1];
00097                         (*child)->child[i^1]= (*tp)->child[i];
00098                         (*tp)->child[i]= *child;
00099                         *child= (*tp)->child[i^1];
00100                         (*tp)->child[i^1]= t;
00101 
00102                         (*tp)->child[0]->state= -((*tp)->state>0);
00103                         (*tp)->child[1]->state=   (*tp)->state<0 ;
00104                         (*tp)->state=0;
00105                     }else{
00106                         *tp= *child;
00107                         *child= (*child)->child[i^1];
00108                         (*tp)->child[i^1]= t;
00109                         if((*tp)->state) t->state  = 0;
00110                         else             t->state>>= 1;
00111                         (*tp)->state= -t->state;
00112                     }
00113                 }
00114             }
00115             if(!(*tp)->state ^ !!*next)
00116                 return key;
00117         }
00118         return ret;
00119     }else{
00120         *tp= *next; *next= NULL;
00121         if(*tp){
00122             (*tp)->elem= key;
00123             return NULL;
00124         }else
00125             return key;
00126     }
00127 }
00128 
00129 void av_tree_destroy(AVTreeNode *t){
00130     if(t){
00131         av_tree_destroy(t->child[0]);
00132         av_tree_destroy(t->child[1]);
00133         av_free(t);
00134     }
00135 }
00136 
00137 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, void *elem), int (*enu)(void *opaque, void *elem)){
00138     if(t){
00139         int v= cmp ? cmp(opaque, t->elem) : 0;
00140         if(v>=0) av_tree_enumerate(t->child[0], opaque, cmp, enu);
00141         if(v==0) enu(opaque, t->elem);
00142         if(v<=0) av_tree_enumerate(t->child[1], opaque, cmp, enu);
00143     }
00144 }
00145 
00146 #ifdef TEST
00147 
00148 #include "lfg.h"
00149 
00150 static int check(AVTreeNode *t){
00151     if(t){
00152         int left= check(t->child[0]);
00153         int right= check(t->child[1]);
00154 
00155         if(left>999 || right>999)
00156             return 1000;
00157         if(right - left != t->state)
00158             return 1000;
00159         if(t->state>1 || t->state<-1)
00160             return 1000;
00161         return FFMAX(left, right)+1;
00162     }
00163     return 0;
00164 }
00165 
00166 static void print(AVTreeNode *t, int depth){
00167     int i;
00168     for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
00169     if(t){
00170         av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
00171         print(t->child[0], depth+1);
00172         print(t->child[1], depth+1);
00173     }else
00174         av_log(NULL, AV_LOG_ERROR, "NULL\n");
00175 }
00176 
00177 static int cmp(void *a, const void *b){
00178     return (uint8_t*)a-(const uint8_t*)b;
00179 }
00180 
00181 int main(void){
00182     int i;
00183     void *k;
00184     AVTreeNode *root= NULL, *node=NULL;
00185     AVLFG prng;
00186 
00187     av_lfg_init(&prng, 1);
00188 
00189     for(i=0; i<10000; i++){
00190         int j = av_lfg_get(&prng) % 86294;
00191         if(check(root) > 999){
00192             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
00193         print(root, 0);
00194             return -1;
00195         }
00196         av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
00197         if(!node)
00198             node= av_mallocz(av_tree_node_size);
00199         av_tree_insert(&root, (void*)(j+1), cmp, &node);
00200 
00201         j = av_lfg_get(&prng) % 86294;
00202         {
00203             AVTreeNode *node2=NULL;
00204             av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j);
00205             av_tree_insert(&root, (void*)(j+1), cmp, &node2);
00206             k= av_tree_find(root, (void*)(j+1), cmp, NULL);
00207             if(k)
00208                 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
00209         }
00210     }
00211     return 0;
00212 }
00213 #endif

Generated on Fri Sep 16 2011 17:17:51 for FFmpeg by  doxygen 1.7.1