X-Git-Url: https://git.sesse.net/?a=blobdiff_plain;f=libavutil%2Ftree.c;h=e614f72cd82971b58a7cc79113d6d182b22ec3bc;hb=9c2f9b0e2dd5bd570e571890bdfb6e77190c4c55;hp=aff749e7910dcb6a2c03ddd974cee63a58baf095;hpb=9eb88fdeba5b72a84f192dee48ec420a57ca208d;p=ffmpeg diff --git a/libavutil/tree.c b/libavutil/tree.c index aff749e7910..e614f72cd82 100644 --- a/libavutil/tree.c +++ b/libavutil/tree.c @@ -1,150 +1,228 @@ /* * copyright (c) 2006 Michael Niedermayer * - * This file is part of FFmpeg. + * This file is part of Libav. * - * FFmpeg is free software; you can redistribute it and/or + * Libav is free software; you can redistribute it and/or * modify it under the terms of the GNU Lesser General Public * License as published by the Free Software Foundation; either * version 2.1 of the License, or (at your option) any later version. * - * FFmpeg is distributed in the hope that it will be useful, + * Libav is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public - * License along with FFmpeg; if not, write to the Free Software + * License along with Libav; if not, write to the Free Software * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA */ -#include "common.h" #include "log.h" #include "tree.h" -typedef struct AVTreeNode{ +typedef struct AVTreeNode { struct AVTreeNode *child[2]; void *elem; int state; -}AVTreeNode; - -void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const void *b), void *next[2]){ - if(t){ - unsigned int v= cmp(t->elem, key); - if(v){ - if(next) next[(v>>31)^1]= t->elem; - return av_tree_find(t->child[v>>31], key, cmp, next); - }else{ +} AVTreeNode; + +const int av_tree_node_size = sizeof(AVTreeNode); + +void *av_tree_find(const AVTreeNode *t, void *key, + int (*cmp)(void *key, const void *b), void *next[2]) +{ + if (t) { + unsigned int v = cmp(key, t->elem); + if (v) { + if (next) next[v >> 31] = t->elem; + return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next); + } else { + if (next) { + av_tree_find(t->child[0], key, cmp, next); + av_tree_find(t->child[1], key, cmp, next); + } return t->elem; } } return NULL; } -void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const void *b)){ - AVTreeNode *t= *tp; - if(t){ - unsigned int v= cmp(t->elem, key); - if(v){ - int i= v>>31; - AVTreeNode **child= &t->child[i]; - void *ret= av_tree_insert(child, key, cmp); - if(!ret){ - t->state -= ((int)v>>31)|1; - if(!(t->state&1)){ - if(t->state){ - if((*child)->state*2 == t->state){ - *tp= *child; - *child= (*child)->child[i^1]; - (*tp)->child[i^1]= t; - t->state= 0; - }else{ - *tp= (*child)->child[i^1]; - (*child)->child[i^1]= (*tp)->child[i]; - (*tp)->child[i]= *child; - *child= (*tp)->child[i^1]; - (*tp)->child[i^1]= t; - - i= (*tp)->state > 0; - (*tp)->child[i ]->state= 0; - (*tp)->child[i^1]->state= -(*tp)->state; - } - (*tp)->state=0; +void *av_tree_insert(AVTreeNode **tp, void *key, + int (*cmp)(void *key, const void *b), AVTreeNode **next) +{ + AVTreeNode *t = *tp; + if (t) { + unsigned int v = cmp(t->elem, key); + void *ret; + if (!v) { + if (*next) + return t->elem; + else if (t->child[0] || t->child[1]) { + int i = !t->child[0]; + void *next_elem[2]; + av_tree_find(t->child[i], key, cmp, next_elem); + key = t->elem = next_elem[i]; + v = -i; + } else { + *next = t; + *tp = NULL; + return NULL; + } + } + ret = av_tree_insert(&t->child[v >> 31], key, cmp, next); + if (!ret) { + int i = (v >> 31) ^ !!*next; + AVTreeNode **child = &t->child[i]; + t->state += 2 * i - 1; + + if (!(t->state & 1)) { + if (t->state) { + /* The following code is equivalent to + if((*child)->state*2 == -t->state) + rotate(child, i^1); + rotate(tp, i); + + with rotate(): + static void rotate(AVTreeNode **tp, int i) { + AVTreeNode *t= *tp; + + *tp= t->child[i]; + t->child[i]= t->child[i]->child[i^1]; + (*tp)->child[i^1]= t; + i= 4*t->state + 2*(*tp)->state + 12; + t ->state= ((0x614586 >> i) & 3)-1; + (*tp)->state= ((*tp)->state>>1) + ((0x400EEA >> i) & 3)-1; + } + but such a rotate function is both bigger and slower + */ + if (( *child )->state * 2 == -t->state) { + *tp = (*child)->child[i ^ 1]; + (*child)->child[i ^ 1] = (*tp)->child[i]; + (*tp)->child[i] = *child; + *child = ( *tp )->child[i ^ 1]; + (*tp)->child[i ^ 1] = t; + + (*tp)->child[0]->state = -((*tp)->state > 0); + (*tp)->child[1]->state = (*tp)->state < 0; + (*tp)->state = 0; + } else { + *tp = *child; + *child = (*child)->child[i ^ 1]; + (*tp)->child[i ^ 1] = t; + if ((*tp)->state) t->state = 0; + else t->state >>= 1; + (*tp)->state = -t->state; } - return key; } } - return ret; - }else{ - return t->elem; + if (!(*tp)->state ^ !!*next) + return key; } - }else{ - *tp= av_mallocz(sizeof(AVTreeNode)); - (*tp)->elem= key; - return NULL; + return ret; + } else { + *tp = *next; + *next = NULL; + if (*tp) { + (*tp)->elem = key; + return NULL; + } else + return key; } } -void av_tree_destroy(AVTreeNode *t){ - av_tree_destroy(t->child[0]); - av_tree_destroy(t->child[1]); - av_free(t); +void av_tree_destroy(AVTreeNode *t) +{ + if (t) { + av_tree_destroy(t->child[0]); + av_tree_destroy(t->child[1]); + av_free(t); + } } -#if 0 -void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*f)(void *opaque, void *elem)){ - f(opaque, t->elem); - av_tree_enumerate(t->child[0], opaque, f); - av_tree_enumerate(t->child[1], opaque, f); +void av_tree_enumerate(AVTreeNode *t, void *opaque, + int (*cmp)(void *opaque, void *elem), + int (*enu)(void *opaque, void *elem)) +{ + if (t) { + int v = cmp ? cmp(opaque, t->elem) : 0; + if (v >= 0) + av_tree_enumerate(t->child[0], opaque, cmp, enu); + if (v == 0) + enu(opaque, t->elem); + if (v <= 0) + av_tree_enumerate(t->child[1], opaque, cmp, enu); + } } -#endif #ifdef TEST -static int check(AVTreeNode *t){ - if(t){ - int left= check(t->child[0]); - int right= check(t->child[1]); +#include "lfg.h" + +static int check(AVTreeNode *t) +{ + if (t) { + int left = check(t->child[0]); + int right = check(t->child[1]); - if(left>999 || right>999) + if (left>999 || right>999) return 1000; - if(right - left != t->state) + if (right - left != t->state) return 1000; - if(t->state>1 || t->state<-1) + if (t->state>1 || t->state<-1) return 1000; - return FFMAX(left, right)+1; + return FFMAX(left, right) + 1; } return 0; } -static void print(AVTreeNode *t, int depth){ +static void print(AVTreeNode *t, int depth) +{ int i; - for(i=0; istate, t->elem); - print(t->child[0], depth+1); - print(t->child[1], depth+1); - }else + for (i = 0; i < depth * 4; i++) av_log(NULL, AV_LOG_ERROR, " "); + if (t) { + av_log(NULL, AV_LOG_ERROR, "Node %p %2d %p\n", t, t->state, t->elem); + print(t->child[0], depth + 1); + print(t->child[1], depth + 1); + } else av_log(NULL, AV_LOG_ERROR, "NULL\n"); } -int cmp(const void *a, const void *b){ - return a-b; +static int cmp(void *a, const void *b) +{ + return (uint8_t *) a - (const uint8_t *) b; } -int main(){ - int i,j,k; - AVTreeNode *root= av_mallocz(sizeof(AVTreeNode)); +int main (void) +{ + int i; + void *k; + AVTreeNode *root = NULL, *node = NULL; + AVLFG prng; + + av_lfg_init(&prng, 1); - for(i=0; i<10000; i++){ - int j= (random()%863294); - if(check(root) > 999){ + for (i = 0; i < 10000; i++) { + int j = av_lfg_get(&prng) % 86294; + if (check(root) > 999) { av_log(NULL, AV_LOG_ERROR, "FATAL error %d\n", i); print(root, 0); return -1; } av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); - av_tree_insert(&root, (void*)(j+1), cmp); + if (!node) + node = av_mallocz(av_tree_node_size); + av_tree_insert(&root, (void *) (j + 1), cmp, &node); + + j = av_lfg_get(&prng) % 86294; + { + AVTreeNode *node2 = NULL; + av_log(NULL, AV_LOG_ERROR, "removing %4d\n", j); + av_tree_insert(&root, (void *) (j + 1), cmp, &node2); + k = av_tree_find(root, (void *) (j + 1), cmp, NULL); + if (k) + av_log(NULL, AV_LOG_ERROR, "removal failure %d\n", i); + } } return 0; }