1/* $Id$ $Revision$ */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14
15#include "nodelist.h"
16#include "circular.h"
17#include <assert.h>
18
19static nodelistitem_t *init_nodelistitem(Agnode_t * n)
20{
21 nodelistitem_t *p = NEW(nodelistitem_t);
22 p->curr = n;
23 return p;
24}
25
26nodelist_t *mkNodelist()
27{
28 nodelist_t *list = NEW(nodelist_t);
29 return list;
30}
31
32void freeNodelist(nodelist_t * list)
33{
34 nodelistitem_t *temp;
35 nodelistitem_t *next;
36
37 if (!list)
38 return;
39
40 for (temp = list->first; temp; temp = next) {
41 next = temp->next;
42 free(temp);
43 }
44 free(list);
45}
46
47/* appendNodelist:
48 * Add node after one.
49 * If one == NULL, add n to end.
50 */
51void appendNodelist(nodelist_t * list, nodelistitem_t * one, Agnode_t * n)
52{
53 nodelistitem_t *np = init_nodelistitem(n);
54
55 list->sz++;
56 if (!one)
57 one = list->last;
58 if (one == list->last) {
59 if (one)
60 one->next = np;
61 else
62 list->first = np;
63 np->prev = one;
64 np->next = NULL;
65 list->last = np;
66 } else {
67 nodelistitem_t *temp = one->next;
68 one->next = np;
69 np->prev = one;
70 temp->prev = np;
71 np->next = temp;
72 }
73}
74
75#ifdef OLD
76/* addNodelist:
77 * Adds node to end of list if not already present.
78 */
79void addNodelist(nodelist_t * list, Agnode_t * n)
80{
81 nodelistitem_t *temp;
82 nodelistitem_t *item = 0;
83
84 for (temp = list->first; temp; temp = temp->next) {
85 if (n == temp->curr) {
86 item = temp;
87 break;
88 }
89 }
90
91 if (item)
92 return;
93
94 item = init_nodelistitem(n);
95 if (list->last) {
96 list->last->next = item;
97 item->prev = list->last;
98 } else
99 list->first = item;
100 list->last = item;
101 list->sz++;
102}
103
104void removeNodelist(nodelist_t * list, Agnode_t * n)
105{
106 nodelistitem_t *temp;
107
108 for (temp = list->first; temp; temp = temp->next) {
109 if (n == temp->curr) {
110 list->sz--;
111 if (temp->prev == NULL) { /* the first node */
112 list->first = temp->next;
113 } else {
114 temp->prev->next = temp->next;
115 }
116 if (temp == list->last) { /* the last node */
117 list->last = temp->prev;
118 } else {
119 temp->next->prev = temp->prev;
120 }
121 free(temp);
122 return;
123 }
124 }
125}
126#endif
127
128/* reverseNodelist;
129 * Destructively reverse a list.
130 */
131nodelist_t *reverseNodelist(nodelist_t * list)
132{
133 nodelistitem_t *temp;
134 nodelistitem_t *p;
135
136 for (p = list->first; p; p = p->prev) {
137 temp = p->next;
138 p->next = p->prev;
139 p->prev = temp;
140 }
141 temp = list->last;
142 list->last = list->first;
143 list->first = temp;
144 return list;
145}
146
147/* realignNodelist:
148 * Make np new front of list, with current last hooked to
149 * current first. I.e., make list circular, then cut between
150 * np and np->prev.
151 */
152void realignNodelist(nodelist_t * list, nodelistitem_t * np)
153{
154 nodelistitem_t *temp;
155 nodelistitem_t *prev;
156
157 if (np == list->first)
158 return;
159
160 temp = list->first;
161 prev = np->prev;
162
163 list->first = np;
164 np->prev = NULL;
165 list->last->next = temp;
166 temp->prev = list->last;
167 list->last = prev;
168 prev->next = NULL;
169}
170
171/* cloneNodelist:
172 * Create a copy of list.
173 */
174nodelist_t *cloneNodelist(nodelist_t * list)
175{
176 nodelist_t *newlist = mkNodelist();
177 nodelistitem_t *temp;
178 nodelistitem_t *prev = 0;
179
180 for (temp = list->first; temp; temp = temp->next) {
181 appendNodelist(newlist, prev, temp->curr);
182 prev = newlist->last;
183 }
184 return newlist;
185}
186
187/* insertNodelist:
188 * Remove cn. Then, insert cn before neighbor if pos == 0 and
189 * after neighbor otherwise.
190 */
191void
192insertNodelist(nodelist_t * list, Agnode_t * cn, Agnode_t * neighbor,
193 int pos)
194{
195 nodelistitem_t *temp;
196 nodelistitem_t *prev;
197 nodelistitem_t *next;
198 nodelistitem_t *actual = 0;
199
200 for (temp = list->first; temp; temp = temp->next) {
201 if (temp->curr == cn) {
202 actual = temp;
203 prev = actual->prev;
204 next = actual->next;
205 if (prev) /* not first */
206 prev->next = next;
207 else
208 list->first = next;
209
210 if (next) /* not last */
211 next->prev = prev;
212 else
213 list->last = prev;
214 break;
215 }
216 }
217 assert(actual);
218
219 prev = NULL;
220 for (temp = list->first; temp; temp = temp->next) {
221 if (temp->curr == neighbor) {
222 if (pos == 0) {
223 if (temp == list->first) {
224 list->first = actual;
225 actual->next = temp;
226 actual->prev = NULL;
227 temp->prev = actual;
228 return;
229 }
230 prev->next = actual;
231 actual->prev = prev;
232 actual->next = temp;
233 temp->prev = actual;
234 return;
235 } else {
236 if (temp == list->last) {
237 list->last = actual;
238 actual->next = NULL;
239 actual->prev = temp;
240 temp->next = actual;
241 return;
242 }
243 actual->prev = temp;
244 actual->next = temp->next;
245 temp->next->prev = actual;
246 temp->next = actual;
247 return;
248 }
249 break;
250 }
251 prev = temp;
252 }
253}
254
255int sizeNodelist(nodelist_t * list)
256{
257 return list->sz;
258#ifdef OLD
259 int i = 0;
260 nodelistitem_t *temp = NULL;
261
262 temp = list->first;
263 while (temp) {
264 i++;
265 temp = temp->next;
266 }
267 return i;
268#endif
269}
270
271#ifdef OLD
272/* node_exists:
273 * Return true if node is in list.
274 */
275int node_exists(nodelist_t * list, Agnode_t * n)
276{
277 nodelistitem_t *temp;
278
279 for (temp = list->first; temp; temp = temp->next) {
280 if (temp->curr == n) {
281 return 1;
282 }
283 }
284 return 0;
285}
286
287/* nodename_exists:
288 * Return true if node with given name is in list.
289 * Assumes n == np->name for some node np;
290 */
291int nodename_exists(nodelist_t * list, char *n)
292{
293 nodelistitem_t *temp;
294
295 temp = list->first;
296
297 for (temp = list->first; temp; temp = temp->next) {
298 if (temp->curr->name == n) {
299 return 1;
300 }
301 }
302 return 0;
303}
304#endif
305
306/* node_position:
307 * Returns index of node n in list, starting at 0.
308 * Returns -1 if not in list.
309 */
310int node_position(nodelist_t * list, Agnode_t * n)
311{
312 return POSITION(n);
313#ifdef OLD
314 nodelistitem_t *temp;
315 int i = 0;
316 char *name = agnameof(n);
317
318 for (temp = list->first; temp; temp = temp->next) {
319 if (streq(agnameof(temp->curr),name)) {
320 return i;
321 }
322 i++;
323 }
324 return -1;
325#endif
326}
327
328/* concatNodelist:
329 * attach l2 to l1.
330 */
331static void concatNodelist(nodelist_t * l1, nodelist_t * l2)
332{
333 if (l2->first) {
334 if (l2->first) {
335 l1->last->next = l2->first;
336 l2->first->prev = l1->last;
337 l1->last = l2->last;
338 l1->sz += l2->sz;
339 } else {
340 *l1 = *l2;
341 }
342 }
343}
344
345/* reverse_append;
346 * Create l1 @ (rev l2)
347 * Destroys and frees l2.
348 */
349void reverseAppend(nodelist_t * l1, nodelist_t * l2)
350{
351 l2 = reverseNodelist(l2);
352 concatNodelist(l1, l2);
353 free(l2);
354}
355
356#ifdef DEBUG
357void printNodelist(nodelist_t * list)
358{
359 nodelistitem_t *temp = NULL;
360
361 temp = list->first;
362 while (temp != NULL) {
363 fprintf(stderr, "%s ", agnameof(temp->curr));
364 temp = temp->next;
365 }
366 fputs("\n", stderr);
367}
368#endif
369