git.sesse.net Git - ffmpeg/blob - 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 "log.h"
  22 #include "mem.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 struct AVTreeNode *av_tree_node_alloc(void)
  34 {
  35     return av_mallocz(sizeof(struct AVTreeNode));
  36 }
  37
  38 void *av_tree_find(const AVTreeNode *t, void *key,
  39                    int (*cmp)(void *key, const void *b), void *next[2])
  40 {
  41     if (t) {
  42         unsigned int v = cmp(key, t->elem);
  43         if (v) {
  44             if (next) next[v >> 31] = t->elem;
  45             return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next);
  46         } else {
  47             if (next) {
  48                 av_tree_find(t->child[0], key, cmp, next);
  49                 av_tree_find(t->child[1], key, cmp, next);
  50             }
  51             return t->elem;
  52         }
  53     }
  54     return NULL;
  55 }
  56
  57 void *av_tree_insert(AVTreeNode **tp, void *key,
  58                      int (*cmp)(void *key, const void *b), AVTreeNode **next)
  59 {
  60     AVTreeNode *t = *tp;
  61     if (t) {
  62         unsigned int v = cmp(t->elem, key);
  63         void *ret;
  64         if (!v) {
  65             if (*next)
  66                 return t->elem;
  67             else if (t->child[0] || t->child[1]) {
  68                 int i = !t->child[0];
  69                 void *next_elem[2];
  70                 av_tree_find(t->child[i], key, cmp, next_elem);
  71                 key = t->elem = next_elem[i];
  72                 v = -i;
  73             } else {
  74                 *next = t;
  75                 *tp = NULL;
  76                 return NULL;
  77             }
  78         }
  79         ret = av_tree_insert(&t->child[v >> 31], key, cmp, next);
  80         if (!ret) {
  81             int i = (v >> 31) ^ !!*next;
  82             AVTreeNode **child = &t->child[i];
  83             t->state += 2 * i - 1;
  84
  85             if (!(t->state & 1)) {
  86                 if (t->state) {
  87                     /* The following code is equivalent to
  88                     if((*child)->state*2 == -t->state)
  89                         rotate(child, i^1);
  90                     rotate(tp, i);
  91
  92                     with rotate():
  93                     static void rotate(AVTreeNode **tp, int i) {
  94                         AVTreeNode *t= *tp;
  95
  96                         *tp= t->child[i];
  97                         t->child[i]= t->child[i]->child[i^1];
  98                         (*tp)->child[i^1]= t;
  99                         i= 4*t->state + 2*(*tp)->state + 12;
 100                           t  ->state=                     ((0x614586 >> i) & 3)-1;
 101                         (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1;
 102                     }
 103                     but such a rotate function is both bigger and slower
 104                     */
 105                     if (( *child )->state * 2 == -t->state) {
 106                         *tp                    = (*child)->child[i ^ 1];
 107                         (*child)->child[i ^ 1] = (*tp)->child[i];
 108                         (*tp)->child[i]        = *child;
 109                         *child                 = ( *tp )->child[i ^ 1];
 110                         (*tp)->child[i ^ 1]    = t;
 111
 112                         (*tp)->child[0]->state = -((*tp)->state > 0);
 113                         (*tp)->child[1]->state =   (*tp)->state < 0;
 114                         (*tp)->state           = 0;
 115                     } else {
 116                         *tp                    = *child;
 117                         *child                 = (*child)->child[i ^ 1];
 118                         (*tp)->child[i ^ 1]    = t;
 119                         if ((*tp)->state) t->state = 0;
 120                         else              t->state >>= 1;
 121                         (*tp)->state           = -t->state;
 122                     }
 123                 }
 124             }
 125             if (!(*tp)->state ^ !!*next)
 126                 return key;
 127         }
 128         return ret;
 129     } else {
 130         *tp   = *next;
 131         *next = NULL;
 132         if (*tp) {
 133             (*tp)->elem = key;
 134             return NULL;
 135         } else
 136             return key;
 137     }
 138 }
 139
 140 void av_tree_destroy(AVTreeNode *t)
 141 {
 142     if (t) {
 143         av_tree_destroy(t->child[0]);
 144         av_tree_destroy(t->child[1]);
 145         av_free(t);
 146     }
 147 }
 148
 149 void av_tree_enumerate(AVTreeNode *t, void *opaque,
 150                        int (*cmp)(void *opaque, void *elem),
 151                        int (*enu)(void *opaque, void *elem))
 152 {
 153     if (t) {
 154         int v = cmp ? cmp(opaque, t->elem) : 0;
 155         if (v >= 0)
 156             av_tree_enumerate(t->child[0], opaque, cmp, enu);
 157         if (v == 0)
 158             enu(opaque, t->elem);
 159         if (v <= 0)
 160             av_tree_enumerate(t->child[1], opaque, cmp, enu);
 161     }
 162 }
 163
 164 #ifdef TEST
 165
 166 #include "common.h"
 167 #include "lfg.h"
 168
 169 static int check(AVTreeNode *t)
 170 {
 171     if (t) {
 172         int left  = check(t->child[0]);
 173         int right = check(t->child[1]);
 174
 175         if (left>999 || right>999)
 176             return 1000;
 177         if (right - left != t->state)
 178             return 1000;
 179         if (t->state>1 || t->state<-1)
 180             return 1000;
 181         return FFMAX(left, right) + 1;
 182     }
 183     return 0;
 184 }
 185
 186 static void print(AVTreeNode *t, int depth)
 187 {
 188     int i;
 189     for (i = 0; i < depth * 4; i++) av_log(NULL, AV_LOG_ERROR, " ");
 190     if (t) {
 191         av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem);
 192         print(t->child[0], depth + 1);
 193         print(t->child[1], depth + 1);
 194     } else
 195         av_log(NULL, AV_LOG_ERROR, "NULL\n");
 196 }
 197
 198 static int cmp(void *a, const void *b)
 199 {
 200     return (uint8_t *) a - (const uint8_t *) b;
 201 }
 202
 203 int main (void)
 204 {
 205     int i;
 206     void *k;
 207     AVTreeNode *root = NULL, *node = NULL;
 208     AVLFG prng;
 209
 210     av_lfg_init(&prng, 1);
 211
 212     for (i = 0; i < 10000; i++) {
 213         intptr_t j = av_lfg_get(&prng) % 86294;
 214         if (check(root) > 999) {
 215             av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i);
 216         print(root, 0);
 217             return -1;
 218         }
 219         av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", (int)j);
 220         if (!node)
 221             node = av_tree_node_alloc();
 222         av_tree_insert(&root, (void *) (j + 1), cmp, &node);
 223
 224         j = av_lfg_get(&prng) % 86294;
 225         {
 226             AVTreeNode *node2 = NULL;
 227             av_log(NULL, AV_LOG_ERROR, "removing %4d\n", (int)j);
 228             av_tree_insert(&root, (void *) (j + 1), cmp, &node2);
 229             k = av_tree_find(root, (void *) (j + 1), cmp, NULL);
 230             if (k)
 231                 av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i);
 232         }
 233     }
 234     return 0;
 235 }
 236 #endif