Return to addnode.c CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / pathalias

Annotation of 43BSD/contrib/pathalias/addnode.c, revision 1.1

1.1     ! root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.