Graphviz  2.41.20170921.2350
deglist.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 <deglist.h>
16 #include <circular.h>
17 #include <blockpath.h>
18 #include <assert.h>
19 
20 typedef struct {
22  int deg;
23  Agnode_t *np; /* linked list of nodes of same degree */
24 } degitem;
25 
26 static degitem *mkItem(Dt_t * d, degitem * obj, Dtdisc_t * disc)
27 {
28  degitem *ap = GNEW(degitem);
29 
30  ap->np = NULL;
31  ap->deg = obj->deg;
32  return ap;
33 }
34 
35 static void freeItem(Dt_t * d, degitem * obj, Dtdisc_t * disc)
36 {
37  free(obj);
38 }
39 
40 static int cmpDegree(Dt_t * d, int *key1, int *key2, Dtdisc_t * disc)
41 {
42  if (*key1 < *key2)
43  return -1;
44  else if (*key1 > *key2)
45  return 1;
46  else
47  return 0;
48 }
49 
50 static Dtdisc_t nodeDisc = {
51  offsetof(degitem, deg), /* key */
52  sizeof(int), /* size */
53  offsetof(degitem, link), /* link */
54  (Dtmake_f) mkItem,
55  (Dtfree_f) freeItem,
56  (Dtcompar_f) cmpDegree,
57  (Dthash_f) 0,
58  (Dtmemory_f) 0,
59  (Dtevent_f) 0
60 };
61 
62 /* mkDeglist:
63  * Create an empty list of nodes.
64  */
66 {
67  deglist_t *s = dtopen(&nodeDisc, Dtoset);
68  return s;
69 }
70 
71 /* freeDeglist:
72  * Delete the node list.
73  * Nodes are not deleted.
74  */
76 {
77  dtclose(s);
78 }
79 
80 /* insertDeglist:
81  * Add a node to the node list.
82  * Nodes are kept sorted by DEGREE, smallest degrees first.
83  */
85 {
86  degitem key;
87  degitem *kp;
88 
89  key.deg = DEGREE(n);
90  kp = dtinsert(ns, &key);
91  ND_next(n) = kp->np;
92  kp->np = n;
93 }
94 
95 /* removeDeglist:
96  * Remove n from list, if it is in the list.
97  */
98 void removeDeglist(deglist_t * list, Agnode_t * n)
99 {
100  degitem key;
101  degitem *ip;
102  Agnode_t *np;
103  Agnode_t *prev;
104 
105  key.deg = DEGREE(n);
106  ip = (degitem *) dtsearch(list, &key);
107  assert(ip);
108  if (ip->np == n) {
109  ip->np = ND_next(n);
110  if (ip->np == NULL)
111  dtdelete(list, ip);
112  } else {
113  prev = ip->np;
114  np = ND_next(prev);
115  while (np && (np != n)) {
116  prev = np;
117  np = ND_next(np);
118  }
119  if (np)
120  ND_next(prev) = ND_next(np);
121  }
122 }
123 
124 /* firstDeglist:
125  * Return the first node in the list (smallest degree)
126  * Remove from list.
127  * If the list is empty, return NULL
128  */
130 {
131  degitem *ip;
132  Agnode_t *np;
133 
134  ip = (degitem *) dtfirst(list);
135  if (ip) {
136  np = ip->np;
137  ip->np = ND_next(np);
138  if (ip->np == NULL)
139  dtdelete(list, ip);
140  return np;
141  } else
142  return 0;
143 }
144 
145 #ifdef DEBUG
146 void printDeglist(deglist_t * dl)
147 {
148  degitem *ip;
149  node_t *np;
150  fprintf(stderr, " dl:\n");
151  for (ip = (degitem *) dtfirst(dl); ip; ip = (degitem *) dtnext(dl, ip)) {
152  np = ip->np;
153  if (np)
154  fprintf(stderr, " (%d)", ip->deg);
155  for (; np; np = ND_next(np)) {
156  fprintf(stderr, " %s", agnameof(np));
157  }
158  fprintf(stderr, "\n");
159  }
160 
161 }
162 #endif
int(* Dtcompar_f)(Dt_t *, void *, void *, Dtdisc_t *)
Definition: cdt.h:40
unsigned int(* Dthash_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:41
CDT_API int dtclose(Dt_t *)
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
CDT_API Dtmethod_t * Dtoset
Definition: cdt.h:166
#define dtdelete(d, o)
Definition: cdt.h:264
#define assert(x)
Definition: cghdr.h:47
Agnode_t * firstDeglist(deglist_t *list)
Definition: deglist.c:129
Definition: cdt.h:80
#define dtfirst(d)
Definition: cdt.h:254
Agnode_t * np
Definition: deglist.c:23
void insertDeglist(deglist_t *ns, Agnode_t *n)
Definition: deglist.c:84
void freeDeglist(deglist_t *s)
Definition: deglist.c:75
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition: dtopen.c:9
int
Definition: grammar.c:1264
#define dtsearch(d, o)
Definition: cdt.h:260
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
#define dtnext(d, o)
Definition: cdt.h:255
void *(* Dtmemory_f)(Dt_t *, void *, size_t, Dtdisc_t *)
Definition: cdt.h:36
Definition: grammar.c:79
#define dtinsert(d, o)
Definition: cdt.h:262
#define DEGREE(n)
Definition: circular.h:125
#define NULL
Definition: logic.h:39
#define GNEW(t)
Definition: memory.h:37
#define ND_next(n)
Definition: types.h:517
int deg
Definition: deglist.c:22
int(* Dtevent_f)(Dt_t *, int, void *, Dtdisc_t *)
Definition: cdt.h:42
void(* Dtfree_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:39
Definition: cdt.h:99
Dtlink_t link
Definition: deglist.c:21
void removeDeglist(deglist_t *list, Agnode_t *n)
Definition: deglist.c:98
deglist_t * mkDeglist(void)
Definition: deglist.c:65