marking.c

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

/* Data structure used for marking. */
typedef struct {
    /* Size of the universe. */
    int size;

    /* "Big" array, containing the entire universe. */
    int *array;

    /* A list structure containing all marks. */
    int *marks;

    /* Size of the mark list. */
    int marks_size;
} marking;

/* Allocate and initialize a new marking with the given size. */
marking *create_marking(int size) {
    marking *m = malloc(sizeof(marking));

    m->size = size;
    m->array = malloc(sizeof(int*) * size);
    m->marks = malloc(sizeof(int*) * size);
    m->marks_size = 0;

    return m;
}

/* Clean up a marking. */
void free_marking(marking *m) {
    free(m->array);
    free(m->marks);
    free(m);
}

/* Check if a given index is marked. */
int is_marked(marking *m, int index) {
    int mark_index = m->array[index];

    /* Check the connection. */
    return mark_index >= 0 &&
            mark_index < m->marks_size &&
            m->marks[mark_index] == index;
}

/* Set a mark at the given index. */
void mark(marking *m, int index) {
    /* Do not mark indices twice */
    if(is_marked(m, index)) return;

    /* Create a link in both directions. */
    m->marks[m->marks_size] = index;
    m->array[index] = m->marks_size++;
}

/* Example main function. */
int main(int argc, char **argv) {
    /* Initialize a marking. */
    marking *m = create_marking(200);
    int i;

    /* Set some marks. */
    for(i = 8; i < 200; i += 16) mark(m, i);

    /* Verify the set marks. */
    for(i = 0; i < 200; i++) {
        if(is_marked(m, i)) printf("%d is marked\n", i);
    }

    free_marking(m);
    return 0;
}