[ create a new paste ] login | about

Link: http://codepad.org/QTR0m3yY    [ raw code | output | fork | 1 comment ]

johannes - C, pasted on Dec 7:
#include <assert.h>
#include <malloc.h>
#include <memory.h>
#include <stdlib.h>
#include <string.h>

typedef struct _node node;
typedef struct _cyclist cyclist;

cyclist *    cyclist_new                ();
void         cyclist_free               (cyclist *d);
void         cyclist_insert             (cyclist *d, void *data, size_t size);
void         cyclist_insert_first       (cyclist *d, void *data, size_t size);
void         cyclist_traverse_once      (cyclist *d, void (* f) (node *));
void         cyclist_traverse_n         (cyclist *d, void (* f) (node *), unsigned int n); 
void         cyclist_traverse_n_reverse (cyclist *d, void (* f) (node *), unsigned int n); 
void *       cyclist_node               (cyclist *d, unsigned int n);
void *       cyclist_take_node          (cyclist *d, unsigned int n);
void         cyclist_delete_node        (cyclist *d, unsigned int n);
unsigned int cyclist_size               (cyclist *d);

void         cyclist_run_tests          ();

struct _node
{
    node *next;
    node *prev;
    void *data;
};

struct _cyclist
{
    unsigned int count;
    node *first;
};

/* Allocate a new, empty doubly-linked list structure. */
cyclist *
cyclist_new ()
{
    cyclist *d;
    d = malloc (sizeof (cyclist));

    if (NULL != d) {
        d->first = NULL;
        d->count = 0;
    }
    return d;
}

/* Destroy a list and release all its associated resources. */
void
cyclist_free (cyclist *d)
{
    node *n, 
         *q;

    q = NULL;
    n = d->first;
    while (q != d->first) {
        q = n->next;
        free (n->data);
        free (n);
        n = q;
    }

    /* Lastly, free the struct itself */
    free (d);
}

/* Insert a new node at the end of a list. */
void
cyclist_insert (cyclist *d, 
                void    *data, 
                size_t   size)
{
    node *n;
    void *p;

    if (NULL == (p = malloc (size)))
        return;

    /* Copy the data element */
    memcpy (p, data, size);

    /* Allocate the node */
    if ((n = malloc (sizeof (node)))) {
        n->data = p;

        if (d->first != NULL) {
            n->next = d->first;
            n->prev = d->first->prev;
            d->first->prev->next = n;
            d->first->prev = n;
        } else {
            /* We are inserting into an empty list */
            n->prev = n->next = n;
            d->first = n;
        }
    
        ++d->count;
    }
}

/* Insert a new node at the beginning of a list. */
void
cyclist_insert_first (cyclist *d, 
                      void    *data, 
                      size_t   size)
{
    cyclist_insert (d, data, size);

    if (d->first != NULL) {
        d->first = d->first->prev;
    }
}

/* Traverse a list once (from start to end) using the provided callback. */
void
cyclist_traverse_once (cyclist *d, void (* f) (node *)) 
{
    node *n; 

    n = d->first;
    while (n != NULL) {
        f (n);
        if ((n = n->next) == d->first) {
            n = NULL;
        }
    }
}

/* Traverse a list by n elements, using the provided callback. Allow repetitions
 * if n is greater than the number of list entries.
 */
void
cyclist_traverse_n (cyclist *d, void (* f) (node *), unsigned int n) 
{
    node *x; 

    if ((x = d->first) == NULL)
        return;

    while (0 != n--) {
        f (x);
        x = x->next;
    }
}

/* Traverse a list by n elements in reverse order, using the provided callback. 
 * Allow repetitions if n is greater than the number of list entries.
 */
void
cyclist_traverse_n_reverse (cyclist *d, void (* f) (node *), unsigned int n) 
{
    node *x; 

    if (NULL == d->first || (x = d->first->prev) == NULL)
        return;

    while (0 != n--) {
        f (x);
        x = x->prev;
    }
}

/* Return a pointer to the data element of node n in the list. */
void *
cyclist_node (cyclist *d, unsigned int n)
{
    node *e;

    if (NULL == (e = d->first))
        return NULL;

    while (0 != n--) 
        e = e->next;

    return e->data;
}

/* Remove and return the nth element of a list. The caller becomes the new
 * owner of the node data pointee.
 */
