commit 68c94884b2b3d184c69d1a03d59637de438c2f78
Author: olikru <olikru@tkruger.se>
Date: Mon, 8 Jan 2024 13:23:07 +0100
initial
Diffstat:
| A | Makefile | | | 40 | ++++++++++++++++++++++++++++++++++++++++ |
| A | README | | | 9 | +++++++++ |
| A | sd.c | | | 60 | ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | sd.h | | | 103 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| A | test_sd.c | | | 106 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
5 files changed, 318 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_sd.c
+HEADER=sd.h
+OBJS=sd.o
+SHARED=sd.so
+LIBSHARED=libsd.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,9 @@
+sd
+==
+
+General purpose functions for "sized data" type.
+
+ typedef struct {
+ size_t size;
+ uint8_t *data;
+ } sd;
diff --git a/sd.c b/sd.c
@@ -0,0 +1,60 @@
+#include "sd.h"
+
+void sd_init(sd_t *s, const size_t size) {
+ s->size = size;
+ s->data = malloc(s->size);
+}
+
+void sd_clear(sd_t *s) {
+ s->size = 0;
+ free(s->data);
+}
+
+static inline uint64_t murmur_u64(uint64_t h) {
+ h ^= h >> 33;
+ h *= 0xff51afd7ed558ccdL;
+ h ^= h >> 33;
+ h *= 0xc4ceb9fe1a85ec53L;
+ h ^= h >> 33;
+ return h;
+}
+
+uint64_t sd_hash(sd_t *s) {
+ uint64_t tmp = s->size;
+
+ size_t i;
+ for (i = 0; i < s->size; i++) {
+ tmp ^= ((uint64_t)s->data[i]) << (i % 4);
+ }
+
+ return murmur_u64(tmp);
+}
+
+int sd_cmp(sd_t *x, sd_t *y) {
+ if (x->size < y->size) {
+ return -1;
+ } else if (x->size > y->size) {
+ return 1;
+ }
+
+ return memcmp(x->data, y->data, x->size);
+}
+
+void sd_init_u64(sd_t *s, const uint64_t x) {
+ sd_init(s, sizeof(x));
+ memcpy(s->data, &x, sizeof(x));
+}
+
+uint64_t sd_conv_u64(sd_t *s) {
+ uint64_t r;
+ memcpy(&r, s->data, sizeof(r));
+ return r;
+}
+
+void sd_init_str(sd_t *s, const char *str) {
+ size_t len = strlen(str) + 1;
+ sd_init(s, sizeof(*str) * len);
+ memcpy(s->data, str, len);
+}
+
+char *sd_get_str(sd_t *s) { return (char *)s->data; }
diff --git a/sd.h b/sd.h
@@ -0,0 +1,103 @@
+#ifndef SD_H
+#define SD_H
+
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct {
+ size_t size;
+ uint8_t *data;
+} sd_t;
+
+/**
+ * Initialise a sized data.
+ *
+ * Allocates memory that needs to be sd_clear'd.
+ *
+ * @param s pointer where to write the sized data obj
+ * @param size number of bytes in the sd
+ */
+void sd_init(sd_t *s, const size_t size);
+
+/**
+ * Clear a sd.
+ *
+ * @param s pointer to the sd
+ */
+void sd_clear(sd_t *s);
+
+/**
+ * Computes a hash of a sd.
+ *
+ * This hash is a simple combination of xoring
+ * in all the bytes to a uint64_t in different
+ * positions, then computing the mix64 function
+ * known as murmur64.
+ *
+ * @param s the sd to get hash of
+ * @return hash of s
+ */
+uint64_t sd_hash(sd_t *s);
+
+/**
+ * Compare two sds.
+ *
+ * Compares the sd's pointed to by x and y. In the
+ * following sense: a < b if either a.size < b.size
+ * or a.data < b.data (in the memcmp order). If
+ * the sd_t are equal then 0 is returned.
+ *
+ * @param x pointer to first sd
+ * @param y pointer to second sd
+ * @return comparison number (lex order)
+ */
+int sd_cmp(sd_t *x, sd_t *y);
+
+/**
+ * Initialises a sd from a uint64_t.
+ *
+ * The size will be 8 bytes, and the order of the
+ * bytes is raw (host order). Allocates memory that
+ * needs to be sd_clear'd.
+ *
+ * @param s ptr to the sd_t to initialise
+ * @param x the uint64_t to initialize from
+ */
+void sd_init_u64(sd_t *s, const uint64_t x);
+
+/**
+ * Converts a sd_t to a uint64_t.
+ *
+ * Gets a uint64_t from a sd_t that has been created
+ * by sd_init_u64.
+ *
+ * @param s ptr to the sd to convert
+ * @return the uint64_t
+ */
+uint64_t sd_conv_u64(sd_t *s);
+
+/**
+ * Initializes a sd from a string.
+ *
+ * Copies a string into a sd_t, including the
+ * terminating null byte. Allocates memory that
+ * needs to be sd_clear'd.
+ *
+ * @param s ptr to the sd to be init'd
+ * @param str the string to copy into new sd
+ */
+void sd_init_str(sd_t *s, const char *str);
+
+/**
+ * Get string stored in sd.
+ *
+ * This returns a char* to the data stored in the
+ * sd_t. This assumes that the data is in fact a
+ * null terminated string.
+ *
+ * @param s ptr to the sd to get string from
+ */
+char *sd_get_str(sd_t *s);
+
+#endif
diff --git a/test_sd.c b/test_sd.c
@@ -0,0 +1,106 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include <assert.h>
+#include "sd.h"
+
+static void test_sd_init() {
+ sd_t s;
+ sd_init(&s, 12);
+
+ assert(s.size == 12);
+
+ size_t i;
+ for (i = 0; i < s.size; i++)
+ s.data[i] = 0x00;
+ for (i = 0; i < s.size; i++) {
+ assert(s.data[i] == 0x00);
+ }
+
+ sd_clear(&s);
+
+ sd_init_u64(&s, 13);
+ uint64_t tretton = 13;
+ assert(s.size == sizeof(uint64_t));
+ assert(memcmp(s.data, &tretton, sizeof(uint64_t)) == 0);
+
+ sd_clear(&s);
+
+ char *mystr = "this is a test";
+ sd_init_str(&s, mystr);
+ assert(s.size == strlen(mystr) + 1);
+ assert(memcmp(s.data, "this is a test", s.size) == 0);
+
+ sd_clear(&s);
+}
+
+static void test_sd_cmp() {
+ char *strs[4] = {"bc", "abc", "abd", "abcd"};
+
+ sd_t ss[4];
+ size_t i;
+ for (i = 0; i < 4; i++) {
+ sd_init_str(&ss[i], strs[i]);
+ }
+
+ assert(sd_cmp(&ss[0], &ss[1]) < 0);
+ assert(sd_cmp(&ss[0], &ss[2]) < 0);
+ assert(sd_cmp(&ss[0], &ss[3]) < 0);
+ assert(sd_cmp(&ss[0], &ss[0]) == 0);
+ assert(sd_cmp(&ss[1], &ss[2]) < 0);
+ assert(sd_cmp(&ss[1], &ss[3]) < 0);
+ assert(sd_cmp(&ss[3], &ss[2]) > 0);
+
+ for (i = 0; i < 4; i++) {
+ sd_clear(&ss[i]);
+ }
+}
+
+static void test_sd_hash() {
+ char *strs[4] = {"bc", "abc", "abd", "abd"};
+
+ sd_t ss[4];
+ size_t i;
+ for (i = 0; i < 4; i++) {
+ sd_init_str(&ss[i], strs[i]);
+ }
+
+ assert(sd_hash(&ss[0]) != sd_hash(&ss[1]));
+ assert(sd_hash(&ss[0]) != sd_hash(&ss[2]));
+ assert(sd_hash(&ss[0]) != sd_hash(&ss[3]));
+ assert(sd_hash(&ss[1]) != sd_hash(&ss[2]));
+ assert(sd_hash(&ss[1]) != sd_hash(&ss[3]));
+ assert(sd_hash(&ss[2]) == sd_hash(&ss[3]));
+
+ for (i = 0; i < 4; i++)
+ sd_clear(&ss[i]);
+}
+
+static void test_sd_conv_u64() {
+ sd_t s;
+ sd_init_u64(&s, 0xdeadbeeffeedbaaf);
+ uint64_t c = sd_conv_u64(&s);
+ assert(c == 0xdeadbeeffeedbaaf);
+ sd_clear(&s);
+}
+
+static void test_sd_get_str() {
+ sd_t s;
+ char *str = "hello world!";
+ sd_init_str(&s, str);
+ char *mystr = sd_get_str(&s);
+
+ assert(mystr != str);
+ assert(strncmp(str, mystr, 13) == 0);
+
+ sd_clear(&s);
+}
+
+int main() {
+ test_sd_init();
+ test_sd_cmp();
+ test_sd_hash();
+ test_sd_conv_u64();
+ test_sd_get_str();
+
+ printf("test ok\n");
+}
