data_structures

data structures in C
Log | Files | Refs | Feed

commit 4b7dd718a203b7f204691c628573b0b32aa5f91d
Author: Jenny Doe <tng@soykaf.me>
Date:   Thu, 21 Mar 2019 19:59:59 +0100

birthday!

Diffstat:
Adlist.c | 111+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Adlist.h | 32++++++++++++++++++++++++++++++++
Adlist_test.c | 62++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Alist.c | 89+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Alist.h | 31+++++++++++++++++++++++++++++++
Alist_test.c | 54++++++++++++++++++++++++++++++++++++++++++++++++++++++
6 files changed, 379 insertions(+), 0 deletions(-)

diff --git a/dlist.c b/dlist.c @@ -0,0 +1,111 @@ +#include <stdlib.h> +#include <limits.h> + +#include "dlist.h" + +#define NULL ((void *)0) + +void +dlist_init(dList * list, void (*destroy) (void *)) +{ + list->destroy = NULL; + list->size = 0; + list->head = NULL; + list->tail = NULL; + + return; +} + + +void +dlist_destroy(dList * list) +{ + void *data; + + while (list->size > 0 && dlist_remove(list, list->head, &data) == 0) { + if (list->destroy != NULL) + list->destroy(data); + } + + /* list->size == 0 on success */ + + return; +} + + +int +dlist_ins_next(dList * list, dListElmt * left, void *data) +{ + /* silently fail */ + if (list->size == UINT_MAX - 1) { + return (1); + } + + dListElmt *new_element = malloc(sizeof(dListElmt)); + if (new_element == NULL) + return (1); + + new_element->data = data; + + if (list->size == 0) { /* insert head */ + new_element->next = NULL; + new_element->prev = NULL; + + list->head = new_element; + list->tail = new_element; + } else { /* insert after `left` */ + new_element->next = left->next; + new_element->prev = left; + + left->next = new_element; + + if (new_element->next != NULL) + new_element->next->prev = new_element; + else + list->tail = new_element; + } + + ++(list->size); + + return (0); +} + +int +dlist_remove(dList * list, dListElmt * to_remove, void **data) +{ + dListElmt *old; + + if (list->size == 0) + return (1); + + if (list->size == 1) { + old = list->head; + + list->head = NULL; + list->tail = NULL; + } else { + + if (to_remove == NULL) + old = list->head; + else + old = to_remove; + + if (old->next == NULL) + list->tail = old->prev; + else + old->next->prev = old->prev; + + if (old->prev == NULL) + list->head = old->next; + else + old->prev->next = old->next; + } + + *data = old->data; + + free(old); + + --(list->size); + + return (0); +} diff --git a/dlist.h b/dlist.h @@ -0,0 +1,32 @@ +#pragma once + +struct dListElmt_ { + void *data; + struct dListElmt_ *prev; + struct dListElmt_ *next; +}; + +struct dList_ { + void (*destroy) (void *); + unsigned int size; + struct dListElmt_ *head; + struct dListElmt_ *tail; +}; + + +/* for convenience */ +typedef struct dListElmt_ dListElmt; +typedef struct dList_ dList; + + +/* cannot fail */ +void dlist_init(dList *, void (*) (void *)); + +/* can fail */ +void dlist_destroy(dList *); + +/* returns 0 on success, 1 when malloc fail */ +int dlist_ins_next(dList *, dListElmt *, void *); + +/* returns 0 on success, 1 if list's size is 0 */ +int dlist_remove(dList *, dListElmt *, void **); diff --git a/dlist_test.c b/dlist_test.c @@ -0,0 +1,62 @@ +#include <stdio.h> +#include <stdlib.h> + +#include "dlist.h" + +int +main(void) +{ + char *t = "abc"; + char *u = "xyz"; + + dList *my_list = malloc(sizeof(dList)); + if (my_list == NULL) { + fprintf(stderr, "Failed to allocate memory!\n"); + return (1); + } + + dlist_init(my_list, NULL); + + dlist_ins_next(my_list, NULL, &t[0]); /* push 'a' */ + + dlist_ins_next(my_list, my_list->head, &t[0]); /* push 'a' */ + dlist_ins_next(my_list, my_list->head, &t[1]); /* push 'b' */ + dlist_ins_next(my_list, my_list->head, &t[2]); /* push 'c' */ + + dlist_ins_next(my_list, my_list->tail, &u[0]); /* queue 'x' */ + dlist_ins_next(my_list, my_list->tail, &u[1]); /* queue 'y' */ + dlist_ins_next(my_list, my_list->tail, &u[2]); /* queue 'z' */ + + dlist_ins_next(my_list, my_list->tail, &u[2]); /* queue 'z' */ + + void *dummy; + dlist_remove(my_list, my_list->head, &dummy); + dlist_remove(my_list, my_list->tail, &dummy); + + /* easier than checking return value */ + if (my_list->size != 6) { + 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); + + for (dListElmt * tmp = my_list->head; tmp != NULL; + tmp = tmp->next) { + + printf("data='%c', prev=%p, current=%p, next=%p\n", + *(char *)tmp->data, tmp->prev, tmp, tmp->next); + } + + printf("tail=%p data='%c'\n", + my_list->tail, *(char *)my_list->tail->data); + + dlist_destroy(my_list); + if (my_list->size != 0) { + fprintf(stderr, "Failed to destroy my_list!\n"); + return (1); + } + + return (0); +} diff --git a/list.c b/list.c @@ -0,0 +1,89 @@ +#include <stdlib.h> +#include <limits.h> + +#include "list.h" + +#define NULL ((void *)0) + +void +list_init(List * list, void (*destroy)(void *)) +{ + list->destroy = NULL; + list->size = 0; + list->head = NULL; + list->tail = NULL; + + return; +} + + +void +list_destroy(List * list) +{ + void *data; + + while (list->size > 0 && list_rem_next(list, NULL, &data) == 0) { + if (list->destroy != NULL) + list->destroy(data); + } + + /* list->size == 0 on success */ + + return; +} + + +int +list_ins_next(List * list, ListElmt * left, void *data) +{ + /* silently fail */ + if (list->size == UINT_MAX - 1) { + return (1); + } + + ListElmt *new_element = malloc(sizeof(ListElmt)); + if (new_element == NULL) + return (1); + + new_element->data = data; + + if (left == NULL) { /* insert head */ + new_element->next = list->head; + list->head = new_element; + } else { /* insert after `left` */ + new_element->next = left->next; + left->next = new_element; + } + + if (new_element->next == NULL) + list->tail = new_element; + + ++(list->size); + + return (0); +} + +int +list_rem_next(List * list, ListElmt * left, void **data) +{ + ListElmt *old; + + if (list->size == 0) + return (1); + + if (left == NULL) { /* remove head */ + old = list->head; + list->head = list->head->next; + } else { /* remove after `left` */ + old = left->next; + left->next = left->next->next; + } + + *data = old->data; + + free(old); + + --(list->size); + + return (0); +} diff --git a/list.h b/list.h @@ -0,0 +1,31 @@ +#pragma once + +struct ListElmt_ { + void *data; + struct ListElmt_ *next; +}; + +struct List_ { + void (*destroy) (void *); + unsigned int size; + struct ListElmt_ *head; + struct ListElmt_ *tail; +}; + + +/* for convenience */ +typedef struct ListElmt_ ListElmt; +typedef struct List_ List; + + +/* cannot fail */ +void list_init(List *, void (*) (void *)); + +/* can fail */ +void list_destroy(List *); + +/* returns 0 on success, 1 when malloc fail */ +int list_ins_next(List *, ListElmt *, void *); + +/* returns 0 on success, 1 if list's size is 0 */ +int list_rem_next(List *, ListElmt *, void **); diff --git a/list_test.c b/list_test.c @@ -0,0 +1,54 @@ +#include <stdio.h> +#include <stdlib.h> + +#include "list.h" + +int +main(void) +{ + char *t = "abc"; + char *u = "xyz"; + + List *my_list = malloc(sizeof(List)); + if (my_list == NULL) { + fprintf(stderr, "Failed to allocate memory!\n"); + return (1); + } + + list_init(my_list, NULL); + + list_ins_next(my_list, NULL, &t[0]); /* push 'a' */ + list_ins_next(my_list, NULL, &t[1]); /* push 'b' */ + list_ins_next(my_list, NULL, &t[2]); /* push 'c' */ + + list_ins_next(my_list, my_list->tail, &u[0]); /* queue 'x' */ + list_ins_next(my_list, my_list->tail, &u[1]); /* queue 'y' */ + list_ins_next(my_list, my_list->tail, &u[2]); /* queue 'z' */ + + /* easier than checking return value */ + if (my_list->size != 6) { + 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); + + for (ListElmt * tmp = my_list->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_list->tail, *(char *)my_list->tail->data); + + list_destroy(my_list); + if (my_list->size != 0) { + fprintf(stderr, "Failed to destroy my_list!\n"); + return (1); + } + + return (0); +}