queue_vs_recursion.c

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

typedef struct data {
    int flag;
    struct data *next;
} data_t;

static data_t *top = NULL;
static data_t *cur = NULL;
static data_t *queue[100000];
static int queue_idx = 0;

void
setup_datas(void)
{
    int i;
    data_t *p;
    for (i = 0; i < 255; i++) {
        p = (data_t *)malloc(sizeof(data_t));
        memset(p, 0, sizeof(p));
        p->next = top;
        top = p;
    }
}

void
mark_by_queue(void)
{
    data_t *p;

    queue[0] = top;
    queue_idx = 1;

    while (queue_idx > 0) {
        p = queue[--queue_idx];
        p->flag = 0;
        if (p->next != NULL) {
            queue[queue_idx] = p->next;
            queue_idx++;
        }
    }
}

void
mark_by_recusion(data_t *p)
{
    if (p != NULL) {
        p->flag = 0;
        mark_by_recusion(p->next);
    }
}

void
main(void)
{
    int i;
    setup_datas();

    for (i = 0; i < 5000000; i++) {
        mark_by_recusion(top);
        //mark_by_queue();
    }
}