#ifndef SHARED_LINKED_LIST_H_ #define SHARED_LINKED_LIST_H_ #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 \ { \ .head = NULL \ } #define linked_list_foreach(ll, val) \ typeof(ll.head) _cur_ = ll.head; \ typeof(_cur_->value) val; \ if (_cur_) val = _cur_->value; \ for (; _cur_ != NULL; _cur_ = _cur_->next, val = _cur_ ? _cur_->value : val) #define NO_ATTRIBUTE #define LINKED_LIST_DECL(T) LINKED_LIST_INTERNAL_DECL(T, NO_ATTRIBUTE) #define LINKED_LIST_STATIC_DECL(T) LINKED_LIST_INTERNAL_DECL(T, static inline) #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(T) * head; \ } linked_list_t(T); \ \ 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(T) LINKED_LIST_INTERNAL_IMPL(T, NO_ATTRIBUTE) #define LINKED_LIST_STATIC_IMPL(T) LINKED_LIST_INTERNAL_IMPL(T, static inline) #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_ */