1 /*
2 * EFhier.c -
3 *
4 * Procedures for manipulating HierNames.
5 *
6 * *********************************************************************
7 * * Copyright (C) 1985, 1990 Regents of the University of California. *
8 * * Permission to use, copy, modify, and distribute this *
9 * * software and its documentation for any purpose and without *
10 * * fee is hereby granted, provided that the above copyright *
11 * * notice appear in all copies. The University of California *
12 * * makes no representations about the suitability of this *
13 * * software for any purpose. It is provided "as is" without *
14 * * express or implied warranty. Export of this software outside *
15 * * of the United States of America may require an export license. *
16 * *********************************************************************
17 */
18
19 #ifndef lint
20 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/extflat/EFname.c,v 1.2 2010/08/10 00:18:45 tim Exp $";
21 #endif /* not lint */
22
23 #include <stdio.h>
24 #include <string.h>
25 #include <math.h>
26
27 #include "tcltk/tclmagic.h"
28 #include "utils/magic.h"
29 #include "utils/geometry.h"
30 #include "utils/geofast.h"
31 #include "utils/hash.h"
32 #include "utils/malloc.h"
33 #include "utils/utils.h"
34 #include "extflat/extflat.h"
35 #include "extflat/EFint.h"
36
37 #ifdef MAGIC_WRAPPER
38 #define PrintErr TxError
39 #else
40 #define PrintErr printf
41 #endif
42
43 /*
44 * Hash table containing all flattened node names.
45 * The keys in this table are HierNames, processed by the
46 * procedures efHNCompare(), efHNHash(), efHierCopy(),
47 * and efHierKill().
48 */
49 HashTable efNodeHashTable;
50
51 /*
52 * Hash table used by efHNFromUse to ensure that it always returns
53 * a pointer to the SAME HierName structure each time it is called
54 * with the same fields.
55 */
56 HashTable efHNUseHashTable;
57
58 extern void EFHNFree();
59 extern void efHNInit();
60 extern void efHNRecord();
61
62
63 /*
64 * ----------------------------------------------------------------------------
65 *
66 * EFHNIsGlob --
67 *
68 * Determine whether a HierName is of the format of a global name,
69 * i.e, it ends in a '!'.
70 *
71 * The Tcl version of magic further refines this to include names
72 * which are defined in the global Tcl variable space. (7.3.94):
73 * also check if the array variable "globals" contains the name as
74 * a key entry.
75 *
76 * Updated 12/2021: Removed the check for Tcl variable names matching
77 * the net name. This seems like a bad idea all around. Left just the
78 * check for the array variable "globals". Otherwise use of VDD and GND
79 * variables cause nets named VDD and GND to become globals, which was
80 * not intended.
81 *
82 * Results:
83 * TRUE if the name is a global.
84 *
85 * Side effects:
86 * None.
87 *
88 * ----------------------------------------------------------------------------
89 */
90
91 bool
EFHNIsGlob(hierName)92 EFHNIsGlob(hierName)
93 HierName *hierName;
94 {
95 #ifdef MAGIC_WRAPPER
96 char *retstr;
97 retstr = (char *)Tcl_GetVar2(magicinterp, "globals", hierName->hn_name,
98 TCL_GLOBAL_ONLY);
99 if (retstr != NULL) return TRUE;
100
101 // retstr = (char *)Tcl_GetVar(magicinterp, hierName->hn_name, TCL_GLOBAL_ONLY);
102 // if (retstr != NULL) return TRUE;
103 #endif
104 return hierName->hn_name[strlen(hierName->hn_name) - 1] == '!';
105 }
106
107 /*
108 * ----------------------------------------------------------------------------
109 *
110 * EFHNIsGND --
111 *
112 * Determine whether a HierName is the same as the global signal GND.
113 *
114 * The Tcl version of magic expands this to include names which are
115 * equal to the global Tcl variable $GND, if it is set.
116 *
117 * This is only used in substrate backwards-compatibility mode, when the
118 * substrate is not specified in the technology file.
119 *
120 * Results:
121 * TRUE if the name is GND, false if not.
122 *
123 * Side effects:
124 * None.
125 *
126 * ----------------------------------------------------------------------------
127 */
128
129 bool
EFHNIsGND(hierName)130 EFHNIsGND(hierName)
131 HierName *hierName;
132 {
133 #ifdef MAGIC_WRAPPER
134 char *retstr;
135 #endif
136
137 if (hierName->hn_parent != (HierName *)NULL) return FALSE;
138
139 #ifdef MAGIC_WRAPPER
140 retstr = (char *)Tcl_GetVar(magicinterp, "GND", TCL_GLOBAL_ONLY);
141 if (retstr != NULL)
142 if (!strcmp(hierName->hn_name, retstr)) return TRUE;
143 #endif
144
145 return (strcmp(hierName->hn_name, "GND!") == 0);
146 }
147
148
149 /*
150 * ----------------------------------------------------------------------------
151 *
152 * EFHNConcat --
153 *
154 * Given a HierName prefix and a HierName suffix, make a newly allocated
155 * copy of the suffix that points to the prefix.
156 *
157 * Results:
158 * Pointer to the new HierName as described above.
159 *
160 * Side effects:
161 * May allocate memory.
162 *
163 * ----------------------------------------------------------------------------
164 */
165
166 HierName *
EFHNConcat(prefix,suffix)167 EFHNConcat(prefix, suffix)
168 HierName *prefix; /* Components of name on root side */
169 HierName *suffix; /* Components of name on leaf side */
170 {
171 HierName *new, *prev;
172 HierName *firstNew;
173 unsigned size;
174
175 for (firstNew = prev = (HierName *) NULL;
176 suffix;
177 prev = new, suffix = suffix->hn_parent)
178 {
179 size = HIERNAMESIZE(strlen(suffix->hn_name));
180 new = (HierName *) mallocMagic((unsigned)(size));
181 if (efHNStats) efHNRecord(size, HN_CONCAT);
182 new->hn_hash = suffix->hn_hash;
183 (void) strcpy(new->hn_name, suffix->hn_name);
184 if (prev)
185 prev->hn_parent = new;
186 else
187 firstNew = new;
188 }
189 prev->hn_parent = prefix;
190
191 return firstNew;
192 }
193
194 /*
195 * ----------------------------------------------------------------------------
196 *
197 * EFStrToHN --
198 *
199 * Given a hierarchical prefix (the HierName pointed to by prefix)
200 * and a name relative to that prefix (the string 'suffixStr'), return a
201 * pointer to the HierName we should use. Normally, this is just a newly
202 * built HierName containing the path components of 'suffixStr' appended to
203 * prefix.
204 *
205 * Results:
206 * Pointer to a name determined as described above.
207 *
208 * Side effects:
209 * May allocate new HierNames.
210 *
211 * ----------------------------------------------------------------------------
212 */
213
214 HierName *
EFStrToHN(prefix,suffixStr)215 EFStrToHN(prefix, suffixStr)
216 HierName *prefix; /* Components of name on side of root */
217 char *suffixStr; /* Leaf part of name (may have /'s) */
218 {
219 char *cp;
220 HashEntry *he;
221 char *slashPtr;
222 HierName *hierName;
223 unsigned size;
224 int len;
225
226 /* Skip to the end of the relative name */
227 slashPtr = NULL;
228 for (cp = suffixStr; *cp; cp++)
229 if (*cp == '/')
230 slashPtr = cp;
231
232 /*
233 * Convert the relative name into a HierName path, with one HierName
234 * created for each slash-separated segment of suffixStr.
235 */
236 cp = slashPtr = suffixStr;
237 for (;;)
238 {
239 if (*cp == '/' || *cp == '\0')
240 {
241 size = HIERNAMESIZE(cp - slashPtr);
242 hierName = (HierName *) mallocMagic((unsigned)(size));
243 if (efHNStats) efHNRecord(size, HN_ALLOC);
244 efHNInit(hierName, slashPtr, cp);
245 hierName->hn_parent = prefix;
246 if (*cp++ == '\0')
247 break;
248 slashPtr = cp;
249 prefix = hierName;
250 }
251 else cp++;
252 }
253
254 return hierName;
255 }
256
257 /*
258 * ----------------------------------------------------------------------------
259 *
260 * EFHNToStr --
261 *
262 * Convert a HierName chain into a printable name.
263 * Stores the result in a static buffer.
264 *
265 * Results:
266 * Returns a pointer to the static buffer containing the
267 * printable name.
268 *
269 * Side effects:
270 * Overwrites the previous contents of the static buffer.
271 *
272 * ----------------------------------------------------------------------------
273 */
274
275 char *
EFHNToStr(hierName)276 EFHNToStr(hierName)
277 HierName *hierName; /* Name to be converted */
278 {
279 static char namebuf[2048];
280
281 (void) efHNToStrFunc(hierName, namebuf);
282 return namebuf;
283 }
284
285 /*
286 * efHNToStrFunc --
287 *
288 * Recursive part of name conversion.
289 * Calls itself recursively on hierName->hn_parent and dstp,
290 * adding the prefix of the pathname to the string pointed to
291 * by dstp. Then stores hierName->hn_name at the end of the
292 * just-stored prefix, and returns a pointer to the end.
293 *
294 * Results:
295 * Returns a pointer to the null byte at the end of
296 * all the pathname components stored so far in dstp.
297 *
298 * Side effects:
299 * Stores characters in dstp.
300 */
301
302 char *
efHNToStrFunc(hierName,dstp)303 efHNToStrFunc(hierName, dstp)
304 HierName *hierName; /* Name to be converted */
305 char *dstp; /* Store name here */
306 {
307 char *srcp;
308
309 if (hierName == NULL)
310 {
311 *dstp = '\0';
312 return dstp;
313 }
314
315 if (hierName->hn_parent)
316 {
317 dstp = efHNToStrFunc(hierName->hn_parent, dstp);
318 *dstp++ = '/';
319 }
320
321 srcp = hierName->hn_name;
322 while (*dstp++ = *srcp++)
323 /* Nothing */;
324
325 return --dstp;
326 }
327
328 /*
329 * ----------------------------------------------------------------------------
330 *
331 * EFHNLook --
332 *
333 * Look for the entry in the efNodeHashTable whose name is formed
334 * by concatenating suffixStr to prefix. If there's not an
335 * entry in efNodeHashTable, or the entry has a NULL value, complain
336 * and return NULL; otherwise return the HashEntry.
337 *
338 * The string errorStr should say what we were processing, e.g,
339 * "fet", "connect(1)", "connect(2)", etc., for use in printing
340 * error messages. If errorStr is NULL, we don't print any error
341 * messages.
342 *
343 * Results:
344 * See above.
345 *
346 * Side effects:
347 * Allocates memory temporarily to build the key for HashLookOnly(),
348 * but then frees it before returning.
349 *
350 * ----------------------------------------------------------------------------
351 */
352
353 HashEntry *
EFHNLook(prefix,suffixStr,errorStr)354 EFHNLook(prefix, suffixStr, errorStr)
355 HierName *prefix; /* Components of name on root side */
356 char *suffixStr; /* Part of name on leaf side */
357 char *errorStr; /* Explanatory string for errors */
358 {
359 HierName *hierName, *hn;
360 bool dontFree = FALSE;
361 HashEntry *he;
362
363 if (suffixStr == NULL)
364 {
365 hierName = prefix;
366 dontFree = TRUE;
367 }
368 else hierName = EFStrToHN(prefix, suffixStr);
369
370 he = HashLookOnly(&efNodeHashTable, (char *) hierName);
371 if (he == NULL || HashGetValue(he) == NULL)
372 {
373 if (errorStr)
374 PrintErr("%s: no such node %s\n", errorStr, EFHNToStr(hierName));
375 he = NULL;
376 }
377
378 /*
379 * Free the portion of the HierName we just allocated for
380 * looking in the table, if we allocated one.
381 */
382 if (!dontFree)
383 EFHNFree(hierName, prefix, HN_ALLOC);
384
385 return he;
386 }
387
388 /*
389 * ----------------------------------------------------------------------------
390 *
391 * EFHNConcatLook --
392 *
393 * Like EFHNLook above, but the argument suffix is itself a HierName.
394 * We construct the full name by concatenating the hierarchical prefix
395 * and the node name 'suffix', then looking it up in the flat node
396 * table for its real name.
397 *
398 * Results:
399 * See EFHNLook()'s comments.
400 *
401 * Side effects:
402 * See EFHNLook()'s comments.
403 *
404 * ----------------------------------------------------------------------------
405 */
406
407 HashEntry *
EFHNConcatLook(prefix,suffix,errorStr)408 EFHNConcatLook(prefix, suffix, errorStr)
409 HierName *prefix; /* Components of name on root side */
410 HierName *suffix; /* Part of name on leaf side */
411 char *errorStr; /* Explanatory string for errors */
412 {
413 HashEntry *he;
414 HierName *hn;
415
416 /*
417 * Find the last component of the suffix, then temporarily
418 * link the HierNames for use as a hash key. This is safe
419 * because HashLookOnly() doesn't ever store anything in the
420 * hash table, so we don't have to worry about this temporarily
421 * built key somehow being saved without our knowledge.
422 */
423 hn = suffix;
424 while (hn->hn_parent)
425 hn = hn->hn_parent;
426 hn->hn_parent = prefix;
427
428 he = HashLookOnly(&efNodeHashTable, (char *) suffix);
429 if (he == NULL || HashGetValue(he) == NULL)
430 {
431 PrintErr("%s: no such node %s\n", errorStr, EFHNToStr(suffix));
432 he = (HashEntry *) NULL;
433 }
434
435 /* Undo the temp link */
436 hn->hn_parent = (HierName *) NULL;
437 return he;
438 }
439
440 /*
441 * ----------------------------------------------------------------------------
442 *
443 * EFHNFree --
444 *
445 * Free a list of HierNames, up to but not including the element pointed
446 * to by 'prefix' (or the NULL indicating the end of the HierName list).
447 *
448 * Results:
449 * None.
450 *
451 * Side effects:
452 * Frees memory.
453 *
454 * ----------------------------------------------------------------------------
455 */
456
457 void
EFHNFree(hierName,prefix,type)458 EFHNFree(hierName, prefix, type)
459 HierName *hierName, *prefix;
460 int type; /* HN_ALLOC, HN_CONCAT, etc */
461 {
462 HierName *hn;
463
464 for (hn = hierName; hn; hn = hn->hn_parent)
465 {
466 if (hn == prefix)
467 break;
468
469 freeMagic((char *) hn);
470 if (efHNStats)
471 {
472 int len = strlen(hn->hn_name);
473 efHNRecord(-HIERNAMESIZE(len), type);
474 }
475 }
476 }
477
478 /*
479 * ----------------------------------------------------------------------------
480 *
481 * EFHNBest --
482 *
483 * Determine which of two names is more preferred. The most preferred
484 * name is a global name. Given two non-global names, the one with the
485 * fewest pathname components is the most preferred. If the two names
486 * have equally many pathname components, we choose the shortest.
487 * If they both are of the same length, we choose the one that comes
488 * later in the alphabet.
489 *
490 * Results:
491 * TRUE if the first name is preferable to the second, FALSE if not.
492 *
493 * Side effects:
494 * None.
495 *
496 * ----------------------------------------------------------------------------
497 */
498
499 bool
EFHNBest(hierName1,hierName2)500 EFHNBest(hierName1, hierName2)
501 HierName *hierName1, *hierName2;
502 {
503 int ncomponents1, ncomponents2, len1, len2;
504 HierName *np1, *np2;
505 char last1, last2;
506
507 for (ncomponents1 = 0, np1 = hierName1; np1; np1 = np1->hn_parent)
508 ncomponents1++;
509 for (ncomponents2 = 0, np2 = hierName2; np2; np2 = np2->hn_parent)
510 ncomponents2++;
511
512 last1 = hierName1->hn_name[strlen(hierName1->hn_name) - 1];
513 last2 = hierName2->hn_name[strlen(hierName2->hn_name) - 1];
514 if (last1 != '!' || last2 != '!')
515 {
516 /* Prefer global over local names */
517 if (last1 == '!') return TRUE;
518 if (last2 == '!') return FALSE;
519
520 /* Neither name is global, so chose label over generated name */
521 if (last1 != '#' && last2 == '#') return TRUE;
522 if (last1 == '#' && last2 != '#') return FALSE;
523 }
524
525 /*
526 * Compare two names the hard way. Both are of the same class,
527 * either both global or both non-global, so compare in order:
528 * number of pathname components, length, and lexicographic
529 * ordering.
530 */
531 if (ncomponents1 < ncomponents2) return TRUE;
532 if (ncomponents1 > ncomponents2) return FALSE;
533
534 /* Non-default substrate node name is preferred over "0" */
535 if (ncomponents1 == 1 && !strcmp(hierName1->hn_name, "0")) return FALSE;
536 if (ncomponents2 == 1 && !strcmp(hierName2->hn_name, "0")) return TRUE;
537
538 /* Same # of pathname components; check length */
539 for (len1 = 0, np1 = hierName1; np1; np1 = np1->hn_parent)
540 len1 += strlen(np1->hn_name);
541 for (len2 = 0, np2 = hierName2; np2; np2 = np2->hn_parent)
542 len2 += strlen(np2->hn_name);
543 if (len1 < len2) return TRUE;
544 if (len1 > len2) return FALSE;
545
546 return (efHNLexOrder(hierName1, hierName2) > 0);
547 }
548
549 /*
550 * ----------------------------------------------------------------------------
551 *
552 * efHNLexOrder --
553 *
554 * Procedure to ensure that the canonical ordering used in determining
555 * preferred names is the same as would have been used if we were comparing
556 * the string version of two HierNames, instead of comparing them as pathnames
557 * with the last component first.
558 *
559 * Results:
560 * Same as strcmp(), i.e,
561 * -1 if hierName1 should precede hierName2 lexicographically,
562 * +1 if hierName1 should follow hierName2, and
563 * 0 is they are identical.
564 *
565 * Side effects:
566 * None.
567 *
568 * ----------------------------------------------------------------------------
569 */
570
571 int
efHNLexOrder(hierName1,hierName2)572 efHNLexOrder(hierName1, hierName2)
573 HierName *hierName1, *hierName2;
574 {
575 int i;
576
577 if (hierName1 == hierName2)
578 return 0;
579
580 if (hierName1->hn_parent)
581 if (i = efHNLexOrder(hierName1->hn_parent, hierName2->hn_parent))
582 return i;
583
584 return strcmp(hierName1->hn_name, hierName2->hn_name);
585 }
586
587 /*
588 * ----------------------------------------------------------------------------
589 *
590 * efHNFromUse --
591 *
592 * Construct a HierName for a cell use (for the array element identified
593 * by (hc_x, hc_y) if the use is an array). The parent pointer of this
594 * newly allocated HierName will be set to prefix.
595 *
596 * Results:
597 * Returns a pointer to a newly allocated HierName.
598 *
599 * Side effects:
600 * See above.
601 * Note: we use a hash table to ensure that we always return
602 * the SAME HierName whenever prefix, the (x, y) use
603 * coordinates, and the use id are the same.
604 *
605 * ----------------------------------------------------------------------------
606 */
607
608 HierName *
efHNFromUse(hc,prefix)609 efHNFromUse(hc, prefix)
610 HierContext *hc; /* Contains use and array information */
611 HierName *prefix; /* Root part of name */
612 {
613 char *srcp, *dstp;
614 char name[2048], *namePtr;
615 Use *u = hc->hc_use;
616 HierName *hierName, *hn;
617 bool hasX, hasY;
618 HashEntry *he;
619 unsigned size;
620
621 hasX = u->use_xlo != u->use_xhi;
622 hasY = u->use_ylo != u->use_yhi;
623 namePtr = u->use_id;
624 if (hasX || hasY)
625 {
626 namePtr = name;
627 srcp = u->use_id;
628 dstp = name;
629 while (*dstp++ = *srcp++)
630 /* Nothing */;
631
632 /* Array subscript */
633 dstp[-1] = '[';
634
635 /* Y comes before X */
636 if (hasY)
637 {
638 (void) sprintf(dstp, "%d", hc->hc_y);
639 while (*dstp++)
640 /* Nothing */;
641 dstp--; /* Leave pointing to NULL byte */
642 }
643
644 if (hasX)
645 {
646 if (hasY) *dstp++ = ',';
647 (void) sprintf(dstp, "%d", hc->hc_x);
648 while (*dstp++)
649 /* Nothing */;
650 dstp--; /* Leave pointing to NULL byte */
651 }
652
653 *dstp++ = ']';
654 *dstp = '\0';
655 }
656
657 size = HIERNAMESIZE(strlen(namePtr));
658 hierName = (HierName *) mallocMagic ((unsigned)(size));
659 if (efHNStats) efHNRecord(size, HN_FROMUSE);
660 efHNInit(hierName, namePtr, (char *) NULL);
661 hierName->hn_parent = prefix;
662
663 /* See if we already have an entry for this one */
664 he = HashFind(&efHNUseHashTable, (char *) hierName);
665 if (HashGetValue(he))
666 {
667 freeMagic((char *) hierName);
668 return (HierName *) HashGetValue(he);
669 }
670 HashSetValue(he, (ClientData) hierName);
671
672 for (hn = hierName; hn; hn = hn->hn_parent)
673 HashFind(&efFreeHashTable, (char *) hierName);
674
675 return hierName;
676 }
677
678 /*
679 * ----------------------------------------------------------------------------
680 *
681 * efHNUseCompare --
682 *
683 * Compare two HierNames for equality, but using a different sense
684 * of comparison than efHNCompare: two names are considered equal
685 * only if their hn_parent fields are equal and their hn_name strings
686 * are identical.
687 *
688 * Results: Returns 0 if they are equal, 1 if not.
689 *
690 * efHNUseHash --
691 *
692 * Convert a HierName to a single 32-bit value suitable for being
693 * turned into a hash bucket by the hash module. Hashes based on
694 * hierName->hn_hash and hierName->hn_parent, rather than summing
695 * the hn_hash values.
696 *
697 * Results: Returns the 32-bit hash value.
698 *
699 * Side effects:
700 * None.
701 *
702 * ----------------------------------------------------------------------------
703 */
704
705 bool
efHNUseCompare(hierName1,hierName2)706 efHNUseCompare(hierName1, hierName2)
707 HierName *hierName1, *hierName2;
708 {
709 return ((bool)(hierName1->hn_parent != hierName2->hn_parent
710 || strcmp(hierName1->hn_name, hierName2->hn_name)
711 ));
712 }
713
714 int
efHNUseHash(hierName)715 efHNUseHash(hierName)
716 HierName *hierName;
717 {
718 return hierName->hn_hash + (spointertype) hierName->hn_parent;
719 }
720
721 /*
722 * ----------------------------------------------------------------------------
723 *
724 * efHNInit --
725 *
726 * Copy the string 'cp' into hierName->hn_name, also initializing
727 * the hn_hash fields of hierName. If 'endp' is NULL, copy all
728 * characters in 'cp' up to a trailing NULL byte; otherwise, copy
729 * up to 'endp'.
730 *
731 * Results:
732 * None.
733 *
734 * Side effects:
735 * See above.
736 *
737 * ----------------------------------------------------------------------------
738 */
739
740 void
efHNInit(hierName,cp,endp)741 efHNInit(hierName, cp, endp)
742 HierName *hierName; /* Fill in fields of this HierName */
743 char *cp; /* Start of name to be stored in hn_name */
744 char *endp; /* End of name if non-NULL; else, see above */
745 {
746 unsigned hashsum;
747 char *dstp;
748
749 hashsum = 0;
750 dstp = hierName->hn_name;
751 if (endp)
752 {
753 while (cp < endp)
754 {
755 hashsum = HASHADDVAL(hashsum, *cp);
756 *dstp++ = *cp++;
757 }
758 *dstp = '\0';
759 }
760 else
761 {
762 while (*dstp++ = *cp)
763 hashsum = HASHADDVAL(hashsum, *cp++);
764 }
765
766 hierName->hn_hash = hashsum;
767 }
768
769 /*
770 * ----------------------------------------------------------------------------
771 *
772 * efHNCompare --
773 *
774 * Compare two HierNames for equality. Passed as a client procedure
775 * to the hash module. The most likely place for a difference in the
776 * two names is in the lowest-level component, which fortunately is
777 * the first in a HierName list.
778 *
779 * Results:
780 * Returns 0 if they are equal, 1 if not.
781 *
782 * efHNHash --
783 *
784 * Convert a HierName to a single 32-bit value suitable for being
785 * turned into a hash bucket by the hash module. Passed as a client
786 * procedure to the hash module.
787 *
788 * Results:
789 * Returns the 32-bit hash value.
790 *
791 * Side effects:
792 * None.
793 *
794 * ----------------------------------------------------------------------------
795 */
796
797 int
efHNCompare(hierName1,hierName2)798 efHNCompare(hierName1, hierName2)
799 HierName *hierName1, *hierName2;
800 {
801 while (hierName1)
802 {
803 if (hierName1 == hierName2)
804 return 0;
805
806 if (hierName2 == NULL
807 || hierName1->hn_hash != hierName2->hn_hash
808 || strcmp(hierName1->hn_name, hierName2->hn_name) != 0)
809 return 1;
810 hierName1 = hierName1->hn_parent;
811 hierName2 = hierName2->hn_parent;
812 }
813
814 return (hierName2 ? 1 : 0);
815 }
816
817 int
efHNHash(hierName)818 efHNHash(hierName)
819 HierName *hierName;
820 {
821 int n;
822
823 for (n = 0; hierName; hierName = hierName->hn_parent)
824 n += hierName->hn_hash;
825
826 return n;
827 }
828
829 /*
830 * ----------------------------------------------------------------------------
831 *
832 * efHNDistCompare --
833 * efHNDistCopy --
834 * efHNDistHash --
835 * efHNDistKill --
836 *
837 * Procedures for managing a HashTable whose keys are pointers
838 * to malloc'd Distance structures. Distances point to a pair of
839 * HierNames; the comparison and hashing functions rely directly
840 * on those for processing HierNames (efHNCompare() and efHNHash()).
841 *
842 * Results:
843 * efHNDistCompare returns 0 if the two keys are equal, 1 if not.
844 * efHNDistCopy returns a pointer to a malloc'd copy of its Distance
845 * argument.
846 * efHNDistHash returns a single 32-bit hash value based on a Distance's
847 * two HierNames.
848 * efHNDistKill has no return value.
849 *
850 * Side effects:
851 * efHNDistKill frees its Distance argument, and adds the HierNames
852 * pointed to by it to the table of HierNames to free.
853 *
854 * ----------------------------------------------------------------------------
855 */
856
857 bool
efHNDistCompare(dist1,dist2)858 efHNDistCompare(dist1, dist2)
859 Distance *dist1, *dist2;
860 {
861 return ((bool)(efHNCompare(dist1->dist_1, dist2->dist_1)
862 || efHNCompare(dist1->dist_2, dist2->dist_2)
863 ));
864 }
865
866 char *
efHNDistCopy(dist)867 efHNDistCopy(dist)
868 Distance *dist;
869 {
870 Distance *distNew;
871
872 distNew = (Distance *) mallocMagic ((unsigned)(sizeof (Distance)));
873 *distNew = *dist;
874 return (char *) distNew;
875 }
876
877 int
efHNDistHash(dist)878 efHNDistHash(dist)
879 Distance *dist;
880 {
881 return efHNHash(dist->dist_1) + efHNHash(dist->dist_2);
882 }
883
884
885 void
efHNDistKill(dist)886 efHNDistKill(dist)
887 Distance *dist;
888 {
889 HierName *hn;
890
891 for (hn = dist->dist_1; hn; hn = hn->hn_parent)
892 (void) HashFind(&efFreeHashTable, (char *) hn);
893 for (hn = dist->dist_2; hn; hn = hn->hn_parent)
894 (void) HashFind(&efFreeHashTable, (char *) hn);
895
896 freeMagic((char *) dist);
897 }
898
899 /*
900 * ----------------------------------------------------------------------------
901 *
902 * efHNBuildDistKey --
903 *
904 * Build the key for looking in the Distance hash table for efFlatDists()
905 * above.
906 *
907 * Results:
908 * None.
909 *
910 * Side effects:
911 * Sets up *distKey.
912 *
913 * ----------------------------------------------------------------------------
914 */
915
916 void
efHNBuildDistKey(prefix,dist,distKey)917 efHNBuildDistKey(prefix, dist, distKey)
918 HierName *prefix;
919 Distance *dist;
920 Distance *distKey;
921 {
922 HierName *hn1, *hn2;
923
924 hn1 = EFHNConcat(prefix, dist->dist_1);
925 hn2 = EFHNConcat(prefix, dist->dist_2);
926 if (EFHNBest(hn1, hn2))
927 {
928 distKey->dist_1 = hn1;
929 distKey->dist_2 = hn2;
930 }
931 else
932 {
933 distKey->dist_1 = hn2;
934 distKey->dist_2 = hn1;
935 }
936
937 distKey->dist_min = dist->dist_min;
938 distKey->dist_max = dist->dist_max;
939 }
940
941 /*
942 * ----------------------------------------------------------------------------
943 *
944 * efHNDump --
945 *
946 * Print all the names in the node hash table efNodeHashTable.
947 * Used for debugging.
948 *
949 * Results:
950 * None.
951 *
952 * Side effects:
953 * Creates a file "hash.dump" and writes the node names to
954 * it, one per line.
955 *
956 * ----------------------------------------------------------------------------
957 */
958
959 void
efHNDump()960 efHNDump()
961 {
962 HashSearch hs;
963 HashEntry *he;
964 FILE *f;
965
966 f = fopen("hash.dump", "w");
967 if (f == NULL)
968 {
969 perror("hash.dump");
970 return;
971 }
972
973 HashStartSearch(&hs);
974 while (he = HashNext(&efNodeHashTable, &hs))
975 fprintf(f, "%s\n", EFHNToStr((HierName *) he->h_key.h_ptr));
976
977 (void) fclose(f);
978 }
979
980 int efHNSizes[4];
981
982 void
efHNRecord(size,type)983 efHNRecord(size, type)
984 int size;
985 int type;
986 {
987 efHNSizes[type] += size;
988 }
989
990 void
efHNPrintSizes(when)991 efHNPrintSizes(when)
992 char *when;
993 {
994 int total, i;
995
996 total = 0;
997 for (i = 0; i < 4; i++)
998 total += efHNSizes[i];
999
1000 printf("Memory used in HierNames %s:\n", when ? when : "");
1001 printf("%8d bytes for global names\n", efHNSizes[HN_GLOBAL]);
1002 printf("%8d bytes for concatenated HierNames\n", efHNSizes[HN_CONCAT]);
1003 printf("%8d bytes for names from cell uses\n", efHNSizes[HN_FROMUSE]);
1004 printf("%8d bytes for names from strings\n", efHNSizes[HN_ALLOC]);
1005 printf("--------\n");
1006 printf("%8d bytes total\n", total);
1007 }
1008