From 425b45d4b0e69c1e1b095301396af3caa6dcbbf3 Mon Sep 17 00:00:00 2001 From: Yordan Makariev Date: Sat, 3 Dec 2011 20:25:57 +0200 Subject: Code clean-up for crc.c, lfg.c, log.c, random_see.d, rational.c and tree.c. Signed-off-by: Ronald S. Bultje --- libavutil/tree.c | 196 ++++++++++++++++++++++++++++++------------------------- 1 file changed, 106 insertions(+), 90 deletions(-) (limited to 'libavutil/tree.c') diff --git a/libavutil/tree.c b/libavutil/tree.c index 067e5b096e..e614f72cd8 100644 --- a/libavutil/tree.c +++ b/libavutil/tree.c @@ -21,22 +21,24 @@ #include "log.h" #include "tree.h" -typedef struct AVTreeNode{ +typedef struct AVTreeNode { struct AVTreeNode *child[2]; void *elem; int state; -}AVTreeNode; +} 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){ +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); } @@ -46,41 +48,43 @@ void *av_tree_find(const AVTreeNode *t, void *key, int (*cmp)(void *key, const v return NULL; } -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 *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) + if (!v) { + if (*next) return t->elem; - else if(t->child[0]||t->child[1]){ - int i= !t->child[0]; + 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; + 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){ + 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){ + static void rotate(AVTreeNode **tp, int i) { AVTreeNode *t= *tp; *tp= t->child[i]; @@ -92,54 +96,62 @@ void *av_tree_insert(AVTreeNode **tp, void *key, int (*cmp)(void *key, const voi } 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; + 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; } } } - if(!(*tp)->state ^ !!*next) + if (!(*tp)->state ^ !!*next) return key; } return ret; - }else{ - *tp= *next; *next= NULL; - if(*tp){ - (*tp)->elem= key; + } else { + *tp = *next; + *next = NULL; + if (*tp) { + (*tp)->elem = key; return NULL; - }else + } else return key; } } -void av_tree_destroy(AVTreeNode *t){ - if(t){ +void av_tree_destroy(AVTreeNode *t) +{ + if (t) { av_tree_destroy(t->child[0]); av_tree_destroy(t->child[1]); av_free(t); } } -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); +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); } } @@ -147,64 +159,68 @@ void av_tree_enumerate(AVTreeNode *t, void *opaque, int (*cmp)(void *opaque, voi #include "lfg.h" -static int check(AVTreeNode *t){ - if(t){ - int left= check(t->child[0]); - int right= check(t->child[1]); +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 + print(t->child[0], depth + 1); + print(t->child[1], depth + 1); + } else av_log(NULL, AV_LOG_ERROR, "NULL\n"); } -static int cmp(void *a, const void *b){ - return (uint8_t*)a-(const uint8_t*)b; +static int cmp(void *a, const void *b) +{ + return (uint8_t *) a - (const uint8_t *) b; } -int main(void){ +int main (void) +{ int i; void *k; - AVTreeNode *root= NULL, *node=NULL; + AVTreeNode *root = NULL, *node = NULL; AVLFG prng; av_lfg_init(&prng, 1); - for(i=0; i<10000; i++){ + for (i = 0; i < 10000; i++) { int j = av_lfg_get(&prng) % 86294; - if(check(root) > 999){ + 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); - if(!node) - node= av_mallocz(av_tree_node_size); - av_tree_insert(&root, (void*)(j+1), cmp, &node); + 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; + 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_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); } } -- cgit v1.2.3