Sorted Insertion into Linked List

Question

AoA,

I've been attempting to debug a problem in my circular linked list for 12hrs now. The function takes in an ADT which has a start and cursor field. The initial dummy cell points to itself. Insert elements. Repeat elements are not allowed.

    int setInsertElementSorted(setADT buffer, setElementT E)
    {
        bool isUnique = true;
        cellT *previous;

        previous = buffer->start;
        buffer->cursor = buffer->start->next;

        while(buffer->cursor != buffer->start){
            if(buffer->cursor->value == E){
                isUnique = false;
            } else if(E < buffer->cursor->value)
                break;
              else {   
                previous = buffer->cursor;
                buffer->cursor = buffer->cursor->next;
            }
        }

        if(isUnique != false){
            cellT *newNode = malloc(sizeof(cellT));
            newNode->value = E;
            previous->next = newNode;
            newNode->next = buffer->cursor;

            buffer->count++;
            return (buffer->count);   
            }
    }

The code takes in a series of integers and then sorts them into the LL parameter. Supposed to be used for a set (hence why no repeat entries).

The output for: 9, 8, 7, 6, 5, 4, 3, 2, 1

is.. 3, 4, 5, 6, 7, 8, 9 (what happened to the first two values?)

When inputting something like: 7, 3, 5, 1, 9, 2

out is only 7, 9 (so it can't handle values separated by more than one.. o.O)

Additional info:

typedef struct cellT {
    int value;
    struct cellT *next;
} cellT;

struct setCDT{
    int count;
    cellT *start;
    cellT *cursor;   
};

setADT setNew()
{
    setADT newNode = malloc(sizeof(struct setCDT));
    newNode->start = newNode->cursor = malloc(sizeof(cellT));
    newNode->start->next = newNode->cursor->next = newNode->start;
    newNode->count = 0;
    return (newNode);
}

setADT is a pointer type to setCDT. setElementT, however, is just a plain and simple int. Sorry for the ambiguity.

Answer 1

Some observations:

while(buffer->cursor != buffer->start && buffer->cursor->value < E){
    if(buffer->cursor->value == E) // never true

The value == E inside the first loop is never true since the loop condition has value < E, hence encountering a value equal to E would stop iterating. Change the loop condition to <= E and simply return if a duplicate is found instead of using the flag.

The path where flag == false also does not return a value (although due to the above bug it is not reachable at the moment), and also the memory allocated for newNode leaks if the bug with flag is fixed and E exists in the list already.

The following if seems pointless, and due to no { after else the indentation is very misleading:

if(buffer->cursor != buffer->start){
    newNode->next = buffer->cursor; // would be harmless in both branches
    previous->next = newNode;       // done in both branches
} else                              // always using { } would make this clear
    previous->next = newNode;
    buffer->count++;
    return (buffer->count);

Also, don't typedef setADT as a pointer type, it's just misleading and combined with constructs like New(setADT) is almost certain to cause bugs.

Meanwhile in setNew, since there is only one node, replace newNode->start->next = newNode->cursor->next = newNode->start; with newNode->start->next = newNode->start;

Summary of changes:

int setInsertElementSorted(struct setCDT * const buffer, const int E) {
    cellT *newNode;
    cellT *previous = buffer->start;
    buffer->cursor = previous->next;

    while (buffer->cursor != buffer->start && buffer->cursor->value <= E) {
        if (buffer->cursor->value == E) {
            return buffer->count; // duplicate value
        }
        previous = buffer->cursor;
        buffer->cursor = buffer->cursor->next;
    }
    if ((newNode = malloc(sizeof(*newNode)))) {
        newNode->value = E;
        newNode->next = buffer->cursor;
        previous->next = newNode;
        buffer->count++;
    }
    return buffer->count;
}

If the bug persists, the error is likely to be elsewhere.

Code to test:

int main (int argc, char **argv) {
    struct setCDT *list = setNew();
    for (int i = 1; i < argc; ++i) {
        setInsertElementSorted(list, atoi(argv[i]));
    }
    list->cursor = list->start;
    while ((list->cursor = list->cursor->next) != list->start) {
        (void) printf("%d\n", list->cursor->value);
    }
    return EXIT_SUCCESS;
}