1
\$\begingroup\$

I have implemented various single linked-list related operations in C.

The .c file contains the implementation and the .h file contains function prototypes and the following definitions:

// Various types of data
typedef enum {
    CHAR,
    INT,
    UINT,
    FLOAT,
    DOUBLE,
    ARRAY,
    LIST,
    POINTER
} info_t;

// Linked list data type
typedef struct data {
    info_t   info_type;
    union {
        char         info_char;
        int          info_int;
        unsigned     info_uint;
        float        info_float;
        double       info_double;
        struct arr  *info_array;
        struct head *info_list;
        void        *info_ptr;
    } info;
}  data_t;

#define MAX_ARR_LEN    10
// Linked list node type
typedef struct arr {
    data_t   data[MAX_ARR_LEN];
    int      len;
} array_t;

// Linked list node type
typedef struct node {
    data_t       data;
    struct node *next;
} node_t;

// Linked list header type
typedef struct head {
    node_t     *first;
    node_t     *last;
    size_t      len;
} head_t;

The following is the source code. I would appreciate some code review feedback, any kind of comment, coding style improvements, as well as time/space efficiency concerns, etc.

#include <stdio.h>
#include <string.h>
#include <inttypes.h>

#include "linked_list.h"

static void get_fmt_str(char *fmt_str, info_t data_type);

// Get a node memory 
node_t *get_node( data_t *d )
{
    node_t *retptr = NULL;
    retptr = (node_t *)malloc( sizeof(node_t) );
    if( retptr == NULL )
        return NULL;
    retptr->data = *d;
    retptr->next = NULL;
    return retptr;
}

// Free a node memory
void free_node( node_t *n )
{
    free( n );
    n = NULL;
}

// Compare two list nodes
int cmp_fn( data_t *d1, data_t *d2)
{
    assert( d1!=NULL && d2!=NULL && d1->info_type==d2->info_type );

    switch( d1->info_type ) {
        case INT:
            return d1->info.info_int - d2->info.info_int;
            break;
        default:
            break;
    }
    return 0;
}

// Init a list
void init_list( head_t *head )
{
    assert(head!=NULL);
    head->first = head->last = NULL;
    head->len = 0;
    //head->free_node = free_node;
    //head->get_node = get_node;
    //head->cmp_fn = cmp_fn;
}

// Free a list, does nto free head as it could be on stack
void free_list( head_t *head )
{
    node_t *tofree = NULL;
    char    fmt_str[2] = { 0 };

    while( head!= NULL && head->len > 0 ) {
        tofree = head->first;
        head->first = head->first->next;
        head->len--;
        get_fmt_str( fmt_str, tofree->data.info_type);
        if (fmt_str[0] == 1) {
            free_list(tofree->data.info.info_list);
            free_node(tofree);
        }
        //else if( fmt_str[0] == 2 ) 
        //    free_array(temp_ptr->data);
        //else if( fmt_str[0] == 3 ) 
        //    free_ptr(temp_ptr->data);
        else {
            free_node(tofree);
        }
    }
}

// Check if list is empty
bool is_empty( head_t *head)
{
    return head->len == 0;
}

#define MAX_LIST_LEN   1000000
// Check if list is full
bool is_full( head_t *head)
{
    return head->len == MAX_LIST_LEN;
}

// Get length of list
size_t get_len( head_t *head )
{
    return head->len;
}

// Push a node = Insert at front
void insert_atfront( head_t *head, node_t *anode )
{
    assert( head != NULL );

    if( anode == NULL )
        return;

    anode->next = head->first;
    head->first = anode;
    head->len++;
    if( head->last == NULL )
        head->last = anode;

}

// Enqueue a node from rear
void insert_atend( head_t *head, node_t *anode )
{
    assert( head != NULL );

    if( anode == NULL )
        return;

    if( head->last == NULL )
        head->first = anode;
    else 
        head->last->next = anode;
    anode->next = NULL;
    head->last = anode;
    head->len++;
}

// Pop a node = Delete from front
// return NULL if list is empty
node_t *remove_fromfront( head_t *head )
{
    node_t *retptr = NULL;
    assert( head != NULL );

    retptr = head->first;
    if( head->first != NULL ) {
        head->first = head->first->next;
        head->len--;
    }
    if( head->first == NULL ) 
        head->last = NULL;

    return retptr;
}

