data_structures

data structures in C
Log | Files | Refs | Feed

commit aaa9b305c81c5e52ab7c44e438abf24a41d08f1f
parent 9934e2c3ee88670ece5520b8d61ed2977e17c99a
Author: Jenny Doe <tng@soykaf.me>
Date:   Thu, 21 Mar 2019 22:54:49 +0100

added: circular lists

Diffstat:
Aclist.c | 90+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Aclist.h | 30++++++++++++++++++++++++++++++
Aclist_test.c | 50++++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 170 insertions(+), 0 deletions(-)

diff --git a/clist.c b/clist.c @@ -0,0 +1,90 @@ +#include <stdlib.h> +#include <limits.h> + +#include "clist.h" + +#define NULL ((void *)0) + +void +clist_init(cList * list, void (*destroy)(void *)) +{ + list->destroy = NULL; + list->size = 0; + list->head = NULL; + + return; +} + + +void +clist_destroy(cList * list) +{ + void *data; + + while (list->size > 0 && clist_rem_next(list, list->head, &data) == 0) { + if (list->destroy != NULL) + list->destroy(data); + } + + /* list->size == 0 on success */ + + return; +} + + +int +clist_ins_next(cList * list, cListElmt * left, void *data) +{ + /* silently fail */ + if (list->size == UINT_MAX - 1) { + return (1); + } + + cListElmt *new_element = malloc(sizeof(cListElmt)); + if (new_element == NULL) + return (1); + + new_element->data = data; + + if (list->size == 0) { /* insert head */ + list->head = new_element; + list->head->next = list->head; + } else { /* insert after `left` */ + new_element->next = left->next; + left->next = new_element; + } + + ++(list->size); + + return (0); +} + +int +clist_rem_next(cList * list, cListElmt * left, void **data) +{ + cListElmt *old; + + if (list->size == 0) + return (1); + + if (list->size == 1) { /* remove head */ + old = list->head; + + list->head = NULL; + } else { /* remove after `left` */ + old = left->next; + + left->next = left->next->next; + + if (old == list->head) + list->head = left->next; /* or left idk */ + } + + *data = old->data; + + free(old); + + --(list->size); + + return (0); +} diff --git a/clist.h b/clist.h @@ -0,0 +1,30 @@ +#pragma once + +struct cListElmt_ { + void *data; + struct cListElmt_ *next; +}; + +struct cList_ { + void (*destroy) (void *); + unsigned int size; + struct cListElmt_ *head; +}; + + +/* for convenience */ +typedef struct cListElmt_ cListElmt; +typedef struct cList_ cList; + + +/* cannot fail */ +void clist_init(cList *, void (*) (void *)); + +/* can fail */ +void clist_destroy(cList *); + +/* returns 0 on success, 1 when malloc fail */ +int clist_ins_next(cList *, cListElmt *, void *); + +/* returns 0 on success, 1 if list's size is 0 */ +int clist_rem_next(cList *, cListElmt *, void **); diff --git a/clist_test.c b/clist_test.c @@ -0,0 +1,50 @@ +#include <stdio.h> +#include <stdlib.h> + +#include "clist.h" + +int +main(void) +{ + char *t = "abc"; + + cList *my_list = malloc(sizeof(cList)); + if (my_list == NULL) { + fprintf(stderr, "Failed to allocate memory!\n"); + return (1); + } + + clist_init(my_list, NULL); + + clist_ins_next(my_list, NULL, &t[0]); /* push 'a' */ + clist_ins_next(my_list, my_list->head, &t[1]); /* push 'b' */ + clist_ins_next(my_list, my_list->head, &t[2]); /* push 'c' */ + + clist_ins_next(my_list, my_list->head, &t[2]); /* push 'c' */ + + void * dummy; + clist_rem_next(my_list, my_list->head, &dummy); + + /* easier than checking return value */ + if (my_list->size != 3) { + fprintf(stderr, "Failed to insert some element in my_list!\n"); + return (1); + } + + printf("head=%p data='%c'\n", + my_list->head, *(char *)my_list->head->data); + + cListElmt *tmp = my_list->head; + do { + printf("data='%c', current=%p, next=%p\n", + *(char *)tmp->data, tmp, tmp->next); + } while ((tmp = tmp->next) != my_list->head); + + clist_destroy(my_list); + if (my_list->size != 0) { + fprintf(stderr, "Failed to destroy my_list!\n"); + return (1); + } + + return (0); +}