4.3BSD - /usr/src/new/pathalias/addnode.c

   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: }

Defined functions

Defined variables

Defined macros