// Dequeue a node = Delete from end
// return NULL if list is empty
node_t *remove_fromend( head_t *head )
{
    node_t *retptr = NULL;
    node_t *prevptr = NULL;
    assert( head != NULL );

    retptr = head->first;
    while( retptr != head->last ) {
        prevptr = retptr;
        retptr = retptr->next;
    }
    head->last = prevptr;
    if( prevptr != NULL ) {
        prevptr->next = NULL;
        head->len--;
    }

    return retptr;
}

// Insert a node at pos p (1-based)
bool insert_at( head_t *head, size_t p, node_t *anode )
{
    node_t *temp = NULL;
    assert( head != NULL );

    if( anode == NULL )
        return true;

    if( p == 0 ) 
        return false;
    else if( p == 1 && head->len == 0 ) {
        // insert at 1st node in an empty list
        head->last = head->first = anode;
        anode->next = NULL;
        head->len++;
    }
    else if( p == head->len ) {
        // insert at the end
        if( head->last == NULL )
            head->first = anode;
        else 
            head->last->next = anode;
        head->last = anode;
        anode->next = NULL;
        head->len++;
    }
    else if( p > head->len ) 
        return false;
    else {
        // insert in the middle
        temp = head->first;
        while( --p ) {
            temp = temp->next;
        }
        // need to insert between temp and temp->next
        anode->next = temp->next;
        temp->next = anode;
        head->len++;
    }
    return true;
}

// Remove a node at pos p (1-based)
node_t *remove_at( head_t *head, size_t p )
{
    node_t *retptr = NULL, *temp_ptr=NULL;

    assert( head != NULL );

    if( p == 0 ) 
        return NULL;
    else if( p == 1 && head->len == 1 ) {
        // remove 1st node of a one node list 
        retptr = head->first;
        head->last = head->first = NULL;
        retptr->next = NULL;
    }
    else if( p == head->len ) {
        // remove the last node
        retptr = head->first;
        while( --p > 1 ) {
            retptr = retptr->next;
        }
        head->last = retptr;
        retptr = retptr->next;
        retptr->next = NULL;
    }
    else if( p > head->len ) 
        return NULL;
    else {
        // remove from the middle
        retptr = head->first;
        while( --p > 1 ) {
            retptr = retptr->next;
        }
        temp_ptr = retptr->next;
        retptr->next = retptr->next->next;
        retptr = temp_ptr;
        temp_ptr->next = NULL;
    }
    head->len--;
    return retptr;
}

// Delete a node at pos p (1-based)
void delete_at( head_t *head, size_t p )
{
    node_t *ret_ptr = NULL;
    ret_ptr = remove_at(head, p);
    if( ret_ptr!= NULL )
        head->len--;
    free_node(ret_ptr);
}

// Find node at pos p (1-based)
node_t *find_at( head_t *head, size_t p )
{
    node_t *retptr = NULL;
    assert( head != NULL );

    if( p == 0 || p > head->len+1 ) 
        return NULL;
    else {
        retptr = head->first;
        while( --p ) {
            retptr = retptr->next;
        }
    }

    return retptr;
}

// Check data of a node at pos p (1-based)
data_t *check_at( head_t *head, size_t p )
{
    node_t *retptr = NULL;
    retptr = find_at( head, p);
    if( retptr == NULL ) 
        return NULL;
    return &retptr->data;
}

// Update data of a node at pos p (1-based)
bool update_at( head_t *head, size_t p, data_t d )
{
    node_t *retptr = NULL;

    retptr = find_at( head, p);
    if( retptr == NULL ) 
        return false;

    retptr->data = d;
    return true;
}

// Find the first position (1-based) of a given data item in list
// search for given node between [start,stop) stop not included
// e.g. to search whole list, pass start=1, and stop=head->len+1
bool find_pos( head_t *head, data_t *data_ptr, size_t *pos, size_t start, size_t stop )
{
    size_t  index = 1;
    node_t *temp = NULL;
    int     retval = 0;

    assert( head!=NULL && data_ptr!=NULL && pos!=NULL );

    temp = head->first;
    if( start==0 || stop==0 || start > head->len || stop > head->len+1 || start >= stop ) {
        printf("Inconsistent start=%"PRIu64" and stop=%"PRIu64" [list len=%"PRIu64"]",
                (unsigned long long)start,(unsigned long long)stop,(unsigned long long)head->len);
        return false;
    }
    // return false for empty list as well
    if(  temp == NULL )
        return false;

    // skip all nodes before start pos
    while( index < start ) {
        temp = temp->next;
        index++;
    }

    // search for given node between [start,stop) stop not included
    while( index <stop ) {
        retval = cmp_fn( &temp->data, data_ptr);
        if( retval == 0 ) {
            *pos = index;
            return true;
        }
        temp = temp->next;
        index++;
    }
    return false;
}

