1 /*
2 * ircd-hybrid: an advanced, lightweight Internet Relay Chat Daemon (ircd)
3 *
4 * Copyright (c) 2000-2021 ircd-hybrid development team
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
19 * USA
20 */
21
22 /*! \file list.c
23 * \brief Maintains doubly-linked lists.
24 * \version $Id: list.c 9858 2021-01-01 04:43:42Z michael $
25 */
26
27 #include "stdinc.h"
28 #include "list.h"
29 #include "memory.h"
30
31
32 /* make_dlink_node()
33 *
34 * inputs - NONE
35 * output - pointer to new dlink_node
36 * side effects - NONE
37 */
38 dlink_node *
make_dlink_node(void)39 make_dlink_node(void)
40 {
41 dlink_node *node = xcalloc(sizeof(*node));
42
43 return node;
44 }
45
46 /* free_dlink_node()
47 *
48 * inputs - pointer to dlink_node
49 * output - NONE
50 * side effects - free given dlink_node
51 */
52 void
free_dlink_node(dlink_node * node)53 free_dlink_node(dlink_node *node)
54 {
55 xfree(node);
56 }
57
58 /*
59 * dlink_ routines are stolen from squid, except for dlinkAddBefore,
60 * which is mine.
61 * -- adrian
62 */
63 void
dlinkAdd(void * data,dlink_node * m,dlink_list * list)64 dlinkAdd(void *data, dlink_node *m, dlink_list *list)
65 {
66 m->data = data;
67 m->prev = NULL;
68 m->next = list->head;
69
70 /* Assumption: If list->tail != NULL, list->head != NULL */
71 if (list->head)
72 list->head->prev = m;
73 else if (list->tail == NULL)
74 list->tail = m;
75
76 list->head = m;
77 list->length++;
78 }
79
80 void
dlinkAddBefore(dlink_node * b,void * data,dlink_node * m,dlink_list * list)81 dlinkAddBefore(dlink_node *b, void *data, dlink_node *m, dlink_list *list)
82 {
83 /* Shortcut - if it's the first one, call dlinkAdd only */
84 if (b == list->head)
85 dlinkAdd(data, m, list);
86 else
87 {
88 m->data = data;
89 b->prev->next = m;
90 m->prev = b->prev;
91 b->prev = m;
92 m->next = b;
93 list->length++;
94 }
95 }
96
97 void
dlinkAddTail(void * data,dlink_node * m,dlink_list * list)98 dlinkAddTail(void *data, dlink_node *m, dlink_list *list)
99 {
100 m->data = data;
101 m->next = NULL;
102 m->prev = list->tail;
103
104 /* Assumption: If list->tail != NULL, list->head != NULL */
105 if (list->tail)
106 list->tail->next = m;
107 else if (list->head == NULL)
108 list->head = m;
109
110 list->tail = m;
111 list->length++;
112 }
113
114 /* Execution profiles show that this function is called the most
115 * often of all non-spontaneous functions. So it had better be
116 * efficient. */
117 void
dlinkDelete(dlink_node * m,dlink_list * list)118 dlinkDelete(dlink_node *m, dlink_list *list)
119 {
120 assert(list->length > 0);
121
122 /* Assumption: If m->next == NULL, then list->tail == m
123 * and: If m->prev == NULL, then list->head == m
124 */
125 if (m->next)
126 m->next->prev = m->prev;
127 else
128 {
129 assert(list->tail == m);
130 list->tail = m->prev;
131 }
132
133 if (m->prev)
134 m->prev->next = m->next;
135 else
136 {
137 assert(list->head == m);
138 list->head = m->next;
139 }
140
141 /* Set this to NULL does matter */
142 m->next = NULL;
143 m->prev = NULL;
144
145 list->length--;
146 }
147
148 /*
149 * dlinkFind
150 * inputs - list to search
151 * - data
152 * output - pointer to link or NULL if not found
153 * side effects - Look for ptr in the linked listed pointed to by link.
154 */
155 dlink_node *
dlinkFind(dlink_list * list,const void * data)156 dlinkFind(dlink_list *list, const void *data)
157 {
158 dlink_node *node;
159
160 DLINK_FOREACH(node, list->head)
161 if (node->data == data)
162 return node;
163
164 return NULL;
165 }
166
167 void
dlinkMoveList(dlink_list * from,dlink_list * to)168 dlinkMoveList(dlink_list *from, dlink_list *to)
169 {
170 /* There are three cases */
171 /* case one, nothing in from list */
172 if (from->head == NULL)
173 return;
174
175 /* case two, nothing in to list */
176 /* actually if to->head is NULL and to->tail isn't, that's a bug */
177 if (to->head == NULL)
178 {
179 to->head = from->head;
180 to->tail = from->tail;
181 from->head = from->tail = NULL;
182 to->length = from->length;
183 from->length = 0;
184 return;
185 }
186
187 /* third case play with the links */
188 from->tail->next = to->head;
189 from->head->prev = to->head->prev;
190 to->head->prev = from->tail;
191 to->head = from->head;
192 from->head = from->tail = NULL;
193 to->length += from->length;
194 from->length = 0;
195 /* I think I got that right */
196 }
197
198 void
dlink_move_node(dlink_node * m,dlink_list * list_del,dlink_list * list_add)199 dlink_move_node(dlink_node *m, dlink_list *list_del, dlink_list *list_add)
200 {
201 /* Assumption: If m->next == NULL, then list_del->tail == m
202 * and: If m->prev == NULL, then list_del->head == m
203 */
204 if (m->next)
205 m->next->prev = m->prev;
206 else
207 {
208 assert(list_del->tail == m);
209 list_del->tail = m->prev;
210 }
211
212 if (m->prev)
213 m->prev->next = m->next;
214 else
215 {
216 assert(list_del->head == m);
217 list_del->head = m->next;
218 }
219
220 /* Set this to NULL does matter */
221 m->prev = NULL;
222 m->next = list_add->head;
223
224 /* Assumption: If list_add->tail != NULL, list_add->head != NULL */
225 if (list_add->head)
226 list_add->head->prev = m;
227 else if (list_add->tail == NULL)
228 list_add->tail = m;
229
230 list_add->head = m;
231 list_add->length++;
232 list_del->length--;
233 }
234
235 dlink_node *
dlinkFindDelete(dlink_list * list,void * data)236 dlinkFindDelete(dlink_list *list, void *data)
237 {
238 dlink_node *m;
239
240 DLINK_FOREACH(m, list->head)
241 {
242 if (m->data == data)
243 {
244 dlinkDelete(m, list);
245 return m;
246 }
247 }
248
249 return NULL;
250 }
251