Polymorphic data structures in C

Question

I am a C beginner with quite a lot of OOP experience (C#) and I am having trouble understanding how some notion of "polymorphism" can be achieved in C.

Right now, I am thinking how to capture the logical structure of a file system using structs. I have a folder that contains both folders and files. Folders in this folder can contain another files and folders, etc.

My approach:

typedef enum { file, folder } node_type;

struct node;
typedef struct {
    node_type type;
    char *name;
    struct node *next;
    struct node *children;
} node;

Is this the best I can do? I have found a lot of posts on "polymorphism in C", but I would like to see how a polymorphic data structure like this can be built cleanly and efficiently (in terms of memory wasted on unused members of those structures).

Thanks.

Answer 1

I hope I understand what you want - I'm unsure but I guess you want to do something like that:

typedef struct
{
   int type; // file or folder?
} Item;

typedef struct
{
   struct A;
   // data related to a file
} File;

typedef struct
{
   struct A;
   // data related to a folder - like pointer to list of Item
} Folder;

As long as both structure follow the same memory mapping (same variables) and adds to it as a child, you'll be able to use the pointer properly in both structs.

Check this one out as well: How can I simulate OO-style polymorphism in C?

Edit: I'm not sure about the syntax above (took it from the link above). I'm used to writing it this way instead:

typedef struct
{
  int type;
  // data for file
} File;

typedef struct
{
  int type;
  // data for folder - list, etc
} Folder;

Answer 2

C has no intrinsic notion of polymorphism.

You will end up implementing the mechanisms that you want from scratch. That's not a bad thing. It gives you a lot more flexibility. For example, C++ virtual methods are hard-wired per class, you can't change method pointers per-instance.

Here are a few ideas:

Your node_type field provides a way to do a runtime type query. Going further, you can pack multiple types into one struct using a discriminated (or tagged) union: http://en.wikipedia.org/wiki/Tagged_union. I'm not sure whether a variant type qualifies as OO though.

Polymorphism is usually about behavior. You could store function pointers ("methods") in the struct, with pointers to different functions providing different behavior for different object instances. The C++ way of doing things is for each class to have a table of function pointers, then each object instance references the table for its class (incidentally the table pointers can also play the role of your node_type for RTTI). This is called a virtual method table.

Data inheritance means that subclasses contain all of the base class' data members plus some extra stuff. In C the easiest way to do this is by embedding the base class struct at the head of the derived class struct. That way a pointer to derived is a pointer to base.

typedef struct BaseClass {
  int baseMember;
} BaseClass;

typedef struct DerivedClass {
  BaseClass base;
  int derivedMember;
} DerivedClass;

You could do worse than read "Inside the C++ Object Model" by Stanley B. Lippman. For example, this will help if you want to get an idea of how to implement multiple inheritance.

Answer 3

Here's an illustration of old-school C polymorphism, based on ancient memories of X/Motif.

If you just want a discriminated union (or even just a typed structure with a child pointer that may be null), it's probably simpler in your case.

enum NodeType { TFile, TFolder };
struct Node {
    enum NodeType type;
    const char *name;
    struct Node *next;
};

struct FileNode {
    struct Node base_;
};

struct FolderNode {
    struct Node base_;
    struct Node *children;
    /* assuming children are linked with their next pointers ... */
};

Here are the constructors - I'll leave populating the linked lists as an exercise for the reader ...

struct Node* create_file(const char *name) {
    struct FileNode *file = malloc(sizeof(*file));
    file->base_.type = TFile;
    file->base_.name = name; /* strdup? */
    file->base_.next = NULL;
    return &file->base_;
}

struct Node* create_folder(const char *name) {
    struct FolderNode *folder = malloc(sizeof(*folder));
    folder->base_.type = TFolder;
    folder->base_.name = name;
    folder->base_.next = NULL;
    folder->children = NULL;
    return &folder->base_;
}

Now we can walk a hierarchy, checking the type of each node and responding appropriately. This relies on the first member subobject having zero offset to the parent - if that doesn't hold (or you need multiple inheritance), you have to use offsetof to convert between base and "derived" types.

void walk(struct Node *root,
          void (*on_file)(struct FileNode *),
          void (*on_folder)(struct FolderNode *))
{
    struct Node *cur = root;
    struct FileNode *file;
    struct FolderNode *folder;

    for (; cur != NULL; cur = cur->next) {
        switch (cur->type) {
        case TFile:
            file = (struct FileNode *)cur;
            on_file(file);
            break;
        case TFolder:
            folder = (struct FolderNode *)cur;
            on_folder(folder);
            walk(folder->children, on_file, on_folder);
            break;
        }
    }
}

Note that we have a sort-of-polymorphic base type, but instead of switching on the type enumeration we could have a more completely polymorphic setup with virtual functions. Just add a function pointer to Node, something like:

void (*visit)(struct Node *self,
             void (*on_file)(struct FileNode *),
             void (*on_folder)(struct FolderNode *));

and have create_file and create_folder set it to an appropriate function (say, visit_file or visit_folder). Then, instead of switching on the enumerated type, walk would just call

cur->visit(cur, on_file, on_folder);