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 */
32typedef 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 */
42static 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 */
59static 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
69struct _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 */
81static 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
97static 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
109static 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 */
115static 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 */
135static 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
146static 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 */
163Grid *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 */
182void 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 */
199void 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 */
210void 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 */
221void 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
235typedef 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 */
243void 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 */
252cell *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 */
264int 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