// Find and delete the first occurences of a data item in list
bool find_delete( head_t *head, data_t *data_ptr )
{
    size_t pos = 0;
    bool   retval = true;
    retval = find_pos(head, data_ptr, &pos, 0, head->len);
    if( retval )
        delete_at(head, pos);
    return retval;
}

// Find and delete all occurences of a data item in list
size_t find_delete_all( head_t *head, data_t *data_ptr )
{
    size_t pos = 0;
    bool   retval = true;
    size_t count = 0;
    while( retval ) {
        retval = find_pos(head, data_ptr, &pos, 0, head->len);
        if( retval ) {
            delete_at(head, pos);
            count++;
        }
    }
    return count;
}

// Count all occurences of a data item in list
size_t count_all( head_t *head, data_t *data_ptr )
{
    node_t *inode = NULL;
    int     retval = 0;
    size_t  count = 0;

    for( inode = head->first; inode!=NULL; inode=inode->next ) {
        retval = cmp_fn( &inode->data, data_ptr);
        if( retval == 0 )
            count++;
    }

    return count;
}

static void get_fmt_str( char *fmt_str, info_t data_type )
{
    switch( data_type ) {
    case CHAR: fmt_str[0] = 'c';
        break;
    case INT: fmt_str[0] = 'd';
        break; 
    case UINT: fmt_str[0] = 'u';
        break;
    case FLOAT: fmt_str[0] = 'f';
        break;
    case DOUBLE: fmt_str[0] = 'D';
        break;
    case LIST: fmt_str[0] = 1;
        break;
    case ARRAY: fmt_str[0] = 2;
        break;
    case POINTER: fmt_str[0] = 3;
        break;
    }
}

// Print a list
void print_list( head_t *head )
{
    unsigned    count = 0;
    node_t     *temp_ptr;
    char        fmt_str[2] = {0};

    // traverse the list from the list head
    if( head == NULL || head->len == 0 ) {
        printf("Empty list.\n");
        return;
    }
    else {
        temp_ptr = head->first;
    }

    printf("*-- ");
    while( count < head->len ) {
        get_fmt_str( fmt_str, temp_ptr->data.info_type);
        if( fmt_str[0] == 1 ) 
            print_list(temp_ptr->data.info.info_list);
        //else if( fmt_str[0] == 2 ) 
        //    print_array(temp_ptr->data);
        //else if( fmt_str[0] == 3 ) 
        //    print_ptr(temp_ptr->data);
        else if( fmt_str[0] == 'c')
            printf("%c, ", temp_ptr->data.info.info_char);
        else if( fmt_str[0] == 'd')
            printf("%d, ", temp_ptr->data.info.info_int);
        else if( fmt_str[0] == 'u')
            printf("%u, ", temp_ptr->data.info.info_uint);
        else if( fmt_str[0] == 'f')
            printf("%f, ", temp_ptr->data.info.info_float);
        else if( fmt_str[0] == 'D')
            printf("%f, ", temp_ptr->data.info.info_double);
        temp_ptr = temp_ptr->next;
        count++;
    }
    if( temp_ptr == NULL )
        printf("NULL--*\n");
    else
        printf("@ \n");
}

// Slice a list
void slice_list( head_t *head )
{
    return;
}

// Reverse a linked list using delete and insert
void reverse_list( head_t *head )
{
    head_t temp_head;
    node_t *temp_node = NULL;

    assert( head!= NULL );

    temp_head.first = NULL;
    temp_head.last = NULL;
    temp_head.len = 0;

    while( (temp_node = remove_fromfront( head )) != NULL ) {
        insert_atfront( &temp_head, temp_node );
    }
    head->first = temp_head.first;
    head->last = temp_head.last;
    head->len = temp_head.len;

}

// Reverse a linked list, iteratively
void reverse_list_iter( head_t *head )
{
    node_t *prevNode=NULL, *currNode=NULL, *nextNode=NULL;

    assert(head!=NULL);
    // return if nothing to reverse (list is empty or only one elemeent)
    if( head->first==NULL || head->first == head->last ) return;

    head->last = head->first;
    currNode = head->first;
    nextNode = currNode->next;
    currNode->next = prevNode;
    while(nextNode!=NULL) {
        head->first = nextNode;
        prevNode = currNode;
        currNode = nextNode;
        nextNode = currNode->next;
        currNode->next = prevNode;
    }

}

