1 /*
2 * linklist.c - linked lists
3 *
4 * This file is part of zsh, the Z shell.
5 *
6 * Copyright (c) 1992-1997 Paul Falstad
7 * All rights reserved.
8 *
9 * Permission is hereby granted, without written agreement and without
10 * license or royalty fees, to use, copy, modify, and distribute this
11 * software and to distribute modified versions of this software for any
12 * purpose, provided that the above copyright notice and the following
13 * two paragraphs appear in all copies of this software.
14 *
15 * In no event shall Paul Falstad or the Zsh Development Group be liable
16 * to any party for direct, indirect, special, incidental, or consequential
17 * damages arising out of the use of this software and its documentation,
18 * even if Paul Falstad and the Zsh Development Group have been advised of
19 * the possibility of such damage.
20 *
21 * Paul Falstad and the Zsh Development Group specifically disclaim any
22 * warranties, including, but not limited to, the implied warranties of
23 * merchantability and fitness for a particular purpose. The software
24 * provided hereunder is on an "as is" basis, and Paul Falstad and the
25 * Zsh Development Group have no obligation to provide maintenance,
26 * support, updates, enhancements, or modifications.
27 *
28 */
29
30 #include "zsh.mdh"
31 #include "linklist.pro"
32
33 /*
34 * Anatomy of a LinkList
35 *
36 * LinkList with 4 nodes:
37 *
38 * LinkList is a first last flags (LinkList)
39 * union; see zsh.h next prev dat (LinkNode)
40 * +-------+------+------+
41 * | | | | See comment in subst.c
42 * +------------> | | | | | | about LF_ARRAY.
43 * | +---|---+---|--+------+
44 * | | |
45 * | +------------+ +--------------+
46 * | | |
47 * | \|/ \|/
48 * | +----+ +----+ +----+ +----+
49 * | | | | | | | | \/ | X here is NULL.
50 * | | -------> | -------> | -------> | /\ |
51 * | |next| |next| |next| |next|
52 * | +----+ +----+ +----+ +----+
53 * | | | | | | | | |
54 * +------ | <------- | <------- | <------- |
55 * |prev| |prev| |prev| |prev|
56 * +----+ +----+ +----+ +----+
57 * | | | | | | | | Pointers to data,
58 * |dat | |dat | |dat | |dat | usually char **.
59 * +----+ +----+ +----+ +----+
60 * LinkNode LinkNode LinkNode LinkNode
61 *
62 *
63 * Empty LinkList:
64 * first last flags
65 * +------+------+-------+
66 * +---> | NULL | | 0 |
67 * | | | | | |
68 * | +------+---|--+-------+
69 * | |
70 * +----------------+
71 *
72 * Traversing a LinkList:
73 * Traversing forward through a list uses an iterator-style paradigm.
74 * for (LinkNode node = firstnode(list); node; incnode(node)) {
75 * // Access/manipulate the node using macros (see zsh.h)
76 * }
77 *
78 * Traversing backwards is the same, with a small caveat.
79 * for (LinkNode node = lastnode(list); node != &list->node; decnode(node)) {
80 * // The loop condition should be obvious given the above diagrams.
81 * }
82 *
83 * If you're going to be moving back and forth, best to AND both
84 * conditions.
85 *
86 * while (node && node != &list->node) {
87 * // If both incnode(list) and decnode(list) are used, and it's
88 * // unknown at which end of the list traversal will stop.
89 * }
90 *
91 * Macros and functions prefixed with 'z' (ie znewlinklist,
92 * zinsertlinknode) use permanent allocation, which you have to free
93 * manually (with freelinklist(), maybe?). Non-z-prefixed
94 * macros/functions allocate from heap, which will be automatically
95 * freed.
96 *
97 */
98
99 /* Get an empty linked list header */
100
101 /**/
102 mod_export LinkList
newlinklist(void)103 newlinklist(void)
104 {
105 LinkList list;
106
107 list = (LinkList) zhalloc(sizeof *list);
108 list->list.first = NULL;
109 list->list.last = &list->node;
110 list->list.flags = 0;
111 return list;
112 }
113
114 /**/
115 mod_export LinkList
znewlinklist(void)116 znewlinklist(void)
117 {
118 LinkList list;
119
120 list = (LinkList) zalloc(sizeof *list);
121 if (!list)
122 return NULL;
123 list->list.first = NULL;
124 list->list.last = &list->node;
125 list->list.flags = 0;
126 return list;
127 }
128
129 /* Insert a node in a linked list after a given node */
130
131 /**/
132 mod_export LinkNode
insertlinknode(LinkList list,LinkNode node,void * dat)133 insertlinknode(LinkList list, LinkNode node, void *dat)
134 {
135 LinkNode tmp, new;
136
137 tmp = node->next;
138 node->next = new = (LinkNode) zhalloc(sizeof *tmp);
139 new->prev = node;
140 new->dat = dat;
141 new->next = tmp;
142 if (tmp)
143 tmp->prev = new;
144 else
145 list->list.last = new;
146 return new;
147 }
148
149 /**/
150 mod_export LinkNode
zinsertlinknode(LinkList list,LinkNode node,void * dat)151 zinsertlinknode(LinkList list, LinkNode node, void *dat)
152 {
153 LinkNode tmp, new;
154
155 tmp = node->next;
156 node->next = new = (LinkNode) zalloc(sizeof *tmp);
157 if (!new)
158 return NULL;
159 new->prev = node;
160 new->dat = dat;
161 new->next = tmp;
162 if (tmp)
163 tmp->prev = new;
164 else
165 list->list.last = new;
166 return new;
167 }
168
169 /* Insert an already-existing node into a linked list after a given node */
170
171 /**/
172 mod_export LinkNode
uinsertlinknode(LinkList list,LinkNode node,LinkNode new)173 uinsertlinknode(LinkList list, LinkNode node, LinkNode new)
174 {
175 LinkNode tmp = node->next;
176 node->next = new;
177 new->prev = node;
178 new->next = tmp;
179 if (tmp)
180 tmp->prev = new;
181 else
182 list->list.last = new;
183 return new;
184 }
185
186 /* Insert a list in another list */
187
188 /**/
189 mod_export void
insertlinklist(LinkList l,LinkNode where,LinkList x)190 insertlinklist(LinkList l, LinkNode where, LinkList x)
191 {
192 LinkNode nx;
193
194 nx = where->next;
195 if (!firstnode(l))
196 return;
197 where->next = firstnode(l);
198 l->list.last->next = nx;
199 l->list.first->prev = where;
200 if (nx)
201 nx->prev = lastnode(l);
202 else
203 x->list.last = lastnode(l);
204 }
205
206 /* Pop the top node off a linked list and free it. */
207
208 /**/
209 mod_export void *
getlinknode(LinkList list)210 getlinknode(LinkList list)
211 {
212 void *dat;
213 LinkNode node;
214
215 if (!(node = firstnode(list)))
216 return NULL;
217 dat = node->dat;
218 list->list.first = node->next;
219 if (node->next)
220 node->next->prev = &list->node;
221 else
222 list->list.last = &list->node;
223 zfree(node, sizeof *node);
224 return dat;
225 }
226
227 /* Pop the top node off a linked list without freeing it. */
228
229 /**/
230 mod_export void *
ugetnode(LinkList list)231 ugetnode(LinkList list)
232 {
233 void *dat;
234 LinkNode node;
235
236 if (!(node = firstnode(list)))
237 return NULL;
238 dat = node->dat;
239 list->list.first = node->next;
240 if (node->next)
241 node->next->prev = &list->node;
242 else
243 list->list.last = &list->node;
244 return dat;
245 }
246
247 /* Remove a node from a linked list */
248
249 /**/
250 mod_export void *
remnode(LinkList list,LinkNode nd)251 remnode(LinkList list, LinkNode nd)
252 {
253 void *dat;
254
255 nd->prev->next = nd->next;
256 if (nd->next)
257 nd->next->prev = nd->prev;
258 else
259 list->list.last = nd->prev;
260 dat = nd->dat;
261 zfree(nd, sizeof *nd);
262
263 return dat;
264 }
265
266 /* Remove a node from a linked list without freeing */
267
268 /**/
269 mod_export void *
uremnode(LinkList list,LinkNode nd)270 uremnode(LinkList list, LinkNode nd)
271 {
272 void *dat;
273
274 nd->prev->next = nd->next;
275 if (nd->next)
276 nd->next->prev = nd->prev;
277 else
278 list->list.last = nd->prev;
279 dat = nd->dat;
280 return dat;
281 }
282
283 /* Free a linked list */
284
285 /**/
286 mod_export void
freelinklist(LinkList list,FreeFunc freefunc)287 freelinklist(LinkList list, FreeFunc freefunc)
288 {
289 LinkNode node, next;
290
291 for (node = firstnode(list); node; node = next) {
292 next = node->next;
293 if (freefunc)
294 freefunc(node->dat);
295 zfree(node, sizeof *node);
296 }
297 zfree(list, sizeof *list);
298 }
299
300 /* Count the number of nodes in a linked list */
301
302 /**/
303 mod_export int
countlinknodes(LinkList list)304 countlinknodes(LinkList list)
305 {
306 LinkNode nd;
307 int ct = 0;
308
309 for (nd = firstnode(list); nd; incnode(nd), ct++);
310 return ct;
311 }
312
313 /* Make specified node first, moving preceding nodes to end */
314
315 /**/
316 mod_export void
rolllist(LinkList l,LinkNode nd)317 rolllist(LinkList l, LinkNode nd)
318 {
319 l->list.last->next = firstnode(l);
320 l->list.first->prev = lastnode(l);
321 l->list.first = nd;
322 l->list.last = nd->prev;
323 nd->prev = &l->node;
324 l->list.last->next = 0;
325 }
326
327 /* Create linklist of specified size. node->dats are not initialized. */
328
329 /**/
330 mod_export LinkList
newsizedlist(int size)331 newsizedlist(int size)
332 {
333 LinkList list;
334 LinkNode node;
335
336 list = (LinkList) zhalloc(sizeof *list + (size * sizeof *node));
337
338 list->list.first = &list[1].node;
339 for (node = firstnode(list); size; size--, node++) {
340 node->prev = node - 1;
341 node->next = node + 1;
342 }
343 list->list.last = node - 1;
344 list->list.first->prev = &list->node;
345 node[-1].next = NULL;
346
347 return list;
348 }
349
350 /*
351 * Join two linked lists. Neither may be null, though either
352 * may be empty.
353 *
354 * It is assumed the pieces come from the heap, but if not it is
355 * safe to free LinkList second.
356 */
357
358 /**/
359 mod_export LinkList
joinlists(LinkList first,LinkList second)360 joinlists(LinkList first, LinkList second)
361 {
362 LinkNode moveme = firstnode(second);
363 if (moveme) {
364 if (firstnode(first)) {
365 LinkNode anchor = lastnode(first);
366 anchor->next = moveme;
367 moveme->prev = anchor;
368 } else {
369 first->list.first = moveme;
370 moveme->prev = &first->node;
371 }
372 first->list.last = second->list.last;
373
374 second->list.first = second->list.last = NULL;
375 }
376 return first;
377 }
378
379 /*
380 * Return the node whose data is the pointer "dat", else NULL.
381 * Can be used as a boolean test.
382 */
383
384 /**/
385 mod_export LinkNode
linknodebydatum(LinkList list,void * dat)386 linknodebydatum(LinkList list, void *dat)
387 {
388 LinkNode node;
389
390 for (node = firstnode(list); node; incnode(node))
391 if (getdata(node) == dat)
392 return node;
393
394 return NULL;
395 }
396
397 /*
398 * Return the node whose data matches the string "dat", else NULL.
399 */
400
401 /**/
402 mod_export LinkNode
linknodebystring(LinkList list,char * dat)403 linknodebystring(LinkList list, char *dat)
404 {
405 LinkNode node;
406
407 for (node = firstnode(list); node; incnode(node))
408 if (!strcmp((char *)getdata(node), dat))
409 return node;
410
411 return NULL;
412 }
413
414 /*
415 * Convert a linked list whose data elements are strings to
416 * an array. Memory is off the heap and the elements of the
417 * array are the same elements as the linked list data if copy is
418 * 0, else copied onto the heap.
419 */
420
421 /**/
422 mod_export char **
hlinklist2array(LinkList list,int copy)423 hlinklist2array(LinkList list, int copy)
424 {
425 int l = countlinknodes(list);
426 char **ret = (char **) zhalloc((l + 1) * sizeof(char *)), **p;
427 LinkNode n;
428
429 for (n = firstnode(list), p = ret; n; incnode(n), p++) {
430 *p = (char *) getdata(n);
431 if (copy)
432 *p = dupstring(*p);
433 }
434 *p = NULL;
435
436 return ret;
437 }
438
439 /*
440 * Convert a linked list whose data elements are strings to
441 * an array. The result is a permanently allocated, freearrayable
442 * array.
443 */
444
445 /**/
446 mod_export char **
zlinklist2array(LinkList list)447 zlinklist2array(LinkList list)
448 {
449 int l = countlinknodes(list);
450 char **ret = (char **) zalloc((l + 1) * sizeof(char *)), **p;
451 LinkNode n;
452
453 for (n = firstnode(list), p = ret; n; incnode(n), p++) {
454 *p = ztrdup((char *) getdata(n));
455 }
456 *p = NULL;
457
458 return ret;
459 }
460