C: Comparing Strings

Question

I am using the below code to add nodes to a double linked list and arrange them such that they are in alphabetical order according to their word. The nodes consist of char * word, struct NODES * prev, and struct NODES * next. I am running into an issue when, after reading file testing a, the list looks like NULL <- a <-> file <-> testing -> NULL that adding a node containing word = c it places c before a instead of between a and file. The function prints "Add: Placing c before list head c" and seems to be evaluating c < a. But even with that evaluation being incorrect I do not know how it is replacing a before doing any node manipulation at all. If anyone know what could cause this issue I'd appreciate the advice. P.S. incoming NODES * arg is always in the form of arg -> next == NULL; arg -> prev == NULL; arg -> word != NULL; but list can have all fields NULL if no nodes have been added yet, list -> prev should always be NULL at the time the function is called and when the function terminates.

int addToList(struct NODES * list, struct NODES * arg){
fprintf(stderr,"Add: Adding %s\n", arg->word);
if(list->word == NULL){
    list->word = (char *)malloc(strlen(arg->word));
    strcpy(list->word, arg->word);
    list->next = NULL;
    list->prev = NULL;
    fprintf(stderr,"Add: Head %s\n", list->word);
    return 2;
}
struct NODES * abc = list;
while(abc->word != NULL){
    if(strcmp(abc->word, arg->word)<0){
        fprintf(stderr, "abc %s < arg %s", abc->word, arg->word);
        if (abc->next != NULL)
            abc = abc->next;
        else{
            abc->next = malloc(sizeof(NODE));
            abc->next->prev = abc;
            abc = abc->next;
            abc->next = NULL;
            abc->word = NULL;
        }
    }
    else if(abc == list){
        fprintf(stderr, "Add: Placing %s before list head %s\n", arg->word, list->word);
        arg->next = list;
        list->prev = arg;
        arg->prev = NULL;
        list = arg;
        fprintf(stderr, "Add: Placed %s before %s\n", list->word, list->next->word);
        return 3;
    }
    else{
        fprintf(stderr, "Add: Placing %s between %s and %s\n", arg->word, abc->word, abc->next->word);
        arg->next = abc;
        arg->prev = abc->prev;
        if(abc->prev != NULL)
            abc->prev->next = arg;
        abc->prev = arg;
        fprintf(stderr, "Added %s after %s and before %s\n", arg->word, arg->prev, arg->next->word);
        return 1;
    }
}
abc->word = (char *)malloc(strlen(arg->word));
strcpy(abc->word, arg->word);
fprintf(stderr, "Added %s after %s and before %s\n", abc->word, abc->prev->word, abc->next);
return 1;
}

Updated to reflect suggestions:

int addToList(struct NODES ** list, struct NODES * arg){
fprintf(stderr,"Add: Adding %s current head %s\n", arg -> word, (*list)->word);
if((*list) -> word == NULL){
    (*list) -> word = malloc(strlen(arg->word)+1);
    strcpy((*list) -> word, arg -> word);
    (*list) -> next = NULL;
    (*list) -> prev = NULL;
    fprintf(stderr,"Add: Head %s\n", (*list) -> word);
    return 2;
}
struct NODES * abc = (*list);
//while arg > abc
fprintf(stderr,"Comparing %s and %s\n", abc->word,arg->word);
while(strcmp(abc->word, arg->word)<0){
    fprintf(stderr,"Comparing %s and %s\n", abc->word,arg->word);
    if (abc -> next == NULL)
        break;
    abc = abc -> next;
}
if (abc == (*list)){
    if(!(strcmp(abc->word, arg->word)<0)){
        arg -> next = abc;
        arg -> prev = NULL;
        abc -> prev = arg;
        *list = arg;
    }
    else{
        abc -> next = arg;
        arg -> prev = abc;
        abc -> next = NULL;
    }
    return 5;
}
if(abc -> next != NULL){
    fprintf(stderr, "Inserting %s between %s and %s\n", arg -> word, abc->prev->word,abc->word); 
    arg -> next = abc;
    arg -> prev = abc -> prev;
    arg -> prev -> next = arg;
    abc -> prev = arg;
    fprintf(stderr, "Added %s before %s and after %s\n", arg->word, arg->prev->word,arg->next->word);
    return 3;
}
return 0
}

Adding spaces around the `->` operator makes it very hard to read the code. And casting `malloc()` in c is not necessary, if you need to because it doesn't compile then you are using the wrong compiler, or maybe it's c++ code, so change the c tag in that case. — Iharob Al Asimi, Apr 12 '15 at 16:52
sorry I personally find it makes it more readable, I'll edit it here @iharob — CSjunkie, Apr 12 '15 at 16:54
No! don't, if for you it's more readable then it's my fault, leave it as it is. — Iharob Al Asimi, Apr 12 '15 at 16:54
I think here you are correct because here it involves more side scrolling with the spaces. And I wasn't sure if I needed the malloc since I am using strcpy. @iharob — CSjunkie, Apr 12 '15 at 16:59
`list->word = (char *)malloc(strlen(arg->word));` --->>>`list->word = malloc(1+ strlen(arg->word));` or `list->word = strdup(arg->word);` (and omit the strcpy() — wildplasser, Apr 12 '15 at 16:59
`list = arg;` won't have any effect once the function returns. — Weather Vane, Apr 12 '15 at 17:03
@WeatherVane good call, do you have any suggestions on how to accomplish what that line is attempting? — CSjunkie, Apr 12 '15 at 17:09
1) You don't seem to care much about the ->prev ponter; if you don't use it, remove it. 2) The roles of `list` and `arg` are not clear to the naive reader. If `arg` is supposed to be inserted/appented into the `list`, then why malloc() yet another node in the insert-function? 3) using a pointer to ponter will reduce the size of the insert function to about ten lines of code. — wildplasser, Apr 12 '15 at 17:45
@wildplasser I use prev pointer later in another function, I discarded the mallocs and will post the new code, and I will post the code that calls addToList as well — CSjunkie, Apr 12 '15 at 18:24

