diff options
-rw-r--r-- | avltree.c | 104 | ||||
-rw-r--r-- | bitmap.c | 28 | ||||
-rw-r--r-- | bitmap.h | 24 | ||||
-rw-r--r-- | cpu.h | 5 | ||||
-rw-r--r-- | error.c | 3 | ||||
-rw-r--r-- | hash.h | 3 | ||||
-rw-r--r-- | list.c | 9 | ||||
-rw-r--r-- | list.h | 3 | ||||
-rw-r--r-- | rbtree.c | 90 | ||||
-rw-r--r-- | rdxtree.c | 128 | ||||
-rw-r--r-- | shell.c | 6 | ||||
-rw-r--r-- | test/test_avltree.c | 9 | ||||
-rw-r--r-- | test/test_rbtree.c | 9 | ||||
-rw-r--r-- | test/test_rdxtree.c | 28 | ||||
-rw-r--r-- | test/test_shell.c | 3 |
15 files changed, 290 insertions, 162 deletions
@@ -58,8 +58,9 @@ avltree_node_index(const struct avltree_node *node, assert(parent != NULL); assert((node == NULL) || (avltree_node_parent(node) == parent)); - if (parent->children[AVLTREE_LEFT] == node) + if (parent->children[AVLTREE_LEFT] == node) { return AVLTREE_LEFT; + } assert(parent->children[AVLTREE_RIGHT] == node); @@ -119,8 +120,9 @@ avltree_node_find_deepest(struct avltree_node *node) if (node == NULL) { node = parent->children[AVLTREE_RIGHT]; - if (node == NULL) + if (node == NULL) { return parent; + } } } } @@ -151,8 +153,9 @@ avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance) parent = avltree_node_parent(node); - if (likely(parent != NULL)) + if (likely(parent != NULL)) { index = avltree_node_index(node, parent); + } lnode = node->children[left]; assert(lnode != NULL); @@ -166,8 +169,9 @@ avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance) if (lbalance != rweight) { node->children[left] = lrnode; - if (lrnode != NULL) + if (lrnode != NULL) { avltree_node_set_parent(lrnode, node); + } lbalance += rweight; @@ -179,10 +183,11 @@ avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance) avltree_node_set_parent(lnode, parent); avltree_node_set_balance(lnode, lbalance); - if (unlikely(parent == NULL)) + if (unlikely(parent == NULL)) { tree->root = lnode; - else + } else { parent->children[index] = lnode; + } /* * If the adjusted balance is now 0, it means that the height of the @@ -201,13 +206,15 @@ avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance) node->children[left] = lrrnode; - if (lrrnode != NULL) + if (lrrnode != NULL) { avltree_node_set_parent(lrrnode, node); + } lnode->children[right] = lrlnode; - if (lrlnode != NULL) + if (lrlnode != NULL) { avltree_node_set_parent(lrlnode, lnode); + } balance = avltree_node_balance(lrnode); @@ -222,10 +229,11 @@ avltree_rotate(struct avltree *tree, struct avltree_node *node, int balance) avltree_node_set_parent(lrnode, parent); avltree_node_set_balance(lrnode, 0); - if (unlikely(parent == NULL)) + if (unlikely(parent == NULL)) { tree->root = lrnode; - else + } else { parent->children[index] = lrnode; + } /* * The balance of the new subtree root is always 0 in this case, which @@ -278,8 +286,9 @@ avltree_insert_rebalance(struct avltree *tree, struct avltree_node *parent, * Both previous and new balances are different from 0, which means the * new one has reached -2 or 2. Rebalance now. */ - if (old_balance != 0) + if (old_balance != 0) { break; + } /* * The new balance is either -1 or 1. Update the current node and @@ -291,8 +300,9 @@ avltree_insert_rebalance(struct avltree *tree, struct avltree_node *parent, /* * The tree root was reached. */ - if (parent == NULL) + if (parent == NULL) { return; + } index = avltree_node_index(node, parent); } @@ -306,11 +316,11 @@ avltree_remove(struct avltree *tree, struct avltree_node *node) struct avltree_node *child, *parent; int left, right, index, old_balance, new_balance; - if (node->children[AVLTREE_LEFT] == NULL) + if (node->children[AVLTREE_LEFT] == NULL) { child = node->children[AVLTREE_RIGHT]; - else if (node->children[AVLTREE_RIGHT] == NULL) + } else if (node->children[AVLTREE_RIGHT] == NULL) { child = node->children[AVLTREE_LEFT]; - else { + } else { struct avltree_node *successor; /* @@ -326,16 +336,18 @@ avltree_remove(struct avltree *tree, struct avltree_node *node) successor = node->children[right]; - while (successor->children[left] != NULL) + while (successor->children[left] != NULL) { successor = successor->children[left]; + } child = successor->children[right]; parent = avltree_node_parent(node); - if (unlikely(parent == NULL)) + if (unlikely(parent == NULL)) { tree->root = successor; - else + } else { parent->children[avltree_node_index(node, parent)] = successor; + } parent = avltree_node_parent(successor); index = avltree_node_index(successor, parent); @@ -347,15 +359,16 @@ avltree_remove(struct avltree *tree, struct avltree_node *node) successor->children[left] = node->children[left]; avltree_node_set_parent(successor->children[left], successor); - if (node == parent) + if (node == parent) { parent = successor; - else { + } else { successor->children[right] = node->children[right]; avltree_node_set_parent(successor->children[right], successor); parent->children[left] = child; - if (child != NULL) + if (child != NULL) { avltree_node_set_parent(child, parent); + } } goto update_balance; @@ -367,8 +380,9 @@ avltree_remove(struct avltree *tree, struct avltree_node *node) parent = avltree_node_parent(node); - if (child != NULL) + if (child != NULL) { avltree_node_set_parent(child, parent); + } if (parent == NULL) { tree->root = child; @@ -400,16 +414,17 @@ update_balance: parent = avltree_node_parent(node); - if (parent != NULL) + if (parent != NULL) { index = avltree_node_index(node, parent); + } /* * The overall subtree height has decreased. Update the current node and * iterate again to propagate the change. */ - if (new_balance == 0) + if (new_balance == 0) { avltree_node_set_balance(node, new_balance); - else { + } else { int decreased; /* @@ -420,15 +435,17 @@ update_balance: decreased = avltree_rotate(tree, node, new_balance); - if (!decreased) + if (!decreased) { break; + } } /* * The tree root was reached. */ - if (parent == NULL) + if (parent == NULL) { break; + } } } @@ -437,13 +454,15 @@ avltree_nearest(struct avltree_node *parent, int index, int direction) { assert(avltree_check_index(direction)); - if (parent == NULL) + if (parent == NULL) { return NULL; + } assert(avltree_check_index(index)); - if (index != direction) + if (index != direction) { return parent; + } return avltree_walk(parent, direction); } @@ -457,8 +476,9 @@ avltree_firstlast(const struct avltree *tree, int direction) prev = NULL; - for (cur = tree->root; cur != NULL; cur = cur->children[direction]) + for (cur = tree->root; cur != NULL; cur = cur->children[direction]) { prev = cur; + } return prev; } @@ -473,14 +493,16 @@ avltree_walk(struct avltree_node *node, int direction) left = direction; right = 1 - left; - if (node == NULL) + if (node == NULL) { return NULL; + } if (node->children[left] != NULL) { node = node->children[left]; - while (node->children[right] != NULL) + while (node->children[right] != NULL) { node = node->children[right]; + } } else { struct avltree_node *parent; int index; @@ -488,14 +510,16 @@ avltree_walk(struct avltree_node *node, int direction) for (;;) { parent = avltree_node_parent(node); - if (parent == NULL) + if (parent == NULL) { return NULL; + } index = avltree_node_index(node, parent); node = parent; - if (index == right) + if (index == right) { break; + } } } @@ -509,8 +533,9 @@ avltree_postwalk_deepest(const struct avltree *tree) node = tree->root; - if (node == NULL) + if (node == NULL) { return NULL; + } return avltree_node_find_deepest(node); } @@ -521,23 +546,26 @@ avltree_postwalk_unlink(struct avltree_node *node) struct avltree_node *parent; int index; - if (node == NULL) + if (node == NULL) { return NULL; + } assert(node->children[AVLTREE_LEFT] == NULL); assert(node->children[AVLTREE_RIGHT] == NULL); parent = avltree_node_parent(node); - if (parent == NULL) + if (parent == NULL) { return NULL; + } index = avltree_node_index(node, parent); parent->children[index] = NULL; node = parent->children[AVLTREE_RIGHT]; - if (node == NULL) + if (node == NULL) { return parent; + } return avltree_node_find_deepest(node); } @@ -45,8 +45,9 @@ bitmap_cmp(const unsigned long *a, const unsigned long *b, int nr_bits) if (n != 0) { rv = memcmp(a, b, n * sizeof(unsigned long)); - if (rv != 0) + if (rv != 0) { return rv; + } nr_bits -= n * LONG_BIT; } @@ -60,19 +61,21 @@ bitmap_cmp(const unsigned long *a, const unsigned long *b, int nr_bits) last_b &= mask; } - if (last_a == last_b) + if (last_a == last_b) { return 0; - else if (last_a < last_b) + } else if (last_a < last_b) { return -1; - else + } else { return 1; + } } static inline unsigned long bitmap_find_next_compute_complement(unsigned long word, int nr_bits) { - if (nr_bits < LONG_BIT) + if (nr_bits < LONG_BIT) { word |= (((unsigned long)-1) << nr_bits); + } return ~word; } @@ -94,27 +97,32 @@ bitmap_find_next_bit(const unsigned long *bm, int nr_bits, int bit, word = *bm; - if (complement) + if (complement) { word = bitmap_find_next_compute_complement(word, nr_bits); + } - if (bit < LONG_BIT) + if (bit < LONG_BIT) { word &= ~(bitmap_mask(bit) - 1); + } for (;;) { bit = __builtin_ffsl(word); - if (bit != 0) + if (bit != 0) { return ((bm - start) * LONG_BIT) + bit - 1; + } bm++; - if (bm >= end) + if (bm >= end) { return -1; + } nr_bits -= LONG_BIT; word = *bm; - if (complement) + if (complement) { word = bitmap_find_next_compute_complement(word, nr_bits); + } } } @@ -74,8 +74,9 @@ bitmap_copy(unsigned long *dest, const unsigned long *src, int nr_bits) static inline void bitmap_set(unsigned long *bm, int bit) { - if (bit >= LONG_BIT) + if (bit >= LONG_BIT) { bitmap_lookup(bm, bit); + } *bm |= bitmap_mask(bit); } @@ -83,8 +84,9 @@ bitmap_set(unsigned long *bm, int bit) static inline void bitmap_set_atomic(unsigned long *bm, int bit) { - if (bit >= LONG_BIT) + if (bit >= LONG_BIT) { bitmap_lookup(bm, bit); + } atomic_or_ulong(bm, bitmap_mask(bit)); } @@ -92,8 +94,9 @@ bitmap_set_atomic(unsigned long *bm, int bit) static inline void bitmap_clear(unsigned long *bm, int bit) { - if (bit >= LONG_BIT) + if (bit >= LONG_BIT) { bitmap_lookup(bm, bit); + } *bm &= ~bitmap_mask(bit); } @@ -101,8 +104,9 @@ bitmap_clear(unsigned long *bm, int bit) static inline void bitmap_clear_atomic(unsigned long *bm, int bit) { - if (bit >= LONG_BIT) + if (bit >= LONG_BIT) { bitmap_lookup(bm, bit); + } atomic_and_ulong(bm, ~bitmap_mask(bit)); } @@ -110,8 +114,9 @@ bitmap_clear_atomic(unsigned long *bm, int bit) static inline int bitmap_test(const unsigned long *bm, int bit) { - if (bit >= LONG_BIT) + if (bit >= LONG_BIT) { bitmap_lookup(bm, bit); + } return ((*bm & bitmap_mask(bit)) != 0); } @@ -123,8 +128,9 @@ bitmap_and(unsigned long *a, const unsigned long *b, int nr_bits) n = BITMAP_LONGS(nr_bits); - for (i = 0; i < n; i++) + for (i = 0; i < n; i++) { a[i] &= b[i]; + } } static inline void @@ -134,8 +140,9 @@ bitmap_or(unsigned long *a, const unsigned long *b, int nr_bits) n = BITMAP_LONGS(nr_bits); - for (i = 0; i < n; i++) + for (i = 0; i < n; i++) { a[i] |= b[i]; + } } static inline void @@ -145,8 +152,9 @@ bitmap_xor(unsigned long *a, const unsigned long *b, int nr_bits) n = BITMAP_LONGS(nr_bits); - for (i = 0; i < n; i++) + for (i = 0; i < n; i++) { a[i] ^= b[i]; + } } static inline int @@ -75,10 +75,11 @@ cpu_id(void) id = sched_getcpu(); - if (id == -1) + if (id == -1) { return 0; - else if (id >= NR_CPUS) + } else if (id >= NR_CPUS) { id &= (NR_CPUS - 1); + } return id; #endif @@ -62,8 +62,9 @@ static const char *errormsg_table[] = { const char * error_str(unsigned int error) { - if (error >= ERRORMSG_TABLE_SIZE) + if (error >= ERRORMSG_TABLE_SIZE) { return "invalid error code"; + } return errormsg_table[error]; } @@ -105,8 +105,9 @@ hash_str(const char *str, unsigned int bits) unsigned long hash; char c; - for (hash = 0; (c = *str) != '\0'; str++) + for (hash = 0; (c = *str) != '\0'; str++) { hash = ((hash << 5) - hash) + c; + } return hash & ((1 << bits) - 1); } @@ -56,8 +56,9 @@ _list_divide(struct list *input_list, struct list *left_list, node = input_list->next; - for (i = 0; (i < list_size) && !list_end(input_list, node); i++) + for (i = 0; (i < list_size) && !list_end(input_list, node); i++) { node = node->next; + } list_split(left_list, input_list, node); } @@ -125,8 +126,9 @@ list_sort(struct list *list, list_sort_cmp_fn_t cmp_fn) for (list_size = 1; /* no condition */; list_size <<= 1) { for (nr_merges = 0; /* no condition */; nr_merges++) { - if (list_empty(list)) + if (list_empty(list)) { break; + } _list_divide(list, &left_list, list_size); _list_merge(&left_list, list, &output_list, list_size, cmp_fn); @@ -135,7 +137,8 @@ list_sort(struct list *list, list_sort_cmp_fn_t cmp_fn) list_concat(list, &output_list); list_init(&output_list); - if (nr_merges <= 1) + if (nr_merges <= 1) { return; + } } } @@ -211,8 +211,9 @@ list_concat(struct list *list1, const struct list *list2) { struct list *last1, *first2, *last2; - if (list_empty(list2)) + if (list_empty(list2)) { return; + } last1 = list1->prev; first2 = list2->next; @@ -47,8 +47,9 @@ rbtree_node_index(const struct rbtree_node *node, assert(parent != NULL); assert((node == NULL) || (rbtree_node_parent(node) == parent)); - if (parent->children[RBTREE_LEFT] == node) + if (parent->children[RBTREE_LEFT] == node) { return RBTREE_LEFT; + } assert(parent->children[RBTREE_RIGHT] == node); @@ -139,8 +140,9 @@ rbtree_node_find_deepest(struct rbtree_node *node) if (node == NULL) { node = parent->children[RBTREE_RIGHT]; - if (node == NULL) + if (node == NULL) { return parent; + } } } } @@ -164,16 +166,18 @@ rbtree_rotate(struct rbtree *tree, struct rbtree_node *node, int direction) node->children[right] = rnode->children[left]; - if (rnode->children[left] != NULL) + if (rnode->children[left] != NULL) { rbtree_node_set_parent(rnode->children[left], node); + } rnode->children[left] = node; rbtree_node_set_parent(rnode, parent); - if (unlikely(parent == NULL)) + if (unlikely(parent == NULL)) { tree->root = rnode; - else + } else { parent->children[rbtree_node_index(node, parent)] = rnode; + } rbtree_node_set_parent(node, rnode); } @@ -192,10 +196,11 @@ rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, node->children[RBTREE_LEFT] = NULL; node->children[RBTREE_RIGHT] = NULL; - if (unlikely(parent == NULL)) + if (unlikely(parent == NULL)) { tree->root = node; - else + } else { parent->children[index] = node; + } for (;;) { if (parent == NULL) { @@ -203,8 +208,9 @@ rbtree_insert_rebalance(struct rbtree *tree, struct rbtree_node *parent, break; } - if (rbtree_node_is_black(parent)) + if (rbtree_node_is_black(parent)) { break; + } grand_parent = rbtree_node_parent(parent); assert(grand_parent != NULL); @@ -253,11 +259,11 @@ rbtree_remove(struct rbtree *tree, struct rbtree_node *node) struct rbtree_node *child, *parent, *brother; int color, left, right; - if (node->children[RBTREE_LEFT] == NULL) + if (node->children[RBTREE_LEFT] == NULL) { child = node->children[RBTREE_RIGHT]; - else if (node->children[RBTREE_RIGHT] == NULL) + } else if (node->children[RBTREE_RIGHT] == NULL) { child = node->children[RBTREE_LEFT]; - else { + } else { struct rbtree_node *successor; /* @@ -266,17 +272,19 @@ rbtree_remove(struct rbtree *tree, struct rbtree_node *node) successor = node->children[RBTREE_RIGHT]; - while (successor->children[RBTREE_LEFT] != NULL) + while (successor->children[RBTREE_LEFT] != NULL) { successor = successor->children[RBTREE_LEFT]; + } color = rbtree_node_color(successor); child = successor->children[RBTREE_RIGHT]; parent = rbtree_node_parent(node); - if (unlikely(parent == NULL)) + if (unlikely(parent == NULL)) { tree->root = successor; - else + } else { parent->children[rbtree_node_index(node, parent)] = successor; + } parent = rbtree_node_parent(successor); @@ -287,16 +295,17 @@ rbtree_remove(struct rbtree *tree, struct rbtree_node *node) successor->children[RBTREE_LEFT] = node->children[RBTREE_LEFT]; rbtree_node_set_parent(successor->children[RBTREE_LEFT], successor); - if (node == parent) + if (node == parent) { parent = successor; - else { + } else { successor->children[RBTREE_RIGHT] = node->children[RBTREE_RIGHT]; rbtree_node_set_parent(successor->children[RBTREE_RIGHT], successor); parent->children[RBTREE_LEFT] = child; - if (child != NULL) + if (child != NULL) { rbtree_node_set_parent(child, parent); + } } goto update_color; @@ -309,21 +318,24 @@ rbtree_remove(struct rbtree *tree, struct rbtree_node *node) color = rbtree_node_color(node); parent = rbtree_node_parent(node); - if (child != NULL) + if (child != NULL) { rbtree_node_set_parent(child, parent); + } - if (unlikely(parent == NULL)) + if (unlikely(parent == NULL)) { tree->root = child; - else + } else { parent->children[rbtree_node_index(node, parent)] = child; + } /* * The node has been removed, update the colors. The child pointer can * be NULL, in which case it is considered a black leaf. */ update_color: - if (color == RBTREE_COLOR_RED) + if (color == RBTREE_COLOR_RED) { return; + } for (;;) { if ((child != NULL) && rbtree_node_is_red(child)) { @@ -331,8 +343,9 @@ update_color: break; } - if (parent == NULL) + if (parent == NULL) { break; + } left = rbtree_node_index(child, parent); right = 1 - left; @@ -397,13 +410,15 @@ rbtree_nearest(struct rbtree_node *parent, int index, int direction) { assert(rbtree_check_index(direction)); - if (parent == NULL) + if (parent == NULL) { return NULL; + } assert(rbtree_check_index(index)); - if (index != direction) + if (index != direction) { return parent; + } return rbtree_walk(parent, direction); } @@ -417,8 +432,9 @@ rbtree_firstlast(const struct rbtree *tree, int direction) prev = NULL; - for (cur = tree->root; cur != NULL; cur = cur->children[direction]) + for (cur = tree->root; cur != NULL; cur = cur->children[direction]) { prev = cur; + } return prev; } @@ -433,14 +449,16 @@ rbtree_walk(struct rbtree_node *node, int direction) left = direction; right = 1 - left; - if (node == NULL) + if (node == NULL) { return NULL; + } if (node->children[left] != NULL) { node = node->children[left]; - while (node->children[right] != NULL) + while (node->children[right] != NULL) { node = node->children[right]; + } } else { struct rbtree_node *parent; int index; @@ -448,14 +466,16 @@ rbtree_walk(struct rbtree_node *node, int direction) for (;;) { parent = rbtree_node_parent(node); - if (parent == NULL) + if (parent == NULL) { return NULL; + } index = rbtree_node_index(node, parent); node = parent; - if (index == right) + if (index == right) { break; + } } } @@ -469,8 +489,9 @@ rbtree_postwalk_deepest(const struct rbtree *tree) node = tree->root; - if (node == NULL) + if (node == NULL) { return NULL; + } return rbtree_node_find_deepest(node); } @@ -481,23 +502,26 @@ rbtree_postwalk_unlink(struct rbtree_node *node) struct rbtree_node *parent; int index; - if (node == NULL) + if (node == NULL) { return NULL; + } assert(node->children[RBTREE_LEFT] == NULL); assert(node->children[RBTREE_RIGHT] == NULL); parent = rbtree_node_parent(node); - if (parent == NULL) + if (parent == NULL) { return NULL; + } index = rbtree_node_index(node, parent); parent->children[index] = NULL; node = parent->children[RBTREE_RIGHT]; - if (node == NULL) + if (node == NULL) { return parent; + } return rbtree_node_find_deepest(node); } @@ -149,15 +149,17 @@ rdxtree_node_create(struct rdxtree_node **nodep, unsigned int height) if (rdxtree_fail_node_creation_threshold != 0) { rdxtree_nr_node_creations++; - if (rdxtree_nr_node_creations == rdxtree_fail_node_creation_threshold) + if (rdxtree_nr_node_creations == rdxtree_fail_node_creation_threshold) { return ERR_NOMEM; + } } #endif /* RDXTREE_ENABLE_NODE_CREATION_FAILURES */ node = malloc(sizeof(*node)); - if (node == NULL) + if (node == NULL) { return ERR_NOMEM; + } rdxtree_assert_alignment(node); node->parent = NULL; @@ -296,10 +298,11 @@ rdxtree_max_key(unsigned int height) shift = RDXTREE_RADIX * height; - if (likely(shift < (sizeof(rdxtree_key_t) * CHAR_BIT))) + if (likely(shift < (sizeof(rdxtree_key_t) * CHAR_BIT))) { return ((rdxtree_key_t)1 << shift) - 1; - else + } else { return ~((rdxtree_key_t)0); + } } static void @@ -311,18 +314,21 @@ rdxtree_shrink(struct rdxtree *tree) while (tree->height > 0) { node = rdxtree_entry_addr(tree->root); - if (node->nr_entries != 1) + if (node->nr_entries != 1) { break; + } entry = node->entries[0]; - if (entry == NULL) + if (entry == NULL) { break; + } tree->height--; - if (tree->height > 0) + if (tree->height > 0) { rdxtree_node_unlink(rdxtree_entry_addr(entry)); + } llsync_assign_ptr(tree->root, entry); rdxtree_node_schedule_destruction(node); @@ -338,8 +344,9 @@ rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key) new_height = tree->height + 1; - while (key > rdxtree_max_key(new_height)) + while (key > rdxtree_max_key(new_height)) { new_height++; + } if (tree->root == NULL) { tree->height = new_height; @@ -356,13 +363,14 @@ rdxtree_grow(struct rdxtree *tree, rdxtree_key_t key) return error; } - if (tree->height == 0) + if (tree->height == 0) { rdxtree_node_bm_clear(node, 0); - else { + } else { rdxtree_node_link(root, node, 0); - if (rdxtree_node_bm_empty(root)) + if (rdxtree_node_bm_empty(root)) { rdxtree_node_bm_clear(node, 0); + } } rdxtree_node_insert(node, 0, tree->root); @@ -381,8 +389,9 @@ rdxtree_cleanup(struct rdxtree *tree, struct rdxtree_node *node) for (;;) { if (likely(!rdxtree_node_empty(node))) { - if (unlikely(node->parent == NULL)) + if (unlikely(node->parent == NULL)) { rdxtree_shrink(tree); + } break; } @@ -408,8 +417,9 @@ rdxtree_insert_bm_clear(struct rdxtree_node *node, unsigned int index) for (;;) { rdxtree_node_bm_clear(node, index); - if (!rdxtree_node_full(node) || (node->parent == NULL)) + if (!rdxtree_node_full(node) || (node->parent == NULL)) { break; + } index = node->index; node = node->parent; @@ -431,20 +441,23 @@ rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, if (unlikely(key > rdxtree_max_key(tree->height))) { error = rdxtree_grow(tree, key); - if (error) + if (error) { return error; + } } height = tree->height; if (unlikely(height == 0)) { - if (tree->root != NULL) + if (tree->root != NULL) { return ERR_BUSY; + } llsync_assign_ptr(tree->root, ptr); - if (slotp != NULL) + if (slotp != NULL) { *slotp = &tree->root; + } return ERR_SUCCESS; } @@ -458,17 +471,18 @@ rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, error = rdxtree_node_create(&node, height - 1); if (error) { - if (prev == NULL) + if (prev == NULL) { tree->height = 0; - else + } else { rdxtree_cleanup(tree, prev); + } return error; } - if (prev == NULL) + if (prev == NULL) { llsync_assign_ptr(tree->root, rdxtree_node_to_entry(node)); - else { + } else { rdxtree_node_link(node, prev, index); rdxtree_node_insert_node(prev, index, node); } @@ -481,14 +495,16 @@ rdxtree_insert_common(struct rdxtree *tree, rdxtree_key_t key, height--; } while (height > 0); - if (unlikely(node != NULL)) + if (unlikely(node != NULL)) { return ERR_BUSY; + } rdxtree_node_insert(prev, index, ptr); rdxtree_insert_bm_clear(prev, index); - if (slotp != NULL) + if (slotp != NULL) { *slotp = &prev->entries[index]; + } return ERR_SUCCESS; } @@ -513,8 +529,9 @@ rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, llsync_assign_ptr(tree->root, ptr); *keyp = 0; - if (slotp != NULL) + if (slotp != NULL) { *slotp = &tree->root; + } return ERR_SUCCESS; } @@ -543,8 +560,9 @@ rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, prev = node; index = rdxtree_node_bm_first(node); - if (index == (unsigned int)-1) + if (index == (unsigned int)-1) { goto grow; + } key |= (rdxtree_key_t)index << shift; node = rdxtree_entry_addr(node->entries[index]); @@ -555,8 +573,9 @@ rdxtree_insert_alloc_common(struct rdxtree *tree, void *ptr, rdxtree_node_insert(prev, index, ptr); rdxtree_insert_bm_clear(prev, index); - if (slotp != NULL) + if (slotp != NULL) { *slotp = &prev->entries[index]; + } goto out; @@ -564,8 +583,9 @@ grow: key = rdxtree_max_key(height) + 1; error = rdxtree_insert_common(tree, key, ptr, slotp); - if (error) + if (error) { return error; + } out: *keyp = key; @@ -578,8 +598,9 @@ rdxtree_remove_bm_set(struct rdxtree_node *node, unsigned int index) do { rdxtree_node_bm_set(node, index); - if (node->parent == NULL) + if (node->parent == NULL) { break; + } index = node->index; node = node->parent; @@ -594,8 +615,9 @@ rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key) height = tree->height; - if (unlikely(key > rdxtree_max_key(height))) + if (unlikely(key > rdxtree_max_key(height))) { return NULL; + } node = rdxtree_entry_addr(tree->root); @@ -607,8 +629,9 @@ rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key) shift = (height - 1) * RDXTREE_RADIX; do { - if (node == NULL) + if (node == NULL) { return NULL; + } prev = node; index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK; @@ -617,8 +640,9 @@ rdxtree_remove(struct rdxtree *tree, rdxtree_key_t key) height--; } while (height > 0); - if (node == NULL) + if (node == NULL) { return NULL; + } rdxtree_node_remove(prev, index); rdxtree_remove_bm_set(prev, index); @@ -644,12 +668,14 @@ rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key, height = rdxtree_entry_is_node(entry) ? node->height + 1 : 0; } - if (key > rdxtree_max_key(height)) + if (key > rdxtree_max_key(height)) { return NULL; + } if (height == 0) { - if (node == NULL) + if (node == NULL) { return NULL; + } return get_slot ? (void *)&tree->root : node; } @@ -657,8 +683,9 @@ rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key, shift = (height - 1) * RDXTREE_RADIX; do { - if (node == NULL) + if (node == NULL) { return NULL; + } prev = node; index = (unsigned int)(key >> shift) & RDXTREE_RADIX_MASK; @@ -668,8 +695,9 @@ rdxtree_lookup_common(const struct rdxtree *tree, rdxtree_key_t key, height--; } while (height > 0); - if (node == NULL) + if (node == NULL) { return NULL; + } return get_slot ? (void *)&prev->entries[index] : node; } @@ -699,13 +727,14 @@ rdxtree_walk_next(struct rdxtree *tree, struct rdxtree_iter *iter) entry = llsync_read_ptr(tree->root); - if (entry == NULL) + if (entry == NULL) { return NULL; + } if (!rdxtree_entry_is_node(entry)) { - if (iter->key != (rdxtree_key_t)-1) + if (iter->key != (rdxtree_key_t)-1) { return NULL; - else { + } else { iter->key = 0; return rdxtree_entry_addr(entry); } @@ -713,8 +742,9 @@ rdxtree_walk_next(struct rdxtree *tree, struct rdxtree_iter *iter) key = iter->key + 1; - if ((key == 0) && (iter->node != NULL)) + if ((key == 0) && (iter->node != NULL)) { return NULL; + } root = rdxtree_entry_addr(entry); @@ -722,8 +752,9 @@ restart: node = root; height = root->height + 1; - if (key > rdxtree_max_key(height)) + if (key > rdxtree_max_key(height)) { return NULL; + } shift = (height - 1) * RDXTREE_RADIX; @@ -737,14 +768,16 @@ restart: shift += RDXTREE_RADIX; key = ((key >> shift) + 1) << shift; - if (key == 0) + if (key == 0) { return NULL; + } goto restart; } - if (orig_index != index) + if (orig_index != index) { key = ((key >> shift) + (index - orig_index)) << shift; + } shift -= RDXTREE_RADIX; height--; @@ -761,8 +794,9 @@ rdxtree_walk(struct rdxtree *tree, struct rdxtree_iter *iter) unsigned int index, orig_index; void *ptr; - if (iter->node == NULL) + if (iter->node == NULL) { return rdxtree_walk_next(tree, iter); + } index = (iter->key + 1) & RDXTREE_RADIX_MASK; @@ -786,8 +820,9 @@ rdxtree_remove_all(struct rdxtree *tree) struct rdxtree_iter iter; if (tree->height == 0) { - if (tree->root != NULL) + if (tree->root != NULL) { llsync_assign_ptr(tree->root, NULL); + } return; } @@ -796,15 +831,16 @@ rdxtree_remove_all(struct rdxtree *tree) rdxtree_iter_init(&iter); rdxtree_walk_next(tree, &iter); - if (iter.node == NULL) + if (iter.node == NULL) { break; + } node = iter.node; parent = node->parent; - if (parent == NULL) + if (parent == NULL) { rdxtree_init(tree); - else { + } else { rdxtree_node_remove(parent, node->index); rdxtree_remove_bm_set(parent, node->index); rdxtree_cleanup(tree, parent); @@ -858,8 +858,9 @@ shell_process_tabulation(void) for (i = 0; i < size; i++) { error = shell_process_raw_char(name[i]); - if (error) + if (error) { goto out; + } } error = 0; @@ -1144,7 +1145,8 @@ shell_setup(void) for (i = 0; i < ARRAY_SIZE(shell_default_cmds); i++) { error = shell_cmd_register(&shell_default_cmds[i]); - if (error) + if (error) { error_die(error); + } } } diff --git a/test/test_avltree.c b/test/test_avltree.c index 395561d..3f11e57 100644 --- a/test/test_avltree.c +++ b/test/test_avltree.c @@ -54,13 +54,15 @@ print_subtree(struct avltree_node *node, int level) char balance; int i; - if (node == NULL) + if (node == NULL) { return; + } print_subtree(node->children[AVLTREE_RIGHT], level + 1); - for (i = level; i > 0; i--) + for (i = level; i > 0; i--) { putchar(' '); + } obj = avltree_entry(node, struct obj, node); @@ -114,8 +116,9 @@ main(int argc, char *argv[]) id = get_id(i); node = avltree_lookup_slot(&tree, id, obj_cmp_lookup, slot); - if (node != NULL) + if (node != NULL) { continue; + } obj = malloc(sizeof(*obj)); obj->id = id; diff --git a/test/test_rbtree.c b/test/test_rbtree.c index 0478a5d..db4b6ca 100644 --- a/test/test_rbtree.c +++ b/test/test_rbtree.c @@ -54,13 +54,15 @@ print_subtree(struct rbtree_node *node, int level) char color; int i; - if (node == NULL) + if (node == NULL) { return; + } print_subtree(node->children[RBTREE_RIGHT], level + 1); - for (i = level; i > 0; i--) + for (i = level; i > 0; i--) { putchar(' '); + } obj = rbtree_entry(node, struct obj, node); color = (node->parent & RBTREE_COLOR_MASK) ? 'b' : 'r'; @@ -99,8 +101,9 @@ main(int argc, char *argv[]) id = get_id(i); node = rbtree_lookup_slot(&tree, id, obj_cmp_lookup, slot); - if (node != NULL) + if (node != NULL) { continue; + } obj = malloc(sizeof(*obj)); obj->id = id; diff --git a/test/test_rdxtree.c b/test/test_rdxtree.c index bfe9820..9ed21ac 100644 --- a/test/test_rdxtree.c +++ b/test/test_rdxtree.c @@ -71,13 +71,15 @@ print_value(void *ptr, size_t index, size_t level) struct obj *obj; int i; - if (ptr == NULL) + if (ptr == NULL) { return; + } obj = ptr; - for (i = level; i > 0; i--) + for (i = level; i > 0; i--) { putchar(' '); + } printf("%zu:%llu\n", index, (unsigned long long)obj->id); } @@ -87,13 +89,15 @@ print_values(struct rdxtree_node *node, size_t index, size_t level) { size_t i; - for (i = level; i > 0; i--) + for (i = level; i > 0; i--) { putchar(' '); + } printf("%zu:n (bm: " BM_FORMAT ")\n", index, node->alloc_bm); - for (i = 0; i < ARRAY_SIZE(node->entries); i++) + for (i = 0; i < ARRAY_SIZE(node->entries); i++) { print_value(node->entries[i], i, level + 1); + } } static void @@ -102,8 +106,9 @@ print_node(struct rdxtree_node *node, int height, size_t index, size_t level) void *entry; size_t i; - for (i = level; i > 0; i--) + for (i = level; i > 0; i--) { putchar(' '); + } printf("%zu:n (bm: " BM_FORMAT ")\n", index, node->alloc_bm); @@ -116,13 +121,15 @@ print_node(struct rdxtree_node *node, int height, size_t index, size_t level) static void print_subtree(struct rdxtree_node *node, int height, size_t index, size_t level) { - if (node == NULL) + if (node == NULL) { return; + } - if (height == 1) + if (height == 1) { print_values(node, index, level); - else + } else { print_node(node, height, index, level); + } } static void @@ -132,10 +139,11 @@ print_tree(struct rdxtree *tree) root = rdxtree_entry_addr(tree->root); - if (tree->height == 0) + if (tree->height == 0) { print_value(root, 0, 0); - else + } else { print_subtree(root, tree->height, 0, 0); + } } static void diff --git a/test/test_shell.c b/test/test_shell.c index 866ae5f..c26e545 100644 --- a/test/test_shell.c +++ b/test/test_shell.c @@ -99,8 +99,9 @@ main(int argc, char *argv[]) for (i = 0; i < ARRAY_SIZE(test_shell_cmds); i++) { ret = shell_cmd_register(&test_shell_cmds[i]); - if (ret) + if (ret) { error_die(ret); + } } setbuf(stdin, NULL); |