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 /*
16 * grid.c
17 * Written by Emden R. Gansner
18 *
19 * Support for grid to speed up layout. On each pass, nodes are
20 * put into grid cells. Given a node, repulsion is only computed
21 * for nodes in one of that nodes 9 adjacent grids.
22 */
23
24 /* uses PRIVATE interface for NOTUSED */
25 #define FDP_PRIVATE 1
26
27 #include <fdp.h>
28 #include <grid.h>
29 #include <macros.h>
30
31 /* structure for maintaining a free list of cells */
32 typedef struct _block {
33 cell *mem; /* block of cells */
34 cell *cur; /* next available cell */
35 cell *endp; /* after last cell */
36 struct _block *next; /* next memory block */
37 } block_t;
38
39 /* newBlock:
40 * Create new block of size cells
41 */
newBlock(int size)42 static block_t *newBlock(int size)
43 {
44 block_t *newb;
45
46 newb = GNEW(block_t);
47 newb->next = 0;
48 newb->mem = N_GNEW(size, cell);
49 newb->endp = newb->mem + size;
50 newb->cur = newb->mem;
51
52 return newb;
53 }
54
55 /* freeBlock:
56 * Free malloc'ed memory and block.
57 * Recurse to next block
58 */
freeBlock(block_t * b)59 static void freeBlock(block_t * b)
60 {
61 if (b) {
62 block_t *next = b->next;
63 free(b->mem);
64 free(b);
65 freeBlock(next);
66 }
67 }
68
69 struct _grid {
70 Dt_t *data; /* cells indexed by (i,j) */
71 block_t *cellMem; /* list of memory blocks for cells */
72 block_t *cellCur; /* current block */
73 int listSize; /* memory of nodes */
74 node_list *listMem; /* list of memory for node items */
75 node_list *listCur; /* next node item */
76 };
77
78 /* getCell:
79 * Create a new cell using memory blocks.
80 */
getCell(Grid * g)81 static cell *getCell(Grid * g)
82 {
83 cell *cp;
84 block_t *bp = g->cellCur; /* current block */
85
86 if (bp->cur == bp->endp) { /* current block is full */
87 if (bp->next == 0) {
88 bp->next = newBlock(2 * (bp->endp - bp->mem));
89 }
90 bp = g->cellCur = bp->next;
91 bp->cur = bp->mem;
92 }
93 cp = bp->cur++;
94 return cp;
95 }
96
ijcmpf(Dt_t * d,gridpt * p1,gridpt * p2,Dtdisc_t * disc)97 static int ijcmpf(Dt_t * d, gridpt * p1, gridpt * p2, Dtdisc_t * disc)
98 {
99 int diff;
100
101 NOTUSED(d);
102 NOTUSED(disc);
103 if ((diff = (p1->i - p2->i)))
104 return diff;
105 else
106 return (p1->j - p2->j);
107 }
108
109 static Grid *_grid; /* hack because can't attach info. to Dt_t */
110
111 /* newCell:
112 * Allocate a new cell from free store and initialize its indices
113 * This is used by the grid discipline to create cells.
114 */
newCell(Dt_t * d,void * obj,Dtdisc_t * disc)115 static void *newCell(Dt_t * d, void *obj, Dtdisc_t * disc)
116 {
117 cell *cellp = (cell *) obj;
118 cell *newp;
119
120 NOTUSED(disc);
121 newp = getCell(_grid);
122 newp->p.i = cellp->p.i;
123 newp->p.j = cellp->p.j;
124 newp->nodes = 0;
125
126 return newp;
127 }
128
129 /* newNode:
130 * Allocate a new node item from free store.
131 * Set node value and hook into list.
132 * A grid assumes the memory allocated in adjustGrid
133 * will be enough more all nodes added.
134 */
newNode(Grid * g,Agnode_t * n,node_list * nxt)135 static node_list *newNode(Grid * g, Agnode_t * n, node_list * nxt)
136 {
137 node_list *newp;
138
139 newp = g->listCur++;
140 newp->node = n;
141 newp->next = nxt;
142
143 return newp;
144 }
145
146 static Dtdisc_t gridDisc = {
147 offsetof(cell, p),
148 sizeof(gridpt),
149 offsetof(cell, link),
150 (Dtmake_f) newCell,
151 NIL(Dtfree_f),
152 (Dtcompar_f) ijcmpf,
153 NIL(Dthash_f),
154 NIL(Dtmemory_f),
155 NIL(Dtevent_f)
156 };
157
158 /* mkGrid:
159 * Create grid data structure.
160 * cellHint provides rough idea of how many cells
161 * may be needed.
162 */
mkGrid(int cellHint)163 Grid *mkGrid(int cellHint)
164 {
165 Grid *g;
166
167 g = GNEW(Grid);
168 _grid = g; /* see comment above */
169 g->data = dtopen(&gridDisc, Dtoset);
170 g->listMem = 0;
171 g->listSize = 0;
172 g->cellMem = newBlock(cellHint);
173 return g;
174 }
175
176 /* adjustGrid:
177 * Set up node list for grid. Make sure the list
178 * can handle nnodes nodes.
179 * It is assumed no more than nnodes will be added
180 * to the grid.
181 */
adjustGrid(Grid * g,int nnodes)182 void adjustGrid(Grid * g, int nnodes)
183 {
184 int nsize;
185
186 if (nnodes > g->listSize) {
187 nsize = MAX(nnodes, 2 * (g->listSize));
188 if (g->listMem)
189 free(g->listMem);
190 g->listMem = N_GNEW(nsize, node_list);
191 g->listSize = nsize;
192 }
193 }
194
195 /* clearGrid:
196 * Reset grid. This clears the dictionary,
197 * and reuses available memory.
198 */
clearGrid(Grid * g)199 void clearGrid(Grid * g)
200 {
201 dtclear(g->data);
202 g->listCur = g->listMem;
203 g->cellCur = g->cellMem;
204 g->cellCur->cur = g->cellCur->mem;
205 }
206
207 /* delGrid:
208 * Close and free all grid resources.
209 */
delGrid(Grid * g)210 void delGrid(Grid * g)
211 {
212 dtclose(g->data);
213 freeBlock(g->cellMem);
214 free(g->listMem);
215 free(g);
216 }
217
218 /* addGrid:
219 * Add node n to cell (i,j) in grid g.
220 */
addGrid(Grid * g,int i,int j,Agnode_t * n)221 void addGrid(Grid * g, int i, int j, Agnode_t * n)
222 {
223 cell *cellp;
224 cell key;
225
226 key.p.i = i;
227 key.p.j = j;
228 cellp = dtinsert(g->data, &key);
229 cellp->nodes = newNode(g, n, cellp->nodes);
230 if (Verbose >= 3) {
231 fprintf(stderr, "grid(%d,%d): %s\n", i, j, agnameof(n));
232 }
233 }
234
235 typedef int (*walkfn_t) (Dt_t *, void *, void *);
236
237 /* walkGrid:
238 * Apply function walkf to each cell in the grid.
239 * The second argument to walkf is the cell; the
240 * third argument is the grid. (The first argument
241 * is the dictionary.) walkf must return 0.
242 */
walkGrid(Grid * g,int (* walkf)(Dt_t *,cell *,Grid *))243 void walkGrid(Grid * g, int (*walkf) (Dt_t *, cell *, Grid *))
244 {
245 dtwalk(g->data, (walkfn_t) walkf, g);
246 }
247
248 /* findGrid;
249 * Return the cell, if any, corresponding to
250 * indices i,j
251 */
findGrid(Grid * g,int i,int j)252 cell *findGrid(Grid * g, int i, int j)
253 {
254 cell key;
255
256 key.p.i = i;
257 key.p.j = j;
258 return ((cell *) dtsearch(g->data, &key));
259 }
260
261 /* gLength:
262 * Return the number of nodes in a cell.
263 */
gLength(cell * p)264 int gLength(cell * p)
265 {
266 int len = 0;
267 node_list *nodes = p->nodes;
268
269 while (nodes) {
270 len++;
271 nodes = nodes->next;
272 }
273 return len;
274 }
275