// Reverse a linked list, recursively
void reverse_list_recur( head_t *head )
{
    node_t *first_node=NULL;

    assert(head!=NULL);
    // return if nothing to reverse (list is empty or only one elemeent)
    if( head->first==NULL || head->first == head->last ) return;

    first_node = head->first;
    head->first = head->first->next;
    reverse_list_recur( head );
    head->last = head->last->next = first_node;
    first_node->next = NULL;

}

// Concatanate two lists: List1 = List1+List2, no separate header for list2 affter concat
void cat_list( head_t *head1, head_t *head2)
{
    assert( head1 != NULL || head2 != NULL );
    if( head2 == NULL || head2->last == NULL )
        return;
    else if( head1 == NULL || head1->last == NULL ) {
        *head1 = *head2;
        return;
    }
    head1->last->next = head2->first;
    head1->last = head2->last;
    head1->len += head2->len;
    init_list( head2 );
}

// Copy a list
head_t *copy_list( head_t *head )
{
    head_t *new_head = NULL;
    node_t *inode = NULL, *new_node = NULL, *prev_node = NULL;

    assert(head!=NULL);
    new_head = (head_t *)malloc(sizeof(head_t));
    if( new_head == NULL ) {
        printf("ERR1:Out of memory\n");
        return NULL;
    }
    memcpy(new_head, head, sizeof(head_t));

    for( inode = head->first; inode != NULL; inode = inode->next ) {
        new_node = (node_t *)malloc(sizeof(node_t));
        if( new_node == NULL ) {
            printf("ERR2:Out of memory\n");
            return NULL;
        }
        if( inode == head->first )
            new_head->first = new_node;
        else
            prev_node->next = new_node;
        memcpy(&new_node->data, &inode->data, sizeof(data_t));
        new_node->next = NULL;
        prev_node = new_node;
    }

    return new_head;
}

// Copy a list, fast
head_t *copy_list_fast( head_t *head )
{
    head_t *new_head = NULL;
    node_t *inode = NULL;
    node_t *bulk_list = NULL;
    int     i = 0;

    assert(head!=NULL);
    new_head = (head_t *)malloc(sizeof(head_t));
    if( new_head == NULL ) {
        printf("ERR1:Out of memory\n");
        return NULL;
    }
    memcpy(new_head, head, sizeof(head_t));

    bulk_list = (node_t *)malloc(head->len * sizeof(node_t));
    if( bulk_list == NULL ) {
        printf("ERR2:Out of memory\n");
        return NULL;
    }
    new_head->first = bulk_list;

    i = 0;
    for( inode = head->first; inode != NULL; inode = inode->next ) {
        bulk_list[i] = *inode;
        if( i<head->len-1 ) 
            bulk_list[i].next = &bulk_list[i+1];
        else
            bulk_list[i].next = NULL;
        i++;
    }
    new_head->last = &bulk_list[i-1];
    new_head->len = i;
    return new_head;
}


// Detect a cycle in a list
bool detect_cycle( head_t *head, size_t *start_pos, size_t *cyc_len )
{
    node_t *slow=NULL, *fast=NULL;
    assert( head!= NULL && start_pos !=NULL && cyc_len!=NULL );
    slow = fast = head->first;

    // detect cycle
    do {
        slow = slow->next;
        fast = fast->next;
        if( fast==NULL ) 
            return false;
        else
            fast = fast->next;
        if( fast==NULL ) 
            return false;
    } while( slow!=fast );

    // find start position of cycle node
    *start_pos = 1;
    slow = head->first;
    do {
        slow = slow->next;
        fast = fast->next;
        (*start_pos)++;
    } while( slow!=fast );

    // find cycle len
    *cyc_len = 0;
    do {
        fast = fast->next;
        (*cyc_len)++;
    } while( slow!=fast );

    return true;
}

// Find minimum value in a list
node_t *find_min( head_t *head)
{
    node_t *inode=NULL, *min_node=NULL;
    int      retval = 0;
    for( inode=min_node=head->first; inode!=NULL; inode=inode->next ) {
        retval = cmp_fn( &inode->data, &min_node->data);
        if( retval < 0 )
            min_node = inode;
    }
    return min_node;
}

// Find maximum value in a list
node_t *find_max( head_t *head)
{
    node_t *inode=NULL, *max_node=NULL;
    int      retval = 0;

    assert( head!= NULL );

    for( inode=max_node=head->first; inode!=NULL; inode=inode->next ) {
        retval = cmp_fn( &inode->data, &max_node->data);
        if( retval > 0 )
            max_node = inode;
    }
    return max_node;
}

// Place a node in a list in sorted order (inc order=0, dec order = 1)
void insert_inorder( head_t *head, node_t *anode, int order )
{
    node_t *inode=NULL, *prevnode=NULL, *temp=NULL;
    int     retval = 0;
    bool    cmp_result = false;

    assert( head!= NULL );
    if( anode == NULL )
        return;

    for( inode=head->first; inode!=NULL; inode=inode->next ) {
        retval = cmp_fn( &anode->data, &inode->data );
        cmp_result = (order==0)? (retval<0): (retval>0);
        if( cmp_result )
            break;
        prevnode = inode;
    }
    // insert at front (including into an empty list)
    if( prevnode == NULL ) {
        if( head->first == NULL ) 
            head->last = anode;
        temp = head->first;
        head->first = anode;
        anode->next = temp;
    }
    // insert after prevnode (including at end)
    else {
        prevnode->next = anode;
        anode->next = inode;
        if( inode == NULL )
            head->last = anode;
    }
    head->len++;
}

// Sort a list using insertion sort
void insert_sort_list( head_t *head, int order )
{
    // pop items from given list and insert in order in a new list
    head_t   new_head;
    node_t  *temp_node = NULL;

    assert(head!=NULL);
    if( head->first == NULL || head->first->next == NULL ) 
        return;

    init_list( &new_head );
    while( (temp_node=remove_fromfront(head)) != NULL ) {
        insert_inorder( &new_head, temp_node, order);
    }
    head->first = new_head.first;
    head->last = new_head.last;
    head->len = new_head.len;
}

// Split an input list into two sublists with odd and even pos nodes
void split_alternate( head_t *head_in, head_t *head_o, head_t *head_e) 
{
    node_t   *move_ptr = NULL;
    head_t   *head_to = NULL;
    assert(head_in!=NULL && head_o!=NULL && head_e!=NULL);

    head_to = head_o;
    while( (move_ptr = remove_fromfront( head_in )) != NULL ) {
        insert_atend( head_to, move_ptr );
        if( head_to == head_o )
            head_to = head_e;
        else
            head_to = head_o;
    }
}

// Break an input list into two sublists with first half and second half
void split_list_half( head_t *head_in, head_t *head_f, head_t *head_b) 
{
    node_t *slow=NULL, *fast=NULL;
    assert(head_in!=NULL && head_f!=NULL && head_b!=NULL);

    init_list(head_f);
    init_list(head_b);

    slow = head_in->first;
    if( slow==NULL ) { // empty list
        return;
    }
    else if( slow->next  == NULL ) { // one element list
        head_f->first = head_f->last = slow;
        head_f->len = 1;
        return;
    }

    fast = slow->next;
    head_f->len = 1;
    do {
        fast = fast->next;
        head_b->len = head_f->len;
        if( fast==NULL ) {
            break; // even number of nodes
        }
        else { 
            slow = slow->next;
            head_f->len++;
            fast = fast->next; 
        }
    } while( fast!=NULL );

    // slow points to the last node of the front half
    if( slow!=NULL ) {
        head_b->first = slow->next;
        slow->next = NULL;
    }
    head_b->last = head_in->last;
    head_f->first = head_in->first;
    head_f->last = slow;
    init_list(head_in);

}

// Merge two lists into one list by taking nodes from eahc list alternatively
void merge_list_alternate( head_t *head1, head_t *head2, head_t *head_out)
{
    node_t   *move_ptr = NULL;
    head_t   *head_from = NULL;
    assert(head_out!=NULL && head1!=NULL && head2!=NULL);

    head_from = head1;
    while( (move_ptr = remove_fromfront( head_from )) != NULL ) {
        insert_atend( head_out, move_ptr );
        if( head_from == head1 )
            head_from = head2;
        else
            head_from = head1;
    }
    if( head_from == head1 )
        head_from = head2;
    else
        head_from = head1;
    while( (move_ptr = remove_fromfront( head_from )) != NULL ) {
        insert_atend( head_out, move_ptr );
    }
}

// Compare first node of list1 with the first node of list 2 and return ptr to lesser/bigger node
node_t *compare_node( head_t *head1, head_t *head2, int order) 
{
    data_t   *data1=NULL, *data2=NULL;
    int       retval = 0;
    bool      cmp_result = false;
    node_t   *retnode = NULL;
    head_t   *head_from=NULL;

    assert(head1!=NULL && head2!=NULL);

    data1 = check_at( head1, 1 );
    data2 = check_at( head2, 1 );
    if( data1!=NULL && data2!=NULL ) {
        retval = cmp_fn( data1, data2 );
        cmp_result = (order==0)? (retval<=0) : (retval>=0);
        head_from = cmp_result? head1: head2;
    }
    else if( data1==NULL ) 
        head_from = head2;
    else
        head_from = head1;

    retnode = remove_fromfront( head_from );

    return retnode;

}

// Merge two ordered list into one ordered list
void merge_list_inorder( head_t *head1, head_t *head2, head_t *head_out, int order)
{
    node_t   *move_ptr = NULL;

    assert(head1!=NULL && head2!=NULL);
    init_list( head_out );

    while( head1->first!=NULL && head2->first!=NULL ) {
        move_ptr = compare_node( head1, head2, order );
        insert_atend( head_out, move_ptr );
    }
    if( head1->first==NULL )
        cat_list( head_out, head2 );
    else
        cat_list( head_out, head1 );
}

// Sort a list using merge sort, using recursion
void merge_sort_list( head_t *head, int order )
{
    head_t head_left, head_right;
    assert( head!=NULL );
    if( head->first == NULL )
        return;
    if( head->first == head->last )
        return;

    init_list( &head_left );
    init_list( &head_right );

    split_list_half( head, &head_left, &head_right );

    merge_sort_list( &head_left, order );
    merge_sort_list( &head_right, order );
    merge_list_inorder( &head_left, &head_right, head, order );

}

// Check if given list is sorted or not
bool is_list_sorted( head_t *head, int order ) 
{
    node_t *inode=NULL, *prevnode=NULL;
    int     retval = 0;
    bool    cmp_result = false;

    assert( head!=NULL );

    if( head->first == NULL || head->first == head->last )
        return true;

    prevnode = head->first;
    for( inode=prevnode->next; inode!=NULL; inode=inode->next ) {
        retval = cmp_fn( &prevnode->data, &inode->data );
        cmp_result = (order==0)? (retval>0):(retval<0);
        if( cmp_result ) 
            return false;
        prevnode = inode;
    }
    return true;
}

// Remove duplicate nodes in a sorted list
void unique_list( head_t *head, head_t *head_dup )
{
    node_t *prev_node=NULL, *inode=NULL, *dup_node=NULL;
    size_t  pos=0;
    int     retval = 0;

    assert( head!=NULL && head_dup!=NULL );
    if( head->first == NULL )
        return;
    if( head->first == head->last )
        return;
    init_list( head_dup );
    prev_node = head->first;
    inode = prev_node->next; 
    pos = 2;
    while( inode!=NULL ) {
        retval = cmp_fn( &inode->data, &prev_node->data );
        if( retval==0 ) { //inode same as prev_node
            dup_node = remove_at( head, pos);
            insert_atend( head_dup, dup_node );
            inode = prev_node->next;
        }
        else {
            prev_node = inode;
            inode = inode->next;
            pos++;
        }
    }

}

// Union and Intersection of two sorted lists, results are sorted & unique as well
size_t union_intersect_list( head_t *head1, head_t *head2, head_t *head_u, head_t *head_i, int order )
{
    size_t   com_count = 0; // number of common nodes
    head_t  *head1_copy=NULL, *head2_copy=NULL, *head1_dup=NULL, *head2_dup=NULL;
    node_t  *move_ptr=NULL, *prev_move_ptr=NULL;
    bool     match = false;
    int      retval = 0;

    assert( head1!=NULL && head2!=NULL && head_u!=NULL && head_i!=NULL );

    // create a copy of the two lists so that they are not modifies
    head1_copy = (head_t *)malloc(sizeof(head_t));
    head1_dup = (head_t *)malloc(sizeof(head_t));
    head2_copy = (head_t *)malloc(sizeof(head_t));
    head2_dup = (head_t *)malloc(sizeof(head_t));
    // init all list headers for a clean start
    init_list( head1_copy );
    init_list( head1_dup );
    init_list( head2_copy );
    init_list( head2_dup );
    init_list( head_u );
    init_list( head_i );

    // remove duplicates as they would not be there in union or intersect outputs
    head1_copy = copy_list( head1 );
    head2_copy = copy_list( head2 );
    unique_list( head1_copy, head1_dup );
    unique_list( head2_copy, head2_dup );
    // free memory not needed anymore
    free_list(head1_dup);
    free_list(head2_dup);
    free(head1_dup);
    free(head2_dup);

    // take care of empty lists as inputs
    if( head1_copy->first==NULL && head2_copy->first==NULL ) {
        free( head1_copy );
        free( head2_copy );
        return com_count;
    }

    // compare the front nodes of two lists and insert them in 
    // union list if they are not matching with prev inserted node
    // else insert it to the intersection list
    move_ptr = compare_node( head1_copy, head2_copy, order );
    insert_atend( head_u, move_ptr );
    prev_move_ptr = move_ptr;

    while( head1_copy->first!=NULL || head2_copy->first!=NULL ) {
        move_ptr = compare_node( head1_copy, head2_copy, order );
        retval = cmp_fn( &move_ptr->data, &prev_move_ptr->data);
        if( retval == 0 ) {
            if( match == false ) {
                insert_atend( head_i, move_ptr );
                match = true;
            }
            com_count++;
        }
        else if( retval != 0 ) {
            insert_atend( head_u, move_ptr );
            match = false;
            prev_move_ptr = move_ptr;
        }
    }

    free( head1_copy );
    free( head2_copy );
    return com_count;

}
\$\endgroup\$
0
2
\$\begingroup\$
  1. Broken code &max_node->data is &NULL->data. Undefined behavior to compute the address of members from a invalid pointer.

    node_t *inode=NULL, *max_node=NULL;
    for( inode=max_node=head->first; inode!=NULL; inode=inode->next ) {
      retval = cmp_fn( &inode->data, &max_node->data);
    
  2. Heavy pollution of name space. CHAR, INT, etc. can very well collide with other code. Consider names less likely to collide.

    // typedef enum {
    //  CHAR,
    //  INT,
    /// UINT,
    typedef enum {
      VYLL_CHAR,
      VYLL_INT,
      VYLL_UINT,
    
  3. Array sizing and indexing are best handled with type size_t. int may be insufficient for large applications. Code did use size_t in head_t

    typedef struct arr {
        data_t   data[MAX_ARR_LEN];
        // int      len;
        size_t      len;
    } array_t;
    
  4. As the header files used size_t, #include <stddef.h>, and maybe others, should be in that header file. Usage of a header file should not oblige .c code to do the including for it.

  5. The .c file should your "linked_list.h" first to insure it does not require prior includes.

    #include "linked_list.h" 
    #include <stdio.h>
    #include <string.h>
    #include <inttypes.h>
    //#include "linked_list.h"
    
  6. No need to assign twice in a row. Once is enoough

    // node_t *retptr = NULL;
    // retptr = (node_t *)malloc( sizeof(node_t) );
    node_t *retptr = (node_t *)malloc( sizeof(node_t) );
    
  7. Cast not needed.

    node_t *retptr = malloc( sizeof(node_t) );
    
  8. Better to determine size by the referenced variable than the type. Easier to code correctly, review and maintain.

    node_t *retptr = malloc(sizeof *retptr);
    head1_copy = malloc(sizeof *head1_copy);
    
  9. Compare of int unnecessarily risks int overflow which is undefined behavior and limits useful range. Instead return 0,1,-1

    return d1->info.info_int - d2->info.info_int;
    return (d1->info.info_int > d2->info.info_int) - 
        (d1->info.info_int < d2->info.info_int);
    
  10. With functions that do not alter referenced data, use const. This conveys functions intentions, allows for wider use and allows for some optimizations.

    // int cmp_fn( data_t *d1, data_t *d2)
    int cmp_fn(const data_t *d1, const data_t *d2)
    
  11. bool used with prior #include <stdbool.h>. This (and other code) hints OP might be using a C++ compiler and not a C one.

  12. get_fmt_str() is amiss in that it does not insure a null character at the end of the fmt[]. Add fmt_str[1] = '\0';

  13. Rather than populate fmt_str[], better to return the format string.

    // static void get_fmt_str( char *fmt_str, info_t data_type ) static const char *get_fmt_str(info_t data_type) { switch( data_type ) { case CHAR: return "c"; case INT: return "d"; ...

  14. Loose use of function names and types. In a large program, these names are not distinctive nor do they imply a commonality of use. is_empty(), array_t, cmp_fn(). Instead I'd expect a naming convention like vyll_is_empty(), vyll_array_t, vyll_cmp_fn().

14 Missing #include <assert.h>

  1. Unclear why MAX_LIST_LEN is in the .C file and not the .h. No need to keep secret from other users.

  2. Recommend to keep variable closer to their use

    // int     retval = 0;
    ...
    for( inode=prevnode->next; inode!=NULL; inode=inode->next ) {
      // retval = cmp_fn( &prevnode->data, &inode->data );
      int retval = cmp_fn( &prevnode->data, &inode->data );
    

  1. Advanced: first and last are not needed - so save space. last is enough. Could use last only and have it point to the first node. End of list then detected when n->next = last->next. This re-structures much of code. This is very useful when an application may have many empty lists.
\$\endgroup\$
4
  • \$\begingroup\$ Thanks a ton! #1: yes, need to make sure head->first is not NULL #2, #3. agree, i will change them. #4. stddef was included via linked_list.h that is why it is not in .c #5, #6, #7, #8, #9, #10. make sense, will update the code #11. using C compiler, stdbool.h is included in linked_list.h #12. agree. \$\endgroup\$ – Vikas Yadav Nov 18 '17 at 21:02
  • \$\begingroup\$ contd. #13. get_fmt_str also returns non-standard values if data type is list or array or a pointer, so returning standard format string will not work. #14. ok #14. in linked_list.h i have '#ifdef DEBUGOK #define assert(CONDITION) \ if (CONDITION) { } else { \ printf ("Assertion `%s' failed.", #CONDITION); \ exit(-1); \ } #else #define assert(CONDITION) #endif' \$\endgroup\$ – Vikas Yadav Nov 18 '17 at 21:06
  • \$\begingroup\$ #20. agree. one is used most of the time. i think last is only used to help in inserting at end and in concat two list. \$\endgroup\$ – Vikas Yadav Nov 18 '17 at 21:07
  • \$\begingroup\$ #15. moved #define to header file #16. ok got it.. will try to optimize as much as possible. \$\endgroup\$ – Vikas Yadav Nov 18 '17 at 21:20
0
\$\begingroup\$
node_t *retptr = NULL;
retptr = (node_t *)malloc( sizeof(node_t) );

Why not just node_t retptr = malloc( sizeof(node_t) );

In free_node() setting n = NULL does nothing because n is just local to the function. Whatever calls it still has a pointer to memory that has just been freed. In fact as a reviewer it "pricks my senses" and makes me wonder if you understand pointers - so I'd spend more time deeply reviewing because I'm now suspicious.

int cmp_fn() is using assert to check things that really don't belong in an assert. It should return "not match" in most of those conditions.

free_list() Why on earth would you make this recursive?

Nothing stops me inserting even after the list is full. Therefore return head->len == MAX_LIST_LEN; should really be return head->len >= MAX_LIST_LEN; otherwise it is misleading.

If you really want to remove from the front and the end, consider a doubly linked list? (Otherwise what is the real reason of keeping the end pointer at all?)

insert_at, remove_at etc can all be simplified by using find_at to locate the correct node (which may be the one before the one you need to play with. Why isn't insert_atfront just a call to insert_at(head, 0, anode)? I'm sure there are other similar cases.

I stopped here - in general my worst complain is too much assert - if you compile not in DEBUG mode behavior will be different (e.g. no checking for NULLs)

\$\endgroup\$
8
  • \$\begingroup\$ If you found them useful an upvote is the traditional way to say thanks. \$\endgroup\$ – John3136 Nov 17 '17 at 3:25
  • \$\begingroup\$ 1. The reason I had n=NULL in free_node is to let the program crash if it accesses freed memory without reallocation, isnt that safer than letting wrong memory used and corrupted due to developers mistake? 2. The recursive call is only needed for the case when list is a list of lists, in this case each node is of type list and I would need to call free_list instead of just free. Am I still missing something? \$\endgroup\$ – Vikas Yadav Nov 17 '17 at 3:38
  • \$\begingroup\$ i did upvote but it does now show up. \$\endgroup\$ – Vikas Yadav Nov 17 '17 at 3:39
  • \$\begingroup\$ n is local to the function so as i said, it does nothing. \$\endgroup\$ – John3136 Nov 17 '17 at 3:41
  • \$\begingroup\$ oh i see :) i missed that part (n is local).. what i want to do is the main var which is pointing to that mem in main code should be set to null. Thanks! \$\endgroup\$ – Vikas Yadav Nov 17 '17 at 5:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.