Skip to content

Instantly share code, notes, and snippets.

@jaspervdj
Created July 11, 2010 13:06
Show Gist options
  • Save jaspervdj/471529 to your computer and use it in GitHub Desktop.
Save jaspervdj/471529 to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment