data_structures

data structures in C
Log | Files | Refs | Feed

commit 7ac9b49a4438693a9473b5d0e73a3e5809afb177
parent adfbbda42700db88028faf9f010732f8767b68c1
Author: Jenny Doe <tng@soykaf.me>
Date:   Fri, 22 Mar 2019 15:03:50 +0100

added: sets

Diffstat:
Aset.c | 69+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aset.h | 28++++++++++++++++++++++++++++
Aset_test.c | 66++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 163 insertions(+), 0 deletions(-)

diff --git a/set.c b/set.c @@ -0,0 +1,69 @@ +#include "list.h" +#include "set.h" + +#define NULL ((void *)0) + +void +set_init(Set * set, + int (*match) (const void *, const void *), + void (*destroy) (void *)) +{ + set->match = match; + set->set->destroy = destroy; + set->set->size = 0; + set->set->head = NULL; + set->set->tail = NULL; + + return; +} + +void +set_destroy(Set * set) +{ + list_destroy(set->set); + + return; +} + +int +set_insert(Set * set, const void *data) +{ + if (set_is_member(set, data) == 1) /* not found */ + return list_ins_next(set->set, NULL, data); + + return (0); /* fail transparently */ +} + +int +set_remove(Set * set, void **data) +{ + if (set->set->size <= 0) + return (1); + + SetElmt *t = set->set->head; + if (set->match(t->data, *data)) { + return list_rem_next(set->set, NULL, data); + } + + while ((t = t->next) != NULL) { + if (set->match(t->next->data, *data)) + return list_rem_next(set->set, t, data); + } + + return (1); +} + +int +set_is_member(Set * set, const void *data) +{ + if (set->set->size == 0) /* empty list */ + return (1); + + SetElmt *t = set->set->head; + do { + if (set->match(t->data, data) == 0) + return (0); + } while ((t = t->next) != NULL); + + return (1); +} diff --git a/set.h b/set.h @@ -0,0 +1,28 @@ +#pragma once + +#include "list.h" + +struct Set_ { + int (*match) (const void *, const void *); + + /* ugly but i didn't feel like rewriting everything */ + List *set; +}; + +typedef struct Set_ Set; +typedef ListElmt SetElmt; + +void set_init(Set *, int (*) (const void *, const void *), + void (*) (void *)); +void set_destroy(Set *); + +int set_insert(Set *, const void *); +int set_remove(Set *, void **); + +int set_union(Set *, const Set *, const Set *); +int set_intersection(Set *, const Set *, const Set *); +int set_difference(Set *, const Set *, const Set *); + +int set_is_member(Set *, const void *); +int set_is_subset(const Set *, const Set *); +int set_is_equal(const Set *, const Set *); diff --git a/set_test.c b/set_test.c @@ -0,0 +1,66 @@ +#include <stdio.h> +#include <stdlib.h> + +#include "list.h" +#include "set.h" + +int +char_match(const void *c1, const void *c2) +{ + return (*(const char *)c1 == *(const char *)c2) ? 0 : 1; +} + +int +main(void) +{ + char t[10] = "abc"; + + Set *my_set = malloc(sizeof(Set)); + if (my_set == NULL) { + fprintf(stderr, "Failed to allocate memory!\n"); + return (1); + } + + my_set->set = malloc(sizeof(List)); + if (my_set->set == NULL) { + fprintf(stderr, "Failed to allocate memory!\n"); + return (1); + } + + set_init(my_set, char_match, NULL); + + set_insert(my_set, &t[0]); /* push 'a' */ + list_ins_next(my_set->set, NULL, &t[0]); + + set_insert(my_set, &t[1]); /* push 'b' */ + set_insert(my_set, &t[2]); /* push 'c' */ + + set_insert(my_set, &t[0]); /* push 'a' */ + + /* easier than checking return value */ + if (my_set->set->size != 3) { + fprintf(stderr, "Failed to insert some element in my_set!\n"); + return (1); + } + + printf("head=%p data='%c'\n", + my_set->set->head, *(char *)my_set->set->head->data); + + for (SetElmt * tmp = my_set->set->head; tmp != NULL; + tmp = tmp->next) { + + printf("data='%c', current=%p, next=%p\n", + *(char *)tmp->data, tmp, tmp->next); + } + + printf("tail=%p data='%c'\n", + my_set->set->tail, *(char *)my_set->set->tail->data); + + set_destroy(my_set); + if (my_set->set->size != 0) { + fprintf(stderr, "Failed to destroy my_set!\n"); + return (1); + } + + return (0); +}