CODEWITHSUNDEEP
cgenericstree
fho
fho

Reputation: 500

Tree datastructure with 2 different key types and minimal redundant code

I'm programming a prefix tree in C to store IP-Prefixes. The keys are the IP-Prefixes. I would like to use it with 32bit or 128bit keys (IPv4/IPv6 addresses).

The insert/remove/lookup functions need to call different bitop functions for the ipv4 or ipv6 variant.

How could I do this in C?

At the end i would like to have the following structs and functions:

  typedef struct tree_node6_t {
    ipv6_addr prefix;
    u_int8_t len;
    struct tree_node6_t* parent;
    struct tree_node6_t* lchild;
    struct tree_node6_t* rchild;
    void* data;
} tree_node6;

typedef struct tree_node4_t {
    ipv4_addr prefix;
    u_int8_t len;
    struct tree_node4_t* parent;
    struct tree_node4_t* lchild;
    struct tree_node4_t* rchild;
    void* data;
} tree_node;

void tree_insert4(tree_node* root, tree_node* new_node, const unsigned int level);
void tree_insert6(tree_node* root, tree_node* new_node, const unsigned int level);
tree_node* tree_lookup4(const tree_node* root_node, const ipv4_addr* prefix, const u_int8_t prefix_len, unsigned int* level);
tree_node* tree_lookup6(const tree_node* root_node, const ipv6_addr* prefix, const u_int8_t prefix_len, unsigned int* level);

thanks for any hints :=)

Upvotes: 0

Views: 218

Answers (2)

Yochai Timmer
Yochai Timmer

Reputation: 49221

You could use another typedef to declare the ip type.
Then you can just change that at compile time with preprocessor directives:

#ifdef USE_NODE4
typedef ipv4_addr ADDRESSTYPE ;
#define TREEINSERT tree_insert4 
#define TREELOOKUP tree_lookup4
#else
typedef ipv6_addr ADDRESSTYPE ;
#define TREEINSERT tree_insert6 
#define TREELOOKUP tree_lookup6
#endif

typedef struct tree_node_general {
    ADDRESSTYPE prefix;
    u_int8_t len;
    struct tree_node_general* parent;
    struct tree_node_general* lchild;
    struct tree_node_general* rchild;
    void* data;
} tree_node; 

void TREEINSERT (tree_node* root, tree_node* new_node, const unsigned int level);
tree_node* TREELOOKUP (const tree_node* root_node, const ADDRESSTYPE* prefix, const u_int8_t prefix_len, unsigned int* level);

Upvotes: 1

marc
marc

Reputation: 6223

You could use the fact that every IPv4 address can be mapped to a IPv6 address.

Upvotes: 1

Related Questions