From 9f38e394636a177c00a4545de2a99c661de36386 Mon Sep 17 00:00:00 2001 From: Guus Sliepen Date: Mon, 9 Sep 2002 21:49:16 +0000 Subject: [PATCH] Switch to K&R style indentation. --- lib/avl_tree.c | 967 +++++++++++++++++++++++++------------------------ lib/avl_tree.h | 50 +-- lib/dropin.c | 177 +++++---- lib/dropin.h | 8 +- lib/list.c | 209 ++++++----- lib/list.h | 28 +- lib/utils.c | 61 ++-- lib/utils.h | 30 +- 8 files changed, 757 insertions(+), 773 deletions(-) diff --git a/lib/avl_tree.c b/lib/avl_tree.c index 8ec680be..009c680b 100644 --- a/lib/avl_tree.c +++ b/lib/avl_tree.c @@ -29,7 +29,7 @@ library for inclusion into tinc (http://tinc.nl.linux.org/) by Guus Sliepen . - $Id: avl_tree.c,v 1.1.2.9 2002/06/21 10:11:11 guus Exp $ + $Id: avl_tree.c,v 1.1.2.10 2002/09/09 21:49:16 guus Exp $ */ #include @@ -55,669 +55,674 @@ #ifndef AVL_DEPTH int lg(unsigned int u) { - int r = 1; - if (!u) - return 0; - if (u & 0xffff0000) - { - u >>= 16; - r += 16; - } - if (u & 0x0000ff00) - { - u >>= 8; - r += 8; - } - if (u & 0x000000f0) - { - u >>= 4; - r += 4; - } - if (u & 0x0000000c) - { - u >>= 2; - r += 2; - } - if (u & 0x00000002) - r++; - return r; + int r = 1; + + if(!u) + return 0; + + if(u & 0xffff0000) { + u >>= 16; + r += 16; + } + + if(u & 0x0000ff00) { + u >>= 8; + r += 8; + } + + if(u & 0x000000f0) { + u >>= 4; + r += 4; + } + + if(u & 0x0000000c) { + u >>= 2; + r += 2; + } + + if(u & 0x00000002) + r++; + + return r; } #endif /* Internal helper functions */ -int avl_check_balance(avl_node_t *node) +int avl_check_balance(avl_node_t * node) { #ifdef AVL_DEPTH - int d; - d = R_AVL_DEPTH(node) - L_AVL_DEPTH(node); - return d < -1 ? -1 : d > 1 ? 1 : 0; + int d; + + d = R_AVL_DEPTH(node) - L_AVL_DEPTH(node); + + return d < -1 ? -1 : d > 1 ? 1 : 0; #else /* int d; * d = lg(AVL_R_COUNT(node)) - lg(AVL_L_COUNT(node)); * d = d<-1?-1:d>1?1:0; */ - int pl, r; + int pl, r; + + pl = lg(AVL_L_COUNT(node)); + r = AVL_R_COUNT(node); + + if(r >> pl + 1) + return 1; - pl = lg(AVL_L_COUNT(node)); - r = AVL_R_COUNT(node); + if(pl < 2 || r >> pl - 2) + return 0; - if (r >> pl + 1) - return 1; - if (pl < 2 || r >> pl - 2) - return 0; - return -1; + return -1; #endif } -void avl_rebalance(avl_tree_t *tree, avl_node_t *node) +void avl_rebalance(avl_tree_t * tree, avl_node_t * node) { - avl_node_t *child; - avl_node_t *gchild; - avl_node_t *parent; - avl_node_t **superparent; + avl_node_t *child; + avl_node_t *gchild; + avl_node_t *parent; + avl_node_t **superparent; - parent = node; + parent = node; - while (node) - { - parent = node->parent; + while(node) { + parent = node->parent; - superparent = parent ? node == parent->left ? &parent->left : &parent->right : &tree->root; + superparent = + parent ? node == + parent->left ? &parent->left : &parent->right : &tree->root; - switch (avl_check_balance(node)) - { - case -1: - child = node->left; + switch (avl_check_balance(node)) { + case -1: + child = node->left; #ifdef AVL_DEPTH - if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) { + if(L_AVL_DEPTH(child) >= R_AVL_DEPTH(child)) { #else - if (AVL_L_COUNT(child) >= AVL_R_COUNT(child)) - { + if(AVL_L_COUNT(child) >= AVL_R_COUNT(child)) { #endif - node->left = child->right; - if (node->left) - node->left->parent = node; - child->right = node; - node->parent = child; - *superparent = child; - child->parent = parent; + node->left = child->right; + if(node->left) + node->left->parent = node; + + child->right = node; + node->parent = child; + *superparent = child; + child->parent = parent; #ifdef AVL_COUNT - node->count = AVL_CALC_COUNT(node); - child->count = AVL_CALC_COUNT(child); + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); #endif #ifdef AVL_DEPTH - node->depth = AVL_CALC_DEPTH(node); - child->depth = AVL_CALC_DEPTH(child); + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); #endif - } else - { - gchild = child->right; - node->left = gchild->right; - if (node->left) - node->left->parent = node; - child->right = gchild->left; - if (child->right) - child->right->parent = child; - gchild->right = node; - if (gchild->right) - gchild->right->parent = gchild; - gchild->left = child; - if (gchild->left) - gchild->left->parent = gchild; - *superparent = gchild; - gchild->parent = parent; + } else { + gchild = child->right; + node->left = gchild->right; + + if(node->left) + node->left->parent = node; + child->right = gchild->left; + + if(child->right) + child->right->parent = child; + gchild->right = node; + + if(gchild->right) + gchild->right->parent = gchild; + gchild->left = child; + + if(gchild->left) + gchild->left->parent = gchild; + *superparent = gchild; + + gchild->parent = parent; #ifdef AVL_COUNT - node->count = AVL_CALC_COUNT(node); - child->count = AVL_CALC_COUNT(child); - gchild->count = AVL_CALC_COUNT(gchild); + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); + gchild->count = AVL_CALC_COUNT(gchild); #endif #ifdef AVL_DEPTH - node->depth = AVL_CALC_DEPTH(node); - child->depth = AVL_CALC_DEPTH(child); - gchild->depth = AVL_CALC_DEPTH(gchild); + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); + gchild->depth = AVL_CALC_DEPTH(gchild); #endif - } - break; - case 1: - child = node->right; + } + break; + + case 1: + child = node->right; #ifdef AVL_DEPTH - if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) { + if(R_AVL_DEPTH(child) >= L_AVL_DEPTH(child)) { #else - if (AVL_R_COUNT(child) >= AVL_L_COUNT(child)) - { + if(AVL_R_COUNT(child) >= AVL_L_COUNT(child)) { #endif - node->right = child->left; - if (node->right) - node->right->parent = node; - child->left = node; - node->parent = child; - *superparent = child; - child->parent = parent; + node->right = child->left; + if(node->right) + node->right->parent = node; + child->left = node; + node->parent = child; + *superparent = child; + child->parent = parent; #ifdef AVL_COUNT - node->count = AVL_CALC_COUNT(node); - child->count = AVL_CALC_COUNT(child); + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); #endif #ifdef AVL_DEPTH - node->depth = AVL_CALC_DEPTH(node); - child->depth = AVL_CALC_DEPTH(child); + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); #endif - } else - { - gchild = child->left; - node->right = gchild->left; - if (node->right) - node->right->parent = node; - child->left = gchild->right; - if (child->left) - child->left->parent = child; - gchild->left = node; - if (gchild->left) - gchild->left->parent = gchild; - gchild->right = child; - if (gchild->right) - gchild->right->parent = gchild; - *superparent = gchild; - gchild->parent = parent; + } else { + gchild = child->left; + node->right = gchild->left; + + if(node->right) + node->right->parent = node; + child->left = gchild->right; + + if(child->left) + child->left->parent = child; + gchild->left = node; + + if(gchild->left) + gchild->left->parent = gchild; + gchild->right = child; + + if(gchild->right) + gchild->right->parent = gchild; + + *superparent = gchild; + gchild->parent = parent; #ifdef AVL_COUNT - node->count = AVL_CALC_COUNT(node); - child->count = AVL_CALC_COUNT(child); - gchild->count = AVL_CALC_COUNT(gchild); + node->count = AVL_CALC_COUNT(node); + child->count = AVL_CALC_COUNT(child); + gchild->count = AVL_CALC_COUNT(gchild); #endif #ifdef AVL_DEPTH - node->depth = AVL_CALC_DEPTH(node); - child->depth = AVL_CALC_DEPTH(child); - gchild->depth = AVL_CALC_DEPTH(gchild); + node->depth = AVL_CALC_DEPTH(node); + child->depth = AVL_CALC_DEPTH(child); + gchild->depth = AVL_CALC_DEPTH(gchild); #endif - } - break; - default: + } + break; + + default: #ifdef AVL_COUNT - node->count = AVL_CALC_COUNT(node); + node->count = AVL_CALC_COUNT(node); #endif #ifdef AVL_DEPTH - node->depth = AVL_CALC_DEPTH(node); + node->depth = AVL_CALC_DEPTH(node); #endif - } - node = parent; - } + } + node = parent; + } } /* (De)constructors */ avl_tree_t *avl_alloc_tree(avl_compare_t compare, avl_action_t delete) { - avl_tree_t *tree; - - tree = xmalloc_and_zero(sizeof(avl_tree_t)); - tree->compare = compare; - tree->delete = delete; + avl_tree_t *tree; + + tree = xmalloc_and_zero(sizeof(avl_tree_t)); + tree->compare = compare; + tree->delete = delete; - return tree; + return tree; } -void avl_free_tree(avl_tree_t *tree) +void avl_free_tree(avl_tree_t * tree) { - free(tree); + free(tree); } avl_node_t *avl_alloc_node(void) { - avl_node_t *node; - - node = xmalloc_and_zero(sizeof(avl_node_t)); - - return node; + return (avl_node_t *)xmalloc_and_zero(sizeof(avl_node_t)); } -void avl_free_node(avl_tree_t *tree, avl_node_t *node) +void avl_free_node(avl_tree_t * tree, avl_node_t * node) { - if(node->data && tree->delete) - tree->delete(node->data); - free(node); + if(node->data && tree->delete) + tree->delete(node->data); + + free(node); } /* Searching */ -void *avl_search(const avl_tree_t *tree, const void *data) +void *avl_search(const avl_tree_t * tree, const void *data) { - avl_node_t *node; - - node = avl_search_node(tree, data); + avl_node_t *node; + + node = avl_search_node(tree, data); - return node?node->data:NULL; + return node ? node->data : NULL; } -void *avl_search_closest(const avl_tree_t *tree, const void *data, int *result) +void *avl_search_closest(const avl_tree_t * tree, const void *data, int *result) { - avl_node_t *node; - - node = avl_search_closest_node(tree, data, result); + avl_node_t *node; + + node = avl_search_closest_node(tree, data, result); - return node?node->data:NULL; + return node ? node->data : NULL; } -void *avl_search_closest_smaller(const avl_tree_t *tree, const void *data) +void *avl_search_closest_smaller(const avl_tree_t * tree, const void *data) { - avl_node_t *node; - - node = avl_search_closest_smaller_node(tree, data); + avl_node_t *node; - return node?node->data:NULL; + node = avl_search_closest_smaller_node(tree, data); + + return node ? node->data : NULL; } -void *avl_search_closest_greater(const avl_tree_t *tree, const void *data) +void *avl_search_closest_greater(const avl_tree_t * tree, const void *data) { - avl_node_t *node; - - node = avl_search_closest_greater_node(tree, data); + avl_node_t *node; + + node = avl_search_closest_greater_node(tree, data); - return node?node->data:NULL; + return node ? node->data : NULL; } -avl_node_t *avl_search_node(const avl_tree_t *tree, const void *data) +avl_node_t *avl_search_node(const avl_tree_t * tree, const void *data) { - avl_node_t *node; - int result; - - node = avl_search_closest_node(tree, data, &result); - - return result?NULL:node; + avl_node_t *node; + int result; + + node = avl_search_closest_node(tree, data, &result); + + return result ? NULL : node; } -avl_node_t *avl_search_closest_node(const avl_tree_t *tree, const void *data, int *result) +avl_node_t *avl_search_closest_node(const avl_tree_t * tree, const void *data, + int *result) { - avl_node_t *node; - int c; - - node = tree->root; - - if (!node) - { - if(result) - *result = 0; - return NULL; - } - - for (;;) - { - c = tree->compare(data, node->data); - - if (c < 0) - { - if (node->left) - node = node->left; - else - { - if(result) - *result = -1; - break; - } - } - else if (c > 0) - { - if (node->right) - node = node->right; - else - { - if(result) - *result = 1; - break; - } - } - else - { - if(result) - *result = 0; - break; - } - } - - return node; + avl_node_t *node; + int c; + + node = tree->root; + + if(!node) { + if(result) + *result = 0; + return NULL; + } + + for(;;) { + c = tree->compare(data, node->data); + + if(c < 0) { + if(node->left) + node = node->left; + else { + if(result) + *result = -1; + break; + } + } else if(c > 0) { + if(node->right) + node = node->right; + else { + if(result) + *result = 1; + break; + } + } else { + if(result) + *result = 0; + break; + } + } + + return node; } -avl_node_t *avl_search_closest_smaller_node(const avl_tree_t *tree, const void *data) +avl_node_t *avl_search_closest_smaller_node(const avl_tree_t * tree, + const void *data) { - avl_node_t *node; - int result; - - node = avl_search_closest_node(tree, data, &result); - - if(result < 0) - node = node->prev; - - return node; + avl_node_t *node; + int result; + + node = avl_search_closest_node(tree, data, &result); + + if(result < 0) + node = node->prev; + + return node; } -avl_node_t *avl_search_closest_greater_node(const avl_tree_t *tree, const void *data) +avl_node_t *avl_search_closest_greater_node(const avl_tree_t * tree, + const void *data) { - avl_node_t *node; - int result; - - node = avl_search_closest_node(tree, data, &result); - - if(result > 0) - node = node->next; - - return node; + avl_node_t *node; + int result; + + node = avl_search_closest_node(tree, data, &result); + + if(result > 0) + node = node->next; + + return node; } /* Insertion and deletion */ -avl_node_t *avl_insert(avl_tree_t *tree, void *data) +avl_node_t *avl_insert(avl_tree_t * tree, void *data) { - avl_node_t *closest, *new; - int result; - - if (!tree->root) - { - new = avl_alloc_node(); - new->data = data; - avl_insert_top(tree, new); - } - else - { - closest = avl_search_closest_node(tree, data, &result); - switch(result) - { - case -1: - new = avl_alloc_node(); - new->data = data; - avl_insert_before(tree, closest, new); - break; - case 1: - new = avl_alloc_node(); - new->data = data; - avl_insert_after(tree, closest, new); - break; - default: - return NULL; - } - } - + avl_node_t *closest, *new; + int result; + + if(!tree->root) { + new = avl_alloc_node(); + new->data = data; + avl_insert_top(tree, new); + } else { + closest = avl_search_closest_node(tree, data, &result); + + switch (result) { + case -1: + new = avl_alloc_node(); + new->data = data; + avl_insert_before(tree, closest, new); + break; + + case 1: + new = avl_alloc_node(); + new->data = data; + avl_insert_after(tree, closest, new); + break; + + default: + return NULL; + } + } + #ifdef AVL_COUNT - new->count = 1; + new->count = 1; #endif #ifdef AVL_DEPTH - new->depth = 1; + new->depth = 1; #endif - return new; + return new; } -avl_node_t *avl_insert_node(avl_tree_t *tree, avl_node_t *node) +avl_node_t *avl_insert_node(avl_tree_t * tree, avl_node_t * node) { - avl_node_t *closest; - int result; - - if (!tree->root) - avl_insert_top(tree, node); - else - { - closest = avl_search_closest_node(tree, node->data, &result); - switch(result) - { - case -1: - avl_insert_before(tree, closest, node); - break; - case 1: - avl_insert_after(tree, closest, node); - break; - case 0: - return NULL; - } - } - + avl_node_t *closest; + int result; + + if(!tree->root) + avl_insert_top(tree, node); + else { + closest = avl_search_closest_node(tree, node->data, &result); + + switch (result) { + case -1: + avl_insert_before(tree, closest, node); + break; + + case 1: + avl_insert_after(tree, closest, node); + break; + + case 0: + return NULL; + } + } + #ifdef AVL_COUNT - node->count = 1; + node->count = 1; #endif #ifdef AVL_DEPTH - node->depth = 1; + node->depth = 1; #endif - return node; + return node; } -void avl_insert_top(avl_tree_t *tree, avl_node_t *node) +void avl_insert_top(avl_tree_t * tree, avl_node_t * node) { - node->prev = node->next = node->parent = NULL; - tree->head = tree->tail = tree->root = node; + node->prev = node->next = node->parent = NULL; + tree->head = tree->tail = tree->root = node; } -void avl_insert_before(avl_tree_t *tree, avl_node_t *before, avl_node_t *node) +void avl_insert_before(avl_tree_t * tree, avl_node_t * before, + avl_node_t * node) { - if (!before) - return tree->tail ? avl_insert_after(tree, tree->tail, node) : avl_insert_top(tree, node); + if(!before) + return tree->tail ? avl_insert_after(tree, tree->tail, node) : avl_insert_top(tree, node); - node->next = before; - node->parent = before; - node->prev = before->prev; + node->next = before; + node->parent = before; + node->prev = before->prev; - if(before->left) - return avl_insert_after(tree, before->prev, node); + if(before->left) + return avl_insert_after(tree, before->prev, node); - if (before->prev) - before->prev->next = node; - else - tree->head = node; + if(before->prev) + before->prev->next = node; + else + tree->head = node; - before->prev = node; - before->left = node; + before->prev = node; + before->left = node; - avl_rebalance(tree, before->parent); + avl_rebalance(tree, before->parent); } -void avl_insert_after(avl_tree_t *tree, avl_node_t *after, avl_node_t *node) +void avl_insert_after(avl_tree_t * tree, avl_node_t * after, avl_node_t * node) { - if (!after) - return tree->head ? avl_insert_before(tree, tree->head, node) : avl_insert_top(tree, node); + if(!after) + return tree->head ? avl_insert_before(tree, tree->head, + node) : avl_insert_top(tree, + node); + + if(after->right) + return avl_insert_before(tree, after->next, node); - if(after->right) - return avl_insert_before(tree, after->next, node); + node->prev = after; + node->parent = after; + node->next = after->next; - node->prev = after; - node->parent = after; - node->next = after->next; + if(after->next) + after->next->prev = node; + else + tree->tail = node; - if (after->next) - after->next->prev = node; - else - tree->tail = node; - - after->next = node; - after->right = node; + after->next = node; + after->right = node; - avl_rebalance(tree, after->parent); + avl_rebalance(tree, after->parent); } -avl_node_t *avl_unlink(avl_tree_t *tree, void *data) +avl_node_t *avl_unlink(avl_tree_t * tree, void *data) { - avl_node_t *node; - - node = avl_search_node(tree, data); + avl_node_t *node; - if(node) - avl_unlink_node(tree, node); + node = avl_search_node(tree, data); - return node; + if(node) + avl_unlink_node(tree, node); + + return node; } -void avl_unlink_node(avl_tree_t *tree, avl_node_t *node) +void avl_unlink_node(avl_tree_t * tree, avl_node_t * node) { - avl_node_t *parent; - avl_node_t **superparent; - avl_node_t *subst, *left, *right; - avl_node_t *balnode; - - if (node->prev) - node->prev->next = node->next; - else - tree->head = node->next; - if (node->next) - node->next->prev = node->prev; - else - tree->tail = node->prev; - - parent = node->parent; - - superparent = parent ? node == parent->left ? &parent->left : &parent->right : &tree->root; - - left = node->left; - right = node->right; - if (!left) - { - *superparent = right; - if (right) - right->parent = parent; - balnode = parent; - } else if (!right) - { - *superparent = left; - left->parent = parent; - balnode = parent; - } else - { - subst = node->prev; - if (subst == left) - { - balnode = subst; - } else - { - balnode = subst->parent; - balnode->right = subst->left; - if (balnode->right) - balnode->right->parent = balnode; - subst->left = left; - left->parent = subst; - } - subst->right = right; - subst->parent = parent; - right->parent = subst; - *superparent = subst; - } - - avl_rebalance(tree, balnode); - - node->next = node->prev = node->parent = node->left = node->right = NULL; + avl_node_t *parent; + avl_node_t **superparent; + avl_node_t *subst, *left, *right; + avl_node_t *balnode; + + if(node->prev) + node->prev->next = node->next; + else + tree->head = node->next; + if(node->next) + node->next->prev = node->prev; + else + tree->tail = node->prev; + + parent = node->parent; + + superparent = + parent ? node == + parent->left ? &parent->left : &parent->right : &tree->root; + + left = node->left; + right = node->right; + if(!left) { + *superparent = right; + + if(right) + right->parent = parent; + + balnode = parent; + } else if(!right) { + *superparent = left; + left->parent = parent; + balnode = parent; + } else { + subst = node->prev; + + if(subst == left) { + balnode = subst; + } else { + balnode = subst->parent; + balnode->right = subst->left; + + if(balnode->right) + balnode->right->parent = balnode; + + subst->left = left; + left->parent = subst; + } + + subst->right = right; + subst->parent = parent; + right->parent = subst; + *superparent = subst; + } + + avl_rebalance(tree, balnode); + + node->next = node->prev = node->parent = node->left = node->right = NULL; #ifdef AVL_COUNT - node->count = 0; + node->count = 0; #endif #ifdef AVL_DEPTH - node->depth = 0; + node->depth = 0; #endif } -void avl_delete_node(avl_tree_t *tree, avl_node_t *node) +void avl_delete_node(avl_tree_t * tree, avl_node_t * node) { - avl_unlink_node(tree, node); - avl_free_node(tree, node); + avl_unlink_node(tree, node); + avl_free_node(tree, node); } -void avl_delete(avl_tree_t *tree, void *data) +void avl_delete(avl_tree_t * tree, void *data) { - avl_node_t *node; + avl_node_t *node; - node = avl_search_node(tree, data); + node = avl_search_node(tree, data); - if (node) - avl_delete_node(tree, node); + if(node) + avl_delete_node(tree, node); } /* Fast tree cleanup */ -void avl_delete_tree(avl_tree_t *tree) +void avl_delete_tree(avl_tree_t * tree) { - avl_node_t *node, *next; - - for(node = tree->root; node; node = next) - { - next = node->next; - avl_free_node(tree, node); - } - - avl_free_tree(tree); + avl_node_t *node, *next; + + for(node = tree->root; node; node = next) { + next = node->next; + avl_free_node(tree, node); + } + + avl_free_tree(tree); } /* Tree walking */ -void avl_foreach(avl_tree_t *tree, avl_action_t action) +void avl_foreach(avl_tree_t * tree, avl_action_t action) { - avl_node_t *node, *next; - - for(node = tree->head; node; node = next) - { - next = node->next; - action(node->data); - } + avl_node_t *node, *next; + + for(node = tree->head; node; node = next) { + next = node->next; + action(node->data); + } } -void avl_foreach_node(avl_tree_t *tree, avl_action_t action) +void avl_foreach_node(avl_tree_t * tree, avl_action_t action) { - avl_node_t *node, *next; - - for(node = tree->head; node; node = next) - { - next = node->next; - action(node); - } + avl_node_t *node, *next; + + for(node = tree->head; node; node = next) { + next = node->next; + action(node); + } } /* Indexing */ #ifdef AVL_COUNT -unsigned int avl_count(avl_tree_t *tree) +unsigned int avl_count(avl_tree_t * tree) { - return AVL_NODE_COUNT(tree->root); + return AVL_NODE_COUNT(tree->root); } -avl_node_t *avl_get_node(const avl_tree_t *tree, unsigned int index) +avl_node_t *avl_get_node(const avl_tree_t * tree, unsigned int index) { - avl_node_t *node; - unsigned int c; - - node = tree->root; - - while (node) - { - c = AVL_L_COUNT(node); - - if (index < c) - { - node = node->left; - } else if (index > c) - { - node = node->right; - index -= c + 1; - } else - { - return node; - } - } - - return NULL; + avl_node_t *node; + unsigned int c; + + node = tree->root; + + while(node) { + c = AVL_L_COUNT(node); + + if(index < c) { + node = node->left; + } else if(index > c) { + node = node->right; + index -= c + 1; + } else { + return node; + } + } + + return NULL; } -unsigned int avl_index(const avl_node_t *node) +unsigned int avl_index(const avl_node_t * node) { - avl_node_t *next; - unsigned int index; + avl_node_t *next; + unsigned int index; - index = AVL_L_COUNT(node); + index = AVL_L_COUNT(node); - while ((next = node->parent)) - { - if (node == next->right) - index += AVL_L_COUNT(next) + 1; - node = next; - } + while((next = node->parent)) { + if(node == next->right) + index += AVL_L_COUNT(next) + 1; + node = next; + } - return index; + return index; } #endif #ifdef AVL_DEPTH -unsigned int avl_depth(avl_tree_t *tree) +unsigned int avl_depth(avl_tree_t * tree) { - return AVL_NODE_DEPTH(tree->root); + return AVL_NODE_DEPTH(tree->root); } #endif diff --git a/lib/avl_tree.h b/lib/avl_tree.h index 35c13a32..08bed6b9 100644 --- a/lib/avl_tree.h +++ b/lib/avl_tree.h @@ -29,7 +29,7 @@ library for inclusion into tinc (http://tinc.nl.linux.org/) by Guus Sliepen . - $Id: avl_tree.h,v 1.1.2.5 2002/06/21 10:11:11 guus Exp $ + $Id: avl_tree.h,v 1.1.2.6 2002/09/09 21:49:16 guus Exp $ */ @@ -37,34 +37,34 @@ #define __AVL_TREE_H__ #ifndef AVL_DEPTH - #ifndef AVL_COUNT - #define AVL_DEPTH - #endif +#ifndef AVL_COUNT +#define AVL_DEPTH +#endif #endif typedef struct avl_node_t { - /* Linked list part */ + /* Linked list part */ - struct avl_node_t *next; - struct avl_node_t *prev; + struct avl_node_t *next; + struct avl_node_t *prev; - /* Tree part */ + /* Tree part */ - struct avl_node_t *parent; - struct avl_node_t *left; - struct avl_node_t *right; + struct avl_node_t *parent; + struct avl_node_t *left; + struct avl_node_t *right; #ifdef AVL_COUNT - unsigned int count; + unsigned int count; #endif #ifdef AVL_DEPTH - unsigned char depth; + unsigned char depth; #endif - /* Payload */ + /* Payload */ - void *data; + void *data; } avl_node_t; @@ -74,17 +74,17 @@ typedef void (*avl_action_node_t) (const avl_node_t *); typedef struct avl_tree_t { - /* Linked list part */ + /* Linked list part */ - avl_node_t *head; - avl_node_t *tail; + avl_node_t *head; + avl_node_t *tail; - /* Tree part */ + /* Tree part */ - avl_node_t *root; + avl_node_t *root; - avl_compare_t compare; - avl_action_t delete; + avl_compare_t compare; + avl_action_t delete; } avl_tree_t; @@ -94,7 +94,7 @@ extern avl_tree_t *avl_alloc_tree(avl_compare_t, avl_action_t); extern void avl_free_tree(avl_tree_t *); extern avl_node_t *avl_alloc_node(void); -extern void avl_free_node(avl_tree_t *tree, avl_node_t *); +extern void avl_free_node(avl_tree_t * tree, avl_node_t *); /* Insertion and deletion */ @@ -106,7 +106,7 @@ extern void avl_insert_before(avl_tree_t *, avl_node_t *, avl_node_t *); extern void avl_insert_after(avl_tree_t *, avl_node_t *, avl_node_t *); extern avl_node_t *avl_unlink(avl_tree_t *, void *); -extern void avl_unlink_node(avl_tree_t *tree, avl_node_t *); +extern void avl_unlink_node(avl_tree_t * tree, avl_node_t *); extern void avl_delete(avl_tree_t *, void *); extern void avl_delete_node(avl_tree_t *, avl_node_t *); @@ -142,4 +142,4 @@ extern unsigned int avl_index(const avl_node_t *); extern unsigned int avl_depth(avl_tree_t *); #endif -#endif /* __AVL_TREE_H__ */ +#endif /* __AVL_TREE_H__ */ diff --git a/lib/dropin.c b/lib/dropin.c index 661c4551..22bc812f 100644 --- a/lib/dropin.c +++ b/lib/dropin.c @@ -17,7 +17,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: dropin.c,v 1.1.2.11 2002/07/12 11:45:21 guus Exp $ + $Id: dropin.c,v 1.1.2.12 2002/09/09 21:49:16 guus Exp $ */ #include "config.h" @@ -51,61 +51,51 @@ */ int daemon(int nochdir, int noclose) { - pid_t pid; - int fd; - - pid = fork(); - - /* Check if forking failed */ - if(pid < 0) - { - perror("fork"); - exit(-1); - } - - /* If we are the parent, terminate */ - if(pid) - exit(0); - - /* Detach by becoming the new process group leader */ - if(setsid() < 0) - { - perror("setsid"); - return -1; - } - - /* Change working directory to the root (to avoid keeping mount - points busy) */ - if(!nochdir) - { - chdir("/"); - } - - /* Redirect stdin/out/err to /dev/null */ - if(!noclose) - { - fd = open("/dev/null", O_RDWR); - - if(fd < 0) - { - perror("opening /dev/null"); - return -1; - } - else - { - dup2(fd, 0); - dup2(fd, 1); - dup2(fd, 2); - } - } - - return 0; + pid_t pid; + int fd; + + pid = fork(); + + /* Check if forking failed */ + if(pid < 0) { + perror("fork"); + exit(-1); + } + + /* If we are the parent, terminate */ + if(pid) + exit(0); + + /* Detach by becoming the new process group leader */ + if(setsid() < 0) { + perror("setsid"); + return -1; + } + + /* Change working directory to the root (to avoid keeping mount + points busy) */ + if(!nochdir) { + chdir("/"); + } + + /* Redirect stdin/out/err to /dev/null */ + if(!noclose) { + fd = open("/dev/null", O_RDWR); + + if(fd < 0) { + perror("opening /dev/null"); + return -1; + } else { + dup2(fd, 0); + dup2(fd, 1); + dup2(fd, 2); + } + } + + return 0; } #endif - - - #ifndef HAVE_GET_CURRENT_DIR_NAME /* Replacement for the GNU get_current_dir_name function: @@ -116,56 +106,55 @@ int daemon(int nochdir, int noclose) */ char *get_current_dir_name(void) { - size_t size; - char *buf; - char *r; - - /* Start with 100 bytes. If this turns out to be insufficient to - contain the working directory, double the size. */ - size = 100; - buf = xmalloc(size); - - errno = 0; /* Success */ - r = getcwd(buf, size); - /* getcwd returns NULL and sets errno to ERANGE if the bufferspace - is insufficient to contain the entire working directory. */ - while(r == NULL && errno == ERANGE) - { - free(buf); - size <<= 1; /* double the size */ - buf = xmalloc(size); - r = getcwd(buf, size); - } - - return buf; + size_t size; + char *buf; + char *r; + + /* Start with 100 bytes. If this turns out to be insufficient to + contain the working directory, double the size. */ + size = 100; + buf = xmalloc(size); + + errno = 0; /* Success */ + r = getcwd(buf, size); + + /* getcwd returns NULL and sets errno to ERANGE if the bufferspace + is insufficient to contain the entire working directory. */ + while(r == NULL && errno == ERANGE) { + free(buf); + size <<= 1; /* double the size */ + buf = xmalloc(size); + r = getcwd(buf, size); + } + + return buf; } #endif #ifndef HAVE_ASPRINTF int asprintf(char **buf, const char *fmt, ...) { - int status; - va_list ap; - int len; - - len = 4096; - *buf = xmalloc(len); + int status; + va_list ap; + int len; + + len = 4096; + *buf = xmalloc(len); - va_start(ap, fmt); - status = vsnprintf (*buf, len, fmt, ap); - va_end (ap); + va_start(ap, fmt); + status = vsnprintf(*buf, len, fmt, ap); + va_end(ap); - if(status >= 0) - *buf = xrealloc(*buf, status); + if(status >= 0) + *buf = xrealloc(*buf, status); - if(status > len-1) - { - len = status; - va_start(ap, fmt); - status = vsnprintf (*buf, len, fmt, ap); - va_end (ap); - } + if(status > len - 1) { + len = status; + va_start(ap, fmt); + status = vsnprintf(*buf, len, fmt, ap); + va_end(ap); + } - return status; + return status; } #endif diff --git a/lib/dropin.h b/lib/dropin.h index ecf14403..0d10c367 100644 --- a/lib/dropin.h +++ b/lib/dropin.h @@ -17,7 +17,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: dropin.h,v 1.1.2.8 2002/06/21 10:11:11 guus Exp $ + $Id: dropin.h,v 1.1.2.9 2002/09/09 21:49:16 guus Exp $ */ #ifndef __DROPIN_H__ @@ -28,7 +28,7 @@ extern int daemon(int, int); #endif #ifndef HAVE_GET_CURRENT_DIR_NAME -extern char* get_current_dir_name(void); +extern char *get_current_dir_name(void); #endif #ifndef HAVE_ASPRINTF @@ -39,7 +39,7 @@ extern int asprintf(char **, const char *, ...); #include #include extern int getnameinfo(const struct sockaddr *sa, size_t salen, char *host, - size_t hostlen, char *serv, size_t servlen, int flags); + size_t hostlen, char *serv, size_t servlen, int flags); #endif -#endif /* __DROPIN_H__ */ +#endif /* __DROPIN_H__ */ diff --git a/lib/list.c b/lib/list.c index b4c5871c..d47ce0eb 100644 --- a/lib/list.c +++ b/lib/list.c @@ -17,7 +17,7 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: list.c,v 1.1.2.11 2002/06/21 10:11:11 guus Exp $ + $Id: list.c,v 1.1.2.12 2002/09/09 21:49:16 guus Exp $ */ #include "config.h" @@ -33,165 +33,158 @@ list_t *list_alloc(list_action_t delete) { - list_t *list; + list_t *list; - list = xmalloc_and_zero(sizeof(list_t)); - list->delete = delete; + list = xmalloc_and_zero(sizeof(list_t)); + list->delete = delete; - return list; + return list; } -void list_free(list_t *list) +void list_free(list_t * list) { - free(list); + free(list); } list_node_t *list_alloc_node(void) { - list_node_t *node; - - node = xmalloc_and_zero(sizeof(list_node_t)); - - return node; + return (list_node_t *)xmalloc_and_zero(sizeof(list_node_t)); } -void list_free_node(list_t *list, list_node_t *node) +void list_free_node(list_t * list, list_node_t * node) { - if(node->data && list->delete) - list->delete(node->data); - - free(node); + if(node->data && list->delete) + list->delete(node->data); + + free(node); } /* Insertion and deletion */ -list_node_t *list_insert_head(list_t *list, void *data) +list_node_t *list_insert_head(list_t * list, void *data) { - list_node_t *node; - - node = list_alloc_node(); - - node->data = data; - node->prev = NULL; - node->next = list->head; - list->head = node; - - if(node->next) - node->next->prev = node; - else - list->tail = node; - - list->count++; - - return node; + list_node_t *node; + + node = list_alloc_node(); + + node->data = data; + node->prev = NULL; + node->next = list->head; + list->head = node; + + if(node->next) + node->next->prev = node; + else + list->tail = node; + + list->count++; + + return node; } -list_node_t *list_insert_tail(list_t *list, void *data) +list_node_t *list_insert_tail(list_t * list, void *data) { - list_node_t *node; - - node = list_alloc_node(); - - node->data = data; - node->next = NULL; - node->prev = list->tail; - list->tail = node; - - if(node->prev) - node->prev->next = node; - else - list->head = node; - - list->count++; - - return node; + list_node_t *node; + + node = list_alloc_node(); + + node->data = data; + node->next = NULL; + node->prev = list->tail; + list->tail = node; + + if(node->prev) + node->prev->next = node; + else + list->head = node; + + list->count++; + + return node; } -void list_unlink_node(list_t *list, list_node_t *node) +void list_unlink_node(list_t * list, list_node_t * node) { - if(node->prev) - node->prev->next = node->next; - else - list->head = node->next; - - if(node->next) - node->next->prev = node->prev; - else - list->tail = node->prev; - - list->count--; + if(node->prev) + node->prev->next = node->next; + else + list->head = node->next; + + if(node->next) + node->next->prev = node->prev; + else + list->tail = node->prev; + + list->count--; } -void list_delete_node(list_t *list, list_node_t *node) +void list_delete_node(list_t * list, list_node_t * node) { - list_unlink_node(list, node); - list_free_node(list, node); + list_unlink_node(list, node); + list_free_node(list, node); } -void list_delete_head(list_t *list) +void list_delete_head(list_t * list) { - list_delete_node(list, list->head); + list_delete_node(list, list->head); } -void list_delete_tail(list_t *list) +void list_delete_tail(list_t * list) { - list_delete_node(list, list->tail); + list_delete_node(list, list->tail); } /* Head/tail lookup */ -void *list_get_head(list_t *list) +void *list_get_head(list_t * list) { - if(list->head) - return list->head->data; - else - return NULL; + if(list->head) + return list->head->data; + else + return NULL; } -void *list_get_tail(list_t *list) +void *list_get_tail(list_t * list) { - if(list->tail) - return list->tail->data; - else - return NULL; + if(list->tail) + return list->tail->data; + else + return NULL; } /* Fast list deletion */ -void list_delete_list(list_t *list) +void list_delete_list(list_t * list) { - list_node_t *node, *next; - - for(node = list->head; node; node = next) - { - next = node->next; - list_free_node(list, node); - } - - list_free(list); + list_node_t *node, *next; + + for(node = list->head; node; node = next) { + next = node->next; + list_free_node(list, node); + } + + list_free(list); } /* Traversing */ -void list_foreach_node(list_t *list, list_action_node_t action) +void list_foreach_node(list_t * list, list_action_node_t action) { - list_node_t *node, *next; + list_node_t *node, *next; - for(node = list->head; node; node = next) - { - next = node->next; - action(node); - } + for(node = list->head; node; node = next) { + next = node->next; + action(node); + } } -void list_foreach(list_t *list, list_action_t action) +void list_foreach(list_t * list, list_action_t action) { - list_node_t *node, *next; - - for(node = list->head; node; node = next) - { - next = node->next; - if(node->data) - action(node->data); - } + list_node_t *node, *next; + + for(node = list->head; node; node = next) { + next = node->next; + if(node->data) + action(node->data); + } } diff --git a/lib/list.h b/lib/list.h index 4c9885d4..326a9296 100644 --- a/lib/list.h +++ b/lib/list.h @@ -17,34 +17,32 @@ along with this program; if not, write to the Free Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. - $Id: list.h,v 1.1.2.6 2002/06/21 10:11:11 guus Exp $ + $Id: list.h,v 1.1.2.7 2002/09/09 21:49:16 guus Exp $ */ #ifndef __TINC_LIST_H__ #define __TINC_LIST_H__ -typedef struct list_node_t -{ - struct list_node_t *prev; - struct list_node_t *next; +typedef struct list_node_t { + struct list_node_t *prev; + struct list_node_t *next; - /* Payload */ + /* Payload */ - void *data; + void *data; } list_node_t; typedef void (*list_action_t) (const void *); typedef void (*list_action_node_t) (const list_node_t *); -typedef struct list_t -{ - list_node_t *head; - list_node_t *tail; - int count; +typedef struct list_t { + list_node_t *head; + list_node_t *tail; + int count; - /* Callbacks */ + /* Callbacks */ - list_action_t delete; + list_action_t delete; } list_t; /* (De)constructors */ @@ -79,4 +77,4 @@ extern void list_delete_list(list_t *); extern void list_foreach(list_t *, list_action_t); extern void list_foreach_node(list_t *, list_action_node_t); -#endif /* __TINC_LIST_H__ */ +#endif /* __TINC_LIST_H__ */ diff --git a/lib/utils.c b/lib/utils.c index ce78dd2e..3b1abc37 100644 --- a/lib/utils.c +++ b/lib/utils.c @@ -38,50 +38,49 @@ char *hexadecimals = "0123456789ABCDEF"; int charhex2bin(char c) { - if(isdigit(c)) - return c - '0'; - else - return toupper(c) - 'A' + 10; + if(isdigit(c)) + return c - '0'; + else + return toupper(c) - 'A' + 10; } void hex2bin(char *src, char *dst, int length) { - int i; - for(i=0; i=0; i--) - { - dst[i*2+1] = hexadecimals[(unsigned char)src[i] & 15]; - dst[i*2] = hexadecimals[(unsigned char)src[i]>>4]; - } + int i; + for(i = length - 1; i >= 0; i--) { + dst[i * 2 + 1] = hexadecimals[(unsigned char) src[i] & 15]; + dst[i * 2] = hexadecimals[(unsigned char) src[i] >> 4]; + } } #ifdef ENABLE_TRACING void cp_trace() { - syslog(LOG_DEBUG, "Checkpoint trace: %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d...", - cp_file[(cp_index+15)%16], cp_line[(cp_index+15)%16], - cp_file[(cp_index+14)%16], cp_line[(cp_index+14)%16], - cp_file[(cp_index+13)%16], cp_line[(cp_index+13)%16], - cp_file[(cp_index+12)%16], cp_line[(cp_index+12)%16], - cp_file[(cp_index+11)%16], cp_line[(cp_index+11)%16], - cp_file[(cp_index+10)%16], cp_line[(cp_index+10)%16], - cp_file[(cp_index+9)%16], cp_line[(cp_index+9)%16], - cp_file[(cp_index+8)%16], cp_line[(cp_index+8)%16], - cp_file[(cp_index+7)%16], cp_line[(cp_index+7)%16], - cp_file[(cp_index+6)%16], cp_line[(cp_index+6)%16], - cp_file[(cp_index+5)%16], cp_line[(cp_index+5)%16], - cp_file[(cp_index+4)%16], cp_line[(cp_index+4)%16], - cp_file[(cp_index+3)%16], cp_line[(cp_index+3)%16], - cp_file[(cp_index+2)%16], cp_line[(cp_index+2)%16], - cp_file[(cp_index+1)%16], cp_line[(cp_index+1)%16], - cp_file[cp_index], cp_line[cp_index] - ); + syslog(LOG_DEBUG, "Checkpoint trace: %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d <- %s:%d...", + cp_file[(cp_index + 15) % 16], cp_line[(cp_index + 15) % 16], + cp_file[(cp_index + 14) % 16], cp_line[(cp_index + 14) % 16], + cp_file[(cp_index + 13) % 16], cp_line[(cp_index + 13) % 16], + cp_file[(cp_index + 12) % 16], cp_line[(cp_index + 12) % 16], + cp_file[(cp_index + 11) % 16], cp_line[(cp_index + 11) % 16], + cp_file[(cp_index + 10) % 16], cp_line[(cp_index + 10) % 16], + cp_file[(cp_index + 9) % 16], cp_line[(cp_index + 9) % 16], + cp_file[(cp_index + 8) % 16], cp_line[(cp_index + 8) % 16], + cp_file[(cp_index + 7) % 16], cp_line[(cp_index + 7) % 16], + cp_file[(cp_index + 6) % 16], cp_line[(cp_index + 6) % 16], + cp_file[(cp_index + 5) % 16], cp_line[(cp_index + 5) % 16], + cp_file[(cp_index + 4) % 16], cp_line[(cp_index + 4) % 16], + cp_file[(cp_index + 3) % 16], cp_line[(cp_index + 3) % 16], + cp_file[(cp_index + 2) % 16], cp_line[(cp_index + 2) % 16], + cp_file[(cp_index + 1) % 16], cp_line[(cp_index + 1) % 16], + cp_file[cp_index], cp_line[cp_index] + ); } #endif diff --git a/lib/utils.h b/lib/utils.h index a1a666bd..7a953a3e 100644 --- a/lib/utils.h +++ b/lib/utils.h @@ -27,15 +27,15 @@ #include "fake-getnameinfo.h" enum { - DEBUG_NOTHING = 0, /* Quiet mode, only show starting/stopping of the daemon */ - DEBUG_CONNECTIONS = 1, /* Show (dis)connects of other tinc daemons via TCP */ - DEBUG_ERROR = 2, /* Show error messages received from other hosts */ - DEBUG_STATUS = 2, /* Show status messages received from other hosts */ - DEBUG_PROTOCOL = 3, /* Show the requests that are sent/received */ - DEBUG_META = 4, /* Show contents of every request that is sent/received */ - DEBUG_TRAFFIC = 5, /* Show network traffic information */ - DEBUG_PACKET = 6, /* Show contents of each packet that is being sent/received */ - DEBUG_SCARY_THINGS = 10 /* You have been warned */ + DEBUG_NOTHING = 0, /* Quiet mode, only show starting/stopping of the daemon */ + DEBUG_CONNECTIONS = 1, /* Show (dis)connects of other tinc daemons via TCP */ + DEBUG_ERROR = 2, /* Show error messages received from other hosts */ + DEBUG_STATUS = 2, /* Show status messages received from other hosts */ + DEBUG_PROTOCOL = 3, /* Show the requests that are sent/received */ + DEBUG_META = 4, /* Show contents of every request that is sent/received */ + DEBUG_TRAFFIC = 5, /* Show network traffic information */ + DEBUG_PACKET = 6, /* Show contents of each packet that is being sent/received */ + DEBUG_SCARY_THINGS = 10 /* You have been warned */ }; #define min(a,b) (((a)<(b))?(a):(b)) @@ -46,15 +46,15 @@ extern volatile char *cp_file[]; extern volatile int cp_index; extern void cp_trace(void); - #define cp() { cp_line[cp_index] = __LINE__; cp_file[cp_index] = __FILE__; cp_index++; cp_index %= 16; } - #define ecp() { fprintf(stderr, "Explicit checkpoint in %s line %d\n", __FILE__, __LINE__); } +#define cp() { cp_line[cp_index] = __LINE__; cp_file[cp_index] = __FILE__; cp_index++; cp_index %= 16; } +#define ecp() { fprintf(stderr, "Explicit checkpoint in %s line %d\n", __FILE__, __LINE__); } #else - #define cp() - #define ecp() - #define cp_trace() +#define cp() +#define ecp() +#define cp_trace() #endif extern void hex2bin(char *src, char *dst, int length); extern void bin2hex(char *src, char *dst, int length); -#endif /* __TINC_UTILS_H__ */ +#endif /* __TINC_UTILS_H__ */ -- 2.39.5