1 /* gEDA - GPL Electronic Design Automation
2 * libgeda - gEDA's library
3 * Copyright (C) 1998-2010 Ales Hvezda
4 * Copyright (C) 1998-2010 gEDA Contributors (see ChangeLog for details)
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20 #include <config.h>
21
22 #include <stdio.h>
23 #ifdef HAVE_STDLIB_H
24 #include <stdlib.h>
25 #endif
26 #include <ctype.h>
27 #include <math.h>
28
29 #include "libgeda_priv.h"
30
31 #ifdef HAVE_LIBDMALLOC
32 #include <dmalloc.h>
33 #endif
34
35 /*! \file s_tile.c
36 * \brief Splits a page into tiles
37 *
38 * With the <b>tiles</b> a page (st_page) is splitted into several smaller areas.
39 * The number of tiles is defined by <b>MAX_TILES_X</b> and <b>MAX_TILES_Y</b>.
40 *
41 * Each <b>TILE</b> (st_tile) can contain zero to many <b>OBJECTS</b>
42 * (st_object) and each OBJECT can be in one or more TILES.
43 *
44 * The usage of tiles makes it easier to find geometrical connections between
45 * the line objects (OBJ_NET, OBJ_PIN, OBJ_BUS).
46 *
47 * \image html s_tile_overview.png
48 * \image latex s_tile_overview.pdf "Tile overview" width=14cm
49 */
50
51 /*! \brief initialize the array of tiles
52 * \par Function Description
53 * This function splits the page size into tiles and initializes
54 * every tile.
55 * \param toplevel TOPLEVEL structure
56 * \param p_current The page that gets the tiles.
57 */
s_tile_init(TOPLEVEL * toplevel,PAGE * p_current)58 void s_tile_init(TOPLEVEL * toplevel, PAGE * p_current)
59 {
60 int i, j;
61 TILE *t_current;
62 int x_size = toplevel->init_right / MAX_TILES_X;
63 int y_size = toplevel->init_bottom / MAX_TILES_Y;
64 int x_sum = 0;
65 int y_sum = 0;
66
67 #if DEBUG
68 printf("X, Y: %d %d\n", x_size, y_size);
69 #endif
70
71 for (j = 0; j < MAX_TILES_Y; j++) {
72 for (i = 0; i < MAX_TILES_X; i++) {
73 t_current = &p_current->world_tiles[i][j];
74
75 t_current->objects = NULL;
76
77 t_current->left = x_sum;
78 t_current->right = x_sum + x_size;
79
80 t_current->top = y_sum;
81 t_current->bottom = y_sum + y_size;
82
83 x_sum = x_sum + x_size;
84 }
85 x_sum = 0;
86 y_sum = y_sum + y_size;
87 }
88
89 #if DEBUG
90 for (j = 0; j < MAX_TILES_Y; j++) {
91 for (i = 0; i < MAX_TILES_X; i++) {
92 t_current = &p_current->world_tiles[i][j];
93 printf("\n%d %d\n", i, j);
94 printf("----------------\n");
95 printf("left %d top %d\n", t_current->left, t_current->top);
96 printf("right %d bottom %d\n", t_current->right,
97 t_current->bottom);
98 }
99 }
100 #endif
101 }
102
103 /*! \brief add a line object to the tiles
104 * \par Function Description
105 * This function takes a single line object and adds it to
106 * every tile that is touched by the line.
107 * It also adds all tiles that are touched by the object to
108 * the objects tile list.
109 * \param toplevel The TOPLEVEL structure
110 * \param object The line OBJECT to add
111 */
s_tile_add_line_object(TOPLEVEL * toplevel,OBJECT * object)112 static void s_tile_add_line_object (TOPLEVEL *toplevel, OBJECT *object)
113 {
114 TILE *t_current;
115 PAGE *p_current;
116 GList *found;
117 int i, j;
118 int v, w;
119 double x1, y1, x2, y2;
120 double bottom;
121 double m, b;
122 double x_size, y_size;
123 double x, y;
124 int start, end;
125
126 #if DEBUG
127 printf("name: %s\n", object->name);
128 #endif
129
130 g_return_if_fail (object != NULL);
131 g_return_if_fail (object->line != NULL);
132
133 p_current = o_get_page (toplevel, object);
134
135 if (p_current == NULL) {
136 return;
137 }
138
139 x_size = (double) toplevel->init_right / (double) MAX_TILES_X;
140 y_size = (double) toplevel->init_bottom / (double) MAX_TILES_Y;
141
142 x1 = (int) (object->line->x[0] / x_size);
143 x2 = (int) (object->line->x[1] / x_size);
144 y1 = (int) (object->line->y[0] / y_size);
145 y2 = (int) (object->line->y[1] / y_size);
146
147 bottom = x2 - x1;
148
149 if (bottom != 0.0) {
150 m = (double) (y2 - y1) / bottom;
151 b = y1 - m * x1;
152
153 start = min((int) x1, (int) x2);
154 end = max((int) x1, (int) x2);
155 for (i = start; i <= end; i++) {
156 x = i;
157 y = m * x + b;
158 if (floor(y) != ceil(y)) {
159
160 v = (int) x;
161 w = (int) floor(y);
162 if (v < 0 || w < 0 || v > MAX_TILES_X-1 || w > MAX_TILES_Y-1) {
163 return;
164 }
165 /* g_assert(v < MAX_TILES_X && w < MAX_TILES_Y && v >= 0 && w >= 0); */
166 t_current = &p_current->world_tiles[v][w];
167 found = g_list_find(t_current->objects, object);
168
169 if (!found) {
170 /*printf("%d %d\n", v, w);*/
171 t_current->objects = g_list_append(t_current->objects,
172 object);
173 object->tiles = g_list_append(object->tiles, t_current);
174 }
175
176 v = (int) x;
177 w = (int) ceil(y);
178 if (v < 0 || w < 0 || v > MAX_TILES_X-1 || w > MAX_TILES_Y-1) {
179 return;
180 }
181 /*g_assert(v < MAX_TILES_X && w < MAX_TILES_Y && v >= 0 && w >= 0);*/
182 t_current = &p_current->world_tiles[v][w];
183 found = g_list_find(t_current->objects, object);
184
185 if (!found) {
186 /*printf("%d %d\n", v, w);*/
187 t_current->objects = g_list_append(t_current->objects,
188 object);
189 object->tiles = g_list_append(object->tiles, t_current);
190 }
191
192 } else {
193 v = (int) x;
194 w = (int) floor(y);
195 if (v < 0 || w < 0 || v > MAX_TILES_X-1 || w > MAX_TILES_Y-1) {
196 return;
197 }
198 /*g_assert(v < MAX_TILES_X && w < MAX_TILES_Y && v >= 0 && w >= 0);*/
199 t_current = &p_current->world_tiles[v][w];
200 found = g_list_find(t_current->objects, object);
201
202 if (!found) {
203 /*printf("%d %d\n", v, w);*/
204 t_current->objects = g_list_append(t_current->objects,
205 object);
206 object->tiles = g_list_append(object->tiles, t_current);
207 }
208 }
209 }
210
211 if (m != 0.0) {
212 start = min((int) y1, (int) y2);
213 end = max((int) y1, (int) y2);
214 for (j = start; j <= end; j++) {
215 y = j;
216 x = (y - b) / m;
217 if (floor(x) != ceil(x)) {
218 w = (int) y;
219 v = (int) floor(x);
220 if (v < 0 || w < 0 || v > MAX_TILES_X-1 || w > MAX_TILES_Y-1) {
221 return;
222 }
223 /*g_assert(v < MAX_TILES_X && w < MAX_TILES_Y &&
224 v >= 0 && w >= 0);*/
225 t_current = &p_current->world_tiles[v][w];
226 found = g_list_find(t_current->objects, object);
227
228 if (!found) {
229 /*printf("%d %d\n", v, w);*/
230 t_current->objects =
231 g_list_append(t_current->objects, object);
232 object->tiles = g_list_append(object->tiles, t_current);
233 }
234
235 w = (int) y;
236 v = (int) ceil(x);
237 if (v < 0 || w < 0 || v > MAX_TILES_X-1 || w > MAX_TILES_Y-1) {
238 return;
239 }
240 /* g_assert(v < MAX_TILES_X && w < MAX_TILES_Y &&
241 v >= 0 && w >= 0);*/
242 t_current = &p_current->world_tiles[v][w];
243 found = g_list_find(t_current->objects, object);
244
245 if (!found) {
246 /*printf("%d %d\n", v, w);*/
247 t_current->objects =
248 g_list_append(t_current->objects, object);
249 object->tiles = g_list_append(object->tiles, t_current);
250 }
251
252 } else {
253 w = (int) y;
254 v = (int) floor(x);
255 if (v < 0 || w < 0 || v > MAX_TILES_X-1 || w > MAX_TILES_Y-1) {
256 return;
257 }
258 /*g_assert(v < MAX_TILES_X && w < MAX_TILES_Y &&
259 v >= 0 && w >= 0);*/
260 t_current = &p_current->world_tiles[v][w];
261 found = g_list_find(t_current->objects, object);
262
263 if (!found) {
264 /*printf("%d %d\n", v, w);*/
265 t_current->objects =
266 g_list_append(t_current->objects, object);
267 object->tiles = g_list_append(object->tiles, t_current);
268 }
269 }
270 }
271 }
272 } else {
273 start = min((int) y1, (int) y2);
274 end = max((int) y1, (int) y2);
275 for (j = start; j <= end; j++) {
276
277 y = j;
278 x = x1;
279 v = (int) x;
280 w = (int) y;
281 if (v < 0 || w < 0 || v > MAX_TILES_X-1 || w > MAX_TILES_Y-1) {
282 return;
283 }
284 /*g_assert(v < MAX_TILES_X && w < MAX_TILES_Y &&
285 v >= 0 && w >= 0);*/
286 t_current = &p_current->world_tiles[v][w];
287 found = g_list_find(t_current->objects, object);
288
289 if (!found) {
290 /*printf("%d %d\n", v, w);*/
291 t_current->objects = g_list_append(t_current->objects,
292 object);
293 object->tiles = g_list_append(object->tiles, t_current);
294 }
295
296 }
297 }
298 }
299
300 /*! \brief add an object to the tile ssytem
301 * \par Function Description
302 * This function takes dispatches the object to the correct
303 * function, depending on its type.
304 *
305 * \param toplevel The TOPLEVEL structure
306 * \param object The line OBJECT to add
307 */
s_tile_add_object(TOPLEVEL * toplevel,OBJECT * object)308 void s_tile_add_object (TOPLEVEL *toplevel, OBJECT *object)
309 {
310 GList *iter;
311
312 switch (object->type) {
313 case OBJ_NET:
314 case OBJ_PIN:
315 case OBJ_BUS:
316 s_tile_add_line_object (toplevel, object);
317 break;
318
319 case OBJ_COMPLEX:
320 case OBJ_PLACEHOLDER:
321 for (iter = object->complex->prim_objs;
322 iter != NULL;
323 iter = g_list_next (iter)) {
324 s_tile_add_object (toplevel, iter->data);
325 }
326 }
327 }
328
329 /*! \brief remove an object from the tiles
330 * \par Function Description
331 * This function remose an object from all tiles that are refered by the object.
332 * It also removes the object from each tile that contained the object.
333 * \param object The object to remove
334 */
s_tile_remove_object(OBJECT * object)335 void s_tile_remove_object(OBJECT *object)
336 {
337 GList *iter;
338 GList *tl_current;
339
340 /* Correctly deal with compound objects */
341 if (object->type == OBJ_COMPLEX || object->type == OBJ_PLACEHOLDER) {
342 for (iter = object->complex->prim_objs;
343 iter != NULL;
344 iter = g_list_next (iter)) {
345 s_tile_remove_object (iter->data);
346 }
347 }
348
349 for (tl_current = object->tiles;
350 tl_current != NULL;
351 tl_current = g_list_next (tl_current)) {
352 TILE *t_current = (TILE*)tl_current->data;
353
354 /* remove object from the list of objects for this tile */
355 t_current->objects = g_list_remove(t_current->objects, object);
356 }
357
358 /* reset the list of tiles for this object appears in */
359 g_list_free(object->tiles);
360 object->tiles = NULL;
361 }
362
363 /*! \brief update the tile informations of an object
364 * \par Function Description
365 * This function updates the tile informations of an object.
366 * This function can be used if an object has been moved on the page
367 * \param toplevel The TOPLEVEL structure
368 * \param object The OBJECT to update
369 */
s_tile_update_object(TOPLEVEL * toplevel,OBJECT * object)370 void s_tile_update_object(TOPLEVEL * toplevel, OBJECT * object)
371 {
372 s_tile_remove_object (object);
373 s_tile_add_object (toplevel, object);
374 }
375
376
377 /*! \brief get a list of object lists of all tiles inside a region
378 * \par Function Description
379 * This functions collects all object lists of the tiles that are touched
380 * by the given rectangle (x1,y1), (x2,y2).
381 * \note The caller has to g_list_free() the returned list.
382 */
s_tile_get_objectlists(TOPLEVEL * toplevel,PAGE * p_current,int world_x1,int world_y1,int world_x2,int world_y2)383 GList* s_tile_get_objectlists(TOPLEVEL *toplevel, PAGE *p_current,
384 int world_x1, int world_y1,
385 int world_x2, int world_y2)
386 {
387 TILE *t_current;
388 int x1, x2, y1, y2, x, y;
389 double x_size, y_size;
390 GList *objectlists = NULL;
391
392 x_size = (double) toplevel->init_right / (double) MAX_TILES_X;
393 y_size = (double) toplevel->init_bottom / (double) MAX_TILES_Y;
394
395 x1 = (int) (world_x1 / x_size);
396 x2 = (int) (world_x2 / x_size);
397 y1 = (int) (world_y1 / y_size);
398 y2 = (int) (world_y2 / y_size);
399
400 /* limit all tile ranges to [0, MAX_TILES-1]
401 (paranoid error checking) */
402 x1= max(x1, 0); x1 = min(x1, MAX_TILES_X-1);
403 x2= max(x2, 0); x2 = min(x2, MAX_TILES_X-1);
404 y1= max(y1, 0); y1 = min(y1, MAX_TILES_Y-1);
405 y2= max(y2, 0); y2 = min(y2, MAX_TILES_Y-1);
406
407 /* Check and correct the order of the coordinates */
408 if (x1 > x2) {
409 x = x1; x1 = x2; x2 = x;
410 }
411 if (y1 > y2) {
412 y = y1; y1 = y2; y2 = y;
413 }
414
415 /* finally, collect all object lists from the tiles */
416 for (x = x1; x <= x2; x++) {
417 for (y = y1; y <= y2; y++) {
418 t_current = &p_current->world_tiles[x][y];
419 objectlists = g_list_append(objectlists, t_current->objects);
420 }
421 }
422
423 return objectlists;
424 }
425
426
427 /*! \brief print all objects for each tile
428 * \par Function Description
429 * Debugging function to print all object names that are inside
430 * the tiles.
431 */
s_tile_print(TOPLEVEL * toplevel,PAGE * page)432 void s_tile_print(TOPLEVEL * toplevel, PAGE *page)
433 {
434 TILE *t_current;
435 GList *temp;
436 OBJECT *o_current;
437 int i, j;
438
439 for (j = 0; j < MAX_TILES_Y; j++) {
440 for (i = 0; i < MAX_TILES_X; i++) {
441 printf("\nTile %d %d\n", i, j);
442
443 t_current = &page->world_tiles[i][j];
444
445 temp = t_current->objects;
446 while (temp) {
447 o_current = (OBJECT *) temp->data;
448
449 printf("%s\n", o_current->name);
450
451 temp = g_list_next(temp);
452 }
453
454 printf("------------------\n");
455 }
456 }
457
458 }
459
460 /*! \brief free all object links from the tiles
461 * \par Function Description
462 * This function removes all objects from the tiles of the given \a page.
463 *
464 * \param [in] p_current The PAGE to clean up the tiles
465 * \note In theory, calling this function is not required. If all objects
466 * have been removed from a page, all object lists of the tiles should be empty.
467 */
s_tile_free_all(PAGE * p_current)468 void s_tile_free_all(PAGE * p_current)
469 {
470 int i, j;
471 TILE *t_current;
472
473 for (j = 0; j < MAX_TILES_Y; j++) {
474 for (i = 0; i < MAX_TILES_X; i++) {
475 t_current = &p_current->world_tiles[i][j];
476 if (g_list_length(t_current->objects) != 0) {
477 fprintf(stderr,
478 "OOPS! t_current->objects had something in it when it was freed!\n");
479 fprintf(stderr, "Length: %d\n", g_list_length(t_current->objects));
480 }
481 g_list_free(t_current->objects);
482 }
483 }
484 }
485
486
487
488