void *
cyclist_take_node (cyclist *d, unsigned int n)
{
    node *e;
    void *v;

    if (NULL == (e = d->first))
        return NULL;

    while (0 != n--) {
        e = e->next;
    }

    if (1 == d->count) {
        d->first = NULL;
    } else {
        e->prev->next = e->next;
        e->next->prev = e->prev;
        if (d->first == e) { 
            d->first = e->next;
        }
    }
    --d->count;
    v = e->data;

    /* Release the node structure */
    free (e);

    return v;
}

/* Remove and delete the nth element of a list. */
void
cyclist_delete_node (cyclist *d, unsigned int n)
{
    free (cyclist_take_node (d, n));
}

unsigned int
cyclist_size (cyclist *d)
{
    return d->count;
}

#ifndef __strdup
/* When compiling in ANSI or C99 mode */
char *
strdup (const char *s)
{
    size_t len;
    void *new;

    len = strlen (s) + 1;
    new = malloc (len);

    if (NULL == new)
        return NULL; 

    return (char *) memcpy (new, s, len);
}
#endif

static void
add_str (cyclist *d, char *s)
{
    char *str;
    str = strdup (s);
    cyclist_insert (d, str, strlen (str) + 1);
}

static void
cyclist_test_take_node ()
{
    cyclist *c;
    char *str;

    c = cyclist_new ();

    add_str (c, "KenKen");
    add_str (c, "Calcudoku");
    add_str (c, "Kendoku");
    add_str (c, "Sumdoku");
    add_str (c, "Rekendoku");

    str = cyclist_take_node (c, 2);
    assert (0 == strcmp (str, "Kendoku"));
    
    free (str);

    assert (4 == cyclist_size (c));

    cyclist_free (c);
}

static void
cyclist_test_insert ()
{
    cyclist *c;
    int n;

    c = cyclist_new ();

    n = 1;
    cyclist_insert (c, &n, sizeof (int));

    n = 2;
    cyclist_insert (c, &n, sizeof (int));

    n = 3;
    cyclist_insert (c, &n, sizeof (int));

    n = 4;
    cyclist_insert (c, &n, sizeof (int));

    assert (4 == cyclist_size (c));

    n = *((int *) cyclist_node (c, 2));
    assert (n == 3);

    n = *((int *) cyclist_node (c, 3));
    assert (n == 4);

    cyclist_free (c);
}

static void
cyclist_test_delete ()
{
    cyclist *c;
    int n;

    c = cyclist_new ();

    n = 1;
    cyclist_insert (c, &n, sizeof (int));

    n = 2;
    cyclist_insert (c, &n, sizeof (int));

    n = 3;
    cyclist_insert (c, &n, sizeof (int));

    n = 4;
    cyclist_insert (c, &n, sizeof (int));

    cyclist_delete_node (c, 1);
    cyclist_delete_node (c, 1);

    n = *((int *) cyclist_node (c, 0));
    assert (n == 1);

    n = *((int *) cyclist_node (c, 1));
    assert (n == 4);

    cyclist_free (c);
}

static void
cyclist_test_insert_first ()
{
    cyclist *c;
    int n;

    c = cyclist_new ();

    n = 1;
    cyclist_insert (c, &n, sizeof (int));

    n = 2;
    cyclist_insert (c, &n, sizeof (int));

    n = 3;
    cyclist_insert (c, &n, sizeof (int));

    n = 4;
    cyclist_insert (c, &n, sizeof (int));

    cyclist_delete_node (c, 1);
    cyclist_delete_node (c, 1);

    n = 5;
    cyclist_insert_first (c, &n, sizeof (int));

    n = 6;
    cyclist_insert_first (c, &n, sizeof (int));

    n = *((int *) cyclist_node (c, 0));
    assert (n == 6);

    n = *((int *) cyclist_node (c, 1));
    assert (n == 5);

    cyclist_free (c);
}

void
cyclist_run_tests ()
{
    cyclist_test_take_node ();
    cyclist_test_insert ();
    cyclist_test_delete ();
    cyclist_test_insert_first ();
}

int main (void)
{
    cyclist_run_tests ();
    printf ("All systems are go.\n");

    return 0;
}


Output:
1
All systems are go.


Create a new paste based on this one


Comments:
posted by johannes on Dec 7
Circular doubly-linked list (ANSI C)
reply