Can data structures be completely abstracted in C?

Question

I am currently building a personal library of data structures, and I realized that they may be able to be abstracted completely by have the data in it be a void *. So let's say that I create a linked list

typedef struct node_ll {
    void *data;
    struct node_ll *next;
} node_ll;

and let's say that I am creating a linked list of structs where they are defined as

struct person {
    char *name;
    int age;
};

Then, is it possible to define an abstract search method

void *traverse(void *head, void* data) {}

to find a person who is age 19 and has the name 'John'?

It is possible, but very error prone. Take a look at http://stackoverflow.com/a/351756/1944441, the book mentioned is not easy to understand. — , Jun 12 '13 at 15:24
May be also pass a function pointer which will handle the type of data which the `void *` points to. — phoxis, Jun 12 '13 at 15:25
It is possible, but you lose type safety. You'd better move away from C and look into the Standard Template Library of C++ or even better start program in Haskell. — Bryan Olivier, Jun 12 '13 at 15:43
@Armin Possibly, but do you agree with the other advices ;)? — Bryan Olivier, Jun 12 '13 at 15:51
@BryanOlivier C should not be used for OOP other than practice or smaller programs. You should pick a favorite OOP language. — , Jun 12 '13 at 15:53
@Armin: C is okay for OOP, for some loose definition of OOP. Sys V streams, and X11 are implemented in C and use an OOP approach. — jxh, Jun 12 '13 at 16:06
Thanks for the book recommendation, I like using C for OOP because of the amount of flexibility, even thought it may be extra work. — user1876508, Jun 12 '13 at 16:08

score 2 · Accepted Answer · answered Jun 12 '13 at 16:10

2

To make your list data structure abstract, simply hide the definition of the node_ll structure in a source file. The header file would only contain the forward declaration, and the prototypes for the APIs:

typedef struct node_ll node_ll;
typedef struct linkedlist { node_ll *head; } linkedlist;

static inline linkedlist make_linkedlist () {
    const linkedlist zero_ll = { 0 };
    return zero_ll;
}
void unmake_linkedlist (linkedlist *list);

void linkedlist_add (linkedlist *list, void *data);
void linkedlist_traverse_until (linkedlist *list,
                                int (*visit)(void *visit_data, void *data),
                                void *visit_data);

The linkedlist_traverse_until() function will basically call the provided visit() function on each node, unless visit() returns 0, at which point it stops. The implementation of the function knows how to access a node_ll because it is in the source file that has the complete definition of the struct node_ll.

while (node) {
    if (visit(visit_data, node->data)) {
        node = node->next;
        continue;
    }
    break;
}

answered Jun 12 '13 at 16:10

jxh

69,070
8
110
193

so basically I have a structure.h file which defines a prototype for the data structure type and I define that data structure with each implementation, and also define a traversal method in that implementation as well? – user1876508 Jun 12 '13 at 16:26
You do not have to define the structure completely in a header file, as long as all the APIs only use a pointer to the forward declaration (a pointer is a complete type). The source file (i.e. the `.c` file) contains the spelled out structure definition (with the `data` and `next` member as you have it in your post), so that the implementation of the APIs can access those members. – jxh Jun 12 '13 at 17:03
Do you know of any full working examples online which illustrate this further? – user1876508 Jun 13 '13 at 04:45
1

Not for linked list, but there is a [red-black tree implementation](http://libredblack.sourceforge.net/) that uses this idea. Opaque data types in general are pretty common. The UNIX file descriptor concept is essentially an opaque type. – jxh Jun 13 '13 at 06:23

Can data structures be completely abstracted in C?

1 Answers1