commit 80b2c917096e504561dc6471d93dc52be66651a3
Author: olikru <olikru@tkruger.se>
Date: Mon, 8 Jan 2024 13:33:30 +0100
initial
Diffstat:
| A | Makefile | | | 43 | +++++++++++++++++++++++++++++++++++++++++++ |
| A | README | | | 8 | ++++++++ |
| A | stack_sd.c | | | 53 | +++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | stack_sd.h | | | 97 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test_stack_sd.c | | | 154 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
5 files changed, 355 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,43 @@
+.SUFFIXES: .c .o .so
+CC=clang
+CFLAGS+=-std=c99 -pedantic -Wall -Werror -Wstrict-prototypes
+CFLAGS+=-Wmissing-prototypes -Wmissing-declarations -Wshadow
+CFLAGS+=-Wpointer-arith -Wcast-qual -Wsign-compare
+CFLAGS+=-O2 -g
+CFLAGS+=-fstack-protector-all -Wtype-limits -fno-common
+CFLAGS+=-fno-builtin
+CFLAGS+=-I/usr/local/include
+
+CFLAGS+=-I$(HOME)/.local/include
+LFLAGS+=-L$(HOME)/.local/lib -lsd
+
+INSTALL_PATH=$(HOME)/.local
+BUILD=build
+
+TEST_SOURCE=test_stack_sd.c
+HEADER=stack_sd.h
+OBJS=stack_sd.o
+SHARED=stack_sd.so
+LIBSHARED=libstack_sd.so
+
+all: build $(OBJS) $(SHARED) test
+
+.c.o:
+ $(CC) $(CFLAGS) -c $< -o $(BUILD)/$@
+
+.o.so:
+ $(CC) -shared -fPIC $(BUILD)/$< -o $(BUILD)/$@ $(LFLAGS)
+
+test: $(TEST_SOURCE)
+ $(CC) $(CFLAGS) -o $(BUILD)/test $(TEST_SOURCE) $(BUILD)/$(OBJS) $(LFLAGS)
+
+build:
+ mkdir -p $(BUILD)
+
+install:
+ cp $(BUILD)/$(SHARED) $(INSTALL_PATH)/lib/$(LIBSHARED)
+ chmod 644 $(INSTALL_PATH)/lib/$(LIBSHARED)
+ cp $(HEADER) $(INSTALL_PATH)/include/
+
+clean:
+ rm -rf $(BUILD)
diff --git a/README b/README
@@ -0,0 +1,8 @@
+stack_sd
+========
+
+Small library for stacks of sd_t's. This stack is only capable of
+increasing it's allocated size, and never shrinking. Do not use it if
+shrinking is neccessary.
+
+
diff --git a/stack_sd.c b/stack_sd.c
@@ -0,0 +1,53 @@
+#include "stack_sd.h"
+
+void stack_sd_init(stack_sd_t *d) {
+ d->nmemb = 0;
+ d->alloc = BASE_STACK_SD_SIZE;
+
+ d->data = calloc(d->alloc, sizeof(*(d->data)));
+}
+
+void stack_sd_init_size(stack_sd_t *d, const size_t size) {
+ d->nmemb = 0;
+ d->alloc = size;
+
+ d->data = calloc(d->alloc, sizeof(*(d->data)));
+}
+
+void stack_sd_clear(stack_sd_t *d) {
+ d->nmemb = 0;
+ free(d->data);
+ d->data = NULL;
+}
+
+void stack_sd_push(stack_sd_t *d, sd_t x) {
+ if (d->alloc <= d->nmemb) {
+ d->alloc <<= 1;
+ d->data = realloc(d->data, d->alloc * sizeof(*(d->data)));
+ }
+
+ d->data[d->nmemb] = x;
+ d->nmemb++;
+}
+
+sd_t stack_sd_get(const stack_sd_t *d, const size_t i) { return d->data[i]; }
+
+sd_t stack_sd_getlast(const stack_sd_t *d) { return stack_sd_get(d, d->nmemb - 1); }
+
+sd_t stack_sd_pop(stack_sd_t *d) {
+ if (d->nmemb == 0)
+ return STACK_SD_EMPTY_POP;
+
+ sd_t r = stack_sd_getlast(d);
+ d->nmemb--;
+ return r;
+}
+
+int stack_sd_lookup(stack_sd_t *d, sd_t s) {
+ size_t i;
+ for (i = 0; i < d->nmemb; i++) {
+ if (sd_cmp(&d->data[i], &s) == 0)
+ return i;
+ }
+ return STACK_SD_LOOKUP_NOT_FOUND;
+}
diff --git a/stack_sd.h b/stack_sd.h
@@ -0,0 +1,97 @@
+#ifndef STACK_SD_H
+#define STACK_SD_H
+
+#include <sd.h>
+#include <stdint.h>
+#include <stdlib.h>
+
+#define BASE_STACK_SD_SIZE 256
+#define STACK_SD_LOOKUP_NOT_FOUND (-1)
+#define STACK_SD_EMPTY_POP ((sd_t){.size = 0, .data = NULL})
+
+typedef struct {
+ size_t nmemb;
+ size_t alloc;
+
+ sd_t *data;
+} stack_sd_t;
+
+/**
+ * Initialization of stack.
+ *
+ * Initialises memory for the stack. Use clear.
+ *
+ * @param d pointer to the address where to write the new stack
+ */
+void stack_sd_init(stack_sd_t *d);
+
+/**
+ * Initialization of stack, with size.
+ *
+ * Initialises memory for the stack. Use clear.
+ *
+ * @param d pointer to the address where to write the new stack
+ * @param size initial size of stack alloc
+ */
+void stack_sd_init_size(stack_sd_t *d, const size_t size);
+
+/**
+ * Clear a stack
+ *
+ * @param d pointer to the stack to clear
+ */
+void stack_sd_clear(stack_sd_t *d);
+
+/**
+ * Pushes a sd_t pointer onto the stack.
+ *
+ * Note that this does not copy the sd_t data, it just pushes the sd
+ * struct including the pointer to the stack.
+ *
+ * @param d pointer to the stack
+ * @param x the sd_t to push
+ */
+void stack_sd_push(stack_sd_t *d, sd_t x);
+
+/**
+ * Gets the element at index i in the stack.
+ *
+ * @param d pointer to the stack
+ * @param i the index to get element at
+ * @return the value of the sd_t at index i
+ */
+sd_t stack_sd_get(const stack_sd_t *d, const size_t i);
+
+/**
+ * Get the last (top) element of a stack.
+ *
+ * @param d pointer to the stack
+ * @return the value of the sd_t at the top
+ */
+sd_t stack_sd_getlast(const stack_sd_t *d);
+
+/**
+ * Pop an element of the stack.
+ *
+ * Note that popping never decreases the amount of memory allocated.
+ * If memory is an issue the stacks have to be destroyed and replaced.
+ * Returns STACK_SD_POP_EMPY if stack is empty.
+ *
+ * @param d pointer to the stack
+ * @return the value of the popped sd
+ */
+sd_t stack_sd_pop(stack_sd_t *d);
+
+/**
+ * Lookup a sd_t on a stack.
+ *
+ * Returns the first index on the stack at which a sd_t appears. Returns
+ * STACK_SD_LOOKUP_NOT_FOUND (== -1) if element is not in stack. It
+ * compares the sd_t elements (i.e. not only the pointers).
+ *
+ * @param d the stack to lookup in
+ * @param s the sd_t to look for in the stack
+ */
+int stack_sd_lookup(stack_sd_t *d, sd_t s);
+
+#endif
diff --git a/test_stack_sd.c b/test_stack_sd.c
@@ -0,0 +1,154 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "stack_sd.h"
+
+static void test_stack_sd_init() {
+ stack_sd_t s;
+ stack_sd_init(&s);
+
+ assert(s.nmemb == 0);
+ assert(s.alloc == BASE_STACK_SD_SIZE);
+ assert(s.data != NULL);
+
+ stack_sd_clear(&s);
+
+ stack_sd_init_size(&s, 4);
+
+ assert(s.nmemb == 0);
+ assert(s.alloc == 4);
+ assert(s.data != NULL);
+
+ stack_sd_clear(&s);
+}
+
+static void test_stack_sd_push() {
+ stack_sd_t s;
+ stack_sd_init_size(&s, 4);
+
+ sd_t topush[5];
+ size_t i;
+ for (i = 0; i < 5; i++) {
+ sd_init_u64(&topush[i], i);
+ stack_sd_push(&s, topush[i]);
+
+ assert(s.nmemb == i + 1);
+ }
+ assert(s.nmemb == 5);
+ assert(s.alloc == 8);
+
+ assert(memcmp(s.data, topush, sizeof(*topush) * 5) == 0);
+
+ for (i = 0; i < 5; i++)
+ sd_clear(&topush[i]);
+ stack_sd_clear(&s);
+}
+
+static void test_stack_sd_get() {
+ stack_sd_t s;
+ stack_sd_init(&s);
+
+ sd_t topush[20];
+ size_t i;
+ for (i = 0; i < 20; i++) {
+ sd_init_u64(&topush[i], i);
+ stack_sd_push(&s, topush[i]);
+ }
+
+ sd_t tmp;
+ for (i = 0; i < 20; i++) {
+ tmp = stack_sd_get(&s, i);
+ assert(tmp.size == topush[i].size);
+ assert(tmp.data == topush[i].data);
+ }
+
+ for (i = 0; i < 5; i++)
+ sd_clear(&topush[i]);
+ stack_sd_clear(&s);
+}
+
+static void test_stack_sd_getlast() {
+ stack_sd_t s;
+ stack_sd_init_size(&s, 8);
+
+ sd_t topush[20];
+ size_t i;
+ for (i = 0; i < 20; i++) {
+ sd_init_u64(&topush[i], i);
+ stack_sd_push(&s, topush[i]);
+ }
+
+ sd_t tmp = stack_sd_getlast(&s);
+ assert(tmp.size == topush[19].size);
+ assert(tmp.data == topush[19].data);
+
+ for (i = 0; i < 5; i++)
+ sd_clear(&topush[i]);
+ stack_sd_clear(&s);
+}
+
+static void test_stack_sd_pop() {
+ stack_sd_t s;
+ stack_sd_init_size(&s, 8);
+
+ sd_t topush[20];
+ size_t i;
+ for (i = 0; i < 20; i++) {
+ sd_init_u64(&topush[i], i);
+ stack_sd_push(&s, topush[i]);
+ }
+
+ sd_t tmp;
+ for (i = 0; i < 20; i++) {
+ tmp = stack_sd_pop(&s);
+ assert(tmp.size == topush[19 - i].size);
+ assert(tmp.data == topush[19 - i].data);
+ }
+
+ tmp = stack_sd_pop(&s);
+ assert(tmp.size == STACK_SD_EMPTY_POP.size);
+ assert(tmp.data == STACK_SD_EMPTY_POP.data);
+
+ tmp = stack_sd_pop(&s);
+ assert(tmp.size == STACK_SD_EMPTY_POP.size);
+ assert(tmp.data == STACK_SD_EMPTY_POP.data);
+
+ for (i = 0; i < 5; i++)
+ sd_clear(&topush[i]);
+ stack_sd_clear(&s);
+}
+
+static void test_stack_sd_lookup() {
+ stack_sd_t s;
+ stack_sd_init_size(&s, 8);
+
+ sd_t topush[20];
+ size_t i;
+ for (i = 0; i < 20; i++) {
+ sd_init_u64(&topush[i], i);
+ stack_sd_push(&s, topush[i]);
+ }
+
+ sd_t tmp;
+ sd_init_u64(&tmp, 13);
+ assert(stack_sd_lookup(&s, tmp) == 13);
+ sd_clear(&tmp);
+ sd_init_u64(&tmp, 22);
+ assert(stack_sd_lookup(&s, tmp) == STACK_SD_LOOKUP_NOT_FOUND);
+ sd_clear(&tmp);
+
+ for (i = 0; i < 5; i++)
+ sd_clear(&topush[i]);
+ stack_sd_clear(&s);
+}
+
+int main() {
+ test_stack_sd_init();
+ test_stack_sd_push();
+ test_stack_sd_getlast();
+ test_stack_sd_get();
+ test_stack_sd_pop();
+ test_stack_sd_lookup();
+
+ printf("test ok\n");
+}
