aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/basic_traits.c42
-rw-r--r--src/basic_traits.h23
-rw-r--r--src/pqueue.c16
-rw-r--r--src/pqueue.h72
-rw-r--r--src/priority_queue.c73
-rw-r--r--src/priority_queue.h19
-rw-r--r--src/sort.c14
-rw-r--r--src/sort.h54
-rw-r--r--src/type_alias.h18
-rw-r--r--src/vec.c8
-rw-r--r--src/vec.h15
11 files changed, 258 insertions, 96 deletions
diff --git a/src/basic_traits.c b/src/basic_traits.c
new file mode 100644
index 0000000..386c72f
--- /dev/null
+++ b/src/basic_traits.c
@@ -0,0 +1,42 @@
+#include "basic_traits.h"
+
+#include <string.h>
+
+#include "mmhash.h"
+
+#define BASIC_TRAITS_IMPL(T) \
+ bool T##_eq(T* lhs, T* rhs) { \
+ return *lhs == *rhs; \
+ } \
+ int T##_cmp(T* lhs, T* rhs) { \
+ if (*lhs == *rhs) return 0; \
+ if (*lhs < *rhs) return -1; \
+ return 1; \
+ } \
+ uint64_t T##_hash(T* x) { \
+ return mmhash(x, sizeof(T), 0); \
+ }
+
+BASIC_TRAITS_IMPL(Char);
+BASIC_TRAITS_IMPL(Bool);
+BASIC_TRAITS_IMPL(Int);
+BASIC_TRAITS_IMPL(Long);
+BASIC_TRAITS_IMPL(UInt);
+BASIC_TRAITS_IMPL(ULong);
+BASIC_TRAITS_IMPL(Double);
+BASIC_TRAITS_IMPL(Float);
+
+bool String_eq(String* lhs, String *rhs) {
+ return strcmp(*lhs, *rhs) == 0;
+}
+
+int String_cmp(String* lhs, String *rhs) {
+ return strcmp(*lhs, *rhs);
+}
+
+ULong String_hash(String *x) {
+ size_t len = strlen(*x);
+ return mmhash(*x, len, 0);
+}
+
+
diff --git a/src/basic_traits.h b/src/basic_traits.h
new file mode 100644
index 0000000..2bc4d8c
--- /dev/null
+++ b/src/basic_traits.h
@@ -0,0 +1,23 @@
+#ifndef ALGDS_BAISC_TRAITS_H_
+#define ALGDS_BAISC_TRAITS_H_
+
+#include "type_alias.h"
+
+// basic traits
+#define BASIC_TRAITS_DEF(T) \
+ Bool T##_eq(T* lhs, T* rhs); \
+ Int T##_cmp(T* lhs, T* rhs); \
+ ULong T##_hash(T* x);
+
+BASIC_TRAITS_DEF(Int);
+BASIC_TRAITS_DEF(Bool);
+BASIC_TRAITS_DEF(Long);
+BASIC_TRAITS_DEF(Char);
+BASIC_TRAITS_DEF(UInt);
+BASIC_TRAITS_DEF(ULong);
+BASIC_TRAITS_DEF(Double);
+BASIC_TRAITS_DEF(Float);
+BASIC_TRAITS_DEF(String);
+
+
+#endif
diff --git a/src/pqueue.c b/src/pqueue.c
new file mode 100644
index 0000000..b1cd733
--- /dev/null
+++ b/src/pqueue.c
@@ -0,0 +1,16 @@
+#include "pqueue.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "basic_traits.h"
+
+PQUEUE_IMPL(Int);
+PQUEUE_IMPL(Bool);
+PQUEUE_IMPL(Long);
+PQUEUE_IMPL(Char);
+PQUEUE_IMPL(UInt);
+PQUEUE_IMPL(ULong);
+PQUEUE_IMPL(Double);
+PQUEUE_IMPL(Float);
+PQUEUE_IMPL(String);
diff --git a/src/pqueue.h b/src/pqueue.h
new file mode 100644
index 0000000..0865051
--- /dev/null
+++ b/src/pqueue.h
@@ -0,0 +1,72 @@
+#ifndef PQUEUE_H_
+#define PQUEUE_H_
+
+#include "vec.h"
+
+#define PQUEUE_DEF(T) \
+ typedef struct { \
+ T##Vector vec; \
+ } T##PQueue; \
+ void T##PQueue_init(T##PQueue *self); \
+ void T##PQueue_push(T##PQueue *self, T *elem); \
+ void T##PQueue_pop(T##PQueue *self); \
+ T* T##PQueue_top(T##PQueue *self); \
+ void T##PQueue_free(T##PQueue *self); \
+
+PQUEUE_DEF(Int);
+PQUEUE_DEF(Bool);
+PQUEUE_DEF(Long);
+PQUEUE_DEF(Char);
+PQUEUE_DEF(UInt);
+PQUEUE_DEF(ULong);
+PQUEUE_DEF(Double);
+PQUEUE_DEF(Float);
+PQUEUE_DEF(String);
+
+#define PQUEUE_IMPL(T) \
+ static int T##PQueue_cmp(T##PQueue *self, int a, int b) { \
+ return T##_cmp(T##Vector_ref(&self->vec, a), T##Vector_ref(&self->vec, b)); \
+ } \
+ void T##PQueue_init(T##PQueue *self) { \
+ T##Vector_init(&self->vec); \
+ } \
+ void T##PQueue_push(T##PQueue *self, T *elem) { \
+ T##Vector_push_back(&self->vec, elem); \
+ int i = self->vec.size - 1; \
+ while (i > 0 && T##PQueue_cmp(self, i, i / 2) > 0) { \
+ T##Vector_swap(&self->vec, i, i / 2); \
+ i /= 2; \
+ } \
+ } \
+ static void T##PQueue_heapify(T##PQueue *self, int idx) { \
+ int left, right, largest; \
+ left = 2 * idx + 1; \
+ right = 2 * idx + 2; \
+ if (left < self->vec.size && T##PQueue_cmp(self, left, idx) > 0) { \
+ largest = left; \
+ } else { \
+ largest = idx; \
+ } \
+ if (right < self->vec.size && T##PQueue_cmp(self, right, largest) > 0) { \
+ largest = right; \
+ } \
+ if (largest != idx) { \
+ T##Vector_swap(&self->vec, largest, idx); \
+ T##PQueue_heapify(self, largest); \
+ } \
+ } \
+ void T##PQueue_pop(T##PQueue *self) { \
+ if (self->vec.size == 0) return; \
+ memcpy(T##Vector_ref(&self->vec, 0), T##Vector_ref(&self->vec, self->vec.size - 1), sizeof(T)); \
+ T##Vector_pop(&self->vec); \
+ T##PQueue_heapify(self, 0); \
+ } \
+ T* T##PQueue_top(T##PQueue *self) { \
+ if (self->vec.size == 0) return NULL; \
+ return self->vec.buffer; \
+ } \
+ void T##PQueue_free(T##PQueue *self) { \
+ T##Vector_free(&self->vec); \
+ } \
+
+#endif
diff --git a/src/priority_queue.c b/src/priority_queue.c
deleted file mode 100644
index 59d64df..0000000
--- a/src/priority_queue.c
+++ /dev/null
@@ -1,73 +0,0 @@
-#include "priority_queue.h"
-
-#include <stdlib.h>
-#include <string.h>
-
-void init_priority_queue(priority_queue_t *pq, int cap, int elem_sz,
- int (*cmp)(void *, void *)) {
- pq->cap = cap;
- pq->size = 0;
- pq->elemsz = elem_sz;
- pq->cmp = cmp;
- pq->buf = malloc(cap * elem_sz);
-}
-
-static void swap(priority_queue_t *pq, int a, int b) {
- char buf[pq->elemsz];
- void *tmp = buf;
- int elemsz = pq->elemsz;
- memcpy(tmp, pq->buf + a * elemsz, elemsz);
- memcpy(pq->buf + a * elemsz, pq->buf + b * elemsz, elemsz);
- memcpy(pq->buf + b * elemsz, tmp, elemsz);
-}
-
-static int cmp(priority_queue_t *pq, int a, int b) {
- return pq->cmp(pq->buf + a * pq->elemsz, pq->buf + b * pq->elemsz);
-}
-
-void priority_queue_push(priority_queue_t *pq, void *elem) {
- if (pq->size + 1 > pq->cap) {
- pq->buf = realloc(pq->buf, 2 * pq->cap * pq->elemsz);
- pq->cap *= 2;
- }
- memcpy(pq->buf + pq->size * pq->elemsz, elem, pq->elemsz);
- pq->size++;
- if (pq->size == 0) {
- return;
- }
- int i = pq->size - 1;
- while (i > 0 && cmp(pq, i, i / 2) > 0) {
- swap(pq, i, i / 2);
- i /= 2;
- }
-}
-
-static void heapify(priority_queue_t *pq, int idx) {
- int left, right, largest;
- left = 2 * idx + 1;
- right = 2 * idx + 2;
- if (left < pq->size && cmp(pq, left, idx) > 0) {
- largest = left;
- } else {
- largest = idx;
- }
- if (right < pq->size && cmp(pq, right, largest) > 0) {
- largest = right;
- }
- if (largest != idx) {
- swap(pq, largest, idx);
- heapify(pq, largest);
- }
-}
-
-void priority_queue_pop(priority_queue_t *pq) {
- if (pq->size == 0) return;
- memcpy(pq->buf, pq->buf + (pq->size - 1) * pq->elemsz, pq->elemsz);
- pq->size -= 1;
- heapify(pq, 0);
-}
-
-void *priority_queue_top(priority_queue_t *pq) {
- if (pq->size == 0) return NULL;
- return pq->buf;
-}
diff --git a/src/priority_queue.h b/src/priority_queue.h
deleted file mode 100644
index 98250c9..0000000
--- a/src/priority_queue.h
+++ /dev/null
@@ -1,19 +0,0 @@
-#ifndef PQUEUE_H_
-#define PQUEUE_H_
-
-struct priority_queue {
- void *buf;
- int elemsz;
- int cap;
- int size;
- int (*cmp)(void *, void *);
-};
-typedef struct priority_queue priority_queue_t;
-
-void init_priority_queue(priority_queue_t *pq, int cap, int elemsz,
- int (*cmp)(void *, void *));
-void priority_queue_push(priority_queue_t *pq, void *elem);
-void priority_queue_pop(priority_queue_t *pq);
-void *priority_queue_top(priority_queue_t *pq);
-
-#endif
diff --git a/src/sort.c b/src/sort.c
new file mode 100644
index 0000000..ed5a1e3
--- /dev/null
+++ b/src/sort.c
@@ -0,0 +1,14 @@
+#include "sort.h"
+
+#include "basic_traits.h"
+
+
+QSORT_IMPL(Int);
+QSORT_IMPL(Bool);
+QSORT_IMPL(Long);
+QSORT_IMPL(Char);
+QSORT_IMPL(UInt);
+QSORT_IMPL(ULong);
+QSORT_IMPL(Double);
+QSORT_IMPL(Float);
+QSORT_IMPL(String);
diff --git a/src/sort.h b/src/sort.h
new file mode 100644
index 0000000..64a5b3e
--- /dev/null
+++ b/src/sort.h
@@ -0,0 +1,54 @@
+#ifndef ALGDS_SORT_H_
+#define ALGDS_SORT_H_
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "type_alias.h"
+
+#define QSORT_DEF(T) \
+ void T##_qsort(T* arr, int n);
+
+#define QSORT_IMPL(T) \
+ void T##_qsort_swap(T* arr, int lhs, int rhs) { \
+ if (lhs == rhs) return; \
+ T buf; \
+ memcpy(&buf, arr+lhs, sizeof(T)); \
+ memcpy(arr+lhs, arr+rhs, sizeof(T)); \
+ memcpy(arr+rhs, &buf, sizeof(T)); \
+ } \
+ void T##_qsort(T* arr, int n) { \
+ if (n <= 1) return; \
+ int pivot = rand() % n; \
+ T##_qsort_swap(arr, 0, pivot); \
+ int lp = 1, rp = n-1; \
+ while (lp < rp) { \
+ if (T##_cmp(arr+lp, arr) < 0) { \
+ lp++; \
+ continue; \
+ } \
+ if (T##_cmp(arr+rp, arr) >= 0) { \
+ rp--; \
+ continue; \
+ } \
+ T##_qsort_swap(arr, lp, rp); \
+ lp++; \
+ rp--; \
+ } \
+ if (T##_cmp(arr + rp, arr) > 0) rp--; \
+ T##_qsort_swap(arr, 0, rp); \
+ T##_qsort(arr, rp); \
+ T##_qsort(arr+rp+1, n-rp-1); \
+ }
+
+QSORT_DEF(Int);
+QSORT_DEF(Bool);
+QSORT_DEF(Long);
+QSORT_DEF(Char);
+QSORT_DEF(UInt);
+QSORT_DEF(ULong);
+QSORT_DEF(Double);
+QSORT_DEF(Float);
+QSORT_DEF(String);
+
+#endif
diff --git a/src/type_alias.h b/src/type_alias.h
new file mode 100644
index 0000000..9d40684
--- /dev/null
+++ b/src/type_alias.h
@@ -0,0 +1,18 @@
+#ifndef ALGDS_TYPE_ALIAS_H_
+#define ALGDS_TYPE_ALIAS_H_
+
+#include <stdint.h>
+#include <stdbool.h>
+
+typedef bool Bool;
+typedef int32_t Int;
+typedef int64_t Long;
+typedef uint32_t UInt;
+typedef uint64_t ULong;
+typedef char Char;
+typedef float Float;
+typedef double Double;
+typedef const char *String;
+
+
+#endif
diff --git a/src/vec.c b/src/vec.c
index 318d328..be1ea65 100644
--- a/src/vec.c
+++ b/src/vec.c
@@ -2,8 +2,12 @@
#include <string.h>
-VECTOR_IMPL(Char);
VECTOR_IMPL(Int);
+VECTOR_IMPL(Bool);
VECTOR_IMPL(Long);
-VECTOR_IMPL(Float);
+VECTOR_IMPL(Char);
+VECTOR_IMPL(UInt);
+VECTOR_IMPL(ULong);
VECTOR_IMPL(Double);
+VECTOR_IMPL(Float);
+VECTOR_IMPL(String);
diff --git a/src/vec.h b/src/vec.h
index 3bb4014..e39c09c 100644
--- a/src/vec.h
+++ b/src/vec.h
@@ -21,6 +21,7 @@
T* T##Vector_begin(T##Vector *self); \
T* T##Vector_end(T##Vector *self); \
T* T##Vector_ref(T##Vector *self, size_t n); \
+ void T##Vector_swap(T##Vector *self, int i, int j); \
void T##Vector_free(T##Vector *self);
#define VECTOR_IMPL(T) \
@@ -66,12 +67,22 @@
T* T##Vector_begin(T##Vector *self) { return self->buffer; } \
T* T##Vector_end(T##Vector *self) { return self->buffer + self->size; } \
T* T##Vector_ref(T##Vector *self, size_t n) { return self->buffer + n; } \
+ void T##Vector_swap(T##Vector *self, int i, int j) { \
+ T buf; \
+ memcpy(&buf, self->buffer + i, sizeof(T)); \
+ memcpy(self->buffer + i, self->buffer + j, sizeof(T)); \
+ memcpy(self->buffer + j, &buf, sizeof(T)); \
+ } \
void T##Vector_free(T##Vector *self) { free(self->buffer); }
-VECTOR_DEF(Char);
VECTOR_DEF(Int);
+VECTOR_DEF(Bool);
VECTOR_DEF(Long);
-VECTOR_DEF(Float);
+VECTOR_DEF(Char);
+VECTOR_DEF(UInt);
+VECTOR_DEF(ULong);
VECTOR_DEF(Double);
+VECTOR_DEF(Float);
+VECTOR_DEF(String);
#endif
generated by cgit v1.0 at 2025-12-29 15:20:04 +0000