Can you modify a typedef in a different header file

Question

I'm working on some data structures in C. I have created a queue data structure that can take any type of data. This is currently being done by a macro which is default initialized to int type.

#ifndef DATATYPE
#define DATATYPE int
#endif

The queue header is being included in another data structure - the binary search tree, and I am using the queue for a breadth-first-search implementation. In the Makefile, I have modified the DATATYPE macro from an int to a binary_tree_node_t * type.

binary_tree: DEFS=-DDATATYPE="struct BINARY_TREE_NODE *"

My question is, is there a better way to do this using typedefs? Can I define a type DATATYPE as an int in the queue implementation, but have it get modified in a different header file? Or is it possible to implement a queue that can take any datatype?

Here are the source files (redacted for sake of brevity) for reference:

queue.h

#ifndef _QUEUE_H
#define _QUEUE_H 

#ifndef DATATYPE
#define DATATYPE int
#endif

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


typedef struct LL_NODE {
  DATATYPE data;
  struct LL_NODE* next;
} node_t;


typedef struct QUEUE {
  node_t* head;
  node_t* tail;
  int size;
  
} queue_t;

queue_t* init_queue();

void destroy(queue_t* queue);

bool is_empty(queue_t* queue);

int size(queue_t* queue);

void enqueue(queue_t* queue, DATATYPE data);
DATATYPE dequeue(queue_t* queue);

DATATYPE peek(queue_t* queue);

#endif

binary_search_tree.c

#include "binary_search_tree.h"

void bfs_trav(binary_tree_node_t* root) {
  queue_t* queue = init_queue();
  binary_tree_node_t* temp = root;
  
  enqueue(queue, root);
  while (!is_empty(queue)) {
    temp = dequeue(queue);
    printf("%d ", temp->data);
    if (temp->left) {
      enqueue(queue, temp->left);
    }
    if (temp->right) {
      enqueue(queue, temp->right);
    }
  }
  destroy(queue);
  return;
}

binary_search_tree.h

#ifndef _BINARY_SEARCH_TREE_H
#define _BINARY_SEARCH_TREE_H

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

#include "../queue/queue.h"

typedef struct BINARY_TREE_NODE {
  int data;
  struct BINARY_TREE_NODE *left;
  struct BINARY_TREE_NODE *right;
} binary_tree_node_t;

void bfs_trav(binary_tree_node_t* root);

#endif

Answer 1

One popular way to do what you're trying to do is to nest your data structures and thereby make "polymorphic" types. In your case, that would mean removing the payload from the LL_NODE struct entirely and declare various "derived" structs as needed. For example:

typedef struct LL_NODE {
  struct LL_NODE* next;
} node_t;

typedef struct INT_NODE {
  node_t node;
  int payload;
} int_node_t;

typedef struct TREE_NODE {
  node_t node;
  struct BINARY_TREE_NODE *payload;
} tree_node_t;

Any time you want to work with the linked list simply pass a pointer to the node struct member for any derived type.

Of course for this to be useful, you'll need a way to "downcast" from a linked list node to a derived type. This is usually done with a macro that will look roughly as follows:

#define LIST_NODE_DOWNCAST(ptr, derivedType, nodeName) \
   (derivedType *)((ptrdiff_t)ptr - (ptrdiff_t)&((derivedType *)0)->nodeName)

So for example, given a node_t pointer called list_ptr, that you know refers to an int_node_t object, you can recover the int_node_t object as follows:

int_node_t *derived = LIST_NODE_DOWNCAST(list_ptr, int_node_t, node);

Note that this is the primary method used in the Linux kernel for managing queues and lists. I answered a related question a while ago where you can see a specific example in usage in the kernel.

Answer 2

I would suggest (quite strongly) that the makefile is the wrong place to make that change. You should be setting the data type in the BST code before including queue.h:

…
#define DATATYPE struct BINARY_TREE_NODE *

#include "queue/queue.h"
…

Your binary tree code knows what it wants to use; it should not rely on the vagaries of the makefile to ensure it gets what it needs.

Whether you should add #undef DATATYPE before defining it is trickier; I'd not do it unless it was proven necessary — and I'd also debate why it's necessary and how you are going to have two sets of functions with the same names but working with different types, given that this is C and C++. On the whole, not using #undef is safer; you will be told if there is a problem which using #undef will conceal — and the concealed problems will be hell to debug!