commit 2aee4b6107c7b2579cb9d3c27ad61aed4bcd781e
Author: olikru <olikru@tkruger.se>
Date: Fri, 5 Jan 2024 22:30:42 +0100
initial
Diffstat:
| A | Makefile | | | 40 | ++++++++++++++++++++++++++++++++++++++++ |
| A | README | | | 13 | +++++++++++++ |
| A | stack_u64.c | | | 40 | ++++++++++++++++++++++++++++++++++++++++ |
| A | stack_u64.h | | | 67 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test_stack_u64.c | | | 80 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
5 files changed, 240 insertions(+), 0 deletions(-)
diff --git a/Makefile b/Makefile
@@ -0,0 +1,40 @@
+.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
+
+INSTALL_PATH=$(HOME)/.local
+BUILD=build
+
+TEST_SOURCE=test_stack_u64.c
+HEADER=stack_u64.h
+OBJS=stack_u64.o
+SHARED=stack_u64.so
+LIBSHARED=libstack_u64.so
+
+all: build $(OBJS) $(SHARED) test
+
+.c.o:
+ $(CC) $(CFLAGS) -c $< -o $(BUILD)/$@
+
+.o.so:
+ $(CC) -shared -fPIC $(BUILD)/$< -o $(BUILD)/$@
+
+test: $(TEST_SOURCE)
+ $(CC) $(CFLAGS) -o $(BUILD)/test $(TEST_SOURCE) $(BUILD)/$(OBJS)
+
+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,13 @@
+stack_u64
+=========
+
+Small library for stacks of uint64_t's. This stack is only capable of
+increasing it's allocated size, and never shrinking. Do not use it if
+shrinking is neccessary.
+
+ typedef struct {
+ size_t nmemb; // number of entries in stack
+ size_t alloc; // number of entries currently allocated for
+
+ uint64_t *data; // array of entries
+ } stack_u64_t;
diff --git a/stack_u64.c b/stack_u64.c
@@ -0,0 +1,40 @@
+#include "stack_u64.h"
+
+void stack_u64_init(stack_u64_t *d) {
+ d->nmemb = 0;
+ d->alloc = BASE_STACK_SIZE;
+
+ d->data = calloc(d->alloc, sizeof(*(d->data)));
+}
+
+void stack_u64_clear(stack_u64_t *d) {
+ d->nmemb = 0;
+ free(d->data);
+ d->data = NULL;
+}
+
+void stack_u64_push(stack_u64_t *d, const uint64_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++;
+}
+
+uint64_t stack_u64_get(const stack_u64_t *d, const size_t i) {
+ return d->data[i];
+}
+
+uint64_t stack_u64_getlast(const stack_u64_t *d) {
+ return stack_u64_get(d, d->nmemb - 1);
+}
+
+uint64_t stack_u64_pop(stack_u64_t *d) {
+ if (d->nmemb == 0)
+ return STACK_U64_EMPTY_POP;
+ uint64_t r = stack_u64_getlast(d);
+ d->nmemb--;
+ return r;
+}
diff --git a/stack_u64.h b/stack_u64.h
@@ -0,0 +1,67 @@
+#ifndef STACK_U64_H
+#define STACK_U64_H
+
+#include <stdint.h>
+#include <stdlib.h>
+
+#define BASE_STACK_SIZE 256
+#define STACK_U64_EMPTY_POP UINT64_MAX
+
+typedef struct {
+ size_t nmemb;
+ size_t alloc;
+
+ uint64_t *data;
+} stack_u64_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_u64_init(stack_u64_t *d);
+
+/**
+ * Clear a stack
+ *
+ * @param d pointer to the stack to clear
+ */
+void stack_u64_clear(stack_u64_t *d);
+
+/**
+ * Pushes a uint64_t onto the stack.
+ *
+ * @param d pointer to the stack
+ * @param x the uint64_t to push
+ */
+void stack_u64_push(stack_u64_t *d, const uint64_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 element at index i
+ */
+uint64_t stack_u64_get(const stack_u64_t *d, const size_t i);
+
+/**
+ * Get the last (top) element of a stack.
+ *
+ * @param d pointer to the stack
+ */
+uint64_t stack_u64_getlast(const stack_u64_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.
+ *
+ * @param d pointer to the stack
+ */
+uint64_t stack_u64_pop(stack_u64_t *d);
+
+#endif
diff --git a/test_stack_u64.c b/test_stack_u64.c
@@ -0,0 +1,80 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "stack_u64.h"
+
+static void test_stack_u64_init() {
+ stack_u64_t t;
+ stack_u64_init(&t);
+
+ assert(t.nmemb == 0);
+ assert(t.alloc > 0);
+ assert(t.data != NULL);
+
+ stack_u64_clear(&t);
+}
+
+static void test_stack_u64_push() {
+ stack_u64_t t;
+ stack_u64_init(&t);
+
+ uint64_t i;
+ for (i = 0; i < 2 * BASE_STACK_SIZE; i++) {
+ stack_u64_push(&t, i);
+ }
+
+ assert(t.alloc == 2 * BASE_STACK_SIZE);
+ assert(t.nmemb == 2 * BASE_STACK_SIZE);
+ for (i = 0; i < 2 * BASE_STACK_SIZE; i++) {
+ assert(t.data[i] == i);
+ }
+
+ stack_u64_clear(&t);
+}
+
+static void test_stack_u64_get_getlast() {
+ stack_u64_t t;
+ stack_u64_init(&t);
+
+ uint64_t i;
+ for (i = 0; i < 2 * BASE_STACK_SIZE; i++) {
+ stack_u64_push(&t, i);
+ }
+
+ for (i = 0; i < t.nmemb; i++) {
+ assert(stack_u64_get(&t, i) == i);
+ }
+ assert(stack_u64_getlast(&t) == 2 * BASE_STACK_SIZE - 1);
+
+ stack_u64_clear(&t);
+}
+
+static void test_stack_u64_pop() {
+ stack_u64_t t;
+ stack_u64_init(&t);
+
+ stack_u64_push(&t, 13);
+ stack_u64_push(&t, 16);
+ stack_u64_push(&t, 17);
+
+ assert(t.nmemb == 3);
+ assert(stack_u64_pop(&t) == 17);
+ assert(t.nmemb == 2);
+ assert(stack_u64_pop(&t) == 16);
+ assert(t.nmemb == 1);
+ assert(stack_u64_pop(&t) == 13);
+ assert(t.nmemb == 0);
+ assert(stack_u64_pop(&t) == STACK_U64_EMPTY_POP);
+ assert(t.nmemb == 0);
+
+ stack_u64_clear(&t);
+}
+
+int main() {
+ test_stack_u64_init();
+ test_stack_u64_push();
+ test_stack_u64_pop();
+ test_stack_u64_get_getlast();
+
+ printf("test ok\n");
+}
