Generic Programming: void* to Generics

C has no generics in the language. Instead it has three escape hatches: void*, macros, and _Generic. This chapter shows all three, then shows how Rust does it properly with monomorphized generics and trait bounds.

The void* Pattern

void* is C's universal pointer -- it can point to any type. The cost is total loss of type information. The compiler cannot check that you cast correctly.

/* void_swap.c -- generic swap with void* */
#include <stdio.h>
#include <string.h>

void generic_swap(void *a, void *b, size_t size)
{
    unsigned char tmp[size];   /* VLA -- C99 */
    memcpy(tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, tmp, size);
}

int main(void)
{
    int x = 10, y = 20;
    generic_swap(&x, &y, sizeof(int));
    printf("x=%d y=%d\n", x, y);   /* x=20 y=10 */

    double p = 3.14, q = 2.72;
    generic_swap(&p, &q, sizeof(double));
    printf("p=%.2f q=%.2f\n", p, q);  /* p=2.72 q=3.14 */

    return 0;
}

This works, but nothing stops you from passing the wrong size or casting the result to the wrong type. The bug compiles cleanly and corrupts memory at runtime.

Caution: void* erases the type. The compiler will not warn if you pass sizeof(int) for a double*. The resulting memory corruption is silent and undefined.

qsort: The Classic void* API

The C standard library's qsort is the canonical example. Its signature:

void qsort(void *base, size_t nmemb, size_t size,
            int (*compar)(const void *, const void *));

Every argument is void* or size_t. The comparison function receives void* and must cast to the real type.

/* qsort_demo.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int cmp_int(const void *a, const void *b)
{
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    return (ia > ib) - (ia < ib);
}

int cmp_str(const void *a, const void *b)
{
    const char *sa = *(const char **)a;
    const char *sb = *(const char **)b;
    return strcmp(sa, sb);
}

int main(void)
{
    int nums[] = {5, 3, 8, 1, 4};
    qsort(nums, 5, sizeof(int), cmp_int);
    for (int i = 0; i < 5; i++)
        printf("%d ", nums[i]);
    printf("\n");   /* 1 3 4 5 8 */

    const char *words[] = {"cherry", "apple", "banana"};
    qsort(words, 3, sizeof(char *), cmp_str);
    for (int i = 0; i < 3; i++)
        printf("%s ", words[i]);
    printf("\n");   /* apple banana cherry */

    return 0;
}

Try It: Write a cmp_int_desc comparator that sorts integers in descending order. Pass it to qsort and verify the output.

typedef for Clarity

Raw function-pointer types are hard to read. typedef helps.

/* typedef_demo.c */
#include <stdio.h>

/* Without typedef: hard to parse */
int (*get_operation_raw(char op))(int, int);

/* With typedef: much clearer */
typedef int (*binop_fn)(int, int);

int add(int a, int b) { return a + b; }
int mul(int a, int b) { return a * b; }

binop_fn get_operation(char op)
{
    switch (op) {
    case '+': return add;
    case '*': return mul;
    default:  return NULL;
    }
}

int main(void)
{
    binop_fn f = get_operation('+');
    if (f)
        printf("3 + 4 = %d\n", f(3, 4));  /* 7 */
    return 0;
}

Macro-Based Generics

When void* is too dangerous, C programmers reach for macros. The preprocessor does text substitution before the compiler sees the code, so a macro can "generate" type-specific functions.

/* macro_generic.c -- type-safe min/max via macros */
#include <stdio.h>

#define DEFINE_MIN(TYPE, NAME)          \
    static inline TYPE NAME(TYPE a, TYPE b) { return a < b ? a : b; }

DEFINE_MIN(int,    min_int)
DEFINE_MIN(double, min_double)

int main(void)
{
    printf("min_int(3,7) = %d\n",      min_int(3, 7));
    printf("min_double(3.1,2.7) = %f\n", min_double(3.1, 2.7));
    return 0;
}

The kernel takes this further. list_for_each_entry iterates over an intrusive list and hands you typed pointers -- no casting needed.

/* Simplified kernel-style iteration macro */
#include <stdio.h>
#include <stddef.h>

#define container_of(ptr, type, member) \
    ((type *)((char *)(ptr) - offsetof(type, member)))

struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

/* Initialize a list head to point to itself (empty circular list) */
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) struct list_head name = LIST_HEAD_INIT(name)

static inline void list_add(struct list_head *new_node,
                            struct list_head *head)
{
    new_node->next = head->next;
    new_node->prev = head;
    head->next->prev = new_node;
    head->next = new_node;
}

#define list_for_each_entry(pos, head, member)                      \
    for (pos = container_of((head)->next, typeof(*pos), member);    \
         &pos->member != (head);                                    \
         pos = container_of(pos->member.next, typeof(*pos), member))

struct task {
    int pid;
    struct list_head link;
};

