How do you write generic list without knowing the implementation of structure?

Question

Let's assume there is an employee ADT, such as

//employee.h

typedef struct employee_t employee_t;

employee_t* employee_create(char* company, char* department, char* position);
void employee_free(employee_t* me);

, and client code would be

#include "employee.h"

employee_t* Kevin = employee_create("Facebook", "Marketing", "Sales");
employee_t* John = employee_create("Microsoft", "R&D", "Engineer");

Now client wanted to use list ADT to insert Kevin and John to list for some task.

//list.h

typedef struct list_t list_t;

list_t* list_create(/*might have some arguments*/);

So client code would then be

#include "employee.h"
#include "list.h"

employee_t* Kevin = employee_create("Facebook", "Marketing", "Sales");
employee_t* John = employee_create("Microsoft", "R&D", "Engineer");

list_t* employee = list_create(/*might have some arguments*/);
list_insert(employee, Kevin);
list_insert(employee, John);

employee_free(Kevin);
employee_free(John);

list_print(employee); //Oops! How to print structure that you can't see?

Because employee is encapsulated by opaque pointer, there is no way for list to copy it.

How to write ADT and implementation for list?

Answer 1

The usual way to do this is to have your list structure store the data as a void*. For example, assmuming your list is a singly linked list:

struct list_t
{
  void *data;
  struct list_t *next;
};

Now list_insert whould be something like this:

list_t *list_insert(list_t *head, void *data)
{
  list_t *newHead = (list_t*)malloc(sizeof(list_t));
  newHead->data;
  newHead->next = head;

  return newHead;
}

If you want to hide away the implementation of the struct then you can add methods to extract the data. For example:

void *list_get_data(list_t *head)
{
  return head->data;
}

Answer 2

How do you write generic list without knowing the implementation of structure?

Create functions that handle the structure abstractly.

How to write ADT and implementation for list?

list_create(); needs to pass in helper function pointers for the particular object type to perform various tasks abstractly.

• A copy function like void *employee_copy(const void *emp) so list_insert(employee, Kevin); knows how to copy Kevin.

• A free function like void employee_free(void *emp) so list_uninsert(employee_t) can free the list when destroyed or members removed one-by-one.

• A print function int employee_print(void *emp) so list_print(employee_t) knows how to print each member of its list.

• Possibly others.

Rather than pass in 3+ function pointers, consider passing in a struct that contains these pointers, then the list only needs the overhead of 1 pointer: list_create(employee_t_function_list)

You are taking your first steps toward re-writing C++

Answer 3

You can use something called intrusive list. This concept is heavily used in Linux kernel. All you need is to embed the node into the struct and let the generic code operate only on this struct member.

#include <stddef.h>

struct list_node {
  struct list_node *next;
};

struct list_head {
  struct list_node *first;
};

/* translates pointer to a node to pointer to containing structure
 * for each pointer `ptr` to a `struct S` that contain `struct list_node node` member:
 *   list_entry(&ptr->node, S, node) == ptr
 */
#define list_entry(ptr, type, member) \
  (type*)((char*)ptr - offsetof(type, member))

void list_insert(struct list_head *head, struct list_node *node) {
  node->next = head->first;
  head->first = node;
}

#define LIST_FOREACH(it, head) \
  for (struct list_node *it = (head)->first; it; it = it->next)

The interface can be easily extended by other helpers like list_is_empty, list_first, list_remove_first, embed size to struct list_head.

Exemplary usage:

typedef struct {
  char *name;
  struct list_node node;
} employee_t;

typedef struct {
  char *name;
  struct list_head employees;
} employer_t;

employer_t company = { .name = "The Company" };
employee_t bob = { .name = "Bob" };
employee_t mark = { .name = "Mark" };

list_insert(&company.employees, &bob.node);
list_insert(&company.employees, &mark.node);

printf("Employees of %s:\n", company.name);
LIST_FOREACH(n, &company.employees) {
  employee_t *e = list_entry(n, employee_t, node);
  printf("%s\n", e->name);
}

Prints:

Employees of The Company:
Mark
Bob

Note that the list_* interface can easily used for other types as well.

See article for more information about using this concept for double-linked list.

---

Edit

Note that list_entry invokes a subtle Undefined Behavior. It is related to performing pointer arithmetics outside of the struct member object but still within a parent object. Note that any objects can be treated as an array of chars.

This code will work on all major compilers and it very unlikely to ever fail because it would break a lot of existing and heavily used code (like Linux kernel or Git).

This program is strictly conforming if struct node is a first member of the embedding struct because C standard allows safe conversion between any structure and its first member.

To be strictly conforming if node is not a first member, The issue could be circumvented by forming a pointer to struct list_node not as &bob.node but rather using a pointer arithmetics on a pointer to bob. The result would be:

(struct list_node*)((char*)&bob + offsetof(employee_t, node))

However, this syntax is really nasty, so personally I would go for &bob.node.