1 //
2 // Copyright 2017 Capitar IT Group BV <info@capitar.com>
3 // Copyright 2020 Staysail Systems, Inc. <info@staysail.tech>
4 //
5 // This software is supplied under the terms of the MIT License, a
6 // copy of which should be located in the distribution where this
7 // file was obtained (LICENSE.txt). A copy of the license may also be
8 // found online at https://opensource.org/licenses/MIT.
9 //
10
11 #include <stdlib.h>
12 #include <string.h>
13
14 #include "core/nng_impl.h"
15
16 // Linked list implementation. We implement a doubly linked list.
17 // Using pointer arithmetic, we can operate as a list of "anything".
18
19 #define NODE(list, item) \
20 (nni_list_node *) (void *)(((char *) item) + list->ll_offset)
21 #define ITEM(list, node) (void *) (((char *) node) - list->ll_offset)
22
23 void
nni_list_init_offset(nni_list * list,size_t offset)24 nni_list_init_offset(nni_list *list, size_t offset)
25 {
26 list->ll_offset = offset;
27 list->ll_head.ln_next = &list->ll_head;
28 list->ll_head.ln_prev = &list->ll_head;
29 }
30
31 void *
nni_list_first(const nni_list * list)32 nni_list_first(const nni_list *list)
33 {
34 nni_list_node *node = list->ll_head.ln_next;
35
36 if (node == &list->ll_head) {
37 return (NULL);
38 }
39 return (ITEM(list, node));
40 }
41
42 void *
nni_list_last(const nni_list * list)43 nni_list_last(const nni_list *list)
44 {
45 nni_list_node *node = list->ll_head.ln_prev;
46
47 if (node == &list->ll_head) {
48 return (NULL);
49 }
50 return (ITEM(list, node));
51 }
52
53 void
nni_list_append(nni_list * list,void * item)54 nni_list_append(nni_list *list, void *item)
55 {
56 nni_list_node *node = NODE(list, item);
57
58 if ((node->ln_next != NULL) || (node->ln_prev != NULL)) {
59 nni_panic("appending node already on a list or not inited");
60 }
61 node->ln_prev = list->ll_head.ln_prev;
62 node->ln_next = &list->ll_head;
63 node->ln_next->ln_prev = node;
64 node->ln_prev->ln_next = node;
65 }
66
67 void
nni_list_prepend(nni_list * list,void * item)68 nni_list_prepend(nni_list *list, void *item)
69 {
70 nni_list_node *node = NODE(list, item);
71
72 if ((node->ln_next != NULL) || (node->ln_prev != NULL)) {
73 nni_panic("prepending node already on a list or not inited");
74 }
75 node->ln_next = list->ll_head.ln_next;
76 node->ln_prev = &list->ll_head;
77 node->ln_next->ln_prev = node;
78 node->ln_prev->ln_next = node;
79 }
80
81 void
nni_list_insert_before(nni_list * list,void * item,void * before)82 nni_list_insert_before(nni_list *list, void *item, void *before)
83 {
84 nni_list_node *node = NODE(list, item);
85 nni_list_node *where = NODE(list, before);
86
87 if ((node->ln_next != NULL) || (node->ln_prev != NULL)) {
88 nni_panic("inserting node already on a list or not inited");
89 }
90 node->ln_next = where;
91 node->ln_prev = where->ln_prev;
92 node->ln_next->ln_prev = node;
93 node->ln_prev->ln_next = node;
94 }
95
96 void
nni_list_insert_after(nni_list * list,void * item,void * after)97 nni_list_insert_after(nni_list *list, void *item, void *after)
98 {
99 nni_list_node *node = NODE(list, item);
100 nni_list_node *where = NODE(list, after);
101
102 if ((node->ln_next != NULL) || (node->ln_prev != NULL)) {
103 nni_panic("inserting node already on a list or not inited");
104 }
105 node->ln_prev = where;
106 node->ln_next = where->ln_next;
107 node->ln_next->ln_prev = node;
108 node->ln_prev->ln_next = node;
109 }
110
111 void *
nni_list_next(const nni_list * list,void * item)112 nni_list_next(const nni_list *list, void *item)
113 {
114 nni_list_node *node = NODE(list, item);
115
116 if (((node = node->ln_next) == &list->ll_head) || (node == NULL)) {
117 return (NULL);
118 }
119 return (ITEM(list, node));
120 }
121
122 void *
nni_list_prev(const nni_list * list,void * item)123 nni_list_prev(const nni_list *list, void *item)
124 {
125 nni_list_node *node = NODE(list, item);
126
127 if (((node = node->ln_prev) == &list->ll_head) || (node == NULL)) {
128 return (NULL);
129 }
130 return (ITEM(list, node));
131 }
132
133 void
nni_list_remove(nni_list * list,void * item)134 nni_list_remove(nni_list *list, void *item)
135 {
136 nni_list_node *node = NODE(list, item);
137
138 node->ln_prev->ln_next = node->ln_next;
139 node->ln_next->ln_prev = node->ln_prev;
140 node->ln_next = NULL;
141 node->ln_prev = NULL;
142 }
143
144 int
nni_list_active(nni_list * list,void * item)145 nni_list_active(nni_list *list, void *item)
146 {
147 nni_list_node *node = NODE(list, item);
148
149 return (node->ln_next == NULL ? 0 : 1);
150 }
151
152 int
nni_list_empty(nni_list * list)153 nni_list_empty(nni_list *list)
154 {
155 // The first check ensures that we treat an uninitialized list
156 // as empty. This use useful for statically initialized lists.
157 return ((list->ll_head.ln_next == NULL) ||
158 (list->ll_head.ln_next == &list->ll_head));
159 }
160
161 int
nni_list_node_active(nni_list_node * node)162 nni_list_node_active(nni_list_node *node)
163 {
164 return (node->ln_next == NULL ? 0 : 1);
165 }
166
167 void
nni_list_node_remove(nni_list_node * node)168 nni_list_node_remove(nni_list_node *node)
169 {
170 if (node->ln_next != NULL) {
171 node->ln_prev->ln_next = node->ln_next;
172 node->ln_next->ln_prev = node->ln_prev;
173 node->ln_next = NULL;
174 node->ln_prev = NULL;
175 }
176 }
177