int main(void)
{
    LIST_HEAD(tasks);

    struct task t1 = { .pid = 1 };
    struct task t2 = { .pid = 2 };
    struct task t3 = { .pid = 3 };

    list_add(&t1.link, &tasks);
    list_add(&t2.link, &tasks);
    list_add(&t3.link, &tasks);

    struct task *pos;
    list_for_each_entry(pos, &tasks, link)
        printf("pid = %d\n", pos->pid);

    return 0;
}

Circular doubly linked list after adding t1, t2, t3:

  tasks (sentinel)
    |
    +--next--> t3.link --next--> t2.link --next--> t1.link --+
    +--prev--- t1.link <--prev-- t2.link <--prev-- t3.link <-+

Driver Prep: list_for_each_entry and container_of are the two macros you will use most often in kernel code. Master them now.

_Generic in C11

C11 introduced _Generic, a compile-time type dispatch. It selects an expression based on the type of its controlling argument.

/* generic_c11.c -- _Generic dispatch (requires C11) */
#include <stdio.h>
#include <math.h>

#define abs_val(x) _Generic((x),       \
    int:    abs,                         \
    long:   labs,                        \
    float:  fabsf,                       \
    double: fabs                         \
)(x)

#define print_val(x) _Generic((x),     \
    int:    print_int,                   \
    double: print_double,                \
    char *: print_str                    \
)(x)

void print_int(int x)       { printf("int: %d\n", x); }
void print_double(double x) { printf("double: %.2f\n", x); }
void print_str(char *s)     { printf("string: %s\n", s); }

int main(void)
{
    printf("abs(-3)   = %d\n",   abs_val(-3));
    printf("abs(-3.5) = %.1f\n", abs_val(-3.5));

    print_val(42);
    print_val(3.14);
    print_val("hello");

    return 0;
}

_Generic is limited: it dispatches on a fixed set of types you enumerate. You cannot write open-ended generic code with it. It is best used for type-overloaded convenience macros.

The typedef + Function Pointer + Macro Trinity

In practice, "generic" C code combines all three techniques:

1. typedef names the function-pointer type so humans can read it.
2. Function pointers supply type-specific operations at runtime.
3. Macros stamp out boilerplate and provide type-safe wrappers.

/* trinity.c -- combining typedef, fn pointers, and macros */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 1. typedef for clarity */
typedef int (*cmp_fn)(const void *, const void *);

/* 2. "Generic" sorted array with function pointer for comparison */
struct sorted_array {
    void   *data;
    size_t  elem_size;
    size_t  len;
    size_t  cap;
    cmp_fn  cmp;
};

struct sorted_array sa_new(size_t elem_size, size_t cap, cmp_fn cmp)
{
    struct sorted_array sa;
    sa.data      = malloc(elem_size * cap);
    sa.elem_size = elem_size;
    sa.len       = 0;
    sa.cap       = cap;
    sa.cmp       = cmp;
    return sa;
}

void sa_insert(struct sorted_array *sa, const void *elem)
{
    if (sa->len >= sa->cap) {
        fprintf(stderr, "sorted_array full\n");
        return;
    }
    /* Find insertion point (linear scan for simplicity) */
    size_t i;
    char *base = (char *)sa->data;
    for (i = 0; i < sa->len; i++) {
        if (sa->cmp(elem, base + i * sa->elem_size) < 0)
            break;
    }
    /* Shift elements right */
    memmove(base + (i + 1) * sa->elem_size,
            base + i * sa->elem_size,
            (sa->len - i) * sa->elem_size);
    memcpy(base + i * sa->elem_size, elem, sa->elem_size);
    sa->len++;
}

/* 3. Macro for type-safe access */
#define SA_GET(sa, type, index) (((type *)(sa)->data)[index])

void sa_free(struct sorted_array *sa) { free(sa->data); }

int cmp_int(const void *a, const void *b)
{
    int ia = *(const int *)a;
    int ib = *(const int *)b;
    return (ia > ib) - (ia < ib);
}

int main(void)
{
    struct sorted_array sa = sa_new(sizeof(int), 16, cmp_int);

    int vals[] = {5, 3, 8, 1, 7};
    for (int i = 0; i < 5; i++)
        sa_insert(&sa, &vals[i]);

    printf("Sorted: ");
    for (size_t i = 0; i < sa.len; i++)
        printf("%d ", SA_GET(&sa, int, i));
    printf("\n");   /* 1 3 5 7 8 */

    sa_free(&sa);
    return 0;
}

Caution: The SA_GET macro trusts you to pass the right type. Get it wrong and you read garbage. C has no defense against this.

Rust: Real Generics

Rust generics are monomorphized -- the compiler generates a separate copy of the function for each concrete type used. You get type safety and zero runtime cost.

