Mercurial > hg > th-libs
view th_datastruct.c @ 761:2263dd13cf2d
Cleanup.
author | Matti Hamalainen <ccr@tnsp.org> |
---|---|
date | Sun, 05 Feb 2023 19:40:14 +0200 |
parents | 618c7fa3a4f8 |
children |
line wrap: on
line source
/* * Various data structure functions * Programmed and designed by Matti 'ccr' Hamalainen * (C) Copyright 2002-2022 Tecnic Software productions (TNSP) * * Please read file 'COPYING' for information on license and distribution. */ #include "th_datastruct.h" /* * Doubly linked list handling * * In this implementation first node's prev points to last node of the list, * and last node's next is NULL. This way we can semi-efficiently traverse to * beginning and end of the list, assuming user does not do weird things. */ th_llist_t * th_llist_new(void *data) { th_llist_t *res = th_malloc0(sizeof(th_llist_t)); res->data = data; return res; } void th_llist_free_func_node(th_llist_t *list, void (*freefunc)(th_llist_t *)) { th_llist_t *curr = list; while (curr != NULL) { th_llist_t *next = curr->next; freefunc(curr); curr = next; } } void th_llist_free_func_data(th_llist_t *list, void (*freefunc)(void *data)) { th_llist_t *curr = list; while (curr != NULL) { th_llist_t *next = curr->next; if (curr->data != NULL) freefunc(curr->data); th_free(curr); curr = next; } } void th_llist_free(th_llist_t *list) { th_llist_t *curr = list; while (curr != NULL) { th_llist_t *next = curr->next; th_free(curr); curr = next; } } void th_llist_append_node(th_llist_t **list, th_llist_t *node) { if (*list != NULL) { node->prev = (*list)->prev; (*list)->prev->next = node; (*list)->prev = node; (*list)->num++; } else { *list = node; node->prev = node; (*list)->num = 1; } node->next = NULL; } th_llist_t *th_llist_append(th_llist_t **list, void *data) { th_llist_t *node = th_llist_new(data); th_llist_append_node(list, node); return node; } void th_llist_prepend_node(th_llist_t **list, th_llist_t *node) { if (*list != NULL) { node->prev = (*list)->prev; node->next = *list; (*list)->prev = node; node->num = (*list)->num + 1; *list = node; } else { *list = node->prev = node; node->next = NULL; (*list)->num = 1; } } th_llist_t *th_llist_prepend(th_llist_t **list, void *data) { th_llist_t *node = th_llist_new(data); th_llist_prepend_node(list, node); return node; } /* 1) Remove a middle node node0->prev->next = node->next (node1) node0->next->prev = node->prev (list) node2 <- list <=> node0 <=> node1 <=> node2 -> NULL node2 <- list <=> node1 <=> node2 -> NULL 2) Remove first node when many items node2 <- list <=> node0 <=> node1 <=> node2 -> NULL node2 <- node0 <=> node1 <=> node2 -> NULL *list = node0 3) Remove last node in list if (node->next == NULL) { list->prev = node->prev; node->prev->next = NULL; } node2 <- list <=> node0 <=> node1 <=> node2 -> NULL node1 <- list <=> node0 <=> node1 -> NULL 4) Remove last list <- list -> NULL */ void th_llist_delete_node(th_llist_t **list, th_llist_t *node) { if (node == *list) { // First node in list th_llist_t *tmp = (*list)->next; if (tmp != NULL) { tmp->num = (*list)->num - 1; tmp->prev = (*list)->prev; } *list = tmp; } else { // Somewhere in middle or end if (node->prev != NULL) node->prev->next = node->next; if (node->next != NULL) node->next->prev = node->prev; else (*list)->prev = node; // Last node (*list)->num--; } node->next = node->prev = NULL; } th_llist_t * th_llist_get_nth(th_llist_t *list, const size_t n) { th_llist_t *curr = list; size_t i; for (i = 0; curr != NULL && i < n; curr = curr->next, i++); return (i == n) ? curr : NULL; } size_t th_llist_length(const th_llist_t *list) { return (list == NULL) ? 0 : list->num; } size_t th_llist_length_slow(const th_llist_t *list) { const th_llist_t *curr = list; size_t i; for (i = 0; curr != NULL; curr = curr->next, i++); return i; } ssize_t th_llist_position(const th_llist_t *list, const th_llist_t *node) { const th_llist_t *curr = list; ssize_t i = 0; while (curr != NULL) { if (curr == node) return i; else i++; curr = curr->next; } return -1; } void th_llist_reverse(th_llist_t **list) { th_llist_t *f_curr = *list, *f_prev = NULL, *b_curr = *list, *b_prev = NULL; size_t count = 0; // NULL list? if (f_curr == NULL) return; // Set initial previous backward pointer if (b_curr != NULL) b_prev = b_curr->prev; // Reverse the list while (f_curr != NULL) { th_llist_t *f_next = f_curr->next, // next = current->next *b_next = b_curr->prev; count++; f_curr->num = 0; f_curr->next = f_prev; // current->next = previous f_prev = f_curr; // previous = current f_curr = f_next; // current = next b_curr->prev = b_prev; b_prev = b_curr; b_curr = b_next; } // Update count f_prev->num = count; // Set list pointer *list = f_prev; // Fix last previous pointer if (b_curr != NULL) b_curr->prev = b_prev; } void th_llist_foreach(th_llist_t *list, void (*func)(th_llist_t *node, void *userdata), void *data) { th_llist_t *curr = list; while (curr != NULL) { th_llist_t *next = curr->next; func(curr, data); curr = next; } } int th_llist_foreach_cond(th_llist_t *list, int (*func)(th_llist_t *node, void *userdata), void *data, th_llist_t **ret) { th_llist_t *curr = list; while (curr != NULL) { int res = func(curr, data); if (res != THERR_OK) { *ret = curr; return res; } curr = curr->next; } return THERR_OK; } th_llist_t * th_llist_find_data(th_llist_t *list, const void *data) { th_llist_t *curr = list; while (curr != NULL) { if (curr->data == data) return curr; curr = curr->next; } return NULL; } th_llist_t * th_llist_find_func(th_llist_t *list, const void *userdata, int (compare)(const void *, const void *)) { th_llist_t *curr = list; while (curr != NULL) { if (compare(curr->data, userdata) == 0) return curr; curr = curr->next; } return NULL; } static th_llist_t *th_llist_mergesort_merge(th_llist_t *left, th_llist_t *right, int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata), void *userdata) { th_llist_t *result; if (left == NULL) return right; else if (right == NULL) return left; if (compare(left, right, userdata)) { result = left; result->next = th_llist_mergesort_merge(left->next, right, compare, userdata); } else { result = right; result->next = th_llist_mergesort_merge(left, right->next, compare, userdata); } if (result->next != NULL) result->prev = result->prev; return result; } static void th_llist_mergesort_do(th_llist_t **list, int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata), void *userdata) { th_llist_t *head = *list, *left, *right, *slow, *fast; if (head == NULL || head->next == NULL) return; slow = head; fast = head->next; while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } left = head; right = slow->next; slow->next = NULL; th_llist_mergesort_do(&left, compare, userdata); th_llist_mergesort_do(&right, compare, userdata); *list = th_llist_mergesort_merge(left, right, compare, userdata); } void th_llist_mergesort(th_llist_t **list, int (compare)(const th_llist_t *lnode, const th_llist_t *rnode, void *userdata), void *userdata) { if (list != NULL && *list != NULL) { size_t num = (*list)->num; th_llist_mergesort_do(list, compare, userdata); (*list)->num = num; } } /* * Ringbuffers */ int th_ringbuf_init(th_ringbuf_t *buf, const size_t size, void (*mdeallocator)(void *data)) { memset(buf, 0, sizeof(*buf)); // Must have at least 2 elements if (size < 2) return THERR_BOUNDS; if ((buf->data = th_calloc(size, sizeof(void *))) == NULL) return THERR_MALLOC; buf->size = size; buf->n = 0; buf->deallocator = mdeallocator; return THERR_OK; } int th_ringbuf_new(th_ringbuf_t **buf, const size_t size, void (*mdeallocator)(void *data)) { int res; if ((*buf = th_malloc0(sizeof(th_ringbuf_t))) == NULL) return THERR_MALLOC; if ((res = th_ringbuf_init(*buf, size, mdeallocator)) != THERR_OK) { th_free(*buf); return res; } (*buf)->is_allocated = true; return THERR_OK; } int th_ringbuf_grow(th_ringbuf_t *buf, const size_t nadd) { if (buf == NULL) return THERR_NULLPTR; buf->data = (void **) th_realloc(buf->data, (buf->size + nadd) * sizeof(void *)); if (buf->data == NULL) return THERR_MALLOC; memset(buf->data + buf->size, 0, sizeof(void *) * nadd); buf->size += nadd; return THERR_OK; } void th_ringbuf_free(th_ringbuf_t *buf) { if (buf != NULL) { for (size_t i = 0; i < buf->size; i++) { buf->deallocator(buf->data[i]); } th_free(buf->data); if (buf->is_allocated) th_free(buf); } } void th_ringbuf_add(th_ringbuf_t *buf, void *ptr) { if (buf->n < buf->size) buf->n++; buf->deallocator(buf->data[0]); memmove(&(buf->data[0]), &(buf->data[1]), (buf->size - 1) * sizeof(void *)); buf->data[buf->size - 1] = ptr; } /* * Growing buffer */ void th_growbuf_clear(th_growbuf_t *buf) { // Simply reset the current "length" buf->len = 0; } void th_growbuf_init(th_growbuf_t *buf, const size_t mingrow) { // Initialize the buffer structure memset(buf, 0, sizeof(th_growbuf_t)); buf->mingrow = mingrow; } th_growbuf_t *th_growbuf_new(const size_t mingrow) { th_growbuf_t *buf; if ((buf = th_malloc(sizeof(th_growbuf_t))) == NULL) return NULL; th_growbuf_init(buf, mingrow); buf->is_allocated = true; return buf; } void th_growbuf_free(th_growbuf_t *buf) { if (buf != NULL) { th_free(buf->data); if (buf->is_allocated) th_free(buf); } } bool th_growbuf_grow(th_growbuf_t *buf, const size_t amount) { if (buf == NULL) return false; if (buf->data == NULL || buf->len + amount >= buf->size) { buf->size += amount + (buf->mingrow > 0 ? buf->mingrow : TH_BUFGROW); if ((buf->data = th_realloc(buf->data, buf->size)) == NULL) return false; } return true; } bool th_growbuf_puts(th_growbuf_t *buf, const char *str, bool eos) { size_t slen; if (str == NULL) return false; slen = strlen(str); if (!th_growbuf_grow(buf, slen + 1)) return false; memcpy(buf->data + buf->len, str, slen + 1); buf->len += eos ? (slen + 1) : slen; return true; } bool th_growbuf_putch(th_growbuf_t *buf, const char ch) { if (!th_growbuf_grow(buf, sizeof(char))) return false; buf->data[buf->len++] = (uint8_t) ch; return true; } bool th_growbuf_put_str(th_growbuf_t *buf, const void *str, const size_t len) { if (str == NULL) return false; if (!th_growbuf_grow(buf, len + 1)) return false; memcpy(buf->data + buf->len, str, len + 1); buf->len += len; return true; } bool th_growbuf_put_u8(th_growbuf_t *buf, const uint8_t val) { if (!th_growbuf_grow(buf, sizeof(uint8_t))) return false; buf->data[buf->len++] = val; return true; } bool th_growbuf_put_u16_be(th_growbuf_t *buf, const uint16_t val) { if (!th_growbuf_grow(buf, sizeof(uint16_t))) return false; buf->data[buf->len++] = (val >> 8) & 0xff; buf->data[buf->len++] = val & 0xff; return true; } bool th_growbuf_put_u16_le(th_growbuf_t *buf, const uint16_t val) { if (!th_growbuf_grow(buf, sizeof(uint16_t))) return false; buf->data[buf->len++] = val & 0xff; buf->data[buf->len++] = (val >> 8) & 0xff; return true; } bool th_growbuf_put_u32_be(th_growbuf_t *buf, const uint32_t val) { if (!th_growbuf_grow(buf, sizeof(uint32_t))) return false; buf->data[buf->len++] = (val >> 24) & 0xff; buf->data[buf->len++] = (val >> 16) & 0xff; buf->data[buf->len++] = (val >> 8) & 0xff; buf->data[buf->len++] = val & 0xff; return true; } bool th_growbuf_put_u32_le(th_growbuf_t *buf, const uint32_t val) { if (!th_growbuf_grow(buf, sizeof(uint32_t))) return false; buf->data[buf->len++] = val & 0xff; buf->data[buf->len++] = (val >> 8) & 0xff; buf->data[buf->len++] = (val >> 16) & 0xff; buf->data[buf->len++] = (val >> 24) & 0xff; return true; } /* * Simple legacy string growing buffer */ bool th_strbuf_grow(char **buf, size_t *bufsize, size_t *len, size_t grow) { if (*buf == NULL) *bufsize = *len = 0; if (*buf == NULL || *len + grow >= *bufsize) { *bufsize += grow + TH_BUFGROW; *buf = th_realloc(*buf, *bufsize); if (*buf == NULL) return false; } return true; } bool th_strbuf_putch(char **buf, size_t *bufsize, size_t *len, const uint8_t ch) { if (!th_strbuf_grow(buf, bufsize, len, 1)) return false; (*buf)[*len] = ch; (*len)++; return true; } bool th_strbuf_putsn(char **buf, size_t *bufsize, size_t *len, const char *str, const size_t slen) { if (str == NULL) return false; if (!th_strbuf_grow(buf, bufsize, len, slen + 1)) return false; memcpy(*buf + *len, str, slen); (*len) += slen; *(buf + *len + slen) = 0; return true; } bool th_strbuf_puts(char **buf, size_t *bufsize, size_t *len, const char *str) { size_t slen; if (str == NULL) return false; slen = strlen(str); if (!th_strbuf_grow(buf, bufsize, len, slen + 1)) return false; memcpy(*buf + *len, str, slen + 1); (*len) += slen; return true; } int th_ptrlist_init(th_ptrlist_t *list, const size_t ninitial, const size_t ngrow) { if (list == NULL) return THERR_NULLPTR; memset(list, 0, sizeof(*list)); if (ngrow == 0) return THERR_INVALID_ARGS; list->nitems = 0; list->nallocated = ninitial; list->ngrow = ngrow; if ((list->items = th_malloc(list->nallocated * sizeof(void *))) == NULL) return THERR_MALLOC; return THERR_OK; } int th_ptrlist_new(th_ptrlist_t **list, const size_t ninitial, const size_t ngrow) { int res; if (list == NULL) return THERR_NULLPTR; if ((*list = th_malloc0(sizeof(th_ptrlist_t))) == NULL) return THERR_MALLOC; if ((res = th_ptrlist_init(*list, ninitial, ngrow)) != THERR_OK) { th_free(*list); return res; } (*list)->is_allocated = true; return THERR_OK; } int th_ptrlist_append(th_ptrlist_t *list, void *data) { if (list == NULL) return THERR_NULLPTR; if (list->nitems + 1 >= list->nallocated) { list->nallocated += list->ngrow; if ((list->items = th_realloc(list->items, list->nallocated * sizeof(void *))) == NULL) return THERR_MALLOC; } list->items[list->nitems++] = data; return THERR_OK; } void th_ptrlist_free(th_ptrlist_t *list, void (*mdeallocator)(void *data)) { if (list != NULL) { if (mdeallocator != NULL) { for (size_t i = 0; i < list->nitems; i++) mdeallocator(list->items[i]); } th_free(list->items); if (list->is_allocated) th_free(list); } }