Branch data Line data Source code
1 : : /*
2 : : * nodelist.cpp - node list class implementation
3 : : *
4 : : * Copyright (C) 2003, 2004, 2006, 2008 Stefan Jahn <stefan@lkcc.org>
5 : : *
6 : : * This 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, or (at your option)
9 : : * any later version.
10 : : *
11 : : * This software 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 package; see the file COPYING. If not, write to
18 : : * the Free Software Foundation, Inc., 51 Franklin Street - Fifth Floor,
19 : : * Boston, MA 02110-1301, USA.
20 : : *
21 : : * $Id$
22 : : *
23 : : */
24 : :
25 : : #if HAVE_CONFIG_H
26 : : # include <config.h>
27 : : #endif
28 : :
29 : : #include <stdio.h>
30 : : #include <stdlib.h>
31 : : #include <string.h>
32 : : #include <assert.h>
33 : :
34 : : #include "logging.h"
35 : : #include "object.h"
36 : : #include "node.h"
37 : : #include "complex.h"
38 : : #include "circuit.h"
39 : : #include "net.h"
40 : : #include "nodelist.h"
41 : :
42 : : namespace qucs {
43 : :
44 : : // Constructor creates an instance of the nodelist class.
45 : 18 : nodelist::nodelist () {
46 : 18 : root = last = NULL;
47 : 18 : narray = NULL;
48 : 18 : txt = NULL;
49 : 18 : sorting = 0;
50 : 18 : }
51 : :
52 : : /* The function creates a nodelist for the given netlist. The
53 : : nodelist is based on the circuit list and consists of unique nodes
54 : : inside the circuit list only. Each node in the list has references
55 : : to their actual circuit nodes and thereby to the circuits it is
56 : : connected to. */
57 : 22682 : nodelist::nodelist (net * subnet) {
58 : 22682 : root = last = NULL;
59 : 22682 : narray = NULL;
60 : 22682 : txt = NULL;
61 : 22682 : sorting = 0;
62 : :
63 : : circuit * c;
64 : : // go through circuit list and find unique nodes
65 [ + + ][ # # ]: 141713 : for (c = subnet->getRoot (); c != NULL; c = (circuit *) c->getNext ()) {
66 [ + + ][ # # ]: 384309 : for (int i = 0; i < c->getSize (); i++) {
67 : 265278 : node * n = c->getNode (i);
68 [ + + # # ]: 265278 : if (contains (n->getName ()) == 0) {
69 : 116551 : add (n->getName (), n->getInternal ());
70 : : }
71 : : }
72 : : }
73 : : // add circuit nodes to each unique node in the list
74 [ + + ][ # # ]: 139233 : for (struct nodelist_t * n = getRoot (); n != NULL; n = n->next) {
75 [ + + ][ # # ]: 1051668 : for (c = subnet->getRoot (); c != NULL; c = (circuit *) c->getNext ()) {
76 [ + + ][ # # ]: 3220385 : for (int i = 0; i < c->getSize (); i++) {
77 [ - + ][ # # ]: 2285268 : assert (n->name != NULL);
78 [ - + ][ # # ]: 2285268 : assert (c->getNode(i)->getName () != NULL);
79 [ + + ][ # # ]: 2285268 : if (!strcmp (n->name, c->getNode(i)->getName ())) {
80 : 265278 : addCircuitNode (n, c->getNode (i));
81 : : }
82 : : }
83 : : }
84 : : }
85 : 22682 : }
86 : :
87 : : /* This copy constructor creates a instance of the nodelist class
88 : : based on the given nodelist. */
89 : 0 : nodelist::nodelist (const nodelist & o) {
90 : : struct nodelist_t * n;
91 : 0 : root = last = NULL;
92 : 0 : narray = NULL;
93 [ # # ][ # # ]: 0 : for (n = o.root; n != NULL; n = n->next) append (copy (n));
94 [ # # ][ # # ]: 0 : txt = o.txt ? strdup (o.txt) : NULL;
95 : 0 : sorting = o.sorting;
96 : 0 : }
97 : :
98 : : // Destructor deletes an instance of the nodelist class.
99 : 22700 : nodelist::~nodelist () {
100 : : struct nodelist_t * next;
101 [ + + ][ # # ]: 139251 : while (root) {
102 : 116551 : next = root->next;
103 : 116551 : release (root);
104 : 116551 : root = next;
105 : : }
106 [ - + ][ # # ]: 22700 : if (txt) free (txt);
107 [ + + ][ # # ]: 22700 : if (narray) free (narray);
108 : 22700 : }
109 : :
110 : : // The function copies the given node with all its properties.
111 : 0 : struct nodelist_t * nodelist::copy (struct nodelist_t * n) {
112 : 0 : struct nodelist_t * copy = create (n->name, n->internal);
113 : 0 : copy->n = n->n;
114 : 0 : copy->nNodes = n->nNodes;
115 : 0 : copy->nAlloc = n->nAlloc;
116 [ # # ]: 0 : if (copy->nAlloc) {
117 : 0 : copy->nodes = (node **) malloc (sizeof (node *) * n->nAlloc);
118 [ # # ]: 0 : if (copy->nNodes) {
119 : 0 : memcpy (copy->nodes, n->nodes, sizeof (node *) * n->nNodes);
120 : : }
121 : : }
122 : 0 : return copy;
123 : : }
124 : :
125 : : // This function adds a node name to the list and saves the internal flag.
126 : 116551 : void nodelist::add (char * str, int intern) {
127 : 116551 : add (create (str, intern));
128 : 116551 : }
129 : :
130 : : // The function creates a node based upon the given arguments.
131 : 256980 : struct nodelist_t * nodelist::create (char * str, int intern) {
132 : : struct nodelist_t * n;
133 : 256980 : n = (struct nodelist_t *) calloc (sizeof (struct nodelist_t), 1);
134 : 256980 : n->internal = intern;
135 [ + - ]: 256980 : n->name = str ? strdup (str) : NULL;
136 : 256980 : return n;
137 : : }
138 : :
139 : : // This function adds a node to the list.
140 : 116988 : void nodelist::add (struct nodelist_t * n) {
141 : 116988 : n->next = root;
142 [ + + ]: 116988 : if (root == NULL) last = n;
143 : 116988 : root = n;
144 : 116988 : }
145 : :
146 : : // This function appends a node name to the list.
147 : 0 : void nodelist::append (char * str, int intern) {
148 : 0 : append (create (str, intern));
149 : 0 : }
150 : :
151 : : // This function appends the given node to the list.
152 : 0 : void nodelist::append (struct nodelist_t * n) {
153 : 0 : n->next = NULL;
154 [ # # ]: 0 : if (root)
155 : 0 : last->next = n;
156 : : else
157 : 0 : root = n;
158 : 0 : last = n;
159 : 0 : }
160 : :
161 : : // This function removes the node with the given name from the list.
162 : 0 : void nodelist::remove (char * name) {
163 : 0 : remove (getNode (name));
164 : 0 : }
165 : :
166 : : // The function removes the given node from the list.
167 : 937488 : void nodelist::remove (struct nodelist_t * del, int keep) {
168 : : struct nodelist_t * prev, * n;
169 : : // go through the list
170 [ + - ]: 4317970 : for (prev = NULL, n = root; n != NULL; prev = n, n = n->next) {
171 [ + + ]: 4317970 : if (n == del) {
172 : : // adjust the chain properly
173 [ + + ]: 937488 : if (prev == NULL)
174 : 287400 : root = n->next;
175 : : else
176 : 650088 : prev->next = n->next;
177 [ + + ]: 937488 : if (n == last) last = prev;
178 : : // delete node if requested and return
179 [ + + ]: 937488 : if (!keep) release (n);
180 : 937488 : return;
181 : : }
182 : : }
183 : : }
184 : :
185 : : // This function free()'s the given node.
186 : 256980 : void nodelist::release (struct nodelist_t * n) {
187 [ + - ]: 256980 : if (n->name) free (n->name);
188 [ + + ]: 256980 : if (n->nodes) free (n->nodes);
189 : 256980 : free (n);
190 : 256980 : }
191 : :
192 : : // This function counts the node names in the list.
193 : 6767250 : int nodelist::length (void) {
194 : 6767250 : int res = 0;
195 [ + + ]: 46631270 : for (struct nodelist_t * n = root; n != NULL; n = n->next) res++;
196 : 6767250 : return res;
197 : : }
198 : :
199 : : // This function finds the specified node name in the list.
200 : 872149 : int nodelist::contains (char * str) {
201 : 872149 : int res = 0;
202 [ + + ]: 11888310 : for (struct nodelist_t * n = root; n != NULL; n = n->next) {
203 [ + - ][ + - ]: 11016161 : if (n->name != NULL && str != NULL && !strcmp (n->name, str))
[ + + ]
204 : 615169 : res++;
205 : : }
206 : 872149 : return res;
207 : : }
208 : :
209 : : // Returns the node number of the given node name.
210 : 5460 : int nodelist::getNodeNr (char * str) {
211 [ + - ]: 19110 : for (struct nodelist_t * n = root; n != NULL; n = n->next) {
212 [ + - ][ + - ]: 19110 : if (n->name != NULL && str != NULL && !strcmp (n->name, str))
[ + + ]
213 : 5460 : return n->n;
214 : : }
215 : 5460 : return -1;
216 : : }
217 : :
218 : : /* This function returns the node name positioned at the specified
219 : : location in the node name list. */
220 : 335347 : char * nodelist::get (int nr) {
221 : 335347 : return narray[nr + 1]->name;
222 : : }
223 : :
224 : : /* This function returns non-zero if the node positioned at the
225 : : specified location in the node name list is marked internal and
226 : : zero otherwise. */
227 : 383814 : int nodelist::isInternal (int nr) {
228 : 383814 : return narray[nr + 1]->internal;
229 : : }
230 : :
231 : : /* The function returns the nodelist structure at the specified
232 : : location in the node name list. */
233 : 61016309 : struct nodelist_t * nodelist::getNode (int nr) {
234 : 61016309 : return narray[nr + 1];
235 : : }
236 : :
237 : : /* The function returns the nodelist structure with the given name in
238 : : the node name list. It returns NULL if there is no such node. */
239 : 1073315 : struct nodelist_t * nodelist::getNode (char * name) {
240 [ + - ]: 5661593 : for (struct nodelist_t * n = root; n != NULL; n = n->next)
241 [ + + ]: 5661593 : if (!strcmp (name, n->name)) return n;
242 : 1073315 : return NULL;
243 : : }
244 : :
245 : : /* Returns a comma separated list of the circuits connected to the
246 : : node specified by the given number. */
247 : 0 : char * nodelist::getNodeString (int nr) {
248 [ # # ]: 0 : if (txt) free (txt); txt = NULL;
249 : : // find the specified node
250 : 0 : struct nodelist_t * n = getNode (nr);
251 : : // append circuit names connected to the node
252 : 0 : int len = (n->nNodes - 1) + 1;
253 : 0 : txt = (char *) malloc (len); txt[0] = '\0';
254 [ # # ]: 0 : for (int i = 0; i < n->nNodes; i++) {
255 : 0 : char * str = n->nodes[i]->getCircuit()->getName ();
256 : 0 : len += strlen (str);
257 : 0 : txt = (char *) realloc (txt, len);
258 : 0 : strcat (txt, str);
259 [ # # ]: 0 : if (i != n->nNodes - 1) strcat (txt, ",");
260 : : }
261 : 0 : return txt;
262 : : }
263 : :
264 : : /* The function returns the nodelist structure at the end of the node
265 : : name list. */
266 : 18 : struct nodelist_t * nodelist::getLastNode (void) {
267 : 18 : return last;
268 : : }
269 : :
270 : : // This function enumerates the nodes in the node name list.
271 : 22664 : void nodelist::assignNodes (void) {
272 : 22664 : int i = 1;
273 : :
274 : : // create fast array access possibility
275 [ - + ]: 22664 : if (narray) free (narray);
276 : : narray = (struct nodelist_t **)
277 : 22664 : malloc (sizeof (struct nodelist_t *) * length ());
278 : :
279 [ + + ]: 138778 : for (struct nodelist_t * n = root; n != NULL; n = n->next) {
280 : : // ground node gets a zero counter
281 [ + + ]: 116114 : if (!strcmp (n->name, "gnd")) {
282 : 22664 : n->n = 0;
283 : 22664 : narray[0] = n;
284 : : }
285 : : // others get a unique number greater than zero
286 : : else {
287 : 93450 : narray[i] = n;
288 : 93450 : n->n = i++;
289 : : }
290 : : }
291 : 22664 : }
292 : :
293 : : /* The function appends a node pointer to the given nodelist
294 : : structure. */
295 : 872149 : void nodelist::addCircuitNode (struct nodelist_t * nl, node * n) {
296 [ + + ]: 872149 : if (nl->nNodes >= nl->nAlloc) { // ensure capacity
297 [ + + ]: 303744 : if (nl->nAlloc == 0) {
298 : 256980 : nl->nAlloc = 2;
299 : 256980 : nl->nodes = (node **) malloc (sizeof (node *) * nl->nAlloc);
300 : : }
301 : : else {
302 : 46764 : nl->nAlloc *= 2;
303 : 46764 : nl->nodes = (node **) realloc (nl->nodes, sizeof (node *) * nl->nAlloc);
304 : : }
305 : : }
306 : 872149 : nl->nodes[nl->nNodes++] = n;
307 [ + + ]: 872149 : if (n->getInternal ()) nl->internal = n->getInternal ();
308 : 872149 : }
309 : :
310 : : /* This function deletes the given node from the nodelist
311 : : structure. */
312 : 606871 : void nodelist::delCircuitNode (struct nodelist_t * nl, node * n) {
313 [ - + ]: 606871 : assert (nl->nNodes > 0);
314 [ + + ]: 606871 : if (nl->nNodes > 1) {
315 : : int i, j;
316 : : // copy nodelist except the given one
317 [ + + ]: 944791 : for (j = i = 0; j < nl->nNodes - 1; i++, j++) {
318 [ + + ]: 478349 : if (nl->nodes[i] == n) i++;
319 : 478349 : nl->nodes[j] = nl->nodes[i];
320 : : }
321 : : }
322 : : else {
323 : : // no more nodes in the list
324 : 140429 : free (nl->nodes);
325 : 140429 : nl->nodes = NULL;
326 : 140429 : nl->nAlloc = 0;
327 : : }
328 : 606871 : nl->nNodes--;
329 : 606871 : }
330 : :
331 : : /* This function is used as sorting criteria for the S-parameter
332 : : analysis. It returns the number of nodes a join of the two
333 : : circuits connected to the given node would yield. */
334 : 7960158 : static int sortfunc (struct nodelist_t * n) {
335 : : int p;
336 : 7960158 : circuit * c1 = n->nodes[0]->getCircuit ();
337 [ + + ]: 7960158 : circuit * c2 = n->nNodes > 1 ? n->nodes[1]->getCircuit () : NULL;
338 [ + + ][ + + ]: 7960158 : if (c1->getPort () || (c2 && c2->getPort ())) return -1;
[ + + ][ + + ]
339 [ + + ]: 7763029 : if (c1 == c2) { // interconnect
340 : 42170 : p = c1->getSize () - 2;
341 : : } else { // connect
342 [ + + ]: 7720859 : p = c1->getSize () + (c2 ? c2->getSize () - 2 : 0);
343 : : }
344 : 7960158 : return p;
345 : : }
346 : :
347 : : /* The function evaluates the sorting criteria of the given two nodes.
348 : : It returns non-zero if 'n1' should be inserted before 'n2'. */
349 : 3510791 : static int insfunc (struct nodelist_t * n1, struct nodelist_t * n2) {
350 : 3510791 : int p1 = sortfunc (n1);
351 : 3510791 : int p2 = sortfunc (n2);
352 [ + - ][ + + ]: 3510791 : return p1 >= 0 && (p1 <= p2 || p2 < 0);
[ + + ]
353 : : }
354 : :
355 : : /* The function inserts the given node structure into the node list.
356 : : If the nodelist is sorted then the node gets inserted at a certain
357 : : position. */
358 : 937051 : void nodelist::insert (struct nodelist_t * n) {
359 : : // first node at all
360 [ - + ]: 937051 : if (root == NULL) {
361 : 0 : last = root = n;
362 : 0 : return;
363 : : }
364 : :
365 : : // sorted node list
366 [ + - ]: 937051 : if (sorting) {
367 : 937051 : int added = 0;
368 : : struct nodelist_t * nl, * prev;
369 [ + - ]: 3510791 : for (prev = NULL, nl = root; nl != NULL; prev = nl, nl = nl->next) {
370 [ + + ]: 3510791 : if (insfunc (n, nl)) {
371 [ + + ]: 937051 : if (prev == NULL) {
372 : 458047 : n->next = root;
373 : 458047 : root = n;
374 : : } else {
375 : 479004 : n->next = nl;
376 : 479004 : prev->next = n;
377 : : }
378 : 937051 : added++;
379 : 937051 : break;
380 : : }
381 : : }
382 [ - + ]: 937051 : if (!added) append (n);
383 : 937051 : return;
384 : : }
385 : :
386 : : // unsorted node list
387 : 937051 : add (n);
388 : : }
389 : :
390 : : /* This function removes the nodes associated with the given circuit
391 : : from the node list. If the node list is sorted then the order gets
392 : : rearranged properly. */
393 : 242129 : void nodelist::remove (circuit * c) {
394 : : // go through each node of the circuit
395 [ + + ]: 849000 : for (int i = 0; i < c->getSize (); i++) {
396 : 606871 : node * n = c->getNode (i);
397 : : struct nodelist_t * nl;
398 [ + - ]: 606871 : if ((nl = getNode (n->getName ())) != NULL) {
399 : : // remove node from node structure
400 : 606871 : delCircuitNode (nl, n);
401 [ + + ]: 606871 : if (nl->nNodes <= 0) {
402 : : // completely remove the node structure
403 : 140429 : remove (nl);
404 : : }
405 [ + - ][ + + ]: 466442 : else if (sorting && sortfunc (nl) > 0) {
[ + + ]
406 : : // rearrange sorting
407 : 398311 : remove (nl, 1);
408 : 398311 : insert (nl);
409 : : }
410 : : }
411 : : }
412 : 242129 : }
413 : :
414 : : /* The following function can be used to insert a new circuit to the
415 : : node list. It goes through each node of the circuit and rearranges
416 : : the node list appropriately. */
417 : 242129 : void nodelist::insert (circuit * c) {
418 : : // go through each node of the circuit
419 [ + + ]: 849000 : for (int i = 0; i < c->getSize (); i++) {
420 : : struct nodelist_t * nl;
421 : 606871 : node * n = c->getNode (i);
422 : : // is this node already in the nodelist?
423 [ + + ]: 606871 : if (contains (n->getName ()) == 0) {
424 : : // no, create new node and put it into the list
425 : 140429 : nl = create (n->getName (), n->getInternal ());
426 : 140429 : addCircuitNode (nl, n);
427 [ + - ]: 140429 : if (sorting) {
428 [ - + ]: 140429 : if (c->getPort ())
429 : 0 : append (nl);
430 : : else
431 : 140429 : insert (nl);
432 : : }
433 : 0 : else add (nl);
434 : : }
435 : : else {
436 : : // yes, put additional node into nodelist structure
437 [ + - ]: 466442 : if ((nl = getNode (n->getName ())) != NULL) {
438 : 466442 : addCircuitNode (nl, n);
439 [ + - ][ + + ]: 466442 : if (sorting && sortfunc (nl) > 0) {
[ + + ]
440 : : // rearrange sorting
441 : 398311 : remove (nl, 1);
442 : 398311 : insert (nl);
443 : : }
444 : : }
445 : : }
446 : : }
447 : 242129 : }
448 : :
449 : : /* The function completely rebuilds the nodelist. Once sort()'ed it
450 : : keeps being sorted when removing or inserting new circuits. */
451 : 18 : void nodelist::sort (void) {
452 : 18 : nodelist * nodes = new nodelist ();
453 : : struct nodelist_t * nl, * cand;
454 : 18 : int p, i, ports, MaxPorts, len = length ();
455 : :
456 : : // go through the list until there is no node left
457 [ + + ]: 455 : for (i = 0; i < len; i++) {
458 : : // find last order node
459 : 437 : cand = NULL;
460 [ + + ]: 6071 : for (MaxPorts = -1, p = 0, nl = root; nl != NULL; nl = nl->next) {
461 : 5692 : ports = sortfunc (nl);
462 [ + + ][ + + ]: 5692 : if (ports > MaxPorts || MaxPorts < 0 || ports == -1) {
[ + + ]
463 : 769 : cand = nl;
464 : 769 : MaxPorts = ports;
465 : : }
466 [ + + ]: 5692 : if (ports == -1) break;
467 : : }
468 : : // add last order node
469 : 437 : remove (cand, 1);
470 : 437 : nodes->add (cand);
471 : : }
472 : :
473 : : // store sorted node list in current object
474 : 18 : root = nodes->getRoot ();
475 : 18 : last = nodes->getLastNode ();
476 : 18 : nodes->root = NULL;
477 : 18 : sorting = 1;
478 : :
479 : : // delete temporary node list
480 [ + - ]: 18 : delete nodes;
481 : 18 : }
482 : :
483 : : // The function returns the first two nodes of the sorted list.
484 : 124675 : void nodelist::sortedNodes (node ** node1, node ** node2) {
485 [ - + ]: 124675 : assert (root->nNodes == 2);
486 : 124675 : *node1 = root->nodes[0];
487 : 124675 : *node2 = root->nodes[1];
488 : 124675 : }
489 : :
490 : : #if DEBUG
491 : : // Debug function: Prints the entire nodelist.
492 : 0 : void nodelist::print (void) {
493 [ # # ]: 0 : for (struct nodelist_t * n = root; n != NULL; n = n->next) {
494 : 0 : logprint (LOG_STATUS, "DEBUG: node %s-%d [", n->name, n->n);
495 [ # # ]: 0 : for (int i = 0; i < n->nNodes; i++) {
496 : 0 : logprint (LOG_STATUS, "%s", n->nodes[i]->getCircuit()->getName ());
497 [ # # ]: 0 : if (i != n->nNodes - 1) logprint (LOG_STATUS, ",");
498 : : }
499 : 0 : logprint (LOG_STATUS, "]\n");
500 : : }
501 : 0 : }
502 : : #endif /* DEBUG */
503 : :
504 : : } // namespace qucs
|
