aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/shared/linked_list.h277
-rw-r--r--src/kern/stdlibrepl.c29
-rw-r--r--tests/test_linked_list.c22
3 files changed, 221 insertions, 107 deletions
diff --git a/include/shared/linked_list.h b/include/shared/linked_list.h
index 3f8e075..ec72377 100644
--- a/include/shared/linked_list.h
+++ b/include/shared/linked_list.h
@@ -1,15 +1,21 @@
#ifndef SHARED_LINKED_LIST_H_
#define SHARED_LINKED_LIST_H_
-#define linked_list_t(type) linked_list_##type##_t
-#define linked_list_node_t(type) linked_list_node_##type##_t
-#define linked_list_push_back(type) linked_list_push_back_##type
-#define linked_list_push_front(type) linked_list_push_front_##type
-#define linked_list_pop_front(type) linked_list_pop_front_##type
-#define linked_list_pop_back(type) linked_list_pop_back_##type
-#define linked_list_front(type) linked_list_front_##type
-#define linked_list_back(type) linked_list_back_##type
-#define linked_list_length(type) linked_list_length_##type
+#include "kern/common.h"
+
+#define linked_list_t(T) linked_list___##T##___t
+#define linked_list_node_t(T) linked_list_node___##T##___t
+#define linked_list_itr_t(T) linked_list_node_itr___##T##___t
+#define linked_list_push_back(T) linked_list_push_back___##T
+#define linked_list_push_front(T) linked_list_push_front___##T
+#define linked_list_pop_front(T) linked_list_pop_front___##T
+#define linked_list_pop_back(T) linked_list_pop_back___##T
+#define linked_list_front(T) linked_list_front___##T
+#define linked_list_back(T) linked_list_back___##T
+#define linked_list_length(T) linked_list_length___##T
+#define linked_list_find_match(T) linked_list_find_match___##T
+#define linked_list_remove_first_match(T) linked_list_remove_first_match___##T
+#define linked_list_remove(T) linked_list_remove___##T
#define LINKED_LIST_INIT \
{ \
@@ -24,108 +30,171 @@
#define NO_ATTRIBUTE
-#define LINKED_LIST_DECL(type) LINKED_LIST_INTERNAL_DECL(type, NO_ATTRIBUTE)
+#define LINKED_LIST_DECL(T) LINKED_LIST_INTERNAL_DECL(T, NO_ATTRIBUTE)
-#define LINKED_LIST_STATIC_DECL(type) LINKED_LIST_INTERNAL_DECL(type, static)
+#define LINKED_LIST_STATIC_DECL(T) LINKED_LIST_INTERNAL_DECL(T, static inline)
-#define LINKED_LIST_INTERNAL_DECL(type, attr) \
- typedef struct LINKED_LIST_NODE_##type { \
- type value; \
- struct LINKED_LIST_NODE_##type* next; \
- } linked_list_node_t(type); \
+#define LINKED_LIST_INTERNAL_DECL(T, attr) \
+ typedef struct LINKED_LIST_NODE_##T { \
+ T value; \
+ struct LINKED_LIST_NODE_##T* next; \
+ } linked_list_node_t(T); \
+ \
+ typedef struct { \
+ linked_list_node_t(T) * prev; \
+ linked_list_node_t(T) * cur; \
+ } linked_list_itr_t(T); \
\
typedef struct { \
- linked_list_node_t(type) * head; \
- } linked_list_t(type); \
+ linked_list_node_t(T) * head; \
+ } linked_list_t(T); \
\
- attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value); \
- attr void linked_list_push_front(type)( \
- linked_list_t(type) * ll, type value); \
- attr void linked_list_pop_back(type)(linked_list_t(type) * ll); \
- attr void linked_list_pop_front(type)(linked_list_t(type) * ll); \
- attr type* linked_list_front(type)(linked_list_t(type) * ll); \
- attr type* linked_list_back(type)(linked_list_t(type) * ll);
+ attr void linked_list_push_back(T)(linked_list_t(T) * ll, T value); \
+ attr void linked_list_push_front(T)(linked_list_t(T) * ll, T value); \
+ attr void linked_list_pop_back(T)(linked_list_t(T) * ll); \
+ attr void linked_list_pop_front(T)(linked_list_t(T) * ll); \
+ attr size_t linked_list_length(T)(const linked_list_t(T) * ll); \
+ attr T* linked_list_front(T)(const linked_list_t(T) * ll); \
+ attr bool linked_list_find_match(T)( \
+ const linked_list_t(T) * ll, \
+ linked_list_itr_t(T) * itr_out, \
+ bool (*match)(T, void*), \
+ void* closure); \
+ attr bool linked_list_remove_first_match(T)( \
+ linked_list_t(T) * ll, T * out, bool (*match)(T, void*), void* closure); \
+ attr T* linked_list_back(T)(const linked_list_t(T) * ll);
-#define LINKED_LIST_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, NO_ATTRIBUTE)
+#define LINKED_LIST_IMPL(T) LINKED_LIST_INTERNAL_IMPL(T, NO_ATTRIBUTE)
-#define LINKED_LIST_STATIC_IMPL(type) LINKED_LIST_INTERNAL_IMPL(type, static)
+#define LINKED_LIST_STATIC_IMPL(T) LINKED_LIST_INTERNAL_IMPL(T, static inline)
-#define LINKED_LIST_INTERNAL_IMPL(type, attr) \
- attr void linked_list_push_back(type)(linked_list_t(type) * ll, type value) \
- { \
- if (!ll->head) { \
- ll->head = kalloc(sizeof(linked_list_node_t(type))); \
- ll->head->value = value; \
- ll->head->next = NULL; \
- } else { \
- linked_list_node_t(type)* c = ll->head; \
- while (c->next) c = c->next; \
- c->next = kalloc(sizeof(linked_list_node_t(type))); \
- c->next->next = NULL; \
- c->next->value = value; \
- } \
- } \
- attr void linked_list_push_front(type)(linked_list_t(type) * ll, type value) \
- { \
- if (!ll->head) { \
- ll->head = kalloc(sizeof(linked_list_node_t(type))); \
- ll->head->value = value; \
- ll->head->next = NULL; \
- } else { \
- linked_list_node_t(type)* node = \
- kalloc(sizeof(linked_list_node_t(type))); \
- node->next = ll->head; \
- node->value = value; \
- ll->head = node; \
- } \
- } \
- attr void linked_list_pop_back(type)(linked_list_t(type) * ll) \
- { \
- if (!ll->head) { \
- return; \
- } \
- if (!ll->head->next) { \
- kfree(ll->head); \
- ll->head = NULL; \
- return; \
- } \
- linked_list_node_t(type)* c = ll->head; \
- while (c->next->next) c = c->next; \
- kfree(c->next); \
- c->next = NULL; \
- return; \
- } \
- attr void linked_list_pop_front(type)(linked_list_t(type) * ll) \
- { \
- if (!ll->head) { \
- return; \
- } \
- linked_list_node_t(type)* node = ll->head; \
- ll->head = node->next; \
- kfree(node); \
- } \
- attr type* linked_list_front(type)(linked_list_t(type) * ll) \
- { \
- if (!ll->head) { \
- return NULL; \
- } \
- return &ll->head->value; \
- } \
- attr type* linked_list_back(type)(linked_list_t(type) * ll) \
- { \
- if (!ll->head) { \
- return NULL; \
- } \
- linked_list_node_t(type)* cur = ll->head; \
- while (cur->next) cur = cur->next; \
- return &cur->value; \
- } \
- attr size_t linked_list_length(type)(linked_list_t(type) * ll) \
- { \
- linked_list_node_t(type) * cur; \
- size_t ret = 0; \
- for (cur = ll->head; cur; cur = cur->next) ++ret; \
- return ret; \
- }
+#define PRAGMA(x) _Pragma(#x)
+#define LINKED_LIST_INTERNAL_IMPL(T, attr) \
+ _Pragma("GCC diagnostic push") \
+ _Pragma("GCC diagnostic ignored \"-Wunused-function\"") \
+ attr void linked_list_push_back(T)(linked_list_t(T) * ll, T value) \
+ { \
+ if (!ll->head) { \
+ ll->head = kalloc(sizeof(linked_list_node_t(T))); \
+ ll->head->value = value; \
+ ll->head->next = NULL; \
+ } else { \
+ linked_list_node_t(T)* c = ll->head; \
+ while (c->next) c = c->next; \
+ c->next = kalloc(sizeof(linked_list_node_t(T))); \
+ c->next->next = NULL; \
+ c->next->value = value; \
+ } \
+ } \
+ attr void linked_list_push_front(T)(linked_list_t(T) * ll, T value) \
+ { \
+ if (!ll->head) { \
+ ll->head = kalloc(sizeof(linked_list_node_t(T))); \
+ ll->head->value = value; \
+ ll->head->next = NULL; \
+ } else { \
+ linked_list_node_t(T)* node = kalloc(sizeof(linked_list_node_t(T))); \
+ node->next = ll->head; \
+ node->value = value; \
+ ll->head = node; \
+ } \
+ } \
+ attr void linked_list_pop_back(T)(linked_list_t(T) * ll) \
+ { \
+ if (!ll->head) { \
+ return; \
+ } \
+ if (!ll->head->next) { \
+ kfree(ll->head); \
+ ll->head = NULL; \
+ return; \
+ } \
+ linked_list_node_t(T)* c = ll->head; \
+ while (c->next->next) c = c->next; \
+ kfree(c->next); \
+ c->next = NULL; \
+ return; \
+ } \
+ attr void linked_list_pop_front(T)(linked_list_t(T) * ll) \
+ { \
+ if (!ll->head) { \
+ return; \
+ } \
+ linked_list_node_t(T)* node = ll->head; \
+ ll->head = node->next; \
+ kfree(node); \
+ } \
+ attr T* linked_list_front(T)(const linked_list_t(T) * ll) \
+ { \
+ if (!ll->head) { \
+ return NULL; \
+ } \
+ return &ll->head->value; \
+ } \
+ attr T* linked_list_back(T)(const linked_list_t(T) * ll) \
+ { \
+ if (!ll->head) { \
+ return NULL; \
+ } \
+ linked_list_node_t(T)* cur = ll->head; \
+ while (cur->next) cur = cur->next; \
+ return &cur->value; \
+ } \
+ attr size_t linked_list_length(T)(const linked_list_t(T) * ll) \
+ { \
+ linked_list_node_t(T) * cur; \
+ size_t ret = 0; \
+ for (cur = ll->head; cur; cur = cur->next) ++ret; \
+ return ret; \
+ } \
+ attr bool linked_list_find_match(T)( \
+ const linked_list_t(T) * ll, \
+ linked_list_itr_t(T) * itr_out, \
+ bool (*match)(T, void*), \
+ void* closure) \
+ { \
+ linked_list_node_t(T)* prev = NULL; \
+ linked_list_node_t(T)* cur = NULL; \
+ if (!ll || !ll->head) { \
+ return 0; \
+ } \
+ for (cur = ll->head; cur != NULL; cur = (prev = cur)->next) { \
+ if (match(cur->value, closure)) { \
+ itr_out->prev = prev; \
+ itr_out->cur = cur; \
+ return 1; \
+ } \
+ } \
+ return 0; \
+ } \
+ attr bool linked_list_remove_first_match(T)( \
+ linked_list_t(T) * ll, T * out, bool (*match)(T, void*), void* closure) \
+ { \
+ linked_list_itr_t(T) ctx; \
+ if (!linked_list_find_match(T)(ll, &ctx, match, closure)) { \
+ return 0; \
+ } \
+ if (out) *out = ctx.cur->value; \
+ if (!ctx.prev) { \
+ ll->head = ctx.cur->next; \
+ } else { \
+ ctx.prev->next = ctx.cur->next; \
+ } \
+ kfree(ctx.cur); \
+ return 1; \
+ } \
+ int memcmp(const void* s1, const void* s2, size_t n); \
+ static inline bool linked_list___##T##___eq(T elem, void* other) \
+ { \
+ return memcmp(&elem, other, sizeof(T)) == 0; \
+ } \
+ attr bool linked_list_remove(T)(linked_list_t(T) * ll, T val) \
+ { \
+ bool (*fn)(T, void*) = &linked_list___##T##___eq; \
+ bool ret = 0; \
+ while (linked_list_remove_first_match(T)(ll, NULL, fn, &val)) ret = 1; \
+ return ret; \
+ } \
+ _Pragma("GCC diagnostic pop")
#endif /* SHARED_LINKED_LIST_H_ */
diff --git a/src/kern/stdlibrepl.c b/src/kern/stdlibrepl.c
index 588191b..38b8477 100644
--- a/src/kern/stdlibrepl.c
+++ b/src/kern/stdlibrepl.c
@@ -15,14 +15,37 @@ size_t strlen(char* ch)
#ifdef ARCH_STM32L4
-void memcpy(void* dest, void* src, size_t size)
+void* memcpy(void* dest, const void* src, size_t size)
{
uint8_t* dest_ = dest;
- uint8_t* src_ = src;
+ const uint8_t* src_ = src;
- while(size --) {
+ while (size--) {
*(dest_++) = *(src_++);
}
+
+ return dest;
+}
+
+int memcmp(const void* s1_, const void* s2_, size_t size)
+{
+ const uint8_t* s1 = s1_;
+ const uint8_t* s2 = s2_;
+
+ while (size--) {
+ if (*s1 != *s2) {
+ if (*s1 > *s2) {
+ return 1;
+ } else {
+ return -1;
+ }
+ }
+
+ ++s1;
+ ++s2;
+ }
+
+ return 0;
}
#endif
diff --git a/tests/test_linked_list.c b/tests/test_linked_list.c
index 7ec96b5..2c51625 100644
--- a/tests/test_linked_list.c
+++ b/tests/test_linked_list.c
@@ -60,3 +60,25 @@ TEST(linked_list, foreach)
return 0;
}
+
+TEST(linked_list, remove)
+{
+ linked_list_t(int) ll = LINKED_LIST_INIT;
+ linked_list_push_front(int)(&ll, 1);
+ linked_list_push_front(int)(&ll, 2);
+ linked_list_push_front(int)(&ll, 3);
+ linked_list_push_front(int)(&ll, 4);
+ linked_list_push_front(int)(&ll, 4);
+
+ int ec = linked_list_remove(int)(&ll, 4);
+ ASSERT_EQ(!!ec, 1);
+ ec = linked_list_remove(int)(&ll, 2);
+ ASSERT_EQ(!!ec, 1);
+ ec = linked_list_remove(int)(&ll, 1);
+ ASSERT_EQ(!!ec, 1);
+
+ ASSERT_EQ(linked_list_length(int)(&ll), 1);
+ ASSERT_EQ(*linked_list_front(int)(&ll), 3);
+
+ return 0;
+}
generated by cgit (git 2.34.1) at 2025-04-28 19:16:57 +0000