Graphviz  2.41.20170921.2350
nodelist.c
Go to the documentation of this file.
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 
19 static nodelistitem_t *init_nodelistitem(Agnode_t * n)
20 {
22  p->curr = n;
23  return p;
24 }
25 
27 {
28  nodelist_t *list = NEW(nodelist_t);
29  return list;
30 }
31 
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  */
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  */
79 void 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 
104 void 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  */
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  */
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  */
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  */
191 void
192 insertNodelist(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 
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  */
275 int 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  */
291 int 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  */
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  */
331 static 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  */
350 {
351  l2 = reverseNodelist(l2);
352  concatNodelist(l1, l2);
353  free(l2);
354 }
355 
356 #ifdef DEBUG
357 void 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
Definition: utils.c:981
nodelistitem_t * last
Definition: nodelist.h:33
void insertNodelist(nodelist_t *list, Agnode_t *cn, Agnode_t *neighbor, int pos)
Definition: nodelist.c:192
#define assert(x)
Definition: cghdr.h:47
int sz
Definition: nodelist.h:34
void realignNodelist(nodelist_t *list, nodelistitem_t *np)
Definition: nodelist.c:152
nodelist_t * cloneNodelist(nodelist_t *list)
Definition: nodelist.c:174
nodelist_t * mkNodelist()
Definition: nodelist.c:26
nodelistitem_t * prev
Definition: nodelist.h:28
void reverseAppend(nodelist_t *l1, nodelist_t *l2)
Definition: nodelist.c:349
int sizeNodelist(nodelist_t *list)
Definition: nodelist.c:255
nodelistitem_t * first
Definition: nodelist.h:32
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
int node_position(nodelist_t *list, Agnode_t *n)
Definition: nodelist.c:310
void freeNodelist(nodelist_t *list)
Definition: nodelist.c:32
void appendNodelist(nodelist_t *list, nodelistitem_t *one, Agnode_t *n)
Definition: nodelist.c:51
node_t * curr
Definition: nodelist.h:26
#define NULL
Definition: logic.h:39
#define streq(s, t)
Definition: cghdr.h:52
struct item_s item
#define POSITION(n)
Definition: circular.h:100
nodelist_t * reverseNodelist(nodelist_t *list)
Definition: nodelist.c:131
#define NEW(t)
Definition: memory.h:35
nodelistitem_t * next
Definition: nodelist.h:27