libavutil/tree.c

   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
  25 typedef struct AVTreeNode{
  26     struct AVTreeNode *child[2];
  27     void *elem;
  28     int state;
  29 }AVTreeNode;
  30
  31 const int av_tree_node_size = sizeof(AVTreeNode);
  32
  33 void *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
  50 void *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                 AVTreeNode **child= &t->child[i];
  61                 void *next_elem[2];
  62                 av_tree_find(*child, key, cmp, next_elem);
  63                 key= t->elem= next_elem[i];
  64                 v= -i;
  65             }else{
  66                 *next= t;
  67                 *tp=NULL;
  68                 return NULL;
  69             }
  70         }
  71         ret= av_tree_insert(&t->child[v>>31], key, cmp, next);
  72         if(!ret){
  73             int i= (v>>31) ^ !!*next;
  74             AVTreeNode **child= &t->child[i];
  75             t->state += 2*i - 1;
  76
  77             if(!(t->state&1)){
  78                 if(t->state){
  79                     if((*child)->state*2 == -t->state){
  80                         *tp= (*child)->child[i^1];
  81                         (*child)->child[i^1]= (*tp)->child[i];
  82                         (*tp)->child[i]= *child;
  83                         *child= (*tp)->child[i^1];
  84                         (*tp)->child[i^1]= t;
  85
  86                         (*tp)->child[0]->state= -((*tp)->state>0);
  87                         (*tp)->child[1]->state=   (*tp)->state<0 ;
  88                         (*tp)->state=0;
  89                     }else{
  90                         *tp= *child;
  91                         *child= (*child)->child[i^1];
  92                         (*tp)->child[i^1]= t;
  93                         if((*tp)->state) t->state  = 0;
  94                         else             t->state>>= 1;
  95                         (*tp)->state= -t->state;
  96                     }
  97                 }
  98             }
  99             if(!(*tp)->state ^ !!*next)
 100                 return key;
 101         }
 102         return ret;
 103     }else{
 104         *tp= *next; *next= NULL;
 105         (*tp)->elem= key;
 106         return NULL;
 107     }
 108 }
 109
 110 void av_tree_destroy(AVTreeNode *t){
 111     av_tree_destroy(t->child[0]);
 112     av_tree_destroy(t->child[1]);
 113     av_free(t);
 114 }
 115
 116 #if 0
 117 void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){
 118     int v= f(opaque, t->elem);
 119     if(v>=0) av_tree_enumerate(t->child[0], opaque, f);
 120     if(v<=0) av_tree_enumerate(t->child[1], opaque, f);
 121 }
 122 #endif
 123
 124 #ifdef TEST
 125 #undef random
 126 static int check(AVTreeNode *t){
 127     if(t){
 128         int left= check(t->child[0]);
 129         int right= check(t->child[1]);
 130
 131         if(left>999 || right>999)
 132             return 1000;
 133         if(right - left != t->state)
 134             return 1000;
 135         if(t->state>1 || t->state<-1)
 136             return 1000;
 137         return FFMAX(left, right)+1;
 138     }
 139     return 0;
 140 }
 141
 142 static void print(AVTreeNode *t, int depth){
 143     int i;
 144     for(i=0; i<depth*4; i++) av_log(NULL, AV_LOG_ERROR, " ");
 145     if(t){
 146         av_log(NULL, AV_LOG_ERROR, "Node %p %2d %4d\n", t, t->state, t->elem);
 147         print(t->child[0], depth+1);
 148         print(t->child[1], depth+1);
 149     }else
 150         av_log(NULL, AV_LOG_ERROR, "NULL\n");
 151 }
 152
 153 int cmp(const void *a, const void *b){
 154     return a-b;
 155 }
 156
 157 int main(void){
 158     int i,k;
 159     AVTreeNode *root= NULL, *node=NULL;
 160
 161     for(i=0; i<10000; i++){
 162         int j= (random()%86294);
 163         if(check(root) > 999){
 164             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
 165         print(root, 0);
 166             return -1;
 167         }
 168         av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j);
 169         if(!node)
 170             node= av_mallocz(av_tree_node_size);
 171         av_tree_insert(&root, (void*)(j+1), cmp, &node);
 172
 173         j= (random()%86294);
 174         k= av_tree_find(root, (void*)(j+1), cmp, NULL);
 175         if(k){
 176             AVTreeNode *node2=NULL;
 177             av_tree_insert(&root, (void*)(j+1), cmp, &node2);
 178             k= av_tree_find(root, (void*)(j+1), cmp, NULL);
 179             if(k)
 180                 av_log(NULL, AV_LOG_ERROR, "removial failure %d\n", i);
 181         }
 182     }
 183     return 0;
 184 }
 185 #endif