1/* 2 * copyright (c) 2006 Michael Niedermayer <michaelni@gmx.at> 3 * 4 * This file is part of FFmpeg. 5 * 6 * FFmpeg is free software; you can redistribute it and/or 7 * modify it under the terms of the GNU Lesser General Public 8 * License as published by the Free Software Foundation; either 9 * version 2.1 of the License, or (at your option) any later version. 10 * 11 * FFmpeg is distributed in the hope that it will be useful, 12 * but WITHOUT ANY WARRANTY; without even the implied warranty of 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14 * Lesser General Public License for more details. 15 * 16 * You should have received a copy of the GNU Lesser General Public 17 * License along with FFmpeg; if not, write to the Free Software 18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA 19 */ 20 21#include "common.h" 22#include "log.h" 23#include "tree.h" 24 25typedef struct AVTreeNode{ 26 struct AVTreeNode *child[2]; 27 void *elem; 28 int state; 29}AVTreeNode; 30 31const int av_tree_node_size = sizeof(AVTreeNode); 32 33void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ 34 if(t){ 35 unsigned int v= cmp(key, t->elem); 36 if(v){ 37 if(next) next[v>>31]= t->elem; 38 return av_tree_find(t->child[(v>>31)^1], key, cmp, next); 39 }else{ 40 if(next){ 41 av_tree_find(t->child[0], key, cmp, next); 42 av_tree_find(t->child[1], key, cmp, next); 43 } 44 return t->elem; 45 } 46 } 47 return NULL; 48} 49 50void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b), AVTreeNode **next){ 51 AVTreeNode *t= *tp; 52 if(t){ 53 unsigned int v= cmp(t->elem, key); 54 void *ret; 55 if(!v){ 56 if(*next) 57 return t->elem; 58 else if(t->child[0]||t->child[1]){ 59 int i= !t->child[0]; 60 void *next_elem[2]; 61 av_tree_find(t->child[i], key, cmp, next_elem); 62 key= t->elem= next_elem[i]; 63 v= -i; 64 }else{ 65 *next= t; 66 *tp=NULL; 67 return NULL; 68 } 69 } 70 ret= av_tree_insert(&t->child[v>>31], key, cmp, next); 71 if(!ret){ 72 int i= (v>>31) ^ !!*next; 73 AVTreeNode **child= &t->child[i]; 74 t->state += 2*i - 1; 75 76 if(!(t->state&1)){ 77 if(t->state){ 78 /* The following code is equivalent to 79 if((*child)->state*2 == -t->state) 80 rotate(child, i^1); 81 rotate(tp, i); 82 83 with rotate(): 84 static void rotate(AVTreeNode **tp, int i){ 85 AVTreeNode *t= *tp; 86 87 *tp= t->child[i]; 88 t->child[i]= t->child[i]->child[i^1]; 89 (*tp)->child[i^1]= t; 90 i= 4*t->state + 2*(*tp)->state + 12; 91 t ->state= ((0x614586 >> i) & 3)-1; 92 (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1; 93 } 94 but such a rotate function is both bigger and slower 95 */ 96 if((*child)->state*2 == -t->state){ 97 *tp= (*child)->child[i^1]; 98 (*child)->child[i^1]= (*tp)->child[i]; 99 (*tp)->child[i]= *child; 100 *child= (*tp)->child[i^1]; 101 (*tp)->child[i^1]= t; 102 103 (*tp)->child[0]->state= -((*tp)->state>0); 104 (*tp)->child[1]->state= (*tp)->state<0 ; 105 (*tp)->state=0; 106 }else{ 107 *tp= *child; 108 *child= (*child)->child[i^1]; 109 (*tp)->child[i^1]= t; 110 if((*tp)->state) t->state = 0; 111 else t->state>>= 1; 112 (*tp)->state= -t->state; 113 } 114 } 115 } 116 if(!(*tp)->state ^ !!*next) 117 return key; 118 } 119 return ret; 120 }else{ 121 *tp= *next; *next= NULL; 122 if(*tp){ 123 (*tp)->elem= key; 124 return NULL; 125 }else 126 return key; 127 } 128} 129 130void av_tree_destroy(AVTreeNode *t){ 131 if(t){ 132 av_tree_destroy(t->child[0]); 133 av_tree_destroy(t->child[1]); 134 av_free(t); 135 } 136} 137 138#if 0 139void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){ 140 int v= f(opaque, t->elem); 141 if(v>=0) av_tree_enumerate(t->child[0], opaque, f); 142 if(v<=0) av_tree_enumerate(t->child[1], opaque, f); 143} 144#endif 145 146#ifdef TEST 147#undef random 148static int check(AVTreeNode *t){ 149 if(t){ 150 int left= check(t->child[0]); 151 int right= check(t->child[1]); 152 153 if(left>999 || right>999) 154 return 1000; 155 if(right - left != t->state) 156 return 1000; 157 if(t->state>1 || t->state<-1) 158 return 1000; 159 return FFMAX(left, right)+1; 160 } 161 return 0; 162} 163 164static void print(AVTreeNode *t, int depth){ 165 int i; 166 for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " "); 167 if(t){ 168 av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem); 169 print(t->child[0], depth+1); 170 print(t->child[1], depth+1); 171 }else 172 av_log(NULL, AV_LOG_ERROR, "NULL\n"); 173} 174 175int cmp(const void *a, const void *b){ 176 return a-b; 177} 178 179int main(void){ 180 int i,k; 181 AVTreeNode *root= NULL, *node=NULL; 182 183 for(i=0; i<10000; i++){ 184 int j= (random()%86294); 185 if(check(root) > 999){ 186 av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); 187 print(root, 0); 188 return -1; 189 } 190 av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); 191 if(!node) 192 node= av_mallocz(av_tree_node_size); 193 av_tree_insert(&root, (void*)(j+1), cmp, &node); 194 195 j= (random()%86294); 196 { 197 AVTreeNode *node2=NULL; 198 av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); 199 av_tree_insert(&root, (void*)(j+1), cmp, &node2); 200 k= av_tree_find(root, (void*)(j+1), cmp, NULL); 201 if(k) 202 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i); 203 } 204 } 205 return 0; 206} 207#endif 208