home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume22 / pathalias10 / part01 / arpatxt.c next >
C/C++ Source or Header  |  1990-06-07  |  13KB  |  683 lines
  1. #ifndef lint
  2. static char *sccsid = "@(#)arpatxt.c    9.4 88/09/21";
  3. #endif
  4.  
  5. /*
  6.  * convert hosts.txt into pathalias format.
  7.  *
  8.  * alias rule: "host.dom.ain,nickname.arpa,..." -> host = nickname, ...
  9.  */
  10.  
  11. /* remove the next line for standard or research unix */
  12. #define BSD
  13.  
  14. #ifdef BSD
  15. #define strchr index
  16. #endif /* BSD */
  17.  
  18. #include <stdio.h>
  19. #include <ctype.h>
  20.  
  21. /* imports */
  22. extern char *re_comp(), *malloc(), *strchr(), *calloc();
  23. extern char *gets(), *strcpy(), *fgets();
  24. extern FILE *fopen();
  25.  
  26. typedef struct node node;
  27.  
  28. struct node {
  29.     node *child;    /* subdomain or member host */
  30.     node *parent;    /* parent domain */
  31.     node *next;    /* sibling in domain tree or host list */
  32.     char *name;    /* host name */
  33.     node *alias;    /* list of aliases */
  34.     node *bucket;
  35.     node *gateway;
  36.     int  flag;
  37. };
  38.  
  39. node *Top;
  40. int Atflag, Fflag, Iflag, Vflag;
  41. char *DotArpa = ".ARPA";
  42. char Fname[256], *Fstart;
  43.  
  44. node *newnode(), *find();
  45. char *strsave(), *lowercase();
  46. void crcinit();
  47. long fold();
  48. FILE *mkfile();
  49. int insert();
  50.  
  51. #define ISADOMAIN(n) ((n) && *((n)->name) == '.')
  52.  
  53. /* for node.flag */
  54. #define COLLISION 1
  55.  
  56. /* for formatprint() */
  57. #define PRIVATE        0
  58. #define HOSTS        1
  59. #define SUBDOMAINS    2
  60.  
  61. /* for usage() */
  62. #define USAGE "usage: %s [-i@] [-g gateway] [-p privatefile] [-f | -d directory] [file ...]\n"
  63.  
  64. main(argc, argv)
  65.     char **argv;
  66. {    int c;
  67.     char *progname;
  68.     extern char *optarg;
  69.     extern int optind;
  70.  
  71.     if ((progname = strchr(argv[0], '/')) != 0)
  72.         progname++;
  73.     else
  74.         progname = argv[0];
  75.     crcinit();
  76.  
  77.     Top = newnode();    /* needed for adding gateways */
  78.     while ((c = getopt(argc, argv, "d:fg:ip:v@")) != EOF)
  79.         switch(c) {
  80.         case 'd':
  81.             strcpy(Fname, optarg);
  82.             break;
  83.         case 'f':    /* filter mode -- write on stdout */
  84.             Fflag++;
  85.             break;
  86.         case 'g':
  87.             gateway(optarg);
  88.             break;
  89.         case 'i':
  90.             Iflag++;
  91.             break;
  92.         case 'p':
  93.             readprivates(optarg);
  94.             break;
  95.         case 'v':
  96.             Vflag++;
  97.             break;
  98.         case '@':
  99.             Atflag++;
  100.             break;
  101.         default:
  102.             usage(progname);
  103.         }
  104.  
  105.     if (Fflag && *Fname)
  106.         usage(progname);
  107.     if (Iflag)
  108.         (void) lowercase(DotArpa);
  109.     if (Top->gateway == 0)
  110.         fprintf(stderr, "%s: warning: no gateway to top level domains\n", progname);
  111.  
  112.     Fstart = Fname + strlen(Fname);
  113.     if (Fstart != Fname) {
  114.         *Fstart++ = '/';
  115.         *Fstart = 0;
  116.     }
  117.     /* should do the mkdir here instead of the shell script ...*/
  118.         
  119.     Top->name = "internet";
  120.     if (optind == argc)
  121.         scan();
  122.     else for ( ; optind < argc; optind++) {
  123.         if (freopen(argv[optind], "r", stdin) == 0) {
  124.             perror(argv[optind]);
  125.             continue;
  126.         }
  127.         scan();
  128.     }
  129.     setuniqflag(Top);    /* look for and mark collisions */
  130.     hashanalyze();        /* check hash algorithm performance */
  131.     merge();        /* make unique domain names */
  132.     dump(Top);        /* print */
  133.     return 0;
  134. }
  135.  
  136. scan()
  137. {    static first;
  138.     char buf0[BUFSIZ], buf1[BUFSIZ], buf2[BUFSIZ];
  139.  
  140.     if (first++ == 0)
  141.         (void) re_comp("^HOST.*SMTP");
  142.     while (gets(buf0) != 0) {
  143.         if (re_exec(buf0) == 0)
  144.             continue;
  145.         if (sscanf(buf0, "HOST : %[^:] : %[^: ]", buf1, buf2) != 2)
  146.             continue;
  147.         if (Iflag)
  148.             (void) lowercase(buf2);
  149.         if (insert(buf2) != 0)
  150.             fprintf(stderr, "input error: %s\n", buf0);
  151.     }
  152. }
  153. /*
  154.  * format of private file:
  155.  *    one per line, optionally followed by white space and comments
  156.  *    line starting with # is comment
  157.  */
  158. readprivates(pfile)
  159.     char *pfile;
  160. {    FILE *f;
  161.     node *n;
  162.     char buf[BUFSIZ], *bptr;
  163.  
  164.     if ((f = fopen(pfile, "r")) == 0) {
  165.         perror(pfile);
  166.         return;
  167.     }
  168.     while (fgets(buf, BUFSIZ, f) != 0) {
  169.         if (*buf == '#')
  170.             continue;
  171.         if ((bptr = strchr(buf, ' ')) != 0)
  172.             *bptr = 0;
  173.         if ((bptr = strchr(buf, '\t')) != 0)
  174.             *bptr = 0;
  175.         if (*buf == 0)
  176.             continue;
  177.         n = newnode();
  178.         n->name = strsave(buf);
  179.         hash(n);
  180.     }
  181.     (void) fclose(f);
  182. }
  183. usage(progname)
  184.     char *progname;
  185. {
  186.     fprintf(stderr, USAGE, progname);
  187.     exit(1);
  188. }
  189.  
  190. dumpgateways(ndom, f)
  191.     node *ndom;
  192.     FILE *f;
  193. {    node *n;
  194.  
  195.     for (n = ndom->gateway; n; n = n->next) {
  196.         fprintf(f, "%s ", n->name);
  197.         if (Atflag)
  198.             putc('@', f);
  199.         fprintf(f, "%s(%s)\t# gateway\n", ndom->name,
  200.                 ndom == Top ? "DEDICATED" : "LOCAL");
  201.     }
  202. }
  203.  
  204. gateway(buf)
  205.     char *buf;
  206. {    node *n, *dom;
  207.     char *dot;
  208.  
  209.     dot = strchr(buf, '.');
  210.     if (dot) {
  211.         dom = find(dot);
  212.         *dot = 0;
  213.     } else
  214.         dom = Top;
  215.  
  216.     n = newnode();
  217.     n->name = strsave(buf);
  218.     n->next = dom->gateway;
  219.     dom->gateway = n;
  220. }
  221.     
  222. int
  223. insert(buf)
  224.     char *buf;
  225. {    char host[BUFSIZ], *hptr, *dot;
  226.     node *n;
  227.  
  228.     for (hptr = host; *hptr = *buf++; hptr++)
  229.         if (*hptr == ',')
  230.             break;
  231.  
  232.     if (*hptr == ',')
  233.         *hptr = 0;
  234.     else
  235.         buf = 0;    /* no aliases */
  236.  
  237.     if ((dot = strchr(host, '.')) == 0)
  238.         return 1;    /* can't happen */
  239.     
  240.     if (strcmp(dot, DotArpa) == 0)
  241.         buf = 0;        /* no aliases */
  242.  
  243.     n = find(dot);
  244.     *dot = 0;
  245.  
  246.     addchild(n, host, buf);
  247.     return 0;
  248. }
  249.  
  250. node *
  251. find(domain)
  252.     char *domain;
  253. {    char *dot;
  254.     node *parent, *child;
  255.  
  256.     if (domain == 0)
  257.         return Top;
  258.     if ((dot = strchr(domain+1, '.')) != 0) {
  259.         parent = find(dot);
  260.         *dot = 0;
  261.     } else
  262.         parent = Top;
  263.  
  264.     for (child = parent->child; child; child = child->next)
  265.         if (strcmp(domain, child->name) == 0)
  266.             break;
  267.     if (child == 0) {
  268.         child = newnode();
  269.         child->next = parent->child;
  270.         parent->child = child;
  271.         child->parent = parent;
  272.         child->name = strsave(domain);
  273.     }
  274.     return child;
  275. }
  276.  
  277. node *
  278. newnode()
  279. {
  280.     node *n;
  281.  
  282.     if ((n = (node *) calloc(1, sizeof(node))) == 0)
  283.         abort();
  284.     return n;
  285. }
  286.  
  287. char *
  288. strsave(buf)
  289.     char *buf;
  290. {    char *mstr;
  291.  
  292.     if ((mstr = malloc(strlen(buf)+1)) == 0)
  293.         abort();
  294.     strcpy(mstr, buf);
  295.     return mstr;
  296. }
  297.  
  298. addchild(n, host, aliases)
  299.     node *n;
  300.     char *host, *aliases;
  301. {    node *child;
  302.  
  303.     /* check for dups?  nah! */
  304.     child = newnode();
  305.     child->name = strsave(host);
  306.     child->parent = n;
  307.     child->next = n->child;
  308.     makealiases(child, aliases);
  309.     n->child = child;
  310. }
  311.  
  312. /* yer basic tree walk to make output */
  313. dump(n)
  314.     node *n;
  315. {    node *child;
  316.     FILE *f;
  317.     int privates;
  318.  
  319.     /* sanity check */
  320.     if (n != Top && ! ISADOMAIN(n))
  321.         abort();
  322.  
  323.     f = mkfile(n);        /* prepare the output file */
  324.     privates = domprint(n, f);        /* print this domain */
  325.     dumpgateways(n, f);    /* print any gateways to this domain */
  326.     if (privates || n == Top)
  327.         fputs("private {}\n", f);    /* end scope of privates */
  328.     if (Fflag)
  329.         putc('\n', f);
  330.     else
  331.         (void) fclose(f);
  332.     for (child = n->child; child; child = child->next)
  333.         if (child->child)
  334.             dump(child);
  335. }
  336.  
  337. qcmp(a, b)
  338.     node **a, **b;
  339. {
  340.     return strcmp((*a)->name, (*b)->name);
  341. }
  342.  
  343. domprint(n, f)
  344.     node *n;
  345.     FILE *f;
  346. {    node *table[8191], *child, *alias;
  347.     char *cost = 0;
  348.     int nelem, i, privates = 0;
  349.  
  350.     /*
  351.      * dump private definitions.  
  352.      * sort hosts and aliases for pretty output.
  353.      */
  354.     if (n != Top) {
  355.         i = 0;
  356.         for (child = n->child; child; child = child->next) {
  357.             table[i++] = child;
  358.             for (alias = child->alias; alias; alias = alias->next)
  359.                 table[i++] = alias;
  360.         }
  361.  
  362.         qsort((char *) table, i, sizeof(table[0]), qcmp);
  363.         privates = formatprint(f, table, i, PRIVATE, "private", cost);
  364.     }
  365.  
  366.     /* dump domains and aliases, sorted for pretty output */
  367.     i = 0;
  368.     for (child = n->child; child; child = child->next)
  369.         table[i++] = child;
  370.     qsort((char *) table, i, sizeof(table[0]), qcmp);
  371.  
  372.     /* cost is DEDICATED for hosts in top-level domains, LOCAL o.w. */
  373.     if (n->parent == Top && strchr(n->name + 1, '.') == 0)
  374.         cost = "DEDICATED";
  375.     else
  376.         cost = "LOCAL";
  377.  
  378.     (void) formatprint(f, table, i, HOSTS, n->name, cost);
  379.     (void) formatprint(f, table, i, SUBDOMAINS, n->name, "0");
  380.  
  381.     /* dump aliases */
  382.     nelem = i;
  383.     for (i = 0; i < nelem; i++) {
  384.         if ((alias = table[i]->alias) == 0)
  385.             continue;
  386.         fprintf(f, "%s = %s", table[i]->name, alias->name);
  387.         for (alias = alias->next; alias; alias = alias->next)
  388.             fprintf(f, ", %s", alias->name);
  389.         putc('\n', f);
  390.     }
  391.     return privates;
  392. }
  393.  
  394. int
  395. formatprint(f, table, nelem, type, lhs, cost)
  396.     FILE *f;
  397.     node **table;
  398.     char *lhs, *cost;
  399. {    int i, didprint;
  400.     char buf[128], *bptr;
  401.  
  402.     sprintf(buf, "%s%s{" /*}*/, lhs, type == PRIVATE ? " " : " = ");
  403.     bptr = buf + strlen(buf);
  404.  
  405.     didprint = 0;
  406.     for (i = 0; i < nelem; i++) {
  407.         if (type == PRIVATE && ! (table[i]->flag & COLLISION))
  408.             continue;
  409.         else if (type == HOSTS && ISADOMAIN(table[i]) )
  410.             continue;
  411.         else if (type == SUBDOMAINS && ! ISADOMAIN(table[i]) )
  412.             continue;
  413.  
  414.         if ((bptr - buf) + strlen(table[i]->name) > 69) {
  415.             *bptr = 0;
  416.             fprintf(f, "%s\n ", buf);    /* continuation */
  417.             bptr = buf;
  418.         }
  419.         sprintf(bptr, "%s, ", table[i]->name);
  420.         bptr += strlen(bptr);
  421.         didprint++;
  422.     }
  423.     *bptr = 0;
  424.  
  425.     if (didprint) {
  426.         fprintf(f, /*{*/ "%s}", buf);
  427.         if (type != PRIVATE)
  428.             fprintf(f, "(%s)", cost);
  429.         putc('\n', f);
  430.     }
  431.     return didprint;
  432. }
  433.  
  434. FILE *                
  435. mkfile(n)
  436.     node *n;
  437. {    node *parent;
  438.     char *bptr;
  439.     FILE *f;
  440.  
  441.     /* build up the domain name in Fname[] */
  442.     bptr = Fstart;
  443.     if (n == Top)
  444.         strcpy(bptr, n->name);
  445.     else {
  446.         strcpy(bptr, n->name + 1);    /* skip leading dot */
  447.         bptr = bptr + strlen(bptr);
  448.         parent = n->parent;
  449.         while (ISADOMAIN(parent)) {
  450.             strcpy(bptr, parent->name);
  451.             bptr += strlen(bptr);
  452.             parent = parent->parent;
  453.         }
  454.         *bptr = 0;
  455.     }
  456.  
  457.     /* get a stream descriptor */
  458.     if (Fflag) {
  459.         printf("# %s\n", Fstart);
  460.         f = stdout;
  461.     } else {
  462. #ifndef BSD
  463.         Fstart[14] = 0;
  464. #endif
  465.         if ((f = fopen(Fname, "w")) == 0) {
  466.             perror(Fname);
  467.             exit(1);
  468.         }
  469.     }
  470.     if (n == Top)
  471.         fprintf(f, "private {%s}\ndead {%s}\n", Top->name, Top->name);
  472.     return f;
  473. }
  474.  
  475. /* map to lower case in place.  return parameter for convenience */
  476. char *
  477. lowercase(buf)
  478.     char *buf;
  479. {    char *str;
  480.  
  481.     for (str = buf ; *str; str++)
  482.         if (isupper(*str))
  483.             *str -= 'A' - 'a';
  484.     return buf;
  485. }
  486.  
  487. /* get the interesting aliases, attach to n->alias */
  488. makealiases(n, line)
  489.     node *n;
  490.     char *line;
  491. {    char *next, *dot;
  492.     node *a;
  493.  
  494.     if (line == 0 || *line == 0)
  495.         return;
  496.  
  497.     for ( ; line; line = next) {
  498.         next = strchr(line, ',');
  499.         if (next)
  500.             *next++ = 0;
  501.         if ((dot = strchr(line, '.')) == 0)
  502.             continue;
  503.         if (strcmp(dot, DotArpa) != 0)
  504.             continue;
  505.         *dot = 0;
  506.  
  507.         if (strcmp(n->name, line) == 0)
  508.             continue;
  509.  
  510.         a = newnode();
  511.         a->name = strsave(line);
  512.         a->next = n->alias;
  513.         n->alias = a;
  514.     }
  515. }
  516.  
  517. /* make unique domain names */
  518. merge()
  519. {    register node *n;
  520.  
  521.     for (n = Top->child; n; n = n->next)
  522.         make_children_unique(n);
  523. }
  524.  
  525. /*
  526.  * another recursive tree walk, this time to make unique domain
  527.  * components.
  528.  *
  529.  * for domains like cc.umich.edu and cc.berkeley.edu, it's inaccurate
  530.  * to describe cc as a member of umich.edu or berkeley.edu.  (i.e., the
  531.  * lousy scoping rules for privates don't permit a clean syntax.)  so.
  532.  *
  533.  * to prevent confusion, tack on to any such domain name its parent domain
  534.  * and promote it in the tree.  e.g., make cc.umich and cc.berkeley
  535.  * subdomains of edu.
  536.  */
  537.  
  538. make_children_unique(parent)
  539.     node *parent;
  540. {    node *prev, *child, *next;
  541.     char buf[BUFSIZ];
  542.  
  543.     prev = 0;
  544.     for (child = parent->child; child; child = next) {
  545.         next = child->next;
  546.  
  547.         /* skip hosts */
  548.         if (!ISADOMAIN(child)) {
  549.             prev = child;
  550.             continue;
  551.         }
  552.  
  553.         /*
  554.          * promote non-unique domain, or any domain with a
  555.          * gateway.  (the latter get promoted all the way to
  556.          * top-level.)
  557.          */
  558.         if ((child->flag & COLLISION) == 0 && child->gateway == 0) {
  559.             /*
  560.              * uninteresting domain.  make its children
  561.              * unique and bump prev.
  562.              */
  563.             make_children_unique(child);
  564.             prev = child;
  565.             continue;
  566.         }
  567.  
  568.         /*
  569.          * gateway or dup domain name found.  don't bump
  570.          * prev: this node is moving up the tree.
  571.          */
  572.  
  573.         /* qualify child domain name */
  574.         sprintf(buf, "%s%s", child->name, parent->name);
  575.         cfree(child->name);
  576.         child->name = strsave(buf);
  577.  
  578.         /* unlink child out of sibling chain */
  579.         if (prev)
  580.             prev->next = child->next;
  581.         else
  582.             parent->child = child->next;
  583.  
  584.         /* link child in as peer of parent */
  585.         child->next = parent->next;
  586.         parent->next = child;
  587.         child->parent = parent->parent;
  588.  
  589.         /*
  590.          * reset collision flag; may promote again on
  591.          * return to caller.
  592.          */
  593.         child->flag &= ~COLLISION;
  594.         hash(child);
  595.     }
  596. }
  597.  
  598. /* another recursive tree walk, this time to set the COLLISION bit. */
  599. setuniqflag(n)
  600.     node *n;
  601. {    node *child, *alias;
  602.  
  603.     /* mark this node in the hash table */
  604.     hash(n);
  605.     /* mark the aliases of this node */
  606.     for (alias = n->alias; alias; alias = alias->next)
  607.         hash(alias);
  608.     /* recursively mark this node's children */
  609.     for (child = n->child; child; child = child->next)
  610.         setuniqflag(child);
  611. }
  612.  
  613. #define NHASH 8191        /* must be prime */
  614. node *Htable[NHASH];        /* hash table */
  615.  
  616. hash(n)
  617.     node *n;
  618. {    node **bucket, *b;
  619.  
  620.     bucket = Htable + (fold(n->name) % NHASH);
  621.     for (b = *bucket; b; b = b->bucket)
  622.         if (strcmp(n->name, b->name) == 0) {
  623.             b->flag |= COLLISION;
  624.             n->flag |= COLLISION;
  625.             return;
  626.         }
  627.  
  628.     n->bucket = *bucket;
  629.     *bucket = n;
  630. }
  631.  
  632. /* stolen from pathalias:addnode.c, q.v. */
  633. #define POLY    0x48000000        /* 31-bit polynomial */
  634. long CrcTable[128];
  635.  
  636. void
  637. crcinit()
  638. {    register int i,j;
  639.     register long sum;
  640.  
  641.     for (i = 0; i < 128; i++) {
  642.         sum = 0;
  643.         for (j = 7-1; j >= 0; --j)
  644.             if (i & (1 << j))
  645.                 sum ^= POLY >> j;
  646.         CrcTable[i] = sum;
  647.     }
  648. }
  649.  
  650. long
  651. fold(s)
  652.     register char *s;
  653. {    register long sum = 0;
  654.     register int c;
  655.  
  656.     while (c = *s++)
  657.         sum = (sum >> 7) ^ CrcTable[(sum ^ c) & 0x7f];
  658.     return sum;
  659. }
  660.  
  661. hashanalyze()
  662. {    int nodecount = 0, maxlen = 0, len, i, probes = 0;
  663.     node *n;
  664.  
  665.     if (!Vflag)
  666.         return;
  667.  
  668.     for (i = 0; i < NHASH; i++) {
  669.         len = 0;
  670.         for (n = Htable[i]; n; n = n->bucket) {
  671.             len++;
  672.             probes += len;
  673.         }
  674.         nodecount += len;
  675.         if (len > maxlen)
  676.             maxlen = len;
  677.     }
  678.     fprintf(stderr,
  679.       "load = %2.2f, probes/access = %2.2f, %d nodes, max chain is %d\n",
  680.       (double) nodecount / (double) NHASH,
  681.       (double) probes / (double) nodecount, nodecount, maxlen);
  682. }
  683.