home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume12 / pathalias9 / part02 / addnode.c next >
Encoding:
C/C++ Source or Header  |  1987-10-08  |  8.3 KB  |  372 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)addnode.c    9.1 87/10/04";
  4. #endif
  5.  
  6. #include "def.h"
  7.  
  8. /* exports */
  9. node *addnode(), *addprivate();
  10. void alias(), hashanalyze(), fixprivate(), penalize();
  11. node **Table;                /* hash table ^ priority queue */
  12. long Tabsize;                /* size of Table */    
  13.  
  14. /* imports */
  15. extern link *addlink();
  16. extern node *newnode(), **newtable();
  17. extern char *strsave();
  18. extern int Iflag, Tflag, Vflag;
  19. extern node **Table;
  20. extern long Ncount, Tabsize;
  21. extern char **Argv;
  22. extern void atrace(), die();
  23.  
  24. /* privates */
  25. STATIC void crcinit(), rehash(), lowercase();
  26. STATIC long fold();
  27. STATIC long hash();
  28. STATIC node *isprivate();
  29. static node *Private;    /* list of private nodes in current input file */
  30. /*
  31.  * these numbers are chosen because:
  32.  *    -> they are prime,
  33.  *    -> they are monotonic increasing,
  34.  *    -> each is a tad smaller than a multiple of 1024,
  35.  *    -> they form a fibonacci sequence (almost).
  36.  * the first point yields good hash functions, the second is used for the
  37.  * standard re-hashing implementation of open addressing, the third
  38.  * optimizes for quirks in some mallocs i have seen, and the fourth simply
  39.  * appeals to me.
  40.  */
  41. static long Primes[] = {
  42.     1021, 2039, 3067, 5113, 8179, 13309, 21499, 34807, 56311, 0
  43. };
  44.  
  45. static int    Tabindex;
  46. static long    Tab128;        /* Tabsize * 128 */
  47.  
  48. node    *
  49. addnode(name)
  50.     register char *name;
  51. {    register long i;
  52.     register node *n;
  53.  
  54.     if (Iflag)
  55.         lowercase(name);
  56.  
  57.     /* is it a private host? */
  58.     n = isprivate(name);
  59.     if (n)
  60.         return n;
  61.  
  62.     i = hash(name, 0);
  63.     if (Table[i]) 
  64.         return Table[i];
  65.  
  66.     n = newnode();
  67.     n->n_name = strsave(name);
  68.     Table[i] = n;
  69.     n->n_tloc = i;    /* essentially a back link to the table */
  70.  
  71.     return n;
  72. }
  73.  
  74. void
  75. alias(n1, n2)
  76.     node *n1, *n2;
  77. {
  78.     link    *l;
  79.  
  80.     if (ISADOMAIN(n1) && ISADOMAIN(n2)) {
  81.         fprintf(stderr, "%s: domain alias %s = %s is illegal\n", Argv[0], n1->n_name, n2->n_name);
  82.         return;
  83.     }
  84.     l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
  85.     l->l_flag |= LALIAS;
  86.     l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
  87.     l->l_flag |= LALIAS;
  88.     if (Tflag)
  89.         atrace(n1, n2);
  90. }
  91.  
  92. /*
  93.  * fold a string into a long int.  31 bit crc (from andrew appel).
  94.  * the crc table is computed at run time by crcinit() -- we could
  95.  * precompute, but it takes 1 clock tick on a 750.
  96.  *
  97.  * This fast table calculation works only if POLY is a prime polynomial
  98.  * in the field of integers modulo 2.  Since the coefficients of a
  99.  * 32-bit polynomail won't fit in a 32-bit word, the high-order bit is
  100.  * implicit.  IT MUST ALSO BE THE CASE that the coefficients of orders
  101.  * 31 down to 25 are zero.  Happily, we have candidates, from
  102.  * E. J.  Watson, "Primitive Polynomials (Mod 2)", Math. Comp. 16 (1962):
  103.  *    x^32 + x^7 + x^5 + x^3 + x^2 + x^1 + x^0
  104.  *    x^31 + x^3 + x^0
  105.  *
  106.  * We reverse the bits to get:
  107.  *    111101010000000000000000000000001 but drop the last 1
  108.  *         f   5   0   0   0   0   0   0
  109.  *    010010000000000000000000000000001 ditto, for 31-bit crc
  110.  *       4   8   0   0   0   0   0   0
  111.  */
  112.  
  113. #define POLY32 0xf5000000    /* 32-bit polynomial */
  114. #define POLY31 0x48000000    /* 31-bit polynomial */
  115. #define POLY POLY31    /* use 31-bit to avoid sign problems */
  116.  
  117. static long CrcTable[128];
  118.  
  119. STATIC void
  120. crcinit()
  121. {    register int i,j;
  122.     register long sum;
  123.  
  124.     for (i = 0; i < 128; i++) {
  125.         sum = 0;
  126.         for (j = 7-1; j >= 0; --j)
  127.             if (i & (1 << j))
  128.                 sum ^= POLY >> j;
  129.         CrcTable[i] = sum;
  130.     }
  131. }
  132.  
  133. STATIC long
  134. fold(s)
  135.     register char *s;
  136. {    register long sum = 0;
  137.     register int c;
  138.  
  139.     while (c = *s++)
  140.         sum = (sum >> 7) ^ CrcTable[(sum ^ c) & 0x7f];
  141.     return sum;
  142. }
  143.  
  144.  
  145. #define HASH1(n) ((n) % Tabsize);
  146. #define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2)))    /* sedgewick */
  147.  
  148. /*
  149.  * when alpha is 0.79, there should be 2 probes per access (gonnet).
  150.  * use long constant to force promotion.  Tab128 biases HIGHWATER by
  151.  * 128/100 for reduction in strength in isfull().
  152.  */
  153. #define HIGHWATER    79L
  154. #define isfull(n)    ((n) * 128 >= Tab128)
  155.     
  156. STATIC long
  157. hash(name, unique)
  158.     char *name;
  159. {    register long probe;
  160.     register long hash2;
  161.     register node *n;
  162.  
  163.     if (isfull(Ncount)) {
  164.         if (Tabsize == 0) {        /* first time */
  165.             crcinit();
  166.             Tabindex = 0;
  167.             Tabsize = Primes[0];
  168.             Table = newtable(Tabsize);
  169.             Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
  170.         } else
  171.             rehash();        /* more, more! */
  172.     }
  173.  
  174.     probe = fold(name);
  175.     hash2 = HASH2(probe);
  176.     probe = HASH1(probe);
  177.  
  178.     /*
  179.      * probe the hash table.
  180.      * if unique is set, we require a fresh slot.
  181.      * otherwise, use double hashing to find either
  182.      *  (1) an empty slot, or
  183.      *  (2) a non-private copy of this host name
  184.      */
  185.     while ((n = Table[probe]) != 0) {
  186.         if (unique)
  187.             goto skip;
  188.         if (n->n_flag & ISPRIVATE)
  189.             goto skip;
  190.         if (strcmp(n->n_name, name) == 0)
  191.             break;            /* this is it! */
  192. skip:
  193.         probe -= hash2;
  194.         if (probe < 0)
  195.             probe += Tabsize;
  196.     }
  197.     return probe;
  198. }
  199.  
  200. STATIC void
  201. rehash()
  202. {    register node **otable, **optr;
  203.     register long probe;
  204.     long osize;
  205.  
  206. #ifdef DEBUG
  207.     hashanalyze();
  208. #endif
  209.     optr = Table + Tabsize - 1;    /* ptr to last */
  210.     otable = Table;
  211.     osize = Tabsize;
  212.     Tabsize = Primes[++Tabindex];
  213.     if (Tabsize == 0)
  214.         die("too many hosts");    /* need more prime numbers */
  215.     vprintf(stderr, "rehash into %d\n", Tabsize);
  216.     Table = newtable(Tabsize);
  217.     Tab128 = (HIGHWATER * Tabsize * 128L)/100L;
  218.  
  219.     do {
  220.         if (*optr == 0)
  221.             continue;    /* empty slot in old table */
  222.         probe = hash((*optr)->n_name, (int) ((*optr)->n_flag & ISPRIVATE));
  223.         if (Table[probe] != 0)
  224.             die("rehash error");
  225.         Table[probe] = *optr;
  226.         (*optr)->n_tloc = probe;
  227.     } while (optr-- > otable);
  228.     freetable(otable, osize);
  229. }
  230.  
  231. void
  232. hashanalyze()
  233. {     long    probe, hash2;
  234.     int    count, i, collision[8];
  235.     int    longest = 0, total = 0, slots = 0, longprobe = 0;
  236.     int    nslots = sizeof(collision)/sizeof(collision[0]);
  237.  
  238.     if (!Vflag)
  239.         return;
  240.  
  241.     strclear((char *) collision, sizeof(collision));
  242.     for (i = 0; i < Tabsize; i++) {
  243.         if (Table[i] == 0)
  244.             continue;
  245.         /* private hosts too hard to account for ... */
  246.         if (Table[i]->n_flag & ISPRIVATE)
  247.             continue;
  248.         count = 1;
  249.         probe = fold(Table[i]->n_name);
  250.         /* don't change the order of the next two lines */
  251.         hash2 = HASH2(probe);
  252.         probe = HASH1(probe);
  253.         /* thank you! */
  254.         while (Table[probe] != 0
  255.             && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
  256.             count++;
  257.             probe -= hash2;
  258.             if (probe < 0)
  259.                 probe += Tabsize;
  260.         }
  261.         if (Table[probe] == 0)
  262.             die("impossible hash error");
  263.         
  264.         total += count;
  265.         slots++;
  266.         if (count > longest) {
  267.             longest = count;
  268.             longprobe = i;
  269.         }
  270.         if (count >= nslots)
  271.             count = 0;
  272.         collision[count]++;
  273.     }
  274.     for (i = 1; i < nslots; i++)
  275.         if (collision[i])
  276.             fprintf(stderr, "%d chains: %d (%ld%%)\n",
  277.                 i, collision[i], (collision[i] * 100L)/ slots);
  278.         if (collision[0])
  279.             fprintf(stderr, "> %d chains: %d (%ld%%)\n",
  280.                 nslots - 1, collision[0],
  281.                 (collision[0] * 100L)/ slots);
  282.     fprintf(stderr, "%2.2f probes per access, longest chain: %d, %s\n",
  283.         (double) total / slots, longest, Table[longprobe]->n_name);
  284.     if (Vflag < 2)
  285.         return;
  286.     probe = fold(Table[longprobe]->n_name);
  287.     hash2 = HASH2(probe);
  288.     probe = HASH1(probe);
  289.     while (Table[probe] != 0
  290.         && strcmp(Table[probe]->n_name, Table[longprobe]->n_name) != 0) {
  291.         fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
  292.         probe -= hash2;
  293.         if (probe < 0)
  294.             probe += Tabsize;
  295.     }
  296.     fprintf(stderr, "%5d %s\n", probe, Table[probe]->n_name);
  297.     
  298. }
  299.  
  300. /* convert to lower case in place */
  301. STATIC void
  302. lowercase(s)
  303.     register char *s;
  304. {
  305.     do {
  306.         if (isupper(*s))
  307.             *s -= 'A' - 'a';    /* ASCII */
  308.     } while (*s++);
  309. }
  310.  
  311. /*
  312.  * this might need change if privates catch on
  313.  */
  314. STATIC node *
  315. isprivate(name)
  316.     register char *name;
  317. {    register node *n;
  318.  
  319.     for (n = Private; n != 0; n = n->n_private)
  320.         if (strcmp(name, n->n_name) == 0)
  321.             return n;
  322.     return 0;
  323. }
  324.  
  325. void
  326. fixprivate()
  327. {    register node *n, *next;
  328.     register long i;
  329.  
  330.     for (n = Private; n != 0; n = next) {
  331.         n->n_flag |= ISPRIVATE;        /* overkill, but safe */
  332.         i = hash(n->n_name, 1);
  333.         if (Table[i] != 0)
  334.             die("impossible private node error");
  335.     
  336.         Table[i] = n;
  337.         n->n_tloc = i;    /* essentially a back link to the table */
  338.         next = n->n_private;
  339.         n->n_private = 0;    /* clear for later use */
  340.     }
  341.     Private = 0;
  342. }
  343.  
  344. node *
  345. addprivate(name)
  346.     register char *name;
  347. {    register node *n;
  348.  
  349.     if (Iflag)
  350.         lowercase(name);
  351.     if ((n = isprivate(name)) != 0)
  352.         return n;
  353.  
  354.     n = newnode();
  355.     n->n_name = strsave(name);
  356.     n->n_private = Private;
  357.     Private = n;
  358.     return n;
  359. }
  360.  
  361. void
  362. penalize(name, cost)
  363.     char *name;
  364.     Cost cost;
  365. {    node *n;
  366.  
  367.     if (Iflag)
  368.         lowercase(name);
  369.     n = addnode(name);
  370.     n->n_cost += cost;    /* cumulative */
  371. }
  372.