diff options
Diffstat (limited to 'include/shared/linked_list.h')
| -rw-r--r-- | include/shared/linked_list.h | 277 |
1 files changed, 173 insertions, 104 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_ */ |