From 10db1a9bca46b0f760a1263d47142b2f57e195d7 Mon Sep 17 00:00:00 2001 From: Diego Biurrun Date: Tue, 16 Oct 2012 16:08:05 +0200 Subject: avutil/tree: K&R formatting cosmetics --- libavutil/tree.c | 82 ++++++++++++++++++++++++++++++-------------------------- 1 file changed, 44 insertions(+), 38 deletions(-) (limited to 'libavutil') diff --git a/libavutil/tree.c b/libavutil/tree.c index fd51a74916..72d7f40abc 100644 --- a/libavutil/tree.c +++ b/libavutil/tree.c @@ -43,7 +43,8 @@ void *av_tree_find(const AVTreeNode *t, void *key, if (t) { unsigned int v = cmp(key, t->elem); if (v) { - if (next) next[v >> 31] = t->elem; + if (next) + next[v >> 31] = t->elem; return av_tree_find(t->child[(v >> 31) ^ 1], key, cmp, next); } else { if (next) { @@ -71,56 +72,60 @@ void *av_tree_insert(AVTreeNode **tp, void *key, void *next_elem[2]; av_tree_find(t->child[i], key, cmp, next_elem); key = t->elem = next_elem[i]; - v = -i; + v = -i; } else { *next = t; - *tp = NULL; + *tp = NULL; return NULL; } } ret = av_tree_insert(&t->child[v >> 31], key, cmp, next); if (!ret) { - int i = (v >> 31) ^ !!*next; + 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) { + * 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 = ((0x400EEA >> i) & 3) - 1 + + * ((*tp)->state >> 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]; + *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)->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; + *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; } } } @@ -174,11 +179,11 @@ static int check(AVTreeNode *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) return 1000; - if (t->state>1 || t->state<-1) + if (t->state > 1 || t->state < -1) return 1000; return FFMAX(left, right) + 1; } @@ -188,7 +193,8 @@ static int check(AVTreeNode *t) static void print(AVTreeNode *t, int depth) { int i; - for (i = 0; i < depth * 4; i++) av_log(NULL, AV_LOG_ERROR, " "); + 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); @@ -202,7 +208,7 @@ 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; @@ -215,20 +221,20 @@ int main (void) 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); + print(root, 0); return -1; } av_log(NULL, AV_LOG_ERROR, "inserting %4d\n", j); if (!node) node = av_tree_node_alloc(); - av_tree_insert(&root, (void *) (j + 1), cmp, &node); + 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); + 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