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
20typedef struct {
21 Dtlink_t link;
22 int deg;
23 Agnode_t *np; /* linked list of nodes of same degree */
24} degitem;
25
26static 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
35static void freeItem(Dt_t * d, degitem * obj, Dtdisc_t * disc)
36{
37 free(obj);
38}
39
40static 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
50static 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 */
65deglist_t *mkDeglist(void)
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 */
75void freeDeglist(deglist_t * s)
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 */
84void insertDeglist(deglist_t * ns, Agnode_t * n)
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 */
98void 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 */
129Agnode_t *firstDeglist(deglist_t * list)
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
146void 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
163