home *** CD-ROM | disk | FTP | other *** search
/ Source Code 1992 March / Source_Code_CD-ROM_Walnut_Creek_March_1992.iso / usenet / compsrcs / unix / volume02 / pathal.ias < prev    next >
Encoding:
Internet Message Format  |  1988-09-11  |  59.5 KB
  1. From: uucp (UNIX-UNIX copy)
  2. Subject: Pathalias - new release
  3. Newsgroups: mod.sources
  4. Approved: john@genrad.UUCP
  5.  
  6. Mod.sources:  Volume 2, Issue 36
  7. Submitted by: Peter Honeyman (princeton!honey)
  8.  
  9. ------------------- cut here --------------------------
  10. : To unbundle, sh this file
  11. echo README 1>&2
  12. sed 's/^-//' >README <<'//GO.SYSIN DD README'
  13. -From princeton!honey Wed Aug  7 00:02:19 EDT 1985
  14. To: whom it may concern
  15. Subject: new pathalias instructions
  16.  
  17. edit config.h
  18. make
  19.     peter
  20. //GO.SYSIN DD README
  21. echo CHANGES 1>&2
  22. sed 's/^-//' >CHANGES <<'//GO.SYSIN DD CHANGES'
  23. --- posted 8/85
  24. Private hosts documented.
  25. Homegrown scanner -- it's true what they say about lex.
  26. Slight improvement in memory allocation.  More to come.
  27. Build dbm file with pathalias ... | makedb ...
  28. Don't print paths for private hosts, or anyone they collide with.
  29. Domain-style addresses.  See man page.
  30. Make links bidirectional by adding DEAD back link.  Dumb, expensive, and wrong.
  31. Gatewayed nets.  See man page.
  32.  
  33. --- posted 1/85
  34. By popular request, no ! in dbm key.
  35. Network character must be one of !@%: -- dot is dead.
  36. Private hosts.  (Undocumented.  Goal is to support host name collisions.)
  37. Discourage mixing of left- (@) and right-associative (!) operators.  
  38. Magic @ <-> % rule in paths involving multiple @'s.
  39.  
  40. --- from smb version
  41. Directed graph.
  42. Reverse the sense of the -c (cost) flag.
  43. Don't complain about duplicate links -- use cheapest.
  44. No network names in the output.
  45.  
  46. --- epoch
  47. //GO.SYSIN DD CHANGES
  48. echo pathalias.1 1>&2
  49. sed 's/^-//' >pathalias.1 <<'//GO.SYSIN DD pathalias.1'
  50. .TH PATHALIAS 1 
  51. .SH NAME
  52. pathalias, makedb \- electronic address router
  53. .SH SYNOPSIS
  54. .B pathalias
  55. [
  56. .B \-vci
  57. ] [
  58. .B \-l
  59. host
  60. ] [
  61. .B \-d
  62. link
  63. ] [
  64. .ig
  65. .\" the -g option is for pathparse.  it's not really used by pathalias.
  66. .B \-g
  67. file
  68. ] [
  69. ..
  70. inputfiles
  71. ]
  72. .PP
  73. .B makedb
  74. [
  75. .B \-a
  76. ] [
  77. .B \-o
  78. dbmfile
  79. ] [
  80. files ...
  81. ]
  82. .SH DESCRIPTION
  83. .I Pathalias
  84. computes the shortest paths and corresponding routes from one
  85. host to all other known, reachable hosts.
  86. \fIPathalias\fP expects as input host-to-host connectivity
  87. information, with
  88. a host name in column 1, followed by white space, followed by
  89. a comma-separated list of links (also host names),
  90. denoting a connection from the host to the links.
  91. Connections are assumed to be unidirectional.
  92. A link-name may be preceded or followed by a network character to use
  93. in the path name.
  94. Valid network characters are `!', `@', `:', and `%'.
  95. The link-name (and network character, if present) may be
  96. followed by a ``cost'' in parentheses.
  97. .PP
  98. For example,
  99. .RS
  100. .nf
  101. down    princeton!(DEDICATED)
  102. princeton    topaz!(DEMAND+LOW)
  103. topaz    @rutgers(LOCAL)
  104. .fi
  105. .RE
  106. Costs may be arbitrary
  107. arithmetic expressions involving numbers, parentheses, '+', '\-', '*',
  108. and '/'.  Several symbolic numbers are
  109. defined, as follows:
  110. .PP
  111. .RS
  112. .nf
  113. .ta 10m 20m
  114. LOCAL    25    (local-area network connection)
  115. DEDICATED    95    (high speed dedicated link)
  116. DIRECT    200    (toll-free call)
  117. DEMAND    300    (long-distance call)
  118. HOURLY    500    (hourly poll)
  119. EVENING    1800    (time restricted call)
  120. DAILY    5000    (daily poll)
  121. WEEKLY    30000    (irregular poll)
  122. .fi
  123. .RE
  124. .PP
  125. In addition,
  126. DEAD is a very large number (effectively infinite),
  127. and HIGH and LOW are \-5 and +5 respectively,
  128. for baud-rate or quality bonuses/penalties.
  129. .PP
  130. The numbers are intended to represent frequency
  131. of connection, which seems to be far more important than baud
  132. rates for this type of traffic.  There is an assumed
  133. high overhead for each hop; thus, e.g., HOURLY is far more than
  134. DAILY / 24.
  135. .PP
  136. For the most part, arithmetic expressions that mix symbolic constants
  137. other than HIGH and LOW make no sense.  Thus, \fIe.g.\fP, if a host
  138. calls a local neighbor whenever there is work,
  139. and additionally polls every evening, the cost is
  140. DIRECT, \fInot\fP DIRECT+EVENING.
  141. .PP
  142. Aliases may be indicated by including lines of the form
  143. .RS
  144. name = alias [ , alias...]
  145. .RE
  146. The primary name is used in the output.
  147. .PP
  148. Fully connected networks, such as the ARPANET or a LAN,
  149. are indicated by
  150. .RS
  151. net = {host, host, ...}
  152. .RE
  153. The host-list may be preceded or followed by a routing
  154. character, and may be followed by a cost:
  155. .RS
  156. .nf
  157. princeton-ethernet = {down, yoyo, flakey, quirky, princeton, ivy}!(LOCAL)
  158. ARPA = @{sri-unix, mit-ai, su-score}(DEDICATED)
  159. .fi
  160. .RE
  161. Also see the section on \fIgateways and domains\fP below.
  162. .PP
  163. Connection data may be given while hiding host names
  164. by declaring
  165. .RS
  166. private {host [, host ...]}
  167. .RE
  168. .PP
  169. .I Pathalias
  170. will not generate routes for private hosts or for any otherwise declared
  171. host with the same name, but may produce routes
  172. through them.
  173. The scope of a private declaration extends from the declaration to the end of
  174. the input file in which it appears.
  175. It is best to put private definitions at the beginning of the
  176. appropriate input file.
  177. .PP
  178. Anything following # on an input line is ignored.  A line that begins with white
  179. space is taken as a continuation of the previous line.
  180. .PP
  181. The output, which appears on the standard output,
  182. is a list of host\-route pairs,
  183. where route is a string appropriate for use with
  184. \fIprintf\fP(3), e.g.
  185. .RS
  186. .nf
  187. .ta 10m 20m
  188. rutgers    princeton!topaz!%s@rutgers
  189. .fi
  190. .RE
  191. The ``%s'' in the route string should be replaced by the
  192. user name at the destination host.
  193. (This task is normally performed by a mailer.)
  194. .PP
  195. Except in the case of \fidomains\fP (see below),
  196. the name of a network is never used in
  197. expansions; thus, in the above example, the path from sri-unix to
  198. mit-ai would be '%s@mit-ai', not '%s@ARPA@mit-ai'.
  199. .PP
  200. Options:
  201. .TP 6
  202. .B  \-i
  203. Map all host names to lower case.
  204. .TP 6
  205. .B  \-c
  206. Print the costs of paths.
  207. .TP 6
  208. .B  \-v
  209. Report some statistics on stderr.
  210. .ig
  211. .\" the -g option is for pathparse and is not for public consumption (yet!).
  212. .TP 6
  213. .BR \-g " file\^"
  214. Dump the edges of the graph into the named file.
  215. ..
  216. .TP 6
  217. .BR  \-l " host\^"
  218. Use host as local host name.
  219. .TP 6
  220. .BR  \-d " link\^"
  221. Declares a dead link, host, or network.
  222. If link is of the form host1!host2, the link from host1 to host2
  223. is treated as an extremely high cost (i.e., dead) link.
  224. If link is a single host name, that
  225. host is treated as dead and will be used as an intermediate host of
  226. last resort on any path.
  227. If link is a network name, the network requires a gateway.
  228. .PP
  229. \fBGateways and domains.\fP\ \ A network is represented by
  230. a pseudo-host and a set of network members.
  231. Links from the network to the members have the weight given in
  232. the input, while
  233. links from the members to the network
  234. have zero cost.
  235. Networks that are declared dead on the command line show these
  236. latter weights as expensive ones,
  237. effectively prohibiting paths to members by way of the network.
  238. If the input also shows non-zero weight links from some members to the network,
  239. these hosts will act as gateways for the network.
  240. E.g., if csnet is declared dead on the command line (with
  241. the -d flag) and the input contains
  242. .RS
  243. .nf
  244. csnet = {...}
  245. csnet-relay    csnet
  246. .fi
  247. .RE
  248. then routes to csnet hosts will use csnet-relay as a gateway,
  249. rather than some other csnet host, one that might not
  250. be able or willing to act as a gateway.
  251. Furthermore, it is presumed that forwarding through
  252. gatewayed networks is to be discouraged.
  253. .PP
  254. Some intermediate nodes expect routes to specify domain names, e.g.,
  255. to get to bitnet host technion through the gateway at psuvax1,
  256. the appropriate route might be psuvax1!technion.bitnet!user.
  257. This syntax is generated if the routing character is repeated in
  258. the declaration of the gateway to the ``domain'', e.g.,
  259. .RS
  260. .nf
  261. bitnet = {..., technion, ...}!(DIRECT)
  262. psuvax1    bitnet!!(DIRECT)
  263. .fi
  264. .RE
  265. This syntax works with other routing characters as well, e.g.,
  266. .RS
  267. .nf
  268. csnet = @{...}
  269. csnet-relay @@csnet
  270. .fi
  271. .RE
  272. .PP
  273. .I Makedb
  274. builds a
  275. .IR dbm (3)
  276. database from the named input files, or from the standard input if
  277. no files are specified.
  278. (This replaces the obsolete 
  279. .I -b
  280. flag of
  281. .IR pathalias .)
  282. Normally, the database is truncated;
  283. if
  284. .B \-a
  285. is specified, the input records are appended to the existing database.
  286. The
  287. .B \-o
  288. flag specifies the base name of the dbm file.
  289. Input is expected to be sequence of ascii records
  290. each consisting of a key field and a data field, separated by a single tab.
  291. If the tab is missing, the data field is assumed to be empty.
  292. .SH FILES
  293. .ta \w'/usr/local/lib/palias.{dir,pag}     'u
  294. /usr/local/lib/palias.{dir,pag}    default dbm output
  295. .SH BUGS
  296. White space in options is mandatory;
  297. .I pathalias
  298. should use
  299. .IR getopt (3).
  300. .br
  301. The format string intended for
  302. .I printf
  303. is unable to anticipate the variety of addressing
  304. rules.
  305. In particular, if it contains an ``@'' and is given to
  306. .I printf
  307. along with an argument that also contains an ``@'', havoc is loosed.
  308. .br
  309. Domains constitute a futile attempt to defeat anarchy.
  310. .br
  311. The -i flag makes rice.rice impossible.
  312. .br
  313. .IR Dbm (3)
  314. wants a non-empty data field, forcing
  315. .I makedb
  316. to be imaginative.
  317. .SH COMPILE-TIME
  318. Edit config.h to accommodate \s-2UNIX\s0 variants.
  319. .SH AUTHORS
  320. Steve Bellovin (ulysses!smb)
  321. .br
  322. Peter Honeyman (princeton!honey)
  323.  
  324. //GO.SYSIN DD pathalias.1
  325. echo Makefile 1>&2
  326. sed 's/^-//' >Makefile <<'//GO.SYSIN DD Makefile'
  327. # pathalias -- by steve bellovin, as told to peter honeyman
  328.  
  329. # if you can't or don't intend to use dbm files, don't bother with makedb
  330. DBM = -ldbm
  331. # or if you roll your own ...
  332. # DBM = dbm.o
  333.  
  334. CC = cc
  335. CFLAGS =
  336. LDFLAGS =
  337. YFLAGS = -d
  338.  
  339. OBJ = addlink.o addnode.o extern.o local.o main.o mapit.o mapaux.o mem.o parse.o yylex.o
  340. HDRS = def.h config.h
  341. SRC = addlink.c addnode.c extern.c local.c main.c mapit.c mapaux.c mem.c parse.y yylex.c
  342. CSRC = addlink.c addnode.c extern.c local.c main.c mapit.c mapaux.c mem.c parse.c yylex.c
  343.  
  344. pathalias: $(OBJ)
  345.     $(CC) $(LDFLAGS) $(OBJ) $(LIBE) -o pathalias
  346.  
  347. all: pathalias makedb
  348.  
  349. $(OBJ):    def.h
  350.  
  351. # if touch had a proper exit status, this would work...
  352. def.h: config.h
  353.     touch def.h || get -s sccs/s.def.h
  354.  
  355. parse.c: parse.y def.h
  356.     $(YACC) $(YFLAGS) parse.y
  357.     mv y.tab.c parse.c
  358.  
  359. yylex.o:    parse.c yylex.c
  360.  
  361. makedb: makedb.o
  362.     $(CC) makedb.o $(DBM) -o makedb
  363.  
  364. makedb.o: config.h
  365.  
  366. clean:
  367.     rm -f *.o pa y.tab.c y.tab.h parse.c core
  368.  
  369. tags: $(SRC) $(HDRS) makedb.c
  370.     ctags -w $(HDRS) $(SRC)
  371.  
  372. bundle:
  373.     @bundle README CHANGES pathalias.1 Makefile ${HDRS} ${SRC} makedb.c
  374.  
  375. lint:    $(CSRC)
  376.     lint $(CFLAGS) $(CSRC)
  377.     lint makedb.c
  378.  
  379.  
  380. # the remainder is site specific and can be deleted.
  381.  
  382. # administering paths on 6 machines is easy -- here's how i do it
  383.  
  384. # hosts running delivermail
  385. DMEQUIV = tilt
  386.  
  387. # hosts running sendmail
  388. SMEQUIV = quirky flakey yoyo
  389.  
  390. # all neighbors
  391. NEIGHBORS = ${DMEQUIV} ${SMEQUIV} princeton
  392.  
  393. # including me
  394. SITES = down ${NEIGHBORS}
  395.  
  396. # in v8, * includes . files, sh has extended syntax.
  397. PATHFILES = paths/[^.]* paths.bell/[^.]* path.map/[^.]*
  398.  
  399. # from observation and rumor
  400. # avoid like the plague
  401. DEADHOSTS = -d harpo -d zeppo -d chico -d gummo -d tucc -d hogpc -d eosp1 -d twg
  402.  
  403. DEADLINKS = -d fortune!analog -d uiucdcs!uokmet -d siemens!uiucdcs -d vax135!uw-beaver -d research!eagle -d decvax!humus -d ulysses!ucbarpa
  404.  
  405. # nets that require gateways
  406. DEADNETS = -d CSNET -d BITNET -d ARPA -d DEC -d MAILNET
  407.  
  408. DEAD = ${DEADHOSTS} ${DEADLINKS} ${DEADNETS}
  409.  
  410. # map output to lower case.  dead links.
  411. ARGS = -i $(DEAD)
  412.  
  413. paths:    ${SITES}
  414.  
  415. # don't touch "down" until completely done.
  416. down:    paths/princeton
  417.     pathalias -v ${ARGS} $(PATHFILES) > down.new 2>ERRORS
  418.     sort down.new > down
  419. #    rm down.new
  420.  
  421. # NEIGHBORS have exactly the same links as down, so turn
  422. #    down    %s
  423. #    up    up!%s
  424. # into
  425. #    up    %s
  426. #    down    down!%s
  427.  
  428. # generate phoney costs for delivermail neighbors
  429. ${DMEQUIV}:    down
  430.     sed -e "s/^down    %s$$/$@    %s/" -e "s/^$@    $@!%s$$/down    down!%s/" -e 's/^/0    /' down > $@
  431.     
  432. # reorder the output and generate phoney costs for sendmail neighbors
  433. ${SMEQUIV}: down
  434.     sed -e "s/^down    %s$$/$@    %s/" -e "s/$@    $@!%s$$/down    down!%s/" -e 's/\(.*\)    \(.*\)/\1    0    \2/' down > $@
  435.  
  436. # ship it!
  437. sendit: ${NEIGHBORS}
  438.     for i in ${DMEQUIV}; do\
  439.         uucp -ga $$i $$i!/usr/local/lib/pathaliases;\
  440.         uux -z -gb $$i!newaliases;\
  441.     done
  442.     for i in ${SMEQUIV} princeton; do uucp $$i $$i!~/paths; done
  443.     touch sendit
  444.  
  445. # reorder the output for princeton/sendmail/uubang and generate phoney costs.
  446. princeton: down
  447.     pathalias ${ARGS} -l $@ $(PATHFILES)> $@.new 2>ERRORS
  448.     sed -e 's/\(.*\)    \(.*\)/\1    0    \2/' $@.new > $@
  449.     rm $@.new
  450.  
  451. # make output for friends.  (make friends for output?)
  452. sfyog rcalabs neoucom:
  453.     pathalias ${ARGS} -l $@ $(PATHFILES) > $@ 2>ERRORS
  454.  
  455. # desperation debugging -- examine the costs.
  456. costs:
  457.     pathalias -vci ${DEAD} -l down $(PATHFILES) > down.costs 2>ERRORS
  458.  
  459. # make one BIG file.  a bad idea.
  460. cat:
  461.     cat $(PATHFILES) > CAT
  462.  
  463. # generate test data using undocumented features.  (go away.)
  464. edges: down
  465.     pathalias -i -g edges $(PATHFILES)
  466.  
  467. //GO.SYSIN DD Makefile
  468. echo def.h 1>&2
  469. sed 's/^-//' >def.h <<'//GO.SYSIN DD def.h'
  470. /* pathalias -- by steve bellovin, as told to peter honeyman */
  471. #ifndef lint
  472. #ifdef MAIN
  473. static char    *h_sccsid = "@(#)def.h    7.1 (down!honey) 85/08/06";
  474. #endif MAIN
  475. #endif lint
  476.  
  477. #include <stdio.h>
  478. #include <ctype.h>
  479. #include "config.h"
  480.  
  481. typedef    long Cost;
  482. typedef struct node node;
  483. typedef struct link link;
  484.  
  485. #ifdef lint
  486. #define vprintf fprintf
  487. #else !lint -- this gives null effect warning
  488. /* because it's there ... */
  489. #define vprintf        !Vflag ? 0 : fprintf
  490. #endif lint
  491.  
  492. /* scanner (yylex) states */
  493. #define OTHER 0
  494. #define COSTING 1
  495. #define NEWLINE 2
  496. #define PRIVATING 3
  497.  
  498. #define    isnetc(c)    ((c)=='!' || (c)==':' || (c)=='@' || (c)=='%')
  499.  
  500. #define dirbits(c)    (c)
  501.  
  502. /* flags for n_flag */
  503. #define ISPRIVATE  0x0001 /* this node invisible outside its definition file */
  504. #define DEHASH       0x0002 /* removed from hash table yet? */
  505. #define ATSIGN       0x0004 /* seen an at sign?  used for magic @/% rules */
  506. #define MAPPED       0x0008 /* done mapping this node */
  507. #define    NDEAD       0x0010 /* node is dead */
  508. #define HASLEFT       0x0020 /* route has a left side net character */
  509. #define HASRIGHT   0x0040 /* route has a right side net character */
  510. #define    NNET       0x0080 /* node is a network name */
  511. #define INDFS       0x0100 /* used when removing net cycles */
  512. #define DUMP       0x0200 /* we have dumped this net's edges */
  513. #define NDOMAIN       0x0400 /* use .domain style addressing */
  514. #define GATEWAYIN  0x0800 /* heaped via gatewayed net */
  515. #define COLLISION  0x1000 /* collides with a private host name */
  516.  
  517. #define DEADNET(n) (((n)->n_flag & (NNET | NDEAD)) == (NNET | NDEAD))
  518.  
  519. /*
  520.  * save some space in nodes -- there are > 10,000 allocated!
  521.  *
  522.  *    node    *n_net        others in this network (parsing)
  523.  *     node    *n_root        root of net cycle (mapping)
  524.  *
  525.  *    node    *n_private    other privates in this file (parsing)
  526.  *    char    *n_path        path to this host (mapping)
  527.  *        
  528.  */
  529.  
  530. #define n_root n_unetroot.nu_root
  531. #define n_net n_unetroot.nu_net
  532.  
  533. #define n_private n_uprivatepath.nu_private
  534. #define n_path n_uprivatepath.nu_path
  535.  
  536. struct node {
  537.     char    *n_name;    /* host name */
  538.     link    *n_link;    /* head of adjacency list */
  539.     node    *n_alias;    /* real node (when this node is an alias) */
  540.     node    *n_aliaslink;    /* other aliases for this node */
  541.     union {
  542.         node    *nu_root;    /* root of net cycle (mapping) */
  543.         node    *nu_net;    /* others in this network (parsing) */
  544.     }    n_unetroot;
  545.     union {
  546.         node    *nu_private;    /* other privates in this file (parsing) */
  547.         char    *nu_path;    /* path to this host (mapping) */
  548.     }    n_uprivatepath;    
  549.     Cost    n_cost;        /* cost to this host */
  550.     short    n_tloc;        /* back ptr to heap/hash table */
  551.     short    n_flag;        /* see manifests above */
  552. };
  553.  
  554. #define    DEFNET    '!'            /* default network character */
  555. #define    DEFDIR    LLEFT            /* host on left in default net */
  556. #define    DEFCOST    ((Cost) 4000)        /* default cost of a link */
  557. #define    INF    ((Cost) 30000000)    /* infinitely expensive link */
  558.  
  559. /* data structure for adjacency list representation */
  560.  
  561. /* flags for l_dir */
  562.  
  563. /*
  564.  * there's an ugly dependency between the following manifests and the
  565.  * variable Netchars = "!:^@%", defined in extern.c.  this saves 2
  566.  * bytes per link (of which there are well over 20k).  this does not
  567.  * mean i'm satsified with bad design.
  568.  */
  569. #define NETDIR(l)    ((l)->l_flag & LDIR)
  570. #define NETCHAR(l)    (Netchars[(l)->l_flag & LNETCHARS])
  571.  
  572. #define LNETCHARS    0x3
  573. #define LBANG        0x0
  574. #define LCOLON        0x1
  575. #define LAT        0x2
  576. #define LPERCENT    0x3
  577.  
  578. #define LDIR    0x8    /* 0 for left, 1 for right */
  579. #define LRIGHT    0x0    /* user@host style */
  580. #define LLEFT    0x8    /* host!user style */
  581.  
  582. #define LDEAD    0x10    /* this link is dead */
  583. #define LDOMAIN 0x20    /* use host.domain.  i feel sick. */
  584.  
  585. struct link {
  586.     link    *l_next;    /* rest of adjacency list */
  587.     node    *l_to;        /* adjacent node */
  588.     Cost    l_cost;        /* edge cost */
  589.     char    l_flag;        /* right/left syntax */
  590. };
  591.  
  592. node    *addnode(), *newnode(), **newtable(), *addprivate();
  593. link    *addlink(), *lmerge(), *newlink();
  594. char    *strsave(), *local();
  595. void    setpath(), pack();
  596.  
  597. #define STATIC static
  598.  
  599. extern node    *Home;
  600. extern char    *Cfile;
  601. extern int    Fcnt;
  602. extern char    **Ifiles;
  603. extern char    *ProgName;
  604. extern int    Lineno;
  605. extern node    **Table;
  606. extern int    Tabsize;
  607. extern char    *Netchars;
  608. extern int    Vflag;
  609. extern int    Cflag;
  610. extern int    Iflag;
  611. extern int    Ncount;
  612. extern int    Lcount;
  613. extern char    *Pathout;
  614. extern char    *Graphout;
  615. extern char    *Linkout;
  616. extern node    *Private;
  617. extern int    Hashpart;
  618. extern int    Scanstate;
  619.  
  620. //GO.SYSIN DD def.h
  621. echo config.h 1>&2
  622. sed 's/^-//' >config.h <<'//GO.SYSIN DD config.h'
  623. /* pathalias -- by steve bellovin, as told to peter honeyman */
  624.  
  625. /* use strchr (strrchr), not index (rindex) -- probably system v */
  626. /* #define STRCHR /* */
  627.  
  628. /* uname() -- probably system v or 8th ed. */
  629. #define UNAME /* */
  630.  
  631. /* memset() -- probably system v or 8th ed. */
  632. #define MEMSET /* */
  633.  
  634. /* gethostname() -- probably 4.2bsd */
  635. /* #define GETHOSTNAME    /* */
  636.  
  637. /* bzero() -- probably 4.2bsd */
  638. /* #define BZERO /* */
  639.  
  640. /* default place for dbm output of makedb; can use -o file at run-time  */
  641. #define    ALIASDB    "/usr/local/lib/palias"
  642.  
  643. /*
  644.  * after much profiling, i finally found a decent malloc/free
  645.  * remove the next line if you disagree
  646.  */
  647. #define MYMALLOC    /**/
  648.  
  649. /*
  650.  * how many trailing 0's needed in a pointer?
  651.  *
  652.  * vax doesn't care, but setting ALIGN to 2 saves about 5% in time, at
  653.  * the expense of about 2% in space.  why bother?
  654.  *
  655.  * i am told that the 68000 and 3b20 want ALIGN to be 1.
  656.  *
  657.  * perkin-elmer 3220 wants ALIGN to be 2. 
  658.  */
  659. #define ALIGN 0
  660.  
  661. /****************************************/
  662. /*    END OF CONFIGURATION SECTION    */
  663. /*        EDIT NO MORE        */
  664. /****************************************/
  665. #ifdef MAIN
  666. #ifndef lint
  667. static char    *c_sccsid = "@(#)config.h    7.1 (down!honey) 85/08/06";
  668. #endif lint
  669. #endif MAIN
  670.  
  671. #ifdef MYMALLOC
  672.  
  673. #define malloc mymalloc
  674. #define free myfree
  675. char    *sbrk(), *mymalloc();
  676.  
  677. #ifdef ALIGN
  678.  
  679. #if ALIGN == 0
  680. #undef ALIGN
  681. #endif ALIGN == 0
  682.  
  683. #endif ALIGN
  684.  
  685. #ifndef ALIGN
  686. #define memget sbrk
  687. #else ALIGN
  688. char    *memget();
  689. #endif ALIGN
  690.  
  691. #endif MYMALLOC
  692.  
  693. #ifdef STRCHR
  694. #define index strchr
  695. #define rindex strrchr
  696. #endif STRCHR
  697.  
  698. #ifdef BZERO
  699. #define strclear(s, n)    ((void) bzero((s), (n)))
  700. #else !BZERO
  701. #    ifdef MEMSET
  702. char    *memset();
  703. #    define strclear(s, n)    ((void) memset((s), 0, (n)))
  704. #    else !MEMSET
  705.     (void) strclear();
  706. #    endif MEMSET
  707. #endif BZERO
  708.  
  709. long    atol();
  710. char    *malloc();
  711. char    *index();
  712. char    *rindex();
  713. FILE    *popen();
  714. char    *strcpy();
  715. //GO.SYSIN DD config.h
  716. echo addlink.c 1>&2
  717. sed 's/^-//' >addlink.c <<'//GO.SYSIN DD addlink.c'
  718. /* pathalias -- by steve bellovin, as told to peter honeyman */
  719. #ifndef lint
  720. static char    *sccsid = "@(#)addlink.c    7.1 (down!honey) 85/08/06";
  721. #endif lint
  722.  
  723. #include "def.h"
  724. link    *
  725. addlink(from, to, cost, netchar, netdir)
  726. node    *from;
  727. register node    *to;
  728. Cost    cost;
  729. char    netchar;
  730. char    netdir;
  731. {
  732.     register link    *l, *prev = 0;
  733.  
  734. #ifndef SQUANDER
  735.     /* welcome to cycle city -- inner loop follows */
  736.  
  737.     /*
  738.      * link chains are sorted by host struct address, largest to smallest.
  739.      * thus, newly declared hosts are at the front of the list.
  740.      */
  741.     for (l = from->n_link; l; l = l->l_next) {
  742.         if (to >= l->l_to)
  743.             break;
  744.         prev = l;
  745.     }
  746.     /* you are now leaving cycle city -- hope you enjoyed your stay */
  747.  
  748.     if (l && (to == l->l_to)) {
  749.         /*
  750.          * this is twisted by the awful gateway semantics.
  751.          *
  752.          * if "to" is a dead network, use the cheapest non-zero cost.
  753.          * ("from" is a gateway.)
  754.          *
  755.          * otherwise, use new cost if cheaper.
  756.          */
  757.         if ((DEADNET(to) && l->l_cost == 0) || cost < l->l_cost) {
  758.             l->l_cost = cost;
  759.             netbits(l, netchar, netdir);
  760.         }
  761.         return(l);
  762.     }
  763.  
  764. #endif !SQUANDER
  765.     l = newlink();
  766.  
  767.     if (prev) {
  768.         l->l_next = prev->l_next;
  769.         prev->l_next = l;
  770.     } else {
  771.         l->l_next = from->n_link;
  772.         from->n_link = l;
  773.     }
  774.  
  775.     l->l_to = to;
  776.     l->l_cost = cost;
  777.     if (netchar == 0) {
  778.         netchar = DEFNET;
  779.         netdir = DEFDIR;
  780.     }
  781.     netbits(l, netchar, netdir);
  782.  
  783.     return(l);
  784. }
  785.  
  786. deadlink(s) 
  787. char    *s;
  788. {
  789.     char    *t, c;
  790.     link    *l;
  791.  
  792.     for (t = s; !isnetc(*t); t++)
  793.         if (*t == 0) 
  794.             break;
  795.     if ((c = *t) != 0) {
  796.         *t = 0;
  797.         l = addlink(addnode(s), addnode(t + 1), INF / 2, c, DEFDIR);
  798.         l->l_flag |= LDEAD;
  799.     } else 
  800.         addnode(s)->n_flag |= NDEAD;
  801. }
  802.  
  803. netbits(l, netchar, netdir)
  804. link    *l;
  805. char    netchar, netdir;
  806. {
  807.     int    isadomain = 0;
  808.     char    *nptr;
  809.  
  810.     if (netchar & 0200) {
  811.         netchar &= 0177;
  812.         isadomain = LDOMAIN;
  813.     }
  814.     if ((nptr = index(Netchars, netchar)) == 0) {
  815.         fprintf(stderr, "%s: unknown network operator: %c\n",
  816.                                 ProgName, netchar);
  817.         badmagic(1);
  818.     }
  819.     l->l_flag &= ~(LNETCHARS|LDIR|LDOMAIN);
  820.     l->l_flag |= (nptr - Netchars) | dirbits(netdir) | isadomain;
  821. }
  822. //GO.SYSIN DD addlink.c
  823. echo addnode.c 1>&2
  824. sed 's/^-//' >addnode.c <<'//GO.SYSIN DD addnode.c'
  825. /* pathalias -- by steve bellovin, as told to peter honeyman */
  826. #ifndef lint
  827. static char    *sccsid = "@(#)addnode.c    7.1 (down!honey) 85/08/07";
  828. #endif lint
  829.  
  830. #include "def.h"
  831.  
  832. void    lowercase();
  833. node    *isprivate();
  834.  
  835. /*
  836.  * these numbers are chosen because:
  837.  *    -> they are prime,
  838.  *    -> they are monotonic increasing,
  839.  *    -> each is a tad smaller than a multiple of 1024.
  840.  * the first point yields good hash functions, the second is used for the
  841.  * standard re-hashing implementation of open addressing, and the third
  842.  * optimizes for quirks in some mallocs i have seen.
  843.  */
  844. STATIC int Primes[]    = {
  845.     1021, 2039, 3067, 4093, 5113, 6133, 7159, 8179, 9209,
  846.     10223, 11261, 12281, 13309, 14327, 15349, 16381, 17401,
  847.     18427, 19447, 20477, 21499, 22511, 23549, 24571, 25589, 0
  848. };
  849. STATIC int    Tabindex = -1;
  850. STATIC int    Collision;    /* mark host name collisions in hash() */
  851.  
  852. int    Tabsize;    /* used later for the priority queue */
  853. node    **Table;    /* ditto */
  854.  
  855. node    *
  856. addnode(name)
  857. register char    *name;
  858. {
  859.     register int    i;
  860.     register node    *n;
  861.  
  862.     if (Iflag)
  863.         lowercase(name);
  864.  
  865.     /* is it a private host? */
  866.     n = isprivate(name);
  867.     if (n != 0) {
  868.         while (n->n_alias)
  869.             n = n->n_alias;
  870.         return(n);
  871.     }
  872.  
  873.     i = hash(name, 0);
  874.     if (Table[i] != 0) {
  875.         n = Table[i];
  876.         while (n->n_alias)
  877.             n = n->n_alias;
  878.         return(n);
  879.     }
  880.  
  881.     n = newnode();
  882.     n->n_name = strsave(name);
  883.     Table[i] = n;
  884.     n->n_tloc = i;    /* essentially a back link to the table */
  885.     if (Collision)
  886.         n->n_flag |= COLLISION;    /* name collision with private host */
  887.  
  888.     return(n);
  889. }
  890.  
  891. alias(parent, child) 
  892. register node    *parent;    /* real node */
  893. register node    *child;        /* alias node */
  894. {
  895.     register node    *root;        /* root of this alias tree */
  896.  
  897.     if (parent == child) {
  898.         char    buf[BUFSIZ];
  899.  
  900.         sprintf(buf, "warning: alias redeclaration: %s = %s",
  901.             parent->n_name, parent->n_name);
  902.         yyerror(buf);
  903.         return;        /* caused by redeclaration of alias */
  904.     }
  905.  
  906.     /* avoid alias loops, force many-to-one */
  907.     /* can't happen -- wish it could ... */
  908.     if (parent->n_alias || child->n_alias) {
  909.         yyerror("can't nest aliases");
  910.         return;
  911.     }
  912.  
  913.     /* merge links from parent(s) to root, point parent at root */
  914.     for (root = parent->n_alias; root; root = root->n_alias) {
  915.         root->n_link = lmerge(root->n_link, parent->n_link);
  916.         parent->n_link = 0;
  917.         parent = root;
  918.     }
  919.  
  920.     /* merge child links into parent (now root) */
  921.     parent->n_link = lmerge(parent->n_link, child->n_link);
  922.     child->n_link = 0;
  923.  
  924.     /* set up the alias pointers */
  925.     child->n_alias = parent;
  926.     child->n_aliaslink = parent->n_aliaslink;
  927.     parent->n_aliaslink = child;
  928. }
  929.  
  930. /* double hashing */
  931. #define HASH1(n)    ((n) % Tabsize);
  932. #define HASH2(n)    (((n) % (Tabsize - 2)) + 1)
  933.  
  934. /*
  935.  * at 75% full, probes per access is about 2.
  936.  */
  937. #define HIGHWATER    75
  938. #define LOWWATER    50
  939. #define isfull(n, size)    ((n) > (((size) * HIGHWATER) / 100))
  940. #define isempty(n, size)    ((n) < (((size) * LOWWATER) / 100))
  941.  
  942. STATIC int
  943. hash(name, unique)
  944. char    *name;
  945. {
  946.     register int    probe, hash2;
  947.     register node    *n;
  948.  
  949.     if (Tabindex < 0) {            /* first time */
  950.         Tabindex = 0;
  951.         Tabsize = Primes[0];
  952.         Table = newtable(Tabsize);
  953.     }
  954.  
  955.     if (isfull(Ncount, Tabsize))
  956.         rehash();            /* more, more! */
  957.                 
  958.     probe = fold(name);
  959.     /* don't change the order of the next two lines */
  960.     hash2 = HASH2(probe);
  961.     probe = HASH1(probe);
  962.     /* thank you! */
  963.  
  964.     /*
  965.      * probe the hash table.
  966.      * if unique is set, we require a fresh slot.
  967.      * otherwise, use double hashing to find either
  968.      *  (1) an empty slot, or
  969.      *  (2) a non-private copy of this host name
  970.      *
  971.      * as a side effect, if we notice a collision with a private host
  972.      * we mark the other so that it is skipped at output time.
  973.      */
  974.     Collision = 0;
  975.     while ((n = Table[probe]) != 0) {
  976.         if (strcmp(n->n_name, name) == 0) {
  977.             if (unique)
  978.                 n->n_flag |= COLLISION;
  979.             else if (n->n_flag & ISPRIVATE)
  980.                 Collision++;
  981.             else
  982.                 break;    /* this is it! */
  983.         }
  984.         probe -= hash2;
  985.         if (probe < 0)
  986.             probe += Tabsize;
  987.     }
  988.     return(probe);
  989. }
  990.  
  991. STATIC int
  992. rehash()
  993. {
  994.     register node    **otable, **optr;
  995.     register int    probe;
  996.     int    osize;
  997.  
  998. #ifdef DEBUG
  999.     hashanalyze();
  1000. #endif DEBUG
  1001.     optr = Table + Tabsize - 1;    /* ptr to last */
  1002.     otable = Table;
  1003.     osize = Tabsize;
  1004.  
  1005.     do {
  1006.         Tabsize = Primes[++Tabindex];
  1007.         if (Tabsize == 0) {
  1008.             fprintf(stderr, "%s: > %d hosts\n", ProgName,
  1009.                             Primes[Tabindex-1]);
  1010.             badmagic(1);
  1011.         }
  1012.     } while (!isempty(Ncount, Tabsize));
  1013.     vprintf(stderr, "rehash into %d\n", Tabsize);
  1014.     Table = newtable(Tabsize);
  1015.  
  1016.     do {
  1017.         if (*optr == 0)
  1018.             continue;
  1019.         probe = hash((*optr)->n_name, (*optr)->n_flag & ISPRIVATE);
  1020.         if (Table[probe] != 0) {
  1021.             fprintf(stderr, "%s: rehash error\n", ProgName);
  1022.             badmagic(1);
  1023.         }
  1024.         Table[probe] = *optr;
  1025.         (*optr)->n_tloc = probe;
  1026.     } while (optr-- > otable);
  1027.     freetable(otable, osize);
  1028. }
  1029.  
  1030.  
  1031. STATIC
  1032. fold(s)
  1033. register char    *s;
  1034. {
  1035.     register int    sum = 0;
  1036.  
  1037.     while (*s) {
  1038.         sum <<= 2;
  1039.         sum += *s++;
  1040.     }
  1041.     if (sum < 0) 
  1042.         sum = -sum;
  1043.     return(sum);
  1044. }
  1045.  
  1046. /* merge the l2 list into the l1 list */
  1047. link    *
  1048. lmerge(l1, l2)
  1049. register link    *l1, *l2;
  1050. {
  1051.     register link    *ltmp;
  1052.     link    *rval;
  1053.  
  1054.     if (l1 == 0)
  1055.         return(l2);
  1056.  
  1057.     if (l2 == 0)
  1058.         return(l1);
  1059.  
  1060.     if (l1->l_to > l2->l_to) {
  1061.         ltmp = rval = l1;
  1062.         l1 = l1->l_next;
  1063.     } else if (l1->l_to < l2->l_to) {
  1064.         ltmp = rval = l2;
  1065.         l2 = l2->l_next;
  1066.     } else if (l1->l_cost <= l2->l_cost) {
  1067.         ltmp = rval = l1;
  1068.         l1 = l1->l_next;
  1069.         free((char *) l2);
  1070.         l2 = l2->l_next;
  1071.     } else {
  1072.         ltmp = rval = l2;
  1073.         l2 = l2->l_next;
  1074.         free((char *) l1);
  1075.         l1 = l1->l_next;
  1076.     }
  1077.  
  1078.     while (l1 && l2) {
  1079.         if (l1->l_to > l2->l_to) {
  1080.             ltmp->l_next = l1;
  1081.             ltmp = l1;
  1082.             l1 = l1->l_next;
  1083.         } else if (l1->l_to < l2->l_to) {
  1084.             ltmp->l_next = l2;
  1085.             ltmp = l2;
  1086.             l2 = l2->l_next;
  1087.         } else if (l1->l_cost <= l2->l_cost) {    /* use cheaper link */
  1088.             ltmp->l_next = l1;
  1089.             ltmp = l1;
  1090.             l1 = l1->l_next;
  1091.             free((char *) l2);
  1092.             l2 = l2->l_next;
  1093.         } else {
  1094.             ltmp->l_next = l2;
  1095.             ltmp = l2;
  1096.             l2 = l2->l_next;
  1097.             free((char *) l1);
  1098.             l1 = l1->l_next;
  1099.         }
  1100.     }
  1101.     if (l1)
  1102.         ltmp->l_next = l1;
  1103.     else
  1104.         ltmp->l_next = l2;
  1105.  
  1106.     return(rval);
  1107. }
  1108.  
  1109. hashanalyze()
  1110. {
  1111.     int    probe, hash2, count, i, collision[5];
  1112.     int    longest = 0, total = 0, slots = 0;
  1113.     int    nslots = sizeof(collision)/sizeof(collision[0]);
  1114.  
  1115.     if (!Vflag)
  1116.         return;
  1117.  
  1118.     strclear((char *) collision, sizeof(collision));
  1119.     for (i = 0; i < Tabsize; i++) {
  1120.         if (Table[i] == 0)
  1121.             continue;
  1122.         /* private hosts too hard to account for ... */
  1123.         if (Table[i]->n_flag & ISPRIVATE)
  1124.             continue;
  1125.         count = 1;
  1126.         probe = fold(Table[i]->n_name);
  1127.         /* don't change the order of the next two lines */
  1128.         hash2 = HASH2(probe);
  1129.         probe = HASH1(probe);
  1130.         /* thank you! */
  1131.         while (Table[probe] != 0
  1132.             && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
  1133.             count++;
  1134.             probe -= hash2;
  1135.             if (probe < 0)
  1136.                 probe += Tabsize;
  1137.         }
  1138.         if (Table[probe] == 0) {
  1139.             fprintf(stderr, "%s: impossible hash error for %s\n",
  1140.                     ProgName, Table[i]->n_name);
  1141.             continue;
  1142.         }
  1143.         
  1144.         total += count;
  1145.         slots++;
  1146.         if (count > longest)
  1147.             longest = count;
  1148.         if (count >= nslots)
  1149.             count = 0;
  1150.         collision[count]++;
  1151.     }
  1152.     for (i = 1; i < nslots; i++)
  1153.         if (collision[i])
  1154.             fprintf(stderr, "%d chains: %d (%d%%)\n",
  1155.                 i, collision[i], (collision[i] * 100)/ slots);
  1156.         if (collision[0])
  1157.             fprintf(stderr, "> %d chains: %d (%d%%)\n",
  1158.                 nslots - 1, collision[0],
  1159.                 (collision[0] * 100)/ slots);
  1160.     fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
  1161.         (double) total / slots, longest);
  1162. }
  1163.  
  1164. STATIC void
  1165. lowercase(s)
  1166. register char    *s;
  1167. {
  1168.     do {
  1169.         *s = isupper(*s) ? tolower(*s) : *s;
  1170.     } while (*s++);
  1171. }
  1172.  
  1173. STATIC node    *
  1174. isprivate(name)
  1175. register char    *name;
  1176. {
  1177.     register node    *n;
  1178.  
  1179.     for (n = Private; n != 0; n = n->n_private)
  1180.         if (strcmp(name, n->n_name) == 0)
  1181.             return(n);
  1182.     return(0);
  1183. }
  1184.  
  1185. fixprivate()
  1186. {
  1187.     register node    *n, *next;
  1188.     register int    i;
  1189.  
  1190.     for (n = Private; n != 0; n = next) {
  1191.         n->n_flag |= ISPRIVATE;        /* overkill, but safe */
  1192.         i = hash(n->n_name, 1);
  1193.         if (Table[i] != 0) {
  1194.             fprintf(stderr, "%s: impossible private node error on %s\n",
  1195.                 ProgName, n->n_name);
  1196.             badmagic(1);
  1197.         }
  1198.     
  1199.         Table[i] = n;
  1200.         n->n_tloc = i;    /* essentially a back link to the table */
  1201.         next = n->n_private;
  1202.         n->n_private = 0;    /* clear for later use */
  1203.     }
  1204.     Private = 0;
  1205. }
  1206.  
  1207. node    *
  1208. addprivate(name)
  1209. register char    *name;
  1210. {
  1211.     register node    *n;
  1212.  
  1213.     if (Iflag)
  1214.         lowercase(name);
  1215.     n = isprivate(name);
  1216.     if (n)
  1217.         return(n);    /* this isn't even worth a warning */
  1218.  
  1219.     n = newnode();
  1220.     n->n_name = strsave(name);
  1221.     n->n_private = Private;
  1222.     Private = n;
  1223.     return(n);
  1224. }
  1225. //GO.SYSIN DD addnode.c
  1226. echo extern.c 1>&2
  1227. sed 's/^-//' >extern.c <<'//GO.SYSIN DD extern.c'
  1228. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1229. #ifndef lint
  1230. static char    *sccsid = "@(#)extern.c    7.1 (down!honey) 85/08/06";
  1231. #endif lint
  1232.  
  1233. #include "def.h"
  1234.  
  1235. node    *Home;
  1236. int    Fcnt = -1;
  1237. char    *Cfile;
  1238. char    **Ifiles;
  1239. char    *ProgName;
  1240. int    Vflag;
  1241. int    Cflag;
  1242. int    Iflag;
  1243. int    Lineno = 1;
  1244. char    *Netchars = "!:@%";    /* sparse, but sufficient */
  1245. int    Ncount;
  1246. int    Lcount;
  1247. char    *Graphout;
  1248. char    *Linkout;
  1249. node    *Private;        /* list of private nodes in this file */
  1250. int    Hashpart;        /* used while mapping -- above is heap */
  1251. int    Scanstate = NEWLINE;    /* scanner (yylex) state */
  1252. //GO.SYSIN DD extern.c
  1253. echo local.c 1>&2
  1254. sed 's/^-//' >local.c <<'//GO.SYSIN DD local.c'
  1255. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1256. #ifndef lint
  1257. static char    *sccsid = "@(#)local.c    7.1 (down!honey) 85/08/06";
  1258. #endif lint
  1259.  
  1260. #include <stdio.h>
  1261. #include "config.h"
  1262.  
  1263. #ifdef    UNAME
  1264. #include <sys/utsname.h>
  1265.  
  1266. char    *
  1267. local()
  1268. {
  1269.     static struct utsname utsname;
  1270.  
  1271.     uname(&utsname);
  1272.     return(utsname.nodename);
  1273. }
  1274.  
  1275. #else !UNAME
  1276.  
  1277. char    *
  1278. local()
  1279. {
  1280.     static char lname[64];
  1281.     void    gethostname();
  1282.  
  1283.     gethostname(lname, sizeof(lname));
  1284.     return(lname);
  1285. }
  1286.  
  1287. #ifndef GETHOSTNAME
  1288.  
  1289. STATIC void
  1290. gethostname(name, len)
  1291. char    *name;
  1292. {
  1293.     FILE    *whoami, *fopen(), *popen();
  1294.     char    *ptr, *index();
  1295.  
  1296.     *name = '\0';
  1297.  
  1298.     /* try /etc/whoami */
  1299.     if ((whoami = fopen("/etc/whoami", "r")) != 0) {
  1300.         (void) fgets(name, len, whoami);
  1301.         (void) fclose(whoami);
  1302.         if ((ptr = index(name, '\n')) != 0)
  1303.             *ptr = '\0';
  1304.     }
  1305.     if (*name)
  1306.         return;
  1307.  
  1308.     /* try /usr/include/whoami.h */
  1309.     if ((whoami = fopen("/usr/include/whoami.h", "r")) != 0) {
  1310.         while (!feof(whoami)) {
  1311.             char    buf[100];
  1312.  
  1313.             if (fgets(buf, 100, whoami) == 0)
  1314.                 break;
  1315.             if (sscanf(buf, "#define sysname \"%[^\"]\"", name))
  1316.                 break;
  1317.         }
  1318.         (void) fclose(whoami);
  1319.         if (*name)
  1320.             return;
  1321.     }
  1322.  
  1323.     /* ask uucp */
  1324.     if ((whoami = popen("uuname -l", "r")) != 0) {
  1325.         (void) fgets(name, len, whoami);
  1326.         (void) pclose(whoami);
  1327.         if ((ptr = index(name, '\n')) != 0)
  1328.             *ptr = '\0';
  1329.     }
  1330.     if (*name)
  1331.         return;
  1332.     
  1333.     /* aw hell, i give up!  is this a real unix? */
  1334.     return;
  1335. }
  1336. #endif GETHOSTNAME
  1337. #endif UNAME
  1338. //GO.SYSIN DD local.c
  1339. echo main.c 1>&2
  1340. sed 's/^-//' >main.c <<'//GO.SYSIN DD main.c'
  1341. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1342. #ifndef lint
  1343. #define MAIN
  1344. static char    *sccsid = "@(#)main.c    7.1 (down!honey) 85/08/06";
  1345. #endif lint
  1346.  
  1347. #include "def.h"
  1348.  
  1349. main(argc, argv) 
  1350. int    argc; 
  1351. char    *argv[];
  1352. {
  1353.     char    *locname = 0;
  1354.  
  1355. #ifdef lint
  1356.     argc = argc;
  1357. #endif lint
  1358.  
  1359.     ProgName = argv[0];
  1360.     while (*++argv && **argv == '-') {
  1361.         (*argv)++;
  1362.         switch(**argv) {
  1363.  
  1364.         case 'l':    /* local name */
  1365.             locname = *++argv;
  1366.             if (!*locname)  {
  1367.                 fprintf(stderr, "%s: -l requires host name\n",
  1368.                     ProgName);
  1369.                 exit(1);
  1370.             }
  1371.             break;
  1372.  
  1373.         case 'd':    /* dead host or link */
  1374.             if (!*++argv) {
  1375.                 fprintf(stderr, "%s: -d requires host name\n",
  1376.                     ProgName);
  1377.                 exit(1);
  1378.             }
  1379.             deadlink(*argv);
  1380.             break;
  1381.  
  1382.         case 'g':    /* graph output file */
  1383.             Graphout = *++argv;
  1384.             if (!*Graphout)  {
  1385.                 fprintf(stderr, "%s: -g requires output file name\n",
  1386.                     ProgName);
  1387.                 exit(1);
  1388.             }
  1389.             break;
  1390.  
  1391.         case 's':    /* show cheapest links */
  1392.             Linkout = *++argv;
  1393.             if (!*Linkout)  {
  1394.                 fprintf(stderr, "%s: -s requires output file name\n",
  1395.                     ProgName);
  1396.                 exit(1);
  1397.             }
  1398.             break;
  1399.  
  1400.         case 0:
  1401.             break;    /* ignore naked '-' */
  1402.  
  1403.         default:
  1404.             while (**argv) {
  1405.                 switch (**argv) {
  1406.             
  1407.                 case 'v':    /* verbose stderr, somewhat boring */
  1408.                     Vflag++;
  1409.                     break;
  1410.  
  1411.                 case 'c':    /* print cost info */
  1412.                     Cflag++;
  1413.                     break;
  1414.  
  1415.                 case 'i':    /* ignore case */
  1416.                     Iflag++;
  1417.                     break;
  1418.  
  1419.                 default:
  1420.                     fprintf(stderr, "%s: -%c: unknown flag\n", ProgName,
  1421.                         **argv);
  1422.                     exit(1);
  1423.                 }
  1424.                 (*argv)++;
  1425.             }
  1426.         }
  1427.     }
  1428.  
  1429.     Fcnt++;
  1430.     if (*argv) {
  1431.         Ifiles = argv;
  1432.         freopen("/dev/null", "r", stdin);
  1433.     }
  1434.  
  1435.     if (!locname) 
  1436.         locname = local();
  1437.     if (*locname == 0) {
  1438.         locname = "lostinspace";
  1439.         fprintf(stderr, "%s: using \"%s\" for local name\n",
  1440.                 ProgName, locname);
  1441.     }
  1442.  
  1443.     Home = addnode(locname);    /* add home node */
  1444.     Home->n_cost = 0;        /* doesn't cost to get here */
  1445.  
  1446.     yyparse();            /* read in link info */
  1447.  
  1448.     hashanalyze();
  1449.  
  1450.     while (Home->n_alias) 
  1451.         Home = Home->n_alias;    /* bad practice, but conceivable */
  1452.  
  1453.     mapit();            /* compute shortest paths */
  1454.  
  1455.     exit(0);
  1456. }
  1457.  
  1458. badmagic(n)
  1459. {
  1460. #ifdef DEBUG
  1461.     abort();
  1462. #else !DEBUG
  1463.     exit(n);
  1464. #endif DEBUG
  1465. }
  1466. //GO.SYSIN DD main.c
  1467. echo mapit.c 1>&2
  1468. sed 's/^-//' >mapit.c <<'//GO.SYSIN DD mapit.c'
  1469. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1470. #ifndef lint
  1471. static char    *sccsid = "@(#)mapit.c    7.1 (down!honey) 85/08/06";
  1472. #endif lint
  1473.  
  1474. #include "def.h"
  1475.  
  1476. void    reheap(), insert(), setpath(), swap();
  1477. node    *min_node();
  1478.  
  1479. STATIC int    Nheap;
  1480.  
  1481. mapit()
  1482. {
  1483.     node *n, *next;
  1484.     link *l;
  1485.     Cost    cost, setcost();
  1486.     char    *sbrk();
  1487.  
  1488.     vprintf(stderr, "%d vertices, %d edges\n", Ncount, Lcount);
  1489.     vprintf(stderr, "break is %ld after parsing\n", (long) sbrk(0));
  1490.     
  1491.     /* use the hash Table for the heap */
  1492.     /* TODO: coalesce the following functions into a single one */
  1493.     pack();        /* remove holes in the Table */
  1494.     amerge();    /* merge all alias links once and for all */
  1495.     if (Linkout && *Linkout)    /* dump cheapest links */
  1496.         showlinks();
  1497.     if (Graphout && *Graphout)    /* dump the edge list */
  1498.         dumpgraph();
  1499.  
  1500.     while (Home->n_alias)
  1501.         Home = Home->n_alias;
  1502.     dehash(Home);
  1503.     Home->n_path = strsave("%s");
  1504.     insert(Home);
  1505.  
  1506.     /*
  1507.      * main mapping loop.
  1508.      * assertion: no alias can ever appear in the heap.  'struth.
  1509.      */
  1510.     while ((n = min_node()) != 0) {
  1511.  
  1512.         printit(n);
  1513.  
  1514.         /*
  1515.          * if reached by a gatewayed net, discourage further links.
  1516.          * this has some relevance to common carriers and the FCC ...
  1517.          */
  1518.         if (n->n_flag & GATEWAYIN)
  1519.             n->n_cost += 2* DEFCOST;
  1520.  
  1521.         /* add children to heap */
  1522.         for (l = n->n_link; l != 0; l = l->l_next) {
  1523.             next = l->l_to;
  1524.             while (next->n_alias)
  1525.                 next = next->n_alias;
  1526.             if (next->n_flag & MAPPED)
  1527.                 continue;
  1528.             dehash(next);
  1529.  
  1530.             cost = setcost(n, l, next);
  1531.  
  1532.             if (next->n_cost == 0) {        /* first time */
  1533.                 next->n_cost = cost;
  1534.                 insert(next);
  1535.             } else if (cost < next->n_cost) {    /* cheaper route */
  1536.                 next->n_cost = cost;
  1537.                 reheap(next);
  1538.             } else                    /* lose lose */
  1539.                 continue;
  1540.  
  1541.             /* note whether we got here via a gatewayed net */
  1542.             if (DEADNET(n))
  1543.                 next->n_flag |= GATEWAYIN;
  1544.             else
  1545.                 next->n_flag &= ~GATEWAYIN;
  1546.  
  1547.             setpath(n, next, l);
  1548.  
  1549.             free((char *) l);    
  1550.         }
  1551.  
  1552.         /* done with this node forever -- free as much as possible */
  1553.         free((char *) n->n_path);    /* absolutely free ... */
  1554.         free((char *) n->n_name);
  1555.  
  1556.         /* expunge aliases */
  1557.         for (next = n->n_aliaslink; next; next = next->n_aliaslink) {
  1558.             dehash(next);
  1559.             Table[next->n_tloc] = 0;
  1560.             next->n_tloc = 0;
  1561.             free((char *) next->n_name);
  1562.         }
  1563.     }
  1564.     vprintf(stderr, "break is %ld at after mapping\n", (long) sbrk(0));
  1565.  
  1566.     if (Nheap != 0) {
  1567.         fprintf(stderr, "%s: null entry found in heap\n", ProgName);
  1568.         badmagic(1);
  1569.     }
  1570.  
  1571.     if (Hashpart < Tabsize) {
  1572.         fprintf(stderr, "You can't get there from here:\n");
  1573.         while (Hashpart < Tabsize) {
  1574.             n = Table[Hashpart++];
  1575.             if (n->n_alias)
  1576.                 continue;    /* primary hosts only */
  1577.             fprintf(stderr, "\t%s", n->n_name);
  1578.             if (n->n_aliaslink) {
  1579.                 fprintf(stderr, " (alias %s", n->n_aliaslink->n_name);
  1580.                 n = n->n_aliaslink;
  1581.                 while (n = n->n_aliaslink)
  1582.                     fprintf(stderr,  ", %s", n->n_name);
  1583.                 putc(')', stderr);
  1584.             }
  1585.             putc('\n', stderr);
  1586.         }
  1587.     }
  1588. }
  1589.  
  1590. STATIC Cost
  1591. setcost(n, l, next)
  1592. register node    *n;
  1593. register link    *l;
  1594. node    *next;
  1595. {
  1596.     register Cost    cost;
  1597.  
  1598.     cost = n->n_cost + l->l_cost;    /* fundamental cost */
  1599.  
  1600.     /*
  1601.      * heuristics:
  1602.      *    charge for getting out of a dead host.
  1603.      *    charge for getting in to a dead net
  1604.      *         unless the link cost is non-zero (gateway).
  1605.      *    charge for a dead link.
  1606.      *    discourage mixing of left and right syntax.
  1607.      */
  1608.     if ((n->n_flag & (NNET | NDEAD)) == NDEAD)
  1609.         cost += INF/2;    /* dead host */
  1610.     if (DEADNET(next) && l->l_cost == 0)
  1611.         cost += INF/2;    /* dead net, not gateway */
  1612.     if (l->l_flag & LDEAD)
  1613.         cost += INF/2;    /* dead link */
  1614.     if ((n->n_flag & HASLEFT) && (NETDIR(l) == LRIGHT))
  1615.         cost += DEFCOST;    /* mix */
  1616.     if ((n->n_flag & HASRIGHT) && (NETDIR(l) == LLEFT))
  1617.         cost += DEFCOST;    /* mix */
  1618.  
  1619.     return(cost);
  1620. }
  1621.  
  1622. /*
  1623.  * heap implementation of priority queue.
  1624.  */
  1625.  
  1626. STATIC void
  1627. insert(n)
  1628. node    *n;
  1629. {
  1630.     int    i, parent;
  1631.  
  1632.     Table[n->n_tloc] = 0;
  1633.     if (Table[Nheap+1] != 0) {
  1634.         fprintf(stderr, "%s: heap error in insert\n", ProgName);
  1635.         badmagic(1);
  1636.     }
  1637.     if (Nheap++ == 0) {
  1638.         Table[1] = n;
  1639.         n->n_tloc = 1;
  1640.         return;
  1641.     }
  1642.  
  1643.     /* insert at the end and percolate up */
  1644.     Table[Nheap] = n;
  1645.     n->n_tloc = Nheap;
  1646.     for (i = Nheap; i > 1; i = parent) {
  1647.         if (Table[i] == 0) {
  1648.             fprintf(stderr, "%s: heap error in insert\n", ProgName);
  1649.             badmagic(1);
  1650.         }
  1651.         parent = i / 2;
  1652.         if (Table[i]->n_cost < Table[parent]->n_cost)
  1653.             swap(i, parent);
  1654.     }
  1655.     return;
  1656. }
  1657.  
  1658. STATIC node    *
  1659. min_node()
  1660. {
  1661.     node    *rval;
  1662.     int    i;
  1663.  
  1664.     if (Nheap == 0)
  1665.         return(0);
  1666.  
  1667.     rval = Table[1];    /* return this one */
  1668.             
  1669.     /* move last entry into root, percolate down */
  1670.     Table[1] = Table[Nheap];
  1671.     Table[1]->n_tloc = 1;
  1672.     Table[Nheap] = 0;
  1673.     if (--Nheap == 0)
  1674.         return(rval);
  1675.  
  1676.     i = 1;
  1677.     for (;;) {
  1678.         /* swap with smaller child  (if larger than same) */
  1679.         int    child;
  1680.  
  1681.         child = i * 2;
  1682.         if (child > Nheap)
  1683.             break;
  1684.         if (child < Nheap)     /* right child exists? */
  1685.             if (Table[child]->n_cost > Table[child+1]->n_cost)
  1686.                 child++;
  1687.             
  1688.         if (Table[i]->n_cost > Table[child]->n_cost)
  1689.             swap(i, child);
  1690.         i = child;
  1691.     }
  1692.  
  1693.     return(rval);
  1694. }
  1695.  
  1696. STATIC void
  1697. swap(i, j)
  1698. {
  1699.     node    *temp;
  1700.  
  1701.     temp = Table[i];
  1702.     Table[i] = Table[j];
  1703.     Table[j] = temp;
  1704.     Table[j]->n_tloc = j;
  1705.     Table[i]->n_tloc = i;
  1706. }
  1707.  
  1708. /* "percolate" node n up the heap by exchanging with the parent */
  1709. STATIC void
  1710. reheap(n)
  1711. node    *n;
  1712. {
  1713.     int    loc, parent;
  1714.     Cost    cost;
  1715.  
  1716.     cost = n->n_cost;
  1717.     for (loc = n->n_tloc; loc != 1; loc = parent) {
  1718.         parent = loc / 2;
  1719.         if (cost >= Table[parent]->n_cost)
  1720.             return;
  1721.         swap(loc, parent);
  1722.     }
  1723. }
  1724.  
  1725. STATIC void
  1726. setpath(prev, next, l) 
  1727. node    *prev, *next;
  1728. link    *l;
  1729. {
  1730.     char    pathbuf[BUFSIZ], hostbuf[BUFSIZ], *hptr;
  1731.     char    netchar, netdir;
  1732.  
  1733.     netchar = NETCHAR(l);
  1734.     netdir = NETDIR(l);
  1735.     /* undo settings from earlier calls */
  1736.     if (next->n_path)
  1737.         free((char *) next->n_path);    /* absolutely free ... */
  1738.  
  1739.     if (prev->n_flag & ATSIGN)
  1740.         next->n_flag |= ATSIGN;
  1741.     else
  1742.         next->n_flag &= ~ATSIGN;
  1743.  
  1744.     if (prev->n_flag & HASLEFT)
  1745.         next->n_flag |= HASLEFT;
  1746.     else
  1747.         next->n_flag &= ~HASLEFT;
  1748.  
  1749.     if (prev->n_flag & HASRIGHT)
  1750.         next->n_flag |= HASRIGHT;
  1751.     else
  1752.         next->n_flag &= ~HASRIGHT;
  1753.  
  1754.     if (next->n_flag & NNET) {
  1755.         /*
  1756.          * grumble. when climbing onto a "domain" style network,
  1757.          * append .netname.  but we can't do it 'til later ...
  1758.          *
  1759.          * unless, of course, we are in transit from another
  1760.          * domain style network, in which case we tack the
  1761.          * predecessor's name onto the next domain.
  1762.          *
  1763.          * e.g., prev = arpa, next = csnet.  change next->n_name
  1764.          * to csnet.arpa.  but first wipe out any previous
  1765.          * domain on next.  this is too gross for words.
  1766.          */
  1767.         if (l->l_flag & LDOMAIN) {
  1768.             next->n_flag |= NDOMAIN;
  1769.             if (prev->n_flag & NDOMAIN) {
  1770.                 /*
  1771.                  * clean out dots in next->n_name -- they're
  1772.                  * no longer valid.  N.B.: we are guaranteed
  1773.                  * that next is not an alias
  1774.                  */
  1775.                 hptr = index(next->n_name, '.');
  1776.                 if (hptr)
  1777.                     *hptr = 0;
  1778.                 sprintf(hostbuf, "%s.%s", next->n_name, prev->n_name);
  1779.                 free(next->n_name);
  1780.                 next->n_name = strsave(hostbuf);
  1781.             }
  1782.         } else
  1783.             next->n_flag &= ~NDOMAIN;
  1784.         next->n_path = strsave(prev->n_path);
  1785.         return;
  1786.     }
  1787.  
  1788.     /* do it by hand instead of sprintf-ing -- foo on '%' */
  1789.     if (netdir == LLEFT) {
  1790.         /* e.g., host!%s */
  1791.         next->n_flag |= HASLEFT;
  1792.         strcpy(hostbuf, next->n_name);
  1793.         hptr = hostbuf + strlen(hostbuf);
  1794.         if (prev->n_flag & NDOMAIN) {
  1795.             *hptr++ = '.';
  1796.             strcpy(hptr, prev->n_name);
  1797.             hptr += strlen(hptr);
  1798.         }
  1799.         *hptr++ = netchar;
  1800.         if (netchar == '%')
  1801.             *hptr++ = netchar;
  1802.         *hptr++ = '%';
  1803.         *hptr++ = 's';
  1804.         *hptr = 0;
  1805.     } else {
  1806.         /* e.g., %s@host, but watch out for the magic @-% conversion */
  1807.         next->n_flag |= HASRIGHT;
  1808.         if (netchar == '@') {
  1809.             next->n_flag |= ATSIGN;
  1810.             if (prev->n_flag & ATSIGN)
  1811.                 netchar = '%';    /* shazam?  shaman? */
  1812.         }
  1813.         hptr = hostbuf;
  1814.         *hptr++ = '%';
  1815.         *hptr++ = 's';
  1816.         *hptr++ = netchar;
  1817.         if (netchar == '%')
  1818.             *hptr++ = '%';
  1819.         strcpy(hptr, next->n_name);
  1820.         if (prev->n_flag & NDOMAIN) {
  1821.             hptr += strlen(hptr);
  1822.             *hptr++ = '.';
  1823.             strcpy(hptr, prev->n_name);
  1824.         }
  1825.     }
  1826.     /* this would be an sprintf were it not for the %'s.  feh. */
  1827.     pathprintf(pathbuf, prev->n_path, hostbuf);
  1828.     next->n_path = strsave(pathbuf);
  1829. }
  1830.  
  1831. dehash(n)
  1832. node    *n;
  1833. {
  1834.     if (n->n_flag & DEHASH)
  1835.         return;
  1836.     Table[Hashpart]->n_tloc = n->n_tloc;
  1837.     Table[n->n_tloc] = Table[Hashpart];
  1838.     Table[Hashpart] = n;
  1839.     n->n_flag |= DEHASH;
  1840.     n->n_tloc = Hashpart++;
  1841. }
  1842.  
  1843. pathprintf(buf, path, host)
  1844. char    *buf, *path, *host;
  1845. {
  1846.     for ( ; *buf = *path; path++) {
  1847.         if (*path == '%') {
  1848.             switch(path[1]) {
  1849.             case 's':
  1850.                 strcpy(buf, host);
  1851.                 buf += strlen(buf);
  1852.                 path++;
  1853.                 break;
  1854.             case '%':
  1855.                 *++buf = *++path;
  1856.                 buf++;
  1857.                 break;
  1858.             }
  1859.         } else
  1860.             buf++;
  1861.     }
  1862. }
  1863.  
  1864. printit(n)
  1865. node    *n;
  1866. {
  1867.     char    *path = n->n_path;
  1868.     Cost    cost = n->n_cost;
  1869.  
  1870.     for ( ; n; n = n->n_aliaslink) {
  1871.         n->n_flag |= MAPPED;
  1872.         if (n->n_flag & (NNET | ISPRIVATE | COLLISION))
  1873.             continue;
  1874.         if (Cflag)
  1875.             printf("%ld\t", (long) cost);
  1876.         printf("%s\t%s\n", n->n_name, path);
  1877.     }
  1878. }
  1879.  
  1880. //GO.SYSIN DD mapit.c
  1881. echo mapaux.c 1>&2
  1882. sed 's/^-//' >mapaux.c <<'//GO.SYSIN DD mapaux.c'
  1883. /* pathalias -- by steve bellovin, as told to peter honeyman */
  1884. #ifndef lint
  1885. static char    *sccsid = "@(#)mapaux.c    7.1 (down!honey) 85/08/06";
  1886. #endif lint
  1887.  
  1888. #include "def.h"
  1889.  
  1890. void    pack();
  1891.  
  1892. void
  1893. pack()
  1894. {
  1895.     int    hole, next;
  1896.  
  1897.     /* find first "hole " */
  1898.     for (hole = Tabsize - 1; hole >= 0 && Table[hole] != 0; --hole)
  1899.         ;
  1900.  
  1901.     /* repeatedly move next filled entry into last hole */
  1902.     for (next = hole - 1; next >= 0; --next) {
  1903.         if (Table[next] != 0) {
  1904.             Table[hole] = Table[next];
  1905.             Table[hole]->n_tloc = hole;
  1906.             Table[next] = 0;
  1907.             while (Table[--hole] != 0)    /* find next hole */
  1908.                 ;
  1909.         }
  1910.     }
  1911.     Hashpart = hole + 1;
  1912. }
  1913.  
  1914. amerge()
  1915. {
  1916.     node    *n, *a;
  1917.     int    i;
  1918.  
  1919.     for (i = Hashpart; i < Tabsize; i++) {
  1920.         n = Table[i];
  1921.         if (n == 0)    /* impossible, but ... */
  1922.             continue;
  1923.         for (a = n->n_alias; a; a = a->n_alias) {
  1924.             a->n_link = lmerge(a->n_link, n->n_link);
  1925.             n->n_link = 0;
  1926.             n = a;
  1927.         }
  1928.     }
  1929. }
  1930.  
  1931. STATIC FILE    *Gstream;
  1932.  
  1933. dumpgraph()
  1934. {
  1935.     int    i;
  1936.     node    *n;
  1937.  
  1938.     if ((Gstream = fopen(Graphout, "w")) == NULL) {
  1939.         fprintf(stderr, "%s: ", ProgName);
  1940.         perror(Graphout);
  1941.     }
  1942.  
  1943.     untangle();    /* untangle net cycles for proper output */
  1944.  
  1945.     for (i = Hashpart; i < Tabsize; i++) {
  1946.         n = Table[i];
  1947.         if (n == 0)
  1948.             continue;    /* impossible, but ... */
  1949.         if (n->n_alias)
  1950.             continue;    /* primaries only (wrong?) */
  1951.         /* a minor optimization ... */
  1952.         if (n->n_link == 0)
  1953.             continue;
  1954.         /* pathparse doesn't need these */
  1955.         if (n->n_flag & NNET)
  1956.             continue;
  1957.         dumpnode(n);
  1958.     }
  1959. }
  1960.  
  1961. dumpnode(from)
  1962. node    *from;
  1963. {
  1964.     node    *to;
  1965.     link    *l;
  1966.     char    netbuf[BUFSIZ], *nptr = netbuf;
  1967.  
  1968.     for (l = from->n_link ; l; l = l->l_next) {
  1969.         to = l->l_to;
  1970.         while (to->n_alias)
  1971.             to = to->n_alias;    /* get to primary */
  1972.         if (from == to)
  1973.             continue;    /* oops -- it's me! */
  1974.  
  1975.         if ((to->n_flag & NNET) == 0) {
  1976.             /* host -> host -- print host>host */
  1977.             if (l->l_cost == INF)
  1978.                 continue;    /* phoney link */
  1979.             fputs(from->n_name, Gstream);
  1980.             putc('>', Gstream);
  1981.             fputs(to->n_name, Gstream);
  1982.             putc('\n', Gstream);
  1983.         } else {
  1984.             /* host -> net -- just cache it for now */
  1985.             while (to->n_root && to != to->n_root)
  1986.                 to = to->n_root;
  1987.             *nptr++ = ',';
  1988.             strcpy(nptr, to->n_name);
  1989.             nptr += strlen(nptr);
  1990.         }
  1991.     }
  1992.  
  1993.     /* dump nets */
  1994.     if (nptr != netbuf) {
  1995.         /* nets -- print host@\tnet,net, ... */
  1996.         *nptr = 0;
  1997.         fputs(from->n_name, Gstream);
  1998.         putc('@', Gstream);
  1999.         *netbuf = '\t';    /* insert tab by killing initial ',' */
  2000.         fputs(netbuf, Gstream);    /* skip initial ',' */
  2001.         putc('\n', Gstream);
  2002.     }
  2003. }
  2004.  
  2005. /*
  2006.  * remove cycles in net definitions. 
  2007.  *
  2008.  * depth-first search
  2009.  *
  2010.  * for each net, run dfs on its neighbors (nets only).  if we return to
  2011.  * a visited node, that's a net cycle.  mark the cycle with a pointer
  2012.  * in the n_root field (which gets us closer to the root of this
  2013.  * portion of the dfs tree).
  2014.  */
  2015. untangle()
  2016. {
  2017.     int    i;
  2018.     node    *n;
  2019.  
  2020.     for (i = Hashpart; i < Tabsize; i++) {
  2021.         n = Table[i];
  2022.         if (n == 0 || (n->n_flag & NNET) == 0 || n->n_root)
  2023.             continue;
  2024.         dfs(n);
  2025.     }
  2026. }
  2027.  
  2028. dfs(n)
  2029. node    *n;
  2030. {
  2031.     link    *l;
  2032.     node    *next;
  2033.  
  2034.     n->n_flag |= INDFS;
  2035.     n->n_root = n;
  2036.     for (l = n->n_link; l; l = l->l_next) {
  2037.         next = l->l_to;
  2038.         if ((next->n_flag & NNET) == 0)
  2039.             continue;
  2040.         if ((next->n_flag & INDFS) == 0) {
  2041.             dfs(next);
  2042.             if (next->n_root != next)
  2043.                 n->n_root = next->n_root;
  2044.         } else
  2045.             n->n_root = next->n_root;
  2046.     }
  2047.     n->n_flag &= ~INDFS;
  2048. }
  2049.  
  2050. showlinks() 
  2051. {
  2052.     link    *l;
  2053.     node    *n;
  2054.     int    i;
  2055.     FILE    *estream;
  2056.  
  2057.     if ((estream = fopen(Linkout, "w")) == 0)
  2058.         return;
  2059.  
  2060.     for (i = Hashpart; i < Tabsize; i++) {
  2061.         n = Table[i];
  2062.         if (n == 0)    /* impossible, but ... */
  2063.             continue;
  2064.         if (l = n->n_link) {
  2065.             fprintf(estream, "%s\t%s(%d)", n->n_name,
  2066.                 l->l_to->n_name,
  2067.                 l->l_cost ? l->l_cost : DEFCOST);
  2068.             for (l = l->l_next; l; l = l->l_next)
  2069.                 fprintf(estream, ",\n\t%s(%d)", l->l_to->n_name,
  2070.                     l->l_cost ? l->l_cost : DEFCOST);
  2071.             fputc('\n', estream);
  2072.         }
  2073.     }
  2074.     (void) fclose(estream);
  2075. }
  2076.  
  2077. //GO.SYSIN DD mapaux.c
  2078. echo mem.c 1>&2
  2079. sed 's/^-//' >mem.c <<'//GO.SYSIN DD mem.c'
  2080. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2081. #ifndef lint
  2082. static char    *sccsid = "@(#)mem.c    7.1 (down!honey) 85/08/06";
  2083. #endif lint
  2084.  
  2085. #include "def.h"
  2086.  
  2087. link    *
  2088. newlink()
  2089. {
  2090.     register link    *rval;
  2091.  
  2092.     if ((rval = (link * ) malloc(sizeof(link))) == 0)
  2093.         nomem();
  2094.     strclear((char *) rval, sizeof(link));    /* fresh as a daisy */
  2095.     Lcount++;
  2096.     return(rval);
  2097. }
  2098.  
  2099. node    *
  2100. newnode()
  2101. {
  2102.     register node    *rval;
  2103.  
  2104.     if ((rval = (node * ) malloc(sizeof(node))) == 0)
  2105.         nomem();
  2106.     strclear((char *) rval, sizeof(node));    /* fresh as a daisy */
  2107.     Ncount++;
  2108.     return(rval);
  2109. }
  2110.  
  2111. char    *
  2112. strsave(s)
  2113. register char    *s;
  2114. {
  2115.     register char *r;
  2116.  
  2117.     if ((r = malloc(strlen(s) + 1)) == 0)
  2118.         nomem();
  2119.     (void) strcpy(r, s);
  2120.     return(r);
  2121. }
  2122.  
  2123. #ifndef strclear
  2124. void
  2125. strclear(dst, len)
  2126. register char *dst;
  2127. register int len;
  2128. {
  2129.     while (--len >= 0)
  2130.         *dst++ = 0;
  2131. }
  2132. #endif strclear
  2133.  
  2134. node    **
  2135. newtable(size)
  2136. register int    size;
  2137. {
  2138.     register node    **rval;
  2139.  
  2140.     if ((rval = (node **) malloc(size * sizeof(*rval))) == 0) 
  2141.         nomem();
  2142.     strclear((char *) rval, size * sizeof(*rval));
  2143.     return(rval);
  2144. }
  2145.  
  2146. freetable(t, size)
  2147. register node    **t;
  2148. {
  2149. #ifdef MYMALLOC
  2150.     addtoheap((char *) t, (long) (size * sizeof(*t)));
  2151. #else !MYMALLOC
  2152.     free((char *) t);
  2153. #endif MYMALLOC
  2154. }
  2155.  
  2156. nomem()
  2157. {
  2158.     fprintf(stderr, "%s: Out of memory\n", ProgName);
  2159.     badmagic(1);
  2160. }
  2161.  
  2162. #ifdef MYMALLOC
  2163. typedef struct heap heap;
  2164. struct heap {
  2165.     heap    *h_next;
  2166.     long    h_size;
  2167. };
  2168.  
  2169. STATIC heap    *Heap;    /* not to be confused with a priority queue */
  2170.  
  2171. addtoheap(p, size)
  2172. register char    *p;
  2173. register long    size;
  2174. {
  2175.     register heap    *hptr = (heap *) p;
  2176.  
  2177.     hptr->h_next = Heap;
  2178.     hptr->h_size = size;
  2179.     Heap = hptr;
  2180. }
  2181.  
  2182. char    *
  2183. mymalloc(n)
  2184. register int    n;
  2185. {
  2186.     static long    size;
  2187.     static char    *mem;
  2188.     register char    *rval;
  2189.     register heap    *hptr;
  2190.  
  2191.     if (n > BUFSIZ)
  2192.         rval = memget(n);
  2193.     else {
  2194. #ifdef ALIGN
  2195.         int adjustment;
  2196.  
  2197.         adjustment = align(mem);
  2198.         mem += adjustment;
  2199.         size -= adjustment;
  2200. #endif ALIGN
  2201.         if (n > size) {
  2202.             /* look in the heap -- already aligned */
  2203.             if (Heap) {
  2204.                 if (Heap->h_size >= size) {
  2205.                     mem = (char *) Heap;
  2206.                     size = Heap->h_size;
  2207.                     Heap = Heap->h_next;
  2208.                 } else {
  2209.                     for (hptr = Heap; hptr->h_next; hptr = hptr->h_next)
  2210.                         if (hptr->h_next->h_size >= size)
  2211.                             break;
  2212.                     if (hptr->h_next) {
  2213.                         mem = (char *) hptr->h_next;
  2214.                         size = hptr->h_next->h_size;
  2215.                         hptr->h_next = hptr->h_next->h_next;
  2216.                     }
  2217.                 }
  2218.             } else {
  2219.                 mem = memget(BUFSIZ);
  2220.                 size = BUFSIZ;
  2221.             }
  2222.         }
  2223.         rval = mem;
  2224.         mem += n;
  2225.         size -= n;
  2226.     }
  2227.     return(rval);
  2228. }
  2229.  
  2230. myfree(s)
  2231. char    *s;
  2232. {
  2233. #ifdef lint
  2234.     s = s;
  2235. #endif lint
  2236. }
  2237.  
  2238. #ifdef ALIGN
  2239. char    *
  2240. memget(n)
  2241. register int    n;
  2242. {
  2243.     register char    *rval;
  2244.     register int    adjustment = 0;
  2245.  
  2246.     adjustment = align(sbrk(0));
  2247.     rval = sbrk(n + adjustment);
  2248.     if (rval <= 0)
  2249.         return(0);
  2250.     return(rval + adjustment);
  2251. }
  2252.  
  2253. align(n)
  2254. register char    *n;
  2255. {
  2256.     register int    abits;    /* alignment bits */
  2257.     register int    adjustment = 0;
  2258.  
  2259.     abits = (int) n & ~(0xff << ALIGN) & 0xff;
  2260.     if (abits != 0)
  2261.         adjustment = (1 << ALIGN) - abits;
  2262.     return(adjustment);
  2263. }
  2264. #endif ALIGN
  2265.  
  2266. #endif MYMALLOC
  2267. //GO.SYSIN DD mem.c
  2268. echo parse.y 1>&2
  2269. sed 's/^-//' >parse.y <<'//GO.SYSIN DD parse.y'
  2270. %{
  2271. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2272. #ifndef lint
  2273. static char    *sccsid = "@(#)parse.y    7.1 (down!honey) 85/08/06";
  2274. #endif lint
  2275.  
  2276. #include "def.h"
  2277.  
  2278. %}
  2279.  
  2280. %union {
  2281.     node    *y_node;
  2282.     Cost    y_cost;
  2283.     char    y_net;
  2284.     char    *y_name;
  2285.     struct {
  2286.         node *ys_node;
  2287.         Cost ys_cost;
  2288.         char ys_net;
  2289.         char ys_dir;
  2290.     } y_s;
  2291. }
  2292.  
  2293. %type <y_s> site
  2294. %type <y_node> links aliases plist network nlist nsite host
  2295. %type <y_cost> cost cexpr
  2296. %type <y_net> netchar
  2297.  
  2298. %token <y_node>    SITE HOST
  2299. %token <y_cost>    COST
  2300. %token <y_net>    NET
  2301. %token NL PRIVATE
  2302.  
  2303. %left    '+' '-'
  2304. %left    '*' '/'
  2305.  
  2306. %%
  2307. map    :    /* empty */
  2308.     |    map NL
  2309.     |    map links NL
  2310.     |    map aliases NL
  2311.     |    map network NL
  2312.     |    map private NL
  2313.     |    error NL
  2314.     ;
  2315.  
  2316. host    :    HOST
  2317.     |    PRIVATE    {$$ = addnode("private");}
  2318.     ;
  2319.  
  2320. private    :    PRIVATE '{' {Scanstate = PRIVATING;} plist {Scanstate = OTHER;} '}'
  2321.     ;
  2322.  
  2323. plist    :    SITE        {$1->n_flag |= ISPRIVATE;}
  2324.     |    plist ',' SITE    {$3->n_flag |= ISPRIVATE;}
  2325.     |    plist ','    /* admit this benign error  */
  2326.     ;
  2327.  
  2328. network    :    host '=' nlist cost
  2329.             {fixnet($1, $3, $4, DEFNET, DEFDIR);}
  2330.     |    host '=' netchar nlist cost
  2331.             {fixnet($1, $4, $5, $3, LRIGHT);}
  2332.     |    host '=' nlist netchar cost
  2333.             {fixnet($1, $3, $5, $4, LLEFT);}
  2334.     ;
  2335.  
  2336. nlist     :    '{' nsite '}'    {$$ = $2;}
  2337.     ;
  2338.  
  2339. nsite    :    SITE
  2340.     |    nsite ',' SITE {
  2341.             /* be careful not to put anything on the list twice */
  2342.             if ($3->n_net == 0) {
  2343.                 $3->n_net = $1;
  2344.                 $$ = $3;
  2345.             }
  2346.         }
  2347.     |    nsite ','    /* admit this benign error */
  2348.     ;
  2349.         
  2350. aliases    :    host '=' SITE        {alias($1, $3);}
  2351.     |    aliases ',' SITE    {alias($1, $3);}
  2352.     |    aliases ','    /* admit this benign error */
  2353.     ;
  2354.  
  2355. links    :    host site cost {
  2356.             addlink($1, $2.ys_node, $3, $2.ys_net, $2.ys_dir);
  2357.             /*
  2358.              * give a default path for the return link.
  2359.              * this is wrong, but it's soothes the masses,
  2360.              * who insist on putting error output in the
  2361.              * output.  who said vox populi, vox Dei?
  2362.              */
  2363.             addlink($2.ys_node, $1, INF, $2.ys_net, $2.ys_dir);
  2364.         }
  2365.     |    links ',' site cost {
  2366.             addlink($1, $3.ys_node, $4, $3.ys_net, $3.ys_dir);
  2367.             /* ditto */
  2368.             addlink($3.ys_node, $1, INF, $3.ys_net, $3.ys_dir);
  2369.         }
  2370.     |    links ','    /* admit this benign error */
  2371.     ;
  2372.  
  2373. site    :    SITE    {
  2374.             $$.ys_node = $1;
  2375.             $$.ys_net = DEFNET;
  2376.             $$.ys_dir = DEFDIR;
  2377.         }
  2378.     |    netchar SITE    {
  2379.             $$.ys_node = $2;
  2380.             $$.ys_net = $1;
  2381.             $$.ys_dir = LRIGHT;
  2382.         }
  2383.     |    SITE netchar {
  2384.             $$.ys_node = $1;
  2385.             $$.ys_net = $2;
  2386.             $$.ys_dir = LLEFT;
  2387.         }
  2388.     ;
  2389.  
  2390. cost    :    /* empty -- cost is always optional */
  2391.             {$$ = DEFCOST;}
  2392.     |    '(' {Scanstate = COSTING;} cexpr {Scanstate = OTHER;} ')'
  2393.             {$$ = $3;}
  2394.     ;
  2395.  
  2396. cexpr    :    COST
  2397.     |    '(' cexpr ')'    {$$ = $2;}
  2398.     |    cexpr '+' cexpr    {$$ = $1 + $3;}
  2399.     |    cexpr '-' cexpr    {$$ = $1 - $3;}
  2400.     |    cexpr '*' cexpr    {$$ = $1 * $3;}
  2401.     |    cexpr '/' cexpr    {
  2402.             if ($3 == 0)
  2403.                 yyerror("zero term in divison\n");
  2404.             else
  2405.                 $$ = $1 / $3;
  2406.         }
  2407.     ;
  2408.  
  2409. netchar    :    NET        /* normal network operator */
  2410.     |    NET NET {    /* for "domains" */
  2411.             if ($1 != $2)
  2412.                 yyerror("invalid domain specifier\n");
  2413.             else
  2414.                 $$=($1 | 0200);
  2415.         }
  2416.     ;
  2417. %%
  2418.  
  2419. node    *revnetlist();
  2420.  
  2421. yyerror(s)
  2422. char *s;
  2423. {
  2424.     /* a concession to bsd error(1) */
  2425.     if (Cfile)
  2426.         fprintf(stderr, "\"%s\", ", Cfile);
  2427.     else
  2428.         fprintf(stderr, "%s: ", ProgName);
  2429.     fprintf(stderr, "line %d: %s\n", Lineno, s);
  2430. }
  2431.  
  2432. /*
  2433.  * patch in the costs of getting on/off the network.
  2434.  *
  2435.  * for each network member on netlist, add links:
  2436.  *    network -> member    cost = parameter;
  2437.  *    member -> network    cost = 0.
  2438.  * note that a network can have varying costs to its members, by suitable
  2439.  * multiple declarations.  this is a feechur.
  2440.  */
  2441. fixnet(netnode, netlist, cost, netchar, netdir)
  2442. register node    *netnode, *netlist;
  2443. Cost    cost;
  2444. char    netchar, netdir;
  2445. {
  2446.     register node    *nextnet;
  2447.  
  2448.     netnode->n_flag |= NNET;
  2449.  
  2450.     /*
  2451.      * avoid quadratic behavior in addlink(), by reversing net list.
  2452.      * this is cheap, and not necessarily effective, but in practice,
  2453.      * it cuts the cost of addlink() by three.  can you believe that?!?
  2454.      */
  2455.     netlist = revnetlist(netlist);
  2456.  
  2457.     /* now insert the links */
  2458.     for ( ; netlist; netlist = nextnet) {
  2459.         /* network -> member */
  2460.         (void) addlink(netnode, netlist, cost, netchar, netdir);
  2461.  
  2462.         /* member -> network */
  2463.         (void) addlink(netlist, netnode, (Cost) 0, netchar, netdir);
  2464.         nextnet = netlist->n_net;
  2465.         netlist->n_net = 0;    /* clear for later use */
  2466.     }
  2467. }
  2468.  
  2469. STATIC node    *
  2470. revnetlist(n)
  2471. node    *n;
  2472. {
  2473.     register node    *pred, *current, *succ;
  2474.  
  2475.     if ((pred = n) == 0 || (current = n->n_net) == 0)
  2476.         return(n);
  2477.  
  2478.     pred->n_net = 0;
  2479.  
  2480.     while (current) {
  2481.         succ = current->n_net;
  2482.         current->n_net = pred;
  2483.         pred = current;
  2484.         current = succ;
  2485.     }
  2486.     return(pred);
  2487. }
  2488. //GO.SYSIN DD parse.y
  2489. echo yylex.c 1>&2
  2490. sed 's/^-//' >yylex.c <<'//GO.SYSIN DD yylex.c'
  2491. #ifndef lint
  2492. static char    *sccsid = "@(#)yylex.c    7.1 (down!honey) 85/08/06";
  2493. #endif lint
  2494.  
  2495. #include "def.h"
  2496. #include "y.tab.h"
  2497.  
  2498. extern    YYSTYPE yylval;
  2499.  
  2500. #define LBRACE '{'
  2501. #define RBRACE '}'
  2502. #define LPAREN '('
  2503. #define RPAREN ')'
  2504. #define QUOTE '"'
  2505.  
  2506. Cost isacost();
  2507.  
  2508. int
  2509. yylex()
  2510. {
  2511.     int    c;
  2512.     Cost    cost;
  2513.     char    buf[BUFSIZ], errbuf[128];
  2514.  
  2515. tailrecursion:
  2516.     if (feof(stdin) && yywrap())
  2517.         return(EOF);
  2518.  
  2519.     if ((c = getchar()) == EOF)
  2520.         goto tailrecursion;
  2521.  
  2522.     while (c == ' ' || c == '\t')
  2523.         c = getchar();
  2524.  
  2525.     if (c == '\n') {
  2526.         Lineno++;
  2527.         c = getchar();
  2528.         if (c == ' ' || c == '\t')
  2529.             goto tailrecursion;
  2530.         ungetc(c, stdin);
  2531.         Scanstate = NEWLINE;
  2532.         return(NL);
  2533.     }
  2534.  
  2535.     if (c == '#') {
  2536.         while ((c = getchar()) != '\n')
  2537.             if (c == EOF)
  2538.                 goto tailrecursion;
  2539.         ungetc(c, stdin);
  2540.         goto tailrecursion;
  2541.     }
  2542.  
  2543.     ungetc(c, stdin);
  2544.  
  2545.     switch(Scanstate) {
  2546.     case COSTING:
  2547.         if (isdigit(c)) {
  2548.             cost = 0;
  2549.             for (c = getchar(); isdigit(c); c = getchar())
  2550.                 cost = (cost * 10) + c - '0';
  2551.  
  2552.             ungetc(c, stdin);
  2553.             yylval.y_cost = cost;
  2554.             return(COST);
  2555.         }
  2556.  
  2557.         
  2558.         if (getword(buf) == 0) {
  2559.             if ((yylval.y_cost = isacost(buf)) == 0) {
  2560.                 sprintf(errbuf, "unknown cost (%s), using default", buf);
  2561.                 yyerror(errbuf);
  2562.                 yylval.y_cost = DEFCOST;
  2563.             }
  2564.             return(COST);
  2565.         }
  2566.  
  2567.         return(getchar());    /* can't be EOF */
  2568.  
  2569.     case NEWLINE:
  2570.         Scanstate = OTHER;
  2571.         if (getword(buf) != 0)
  2572.             return(getchar());    /* can't be EOF */
  2573.         if (c != '"' && strcmp(buf, "private") == 0)
  2574.             return(PRIVATE);
  2575.  
  2576.         yylval.y_node = addnode(buf);
  2577.         return(HOST);
  2578.  
  2579.     case PRIVATING:
  2580.         if (getword(buf) == 0) {
  2581.             yylval.y_node = addprivate(buf);
  2582.             return(SITE);
  2583.         }
  2584.         return(getchar());    /* can't be EOF */
  2585.     }
  2586.  
  2587.     if (getword(buf) == 0) {
  2588.         yylval.y_node = addnode(buf);
  2589.         return(SITE);
  2590.     }
  2591.  
  2592.     c = getchar();    /* can't be EOF */
  2593.  
  2594.     if (index(Netchars, c)) {
  2595.         yylval.y_net = c;
  2596.         return(NET);
  2597.     }
  2598.  
  2599.     return(c);
  2600. }
  2601.  
  2602. getword(str)
  2603. char    *str;
  2604. {
  2605.     int    c;
  2606.  
  2607.     c = getchar();
  2608.     if (c == QUOTE) {
  2609.         for ( ; (*str = getchar()) != '"'; str++) {
  2610.             if (*str == '\n') {
  2611.                 yyerror("newline in quoted string\n");
  2612.                 ungetc('\n', stdin);
  2613.                 return(-1);
  2614.             }
  2615.         }
  2616.         *str = 0;
  2617.         return(0);
  2618.     }
  2619.  
  2620.     /* host name must start with alphanumeric or _ */
  2621.     if (!isalnum(c) && c != '_') {
  2622.         ungetc(c, stdin);
  2623.         return(-1);
  2624.     }
  2625.  
  2626. yymore:
  2627.     do {
  2628.         *str++ = c;
  2629.         c = getchar();
  2630.     } while (isalnum(c) || c == '.' || c == '_');
  2631.  
  2632.     if (c == '-' && Scanstate != COSTING)
  2633.         goto yymore;
  2634.  
  2635.     ungetc(c, stdin);
  2636.     *str = 0;
  2637.     return(0);
  2638. }
  2639.  
  2640. static struct ctable {
  2641.     char *cname;
  2642.     Cost cval;
  2643. } ctable[] = {
  2644.     /*
  2645.      * this list is searched sequentially (with strcmps!).
  2646.      * it is too long.  (they are ordered by frequency of
  2647.      * appearance in a "typical" dataset.)
  2648.      *
  2649.      * adding a 0 cost token breaks isacost().  don't do it.
  2650.      */
  2651.     {"DEMAND", 300},
  2652.     {"DAILY", 5000},
  2653.     {"DIRECT", 200},
  2654.     {"EVENING", 1800},
  2655.     {"LOCAL", 25},
  2656.     {"LOW", 5},    /* baud rate penalty */
  2657.     {"HOURLY", 500},
  2658.     {"POLLED", 5000},
  2659.     {"DEDICATED", 95},
  2660.     {"WEEKLY", 30000},
  2661.     {"DEAD", INF/2},
  2662.     {"HIGH", -5},    /* baud rate bonus */
  2663.     /* the remainder are reviled */
  2664.     {"ARPA", 100},
  2665.     {"DIALED", 300},
  2666.     {"A", 300},
  2667.     {"B", 500},
  2668.     {"C", 1800},
  2669.     {"D", 5000},
  2670.     {"E", 30000},
  2671.     {"F", INF/2},
  2672.     0
  2673. };
  2674.  
  2675. STATIC Cost
  2676. isacost(buf)
  2677. char    *buf;
  2678. {
  2679.     struct ctable    *ct;
  2680.  
  2681.     for (ct = ctable; ct->cname; ct++)
  2682.         if (strcmp(buf, ct->cname) == 0)
  2683.             return(ct->cval);
  2684.  
  2685.     return((Cost) 0);
  2686. }
  2687.  
  2688. yywrap()
  2689. {
  2690.     char    errbuf[100];
  2691.  
  2692.     fixprivate();    /* munge private host definitions */
  2693.  
  2694.     if (Ifiles == 0) 
  2695.         return(1);
  2696.  
  2697.     fclose(stdin);
  2698.     while (*Ifiles) {
  2699.         Lineno = 1;
  2700.         Fcnt++;
  2701.         if (fopen((Cfile = *Ifiles++), "r"))
  2702.             return(0);
  2703.         sprintf(errbuf, "%s: %s", ProgName, Cfile);
  2704.         perror(errbuf);
  2705.     }
  2706.     return(1);
  2707. }
  2708. //GO.SYSIN DD yylex.c
  2709. echo makedb.c 1>&2
  2710. sed 's/^-//' >makedb.c <<'//GO.SYSIN DD makedb.c'
  2711. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2712. #ifndef lint
  2713. static char    *sccsid = "@(#)makedb.c    7.1 (down!honey) 85/08/06";
  2714. #endif lint
  2715.  
  2716. #include <stdio.h>
  2717. #include "config.h"
  2718.  
  2719. typedef struct {
  2720.     char *dptr;
  2721.     int dsize;
  2722. } datum;
  2723.  
  2724. char    *Ofile = ALIASDB, *ProgName, *Fname;
  2725. int    Nets, Paths, Edges;
  2726.  
  2727. char    *strany();
  2728.  
  2729. #define USAGE "makedb [-o dbname] [file ...]"
  2730.  
  2731. main(argc, argv)
  2732.     char    *argv[];
  2733. {    int    verbose = 0, append = 0;
  2734.     char    *ofptr;
  2735.     FILE    *dbstream;
  2736.  
  2737.     ProgName = argv[0];
  2738.     --argc;
  2739.     for ( ; *++argv && **argv == '-'; --argc) {
  2740.         (*argv)++;
  2741.         switch(**argv) {
  2742.  
  2743.         case 'o':    /* dbm output file */
  2744.             Ofile = *++argv;
  2745.             --argc;
  2746.             if (*Ofile == 0) {
  2747.                 usage();
  2748.                 exit(1);
  2749.             }
  2750.             if ((ofptr = rindex(Ofile, '/')) != 0)
  2751.                 ofptr++;
  2752.             else
  2753.                 ofptr = Ofile;
  2754.             if (strlen(ofptr) > 10) {
  2755.                 ofptr[10] = 0;
  2756.                 fprintf(stderr, "%s: using %s for db output\n",
  2757.                     ProgName, Ofile);
  2758.             }
  2759.             break;
  2760.  
  2761.         case 'v':    /* chatty */
  2762.             verbose++;
  2763.             break;
  2764.  
  2765.         case 'a':    /* append mode */
  2766.             append++;
  2767.             break;
  2768.  
  2769.         default:
  2770.             fprintf(stderr, "%s: -%s: unknown flag\n", ProgName, *argv);
  2771.             usage();
  2772.             exit(1);
  2773.             break;
  2774.  
  2775.         }
  2776.     }
  2777.  
  2778.     if (append == 0 && dbmfile(Ofile) < 0) {
  2779.         perror_(Ofile);
  2780.         exit(1);
  2781.     }
  2782.  
  2783.     if (dbminit(Ofile) < 0) {
  2784.         perror_(Ofile);
  2785.         exit(1);
  2786.     }
  2787.  
  2788.     if (argc == 0) {
  2789.         makedb(stdin);
  2790.     } else {
  2791.         while (argc > 0) {
  2792.             if ((dbstream = fopen(*argv, "r")) == NULL) {
  2793.                 perror_(*argv);
  2794.             } else {
  2795.                 Fname = *argv;
  2796.                 makedb(dbstream);
  2797.                 fclose(dbstream);
  2798.             }
  2799.             --argc;
  2800.             argv++;
  2801.         }
  2802.     }
  2803.     if (verbose)
  2804.         fprintf(stderr, "%d paths, %d edges, %d nets\n", Paths, Edges, Nets);
  2805. }
  2806.  
  2807. dbmfile(dbmf)
  2808.     char    *dbmf;
  2809. {    int    fd;
  2810.     char    buf[BUFSIZ];
  2811.  
  2812.     sprintf(buf, "%s.dir", dbmf);
  2813.     fd = creat(buf, 0666);
  2814.     if (fd < 0)
  2815.         return(-1);
  2816.     close(fd);
  2817.  
  2818.     sprintf(buf, "%s.pag", dbmf);
  2819.     fd = creat(buf, 0666);
  2820.     if (fd < 0)
  2821.         return(-1);
  2822.     close(fd);
  2823.  
  2824.     return(0);
  2825. }
  2826.  
  2827. makedb(stream)
  2828.     FILE    *stream;
  2829. {    char    *op, line[BUFSIZ], *end;
  2830.     datum    key, val;
  2831.  
  2832.     /*
  2833.      * keys and values are 0 terminated.  this wastes time and
  2834.      * (disk) space, and is generally stupid.  it does buy
  2835.      * simplicity and backwards compatibility.
  2836.      */
  2837.     key.dptr = line;
  2838.     while (fgets(line, sizeof(line), stream) != NULL) {
  2839.         end = line + strlen(line);
  2840.         end[-1] = 0;            /* kill newline */
  2841.         op = index(line, '\t');
  2842.         if (op != 0) {
  2843.             *op++ = 0;
  2844.             key.dsize = op - line;        /* 0 terminated */
  2845.             val.dptr = op;
  2846.             val.dsize = end - op;        /* 0 terminated */
  2847.         } else {
  2848.             key.dsize = end - line;        /* 0 terminated */
  2849.             val.dptr = "\0";        /* why must i do this? */
  2850.             val.dsize = 1;
  2851.         }
  2852.         if (store(key, val) < 0)
  2853.             perror_(Ofile);
  2854.     }
  2855. }
  2856.  
  2857. perror_(str)
  2858.     char    *str;
  2859. {
  2860.     fprintf(stderr, "%s: ", ProgName);
  2861.     perror(str);
  2862. }
  2863.  
  2864. usage()
  2865. {
  2866.     fputs(USAGE, stderr);
  2867. }
  2868. //GO.SYSIN DD makedb.c
  2869. exit
  2870.  
  2871.  
  2872.