Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Generic programming in C

Name: Anonymous 2012-01-12 3:49

I love C so much, and I really want to hate sepples, but I can't help but think that generic programming in C is shit! Macros are no good for generic data structures, as they are clunky and blow out code size, nor are void pointers, as you need to allocate separate memory just to store an integer (don't stuff ints into pointers; zeros won't work on architectures where the null pointer constant is non-zero). I really want to write my data structure library in sepples, where templates allow type genericism without issue. What should I do, /prague/; what should I do?!

Name: Anonymous 2012-01-14 6:56

A generic linked list that will contain anything you could think of. No macros! It assumes struct node has the strictest alignment.

#include <stdlib.h>
#include <stddef.h>
#include <string.h>

// API
struct list;

struct list *make_list(size_t elem_size);
void *prepend(struct list *l);
void *append(struct list *l);
void *insert_after(struct list *l, void *node);
void *insert_before(struct list *l, void *node);
void *head(struct list *l);
void *tail(struct list *l);
void *next(void *node);
void *previous(void *node);

// implementation

struct list
{
    size_t elem_size;
    struct node head, tail;
};

struct node
{
    struct node *prev, *next;
};

struct list *make_list(size_t elem_size)
{
    struct list *l;

    l = malloc(sizeof *l);
    l->elem_size = elem_size;
    l->head.next = &l->tail;
    l->tail.prev = &l->head;
    return l;
}

static struct node *make_node(size_t elem_size)
{
    struct node *n;
    size_t size;

    size = sizeof *n + (elem_size + sizeof *n - 1) / sizeof *n;
    n = malloc(size);
    return n;
}

static void insert(struct node *i, struct node *p, struct node *n)
{
    p->next = i;
    i->prev = p;
    i->next = n;
    n->prev = i;
}


void *prepend(struct list *l)
{
    struct node *n;

    n = make_node(l->elem_size);
    insert(n, &l->head, l->head.next);
    return n + 1;
}

void *append(struct list *l)
{
    struct node *n;

    n = make_node(l->elem_size);
    insert(n, l->tail.prev, &l->tail);
    return n + 1;
}

void *insert_after(struct list *l, void *node)
{
    struct node *m, *n;

    m = (struct node *)node - 1;
    n = make_node(l->elem_size);
    insert(n, m, m->next);
    return n + 1;
}

void *insert_before(struct list *l, void *node)
{
    struct node *m, *n;

    m = (struct node *)node - 1;
    n = make_node(l->elem_size);
    insert(n, m->prev, m);
    return n + 1;
}

void *head(struct list *l)
{
    return &l->head + 1;
}

void *tail(struct list *l)
{
    return &l->tail + 1;
}

void *next(void *node)
{
    struct node *n;

    n = (struct node *)node - 1;
    return n->next + 1;
}

void *previous(void *node)
{
    struct node *n;

    n = (struct node *)node - 1;
    return n->prev + 1;
}

// example

struct person
{
    char name[60];
    int age;
};

void init_person(struct person *p, const char *name, int age)
{
    strcpy(p->name, name);
    p->age = age;
}

int main()
{
    struct list *l;
    struct person *p;

    l = make_list(sizeof *p);
    init_person(append(l), "Charlie", 8);
    init_person(append(l), "Bob", 42);
    init_person(append(l), "Niels", 9);
    init_person(append(l), "Jon", 11);
    init_person(append(l), "Becky", 10);
    init_person(append(l), "Ashley",9);

    for (p = next(head(l)); p != tail(l); p = next(p)) {
        printf("%s %d\n", p->name, p->age);
    }

    exit(EXIT_SUCCESS);
}

I wrote this on my phone, so I probably made some mistakes. I didn't bother to add remove() or error handling, but that should be straight-forward.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List