Graphviz  2.41.20170921.2350
grid.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 /*
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  */
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  */
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  */
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 
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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  */
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 }
cell * cur
Definition: grid.c:34
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
#define MAX(a, b)
Definition: agerror.c:17
CDT_API int dtclose(Dt_t *)
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
Agnode_t * node
Definition: grid.h:29
CDT_API Dtmethod_t * Dtoset
Definition: cdt.h:166
gridpt p
Definition: grid.h:38
int j
Definition: grid.h:34
#define NOTUSED(var)
Definition: cghdr.h:54
Definition: cdt.h:80
struct block block_t
Definition: block.h:23
struct _block * next
Definition: grid.c:36
int(* walkfn_t)(Dt_t *, void *, void *)
Definition: grid.c:235
block_t * cellMem
Definition: grid.c:71
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition: dtopen.c:9
cell * endp
Definition: grid.c:35
node_list * nodes
Definition: grid.h:39
struct _node_list * next
Definition: grid.h:30
#define NIL(t)
Definition: dthdr.h:13
int
Definition: grammar.c:1264
#define dtsearch(d, o)
Definition: cdt.h:260
cell * mem
Definition: grid.c:33
Definition: grid.c:69
CGRAPH_API char * agnameof(void *)
Definition: id.c:143
void addGrid(Grid *g, int i, int j, Agnode_t *n)
Definition: grid.c:221
Definition: grid.h:37
Grid * mkGrid(int cellHint)
Definition: grid.c:163
int listSize
Definition: grid.c:73
void *(* Dtmemory_f)(Dt_t *, void *, size_t, Dtdisc_t *)
Definition: cdt.h:36
int i
Definition: grid.h:34
Definition: block.h:30
void walkGrid(Grid *g, int(*walkf)(Dt_t *, cell *, Grid *))
Definition: grid.c:243
void adjustGrid(Grid *g, int nnodes)
Definition: grid.c:182
void delGrid(Grid *g)
Definition: grid.c:210
#define dtinsert(d, o)
Definition: cdt.h:262
node_list * listCur
Definition: grid.c:75
#define GNEW(t)
Definition: memory.h:37
block_t * next
Definition: block.h:32
CDT_API int dtwalk(Dt_t *, int(*)(Dt_t *, void *, void *), void *)
EXTERN unsigned char Verbose
Definition: globals.h:64
node_list * listMem
Definition: grid.c:74
#define dtclear(d)
Definition: cdt.h:267
cell * findGrid(Grid *g, int i, int j)
Definition: grid.c:252
void freeBlock(block_t *sp)
Definition: block.c:51
Definition: grid.c:32
void clearGrid(Grid *g)
Definition: grid.c:199
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
Dt_t * data
Definition: grid.c:70
Definition: cdt.h:99
Definition: grid.h:33
int gLength(cell *p)
Definition: grid.c:264
#define N_GNEW(n, t)
Definition: agxbuf.c:20
block_t * cellCur
Definition: grid.c:72