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/**/
102mod_export LinkList
103newlinklist(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/**/
115mod_export LinkList
116znewlinklist(void)
117{
118    LinkList list;
119
120    list = (LinkList) zalloc(sizeof *list);
121    list->list.first = NULL;
122    list->list.last = &list->node;
123    list->list.flags = 0;
124    return list;
125}
126
127/* Insert a node in a linked list after a given node */
128
129/**/
130mod_export LinkNode
131insertlinknode(LinkList list, LinkNode node, void *dat)
132{
133    LinkNode tmp, new;
134
135    tmp = node->next;
136    node->next = new = (LinkNode) zhalloc(sizeof *tmp);
137    new->prev = node;
138    new->dat = dat;
139    new->next = tmp;
140    if (tmp)
141	tmp->prev = new;
142    else
143	list->list.last = new;
144    return new;
145}
146
147/**/
148mod_export LinkNode
149zinsertlinknode(LinkList list, LinkNode node, void *dat)
150{
151    LinkNode tmp, new;
152
153    tmp = node->next;
154    node->next = new = (LinkNode) zalloc(sizeof *tmp);
155    new->prev = node;
156    new->dat = dat;
157    new->next = tmp;
158    if (tmp)
159	tmp->prev = new;
160    else
161	list->list.last = new;
162    return new;
163}
164
165/* Insert an already-existing node into a linked list after a given node */
166
167/**/
168mod_export LinkNode
169uinsertlinknode(LinkList list, LinkNode node, LinkNode new)
170{
171    LinkNode tmp = node->next;
172    node->next = new;
173    new->prev = node;
174    new->next = tmp;
175    if (tmp)
176	tmp->prev = new;
177    else
178	list->list.last = new;
179    return new;
180}
181
182/* Insert a list in another list */
183
184/**/
185mod_export void
186insertlinklist(LinkList l, LinkNode where, LinkList x)
187{
188    LinkNode nx;
189
190    nx = where->next;
191    if (!firstnode(l))
192	return;
193    where->next = firstnode(l);
194    l->list.last->next = nx;
195    l->list.first->prev = where;
196    if (nx)
197	nx->prev = lastnode(l);
198    else
199	x->list.last = lastnode(l);
200}
201
202/* Pop the top node off a linked list and free it. */
203
204/**/
205mod_export void *
206getlinknode(LinkList list)
207{
208    void *dat;
209    LinkNode node;
210
211    if (!(node = firstnode(list)))
212	return NULL;
213    dat = node->dat;
214    list->list.first = node->next;
215    if (node->next)
216	node->next->prev = &list->node;
217    else
218	list->list.last = &list->node;
219    zfree(node, sizeof *node);
220    return dat;
221}
222
223/* Pop the top node off a linked list without freeing it. */
224
225/**/
226mod_export void *
227ugetnode(LinkList list)
228{
229    void *dat;
230    LinkNode node;
231
232    if (!(node = firstnode(list)))
233	return NULL;
234    dat = node->dat;
235    list->list.first = node->next;
236    if (node->next)
237	node->next->prev = &list->node;
238    else
239	list->list.last = &list->node;
240    return dat;
241}
242
243/* Remove a node from a linked list */
244
245/**/
246mod_export void *
247remnode(LinkList list, LinkNode nd)
248{
249    void *dat;
250
251    nd->prev->next = nd->next;
252    if (nd->next)
253	nd->next->prev = nd->prev;
254    else
255	list->list.last = nd->prev;
256    dat = nd->dat;
257    zfree(nd, sizeof *nd);
258
259    return dat;
260}
261
262/* Remove a node from a linked list without freeing */
263
264/**/
265mod_export void *
266uremnode(LinkList list, LinkNode nd)
267{
268    void *dat;
269
270    nd->prev->next = nd->next;
271    if (nd->next)
272	nd->next->prev = nd->prev;
273    else
274	list->list.last = nd->prev;
275    dat = nd->dat;
276    return dat;
277}
278
279/* Free a linked list */
280
281/**/
282mod_export void
283freelinklist(LinkList list, FreeFunc freefunc)
284{
285    LinkNode node, next;
286
287    for (node = firstnode(list); node; node = next) {
288	next = node->next;
289	if (freefunc)
290	    freefunc(node->dat);
291	zfree(node, sizeof *node);
292    }
293    zfree(list, sizeof *list);
294}
295
296/* Count the number of nodes in a linked list */
297
298/**/
299mod_export int
300countlinknodes(LinkList list)
301{
302    LinkNode nd;
303    int ct = 0;
304
305    for (nd = firstnode(list); nd; incnode(nd), ct++);
306    return ct;
307}
308
309/* Make specified node first, moving preceding nodes to end */
310
311/**/
312mod_export void
313rolllist(LinkList l, LinkNode nd)
314{
315    l->list.last->next = firstnode(l);
316    l->list.first->prev = lastnode(l);
317    l->list.first = nd;
318    l->list.last = nd->prev;
319    nd->prev = &l->node;
320    l->list.last->next = 0;
321}
322
323/* Create linklist of specified size. node->dats are not initialized. */
324
325/**/
326mod_export LinkList
327newsizedlist(int size)
328{
329    LinkList list;
330    LinkNode node;
331
332    list = (LinkList) zhalloc(sizeof *list + (size * sizeof *node));
333
334    list->list.first = &list[1].node;
335    for (node = firstnode(list); size; size--, node++) {
336	node->prev = node - 1;
337	node->next = node + 1;
338    }
339    list->list.last = node - 1;
340    list->list.first->prev = &list->node;
341    node[-1].next = NULL;
342
343    return list;
344}
345
346/*
347 * Return the node whose data is the pointer "dat", else NULL.
348 * Can be used as a boolean test.
349 */
350
351/**/
352mod_export LinkNode
353linknodebydatum(LinkList list, void *dat)
354{
355    LinkNode node;
356
357    for (node = firstnode(list); node; incnode(node))
358	if (getdata(node) == dat)
359	    return node;
360
361    return NULL;
362}
363
364/*
365 * Return the node whose data matches the string "dat", else NULL.
366 */
367
368/**/
369mod_export LinkNode
370linknodebystring(LinkList list, char *dat)
371{
372    LinkNode node;
373
374    for (node = firstnode(list); node; incnode(node))
375	if (!strcmp((char *)getdata(node), dat))
376	    return node;
377
378    return NULL;
379}
380
381/*
382 * Convert a linked list whose data elements are strings to
383 * an array.  Memory is off the heap and the elements of the
384 * array are the same elements as the linked list data if copy is
385 * 0, else copied onto the heap.
386 */
387
388/**/
389mod_export char **
390hlinklist2array(LinkList list, int copy)
391{
392    int l = countlinknodes(list);
393    char **ret = (char **) zhalloc((l + 1) * sizeof(char *)), **p;
394    LinkNode n;
395
396    for (n = firstnode(list), p = ret; n; incnode(n), p++) {
397	*p = (char *) getdata(n);
398	if (copy)
399	    *p = dupstring(*p);
400    }
401    *p = NULL;
402
403    return ret;
404}
405
406/*
407 * Convert a linked list whose data elements are strings to
408 * an array.  The result is a permanently allocated, freearrayable
409 * array.
410 */
411
412/**/
413mod_export char **
414zlinklist2array(LinkList list)
415{
416    int l = countlinknodes(list);
417    char **ret = (char **) zalloc((l + 1) * sizeof(char *)), **p;
418    LinkNode n;
419
420    for (n = firstnode(list), p = ret; n; incnode(n), p++) {
421	*p = ztrdup((char *) getdata(n));
422    }
423    *p = NULL;
424
425    return ret;
426}
427