queue

queue.c

#include <stdio.h>
#include <stdlib.h>


typedef void (*Func) (void *udata);

typedef struct node {
    Func         func;
    void        *udata;
    struct node *next;
} Node;

typedef struct {
    size_t  len;
    size_t  cap;
    size_t  max_cap;
    Node   *first;
    Node   *last;
    Node   *resv;  /* reserved nodes: avoid unnecessary malloc (reuse) */
} CList;

static int   clist_init(CList *c, size_t init_size, size_t max_cap);
static void  clist_deinit(CList *c);
static int   clist_queue(CList *c, Func func, void *udata);

/* Don't free() the returned node */
static Node *clist_dequeue(CList *c);

/* resv list */
static void  _clist_append(CList *c, Node *new_node);
static Node *_clist_pop(CList *c);
static void  _clist_destroy(CList *c);


static int
clist_init(CList *c, size_t init_size, size_t max_cap)
{
    c->resv = NULL;

    for (size_t i = 0; i < init_size; i++) {
        Node *const node = malloc(sizeof(Node));
        if (node == NULL) {
            _clist_destroy(c);
            return -1;
        }

        _clist_append(c, node);
    }


    c->len = 0;
    c->cap = init_size;
    c->max_cap = max_cap;
    c->first = NULL;
    c->last = NULL;
    return 0;
}


static void
clist_deinit(CList *c)
{
    Node *node;
    while ((node = clist_dequeue(c)) != NULL);

    _clist_destroy(c);
    c->first = NULL;
    c->last = NULL;
}


static int
clist_queue(CList *c, Func func, void *udata)
{
    Node *new_node = _clist_pop(c);
    if (new_node == NULL) {
        if (c->cap >= c->max_cap)
            return -1;

        new_node = malloc(sizeof(Node));
        if (new_node == NULL)
            return -1;

        printf("need alloc\n");
        c->cap++;
    }

    if (c->last == NULL)
        c->first = new_node;
    else
        c->last->next = new_node;
    
    new_node->func = func;
    new_node->udata = udata;
    new_node->next = NULL;
    c->last = new_node;
    c->len++;
    return 0;
}


static Node *
clist_dequeue(CList *c)
{
    Node *const ret = c->first;
    if ((ret == NULL) || (c->len == 0))
        return NULL;

    c->first = ret->next;
    if (c->first == NULL)
        c->last = NULL;

    _clist_append(c, ret);
    c->len--;
    return ret;
}


static void
_clist_append(CList *c, Node *new_node)
{
    new_node->next = c->resv;
    c->resv = new_node;
}


static Node *
_clist_pop(CList *c)
{
    Node *const ret = c->resv;
    if (ret != NULL)
        c->resv = ret->next;

    return ret;
}


static void
_clist_destroy(CList *c)
{
    Node *node;
    while ((node = _clist_pop(c)) != NULL)
        free(node);

    c->resv = NULL;
}


// test
static void
func(void *v)
{
    printf("%p: %d\n", v, *((int *)v));
}


static void
test0(void)
{
    CList list;
    if (clist_init(&list, 1, 100) < 0)
        return;
    
    int arr[10];
    for (int i = 0; i < 10; i++)
        arr[i] = i;

    for (int i = 0; i < 10; i ++)
        clist_queue(&list, func, &arr[i]);

    Node *n = clist_dequeue(&list);
    if (n != NULL)
        n->func(n->udata);

    n = clist_dequeue(&list);
    if (n != NULL)
        n->func(n->udata);

    n = clist_dequeue(&list);
    if (n != NULL)
        n->func(n->udata);

    n->func = NULL;
    n->udata = NULL;

    n = clist_dequeue(&list);
    if (n != NULL)
        n->func(n->udata);

    n = clist_dequeue(&list);
    if (n != NULL)
        n->func(n->udata);

    for (int i = 0; i < 5; i ++)
        clist_queue(&list, func, &arr[i]);

    n = clist_dequeue(&list);
    if (n != NULL)
        n->func(n->udata);

    n = clist_dequeue(&list);
    if (n != NULL)
        n->func(n->udata);

    printf("len: %zu, cap: %zu, max: %zu\n", list.len, list.cap, list.max_cap);
    clist_deinit(&list);
}


int
main(void)
{
    test0();
    return 0;
}