1 /* Lepton EDA library
2 * Copyright (C) 1998-2010 Ales Hvezda
3 * Copyright (C) 1998-2015 gEDA Contributors
4 * Copyright (C) 2017-2021 Lepton EDA Contributors
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 #include <ctype.h>
24 #ifdef HAVE_STDLIB_H
25 #include <stdlib.h>
26 #endif
27
28 #include "liblepton_priv.h"
29
30 /*! \file s_conn.c
31 * \brief The connection system
32 *
33 * The connection system stores and tracks the connections between
34 * connected <b>OBJECTS</b>. The connected OBJECTS are either
35 * <b>pins</b>, <b>nets</b> and <b>busses</b>.
36 *
37 * Each connection object with the type <b>st_conn</b> represents a
38 * single unidirectional relation to another object.
39 *
40 * The following figure with two nets and a pin shows the relations
41 * between connections and OBJECTS:
42 *
43 * \image html s_conn_overview.png
44 * \image latex s_conn_overview.pdf "Connection overview" width=14cm
45 */
46
47
48 /*! \brief create a new connection object
49 * \par Function Description
50 * create a single st_conn object and initialize it with the
51 * given parameters.
52 *
53 * \return The new connection object
54 */
55 LeptonConn*
s_conn_return_new(LeptonObject * other_object,int type,int x,int y,int whichone,int other_whichone)56 s_conn_return_new (LeptonObject *other_object,
57 int type,
58 int x,
59 int y,
60 int whichone,
61 int other_whichone)
62 {
63 LeptonConn *new_conn;
64
65 new_conn = (LeptonConn *) g_malloc(sizeof(LeptonConn));
66
67 #if DEBUG
68 printf("** creating: %s %d %d\n", other_object->name, x, y);
69 #endif
70
71 new_conn->other_object = other_object;
72 new_conn->type = type;
73 new_conn->x = x;
74 new_conn->y = y;
75 new_conn->whichone = whichone;
76 new_conn->other_whichone = other_whichone;
77
78 return (new_conn);
79 }
80
81 /*! \brief check if a connection is uniq in a list
82 * \par Function Description
83 * This function checks if there's no identical connection
84 * in the list of connections.
85 * \param conn_list list of connection objects
86 * \param input_conn single connection object.
87 * \return TRUE if the LeptonConn structure is unique, FALSE otherwise.
88 */
89 int
s_conn_uniq(GList * conn_list,LeptonConn * input_conn)90 s_conn_uniq (GList * conn_list,
91 LeptonConn * input_conn)
92 {
93 GList *c_current;
94 LeptonConn *conn;
95
96 c_current = conn_list;
97 while (c_current != NULL) {
98 conn = (LeptonConn *) c_current->data;
99
100 if (conn->other_object == input_conn->other_object &&
101 conn->x == input_conn->x && conn->y == input_conn->y &&
102 conn->type == input_conn->type) {
103 return (FALSE);
104 }
105
106 c_current = g_list_next(c_current);
107 }
108
109 return (TRUE);
110 }
111
112 /*! \brief remove a object from the connection list of another object
113 * \par Function Description
114 * This function removes the LeptonObject <b>to_remove</b> from the connection
115 * list of the LeptonObject <b>other_object</b>.
116 *
117 * \param other_object LeptonObject from that the to_remove LeptonObject needs to be removed
118 * \param to_remove LeptonObject to remove
119 * \return TRUE if a connection has been deleted, FALSE otherwise
120 */
121 int
s_conn_remove_other(LeptonObject * other_object,LeptonObject * to_remove)122 s_conn_remove_other (LeptonObject *other_object,
123 LeptonObject *to_remove)
124 {
125 GList *c_current = NULL;
126 LeptonConn *conn = NULL;
127
128 lepton_object_emit_pre_change_notify (other_object);
129
130 c_current = other_object->conn_list;
131 while (c_current != NULL) {
132 conn = (LeptonConn *) c_current->data;
133
134 if (conn->other_object == to_remove) {
135 other_object->conn_list =
136 g_list_remove(other_object->conn_list, conn);
137
138 #if DEBUG
139 printf("Found other_object in remove_other\n");
140 printf("Freeing other: %s %d %d\n", conn->other_object->name,
141 conn->x, conn->y);
142 #endif
143
144 /* Do not write modify c_current like this, since this will cause */
145 /* very nasty data corruption and upset glib's memory slice */
146 /* allocator. */
147 /* c_current->data = NULL; Do not comment in */
148
149 g_free(conn);
150
151 #if 0 /* this does not work right */
152 if (lepton_object_is_bus (other_object) &&
153 other_object->conn_list == NULL) {
154 other_object->bus_ripper_direction = 0;
155 }
156 #endif
157
158 return (TRUE);
159 }
160
161 c_current = g_list_next(c_current);
162 }
163
164 lepton_object_emit_change_notify (other_object);
165
166 return (FALSE);
167 }
168
169 /*! \brief remove an LeptonObject from the connection system
170 * \par Function Description
171 * This function removes all connections from and to the LeptonObject
172 * <b>to_remove</b>.
173 *
174 * \param to_remove LeptonObject to unconnected from all other objects
175 */
176 void
s_conn_remove_object_connections(LeptonObject * to_remove)177 s_conn_remove_object_connections (LeptonObject *to_remove)
178 {
179 GList *c_iter;
180 LeptonConn *conn;
181 GList *iter;
182 LeptonObject *o_current;
183
184 switch (lepton_object_get_type (to_remove)) {
185 case OBJ_PIN:
186 case OBJ_NET:
187 case OBJ_BUS:
188 for (c_iter = to_remove->conn_list;
189 c_iter != NULL;
190 c_iter = g_list_next (c_iter)) {
191 conn = (LeptonConn *) c_iter->data;
192
193 /* keep calling this till it returns false (all refs removed) */
194 /* there is NO body to this while loop */
195 while (s_conn_remove_other (conn->other_object, to_remove));
196
197 c_iter->data = NULL;
198 g_free (conn);
199 }
200
201 g_list_free (to_remove->conn_list);
202 to_remove->conn_list = NULL;
203 break;
204
205 case OBJ_COMPONENT:
206 for (iter = lepton_component_object_get_contents (to_remove);
207 iter != NULL;
208 iter = g_list_next (iter))
209 {
210 o_current = (LeptonObject*) iter->data;
211 s_conn_remove_object_connections (o_current);
212 }
213 break;
214 }
215 }
216
217 /*! \brief Checks if a point is a midpoint of an LeptonObject
218 * \par Function Description
219 * Checks if the point (<b>x</b>,<b>y</b>) is on the LeptonObject
220 * and between it's endpoints.
221 * \return TRUE if the point is a midpoint of the LeptonObject. FALSE
222 * if the point is not a midpoinit or if the LeptonObject is not a
223 * NET a PIN or a BUS or if the LeptonObject
224 * has neither horizontal nor vertical orientation.
225 */
s_conn_check_midpoint(LeptonObject * o_current,int x,int y)226 LeptonObject *s_conn_check_midpoint(LeptonObject *o_current, int x, int y)
227 {
228 int min_x, min_y, max_x, max_y;
229
230 switch (lepton_object_get_type (o_current)) {
231 case(OBJ_NET):
232 case(OBJ_PIN):
233 case(OBJ_BUS):
234 min_y = MIN(o_current->line->y[0],
235 o_current->line->y[1]);
236 max_y = MAX(o_current->line->y[0],
237 o_current->line->y[1]);
238
239 /* vertical */
240 if ( (o_current->line->x[0] == x) &&
241 (y > min_y) && (y < max_y) &&
242 (o_current->line->x[0] ==
243 o_current->line->x[1]) ) {
244 #if DEBUG
245 printf("Found vertical point\n");
246 #endif
247 return(o_current);
248 }
249
250 min_x = MIN(o_current->line->x[0],
251 o_current->line->x[1]);
252 max_x = MAX(o_current->line->x[0],
253 o_current->line->x[1]);
254
255 /* horizontal */
256 if ( (o_current->line->y[0] == y) &&
257 (x > min_x) && (x < max_x) &&
258 (o_current->line->y[0] ==
259 o_current->line->y[1]) ) {
260 #if DEBUG
261 printf("Found horizontal point\n");
262 #endif
263 return(o_current);
264 }
265
266 break;
267 }
268 return(NULL);
269 }
270
271 /*! \brief adds a GList of LeptonObjects to the connection system
272 *
273 * \par Function Description
274 * This function adds all connections from and to the OBJECTS
275 * of the given GList.
276 *
277 * \param page The LeptonPage structure
278 * \param obj_list GList of LeptonObjects to add into the connection system
279 */
s_conn_update_glist(LeptonPage * page,GList * obj_list)280 void s_conn_update_glist (LeptonPage* page,
281 GList *obj_list)
282 {
283 LeptonObject *o_current;
284 GList *iter;
285
286 for (iter = obj_list; iter != NULL; iter = g_list_next (iter)) {
287 o_current = (LeptonObject*) iter->data;
288 s_conn_update_object (page, o_current);
289 }
290 }
291
292
293 /*! \brief Checks if an object is bus, or a bus pin
294 *
295 * \par Function Description
296 * Checks if an object is a bus or a bus pin
297 *
298 * \param object The LeptonObject to test
299 * \return TRUE if the objects is a bis, or bus pin
300 */
is_bus_related(LeptonObject * object)301 static int is_bus_related (LeptonObject *object)
302 {
303 return (lepton_object_is_bus (object) ||
304 (lepton_object_is_pin (object) && object->pin_type == PIN_TYPE_BUS));
305 }
306
307
308 /*! \brief Checks if two objects are of compatible types to be connected
309 *
310 * \par Function Description
311 * Checks if two objects are legal to be connected together
312 *
313 * \param object1 First LeptonObject
314 * \param object2 Second LeptonObject
315 * \return TRUE if the objects are compatible, FALSE if not
316 */
check_direct_compat(LeptonObject * object1,LeptonObject * object2)317 static int check_direct_compat (LeptonObject *object1, LeptonObject *object2)
318 {
319 return (is_bus_related (object1) == is_bus_related (object2));
320 }
321
322
add_connection(LeptonObject * object,LeptonObject * other_object,int type,int x,int y,int whichone,int other_whichone)323 static void add_connection (LeptonObject *object, LeptonObject *other_object,
324 int type, int x, int y,
325 int whichone, int other_whichone)
326 {
327 /* Describe the connection */
328 LeptonConn *new_conn =
329 s_conn_return_new (other_object, type, x, y, whichone, other_whichone);
330 /* Do uniqness check */
331 if (s_conn_uniq (object->conn_list, new_conn)) {
332 object->conn_list = g_list_append (object->conn_list, new_conn);
333 } else {
334 g_free (new_conn);
335 }
336 }
337
338 /*! \brief add a line LeptonObject to the connection system
339 * \par Function Description
340 * This function searches for all geometrical connections of the
341 * LeptonObject <b>object</b> to all other connectable
342 * objects. It adds connections to the object and from all other
343 * objects to this one.
344 * \param page The LeptonPage structure
345 * \param object LeptonObject to add into the connection system
346 */
347 static void
s_conn_update_line_object(LeptonPage * page,LeptonObject * object)348 s_conn_update_line_object (LeptonPage* page,
349 LeptonObject *object)
350 {
351 GList *object_list;
352 LeptonObject *other_object;
353 LeptonObject *found;
354 int j, k;
355 LeptonObject *component, *other_component;
356
357 component = lepton_object_get_parent (object);
358
359 /* loop over all connectible objects */
360 for (object_list = page->connectible_list;
361 object_list != NULL;
362 object_list = g_list_next (object_list)) {
363 other_object = (LeptonObject*) object_list->data;
364
365 if (object == other_object)
366 continue;
367
368 other_component = lepton_object_get_parent (other_object);
369
370 /* An object inside a symbol can only be connected up to another
371 * object if they are (a) both inside the same object, or (b)
372 * the object inside a symbol is a pin. */
373
374 /* 1. Both objects are inside a symbol */
375 if (component && other_component) {
376 /* If inside different symbols, both must be pins to connect. */
377 if (component != other_component
378 && (!lepton_object_is_pin (object) ||
379 !lepton_object_is_pin (other_object))) {
380 continue;
381 }
382
383 /* 2. Updating object is inside a symbol, but other object is not. */
384 }
385 else if (component && !other_component)
386 {
387 if (!lepton_object_is_pin (object)) continue;
388 /* 3. Updating object not inside symbol, but other object is. */
389 }
390 else if (!component && other_component)
391 {
392 if (!lepton_object_is_pin (other_object)) continue;
393 }
394
395 /* Here is where you check the end points */
396 /* Check both end points of the other object */
397 for (k = 0; k < 2; k++) {
398
399 /* If the other object is a pin, only check the correct end */
400 if (lepton_object_is_pin (other_object) &&
401 other_object->whichend != k)
402 continue;
403
404 /* Check both end points of the object */
405 for (j = 0; j < 2; j++) {
406
407 /* If the object is a pin, only check the correct end */
408 if (lepton_object_is_pin (object) &&
409 object->whichend != j)
410 continue;
411
412 /* Check for coincidence and compatibility between
413 the objects being tested. */
414 if (object->line->x[j] == other_object->line->x[k] &&
415 object->line->y[j] == other_object->line->y[k] &&
416 check_direct_compat (object, other_object)) {
417
418 lepton_object_emit_pre_change_notify (other_object);
419
420 add_connection (object, other_object, CONN_ENDPOINT,
421 other_object->line->x[k],
422 other_object->line->y[k], j, k);
423
424 add_connection (other_object, object, CONN_ENDPOINT,
425 object->line->x[j],
426 object->line->y[j], k, j);
427
428 lepton_object_emit_change_notify (other_object);
429 }
430 }
431 }
432
433 /* Check both end points of the object against midpoints of the other */
434 for (k = 0; k < 2; k++) {
435
436 /* If the object is a pin, only check the correct end */
437 if (lepton_object_is_pin (object) &&
438 object->whichend != k)
439 continue;
440
441 /* check for midpoint of other object, k endpoint of current obj*/
442 found = s_conn_check_midpoint (other_object, object->line->x[k],
443 object->line->y[k]);
444
445 /* Pins are not allowed midpoint connections onto them. */
446 /* Allow nets to connect to the middle of buses. */
447 /* Allow compatible objects to connect. */
448 if (found && !lepton_object_is_pin (other_object) &&
449 ((lepton_object_is_net (object) &&
450 lepton_object_is_bus (other_object)) ||
451 check_direct_compat (object, other_object)))
452 {
453
454 add_connection (object, other_object, CONN_MIDPOINT,
455 object->line->x[k],
456 object->line->y[k], k, -1);
457
458 add_connection (other_object, object, CONN_MIDPOINT,
459 object->line->x[k],
460 object->line->y[k], -1, k);
461 }
462 }
463
464 /* Check both end points of the other object against midpoints of the first */
465 for (k = 0; k < 2; k++) {
466
467 /* If the other object is a pin, only check the correct end */
468 if (lepton_object_is_pin (other_object) &&
469 other_object->whichend != k)
470 continue;
471
472 /* do object's endpoints cross the middle of other_object? */
473 /* check for midpoint of other object, k endpoint of current obj*/
474 found = s_conn_check_midpoint (object, other_object->line->x[k],
475 other_object->line->y[k]);
476
477 /* Pins are not allowed midpoint connections onto them. */
478 /* Allow nets to connect to the middle of buses. */
479 /* Allow compatible objects to connect. */
480 if (found && !lepton_object_is_pin (object) &&
481 ((lepton_object_is_bus (object) &&
482 lepton_object_is_net (other_object)) ||
483 check_direct_compat (object, other_object))) {
484
485 add_connection (object, other_object, CONN_MIDPOINT,
486 other_object->line->x[k],
487 other_object->line->y[k], -1, k);
488
489 add_connection (other_object, object, CONN_MIDPOINT,
490 other_object->line->x[k],
491 other_object->line->y[k], k, -1);
492 }
493 }
494 }
495
496 #if DEBUG
497 s_conn_print(object->conn_list);
498 #endif
499 }
500
501 /*! \brief add an LeptonObject to the connection system
502 *
503 * \par Function Description
504 * This function searches for all geometrical connections of the
505 * LeptonObject <b>object</b> to all other connectable
506 * objects. It adds connections to the object and from all other
507 * objects to this one.
508 *
509 * \param page The LeptonPage structure
510 * \param object LeptonObject to add into the connection system
511 */
512 void
s_conn_update_object(LeptonPage * page,LeptonObject * object)513 s_conn_update_object (LeptonPage* page,
514 LeptonObject *object)
515 {
516 GList *primitives = NULL;
517
518 /* Add object to the list of connectible objects */
519 s_conn_add_object (page, object);
520
521 switch (lepton_object_get_type (object)) {
522 case OBJ_PIN:
523 case OBJ_NET:
524 case OBJ_BUS:
525 s_conn_update_line_object (page, object);
526 break;
527
528 case OBJ_COMPONENT:
529 primitives = lepton_component_object_get_contents (object);
530 s_conn_update_glist (page, primitives);
531 break;
532 }
533 }
534
535 /*! \brief print all connections of a connection list
536 * \par Function Description
537 * This is a debugging function to print a List of connections.
538 * \param conn_list GList of connection objects
539 */
s_conn_print(GList * conn_list)540 void s_conn_print(GList * conn_list)
541 {
542 LeptonConn *conn;
543 GList *cl_current;
544
545 printf("\nStarting s_conn_print\n");
546 cl_current = conn_list;
547 while (cl_current != NULL) {
548
549 conn = (LeptonConn *) cl_current->data;
550 printf("-----------------------------------\n");
551 printf("other object: %s\n", conn->other_object->name);
552 printf("type: %d\n", conn->type);
553 printf("x: %d y: %d\n", conn->x, conn->y);
554 printf("whichone: %d\n", conn->whichone);
555 printf("other_whichone: %d\n", conn->other_whichone);
556 printf("-----------------------------------\n");
557
558 cl_current = g_list_next(cl_current);
559 }
560
561 }
562
563 /*! \brief Search for net in existing connections.
564 * \par Function Description
565 * This method searches the connection list for the first matching
566 * connection with the given x, y, and whichone endpoint.
567 *
568 * \param [in] new_net Net LeptonObject to compare to.
569 * \param [in] whichone The connection number to check.
570 * \param [in] conn_list List of existing connections to compare
571 * <B>new_net</B> to.
572 * \return TRUE if a matching connection is found, FALSE otherwise.
573 */
s_conn_net_search(LeptonObject * new_net,int whichone,GList * conn_list)574 int s_conn_net_search(LeptonObject* new_net, int whichone, GList * conn_list)
575 {
576 LeptonConn *conn;
577 GList *cl_current;
578
579 cl_current = conn_list;
580 while (cl_current != NULL) {
581
582 conn = (LeptonConn *) cl_current->data;
583 if (conn != NULL && conn->whichone == whichone &&
584 conn->x == new_net->line->x[whichone] &&
585 conn->y == new_net->line->y[whichone])
586 {
587 return TRUE;
588 }
589
590 cl_current = g_list_next(cl_current);
591 }
592
593 return FALSE;
594 }
595
596 /*! \brief get a list of all objects connected to a list of LeptonObjects.
597 *
598 * \par Function Description
599 * This function gets all other_object from the connection
600 * list of the LeptonObjects in the pased list.
601 *
602 * \param [in] input_list GList of LeptonObject's or NULL
603 * \param [in] obj_list The GList of LeptonObject to get connections from
604 * \return A GList of objects
605 *
606 * \warning
607 * Caller must g_list_free returned GList pointer.
608 * Do not free individual data items in list.
609 */
s_conn_return_glist_others(GList * input_list,GList * obj_list)610 static GList *s_conn_return_glist_others (GList *input_list, GList *obj_list)
611 {
612 GList *return_list;
613 GList *iter;
614 LeptonObject *o_current;
615
616 return_list = input_list;
617
618 for (iter = obj_list; iter != NULL; iter = g_list_next (iter)) {
619 o_current = (LeptonObject*) iter->data;
620 return_list = s_conn_return_others (return_list, o_current);
621 }
622
623 return return_list;
624 }
625
626 /*! \brief get a list of all objects connected to this one
627 *
628 * \par Function Description
629 * This function gets all other_object from the connection list of the current object.
630 * Component objects are entered, and their prim_objs processed. If an <b>input_list</b>
631 * is given, the other objects are appended to that list.
632 *
633 * \param [in] input_list GList of LeptonObject's
634 * \param [in] object LeptonObject to get other LeptonObjects from
635 * \return A GList of LeptonObjects
636 *
637 * \warning
638 * Caller must g_list_free returned GList pointer.
639 * Do not free individual data items in list.
640 */
s_conn_return_others(GList * input_list,LeptonObject * object)641 GList *s_conn_return_others(GList *input_list, LeptonObject *object)
642 {
643 GList *c_iter;
644 GList *return_list;
645 GList *primitives;
646
647 return_list = input_list;
648
649 switch (lepton_object_get_type (object)) {
650 case OBJ_PIN:
651 case OBJ_NET:
652 case OBJ_BUS:
653 for (c_iter = object->conn_list;
654 c_iter != NULL; c_iter = g_list_next (c_iter)) {
655 LeptonConn *conn = (LeptonConn *) c_iter->data;
656
657 if (conn->other_object && conn->other_object != object) {
658 return_list = g_list_append(return_list, conn->other_object);
659 }
660 }
661 break;
662
663 case OBJ_COMPONENT:
664 primitives = lepton_component_object_get_contents (object);
665 return_list = s_conn_return_glist_others (return_list, primitives);
666 break;
667 }
668
669 return return_list;
670 }
671
672 /*! \brief add a line object to the list of connectible objects
673 * \par Function Description
674 * \param page The LeptonPage structure
675 * \param object The line LeptonObject to add
676 */
677 static void
s_conn_add_line_object(LeptonPage * page,LeptonObject * object)678 s_conn_add_line_object (LeptonPage *page,
679 LeptonObject *object)
680 {
681 g_return_if_fail (object != NULL);
682 g_return_if_fail (object->line != NULL);
683
684 #if DEBUG
685 printf ("name: %s\n", object->name);
686 #endif
687
688 if (page == NULL) {
689 return;
690 }
691
692 if (!g_list_find (page->connectible_list, object)) {
693 page->connectible_list = g_list_append (page->connectible_list, object);
694 }
695 }
696
697 /*! \brief add an object to the list of connectible objects
698 * \par Function Description
699 * This function takes dispatches the object to the correct
700 * function, depending on its type.
701 *
702 * \param page The LeptonPage structure
703 * \param object The line LeptonObject to add
704 */
705 void
s_conn_add_object(LeptonPage * page,LeptonObject * object)706 s_conn_add_object (LeptonPage *page,
707 LeptonObject *object)
708 {
709 GList *iter;
710
711 switch (lepton_object_get_type (object)) {
712 case OBJ_NET:
713 case OBJ_PIN:
714 case OBJ_BUS:
715 s_conn_add_line_object (page, object);
716 break;
717
718 case OBJ_COMPONENT:
719 for (iter = lepton_component_object_get_contents (object);
720 iter != NULL;
721 iter = g_list_next (iter)) {
722 s_conn_add_object (page, (LeptonObject*) iter->data);
723 }
724 }
725 }
726
727 /*! \brief remove an object from the list of connectible objects
728 * \par Function Description
729 * \param object The object to remove
730 */
731 void
s_conn_remove_object(LeptonPage * page,LeptonObject * object)732 s_conn_remove_object (LeptonPage* page,
733 LeptonObject *object)
734 {
735 GList *iter;
736
737 if (page == NULL) {
738 return;
739 }
740
741 /* Correctly deal with compound objects */
742 if (lepton_object_is_component (object))
743 {
744 for (iter = lepton_component_object_get_contents (object);
745 iter != NULL;
746 iter = g_list_next (iter)) {
747 s_conn_remove_object (page, (LeptonObject*) iter->data);
748 }
749 }
750
751 page->connectible_list = g_list_remove (page->connectible_list, object);
752 }
753