From 73010dc96357a9715b87421534bebc19ecd5863d Mon Sep 17 00:00:00 2001 From: Alexandre Jesus Date: Wed, 5 Oct 2016 18:42:30 +0100 Subject: Fix issues that would lead to seg fault on the online method --- src/dfs.c | 11 ++++++--- src/main/online.c | 9 ++++--- src/random_heuristic.c | 66 ++++++++++++++++++++++++-------------------------- 3 files changed, 45 insertions(+), 41 deletions(-) diff --git a/src/dfs.c b/src/dfs.c index b0bda53..12f4ee2 100644 --- a/src/dfs.c +++ b/src/dfs.c @@ -92,11 +92,12 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s front_last->next = new_front_item(tree->values.p, tree->values.w, front_last, NULL); front_last = front_last->next; + /* Adjust prev and next */ + if(tree->prev != NULL) tree->prev->next = tree->next; + if(tree->next != NULL) tree->next->prev = tree->prev; + struct tree_item * old = tree; tree = tree->next; - if(tree != NULL) { - tree->prev = old->prev; - } free(old); change++; @@ -125,6 +126,10 @@ struct online_return dfs_online(struct data * data, struct front_item * front, s /* Update left next */ left->next = right; + /* Adjust prev and next */ + if(tree->prev != NULL) tree->prev->next = left; + if(tree->next != NULL) tree->next->prev = right; + /* Update tree to left node and free old node */ struct tree_item * old = tree; tree = left; diff --git a/src/main/online.c b/src/main/online.c index ba8a94c..fb400ef 100644 --- a/src/main/online.c +++ b/src/main/online.c @@ -13,13 +13,13 @@ int main(int argc, char * argv[]){ struct front_item * front = NULL; struct online_return ret; - if(argc!=5){ + if(argc!=6){ printf("Wrong number of arguments!\n"); - printf("Example usage: %s algorithm1 algorithm2 sort_method data_file\n",argv[0]); + printf("Example usage: %s algorithm1 algorithm2 sort_method cut_pointa data_file\n", argv[0]); return 0; } - data = input(argv[4]); + data = input(argv[5]); /* Sort data */ srand(time(NULL)); @@ -29,10 +29,11 @@ int main(int argc, char * argv[]){ qsort(data->items, data->N, sizeof(struct item), cmp_items_ratio); } + printf("%d\n", atoi(argv[4])); clock_t t = clock(); /* Choose algorithm1 */ if(strcmp(argv[1], "dfs") == 0) { - ret = dfs_online(data, NULL, NULL, 20); + ret = dfs_online(data, NULL, NULL, atoi(argv[4])); } else if(strcmp(argv[1], "random_heuristic") == 0) { ret = random_heuristic_online(data, NULL, NULL); } diff --git a/src/random_heuristic.c b/src/random_heuristic.c index 0076728..529a186 100644 --- a/src/random_heuristic.c +++ b/src/random_heuristic.c @@ -9,12 +9,13 @@ struct front_item * random_heuristic(struct data * data) { struct front_item * front_last = front; struct tree_item * tree = new_tree_item(0, 0, 0, 0, NULL, NULL); long int tree_size = 1; + + /* Choose tree node randomly */ + long int position = rand() % tree_size; + struct tree_item * node = tree; + for(int i = 0; i < position; i++,node=node->next); do { - /* Choose tree node randomly */ - long int position = rand() % tree_size; - struct tree_item * node = tree; - for(int i = 0; i < position; i++,node=node->next); /* Check if node is leaf */ if(node->depth == data->N) { @@ -35,6 +36,13 @@ struct front_item * random_heuristic(struct data * data) { free(old); /* Reduce tree_size */ tree_size--; + + if(tree != NULL) { + /* Select new random node */ + position = rand() % tree_size; + node = tree; + for(int i = 0; i < position; i++,node=node->next); + } continue; } @@ -73,6 +81,13 @@ struct front_item * random_heuristic(struct data * data) { tree = left; } free(old); + + /* Choose left or right randomly for node */ + if(rand() % 2 == 0) { + node = left; + } else { + node = right; + } /* Increment tree_size */ tree_size++; @@ -87,8 +102,6 @@ struct front_item * random_heuristic(struct data * data) { } struct online_return random_heuristic_online(struct data * data, struct front_item * front, struct tree_item * tree) { - - if(front == NULL) { front = new_front_item(0, 0, NULL, NULL); } @@ -100,7 +113,7 @@ struct online_return random_heuristic_online(struct data * data, struct front_it } long int tree_size = 0; for(struct tree_item * tree_node = tree; tree_node != NULL; tree_node = tree_node->next, tree_size++); - + /* Choose tree node randomly */ long int position = rand() % tree_size; struct tree_item * node = tree; @@ -112,18 +125,12 @@ struct online_return random_heuristic_online(struct data * data, struct front_it front_last->next = new_front_item(node->values.p, node->values.w, front_last, NULL); front_last = front_last->next; - struct tree_item * old = node; - if(tree == old) { - tree = node->next; - } + if(node->prev != NULL) node->prev->next = node->next; + if(node->next != NULL) node->next->prev = node->prev; + + if(tree == node) tree = node->next; + free(node); - if(node->next != NULL) { - node->next->prev = node->prev; - } - if(node->prev != NULL) { - node->prev->next = node->next; - } - free(old); /* Reduce tree_size */ tree_size--; @@ -146,9 +153,6 @@ struct online_return random_heuristic_online(struct data * data, struct front_it node->prev, node ); - if(node->prev != NULL){ - node->prev->next = left; - } /* Make right node (do not select item) */ struct tree_item * right = new_tree_item( @@ -159,28 +163,22 @@ struct online_return random_heuristic_online(struct data * data, struct front_it left, node->next ); - if(node->next != NULL) { - node->next->prev = right; - } /* Adjust left->next to right */ left->next = right; - struct tree_item * old = node; - if(node == tree) { - tree = left; - } - free(old); + if(node->prev != NULL) node->prev->next = left; + if(node->next != NULL) node->next->prev = right; + + if(tree == node) tree = left; + free(node); /* Choose left or right randomly for node */ - if(rand() % 2 == 0) { - node = left; - } else { - node = right; - } + node = rand() % 2 == 0 ? left : right; /* Increment tree_size */ tree_size++; + } while(tree != NULL); struct online_return ret; -- cgit v1.2.3