CODEWITHSUNDEEP
cstructbinary-treefunction-pointersheader-files
hacatu
hacatu

Reputation: 665

C struct, function pointer, and header problems (unsure which is the cause)

So, I'm trying to make this binary tree program in C and it just keeps throwing the darndest compile errors. Whenever I change something to find what is causing the error, it changes! I have not forgotten my include guards, I used #pragma once. If I place the struct in the header I get incompatible types, if I put it in the .c I get a redefinition of pretty_print which goes away when I rename pretty_print. As I trim out the other functions in bintree.c and the header, the error changes to intTree being undefined. If I then change intTree to just int it becomes incompatible types. This goes away if I merge the header into the .c. Now it's gone. I think these might be seperate errors and the changing error might be my bad, but it is happening an I have no idea why. I will present code that demonstrates as many of these, but whenever I try to duplicate what I did it throws a different error. But I'm not frustrated. I would like to be able to post a well-formatted question with helpful information, but I have none, despite spending several hours on this program.

bintree.cxx

#include "bintree.h"

int add(intTree* root,int key,void* val){
    if(!root){
        root=malloc(sizeof(intTree));
        if(!root){
            return 1;
        }
        root->key=key;
        root->val=val;
        root->left=0;
        root->right=0;
        return 0;
    }
    if(key>root->key){
        if(root->right){
            return add(root->right,key,val);
        }else{
            root->right=(intTree*) malloc(sizeof(intTree));
            if(!root->right){
                return 1;
            }
            root->right->key=key;
            root->right->val=val;
            root->right->left=0;
            root->right->right=0;
            return 0;
        }
    }
    if(key<root->key){
        if(root->left){
            return add(root->left,key,val);
        }else{
            root->left=malloc(sizeof(intTree));
            if(!root->left){
                return 1;
            }
            root->left->key=key;
            root->left->val=val;
            root->left->left=0;
            root->left->right=0;
            return 0;
        }
    }
    return 2;
}

void* get(intTree* root,int key){
    if(!root){
        return 0;
    }
    if(key>root->key){
        return get(root->right,key);
    }
    if(key<root->key){
        return get(root->left,key);
    }
    return root->val;
}

int remove_root(intTree* root){
    if(!root){
        return 1;
    }
    if(root->right){
        root->key=root->right->key;
        root->val=root->right->val;
        return remove_root(root->right);
    }
    if(root->left){
        root->key=root->left->key;
        root->val=root->left->val;
        return remove_root(root->left);
    }
    free(root);
    return 0;
}

int remove_node(intTree* root,int key){
    if(!root){
        return 1;
    }
    if(key>root->key){
        return remove_node(root->right,key);
    }
    if(key<root->key){
        return remove_node(root->left,key);
    }
    return remove_root(root);
}

void delete(intTree* root){
    if(root){
        delete(root->right);
        delete(root->left);
        free(root);
    }
}

void pretty_print(intTree* root,int ws,int wso,void (*print_val)(void*)){
    if(!root) return;
    printf("%*s",ws,"");
    print_val(root->val);
    pretty_print(root->left,ws+wso,wso,print_val);
    pretty_print(root->right,ws+wso,wso,print_val);
}

bintree.h

#pragma once

#include <stdlib.h>

typedef struct intTree_s{
    int key;
    void* val;
    struct intTree_s* left;
    struct intTree_s* right;
} intTree;

int add(intTree*,int,void*);
void* get(intTree*,int);
int remove_root(intTree*);
int remove_node(intTree*,int);
void delete(intTree*);
void pretty_print(intTree*,int,int,void(*)(void*));

These throw hundreds of errors about intTree being an incomplete type. This persists for whichever format of typedef/struct I use to define intTree.

bintree.c

#include "pretty_print.h"
void pretty_print(void){return;}

pretty_print.h

void pretty_print(void);

Throws conflicting types for "pretty_print", though it does not if I rename to "p", inline the header, or change the arguments to "int v". This also works with the arguments "int* a,void()(void)", as in the original program.

Final "error": warns about implicit redefinition of malloc, free, printf, and puts.

bintree.cxx

struct intTree_s{
    int key;
    void* val;
    struct intTree_s* left;
    struct intTree_s* right;
};

typedef struct intTree_s intTree;

int add(intTree* root,int key,void* val){
    if(!root){
        root=malloc(sizeof(intTree));
        if(!root){
            return 1;
        }
        root->key=key;
        root->val=val;
        root->left=0;
        root->right=0;
        return 0;
    }
    if(key>root->key){
        if(root->right){
            return add(root->right,key,val);
        }else{
            root->right=(intTree*) malloc(sizeof(intTree));
            if(!root->right){
                return 1;
            }
            root->right->key=key;
            root->right->val=val;
            root->right->left=0;
            root->right->right=0;
            return 0;
        }
    }
    if(key<root->key){
        if(root->left){
            return add(root->left,key,val);
        }else{
            root->left=malloc(sizeof(intTree));
            if(!root->left){
                return 1;
            }
            root->left->key=key;
            root->left->val=val;
            root->left->left=0;
            root->left->right=0;
            return 0;
        }
    }
    return 2;
}