Weather Vane · Accepted Answer · 2015-04-12T18:23:31.440

The list argument received by the function is a copy of the list pointer the caller has. To return a revised list pointer the function could be like this:

int addToList(struct NODES ** list, struct NODES * arg)

and it would be called something like this:

result = addToList(&list, arg);

The function would provide a new list pointer like this

*list = arg;

and all the list access you currently have would be one step more indirect

if(list->word == NULL)

would become

if((*list)->word == NULL)

UPDATE

Try this simplified code, I found this easier than getting my head round yours.

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

struct NODES {
    struct NODES *prev;
    struct NODES *next;
    char *word;
};

void showList(struct NODES * list) {
    while (list) {
        if (list->prev)
            printf("%-10s", list->prev->word);
        else
            printf("%-10s", "NULL");
        printf(" <- %-10s -> ", list->word);
        if (list->next)
            printf("%-10s", list->next->word);
        else
            printf("%-10s", "NULL");
        printf("\n");
        list = list->next;
    }
}

int addToList(struct NODES ** list, char *word){
    struct NODES *wptr, *lptr = *list, *pptr = NULL;
    if ((wptr = malloc(sizeof(struct NODES))) == NULL)
        return -1;
    wptr->prev = NULL; 
    wptr->next = NULL;
    if ((wptr->word = strdup(word)) == NULL)
        return -2;

    if (lptr == NULL) {
        *list = wptr;                 // first list item
        return 0;
    }

    while (lptr) {
        if (strcmp(word, lptr->word) <= 0) {
            wptr->next = lptr;        // insert before current node
            wptr->prev = pptr;
            if (pptr)
                pptr->next = wptr;
            else
                *list = wptr;
            lptr->prev = wptr;
            return 1;
        }
        pptr = lptr;
        lptr = lptr->next;
    }

    wptr->prev = pptr;                // insert at tail
    pptr->next = wptr;
    return 2;
}

int main()
{
    struct NODES *list = NULL;
    addToList(&list, "one");
    addToList(&list, "two");
    addToList(&list, "three");
    addToList(&list, "four");
    addToList(&list, "five");
    showList(list);
    return 0;
}

Program output:

NULL       <- five       -> four
five       <- four       -> one
four       <- one        -> three
one        <- three      -> two
three      <- two        -> NULL

Thank you, that was very helpful but in the example in the question the node containing `c` is still incorrectly replacing the head of the list and the print statement before doing the action is printing "Add: Placing c before list head c" which seems to imply that c replaced the head of the list before being added to the list — CSjunkie, Apr 12 '15 at 17:30
Thank you, that produces the functionality I was seeking. This program is multi-threaded and has many other parts so I must have been over thinking it. — CSjunkie, Apr 12 '15 at 18:39

score 0 · Answer 2 · edited May 23 '17 at 10:24

0

I suspect your problem is here:

list->word = (char *)malloc(strlen(arg->word));
strcpy(list->word, arg->word);

Since you do not allocate room for the terminating null-character, later calls to strcmp will read beyond the allocated buffer. This can have all sorts of behaviours, most likely also the one you see.

Also, drop the (char *) cast, it may hide other problems with your code.

edited May 23 '17 at 10:24

Community

1
1

answered Apr 12 '15 at 17:04

harald

5,976
1
24
41

Thank you but I changed that line to list->word=malloc(strlen(arg->word)+1) based on the suggestion of commentator wildplasser and am still experiencing the issue. – CSjunkie Apr 12 '15 at 17:07
`... later calls to strlen will not know when the string ends.`. They *do* know where the string ends, but the NUL character will be beyond the allocated size for list->word. – wildplasser Apr 12 '15 at 17:07
@CSjunkie, how is `arg->word` allocated, then? – harald Apr 12 '15 at 17:13
`tmp -> word = malloc(strlen(curBuf -> word)+1);` tmp is fed into the function as arg and curBuf points to another list that is filled from input from a file where every word in this buffer is `malloc(maxLS)` where maxLS is the maximum number of chars + 1 for the NUL char – CSjunkie Apr 12 '15 at 17:18
@CSjunkie, you only changed it one place... As well as the problems Weather Vane points out. – harald Apr 12 '15 at 17:25
@harald I updated the question to reflect the suggested changes I've made. I don't see where I missed any changes but if you see one please let me know – CSjunkie Apr 12 '15 at 17:41

C: Comparing Strings

2 Answers2