Libav 0.7.1
|
00001 /* 00002 * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> 00003 * 00004 * This file is part of Libav. 00005 * 00006 * Libav 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 * Libav 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 Libav; 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