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