Doubly linked list: Incompatible pointer types

Question

at the moment I'm working on an implementation of a balanced B-Tree in C. I decided to use doubly linked lists but I have run into some problems. At the moment I get warnings for line 94, 95 and 96 because apparently the pointer types are incompatible. I really don't see how and any help would be greatly appreciated.

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

typedef struct {
    int data1;
    int data2;
    int data2exists; // no: 0 , yes: 1
    struct node * parent;
    struct node * left;
    struct node * middle;
    struct node * right;
} node;

node * insert(int *, node *, node *);
void getInput(int *);
node * createNode(int *);
void quickSwap(node *, int *, int *, int *, int *);
node * splitLeaf(int *, int *, int *, node *, node *);
void printTree(node *);

void main() {
    int input;
    getInput(&input);
    node * root = createNode(&input);
    getInput(&input);
    insert(&input, root, root); // returns current pos
    getInput(&input);
    insert(&input, root, root); // returns current pos
    getInput(&input);
    insert(&input, root, root); // returns current pos
    printTree(root);
}

node * insert(int * input, node * root, node * currentPos) {
    printf("data1: [%i], data2: [%i], d2exists: [%i], input: [%i]\n", currentPos->data1, currentPos->data2, currentPos->data2exists, *input);
    if (currentPos->left == NULL && currentPos->middle == NULL && currentPos->right == NULL) {
        // no children
        if (*input > currentPos->data1 && currentPos->data2exists == 0) {
            // data1 < input, no data2

            currentPos->data2 = *input;
            currentPos->data2exists = 1;
            return(currentPos);
            // printf("CASE1: data1 < input, no data2, no children\n");
        }
        if (*input < currentPos->data1 && currentPos->data2exists == 0) {
            // data1 > input, no data2

            currentPos->data2 = currentPos->data1;
            currentPos->data1 = *input;
            currentPos->data2exists = 1;
            return(currentPos);
            // printf("CASE2: data1 > input, no data2, no children\n");
        }
        if (currentPos->data2exists == 1) {
            // data2 exists
            int smallest;
            int middle;
            int largest;
            quickSwap(currentPos, input, &smallest, &middle, &largest);
            printf("s: [%i] m: [%i] l: [%i]\n", smallest, middle, largest);
            root = splitLeaf(&smallest, &middle, &largest, currentPos, root);
        }
    }
    return(currentPos);
}

void printTree(node * root) {
    if (root->parent != NULL) {
        printf("printTree() did not receive root!!!!\n");
        return;
    }
    else {
        printf("%i || %i", root->data1, root->data2);
        printf("\n");
        // printf("%i || %i", root->left->data1, root->left->data2);
        // printf("\t\t");
        // printf("%i || %i", root->middle->data1, root->middle->data2);
        // printf("\t\t");
        // printf("%i || %i", root->right->data1, root->right->data2);
        // printf("\n");
    }
}

node * splitLeaf(int * smallest, int * middle, int * largest, node * currentPos, node * root) {
// this function needs to return root!
    if (currentPos->parent == NULL) {
        // currentPos is root
        // create a parent with median
        node * root = createNode(middle);
        node * left = createNode(smallest);
        node * middle = createNode(largest);
        // genau hier gehts weiter! hier müssen root, left und, middle verknüpft werden!
        root->left = left;
        root->middle = middle;
        left->parent = middle->parent = root;
        // printf("root-addr: %i, left->parent: %i\n", root, left->parent);
        return(root);
    }
}

void quickSwap(node * currentPos, int * input, int * smallest, int * middle, int * largest) {
    // writes values to *smallest, *middle and *largest ordered by size

    if (currentPos->data1 > currentPos->data2) {
        *smallest = currentPos->data2;
        *middle = currentPos->data1;
    }
    else {
        *smallest = currentPos->data1;
        *middle = currentPos->data2;
    }
    if (*input < *smallest) {
        *largest = *middle;
        *middle = *smallest;
        *smallest = *input;
    }
    else if (*input < *middle) {
        *largest = *middle;
        *middle = *input;
    }
    else {
        *largest = *input;
    }
}

node * createNode(int * input) {
    node * ptr = (node*) malloc(sizeof(node));
    ptr->data1 = * input;
    ptr->data2 = 0;
    ptr->data2exists = 0;
    ptr->parent = NULL;
    ptr->left = NULL;
    ptr->middle = NULL;
    ptr->right = NULL;
    return(ptr);
}

void getInput(int * input) {
    printf("Enter a number\n");
    scanf(" %i",input);
}

@quinxorin It gives the warnings when you compile with -Wall -pedantic (which you should always have enabled). — Kninnug
– Kninnug, Commented Jun 8, 2013 at 14:01
No, even without -Wall or -pedantic. Something went a little wrong with my installation so when I use -Wall i get about a 100 warnings that are just caused by the gcc.. — flntzr
– flntzr, Commented Jun 8, 2013 at 14:12
Ah, you're right, I was assuming that was the case. Can you not reinstall GCC, -Wall and -pedantic are very useful (and should just be enabled inside GCC by default). — Kninnug
– Kninnug, Commented Jun 8, 2013 at 14:16

Kninnug · Accepted Answer · 2013-06-08 14:13:44Z

5

Aha! The problem is a tricky one. It has to do with the definition of your node struct. The members parent, left, middle and right are of type struct node but you typedefed the struct to be node directly. My guess is that GCC ignores the undefined struct node and hopes it's defined somewhere else.

In other words: the type node exists, but struct node doesn't. Therefore when you try to assign a node to a struct node GCC doesn't know what to do. So change

typedef struct {
    ...
} node;

to

typedef struct node {
    ...
} node;

Although it might be wiser to use another name for the struct node than the type node.

Some nitpicks:

GCC complains that main doesn't return an int (just return 0;)
In splitLeaf you're redeclaring the arguments int * middle to node * middle and the same with root.
splitLeaf doesn't return anything when currentPos->parent isn't NULL (though maybe you haven't finished the function yet)

answered Jun 8, 2013 at 14:13

Kninnug

8,1121 gold badge34 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

flntzr Over a year ago

Thanks a lot! I was going crazy over this. Wouldn't have thought of this in a million years..

alk Over a year ago

"...Although it might be wiser to use another name for the struct node than the type node ..." Yes, yes, yes! +1 :-)

Kninnug Over a year ago

You're very welcome. This has become another reason for me to not typedef my structs.

Collectives™ on Stack Overflow

Doubly linked list: Incompatible pointer types

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related