implementation of a basic radix trie in C

Question

I'm currently implementing the algorithm described here (wikipedia).
The article describes 2 main structures :

• A node, containing an array of edges
• An edge, containing a pointer to a target node and a label

So, currently I've got 2 struct in my C code: radix_node_s and radix_edge_s

typedef struct radix_node_s radix_node_t;

typedef struct radix_edge_s {
    radix_node_t                *target_node;
    char                        *label;

    SLIST_ENTRY(radix_edge_s)   next;
} radix_edge_t;

struct radix_node_s {
    SLIST_HEAD(radix_edge_list_s, radix_edge_s) edges;
    void                                        *data;
};

I was wondering if I could make the edge structure disappear and merge its contain with its target node. Thus, the edge label would be a new field of a node.

Would it be a fine way to do this or do I miss something?

Answer 1

Well, if label of edge is same as label of either source or target node, then just change the edge structure to pointer to node, no point in duplicating data.

But if it is the name of the edge, and node may have edges with different names, then you really do need "tuple" of data for edge: target and name. And best way to handle this with C is to have edge struct.

Saying this just in case, maybe it is already like this (don't know what the SLIST_* are): since your struct is small, you should use it as value type. That is, instead of having an array of pointers to edge structs or linked list of edge structs, have pointer to array of edge struct values. Even if you need to resize the array of small structs, it's still much more efficient with modern processors, than keeping a linked lists or extra indirection through an array of pointers.