Created
April 13, 2012 14:51
-
-
Save marcomorain/2377413 to your computer and use it in GitHub Desktop.
A string set in C
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// gcc -std=c99 -Wall -Werror string_set.c && ./a.out | |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <string.h> | |
struct string_set* string_set_create(void); | |
void string_set_destroy(struct string_set* set); | |
int string_set_cardinality(struct string_set* set); | |
int string_set_contains(struct string_set* set, const char* string); | |
void string_set_add(struct string_set* set, const char* string); | |
void string_set_remove(struct string_set* set, char* string); | |
struct string_set* string_set_union(struct string_set* a, struct string_set* b); | |
typedef void (*string_set_iterator)(void* context, const char* string); | |
struct string_set_node | |
{ | |
char* data; | |
struct string_set_node* next; | |
}; | |
struct string_set | |
{ | |
struct string_set_node* head; | |
}; | |
static void iterate(struct string_set* set, string_set_iterator iterator, void* context) | |
{ | |
for(struct string_set_node* node = set->head; node; node = node->next) | |
iterator(context, node->data); | |
} | |
struct string_set* string_set_create(void) | |
{ | |
struct string_set* set = malloc(sizeof(struct string_set)); | |
set->head = NULL; | |
return set; | |
} | |
void string_set_destroy(struct string_set* set) | |
{ | |
for (struct string_set_node* node = set->head; node;) | |
{ | |
struct string_set_node* to_delete = node; | |
node = node->next; | |
free(to_delete->data); | |
free(to_delete); | |
} | |
} | |
int string_set_cardinality(struct string_set* set) | |
{ | |
int cardinality = 0; | |
for (struct string_set_node* node = set->head; node; node = node->next) | |
cardinality++; | |
return cardinality; | |
} | |
int string_set_contains(struct string_set* set, const char* string) | |
{ | |
for (struct string_set_node* node = set->head; node; node = node->next) | |
if (strcmp(string, node->data) == 0) | |
return 1; | |
return 0; | |
} | |
void string_set_add(struct string_set* set, const char* string) | |
{ | |
if (string_set_contains(set, string)) | |
return; | |
struct string_set_node* node = malloc(sizeof(struct string_set_node)); | |
node->data = strdup(string); | |
node->next = set->head; | |
set->head = node; | |
} | |
static struct string_set_node* without(struct string_set_node* list, char* string) | |
{ | |
// If the list is empty, return null | |
if (!list) return NULL; | |
// If the head of the list is the item, remove it | |
// This leaks the memory. | |
if (strcmp(list->data, string) == 0) | |
return without(list->next, string); | |
// Otherwise return the head and the processed tail | |
list->next = without(list->next, string); | |
return list; | |
} | |
void string_set_remove(struct string_set* set, char* string) | |
{ | |
set->head = without(set->head, string); | |
} | |
static void add_to_set(void* context, const char* data) | |
{ | |
struct string_set* target = context; | |
string_set_add(target, data); | |
} | |
struct string_set* string_set_union(struct string_set* a, struct string_set* b) | |
{ | |
struct string_set* result = string_set_create(); | |
iterate(result, add_to_set, a); | |
iterate(result, add_to_set, b); | |
return result; | |
} | |
struct string_set* string_set_intersection(struct string_set* a, struct string_set* b) | |
{ | |
struct string_set* result = string_set_create(); | |
for(struct string_set_node* node = a->head; node; node = node->next) | |
if (string_set_contains(b, node->data)) | |
string_set_add(result, node->data); | |
return result; | |
} | |
static int pass = 0; | |
static int fail = 0; | |
static void test(int expected, int actual, const char* file, int line) | |
{ | |
pass += expected == actual; | |
fail += expected != actual; | |
if (expected != actual) | |
printf("%s:%d Failure: expected: %d actual: %d\n", file, line, expected, actual); | |
} | |
#define TEST(expected, actual) (test((expected),(actual), __FILE__, __LINE__)) | |
int main(int argc, char** argv) | |
{ | |
struct string_set* set = string_set_create(); | |
TEST(0, string_set_cardinality(set)); | |
string_set_add(set, "foo"); | |
TEST(1, string_set_cardinality(set)); | |
string_set_add(set, "bar"); | |
TEST(2, string_set_cardinality(set)); | |
TEST(1, string_set_contains(set, "foo")); | |
TEST(1, string_set_contains(set, "bar")); | |
TEST(0, string_set_contains(set, "baz")); | |
string_set_remove(set, "foo"); | |
TEST(1, string_set_cardinality(set)); | |
TEST(0, string_set_contains(set, "foo")); | |
TEST(1, string_set_contains(set, "bar")); | |
TEST(0, string_set_contains(set, "baz")); | |
string_set_remove(set, "bar"); | |
TEST(0, string_set_cardinality(set)); | |
TEST(0, string_set_contains(set, "foo")); | |
TEST(0, string_set_contains(set, "bar")); | |
TEST(0, string_set_contains(set, "baz")); | |
string_set_add(set, "foobar"); | |
TEST(1, string_set_cardinality(set)); | |
TEST(1, string_set_contains(set, "foobar")); | |
string_set_add(set, "foobar"); | |
string_set_add(set, "foobar"); | |
string_set_add(set, "foobar"); | |
TEST(1, string_set_cardinality(set)); | |
string_set_destroy(set); | |
printf("Pass: %d Fail: %d\n", pass, fail); | |
return fail != 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment