linklist.c 9.96 KB
Newer Older
Tanaka Akira's avatar
Tanaka Akira committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
/*
 * linklist.c - linked lists
 *
 * This file is part of zsh, the Z shell.
 *
 * Copyright (c) 1992-1997 Paul Falstad
 * All rights reserved.
 *
 * Permission is hereby granted, without written agreement and without
 * license or royalty fees, to use, copy, modify, and distribute this
 * software and to distribute modified versions of this software for any
 * purpose, provided that the above copyright notice and the following
 * two paragraphs appear in all copies of this software.
 *
 * In no event shall Paul Falstad or the Zsh Development Group be liable
 * to any party for direct, indirect, special, incidental, or consequential
 * damages arising out of the use of this software and its documentation,
 * even if Paul Falstad and the Zsh Development Group have been advised of
 * the possibility of such damage.
 *
 * Paul Falstad and the Zsh Development Group specifically disclaim any
 * warranties, including, but not limited to, the implied warranties of
 * merchantability and fitness for a particular purpose.  The software
 * provided hereunder is on an "as is" basis, and Paul Falstad and the
 * Zsh Development Group have no obligation to provide maintenance,
 * support, updates, enhancements, or modifications.
 *
 */

#include "zsh.mdh"
#include "linklist.pro"

33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98
/*
 * Anatomy of a LinkList
 *
 * LinkList with 4 nodes:
 *
 * LinkList is a        first   last   flags   (LinkList)
 * union; see zsh.h     next    prev   dat     (LinkNode)
 *                    +-------+------+------+
 *                    |       |      |      | See comment in subst.c
 *     +------------> |   |   |   |  |      | about LF_ARRAY.
 *     |              +---|---+---|--+------+
 *     |                  |       |
 *     |     +------------+       +--------------+
 *     |     |                                   |
 *     |    \|/                                 \|/
 *     |   +----+      +----+      +----+      +----+
 *     |   |    |      |    |      |    |      | \/ |  X here is NULL.
 *     |   |  -------> |  -------> |  -------> | /\ |
 *     |   |next|      |next|      |next|      |next|
 *     |   +----+      +----+      +----+      +----+
 *     |   |    |      |    |      |    |      |    |
 *     +------  | <-------  | <-------  | <-------  |
 *         |prev|      |prev|      |prev|      |prev|
 *         +----+      +----+      +----+      +----+
 *         |    |      |    |      |    |      |    | Pointers to data,
 *         |dat |      |dat |      |dat |      |dat | usually char **.
 *         +----+      +----+      +----+      +----+
 *        LinkNode    LinkNode    LinkNode    LinkNode
 *
 *
 * Empty LinkList:
 *                    first   last   flags
 *                   +------+------+-------+
 *             +---> | NULL |      |   0   |
 *             |     |      |   |  |       |
 *             |     +------+---|--+-------+
 *             |                |
 *             +----------------+
 *
 * Traversing a LinkList:
 * Traversing forward through a list uses an iterator-style paradigm.
 * for (LinkNode node = firstnode(list); node; incnode(node)) {
 *     // Access/manipulate the node using macros (see zsh.h)
 * }
 *
 * Traversing backwards is the same, with a small caveat.
 * for (LinkNode node = lastnode(list); node != &list->node; decnode(node)) {
 *     // The loop condition should be obvious given the above diagrams.
 * }
 *
 * If you're going to be moving back and forth, best to AND both
 * conditions.
 *
 * while (node && node != &list->node) {
 *     // If both incnode(list) and decnode(list) are used, and it's
 *     // unknown at which end of the list traversal will stop.
 * }
 *
 * Macros and functions prefixed with 'z' (ie znewlinklist,
 * zinsertlinknode) use permanent allocation, which you have to free
 * manually (with freelinklist(), maybe?). Non-z-prefixed
 * macros/functions allocate from heap, which will be automatically
 * freed.
 *
 */

Tanaka Akira's avatar
Tanaka Akira committed
99 100 101
/* Get an empty linked list header */

/**/
102
mod_export LinkList
Tanaka Akira's avatar
Tanaka Akira committed
103 104 105 106
newlinklist(void)
{
    LinkList list;

107
    list = (LinkList) zhalloc(sizeof *list);
108 109
    list->list.first = NULL;
    list->list.last = &list->node;
110
    list->list.flags = 0;
111 112 113 114 115 116 117 118 119 120
    return list;
}

/**/
mod_export LinkList
znewlinklist(void)
{
    LinkList list;

    list = (LinkList) zalloc(sizeof *list);
121 122
    if (!list)
	return NULL;
123 124
    list->list.first = NULL;
    list->list.last = &list->node;
125
    list->list.flags = 0;
Tanaka Akira's avatar
Tanaka Akira committed
126 127 128 129 130 131
    return list;
}

/* Insert a node in a linked list after a given node */

/**/
132
mod_export LinkNode
Tanaka Akira's avatar
Tanaka Akira committed
133 134 135 136 137
insertlinknode(LinkList list, LinkNode node, void *dat)
{
    LinkNode tmp, new;

    tmp = node->next;
138
    node->next = new = (LinkNode) zhalloc(sizeof *tmp);
139
    new->prev = node;
140 141 142
    new->dat = dat;
    new->next = tmp;
    if (tmp)
143
	tmp->prev = new;
144
    else
145
	list->list.last = new;
146 147 148 149 150 151 152 153 154 155 156
    return new;
}

/**/
mod_export LinkNode
zinsertlinknode(LinkList list, LinkNode node, void *dat)
{
    LinkNode tmp, new;

    tmp = node->next;
    node->next = new = (LinkNode) zalloc(sizeof *tmp);
157 158
    if (!new)
	return NULL;
159
    new->prev = node;
Tanaka Akira's avatar
Tanaka Akira committed
160 161 162
    new->dat = dat;
    new->next = tmp;
    if (tmp)
163
	tmp->prev = new;
Tanaka Akira's avatar
Tanaka Akira committed
164
    else
165
	list->list.last = new;
Tanaka Akira's avatar
Tanaka Akira committed
166 167 168 169 170 171
    return new;
}

/* Insert an already-existing node into a linked list after a given node */

/**/
172
mod_export LinkNode
Tanaka Akira's avatar
Tanaka Akira committed
173 174 175 176
uinsertlinknode(LinkList list, LinkNode node, LinkNode new)
{
    LinkNode tmp = node->next;
    node->next = new;
177
    new->prev = node;
Tanaka Akira's avatar
Tanaka Akira committed
178 179
    new->next = tmp;
    if (tmp)
180
	tmp->prev = new;
Tanaka Akira's avatar
Tanaka Akira committed
181
    else
182
	list->list.last = new;
Tanaka Akira's avatar
Tanaka Akira committed
183 184 185 186 187 188
    return new;
}

/* Insert a list in another list */

/**/
189
mod_export void
Tanaka Akira's avatar
Tanaka Akira committed
190 191 192 193 194
insertlinklist(LinkList l, LinkNode where, LinkList x)
{
    LinkNode nx;

    nx = where->next;
195
    if (!firstnode(l))
Tanaka Akira's avatar
Tanaka Akira committed
196
	return;
197 198
    where->next = firstnode(l);
    l->list.last->next = nx;
199
    l->list.first->prev = where;
Tanaka Akira's avatar
Tanaka Akira committed
200
    if (nx)
201
	nx->prev = lastnode(l);
Tanaka Akira's avatar
Tanaka Akira committed
202
    else
203
	x->list.last = lastnode(l);
Tanaka Akira's avatar
Tanaka Akira committed
204 205
}

206
/* Pop the top node off a linked list and free it. */
Tanaka Akira's avatar
Tanaka Akira committed
207 208

/**/
209
mod_export void *
Tanaka Akira's avatar
Tanaka Akira committed
210 211 212 213 214
getlinknode(LinkList list)
{
    void *dat;
    LinkNode node;

215
    if (!(node = firstnode(list)))
Tanaka Akira's avatar
Tanaka Akira committed
216 217
	return NULL;
    dat = node->dat;
218
    list->list.first = node->next;
Tanaka Akira's avatar
Tanaka Akira committed
219
    if (node->next)
220
	node->next->prev = &list->node;
Tanaka Akira's avatar
Tanaka Akira committed
221
    else
222 223
	list->list.last = &list->node;
    zfree(node, sizeof *node);
Tanaka Akira's avatar
Tanaka Akira committed
224 225 226
    return dat;
}

227
/* Pop the top node off a linked list without freeing it. */
Tanaka Akira's avatar
Tanaka Akira committed
228 229

/**/
230
mod_export void *
Tanaka Akira's avatar
Tanaka Akira committed
231 232 233 234 235
ugetnode(LinkList list)
{
    void *dat;
    LinkNode node;

236
    if (!(node = firstnode(list)))
Tanaka Akira's avatar
Tanaka Akira committed
237 238
	return NULL;
    dat = node->dat;
239
    list->list.first = node->next;
Tanaka Akira's avatar
Tanaka Akira committed
240
    if (node->next)
241
	node->next->prev = &list->node;
Tanaka Akira's avatar
Tanaka Akira committed
242
    else
243
	list->list.last = &list->node;
Tanaka Akira's avatar
Tanaka Akira committed
244 245 246 247 248 249
    return dat;
}

/* Remove a node from a linked list */

/**/
250
mod_export void *
Tanaka Akira's avatar
Tanaka Akira committed
251 252 253 254
remnode(LinkList list, LinkNode nd)
{
    void *dat;

255
    nd->prev->next = nd->next;
Tanaka Akira's avatar
Tanaka Akira committed
256
    if (nd->next)
257
	nd->next->prev = nd->prev;
Tanaka Akira's avatar
Tanaka Akira committed
258
    else
259
	list->list.last = nd->prev;
Tanaka Akira's avatar
Tanaka Akira committed
260
    dat = nd->dat;
261
    zfree(nd, sizeof *nd);
Tanaka Akira's avatar
Tanaka Akira committed
262 263 264 265 266 267 268

    return dat;
}

/* Remove a node from a linked list without freeing */

/**/
269
mod_export void *
Tanaka Akira's avatar
Tanaka Akira committed
270 271 272 273
uremnode(LinkList list, LinkNode nd)
{
    void *dat;

274
    nd->prev->next = nd->next;
Tanaka Akira's avatar
Tanaka Akira committed
275
    if (nd->next)
276
	nd->next->prev = nd->prev;
Tanaka Akira's avatar
Tanaka Akira committed
277
    else
278
	list->list.last = nd->prev;
Tanaka Akira's avatar
Tanaka Akira committed
279 280 281 282 283 284 285
    dat = nd->dat;
    return dat;
}

/* Free a linked list */

/**/
286
mod_export void
Tanaka Akira's avatar
Tanaka Akira committed
287 288 289 290
freelinklist(LinkList list, FreeFunc freefunc)
{
    LinkNode node, next;

291
    for (node = firstnode(list); node; node = next) {
Tanaka Akira's avatar
Tanaka Akira committed
292 293 294
	next = node->next;
	if (freefunc)
	    freefunc(node->dat);
295
	zfree(node, sizeof *node);
Tanaka Akira's avatar
Tanaka Akira committed
296
    }
297
    zfree(list, sizeof *list);
Tanaka Akira's avatar
Tanaka Akira committed
298 299 300 301 302
}

/* Count the number of nodes in a linked list */

/**/
303
mod_export int
Tanaka Akira's avatar
Tanaka Akira committed
304 305 306 307 308 309 310 311 312
countlinknodes(LinkList list)
{
    LinkNode nd;
    int ct = 0;

    for (nd = firstnode(list); nd; incnode(nd), ct++);
    return ct;
}

313 314
/* Make specified node first, moving preceding nodes to end */

Tanaka Akira's avatar
Tanaka Akira committed
315
/**/
316
mod_export void
Tanaka Akira's avatar
Tanaka Akira committed
317 318
rolllist(LinkList l, LinkNode nd)
{
319
    l->list.last->next = firstnode(l);
320
    l->list.first->prev = lastnode(l);
321
    l->list.first = nd;
322 323
    l->list.last = nd->prev;
    nd->prev = &l->node;
324
    l->list.last->next = 0;
Tanaka Akira's avatar
Tanaka Akira committed
325 326
}

327 328
/* Create linklist of specified size. node->dats are not initialized. */

329 330 331 332 333 334 335
/**/
mod_export LinkList
newsizedlist(int size)
{
    LinkList list;
    LinkNode node;

336
    list = (LinkList) zhalloc(sizeof *list + (size * sizeof *node));
337

338 339
    list->list.first = &list[1].node;
    for (node = firstnode(list); size; size--, node++) {
340
	node->prev = node - 1;
341 342
	node->next = node + 1;
    }
343
    list->list.last = node - 1;
344
    list->list.first->prev = &list->node;
345 346 347 348 349
    node[-1].next = NULL;

    return list;
}

350 351 352 353 354
/*
 * Return the node whose data is the pointer "dat", else NULL.
 * Can be used as a boolean test.
 */

355
/**/
356 357
mod_export LinkNode
linknodebydatum(LinkList list, void *dat)
358 359 360 361 362
{
    LinkNode node;

    for (node = firstnode(list); node; incnode(node))
	if (getdata(node) == dat)
363
	    return node;
364

365
    return NULL;
366 367
}

368 369 370 371
/*
 * Return the node whose data matches the string "dat", else NULL.
 */

372 373
/**/
mod_export LinkNode
374
linknodebystring(LinkList list, char *dat)
375 376 377 378
{
    LinkNode node;

    for (node = firstnode(list); node; incnode(node))
379
	if (!strcmp((char *)getdata(node), dat))
380 381 382 383
	    return node;

    return NULL;
}
384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430

/*
 * Convert a linked list whose data elements are strings to
 * an array.  Memory is off the heap and the elements of the
 * array are the same elements as the linked list data if copy is
 * 0, else copied onto the heap.
 */

/**/
mod_export char **
hlinklist2array(LinkList list, int copy)
{
    int l = countlinknodes(list);
    char **ret = (char **) zhalloc((l + 1) * sizeof(char *)), **p;
    LinkNode n;

    for (n = firstnode(list), p = ret; n; incnode(n), p++) {
	*p = (char *) getdata(n);
	if (copy)
	    *p = dupstring(*p);
    }
    *p = NULL;

    return ret;
}

/*
 * Convert a linked list whose data elements are strings to
 * an array.  The result is a permanently allocated, freearrayable
 * array.
 */

/**/
mod_export char **
zlinklist2array(LinkList list)
{
    int l = countlinknodes(list);
    char **ret = (char **) zalloc((l + 1) * sizeof(char *)), **p;
    LinkNode n;

    for (n = firstnode(list), p = ret; n; incnode(n), p++) {
	*p = ztrdup((char *) getdata(n));
    }
    *p = NULL;

    return ret;
}