// generics.rs -- Rust generics with trait bounds
fn min_val<T: PartialOrd>(a: T, b: T) -> T {
    if a < b { a } else { b }
}

fn print_sorted<T: Ord + std::fmt::Debug>(mut items: Vec<T>) {
    items.sort();
    println!("{:?}", items);
}

fn main() {
    println!("min(3, 7) = {}", min_val(3, 7));
    println!("min(3.1, 2.7) = {}", min_val(3.1, 2.7));

    print_sorted(vec![5, 3, 8, 1, 7]);    // [1, 3, 5, 7, 8]
    print_sorted(vec!["cherry", "apple", "banana"]);
}

Rust Note: Monomorphization means min_val::<i32> and min_val::<f64> are two separate compiled functions. There is no void*, no casting, no runtime dispatch. The compiler catches type errors at compile time.

Trait Bounds and Where Clauses

Trait bounds constrain what a generic type must support. A where clause is just a cleaner way to write the same constraints.

// trait_bounds.rs
use std::fmt::Display;
use std::ops::Add;

// Inline bounds
fn sum_and_print<T: Add<Output = T> + Display + Copy>(a: T, b: T) {
    let result = a + b;
    println!("{} + {} = {}", a, b, result);
}

// Equivalent with where clause (clearer for many bounds)
fn describe<T>(item: &T)
where
    T: Display + PartialOrd + Copy,
{
    println!("Value: {}", item);
}

// Multiple generic parameters
fn largest<T>(list: &[T]) -> &T
where
    T: PartialOrd,
{
    let mut max = &list[0];
    for item in &list[1..] {
        if item > max {
            max = item;
        }
    }
    max
}

fn main() {
    sum_and_print(3, 4);       // 3 + 4 = 7
    sum_and_print(1.5, 2.5);   // 1.5 + 2.5 = 4

    describe(&42);
    describe(&"hello");

    let nums = vec![5, 3, 8, 1, 7];
    println!("largest = {}", largest(&nums));   // 8
}

Generic Structs

In C, you fake generic containers with void* and macros. In Rust, you declare a generic struct directly.

// generic_struct.rs
struct SortedVec<T: Ord> {
    data: Vec<T>,
}

impl<T: Ord> SortedVec<T> {
    fn new() -> Self {
        SortedVec { data: Vec::new() }
    }

    fn insert(&mut self, value: T) {
        let pos = self.data.binary_search(&value).unwrap_or_else(|e| e);
        self.data.insert(pos, value);
    }

    fn contains(&self, value: &T) -> bool {
        self.data.binary_search(value).is_ok()
    }

    fn iter(&self) -> impl Iterator<Item = &T> {
        self.data.iter()
    }
}

fn main() {
    let mut sv = SortedVec::new();
    sv.insert(5);
    sv.insert(3);
    sv.insert(8);
    sv.insert(1);
    sv.insert(7);

    print!("Sorted: ");
    for v in sv.iter() {
        print!("{} ", v);
    }
    println!();  // 1 3 5 7 8

    println!("contains 3? {}", sv.contains(&3));  // true
    println!("contains 6? {}", sv.contains(&6));  // false
}

Why the Kernel Chose Macros Over void*

The kernel avoids void* for linked lists. Here is why:

  void* approach:                Macro approach:

  struct list_node {             struct list_head {
      void *data;  <-- cast!         struct list_head *next;
      struct list_node *next;        struct list_head *prev;
  };                             };
                                 // Embed list_head in your struct.
  Requires:                      // container_of recovers parent.
  - runtime cast on every access
  - extra indirection (pointer   Requires:
    to data, not data itself)    - typeof / offsetof at compile time
  - no type checking             - zero extra indirection
                                 - type-safe iteration macros

The macro approach gives:

• No extra allocations: the list node lives inside the data struct.
• No casts at use sites: list_for_each_entry hands you a typed pointer.
• No double indirection: one fewer pointer dereference per access.

Try It: Rewrite the generic_swap function from the beginning of this chapter using a macro instead of void*. The macro version should work for any type without requiring a size parameter. (Hint: use typeof.)

Knowledge Check

1. What goes wrong if you pass sizeof(int) to generic_swap but the pointers actually point to double values?
2. In _Generic, what happens if the controlling expression's type does not match any of the listed types and there is no default case?
3. What does "monomorphization" mean in Rust, and how does it differ from C++'s template instantiation?

Common Pitfalls

• Casting void* to the wrong type -- the compiler says nothing, the program corrupts memory silently.
• Macro hygiene -- macro arguments evaluated multiple times cause bugs: MIN(x++, y) increments x twice.
• _Generic does not support user-defined types easily -- you must enumerate every type explicitly.
• Forgetting trait bounds in Rust -- the compiler will tell you exactly which trait is missing, but the error messages can be long.
• Over-constraining generics -- requiring more traits than necessary reduces reusability.