home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume3 / pathalias2 / part2 / addnode.c < prev    next >
Encoding:
C/C++ Source or Header  |  1986-11-30  |  6.4 KB  |  309 lines
  1. /* pathalias -- by steve bellovin, as told to peter honeyman */
  2. #ifndef lint
  3. static char    *sccsid = "@(#)addnode.c    8.1 (down!honey) 86/01/19";
  4. #endif
  5.  
  6. #include "def.h"
  7.  
  8. extern void    lowercase(), rehash();
  9. extern node    *isprivate();
  10. extern long    hash();
  11.  
  12. /*
  13.  * these numbers are chosen because:
  14.  *    -> they are prime,
  15.  *    -> they are monotonic increasing,
  16.  *    -> each is a tad smaller than a multiple of 1024,
  17.  *    -> they form a fibonacci sequence (almost).
  18.  * the first point yields good hash functions, the second is used for the
  19.  * standard re-hashing implementation of open addressing, the third
  20.  * optimizes for quirks in some mallocs i have seen, and the fourth simply
  21.  * appeals to me.
  22.  */
  23. static int Primes[]    = {
  24. #ifndef SQUANDER
  25.     1021, 2039, 3067, 5113, 8179,
  26. #endif
  27.     13309, 21499, 0
  28. };
  29.  
  30. static int    Tabindex = -1;
  31. static int    Collision;    /* mark host name collisions in hash() */
  32.  
  33. node    *
  34. addnode(name)
  35. register char    *name;
  36. {
  37.     register long    i;
  38.     register node    *n;
  39.  
  40.     if (Iflag)
  41.         lowercase(name);
  42.  
  43.     /* is it a private host? */
  44.     n = isprivate(name);
  45.     if (n)
  46.         return(n);
  47.  
  48.     i = hash(name, 0);
  49.     if (Table[i]) 
  50.         return(Table[i]);
  51.  
  52.     n = newnode();
  53.     n->n_name = strsave(name);
  54.     Table[i] = n;
  55.     n->n_tloc = i;    /* essentially a back link to the table */
  56.     if (Collision)
  57.         n->n_flag |= COLLISION;    /* name collision with private host */
  58.  
  59.     return(n);
  60. }
  61.  
  62. alias(n1, n2)
  63. node    *n1, *n2;
  64. {
  65.     link    *l;
  66.     extern link *addlink();
  67.  
  68.     l = addlink(n1, n2, (Cost) 0, DEFNET, DEFDIR);
  69.     l->l_flag |= LALIAS;
  70.     l = addlink(n2, n1, (Cost) 0, DEFNET, DEFDIR);
  71.     l->l_flag |= LALIAS;
  72.     if (Tflag)
  73.         atrace(n1, n2);
  74. }
  75.  
  76. /*
  77.  * fold a string into a long int.  this algorithm ignores all but the last
  78.  * eight bytes, which affects < 15% of all host names, many of which have
  79.  * common prefixes anyway.
  80.  */
  81. STATIC long
  82. fold(str)
  83. register char    *str;
  84. {
  85.     register long    sum;
  86.  
  87.     sum = *str++;
  88.     while (*str) {
  89.         sum <<= 4;
  90.         sum += *str++;
  91.     }
  92.     if (sum < 0) 
  93.         sum = -sum;
  94.     return(sum);
  95. }
  96.  
  97. #define HASH1(n) ((n) % Tabsize);
  98. #define HASH2(n) (Tabsize - 2 - ((n) % (Tabsize-2)))    /* princeton!rs */
  99.  
  100. /*
  101.  * with a 0.75 high water mark, probes per access should be 1.84.
  102.  * use long constant to force promotion.
  103.  */
  104. #define HIGHWATER    75L
  105. #define isfull(n, size)    ((n) > ((size) * HIGHWATER) / 100)
  106.  
  107. STATIC long
  108. hash(name, unique)
  109. char    *name;
  110. {
  111.     register long    probe, hash2;
  112.     register node    *n;
  113.  
  114.     if (Tabindex < 0) {            /* first time */
  115.         Tabindex = 0;
  116.         Tabsize = Primes[0];
  117.         Table = newtable(Tabsize);
  118.     } else if (isfull(Ncount, Tabsize))
  119.         rehash();            /* more, more! */
  120.                 
  121.     probe = fold(name);
  122.     /* don't change the order of the next two lines */
  123.     hash2 = HASH2(probe);
  124.     probe = HASH1(probe);
  125.     /* thank you! */
  126.  
  127.     /*
  128.      * probe the hash table.
  129.      * if unique is set, we require a fresh slot.
  130.      * otherwise, use double hashing to find either
  131.      *  (1) an empty slot, or
  132.      *  (2) a non-private copy of this host name
  133.      *
  134.      * as a side effect, if we notice a collision with a private host
  135.      * we mark the other so that it is skipped at output time.
  136.      */
  137.     Collision = 0;
  138.     while ((n = Table[probe]) != 0) {
  139.         if (strcmp(n->n_name, name) == 0) {
  140.             if (unique)
  141.                 n->n_flag |= COLLISION;
  142.             else if (n->n_flag & ISPRIVATE)
  143.                 Collision++;
  144.             else
  145.                 break;    /* this is it! */
  146.         }
  147.         probe -= hash2;
  148.         if (probe < 0)
  149.             probe += Tabsize;
  150.     }
  151.     return(probe);
  152. }
  153.  
  154. STATIC void
  155. rehash()
  156. {
  157.     register node    **otable, **optr;
  158.     register long    probe;
  159.     long    osize;
  160.  
  161. #ifdef DEBUG
  162.     hashanalyze();
  163. #endif
  164.     optr = Table + Tabsize - 1;    /* ptr to last */
  165.     otable = Table;
  166.     osize = Tabsize;
  167.     Tabsize = Primes[++Tabindex];
  168.     if (Tabsize == 0) {    /* need more prime numbers */
  169.         fprintf(stderr, "%s: > %d hosts\n", ProgName, Primes[Tabindex-1]);
  170.         badmagic(1);
  171.     }
  172.     vprintf(stderr, "rehash into %d\n", Tabsize);
  173.     Table = newtable(Tabsize);
  174.  
  175.     do {
  176.         if (*optr == 0)
  177.             continue;    /* empty slot in old table */
  178.         probe = hash((*optr)->n_name, (*optr)->n_flag & ISPRIVATE);
  179.         if (Table[probe] != 0) {
  180.             fprintf(stderr, "%s: rehash error\n", ProgName);
  181.             badmagic(1);
  182.         }
  183.         Table[probe] = *optr;
  184.         (*optr)->n_tloc = probe;
  185.     } while (optr-- > otable);
  186.     freetable(otable, osize);
  187. }
  188.  
  189. hashanalyze()
  190. {
  191.     long    probe, hash2;
  192.     int    count, i, collision[8];
  193.     int    longest = 0, total = 0, slots = 0;
  194.     int    nslots = sizeof(collision)/sizeof(collision[0]);
  195.  
  196.     if (!Vflag)
  197.         return;
  198.  
  199.     strclear((char *) collision, sizeof(collision));
  200.     for (i = 0; i < Tabsize; i++) {
  201.         if (Table[i] == 0)
  202.             continue;
  203.         /* private hosts too hard to account for ... */
  204.         if (Table[i]->n_flag & ISPRIVATE)
  205.             continue;
  206.         count = 1;
  207.         probe = fold(Table[i]->n_name);
  208.         /* don't change the order of the next two lines */
  209.         hash2 = HASH2(probe);
  210.         probe = HASH1(probe);
  211.         /* thank you! */
  212.         while (Table[probe] != 0
  213.             && strcmp(Table[probe]->n_name, Table[i]->n_name) != 0) {
  214.             count++;
  215.             probe -= hash2;
  216.             if (probe < 0)
  217.                 probe += Tabsize;
  218.         }
  219.         if (Table[probe] == 0) {
  220.             fprintf(stderr, "%s: impossible hash error for %s\n",
  221.                     ProgName, Table[i]->n_name);
  222.             badmagic(1);
  223.         }
  224.         
  225.         total += count;
  226.         slots++;
  227.         if (count > longest)
  228.             longest = count;
  229.         if (count >= nslots)
  230.             count = 0;
  231.         collision[count]++;
  232.     }
  233.     for (i = 1; i < nslots; i++)
  234.         if (collision[i])
  235.             fprintf(stderr, "%d chains: %d (%ld%%)\n",
  236.                 i, collision[i], (collision[i] * 100L)/ slots);
  237.         if (collision[0])
  238.             fprintf(stderr, "> %d chains: %d (%ld%%)\n",
  239.                 nslots - 1, collision[0],
  240.                 (collision[0] * 100L)/ slots);
  241.     fprintf(stderr, "%2.2f probes per access, longest chain: %d\n",
  242.         (double) total / slots, longest);
  243. }
  244.  
  245. STATIC void
  246. lowercase(s)
  247. register char    *s;
  248. {
  249.     do {
  250.         if (isupper(*s))
  251.             *s -= 'A' - 'a';    /* assumes ASCII */
  252.     } while (*s++);
  253. }
  254.  
  255. /*
  256.  * this might have to be recoded for performance if privates catch on
  257.  */
  258. STATIC node    *
  259. isprivate(name)
  260. register char    *name;
  261. {
  262.     register node    *n;
  263.  
  264.     for (n = Private; n != 0; n = n->n_private)
  265.         if (strcmp(name, n->n_name) == 0)
  266.             return(n);
  267.     return(0);
  268. }
  269.  
  270. fixprivate()
  271. {
  272.     register node    *n, *next;
  273.     register long    i;
  274.  
  275.     for (n = Private; n != 0; n = next) {
  276.         n->n_flag |= ISPRIVATE;        /* overkill, but safe */
  277.         i = hash(n->n_name, 1);
  278.         if (Table[i] != 0) {
  279.             fprintf(stderr, "%s: impossible private node error on %s\n",
  280.                 ProgName, n->n_name);
  281.             badmagic(1);
  282.         }
  283.     
  284.         Table[i] = n;
  285.         n->n_tloc = i;    /* essentially a back link to the table */
  286.         next = n->n_private;
  287.         n->n_private = 0;    /* clear for later use */
  288.     }
  289.     Private = 0;
  290. }
  291.  
  292. node    *
  293. addprivate(name)
  294. register char    *name;
  295. {
  296.     register node    *n;
  297.  
  298.     if (Iflag)
  299.         lowercase(name);
  300.     if ((n = isprivate(name)) != 0)
  301.         return(n);
  302.  
  303.     n = newnode();
  304.     n->n_name = strsave(name);
  305.     n->n_private = Private;
  306.     Private = n;
  307.     return(n);
  308. }
  309.