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);
}

Answer 1

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)