void* get(intTree* root,int key){
    if(!root){
        return 0;
    }
    if(key>root->key){
        return get(root->right,key);
    }
    if(key<root->key){
        return get(root->left,key);
    }
    return root->val;
}

int remove_root(intTree* root){
    if(!root){
        return 1;
    }
    if(root->right){
        root->key=root->right->key;
        root->val=root->right->val;
        return remove_root(root->right);
    }
    if(root->left){
        root->key=root->left->key;
        root->val=root->left->val;
        return remove_root(root->left);
    }
    free(root);
    return 0;
}

int remove_node(intTree* root,int key){
    if(!root){
        return 1;
    }
    if(key>root->key){
        return remove_node(root->right,key);
    }
    if(key<root->key){
        return remove_node(root->left,key);
    }
    return remove_root(root);
}

void delete(intTree* root){
    if(root){
        delete(root->right);
        delete(root->left);
        free(root);
    }
}

void pretty_print(intTree* root,int ws,int wso,void (*print_val)(void*)){
    if(!root) return;
    printf("%*s",ws,"");
    print_val(root->val);
    pretty_print(root->left,ws+wso,wso,print_val);
    pretty_print(root->right,ws+wso,wso,print_val);
}

I can't seem to generate the original error, which was about a redefinition of pretty_print, again. I apoligize for how little I know about this problem (basically just that it is).

Upvotes: 0

Views: 182

Answers (2)

user3629249
user3629249

Reputation: 16540

This typedef struct format your using is deprecated syntax.
rather, use:


struct intTree_s{
    int key;
    void* val;
    struct intTree_s* left;
    struct intTree_s* right;
};

Then on every reference to intTree_s, write it as: struct intTree_s
This will eliminate the 'incomplete struct' error messages

Upvotes: 1

Jonathon Reinhart
Jonathon Reinhart

Reputation: 137398

implicit redefinition of malloc, free, printf, and puts.

This means you're not including the proper header files. Add these to every C file that calls these functions. 

#include <stdio.h>      // printf, puts and friends
#include <stdlib.h>     // malloc/free

Don't put them in some common header file - only do that if they expose a type that you use in the header file itself.

You're getting an "implicit redefinition" because, if you don't include the proper header files, the compiler will implicitly define their signatures based upon your usage (the dumbest feature of C, IMO).

People seem to have a hard time knowing what goes in the .c file and the header files. It's simple:

  1. Start out putting everything related to this component (e.g your intTree implementation) in one .c file. (Including structs). Mark all functions static which means they are not visible to anyone outside of the file.

  2. Decide which functions are part of your publicly-accessible API. Remove static from these functions, and copy/paste their prototype to that .c file's accompanying .h file. (e.g. int add(intTree* root,int key,void* val);).

  3. Decide if any structs need to be visible as well, or if they can be hidden. It's best to leave the actual struct definition hidden in the .C file. Your public API functions will take only pointers to those structures, so outside code will never need to know the size/offsets of those structs. So just add struct foo; to the header file, leaving its definition in the .C file.

Example:

foo.c

#include "foo.h"

/** Definition of struct foo - hidden to consumers of foo **/
struct foo
{
    int a;
    int b;
    int c;
};             /* This always gets forgotten :-) */

/** "private" internal function, marked static to hide from consumers **/
static void _foo_internal(struct foo *f)
{
    // ... internal function ****
}

/** Foo Public API **/
struct foo *new_foo(int a, int b, int c)
{
    struct foo* f;

    f = malloc(sizeof(*f));
    if (f == NULL)
        return NULL;

    _foo_internal(f);
    f->a = a;
    f->b = b;
    f->c = c;
}

int foo_get_a(struct foo *f)
{
    _foo_internal(f);
    return f->a;
}

void foo_set_a(struct foo *f, int val)
{
    _foo_internal(f);
    f->a = val;
}

foo.h

#ifndef FOO_H
#define FOO_H

/**
 * Consumers need to know only that struct foo exists,
 * not its size of member offsets.
 */
struct foo;

/** Prototypes for foo public API **/
struct foo *new_foo(int a, int b, int c);
int foo_get_a(struct foo *f);
void foo_set_a(struct foo *f, int val);

#endif /* FOO_H */

test.c

#include "foo.h"

int main(void)
{
    /**
     * No static instances of foo allowed!
     * test.c does not know the size of struct foo!
     */
    //struct foo my_foo;

    struct foo *pFoo;

    pFoo = new_foo(1,2,3);
    if (pFoo == NULL)
        return 1;

    set_foo_a(pFoo, 42);

    return 0;
}

Upvotes: 6

Related Questions