diff options
Diffstat (limited to 'src/red-black-tree.c')
| -rw-r--r-- | src/red-black-tree.c | 32 |
1 files changed, 15 insertions, 17 deletions
diff --git a/src/red-black-tree.c b/src/red-black-tree.c index 7c2d2c1..5ae0f31 100644 --- a/src/red-black-tree.c +++ b/src/red-black-tree.c | |||
| @@ -6,8 +6,6 @@ | |||
| 6 | #include <stdlib.h> | 6 | #include <stdlib.h> |
| 7 | #include <time.h> | 7 | #include <time.h> |
| 8 | 8 | ||
| 9 | #include "util.h" | ||
| 10 | |||
| 11 | /* The authors of this work have released all rights to it and placed it | 9 | /* The authors of this work have released all rights to it and placed it |
| 12 | in the public domain under the Creative Commons CC0 1.0 waiver | 10 | in the public domain under the Creative Commons CC0 1.0 waiver |
| 13 | (http://creativecommons.org/publicdomain/zero/1.0/). | 11 | (http://creativecommons.org/publicdomain/zero/1.0/). |
| @@ -27,22 +25,22 @@ enum rbtree_node_color { RED, | |||
| 27 | BLACK }; | 25 | BLACK }; |
| 28 | 26 | ||
| 29 | typedef struct rbtree_node_t { | 27 | typedef struct rbtree_node_t { |
| 30 | void * key; | 28 | void *key; |
| 31 | void * value; | 29 | void *value; |
| 32 | struct rbtree_node_t * left; | 30 | struct rbtree_node_t *left; |
| 33 | struct rbtree_node_t * right; | 31 | struct rbtree_node_t *right; |
| 34 | struct rbtree_node_t * parent; | 32 | struct rbtree_node_t *parent; |
| 35 | enum rbtree_node_color color; | 33 | enum rbtree_node_color color; |
| 36 | } * rbtree_node; | 34 | } *rbtree_node; |
| 37 | 35 | ||
| 38 | typedef struct rbtree_t { | 36 | typedef struct rbtree_t { |
| 39 | rbtree_node root; | 37 | rbtree_node root; |
| 40 | } * rbtree; | 38 | } *rbtree; |
| 41 | 39 | ||
| 42 | typedef int (*compare_func)(void *left, void *right); | 40 | typedef int (*compare_func)(void *left, void *right); |
| 43 | 41 | ||
| 44 | rbtree rbtree_create(); | 42 | rbtree rbtree_create(void); |
| 45 | void * rbtree_lookup(rbtree t, void *key, compare_func compare); | 43 | void *rbtree_lookup(rbtree t, void *key, compare_func compare); |
| 46 | void rbtree_insert(rbtree t, void *key, void *value, compare_func compare); | 44 | void rbtree_insert(rbtree t, void *key, void *value, compare_func compare); |
| 47 | void rbtree_delete(rbtree t, void *key, compare_func compare); | 45 | void rbtree_delete(rbtree t, void *key, compare_func compare); |
| 48 | 46 | ||
| @@ -187,7 +185,7 @@ verify_property_5_helper(node n, int black_count, int *path_black_count) | |||
| 187 | } | 185 | } |
| 188 | 186 | ||
| 189 | rbtree | 187 | rbtree |
| 190 | rbtree_create() | 188 | rbtree_create(void) |
| 191 | { | 189 | { |
| 192 | rbtree t = malloc(sizeof *t); | 190 | rbtree t = malloc(sizeof *t); |
| 193 | t->root = NULL; | 191 | t->root = NULL; |
| @@ -538,8 +536,8 @@ static void print_tree_helper(rbtree_node n, int indent); | |||
| 538 | int | 536 | int |
| 539 | compare_int(void *leftp, void *rightp) | 537 | compare_int(void *leftp, void *rightp) |
| 540 | { | 538 | { |
| 541 | int left = (int) leftp; | 539 | long left = (long) leftp; |
| 542 | int right = (int) rightp; | 540 | long right = (long) rightp; |
| 543 | if ( left < right ) | 541 | if ( left < right ) |
| 544 | return -1; | 542 | return -1; |
| 545 | else if ( left > right ) | 543 | else if ( left > right ) |
| @@ -575,16 +573,16 @@ print_tree_helper(rbtree_node n, int indent) | |||
| 575 | for ( i = 0; i < indent; i++ ) | 573 | for ( i = 0; i < indent; i++ ) |
| 576 | fputs(" ", stdout); | 574 | fputs(" ", stdout); |
| 577 | if ( n->color == BLACK ) | 575 | if ( n->color == BLACK ) |
| 578 | printf("%d\n", (int) n->key); | 576 | printf("%ld\n", (long) n->key); |
| 579 | else | 577 | else |
| 580 | printf("<%d>\n", (int) n->key); | 578 | printf("<%ld>\n", (long) n->key); |
| 581 | if ( n->left != NULL ) { | 579 | if ( n->left != NULL ) { |
| 582 | print_tree_helper(n->left, indent + INDENT_STEP); | 580 | print_tree_helper(n->left, indent + INDENT_STEP); |
| 583 | } | 581 | } |
| 584 | } | 582 | } |
| 585 | 583 | ||
| 586 | int | 584 | int |
| 587 | main() | 585 | main(void) |
| 588 | { | 586 | { |
| 589 | int i; | 587 | int i; |
| 590 | rbtree t = rbtree_create(); | 588 | rbtree t = rbtree_create(); |
