typedef struct list_node_tag {
// Private members for list.c only
Data *data_ptr;
struct list_node_tag *prev;
struct list_node_tag *next;
} ListNode;
typedef struct list_tag {
// Private members for list.c only
ListNode *head;
ListNode *tail;
int current_list_size;
int list_sorted_state;
// Private method for list.c only
int (*comp_proc)(const Data *, const Data
*);
void (*data_clean)(Data *);
} List;
and I have a program that needs to perform merge sort in
addition to other forms of sort to perform and analysis on the
different run times. My merge sort function works perfectly when I
used my small test case, and it continues to give a result until I
get to a list of 400,000 where it seg faults. Valgrind also works
for the smaller lists but times out when I get to the larger ones
it seg faults and tell me nothing about it:
- I Have The Following Structure Typedef Struct List Node Tag Private Members For List C Only Data Data Ptr 1 (122.27 KiB) Viewed 56 times
/* Sorting the list via the merge sort algorithm
*
* L: pointer to list-of-interest.
* sort_order: 1 sort list in descending order 2 sort in
ascending order
*/
void list_merge_sort(List** L, int sort_order)
{
List* original_list = (*L);
/* check for invalid conditions */
if (original_list->current_list_size > 2)
{
/* recursive sort and
merge */
(*L)->head =
recursive_merge_sort((*L)->head, sort_order);
return;
}
else {
return;
}
}
/* function to split a given list in two
*
* node: pointer to the head of the list to be split
*
* RETURNS pointer to the head of the second list
*/
ListNode* split_lists(ListNode* node)
{
ListNode* slow_list = node;
ListNode* fast_list = node;
ListNode* temp_node = NULL;
/* move fast_list by two nodes and slow list
by one */
while (fast_list->next &&
fast_list->next->next) {
fast_list =
fast_list->next->next;
slow_list =
slow_list->next;
}
temp_node = slow_list->next;
slow_list->next = NULL;
return temp_node;
}
/* function to merge two lists together
*
* node_one: pointer to the first node of the first list
* node_two: pointer to the first node of the second
list
*
* RETURNS pointer to the head of the merged list
*/
ListNode* merge_lists(ListNode* node_one, ListNode* node_two, int
sort_order)
{
/* if either list is empty */
if (!node_one) {
return node_two;
}
if (!node_two) {
return node_one;
}
/* determine sort order */
if (sort_order == 1) {
/* DESCENDING order
*/
if
(node_one->data_ptr->task_id >
node_two->data_ptr->task_id) {
node_one->next = merge_lists(node_one->next, node_two,
sort_order);
node_one->next->prev = node_one;
node_one->prev = NULL;
return node_one;
}
else {
node_two->next = merge_lists(node_one, node_two->next,
sort_order);
node_two->next->prev = node_two;
node_two->prev = NULL;
return node_two;
}
}
else {
/* ASCENDING order
*/
if
(node_one->data_ptr->task_id <
node_two->data_ptr->task_id) {
node_one->next = merge_lists(node_one->next, node_two,
sort_order);
node_one->next->prev = node_one;
node_one->prev = NULL;
return node_one;
}
else {
node_two->next = merge_lists(node_one, node_two->next,
sort_order);
node_two->next->prev = node_two;
node_two->prev = NULL;
return node_two;
}
}
}
/* helper function to perform a recursive merge sort on the
given list
*
* node: the head node
*
* RETURNS pointer to the head of the merged list
*/
ListNode* recursive_merge_sort(ListNode* node, int
sort_order)
{
if (!node || !node->next) {
return node;
}
ListNode* second_list = split_lists(node);
/* recure left and right */
node = recursive_merge_sort(node,
sort_order);
second_list = recursive_merge_sort(second_list,
sort_order);
return merge_lists(node, second_list,
sort_order);
}
Why does it keep seg faulting and why only at the larger
lists?
- == == - -=15163== Memcheck, a memory error detector =15163== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al. =15163== Using Valgrind-3.15.0 and Lib VEX; rerun with -h for copyright info -=15163== Command: /geninput 400000 1 52 =15163 -=15163 =15163= HEAP SUMMARY: =15163= in use at exit: O bytes in 0 blocks -=15163= total heap usage: 1 allocs, 1 frees, 4,096 bytes allocated =15163= =15163= All heap blocks were freed no leaks are possible =15163= ==15163= For lists of detected and suppressed errors, rerun with: -S ==15163== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0) Segmentation fault (core dumped) == == == - - -