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

Defined functions

Defined variables

Defined macros