From 091043a0df9568b18e9bb49b07762b95e3508108 Mon Sep 17 00:00:00 2001 From: Garrett D'Amore Date: Sun, 11 Dec 2016 22:51:28 -0800 Subject: Added linked list implementation. --- src/core/list.c | 122 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/core/list.h | 54 +++++++++++++++++++++++++ 2 files changed, 176 insertions(+) create mode 100644 src/core/list.c create mode 100644 src/core/list.h (limited to 'src') diff --git a/src/core/list.c b/src/core/list.c new file mode 100644 index 00000000..f59c75e0 --- /dev/null +++ b/src/core/list.c @@ -0,0 +1,122 @@ +/* + * Copyright 2016 Garrett D'Amore + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom + * the Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#include +#include + +#include "core/nng_impl.h" + +/* + * Linked list implementation. We implement a doubly linked list. + * Using pointer arithmetic, we can operate as a list of "anything". + */ + +#define NODE(list, item) \ + (nni_list_node_t)(void *)(((char *)item) + list->ll_offset) +#define ITEM(list, node) \ + (void *)(((char *)node) - list->ll_offset) + +void +nni_list_init_offset(nni_list_t list, size_t offset) +{ + list->ll_offset = offset; + list->ll_head.ln_next = &list->ll_head; + list->ll_head.ln_prev = &list->ll_head; +} + +void * +nni_list_first(nni_list_t list) +{ + nni_list_node_t node = list->ll_head.ln_next; + if (node == &list->ll_head) { + return (NULL); + } + return (ITEM(list, node)); +} + +void * +nni_list_last(nni_list_t list) +{ + nni_list_node_t node = list->ll_head.ln_prev; + if (node == &list->ll_head) { + return (NULL); + } + return (ITEM(list, node)); +} + +void +nni_list_append(nni_list_t list, void *item) +{ + nni_list_node_t node = NODE(list, item); + + node->ln_prev = list->ll_head.ln_prev; + node->ln_next = &list->ll_head; + node->ln_next->ln_prev = node; + node->ln_prev->ln_next = node; +} +void +nni_list_prepend(nni_list_t list, void *item) +{ + nni_list_node_t node = NODE(list, item); + + node->ln_next = list->ll_head.ln_next; + node->ln_prev = &list->ll_head; + node->ln_next->ln_prev = node; + node->ln_prev->ln_next = node; +} + +void * +nni_list_next(nni_list_t list, void *item) +{ + nni_list_node_t node = NODE(list, item); + + if ((node = node->ln_next) == &list->ll_head) { + return (NULL); + } + return (ITEM(list, node)); +} + +void * +nni_list_prev(nni_list_t list, void *item) +{ + nni_list_node_t node = NODE(list, item); + + if ((node = node->ln_prev) == &list->ll_head) { + return (NULL); + } + return (ITEM(list, node)); +} + +void +nni_list_remove(nni_list_t list, void *item) +{ + nni_list_node_t node = NODE(list, item); + node->ln_prev->ln_next = node->ln_next; + node->ln_next->ln_prev = node->ln_prev; +} + +void +nni_list_node_init(nni_list_t list, void *item) +{ + nni_list_node_t node = NODE(list, item); + node->ln_prev = node->ln_next = NULL; +} diff --git a/src/core/list.h b/src/core/list.h new file mode 100644 index 00000000..c55870cb --- /dev/null +++ b/src/core/list.h @@ -0,0 +1,54 @@ +/* + * Copyright 2016 Garrett D'Amore + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom + * the Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included + * in all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +#ifndef CORE_LIST_H +#define CORE_LIST_H + +#include "core/nng_impl.h" + +/* + * In order to make life easy, we just define the list structures + * directly, and let consumers directly inline structures. + */ +typedef struct nni_list_node { + struct nni_list_node *ln_next; + struct nni_list_node *ln_prev; +} *nni_list_node_t; + +typedef struct nni_list { + struct nni_list_node ll_head; + size_t ll_offset; +} *nni_list_t; + +extern void nni_list_init_offset(nni_list_t list, size_t offset); +#define NNI_LIST_INIT(list, type, field) \ + nni_list_init_offset(list, type, (size_t)&((type *)0)->field) +extern void *nni_list_first(nni_list_t list); +extern void *nni_list_last(nni_list_t list); +extern void nni_list_append(nni_list_t list, void *item); +extern void nni_list_prepend(nni_list_t list, void *item); +extern void *nni_list_next(nni_list_t list, void *item); +extern void *nni_list_prev(nni_list_t list, void *item); +extern void nni_list_remove(nni_list_t list, void *item); +extern void nni_list_node_init(nni_list_t, void *); + +#endif /* CORE_MSQUEUE_H */ -- cgit v1.2.3-70-g09d2