/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume3 / pathalias2 / part2

< prev

next >

MacOS 8.1

Win98

DOS

browse contents

view JSON data

view as text

+--------+-------------------------+-------------------------+--------+--------+
|00000000| 53 75 62 6a 65 63 74 3a | 20 4e 65 77 20 70 61 74 |Subject:| New pat|
|00000010| 68 61 6c 69 61 73 2c 20 | 70 61 72 74 20 32 20 6f |halias, |part 2 o|
|00000020| 66 20 32 0a 4e 65 77 73 | 67 72 6f 75 70 73 3a 20 |f 2.News|groups: |
|00000030| 6d 6f 64 2e 73 6f 75 72 | 63 65 73 0a 41 70 70 72 |mod.sour|ces.Appr|
|00000040| 6f 76 65 64 3a 20 6a 70 | 6e 40 70 61 6e 64 61 2e |oved: jp|n@panda.|
|00000050| 55 55 43 50 0a 0a 4d 6f | 64 2e 73 6f 75 72 63 65 |UUCP..Mo|d.source|
|00000060| 73 3a 20 20 56 6f 6c 75 | 6d 65 20 33 2c 20 49 73 |s:  Volu|me 3, Is|
|00000070| 73 75 65 20 39 33 0a 53 | 75 62 6d 69 74 74 65 64 |sue 93.S|ubmitted|
|00000080| 20 62 79 3a 20 70 72 69 | 6e 63 65 74 6f 6e 21 64 | by: pri|nceton!d|
|00000090| 6f 77 6e 21 68 6f 6e 65 | 79 20 28 50 65 74 65 72 |own!hone|y (Peter|
|000000a0| 20 48 6f 6e 65 79 6d 61 | 6e 29 0a 0a 23 21 20 2f | Honeyma|n)..#! /|
|000000b0| 62 69 6e 2f 73 68 0a 23 | 20 54 68 69 73 20 69 73 |bin/sh.#| This is|
|000000c0| 20 61 20 73 68 65 6c 6c | 20 61 72 63 68 69 76 65 | a shell| archive|
|000000d0| 2c 20 6d 65 61 6e 69 6e | 67 3a 0a 23 20 31 2e 20 |, meanin|g:.# 1. |
|000000e0| 52 65 6d 6f 76 65 20 65 | 76 65 72 79 74 68 69 6e |Remove e|verythin|
|000000f0| 67 20 61 62 6f 76 65 20 | 74 68 65 20 23 21 20 2f |g above |the #! /|
|00000100| 62 69 6e 2f 73 68 20 6c | 69 6e 65 2e 0a 23 20 32 |bin/sh l|ine..# 2|
|00000110| 2e 20 53 61 76 65 20 74 | 68 65 20 72 65 73 75 6c |. Save t|he resul|
|00000120| 74 69 6e 67 20 74 65 78 | 74 20 69 6e 20 61 20 66 |ting tex|t in a f|
|00000130| 69 6c 65 2e 0a 23 20 33 | 2e 20 45 78 65 63 75 74 |ile..# 3|. Execut|
|00000140| 65 20 74 68 65 20 66 69 | 6c 65 20 77 69 74 68 20 |e the fi|le with |
|00000150| 2f 62 69 6e 2f 73 68 20 | 28 6e 6f 74 20 63 73 68 |/bin/sh |(not csh|
|00000160| 29 20 74 6f 20 63 72 65 | 61 74 65 20 74 68 65 20 |) to cre|ate the |
|00000170| 66 69 6c 65 73 3a 0a 23 | 09 61 64 64 6c 69 6e 6b |files:.#|.addlink|
|00000180| 2e 63 0a 23 09 61 64 64 | 6e 6f 64 65 2e 63 0a 23 |.c.#.add|node.c.#|
|00000190| 09 65 78 74 65 72 6e 2e | 63 0a 23 09 6c 6f 63 61 |.extern.|c.#.loca|
|000001a0| 6c 2e 63 0a 23 09 6d 61 | 69 6e 2e 63 0a 23 09 6d |l.c.#.ma|in.c.#.m|
|000001b0| 61 6b 65 64 62 2e 63 0a | 23 09 6d 61 70 61 75 78 |akedb.c.|#.mapaux|
|000001c0| 2e 63 0a 23 09 6d 61 70 | 69 74 2e 63 0a 23 09 6d |.c.#.map|it.c.#.m|
|000001d0| 65 6d 2e 63 0a 23 09 70 | 72 69 6e 74 69 74 2e 63 |em.c.#.p|rintit.c|
|000001e0| 0a 23 09 70 61 72 73 65 | 2e 79 0a 23 20 54 68 69 |.#.parse|.y.# Thi|
|000001f0| 73 20 61 72 63 68 69 76 | 65 20 63 72 65 61 74 65 |s archiv|e create|
|00000200| 64 3a 20 57 65 64 20 4a | 61 6e 20 32 32 20 31 38 |d: Wed J|an 22 18|
|00000210| 3a 35 33 3a 31 36 20 31 | 39 38 36 0a 65 78 70 6f |:53:16 1|986.expo|
|00000220| 72 74 20 50 41 54 48 3b | 20 50 41 54 48 3d 2f 62 |rt PATH;| PATH=/b|
|00000230| 69 6e 3a 24 50 41 54 48 | 0a 65 63 68 6f 20 73 68 |in:$PATH|.echo sh|
|00000240| 61 72 3a 20 65 78 74 72 | 61 63 74 69 6e 67 20 22 |ar: extr|acting "|
|00000250| 27 61 64 64 6c 69 6e 6b | 2e 63 27 22 20 27 28 33 |'addlink|.c'" '(3|
|00000260| 33 35 38 20 63 68 61 72 | 61 63 74 65 72 73 29 27 |358 char|acters)'|
|00000270| 0a 69 66 20 74 65 73 74 | 20 2d 66 20 27 61 64 64 |.if test| -f 'add|
|00000280| 6c 69 6e 6b 2e 63 27 0a | 74 68 65 6e 0a 09 65 63 |link.c'.|then..ec|
|00000290| 68 6f 20 73 68 61 72 3a | 20 77 69 6c 6c 20 6e 6f |ho shar:| will no|
|000002a0| 74 20 6f 76 65 72 2d 77 | 72 69 74 65 20 65 78 69 |t over-w|rite exi|
|000002b0| 73 74 69 6e 67 20 66 69 | 6c 65 20 22 27 61 64 64 |sting fi|le "'add|
|000002c0| 6c 69 6e 6b 2e 63 27 22 | 0a 65 6c 73 65 0a 63 61 |link.c'"|.else.ca|
|000002d0| 74 20 3c 3c 20 5c 53 48 | 41 52 5f 45 4f 46 20 3e |t << \SH|AR_EOF >|
|000002e0| 20 27 61 64 64 6c 69 6e | 6b 2e 63 27 0a 2f 2a 20 | 'addlin|k.c'./* |
|000002f0| 70 61 74 68 61 6c 69 61 | 73 20 2d 2d 20 62 79 20 |pathalia|s -- by |
|00000300| 73 74 65 76 65 20 62 65 | 6c 6c 6f 76 69 6e 2c 20 |steve be|llovin, |
|00000310| 61 73 20 74 6f 6c 64 20 | 74 6f 20 70 65 74 65 72 |as told |to peter|
|00000320| 20 68 6f 6e 65 79 6d 61 | 6e 20 2a 2f 0a 23 69 66 | honeyma|n */.#if|
|00000330| 6e 64 65 66 20 6c 69 6e | 74 0a 73 74 61 74 69 63 |ndef lin|t.static|
|00000340| 20 63 68 61 72 09 2a 73 | 63 63 73 69 64 20 3d 20 | char.*s|ccsid = |
|00000350| 22 40 28 23 29 61 64 64 | 6c 69 6e 6b 2e 63 09 38 |"@(#)add|link.c.8|
|00000360| 2e 31 20 28 64 6f 77 6e | 21 68 6f 6e 65 79 29 20 |.1 (down|!honey) |
|00000370| 38 36 2f 30 31 2f 31 39 | 22 3b 0a 23 65 6e 64 69 |86/01/19|";.#endi|
|00000380| 66 20 6c 69 6e 74 0a 0a | 23 69 6e 63 6c 75 64 65 |f lint..|#include|
|00000390| 20 22 64 65 66 2e 68 22 | 0a 0a 73 74 61 74 69 63 | "def.h"|..static|
|000003a0| 20 6c 69 6e 6b 09 2a 54 | 72 61 63 65 5b 4e 54 52 | link.*T|race[NTR|
|000003b0| 41 43 45 5d 3b 0a 73 74 | 61 74 69 63 20 69 6e 74 |ACE];.st|atic int|
|000003c0| 09 54 72 61 63 65 63 6f | 75 6e 74 3b 0a 0a 6c 69 |.Traceco|unt;..li|
|000003d0| 6e 6b 09 2a 0a 61 64 64 | 6c 69 6e 6b 28 66 72 6f |nk.*.add|link(fro|
|000003e0| 6d 2c 20 74 6f 2c 20 63 | 6f 73 74 2c 20 6e 65 74 |m, to, c|ost, net|
|000003f0| 63 68 61 72 2c 20 6e 65 | 74 64 69 72 29 0a 6e 6f |char, ne|tdir).no|
|00000400| 64 65 09 2a 66 72 6f 6d | 3b 0a 72 65 67 69 73 74 |de.*from|;.regist|
|00000410| 65 72 20 6e 6f 64 65 09 | 2a 74 6f 3b 0a 43 6f 73 |er node.|*to;.Cos|
|00000420| 74 09 63 6f 73 74 3b 0a | 63 68 61 72 09 6e 65 74 |t.cost;.|char.net|
|00000430| 63 68 61 72 3b 0a 63 68 | 61 72 09 6e 65 74 64 69 |char;.ch|ar.netdi|
|00000440| 72 3b 0a 7b 0a 09 72 65 | 67 69 73 74 65 72 20 6c |r;.{..re|gister l|
|00000450| 69 6e 6b 09 2a 6c 2c 20 | 2a 70 72 65 76 20 3d 20 |ink.*l, |*prev = |
|00000460| 30 3b 0a 0a 09 69 66 20 | 28 54 66 6c 61 67 29 0a |0;...if |(Tflag).|
|00000470| 09 09 6c 74 72 61 63 65 | 28 66 72 6f 6d 2c 20 74 |..ltrace|(from, t|
|00000480| 6f 2c 20 63 6f 73 74 2c | 20 6e 65 74 63 68 61 72 |o, cost,| netchar|
|00000490| 2c 20 6e 65 74 64 69 72 | 29 3b 0a 09 2f 2a 20 6d |, netdir|);../* m|
|000004a0| 61 69 6e 74 61 69 6e 20 | 75 6e 69 71 75 65 6e 65 |aintain |uniquene|
|000004b0| 73 73 20 66 6f 72 20 64 | 65 61 64 20 6c 69 6e 6b |ss for d|ead link|
|000004c0| 73 20 28 6f 6e 6c 79 29 | 20 2a 2f 0a 09 66 6f 72 |s (only)| */..for|
|000004d0| 20 28 6c 20 3d 20 66 72 | 6f 6d 2d 3e 6e 5f 6c 69 | (l = fr|om->n_li|
|000004e0| 6e 6b 3b 20 6c 20 26 26 | 20 6c 2d 3e 6c 5f 66 6c |nk; l &&| l->l_fl|
|000004f0| 61 67 20 26 20 4c 44 45 | 41 44 3b 20 6c 20 3d 20 |ag & LDE|AD; l = |
|00000500| 6c 2d 3e 6c 5f 6e 65 78 | 74 29 20 7b 0a 09 09 69 |l->l_nex|t) {...i|
|00000510| 66 20 28 74 6f 20 3d 3d | 20 6c 2d 3e 6c 5f 74 6f |f (to ==| l->l_to|
|00000520| 29 20 7b 0a 09 09 09 2f | 2a 20 77 68 61 74 20 74 |) {..../|* what t|
|00000530| 68 65 20 68 65 6c 6c 2c | 20 75 73 65 20 63 68 65 |he hell,| use che|
|00000540| 61 70 65 72 20 63 6f 73 | 74 20 2a 2f 0a 09 09 09 |aper cos|t */....|
|00000550| 69 66 20 28 63 6f 73 74 | 20 3c 20 6c 2d 3e 6c 5f |if (cost| < l->l_|
|00000560| 63 6f 73 74 29 20 7b 0a | 09 09 09 09 6c 2d 3e 6c |cost) {.|....l->l|
|00000570| 5f 63 6f 73 74 20 3d 20 | 63 6f 73 74 3b 0a 09 09 |_cost = |cost;...|
|00000580| 09 09 6e 65 74 62 69 74 | 73 28 6c 2c 20 6e 65 74 |..netbit|s(l, net|
|00000590| 63 68 61 72 2c 20 6e 65 | 74 64 69 72 29 3b 0a 09 |char, ne|tdir);..|
|000005a0| 09 09 7d 0a 09 09 09 72 | 65 74 75 72 6e 28 6c 29 |..}....r|eturn(l)|
|000005b0| 3b 0a 09 09 7d 0a 09 09 | 70 72 65 76 20 3d 20 6c |;...}...|prev = l|
|000005c0| 3b 0a 09 7d 0a 0a 09 2f | 2a 20 61 6c 6c 6f 63 61 |;..}.../|* alloca|
|000005d0| 74 65 20 61 6e 64 20 6c | 69 6e 6b 20 69 6e 20 74 |te and l|ink in t|
|000005e0| 68 65 20 6e 65 77 20 6c | 69 6e 6b 20 73 74 72 75 |he new l|ink stru|
|000005f0| 63 74 20 2a 2f 0a 09 6c | 20 3d 20 6e 65 77 6c 69 |ct */..l| = newli|
|00000600| 6e 6b 28 29 3b 0a 09 69 | 66 20 28 63 6f 73 74 20 |nk();..i|f (cost |
|00000610| 21 3d 20 49 4e 46 29 09 | 2f 2a 20 69 67 6e 6f 72 |!= INF).|/* ignor|
|00000620| 65 20 62 61 63 6b 20 6c | 69 6e 6b 73 20 2a 2f 0a |e back l|inks */.|
|00000630| 09 09 4c 63 6f 75 6e 74 | 2b 2b 3b 0a 09 69 66 20 |..Lcount|++;..if |
|00000640| 28 70 72 65 76 29 20 7b | 0a 09 09 6c 2d 3e 6c 5f |(prev) {|...l->l_|
|00000650| 6e 65 78 74 20 3d 20 70 | 72 65 76 2d 3e 6c 5f 6e |next = p|rev->l_n|
|00000660| 65 78 74 3b 0a 09 09 70 | 72 65 76 2d 3e 6c 5f 6e |ext;...p|rev->l_n|
|00000670| 65 78 74 20 3d 20 6c 3b | 0a 09 7d 20 65 6c 73 65 |ext = l;|..} else|
|00000680| 20 7b 0a 09 09 6c 2d 3e | 6c 5f 6e 65 78 74 20 3d | {...l->|l_next =|
|00000690| 20 66 72 6f 6d 2d 3e 6e | 5f 6c 69 6e 6b 3b 0a 09 | from->n|_link;..|
|000006a0| 09 66 72 6f 6d 2d 3e 6e | 5f 6c 69 6e 6b 20 3d 20 |.from->n|_link = |
|000006b0| 6c 3b 0a 09 7d 0a 0a 09 | 6c 2d 3e 6c 5f 74 6f 20 |l;..}...|l->l_to |
|000006c0| 3d 20 74 6f 3b 0a 09 6c | 2d 3e 6c 5f 63 6f 73 74 |= to;..l|->l_cost|
|000006d0| 20 3d 20 63 6f 73 74 3b | 0a 09 69 66 20 28 6e 65 | = cost;|..if (ne|
|000006e0| 74 63 68 61 72 20 3d 3d | 20 30 29 20 7b 0a 09 09 |tchar ==| 0) {...|
|000006f0| 6e 65 74 63 68 61 72 20 | 3d 20 44 45 46 4e 45 54 |netchar |= DEFNET|
|00000700| 3b 0a 09 09 6e 65 74 64 | 69 72 20 3d 20 44 45 46 |;...netd|ir = DEF|
|00000710| 44 49 52 3b 0a 09 7d 0a | 09 6e 65 74 62 69 74 73 |DIR;..}.|.netbits|
|00000720| 28 6c 2c 20 6e 65 74 63 | 68 61 72 2c 20 6e 65 74 |(l, netc|har, net|
|00000730| 64 69 72 29 3b 0a 0a 09 | 72 65 74 75 72 6e 28 6c |dir);...|return(l|
|00000740| 29 3b 0a 7d 0a 0a 6c 69 | 6e 6b 09 2a 0a 61 64 64 |);.}..li|nk.*.add|
|00000750| 67 61 74 65 77 61 79 28 | 66 72 6f 6d 2c 20 74 6f |gateway(|from, to|
|00000760| 2c 20 63 6f 73 74 2c 20 | 6e 65 74 63 68 61 72 2c |, cost, |netchar,|
|00000770| 20 6e 65 74 64 69 72 29 | 0a 6e 6f 64 65 09 2a 66 | netdir)|.node.*f|
|00000780| 72 6f 6d 3b 0a 6e 6f 64 | 65 09 2a 74 6f 3b 0a 43 |rom;.nod|e.*to;.C|
|00000790| 6f 73 74 09 63 6f 73 74 | 3b 0a 63 68 61 72 09 6e |ost.cost|;.char.n|
|000007a0| 65 74 63 68 61 72 3b 0a | 63 68 61 72 09 6e 65 74 |etchar;.|char.net|
|000007b0| 64 69 72 3b 0a 7b 0a 09 | 72 65 67 69 73 74 65 72 |dir;.{..|register|
|000007c0| 20 6c 69 6e 6b 09 2a 6c | 3b 0a 0a 09 6c 20 3d 20 | link.*l|;...l = |
|000007d0| 61 64 64 6c 69 6e 6b 28 | 66 72 6f 6d 2c 20 74 6f |addlink(|from, to|
|000007e0| 2c 20 63 6f 73 74 2c 20 | 6e 65 74 63 68 61 72 2c |, cost, |netchar,|
|000007f0| 20 6e 65 74 64 69 72 29 | 3b 0a 09 6c 2d 3e 6c 5f | netdir)|;..l->l_|
|00000800| 66 6c 61 67 20 7c 3d 20 | 4c 47 41 54 45 57 41 59 |flag |= |LGATEWAY|
|00000810| 3b 0a 09 72 65 74 75 72 | 6e 28 6c 29 3b 0a 7d 0a |;..retur|n(l);.}.|
|00000820| 0a 64 65 61 64 6c 69 6e | 6b 28 73 29 20 0a 63 68 |.deadlin|k(s) .ch|
|00000830| 61 72 09 2a 73 3b 0a 7b | 0a 09 63 68 61 72 09 2a |ar.*s;.{|..char.*|
|00000840| 74 2c 20 63 3b 0a 09 6c | 69 6e 6b 09 2a 6c 3b 0a |t, c;..l|ink.*l;.|
|00000850| 0a 09 74 20 3d 20 69 6e | 64 65 78 28 73 2c 20 27 |..t = in|dex(s, '|
|00000860| 21 27 29 3b 0a 09 69 66 | 20 28 74 29 20 7b 0a 09 |!');..if| (t) {..|
|00000870| 09 63 20 3d 20 2a 74 3b | 0a 09 09 2a 74 20 3d 20 |.c = *t;|...*t = |
|00000880| 30 3b 0a 09 09 6c 20 3d | 20 61 64 64 6c 69 6e 6b |0;...l =| addlink|
|00000890| 28 61 64 64 6e 6f 64 65 | 28 73 29 2c 20 61 64 64 |(addnode|(s), add|
|000008a0| 6e 6f 64 65 28 74 20 2b | 20 31 29 2c 20 49 4e 46 |node(t +| 1), INF|
|000008b0| 20 2f 20 32 2c 20 63 2c | 20 44 45 46 44 49 52 29 | / 2, c,| DEFDIR)|
|000008c0| 3b 0a 09 09 6c 2d 3e 6c | 5f 66 6c 61 67 20 7c 3d |;...l->l|_flag |=|
|000008d0| 20 4c 44 45 41 44 3b 0a | 09 7d 20 65 6c 73 65 20 | LDEAD;.|.} else |
|000008e0| 0a 09 09 61 64 64 6e 6f | 64 65 28 73 29 2d 3e 6e |...addno|de(s)->n|
|000008f0| 5f 66 6c 61 67 20 7c 3d | 20 4e 44 45 41 44 3b 0a |_flag |=| NDEAD;.|
|00000900| 7d 0a 0a 6e 65 74 62 69 | 74 73 28 6c 2c 20 6e 65 |}..netbi|ts(l, ne|
|00000910| 74 63 68 61 72 2c 20 6e | 65 74 64 69 72 29 0a 6c |tchar, n|etdir).l|
|00000920| 69 6e 6b 09 2a 6c 3b 0a | 63 68 61 72 09 6e 65 74 |ink.*l;.|char.net|
|00000930| 63 68 61 72 2c 20 6e 65 | 74 64 69 72 3b 0a 7b 0a |char, ne|tdir;.{.|
|00000940| 09 63 68 61 72 09 2a 6e | 70 74 72 3b 0a 0a 09 69 |.char.*n|ptr;...i|
|00000950| 66 20 28 28 6e 70 74 72 | 20 3d 20 69 6e 64 65 78 |f ((nptr| = index|
|00000960| 28 4e 65 74 63 68 61 72 | 73 2c 20 6e 65 74 63 68 |(Netchar|s, netch|
|00000970| 61 72 29 29 20 3d 3d 20 | 30 29 20 7b 0a 09 09 66 |ar)) == |0) {...f|
|00000980| 70 72 69 6e 74 66 28 73 | 74 64 65 72 72 2c 20 22 |printf(s|tderr, "|
|00000990| 25 73 3a 20 75 6e 6b 6e | 6f 77 6e 20 6e 65 74 77 |%s: unkn|own netw|
|000009a0| 6f 72 6b 20 6f 70 65 72 | 61 74 6f 72 3a 20 25 63 |ork oper|ator: %c|
|000009b0| 5c 6e 22 2c 0a 09 09 09 | 09 09 09 09 09 50 72 6f |\n",....|.....Pro|
|000009c0| 67 4e 61 6d 65 2c 20 6e | 65 74 63 68 61 72 29 3b |gName, n|etchar);|
|000009d0| 0a 09 09 62 61 64 6d 61 | 67 69 63 28 31 29 3b 0a |...badma|gic(1);.|
|000009e0| 09 7d 0a 09 6c 2d 3e 6c | 5f 66 6c 61 67 20 26 3d |.}..l->l|_flag &=|
|000009f0| 20 7e 28 4c 4e 45 54 43 | 48 41 52 53 7c 4c 44 49 | ~(LNETC|HARS|LDI|
|00000a00| 52 29 3b 0a 09 6c 2d 3e | 6c 5f 66 6c 61 67 20 7c |R);..l->|l_flag ||
|00000a10| 3d 20 28 6e 70 74 72 20 | 2d 20 4e 65 74 63 68 61 |= (nptr |- Netcha|
|00000a20| 72 73 29 20 7c 20 64 69 | 72 62 69 74 73 28 6e 65 |rs) | di|rbits(ne|
|00000a30| 74 64 69 72 29 3b 0a 7d | 0a 0a 74 72 61 63 65 6c |tdir);.}|..tracel|
|00000a40| 69 6e 6b 28 61 72 67 29 | 20 0a 63 68 61 72 09 2a |ink(arg)| .char.*|
|00000a50| 61 72 67 3b 0a 7b 0a 09 | 63 68 61 72 09 2a 62 61 |arg;.{..|char.*ba|
|00000a60| 6e 67 3b 0a 09 6c 69 6e | 6b 09 2a 6c 3b 0a 0a 09 |ng;..lin|k.*l;...|
|00000a70| 69 66 20 28 54 72 61 63 | 65 63 6f 75 6e 74 20 3e |if (Trac|ecount >|
|00000a80| 3d 20 4e 54 52 41 43 45 | 29 0a 09 09 72 65 74 75 |= NTRACE|)...retu|
|00000a90| 72 6e 28 2d 31 29 3b 0a | 09 6c 20 3d 20 6e 65 77 |rn(-1);.|.l = new|
|00000aa0| 6c 69 6e 6b 28 29 3b 0a | 09 62 61 6e 67 20 3d 20 |link();.|.bang = |
|00000ab0| 69 6e 64 65 78 28 61 72 | 67 2c 20 27 21 27 29 3b |index(ar|g, '!');|
|00000ac0| 0a 09 69 66 20 28 62 61 | 6e 67 29 20 7b 0a 09 09 |..if (ba|ng) {...|
|00000ad0| 2a 62 61 6e 67 20 3d 20 | 30 3b 0a 09 09 6c 2d 3e |*bang = |0;...l->|
|00000ae0| 6c 5f 74 6f 20 3d 20 61 | 64 64 6e 6f 64 65 28 62 |l_to = a|ddnode(b|
|00000af0| 61 6e 67 2b 31 29 3b 0a | 09 7d 20 65 6c 73 65 20 |ang+1);.|.} else |
|00000b00| 0a 09 09 6c 2d 3e 6c 5f | 74 6f 20 3d 20 30 3b 0a |...l->l_|to = 0;.|
|00000b10| 0a 09 6c 2d 3e 6c 5f 66 | 72 6f 6d 20 3d 20 28 6c |..l->l_f|rom = (l|
|00000b20| 69 6e 6b 20 2a 29 20 61 | 64 64 6e 6f 64 65 28 61 |ink *) a|ddnode(a|
|00000b30| 72 67 29 3b 0a 09 54 72 | 61 63 65 5b 54 72 61 63 |rg);..Tr|ace[Trac|
|00000b40| 65 63 6f 75 6e 74 2b 2b | 5d 20 3d 20 6c 3b 0a 09 |ecount++|] = l;..|
|00000b50| 72 65 74 75 72 6e 28 30 | 29 3b 0a 7d 0a 0a 53 54 |return(0|);.}..ST|
|00000b60| 41 54 49 43 0a 6c 74 72 | 61 63 65 28 66 72 6f 6d |ATIC.ltr|ace(from|
|00000b70| 2c 20 74 6f 2c 20 63 6f | 73 74 2c 20 6e 65 74 63 |, to, co|st, netc|
|00000b80| 68 61 72 2c 20 6e 65 74 | 64 69 72 29 0a 6e 6f 64 |har, net|dir).nod|
|00000b90| 65 09 2a 66 72 6f 6d 2c | 20 2a 74 6f 3b 0a 43 6f |e.*from,| *to;.Co|
|00000ba0| 73 74 09 63 6f 73 74 3b | 0a 63 68 61 72 09 6e 65 |st.cost;|.char.ne|
|00000bb0| 74 63 68 61 72 3b 0a 63 | 68 61 72 09 6e 65 74 64 |tchar;.c|har.netd|
|00000bc0| 69 72 3b 0a 7b 0a 09 6c | 69 6e 6b 09 2a 6c 3b 0a |ir;.{..l|ink.*l;.|
|00000bd0| 09 69 6e 74 09 69 3b 0a | 0a 09 66 6f 72 20 28 69 |.int.i;.|..for (i|
|00000be0| 20 3d 20 30 3b 20 69 20 | 3c 20 54 72 61 63 65 63 | = 0; i |< Tracec|
|00000bf0| 6f 75 6e 74 3b 20 69 2b | 2b 29 20 7b 0a 09 09 6c |ount; i+|+) {...l|
|00000c00| 20 3d 20 54 72 61 63 65 | 5b 69 5d 3b 0a 09 09 2f | = Trace|[i];.../|
|00000c10| 2a 20 6f 76 65 72 6b 69 | 6c 6c 20 2d 2d 20 79 6f |* overki|ll -- yo|
|00000c20| 75 20 61 73 6b 65 64 20 | 66 6f 72 20 69 74 21 20 |u asked |for it! |
|00000c30| 2a 2f 0a 09 09 69 66 20 | 28 28 6c 2d 3e 6c 5f 74 |*/...if |((l->l_t|
|00000c40| 6f 20 3d 3d 20 30 0a 09 | 09 20 20 26 26 20 28 66 |o == 0..|.  && (f|
|00000c50| 72 6f 6d 20 3d 3d 20 28 | 6e 6f 64 65 20 2a 29 20 |rom == (|node *) |
|00000c60| 6c 2d 3e 6c 5f 66 72 6f | 6d 20 7c 7c 20 74 6f 20 |l->l_fro|m || to |
|00000c70| 3d 3d 20 28 6e 6f 64 65 | 20 2a 29 20 6c 2d 3e 6c |== (node| *) l->l|
|00000c80| 5f 66 72 6f 6d 29 29 0a | 09 09 20 7c 7c 20 28 66 |_from)).|.. || (f|
|00000c90| 72 6f 6d 20 3d 3d 20 28 | 6e 6f 64 65 20 2a 29 20 |rom == (|node *) |
|00000ca0| 6c 2d 3e 6c 5f 66 72 6f | 6d 20 26 26 20 74 6f 20 |l->l_fro|m && to |
|00000cb0| 3d 3d 20 6c 2d 3e 6c 5f | 74 6f 29 0a 09 09 20 7c |== l->l_|to)... ||
|00000cc0| 7c 20 28 74 6f 20 3d 3d | 20 28 6e 6f 64 65 20 2a || (to ==| (node *|
|00000cd0| 29 20 6c 2d 3e 6c 5f 66 | 72 6f 6d 20 26 26 20 66 |) l->l_f|rom && f|
|00000ce0| 72 6f 6d 20 3d 3d 20 6c | 2d 3e 6c 5f 74 6f 29 29 |rom == l|->l_to))|
|00000cf0| 20 7b 0a 09 09 09 6c 74 | 72 70 72 69 6e 74 28 66 | {....lt|rprint(f|
|00000d00| 72 6f 6d 2c 20 74 6f 2c | 20 63 6f 73 74 2c 20 6e |rom, to,| cost, n|
|00000d10| 65 74 63 68 61 72 2c 20 | 6e 65 74 64 69 72 29 3b |etchar, |netdir);|
|00000d20| 0a 09 09 09 72 65 74 75 | 72 6e 3b 0a 09 09 7d 0a |....retu|rn;...}.|
|00000d30| 09 7d 0a 7d 0a 0a 2f 2a | 20 70 72 69 6e 74 20 61 |.}.}../*| print a|
|00000d40| 20 74 72 61 63 65 20 69 | 74 65 6d 20 2a 2f 0a 53 | trace i|tem */.S|
|00000d50| 54 41 54 49 43 0a 6c 74 | 72 70 72 69 6e 74 28 66 |TATIC.lt|rprint(f|
|00000d60| 72 6f 6d 2c 20 74 6f 2c | 20 63 6f 73 74 2c 20 6e |rom, to,| cost, n|
|00000d70| 65 74 63 68 61 72 2c 20 | 6e 65 74 64 69 72 29 0a |etchar, |netdir).|
|00000d80| 6e 6f 64 65 09 2a 66 72 | 6f 6d 2c 20 2a 74 6f 3b |node.*fr|om, *to;|
|00000d90| 0a 43 6f 73 74 09 63 6f | 73 74 3b 0a 63 68 61 72 |.Cost.co|st;.char|
|00000da0| 09 6e 65 74 63 68 61 72 | 3b 0a 63 68 61 72 09 6e |.netchar|;.char.n|
|00000db0| 65 74 64 69 72 3b 0a 7b | 0a 09 63 68 61 72 09 62 |etdir;.{|..char.b|
|00000dc0| 75 66 5b 32 35 36 5d 2c | 20 2a 62 70 74 72 20 3d |uf[256],| *bptr =|
|00000dd0| 20 62 75 66 3b 0a 0a 09 | 73 74 72 63 70 79 28 62 | buf;...|strcpy(b|
|00000de0| 70 74 72 2c 20 66 72 6f | 6d 2d 3e 6e 5f 6e 61 6d |ptr, fro|m->n_nam|
|00000df0| 65 29 3b 0a 09 62 70 74 | 72 20 2b 3d 20 73 74 72 |e);..bpt|r += str|
|00000e00| 6c 65 6e 28 62 70 74 72 | 29 3b 0a 09 2a 62 70 74 |len(bptr|);..*bpt|
|00000e10| 72 2b 2b 20 3d 20 27 20 | 27 3b 0a 09 69 66 20 28 |r++ = ' |';..if (|
|00000e20| 6e 65 74 64 69 72 20 3d | 3d 20 4c 52 49 47 48 54 |netdir =|= LRIGHT|
|00000e30| 29 09 09 09 2f 2a 20 40 | 25 20 2a 2f 0a 09 09 2a |).../* @|% */...*|
|00000e40| 62 70 74 72 2b 2b 20 3d | 20 6e 65 74 63 68 61 72 |bptr++ =| netchar|
|00000e50| 3b 0a 09 73 74 72 63 70 | 79 28 62 70 74 72 2c 20 |;..strcp|y(bptr, |
|00000e60| 74 6f 2d 3e 6e 5f 6e 61 | 6d 65 29 3b 0a 09 62 70 |to->n_na|me);..bp|
|00000e70| 74 72 20 2b 3d 20 73 74 | 72 6c 65 6e 28 62 70 74 |tr += st|rlen(bpt|
|00000e80| 72 29 3b 0a 09 69 66 20 | 28 6e 65 74 64 69 72 20 |r);..if |(netdir |
|00000e90| 3d 3d 20 4c 4c 45 46 54 | 29 09 09 09 2f 2a 20 21 |== LLEFT|).../* !|
|00000ea0| 3a 20 2a 2f 0a 09 09 2a | 62 70 74 72 2b 2b 20 3d |: */...*|bptr++ =|
|00000eb0| 20 6e 65 74 63 68 61 72 | 3b 0a 09 73 70 72 69 6e | netchar|;..sprin|
|00000ec0| 74 66 28 62 70 74 72 2c | 20 22 28 25 6c 64 29 22 |tf(bptr,| "(%ld)"|
|00000ed0| 2c 20 63 6f 73 74 29 3b | 0a 09 79 79 65 72 72 6f |, cost);|..yyerro|
|00000ee0| 72 28 62 75 66 29 3b 0a | 7d 0a 0a 61 74 72 61 63 |r(buf);.|}..atrac|
|00000ef0| 65 28 6e 31 2c 20 6e 32 | 29 0a 6e 6f 64 65 09 2a |e(n1, n2|).node.*|
|00000f00| 6e 31 2c 20 2a 6e 32 3b | 0a 7b 0a 09 6c 69 6e 6b |n1, *n2;|.{..link|
|00000f10| 09 2a 6c 3b 0a 09 69 6e | 74 09 69 3b 0a 09 63 68 |.*l;..in|t.i;..ch|
|00000f20| 61 72 09 62 75 66 5b 32 | 35 36 5d 3b 0a 0a 09 66 |ar.buf[2|56];...f|
|00000f30| 6f 72 20 28 69 20 3d 20 | 30 3b 20 69 20 3c 20 54 |or (i = |0; i < T|
|00000f40| 72 61 63 65 63 6f 75 6e | 74 3b 20 69 2b 2b 29 20 |racecoun|t; i++) |
|00000f50| 7b 0a 09 09 6c 20 3d 20 | 54 72 61 63 65 5b 69 5d |{...l = |Trace[i]|
|00000f60| 3b 0a 09 09 69 66 20 28 | 6c 2d 3e 6c 5f 74 6f 20 |;...if (|l->l_to |
|00000f70| 3d 3d 20 30 20 26 26 20 | 28 28 6e 6f 64 65 20 2a |== 0 && |((node *|
|00000f80| 29 20 6c 2d 3e 6c 5f 66 | 72 6f 6d 20 3d 3d 20 6e |) l->l_f|rom == n|
|00000f90| 31 20 7c 7c 20 28 6e 6f | 64 65 20 2a 29 20 6c 2d |1 || (no|de *) l-|
|00000fa0| 3e 6c 5f 66 72 6f 6d 20 | 3d 3d 20 6e 32 29 29 20 |>l_from |== n2)) |
|00000fb0| 7b 0a 09 09 09 73 70 72 | 69 6e 74 66 28 62 75 66 |{....spr|intf(buf|
|00000fc0| 2c 20 22 25 73 20 3d 20 | 25 73 22 2c 20 6e 31 2d |, "%s = |%s", n1-|
|00000fd0| 3e 6e 5f 6e 61 6d 65 2c | 20 6e 32 2d 3e 6e 5f 6e |>n_name,| n2->n_n|
|00000fe0| 61 6d 65 29 3b 0a 09 09 | 09 79 79 65 72 72 6f 72 |ame);...|.yyerror|
|00000ff0| 28 62 75 66 29 3b 0a 09 | 09 09 72 65 74 75 72 6e |(buf);..|..return|
|00001000| 3b 0a 09 09 7d 0a 09 7d | 0a 7d 0a 53 48 41 52 5f |;...}..}|.}.SHAR_|
|00001010| 45 4f 46 0a 69 66 20 74 | 65 73 74 20 33 33 35 38 |EOF.if t|est 3358|
|00001020| 20 2d 6e 65 20 22 60 77 | 63 20 2d 63 20 3c 20 27 | -ne "`w|c -c < '|
|00001030| 61 64 64 6c 69 6e 6b 2e | 63 27 60 22 0a 74 68 65 |addlink.|c'`".the|
|00001040| 6e 0a 09 65 63 68 6f 20 | 73 68 61 72 3a 20 65 72 |n..echo |shar: er|
|00001050| 72 6f 72 20 74 72 61 6e | 73 6d 69 74 74 69 6e 67 |ror tran|smitting|
|00001060| 20 22 27 61 64 64 6c 69 | 6e 6b 2e 63 27 22 20 27 | "'addli|nk.c'" '|
|00001070| 28 73 68 6f 75 6c 64 20 | 68 61 76 65 20 62 65 65 |(should |have bee|
|00001080| 6e 20 33 33 35 38 20 63 | 68 61 72 61 63 74 65 72 |n 3358 c|haracter|
|00001090| 73 29 27 0a 66 69 0a 66 | 69 0a 65 63 68 6f 20 73 |s)'.fi.f|i.echo s|
|000010a0| 68 61 72 3a 20 65 78 74 | 72 61 63 74 69 6e 67 20 |har: ext|racting |
|000010b0| 22 27 61 64 64 6e 6f 64 | 65 2e 63 27 22 20 27 28 |"'addnod|e.c'" '(|
|000010c0| 36 35 38 35 20 63 68 61 | 72 61 63 74 65 72 73 29 |6585 cha|racters)|
|000010d0| 27 0a 69 66 20 74 65 73 | 74 20 2d 66 20 27 61 64 |'.if tes|t -f 'ad|
|000010e0| 64 6e 6f 64 65 2e 63 27 | 0a 74 68 65 6e 0a 09 65 |dnode.c'|.then..e|
|000010f0| 63 68 6f 20 73 68 61 72 | 3a 20 77 69 6c 6c 20 6e |cho shar|: will n|
|00001100| 6f 74 20 6f 76 65 72 2d | 77 72 69 74 65 20 65 78 |ot over-|write ex|
|00001110| 69 73 74 69 6e 67 20 66 | 69 6c 65 20 22 27 61 64 |isting f|ile "'ad|
|00001120| 64 6e 6f 64 65 2e 63 27 | 22 0a 65 6c 73 65 0a 63 |dnode.c'|".else.c|
|00001130| 61 74 20 3c 3c 20 5c 53 | 48 41 52 5f 45 4f 46 20 |at << \S|HAR_EOF |
|00001140| 3e 20 27 61 64 64 6e 6f | 64 65 2e 63 27 0a 2f 2a |> 'addno|de.c'./*|
|00001150| 20 70 61 74 68 61 6c 69 | 61 73 20 2d 2d 20 62 79 | pathali|as -- by|
|00001160| 20 73 74 65 76 65 20 62 | 65 6c 6c 6f 76 69 6e 2c | steve b|ellovin,|
|00001170| 20 61 73 20 74 6f 6c 64 | 20 74 6f 20 70 65 74 65 | as told| to pete|
|00001180| 72 20 68 6f 6e 65 79 6d | 61 6e 20 2a 2f 0a 23 69 |r honeym|an */.#i|
|00001190| 66 6e 64 65 66 20 6c 69 | 6e 74 0a 73 74 61 74 69 |fndef li|nt.stati|
|000011a0| 63 20 63 68 61 72 09 2a | 73 63 63 73 69 64 20 3d |c char.*|sccsid =|
|000011b0| 20 22 40 28 23 29 61 64 | 64 6e 6f 64 65 2e 63 09 | "@(#)ad|dnode.c.|
|000011c0| 38 2e 31 20 28 64 6f 77 | 6e 21 68 6f 6e 65 79 29 |8.1 (dow|n!honey)|
|000011d0| 20 38 36 2f 30 31 2f 31 | 39 22 3b 0a 23 65 6e 64 | 86/01/1|9";.#end|
|000011e0| 69 66 0a 0a 23 69 6e 63 | 6c 75 64 65 20 22 64 65 |if..#inc|lude "de|
|000011f0| 66 2e 68 22 0a 0a 65 78 | 74 65 72 6e 20 76 6f 69 |f.h"..ex|tern voi|
|00001200| 64 09 6c 6f 77 65 72 63 | 61 73 65 28 29 2c 20 72 |d.lowerc|ase(), r|
|00001210| 65 68 61 73 68 28 29 3b | 0a 65 78 74 65 72 6e 20 |ehash();|.extern |
|00001220| 6e 6f 64 65 09 2a 69 73 | 70 72 69 76 61 74 65 28 |node.*is|private(|
|00001230| 29 3b 0a 65 78 74 65 72 | 6e 20 6c 6f 6e 67 09 68 |);.exter|n long.h|
|00001240| 61 73 68 28 29 3b 0a 0a | 2f 2a 0a 20 2a 20 74 68 |ash();..|/*. * th|
|00001250| 65 73 65 20 6e 75 6d 62 | 65 72 73 20 61 72 65 20 |ese numb|ers are |
|00001260| 63 68 6f 73 65 6e 20 62 | 65 63 61 75 73 65 3a 0a |chosen b|ecause:.|
|00001270| 20 2a 09 2d 3e 20 74 68 | 65 79 20 61 72 65 20 70 | *.-> th|ey are p|
|00001280| 72 69 6d 65 2c 0a 20 2a | 09 2d 3e 20 74 68 65 79 |rime,. *|.-> they|
|00001290| 20 61 72 65 20 6d 6f 6e | 6f 74 6f 6e 69 63 20 69 | are mon|otonic i|
|000012a0| 6e 63 72 65 61 73 69 6e | 67 2c 0a 20 2a 09 2d 3e |ncreasin|g,. *.->|
|000012b0| 20 65 61 63 68 20 69 73 | 20 61 20 74 61 64 20 73 | each is| a tad s|
|000012c0| 6d 61 6c 6c 65 72 20 74 | 68 61 6e 20 61 20 6d 75 |maller t|han a mu|
|000012d0| 6c 74 69 70 6c 65 20 6f | 66 20 31 30 32 34 2c 0a |ltiple o|f 1024,.|
|000012e0| 20 2a 09 2d 3e 20 74 68 | 65 79 20 66 6f 72 6d 20 | *.-> th|ey form |
|000012f0| 61 20 66 69 62 6f 6e 61 | 63 63 69 20 73 65 71 75 |a fibona|cci sequ|
|00001300| 65 6e 63 65 20 28 61 6c | 6d 6f 73 74 29 2e 0a 20 |ence (al|most).. |
|00001310| 2a 20 74 68 65 20 66 69 | 72 73 74 20 70 6f 69 6e |* the fi|rst poin|
|00001320| 74 20 79 69 65 6c 64 73 | 20 67 6f 6f 64 20 68 61 |t yields| good ha|
|00001330| 73 68 20 66 75 6e 63 74 | 69 6f 6e 73 2c 20 74 68 |sh funct|ions, th|
|00001340| 65 20 73 65 63 6f 6e 64 | 20 69 73 20 75 73 65 64 |e second| is used|
|00001350| 20 66 6f 72 20 74 68 65 | 0a 20 2a 20 73 74 61 6e | for the|. * stan|
|00001360| 64 61 72 64 20 72 65 2d | 68 61 73 68 69 6e 67 20 |dard re-|hashing |
|00001370| 69 6d 70 6c 65 6d 65 6e | 74 61 74 69 6f 6e 20 6f |implemen|tation o|
|00001380| 66 20 6f 70 65 6e 20 61 | 64 64 72 65 73 73 69 6e |f open a|ddressin|
|00001390| 67 2c 20 74 68 65 20 74 | 68 69 72 64 0a 20 2a 20 |g, the t|hird. * |
|000013a0| 6f 70 74 69 6d 69 7a 65 | 73 20 66 6f 72 20 71 75 |optimize|s for qu|
|000013b0| 69 72 6b 73 20 69 6e 20 | 73 6f 6d 65 20 6d 61 6c |irks in |some mal|
|000013c0| 6c 6f 63 73 20 69 20 68 | 61 76 65 20 73 65 65 6e |locs i h|ave seen|
|000013d0| 2c 20 61 6e 64 20 74 68 | 65 20 66 6f 75 72 74 68 |, and th|e fourth|
|000013e0| 20 73 69 6d 70 6c 79 0a | 20 2a 20 61 70 70 65 61 | simply.| * appea|
|000013f0| 6c 73 20 74 6f 20 6d 65 | 2e 0a 20 2a 2f 0a 73 74 |ls to me|.. */.st|
|00001400| 61 74 69 63 20 69 6e 74 | 20 50 72 69 6d 65 73 5b |atic int| Primes[|
|00001410| 5d 09 3d 20 7b 0a 23 69 | 66 6e 64 65 66 20 53 51 |].= {.#i|fndef SQ|
|00001420| 55 41 4e 44 45 52 0a 09 | 31 30 32 31 2c 20 32 30 |UANDER..|1021, 20|
|00001430| 33 39 2c 20 33 30 36 37 | 2c 20 35 31 31 33 2c 20 |39, 3067|, 5113, |
|00001440| 38 31 37 39 2c 0a 23 65 | 6e 64 69 66 0a 09 31 33 |8179,.#e|ndif..13|
|00001450| 33 30 39 2c 20 32 31 34 | 39 39 2c 20 30 0a 7d 3b |309, 214|99, 0.};|
|00001460| 0a 0a 73 74 61 74 69 63 | 20 69 6e 74 09 54 61 62 |..static| int.Tab|
|00001470| 69 6e 64 65 78 20 3d 20 | 2d 31 3b 0a 73 74 61 74 |index = |-1;.stat|
|00001480| 69 63 20 69 6e 74 09 43 | 6f 6c 6c 69 73 69 6f 6e |ic int.C|ollision|
|00001490| 3b 09 2f 2a 20 6d 61 72 | 6b 20 68 6f 73 74 20 6e |;./* mar|k host n|
|000014a0| 61 6d 65 20 63 6f 6c 6c | 69 73 69 6f 6e 73 20 69 |ame coll|isions i|
|000014b0| 6e 20 68 61 73 68 28 29 | 20 2a 2f 0a 0a 6e 6f 64 |n hash()| */..nod|
|000014c0| 65 09 2a 0a 61 64 64 6e | 6f 64 65 28 6e 61 6d 65 |e.*.addn|ode(name|
|000014d0| 29 0a 72 65 67 69 73 74 | 65 72 20 63 68 61 72 09 |).regist|er char.|
|000014e0| 2a 6e 61 6d 65 3b 0a 7b | 0a 09 72 65 67 69 73 74 |*name;.{|..regist|
|000014f0| 65 72 20 6c 6f 6e 67 09 | 69 3b 0a 09 72 65 67 69 |er long.|i;..regi|
|00001500| 73 74 65 72 20 6e 6f 64 | 65 09 2a 6e 3b 0a 0a 09 |ster nod|e.*n;...|
|00001510| 69 66 20 28 49 66 6c 61 | 67 29 0a 09 09 6c 6f 77 |if (Ifla|g)...low|
|00001520| 65 72 63 61 73 65 28 6e | 61 6d 65 29 3b 0a 0a 09 |ercase(n|ame);...|
|00001530| 2f 2a 20 69 73 20 69 74 | 20 61 20 70 72 69 76 61 |/* is it| a priva|
|00001540| 74 65 20 68 6f 73 74 3f | 20 2a 2f 0a 09 6e 20 3d |te host?| */..n =|
|00001550| 20 69 73 70 72 69 76 61 | 74 65 28 6e 61 6d 65 29 | ispriva|te(name)|
|00001560| 3b 0a 09 69 66 20 28 6e | 29 0a 09 09 72 65 74 75 |;..if (n|)...retu|
|00001570| 72 6e 28 6e 29 3b 0a 0a | 09 69 20 3d 20 68 61 73 |rn(n);..|.i = has|
|00001580| 68 28 6e 61 6d 65 2c 20 | 30 29 3b 0a 09 69 66 20 |h(name, |0);..if |
|00001590| 28 54 61 62 6c 65 5b 69 | 5d 29 20 0a 09 09 72 65 |(Table[i|]) ...re|
|000015a0| 74 75 72 6e 28 54 61 62 | 6c 65 5b 69 5d 29 3b 0a |turn(Tab|le[i]);.|
|000015b0| 0a 09 6e 20 3d 20 6e 65 | 77 6e 6f 64 65 28 29 3b |..n = ne|wnode();|
|000015c0| 0a 09 6e 2d 3e 6e 5f 6e | 61 6d 65 20 3d 20 73 74 |..n->n_n|ame = st|
|000015d0| 72 73 61 76 65 28 6e 61 | 6d 65 29 3b 0a 09 54 61 |rsave(na|me);..Ta|
|000015e0| 62 6c 65 5b 69 5d 20 3d | 20 6e 3b 0a 09 6e 2d 3e |ble[i] =| n;..n->|
|000015f0| 6e 5f 74 6c 6f 63 20 3d | 20 69 3b 09 2f 2a 20 65 |n_tloc =| i;./* e|
|00001600| 73 73 65 6e 74 69 61 6c | 6c 79 20 61 20 62 61 63 |ssential|ly a bac|
|00001610| 6b 20 6c 69 6e 6b 20 74 | 6f 20 74 68 65 20 74 61 |k link t|o the ta|
|00001620| 62 6c 65 20 2a 2f 0a 09 | 69 66 20 28 43 6f 6c 6c |ble */..|if (Coll|
|00001630| 69 73 69 6f 6e 29 0a 09 | 09 6e 2d 3e 6e 5f 66 6c |ision)..|.n->n_fl|
|00001640| 61 67 20 7c 3d 20 43 4f | 4c 4c 49 53 49 4f 4e 3b |ag |= CO|LLISION;|
|00001650| 09 2f 2a 20 6e 61 6d 65 | 20 63 6f 6c 6c 69 73 69 |./* name| collisi|
|00001660| 6f 6e 20 77 69 74 68 20 | 70 72 69 76 61 74 65 20 |on with |private |
|00001670| 68 6f 73 74 20 2a 2f 0a | 0a 09 72 65 74 75 72 6e |host */.|..return|
|00001680| 28 6e 29 3b 0a 7d 0a 0a | 61 6c 69 61 73 28 6e 31 |(n);.}..|alias(n1|
|00001690| 2c 20 6e 32 29 0a 6e 6f | 64 65 09 2a 6e 31 2c 20 |, n2).no|de.*n1, |
|000016a0| 2a 6e 32 3b 0a 7b 0a 09 | 6c 69 6e 6b 09 2a 6c 3b |*n2;.{..|link.*l;|
|000016b0| 0a 09 65 78 74 65 72 6e | 20 6c 69 6e 6b 20 2a 61 |..extern| link *a|
|000016c0| 64 64 6c 69 6e 6b 28 29 | 3b 0a 0a 09 6c 20 3d 20 |ddlink()|;...l = |
|000016d0| 61 64 64 6c 69 6e 6b 28 | 6e 31 2c 20 6e 32 2c 20 |addlink(|n1, n2, |
|000016e0| 28 43 6f 73 74 29 20 30 | 2c 20 44 45 46 4e 45 54 |(Cost) 0|, DEFNET|
|000016f0| 2c 20 44 45 46 44 49 52 | 29 3b 0a 09 6c 2d 3e 6c |, DEFDIR|);..l->l|
|00001700| 5f 66 6c 61 67 20 7c 3d | 20 4c 41 4c 49 41 53 3b |_flag |=| LALIAS;|
|00001710| 0a 09 6c 20 3d 20 61 64 | 64 6c 69 6e 6b 28 6e 32 |..l = ad|dlink(n2|
|00001720| 2c 20 6e 31 2c 20 28 43 | 6f 73 74 29 20 30 2c 20 |, n1, (C|ost) 0, |
|00001730| 44 45 46 4e 45 54 2c 20 | 44 45 46 44 49 52 29 3b |DEFNET, |DEFDIR);|
|00001740| 0a 09 6c 2d 3e 6c 5f 66 | 6c 61 67 20 7c 3d 20 4c |..l->l_f|lag |= L|
|00001750| 41 4c 49 41 53 3b 0a 09 | 69 66 20 28 54 66 6c 61 |ALIAS;..|if (Tfla|
|00001760| 67 29 0a 09 09 61 74 72 | 61 63 65 28 6e 31 2c 20 |g)...atr|ace(n1, |
|00001770| 6e 32 29 3b 0a 7d 0a 0a | 2f 2a 0a 20 2a 20 66 6f |n2);.}..|/*. * fo|
|00001780| 6c 64 20 61 20 73 74 72 | 69 6e 67 20 69 6e 74 6f |ld a str|ing into|
|00001790| 20 61 20 6c 6f 6e 67 20 | 69 6e 74 2e 20 20 74 68 | a long |int.  th|
|000017a0| 69 73 20 61 6c 67 6f 72 | 69 74 68 6d 20 69 67 6e |is algor|ithm ign|
|000017b0| 6f 72 65 73 20 61 6c 6c | 20 62 75 74 20 74 68 65 |ores all| but the|
|000017c0| 20 6c 61 73 74 0a 20 2a | 20 65 69 67 68 74 20 62 | last. *| eight b|
|000017d0| 79 74 65 73 2c 20 77 68 | 69 63 68 20 61 66 66 65 |ytes, wh|ich affe|
|000017e0| 63 74 73 20 3c 20 31 35 | 25 20 6f 66 20 61 6c 6c |cts < 15|% of all|
|000017f0| 20 68 6f 73 74 20 6e 61 | 6d 65 73 2c 20 6d 61 6e | host na|mes, man|
|00001800| 79 20 6f 66 20 77 68 69 | 63 68 20 68 61 76 65 0a |y of whi|ch have.|
|00001810| 20 2a 20 63 6f 6d 6d 6f | 6e 20 70 72 65 66 69 78 | * commo|n prefix|
|00001820| 65 73 20 61 6e 79 77 61 | 79 2e 0a 20 2a 2f 0a 53 |es anywa|y.. */.S|
|00001830| 54 41 54 49 43 20 6c 6f | 6e 67 0a 66 6f 6c 64 28 |TATIC lo|ng.fold(|
|00001840| 73 74 72 29 0a 72 65 67 | 69 73 74 65 72 20 63 68 |str).reg|ister ch|
|00001850| 61 72 09 2a 73 74 72 3b | 0a 7b 0a 09 72 65 67 69 |ar.*str;|.{..regi|
|00001860| 73 74 65 72 20 6c 6f 6e | 67 09 73 75 6d 3b 0a 0a |ster lon|g.sum;..|
|00001870| 09 73 75 6d 20 3d 20 2a | 73 74 72 2b 2b 3b 0a 09 |.sum = *|str++;..|
|00001880| 77 68 69 6c 65 20 28 2a | 73 74 72 29 20 7b 0a 09 |while (*|str) {..|
|00001890| 09 73 75 6d 20 3c 3c 3d | 20 34 3b 0a 09 09 73 75 |.sum <<=| 4;...su|
|000018a0| 6d 20 2b 3d 20 2a 73 74 | 72 2b 2b 3b 0a 09 7d 0a |m += *st|r++;..}.|
|000018b0| 09 69 66 20 28 73 75 6d | 20 3c 20 30 29 20 0a 09 |.if (sum| < 0) ..|
|000018c0| 09 73 75 6d 20 3d 20 2d | 73 75 6d 3b 0a 09 72 65 |.sum = -|sum;..re|
|000018d0| 74 75 72 6e 28 73 75 6d | 29 3b 0a 7d 0a 0a 23 64 |turn(sum|);.}..#d|
|000018e0| 65 66 69 6e 65 20 48 41 | 53 48 31 28 6e 29 20 28 |efine HA|SH1(n) (|
|000018f0| 28 6e 29 20 25 20 54 61 | 62 73 69 7a 65 29 3b 0a |(n) % Ta|bsize);.|
|00001900| 23 64 65 66 69 6e 65 20 | 48 41 53 48 32 28 6e 29 |#define |HASH2(n)|
|00001910| 20 28 54 61 62 73 69 7a | 65 20 2d 20 32 20 2d 20 | (Tabsiz|e - 2 - |
|00001920| 28 28 6e 29 20 25 20 28 | 54 61 62 73 69 7a 65 2d |((n) % (|Tabsize-|
|00001930| 32 29 29 29 09 2f 2a 20 | 70 72 69 6e 63 65 74 6f |2)))./* |princeto|
|00001940| 6e 21 72 73 20 2a 2f 0a | 0a 2f 2a 0a 20 2a 20 77 |n!rs */.|./*. * w|
|00001950| 69 74 68 20 61 20 30 2e | 37 35 20 68 69 67 68 20 |ith a 0.|75 high |
|00001960| 77 61 74 65 72 20 6d 61 | 72 6b 2c 20 70 72 6f 62 |water ma|rk, prob|
|00001970| 65 73 20 70 65 72 20 61 | 63 63 65 73 73 20 73 68 |es per a|ccess sh|
|00001980| 6f 75 6c 64 20 62 65 20 | 31 2e 38 34 2e 0a 20 2a |ould be |1.84.. *|
|00001990| 20 75 73 65 20 6c 6f 6e | 67 20 63 6f 6e 73 74 61 | use lon|g consta|
|000019a0| 6e 74 20 74 6f 20 66 6f | 72 63 65 20 70 72 6f 6d |nt to fo|rce prom|
|000019b0| 6f 74 69 6f 6e 2e 0a 20 | 2a 2f 0a 23 64 65 66 69 |otion.. |*/.#defi|
|000019c0| 6e 65 20 48 49 47 48 57 | 41 54 45 52 09 37 35 4c |ne HIGHW|ATER.75L|
|000019d0| 0a 23 64 65 66 69 6e 65 | 20 69 73 66 75 6c 6c 28 |.#define| isfull(|
|000019e0| 6e 2c 20 73 69 7a 65 29 | 09 28 28 6e 29 20 3e 20 |n, size)|.((n) > |
|000019f0| 28 28 73 69 7a 65 29 20 | 2a 20 48 49 47 48 57 41 |((size) |* HIGHWA|
|00001a00| 54 45 52 29 20 2f 20 31 | 30 30 29 0a 0a 53 54 41 |TER) / 1|00)..STA|
|00001a10| 54 49 43 20 6c 6f 6e 67 | 0a 68 61 73 68 28 6e 61 |TIC long|.hash(na|
|00001a20| 6d 65 2c 20 75 6e 69 71 | 75 65 29 0a 63 68 61 72 |me, uniq|ue).char|
|00001a30| 09 2a 6e 61 6d 65 3b 0a | 7b 0a 09 72 65 67 69 73 |.*name;.|{..regis|
|00001a40| 74 65 72 20 6c 6f 6e 67 | 09 70 72 6f 62 65 2c 20 |ter long|.probe, |
|00001a50| 68 61 73 68 32 3b 0a 09 | 72 65 67 69 73 74 65 72 |hash2;..|register|
|00001a60| 20 6e 6f 64 65 09 2a 6e | 3b 0a 0a 09 69 66 20 28 | node.*n|;...if (|
|00001a70| 54 61 62 69 6e 64 65 78 | 20 3c 20 30 29 20 7b 09 |Tabindex| < 0) {.|
|00001a80| 09 09 2f 2a 20 66 69 72 | 73 74 20 74 69 6d 65 20 |../* fir|st time |
|00001a90| 2a 2f 0a 09 09 54 61 62 | 69 6e 64 65 78 20 3d 20 |*/...Tab|index = |
|00001aa0| 30 3b 0a 09 09 54 61 62 | 73 69 7a 65 20 3d 20 50 |0;...Tab|size = P|
|00001ab0| 72 69 6d 65 73 5b 30 5d | 3b 0a 09 09 54 61 62 6c |rimes[0]|;...Tabl|
|00001ac0| 65 20 3d 20 6e 65 77 74 | 61 62 6c 65 28 54 61 62 |e = newt|able(Tab|
|00001ad0| 73 69 7a 65 29 3b 0a 09 | 7d 20 65 6c 73 65 20 69 |size);..|} else i|
|00001ae0| 66 20 28 69 73 66 75 6c | 6c 28 4e 63 6f 75 6e 74 |f (isful|l(Ncount|
|00001af0| 2c 20 54 61 62 73 69 7a | 65 29 29 0a 09 09 72 65 |, Tabsiz|e))...re|
|00001b00| 68 61 73 68 28 29 3b 09 | 09 09 2f 2a 20 6d 6f 72 |hash();.|../* mor|
|00001b10| 65 2c 20 6d 6f 72 65 21 | 20 2a 2f 0a 09 09 09 09 |e, more!| */.....|
|00001b20| 0a 09 70 72 6f 62 65 20 | 3d 20 66 6f 6c 64 28 6e |..probe |= fold(n|
|00001b30| 61 6d 65 29 3b 0a 09 2f | 2a 20 64 6f 6e 27 74 20 |ame);../|* don't |
|00001b40| 63 68 61 6e 67 65 20 74 | 68 65 20 6f 72 64 65 72 |change t|he order|
|00001b50| 20 6f 66 20 74 68 65 20 | 6e 65 78 74 20 74 77 6f | of the |next two|
|00001b60| 20 6c 69 6e 65 73 20 2a | 2f 0a 09 68 61 73 68 32 | lines *|/..hash2|
|00001b70| 20 3d 20 48 41 53 48 32 | 28 70 72 6f 62 65 29 3b | = HASH2|(probe);|
|00001b80| 0a 09 70 72 6f 62 65 20 | 3d 20 48 41 53 48 31 28 |..probe |= HASH1(|
|00001b90| 70 72 6f 62 65 29 3b 0a | 09 2f 2a 20 74 68 61 6e |probe);.|./* than|
|00001ba0| 6b 20 79 6f 75 21 20 2a | 2f 0a 0a 09 2f 2a 0a 09 |k you! *|/.../*..|
|00001bb0| 20 2a 20 70 72 6f 62 65 | 20 74 68 65 20 68 61 73 | * probe| the has|
|00001bc0| 68 20 74 61 62 6c 65 2e | 0a 09 20 2a 20 69 66 20 |h table.|.. * if |
|00001bd0| 75 6e 69 71 75 65 20 69 | 73 20 73 65 74 2c 20 77 |unique i|s set, w|
|00001be0| 65 20 72 65 71 75 69 72 | 65 20 61 20 66 72 65 73 |e requir|e a fres|
|00001bf0| 68 20 73 6c 6f 74 2e 0a | 09 20 2a 20 6f 74 68 65 |h slot..|. * othe|
|00001c00| 72 77 69 73 65 2c 20 75 | 73 65 20 64 6f 75 62 6c |rwise, u|se doubl|
|00001c10| 65 20 68 61 73 68 69 6e | 67 20 74 6f 20 66 69 6e |e hashin|g to fin|
|00001c20| 64 20 65 69 74 68 65 72 | 0a 09 20 2a 20 20 28 31 |d either|.. *  (1|
|00001c30| 29 20 61 6e 20 65 6d 70 | 74 79 20 73 6c 6f 74 2c |) an emp|ty slot,|
|00001c40| 20 6f 72 0a 09 20 2a 20 | 20 28 32 29 20 61 20 6e | or.. * | (2) a n|
|00001c50| 6f 6e 2d 70 72 69 76 61 | 74 65 20 63 6f 70 79 20 |on-priva|te copy |
|00001c60| 6f 66 20 74 68 69 73 20 | 68 6f 73 74 20 6e 61 6d |of this |host nam|
|00001c70| 65 0a 09 20 2a 0a 09 20 | 2a 20 61 73 20 61 20 73 |e.. *.. |* as a s|
|00001c80| 69 64 65 20 65 66 66 65 | 63 74 2c 20 69 66 20 77 |ide effe|ct, if w|
|00001c90| 65 20 6e 6f 74 69 63 65 | 20 61 20 63 6f 6c 6c 69 |e notice| a colli|
|00001ca0| 73 69 6f 6e 20 77 69 74 | 68 20 61 20 70 72 69 76 |sion wit|h a priv|
|00001cb0| 61 74 65 20 68 6f 73 74 | 0a 09 20 2a 20 77 65 20 |ate host|.. * we |
|00001cc0| 6d 61 72 6b 20 74 68 65 | 20 6f 74 68 65 72 20 73 |mark the| other s|
|00001cd0| 6f 20 74 68 61 74 20 69 | 74 20 69 73 20 73 6b 69 |o that i|t is ski|
|00001ce0| 70 70 65 64 20 61 74 20 | 6f 75 74 70 75 74 20 74 |pped at |output t|
|00001cf0| 69 6d 65 2e 0a 09 20 2a | 2f 0a 09 43 6f 6c 6c 69 |ime... *|/..Colli|
|00001d00| 73 69 6f 6e 20 3d 20 30 | 3b 0a 09 77 68 69 6c 65 |sion = 0|;..while|
|00001d10| 20 28 28 6e 20 3d 20 54 | 61 62 6c 65 5b 70 72 6f | ((n = T|able[pro|
|00001d20| 62 65 5d 29 20 21 3d 20 | 30 29 20 7b 0a 09 09 69 |be]) != |0) {...i|
|00001d30| 66 20 28 73 74 72 63 6d | 70 28 6e 2d 3e 6e 5f 6e |f (strcm|p(n->n_n|
|00001d40| 61 6d 65 2c 20 6e 61 6d | 65 29 20 3d 3d 20 30 29 |ame, nam|e) == 0)|
|00001d50| 20 7b 0a 09 09 09 69 66 | 20 28 75 6e 69 71 75 65 | {....if| (unique|
|00001d60| 29 0a 09 09 09 09 6e 2d | 3e 6e 5f 66 6c 61 67 20 |).....n-|>n_flag |
|00001d70| 7c 3d 20 43 4f 4c 4c 49 | 53 49 4f 4e 3b 0a 09 09 ||= COLLI|SION;...|
|00001d80| 09 65 6c 73 65 20 69 66 | 20 28 6e 2d 3e 6e 5f 66 |.else if| (n->n_f|
|00001d90| 6c 61 67 20 26 20 49 53 | 50 52 49 56 41 54 45 29 |lag & IS|PRIVATE)|
|00001da0| 0a 09 09 09 09 43 6f 6c | 6c 69 73 69 6f 6e 2b 2b |.....Col|lision++|
|00001db0| 3b 0a 09 09 09 65 6c 73 | 65 0a 09 09 09 09 62 72 |;....els|e.....br|
|00001dc0| 65 61 6b 3b 09 2f 2a 20 | 74 68 69 73 20 69 73 20 |eak;./* |this is |
|00001dd0| 69 74 21 20 2a 2f 0a 09 | 09 7d 0a 09 09 70 72 6f |it! */..|.}...pro|
|00001de0| 62 65 20 2d 3d 20 68 61 | 73 68 32 3b 0a 09 09 69 |be -= ha|sh2;...i|
|00001df0| 66 20 28 70 72 6f 62 65 | 20 3c 20 30 29 0a 09 09 |f (probe| < 0)...|
|00001e00| 09 70 72 6f 62 65 20 2b | 3d 20 54 61 62 73 69 7a |.probe +|= Tabsiz|
|00001e10| 65 3b 0a 09 7d 0a 09 72 | 65 74 75 72 6e 28 70 72 |e;..}..r|eturn(pr|
|00001e20| 6f 62 65 29 3b 0a 7d 0a | 0a 53 54 41 54 49 43 20 |obe);.}.|.STATIC |
|00001e30| 76 6f 69 64 0a 72 65 68 | 61 73 68 28 29 0a 7b 0a |void.reh|ash().{.|
|00001e40| 09 72 65 67 69 73 74 65 | 72 20 6e 6f 64 65 09 2a |.registe|r node.*|
|00001e50| 2a 6f 74 61 62 6c 65 2c | 20 2a 2a 6f 70 74 72 3b |*otable,| **optr;|
|00001e60| 0a 09 72 65 67 69 73 74 | 65 72 20 6c 6f 6e 67 09 |..regist|er long.|
|00001e70| 70 72 6f 62 65 3b 0a 09 | 6c 6f 6e 67 09 6f 73 69 |probe;..|long.osi|
|00001e80| 7a 65 3b 0a 0a 23 69 66 | 64 65 66 20 44 45 42 55 |ze;..#if|def DEBU|
|00001e90| 47 0a 09 68 61 73 68 61 | 6e 61 6c 79 7a 65 28 29 |G..hasha|nalyze()|
|00001ea0| 3b 0a 23 65 6e 64 69 66 | 0a 09 6f 70 74 72 20 3d |;.#endif|..optr =|
|00001eb0| 20 54 61 62 6c 65 20 2b | 20 54 61 62 73 69 7a 65 | Table +| Tabsize|
|00001ec0| 20 2d 20 31 3b 09 2f 2a | 20 70 74 72 20 74 6f 20 | - 1;./*| ptr to |
|00001ed0| 6c 61 73 74 20 2a 2f 0a | 09 6f 74 61 62 6c 65 20 |last */.|.otable |
|00001ee0| 3d 20 54 61 62 6c 65 3b | 0a 09 6f 73 69 7a 65 20 |= Table;|..osize |
|00001ef0| 3d 20 54 61 62 73 69 7a | 65 3b 0a 09 54 61 62 73 |= Tabsiz|e;..Tabs|
|00001f00| 69 7a 65 20 3d 20 50 72 | 69 6d 65 73 5b 2b 2b 54 |ize = Pr|imes[++T|
|00001f10| 61 62 69 6e 64 65 78 5d | 3b 0a 09 69 66 20 28 54 |abindex]|;..if (T|
|00001f20| 61 62 73 69 7a 65 20 3d | 3d 20 30 29 20 7b 09 2f |absize =|= 0) {./|
|00001f30| 2a 20 6e 65 65 64 20 6d | 6f 72 65 20 70 72 69 6d |* need m|ore prim|
|00001f40| 65 20 6e 75 6d 62 65 72 | 73 20 2a 2f 0a 09 09 66 |e number|s */...f|
|00001f50| 70 72 69 6e 74 66 28 73 | 74 64 65 72 72 2c 20 22 |printf(s|tderr, "|
|00001f60| 25 73 3a 20 3e 20 25 64 | 20 68 6f 73 74 73 5c 6e |%s: > %d| hosts\n|
|00001f70| 22 2c 20 50 72 6f 67 4e | 61 6d 65 2c 20 50 72 69 |", ProgN|ame, Pri|
|00001f80| 6d 65 73 5b 54 61 62 69 | 6e 64 65 78 2d 31 5d 29 |mes[Tabi|ndex-1])|
|00001f90| 3b 0a 09 09 62 61 64 6d | 61 67 69 63 28 31 29 3b |;...badm|agic(1);|
|00001fa0| 0a 09 7d 0a 09 76 70 72 | 69 6e 74 66 28 73 74 64 |..}..vpr|intf(std|
|00001fb0| 65 72 72 2c 20 22 72 65 | 68 61 73 68 20 69 6e 74 |err, "re|hash int|
|00001fc0| 6f 20 25 64 5c 6e 22 2c | 20 54 61 62 73 69 7a 65 |o %d\n",| Tabsize|
|00001fd0| 29 3b 0a 09 54 61 62 6c | 65 20 3d 20 6e 65 77 74 |);..Tabl|e = newt|
|00001fe0| 61 62 6c 65 28 54 61 62 | 73 69 7a 65 29 3b 0a 0a |able(Tab|size);..|
|00001ff0| 09 64 6f 20 7b 0a 09 09 | 69 66 20 28 2a 6f 70 74 |.do {...|if (*opt|
|00002000| 72 20 3d 3d 20 30 29 0a | 09 09 09 63 6f 6e 74 69 |r == 0).|...conti|
|00002010| 6e 75 65 3b 09 2f 2a 20 | 65 6d 70 74 79 20 73 6c |nue;./* |empty sl|
|00002020| 6f 74 20 69 6e 20 6f 6c | 64 20 74 61 62 6c 65 20 |ot in ol|d table |
|00002030| 2a 2f 0a 09 09 70 72 6f | 62 65 20 3d 20 68 61 73 |*/...pro|be = has|
|00002040| 68 28 28 2a 6f 70 74 72 | 29 2d 3e 6e 5f 6e 61 6d |h((*optr|)->n_nam|
|00002050| 65 2c 20 28 2a 6f 70 74 | 72 29 2d 3e 6e 5f 66 6c |e, (*opt|r)->n_fl|
|00002060| 61 67 20 26 20 49 53 50 | 52 49 56 41 54 45 29 3b |ag & ISP|RIVATE);|
|00002070| 0a 09 09 69 66 20 28 54 | 61 62 6c 65 5b 70 72 6f |...if (T|able[pro|
|00002080| 62 65 5d 20 21 3d 20 30 | 29 20 7b 0a 09 09 09 66 |be] != 0|) {....f|
|00002090| 70 72 69 6e 74 66 28 73 | 74 64 65 72 72 2c 20 22 |printf(s|tderr, "|
|000020a0| 25 73 3a 20 72 65 68 61 | 73 68 20 65 72 72 6f 72 |%s: reha|sh error|
|000020b0| 5c 6e 22 2c 20 50 72 6f | 67 4e 61 6d 65 29 3b 0a |\n", Pro|gName);.|
|000020c0| 09 09 09 62 61 64 6d 61 | 67 69 63 28 31 29 3b 0a |...badma|gic(1);.|
|000020d0| 09 09 7d 0a 09 09 54 61 | 62 6c 65 5b 70 72 6f 62 |..}...Ta|ble[prob|
|000020e0| 65 5d 20 3d 20 2a 6f 70 | 74 72 3b 0a 09 09 28 2a |e] = *op|tr;...(*|
|000020f0| 6f 70 74 72 29 2d 3e 6e | 5f 74 6c 6f 63 20 3d 20 |optr)->n|_tloc = |
|00002100| 70 72 6f 62 65 3b 0a 09 | 7d 20 77 68 69 6c 65 20 |probe;..|} while |
|00002110| 28 6f 70 74 72 2d 2d 20 | 3e 20 6f 74 61 62 6c 65 |(optr-- |> otable|
|00002120| 29 3b 0a 09 66 72 65 65 | 74 61 62 6c 65 28 6f 74 |);..free|table(ot|
|00002130| 61 62 6c 65 2c 20 6f 73 | 69 7a 65 29 3b 0a 7d 0a |able, os|ize);.}.|
|00002140| 0a 68 61 73 68 61 6e 61 | 6c 79 7a 65 28 29 0a 7b |.hashana|lyze().{|
|00002150| 0a 09 6c 6f 6e 67 09 70 | 72 6f 62 65 2c 20 68 61 |..long.p|robe, ha|
|00002160| 73 68 32 3b 0a 09 69 6e | 74 09 63 6f 75 6e 74 2c |sh2;..in|t.count,|
|00002170| 20 69 2c 20 63 6f 6c 6c | 69 73 69 6f 6e 5b 38 5d | i, coll|ision[8]|
|00002180| 3b 0a 09 69 6e 74 09 6c | 6f 6e 67 65 73 74 20 3d |;..int.l|ongest =|
|00002190| 20 30 2c 20 74 6f 74 61 | 6c 20 3d 20 30 2c 20 73 | 0, tota|l = 0, s|
|000021a0| 6c 6f 74 73 20 3d 20 30 | 3b 0a 09 69 6e 74 09 6e |lots = 0|;..int.n|
|000021b0| 73 6c 6f 74 73 20 3d 20 | 73 69 7a 65 6f 66 28 63 |slots = |sizeof(c|
|000021c0| 6f 6c 6c 69 73 69 6f 6e | 29 2f 73 69 7a 65 6f 66 |ollision|)/sizeof|
|000021d0| 28 63 6f 6c 6c 69 73 69 | 6f 6e 5b 30 5d 29 3b 0a |(collisi|on[0]);.|
|000021e0| 0a 09 69 66 20 28 21 56 | 66 6c 61 67 29 0a 09 09 |..if (!V|flag)...|
|000021f0| 72 65 74 75 72 6e 3b 0a | 0a 09 73 74 72 63 6c 65 |return;.|..strcle|
|00002200| 61 72 28 28 63 68 61 72 | 20 2a 29 20 63 6f 6c 6c |ar((char| *) coll|
|00002210| 69 73 69 6f 6e 2c 20 73 | 69 7a 65 6f 66 28 63 6f |ision, s|izeof(co|
|00002220| 6c 6c 69 73 69 6f 6e 29 | 29 3b 0a 09 66 6f 72 20 |llision)|);..for |
|00002230| 28 69 20 3d 20 30 3b 20 | 69 20 3c 20 54 61 62 73 |(i = 0; |i < Tabs|
|00002240| 69 7a 65 3b 20 69 2b 2b | 29 20 7b 0a 09 09 69 66 |ize; i++|) {...if|
|00002250| 20 28 54 61 62 6c 65 5b | 69 5d 20 3d 3d 20 30 29 | (Table[|i] == 0)|
|00002260| 0a 09 09 09 63 6f 6e 74 | 69 6e 75 65 3b 0a 09 09 |....cont|inue;...|
|00002270| 2f 2a 20 70 72 69 76 61 | 74 65 20 68 6f 73 74 73 |/* priva|te hosts|
|00002280| 20 74 6f 6f 20 68 61 72 | 64 20 74 6f 20 61 63 63 | too har|d to acc|
|00002290| 6f 75 6e 74 20 66 6f 72 | 20 2e 2e 2e 20 2a 2f 0a |ount for| ... */.|
|000022a0| 09 09 69 66 20 28 54 61 | 62 6c 65 5b 69 5d 2d 3e |..if (Ta|ble[i]->|
|000022b0| 6e 5f 66 6c 61 67 20 26 | 20 49 53 50 52 49 56 41 |n_flag &| ISPRIVA|
|000022c0| 54 45 29 0a 09 09 09 63 | 6f 6e 74 69 6e 75 65 3b |TE)....c|ontinue;|
|000022d0| 0a 09 09 63 6f 75 6e 74 | 20 3d 20 31 3b 0a 09 09 |...count| = 1;...|
|000022e0| 70 72 6f 62 65 20 3d 20 | 66 6f 6c 64 28 54 61 62 |probe = |fold(Tab|
|000022f0| 6c 65 5b 69 5d 2d 3e 6e | 5f 6e 61 6d 65 29 3b 0a |le[i]->n|_name);.|
|00002300| 09 09 2f 2a 20 64 6f 6e | 27 74 20 63 68 61 6e 67 |../* don|'t chang|
|00002310| 65 20 74 68 65 20 6f 72 | 64 65 72 20 6f 66 20 74 |e the or|der of t|
|00002320| 68 65 20 6e 65 78 74 20 | 74 77 6f 20 6c 69 6e 65 |he next |two line|
|00002330| 73 20 2a 2f 0a 09 09 68 | 61 73 68 32 20 3d 20 48 |s */...h|ash2 = H|
|00002340| 41 53 48 32 28 70 72 6f | 62 65 29 3b 0a 09 09 70 |ASH2(pro|be);...p|
|00002350| 72 6f 62 65 20 3d 20 48 | 41 53 48 31 28 70 72 6f |robe = H|ASH1(pro|
|00002360| 62 65 29 3b 0a 09 09 2f | 2a 20 74 68 61 6e 6b 20 |be);.../|* thank |
|00002370| 79 6f 75 21 20 2a 2f 0a | 09 09 77 68 69 6c 65 20 |you! */.|..while |
|00002380| 28 54 61 62 6c 65 5b 70 | 72 6f 62 65 5d 20 21 3d |(Table[p|robe] !=|
|00002390| 20 30 0a 09 09 20 20 20 | 20 26 26 20 73 74 72 63 | 0...   | && strc|
|000023a0| 6d 70 28 54 61 62 6c 65 | 5b 70 72 6f 62 65 5d 2d |mp(Table|[probe]-|
|000023b0| 3e 6e 5f 6e 61 6d 65 2c | 20 54 61 62 6c 65 5b 69 |>n_name,| Table[i|
|000023c0| 5d 2d 3e 6e 5f 6e 61 6d | 65 29 20 21 3d 20 30 29 |]->n_nam|e) != 0)|
|000023d0| 20 7b 0a 09 09 09 63 6f | 75 6e 74 2b 2b 3b 0a 09 | {....co|unt++;..|
|000023e0| 09 09 70 72 6f 62 65 20 | 2d 3d 20 68 61 73 68 32 |..probe |-= hash2|
|000023f0| 3b 0a 09 09 09 69 66 20 | 28 70 72 6f 62 65 20 3c |;....if |(probe <|
|00002400| 20 30 29 0a 09 09 09 09 | 70 72 6f 62 65 20 2b 3d | 0).....|probe +=|
|00002410| 20 54 61 62 73 69 7a 65 | 3b 0a 09 09 7d 0a 09 09 | Tabsize|;...}...|
|00002420| 69 66 20 28 54 61 62 6c | 65 5b 70 72 6f 62 65 5d |if (Tabl|e[probe]|
|00002430| 20 3d 3d 20 30 29 20 7b | 0a 09 09 09 66 70 72 69 | == 0) {|....fpri|
|00002440| 6e 74 66 28 73 74 64 65 | 72 72 2c 20 22 25 73 3a |ntf(stde|rr, "%s:|
|00002450| 20 69 6d 70 6f 73 73 69 | 62 6c 65 20 68 61 73 68 | impossi|ble hash|
|00002460| 20 65 72 72 6f 72 20 66 | 6f 72 20 25 73 5c 6e 22 | error f|or %s\n"|
|00002470| 2c 0a 09 09 09 09 09 50 | 72 6f 67 4e 61 6d 65 2c |,......P|rogName,|
|00002480| 20 54 61 62 6c 65 5b 69 | 5d 2d 3e 6e 5f 6e 61 6d | Table[i|]->n_nam|
|00002490| 65 29 3b 0a 09 09 09 62 | 61 64 6d 61 67 69 63 28 |e);....b|admagic(|
|000024a0| 31 29 3b 0a 09 09 7d 0a | 09 09 0a 09 09 74 6f 74 |1);...}.|.....tot|
|000024b0| 61 6c 20 2b 3d 20 63 6f | 75 6e 74 3b 0a 09 09 73 |al += co|unt;...s|
|000024c0| 6c 6f 74 73 2b 2b 3b 0a | 09 09 69 66 20 28 63 6f |lots++;.|..if (co|
|000024d0| 75 6e 74 20 3e 20 6c 6f | 6e 67 65 73 74 29 0a 09 |unt > lo|ngest)..|
|000024e0| 09 09 6c 6f 6e 67 65 73 | 74 20 3d 20 63 6f 75 6e |..longes|t = coun|
|000024f0| 74 3b 0a 09 09 69 66 20 | 28 63 6f 75 6e 74 20 3e |t;...if |(count >|
|00002500| 3d 20 6e 73 6c 6f 74 73 | 29 0a 09 09 09 63 6f 75 |= nslots|)....cou|
|00002510| 6e 74 20 3d 20 30 3b 0a | 09 09 63 6f 6c 6c 69 73 |nt = 0;.|..collis|
|00002520| 69 6f 6e 5b 63 6f 75 6e | 74 5d 2b 2b 3b 0a 09 7d |ion[coun|t]++;..}|
|00002530| 0a 09 66 6f 72 20 28 69 | 20 3d 20 31 3b 20 69 20 |..for (i| = 1; i |
|00002540| 3c 20 6e 73 6c 6f 74 73 | 3b 20 69 2b 2b 29 0a 09 |< nslots|; i++)..|
|00002550| 09 69 66 20 28 63 6f 6c | 6c 69 73 69 6f 6e 5b 69 |.if (col|lision[i|
|00002560| 5d 29 0a 09 09 09 66 70 | 72 69 6e 74 66 28 73 74 |])....fp|rintf(st|
|00002570| 64 65 72 72 2c 20 22 25 | 64 20 63 68 61 69 6e 73 |derr, "%|d chains|
|00002580| 3a 20 25 64 20 28 25 6c | 64 25 25 29 5c 6e 22 2c |: %d (%l|d%%)\n",|
|00002590| 0a 09 09 09 09 69 2c 20 | 63 6f 6c 6c 69 73 69 6f |.....i, |collisio|
|000025a0| 6e 5b 69 5d 2c 20 28 63 | 6f 6c 6c 69 73 69 6f 6e |n[i], (c|ollision|
|000025b0| 5b 69 5d 20 2a 20 31 30 | 30 4c 29 2f 20 73 6c 6f |[i] * 10|0L)/ slo|
|000025c0| 74 73 29 3b 0a 09 09 69 | 66 20 28 63 6f 6c 6c 69 |ts);...i|f (colli|
|000025d0| 73 69 6f 6e 5b 30 5d 29 | 0a 09 09 09 66 70 72 69 |sion[0])|....fpri|
|000025e0| 6e 74 66 28 73 74 64 65 | 72 72 2c 20 22 3e 20 25 |ntf(stde|rr, "> %|
|000025f0| 64 20 63 68 61 69 6e 73 | 3a 20 25 64 20 28 25 6c |d chains|: %d (%l|
|00002600| 64 25 25 29 5c 6e 22 2c | 0a 09 09 09 09 6e 73 6c |d%%)\n",|.....nsl|
|00002610| 6f 74 73 20 2d 20 31 2c | 20 63 6f 6c 6c 69 73 69 |ots - 1,| collisi|
|00002620| 6f 6e 5b 30 5d 2c 0a 09 | 09 09 09 28 63 6f 6c 6c |on[0],..|...(coll|
|00002630| 69 73 69 6f 6e 5b 30 5d | 20 2a 20 31 30 30 4c 29 |ision[0]| * 100L)|
|00002640| 2f 20 73 6c 6f 74 73 29 | 3b 0a 09 66 70 72 69 6e |/ slots)|;..fprin|
|00002650| 74 66 28 73 74 64 65 72 | 72 2c 20 22 25 32 2e 32 |tf(stder|r, "%2.2|
|00002660| 66 20 70 72 6f 62 65 73 | 20 70 65 72 20 61 63 63 |f probes| per acc|
|00002670| 65 73 73 2c 20 6c 6f 6e | 67 65 73 74 20 63 68 61 |ess, lon|gest cha|
|00002680| 69 6e 3a 20 25 64 5c 6e | 22 2c 0a 09 09 28 64 6f |in: %d\n|",...(do|
|00002690| 75 62 6c 65 29 20 74 6f | 74 61 6c 20 2f 20 73 6c |uble) to|tal / sl|
|000026a0| 6f 74 73 2c 20 6c 6f 6e | 67 65 73 74 29 3b 0a 7d |ots, lon|gest);.}|
|000026b0| 0a 0a 53 54 41 54 49 43 | 20 76 6f 69 64 0a 6c 6f |..STATIC| void.lo|
|000026c0| 77 65 72 63 61 73 65 28 | 73 29 0a 72 65 67 69 73 |wercase(|s).regis|
|000026d0| 74 65 72 20 63 68 61 72 | 09 2a 73 3b 0a 7b 0a 09 |ter char|.*s;.{..|
|000026e0| 64 6f 20 7b 0a 09 09 69 | 66 20 28 69 73 75 70 70 |do {...i|f (isupp|
|000026f0| 65 72 28 2a 73 29 29 0a | 09 09 09 2a 73 20 2d 3d |er(*s)).|...*s -=|
|00002700| 20 27 41 27 20 2d 20 27 | 61 27 3b 09 2f 2a 20 61 | 'A' - '|a';./* a|
|00002710| 73 73 75 6d 65 73 20 41 | 53 43 49 49 20 2a 2f 0a |ssumes A|SCII */.|
|00002720| 09 7d 20 77 68 69 6c 65 | 20 28 2a 73 2b 2b 29 3b |.} while| (*s++);|
|00002730| 0a 7d 0a 0a 2f 2a 0a 20 | 2a 20 74 68 69 73 20 6d |.}../*. |* this m|
|00002740| 69 67 68 74 20 68 61 76 | 65 20 74 6f 20 62 65 20 |ight hav|e to be |
|00002750| 72 65 63 6f 64 65 64 20 | 66 6f 72 20 70 65 72 66 |recoded |for perf|
|00002760| 6f 72 6d 61 6e 63 65 20 | 69 66 20 70 72 69 76 61 |ormance |if priva|
|00002770| 74 65 73 20 63 61 74 63 | 68 20 6f 6e 0a 20 2a 2f |tes catc|h on. */|
|00002780| 0a 53 54 41 54 49 43 20 | 6e 6f 64 65 09 2a 0a 69 |.STATIC |node.*.i|
|00002790| 73 70 72 69 76 61 74 65 | 28 6e 61 6d 65 29 0a 72 |sprivate|(name).r|
|000027a0| 65 67 69 73 74 65 72 20 | 63 68 61 72 09 2a 6e 61 |egister |char.*na|
|000027b0| 6d 65 3b 0a 7b 0a 09 72 | 65 67 69 73 74 65 72 20 |me;.{..r|egister |
|000027c0| 6e 6f 64 65 09 2a 6e 3b | 0a 0a 09 66 6f 72 20 28 |node.*n;|...for (|
|000027d0| 6e 20 3d 20 50 72 69 76 | 61 74 65 3b 20 6e 20 21 |n = Priv|ate; n !|
|000027e0| 3d 20 30 3b 20 6e 20 3d | 20 6e 2d 3e 6e 5f 70 72 |= 0; n =| n->n_pr|
|000027f0| 69 76 61 74 65 29 0a 09 | 09 69 66 20 28 73 74 72 |ivate)..|.if (str|
|00002800| 63 6d 70 28 6e 61 6d 65 | 2c 20 6e 2d 3e 6e 5f 6e |cmp(name|, n->n_n|
|00002810| 61 6d 65 29 20 3d 3d 20 | 30 29 0a 09 09 09 72 65 |ame) == |0)....re|
|00002820| 74 75 72 6e 28 6e 29 3b | 0a 09 72 65 74 75 72 6e |turn(n);|..return|
|00002830| 28 30 29 3b 0a 7d 0a 0a | 66 69 78 70 72 69 76 61 |(0);.}..|fixpriva|
|00002840| 74 65 28 29 0a 7b 0a 09 | 72 65 67 69 73 74 65 72 |te().{..|register|
|00002850| 20 6e 6f 64 65 09 2a 6e | 2c 20 2a 6e 65 78 74 3b | node.*n|, *next;|
|00002860| 0a 09 72 65 67 69 73 74 | 65 72 20 6c 6f 6e 67 09 |..regist|er long.|
|00002870| 69 3b 0a 0a 09 66 6f 72 | 20 28 6e 20 3d 20 50 72 |i;...for| (n = Pr|
|00002880| 69 76 61 74 65 3b 20 6e | 20 21 3d 20 30 3b 20 6e |ivate; n| != 0; n|
|00002890| 20 3d 20 6e 65 78 74 29 | 20 7b 0a 09 09 6e 2d 3e | = next)| {...n->|
|000028a0| 6e 5f 66 6c 61 67 20 7c | 3d 20 49 53 50 52 49 56 |n_flag ||= ISPRIV|
|000028b0| 41 54 45 3b 09 09 2f 2a | 20 6f 76 65 72 6b 69 6c |ATE;../*| overkil|
|000028c0| 6c 2c 20 62 75 74 20 73 | 61 66 65 20 2a 2f 0a 09 |l, but s|afe */..|
|000028d0| 09 69 20 3d 20 68 61 73 | 68 28 6e 2d 3e 6e 5f 6e |.i = has|h(n->n_n|
|000028e0| 61 6d 65 2c 20 31 29 3b | 0a 09 09 69 66 20 28 54 |ame, 1);|...if (T|
|000028f0| 61 62 6c 65 5b 69 5d 20 | 21 3d 20 30 29 20 7b 0a |able[i] |!= 0) {.|
|00002900| 09 09 09 66 70 72 69 6e | 74 66 28 73 74 64 65 72 |...fprin|tf(stder|
|00002910| 72 2c 20 22 25 73 3a 20 | 69 6d 70 6f 73 73 69 62 |r, "%s: |impossib|
|00002920| 6c 65 20 70 72 69 76 61 | 74 65 20 6e 6f 64 65 20 |le priva|te node |
|00002930| 65 72 72 6f 72 20 6f 6e | 20 25 73 5c 6e 22 2c 0a |error on| %s\n",.|
|00002940| 09 09 09 09 50 72 6f 67 | 4e 61 6d 65 2c 20 6e 2d |....Prog|Name, n-|
|00002950| 3e 6e 5f 6e 61 6d 65 29 | 3b 0a 09 09 09 62 61 64 |>n_name)|;....bad|
|00002960| 6d 61 67 69 63 28 31 29 | 3b 0a 09 09 7d 0a 09 0a |magic(1)|;...}...|
|00002970| 09 09 54 61 62 6c 65 5b | 69 5d 20 3d 20 6e 3b 0a |..Table[|i] = n;.|
|00002980| 09 09 6e 2d 3e 6e 5f 74 | 6c 6f 63 20 3d 20 69 3b |..n->n_t|loc = i;|
|00002990| 09 2f 2a 20 65 73 73 65 | 6e 74 69 61 6c 6c 79 20 |./* esse|ntially |
|000029a0| 61 20 62 61 63 6b 20 6c | 69 6e 6b 20 74 6f 20 74 |a back l|ink to t|
|000029b0| 68 65 20 74 61 62 6c 65 | 20 2a 2f 0a 09 09 6e 65 |he table| */...ne|
|000029c0| 78 74 20 3d 20 6e 2d 3e | 6e 5f 70 72 69 76 61 74 |xt = n->|n_privat|
|000029d0| 65 3b 0a 09 09 6e 2d 3e | 6e 5f 70 72 69 76 61 74 |e;...n->|n_privat|
|000029e0| 65 20 3d 20 30 3b 09 2f | 2a 20 63 6c 65 61 72 20 |e = 0;./|* clear |
|000029f0| 66 6f 72 20 6c 61 74 65 | 72 20 75 73 65 20 2a 2f |for late|r use */|
|00002a00| 0a 09 7d 0a 09 50 72 69 | 76 61 74 65 20 3d 20 30 |..}..Pri|vate = 0|
|00002a10| 3b 0a 7d 0a 0a 6e 6f 64 | 65 09 2a 0a 61 64 64 70 |;.}..nod|e.*.addp|
|00002a20| 72 69 76 61 74 65 28 6e | 61 6d 65 29 0a 72 65 67 |rivate(n|ame).reg|
|00002a30| 69 73 74 65 72 20 63 68 | 61 72 09 2a 6e 61 6d 65 |ister ch|ar.*name|
|00002a40| 3b 0a 7b 0a 09 72 65 67 | 69 73 74 65 72 20 6e 6f |;.{..reg|ister no|
|00002a50| 64 65 09 2a 6e 3b 0a 0a | 09 69 66 20 28 49 66 6c |de.*n;..|.if (Ifl|
|00002a60| 61 67 29 0a 09 09 6c 6f | 77 65 72 63 61 73 65 28 |ag)...lo|wercase(|
|00002a70| 6e 61 6d 65 29 3b 0a 09 | 69 66 20 28 28 6e 20 3d |name);..|if ((n =|
|00002a80| 20 69 73 70 72 69 76 61 | 74 65 28 6e 61 6d 65 29 | ispriva|te(name)|
|00002a90| 29 20 21 3d 20 30 29 0a | 09 09 72 65 74 75 72 6e |) != 0).|..return|
|00002aa0| 28 6e 29 3b 0a 0a 09 6e | 20 3d 20 6e 65 77 6e 6f |(n);...n| = newno|
|00002ab0| 64 65 28 29 3b 0a 09 6e | 2d 3e 6e 5f 6e 61 6d 65 |de();..n|->n_name|
|00002ac0| 20 3d 20 73 74 72 73 61 | 76 65 28 6e 61 6d 65 29 | = strsa|ve(name)|
|00002ad0| 3b 0a 09 6e 2d 3e 6e 5f | 70 72 69 76 61 74 65 20 |;..n->n_|private |
|00002ae0| 3d 20 50 72 69 76 61 74 | 65 3b 0a 09 50 72 69 76 |= Privat|e;..Priv|
|00002af0| 61 74 65 20 3d 20 6e 3b | 0a 09 72 65 74 75 72 6e |ate = n;|..return|
|00002b00| 28 6e 29 3b 0a 7d 0a 53 | 48 41 52 5f 45 4f 46 0a |(n);.}.S|HAR_EOF.|
|00002b10| 69 66 20 74 65 73 74 20 | 36 35 38 35 20 2d 6e 65 |if test |6585 -ne|
|00002b20| 20 22 60 77 63 20 2d 63 | 20 3c 20 27 61 64 64 6e | "`wc -c| < 'addn|
|00002b30| 6f 64 65 2e 63 27 60 22 | 0a 74 68 65 6e 0a 09 65 |ode.c'`"|.then..e|
|00002b40| 63 68 6f 20 73 68 61 72 | 3a 20 65 72 72 6f 72 20 |cho shar|: error |
|00002b50| 74 72 61 6e 73 6d 69 74 | 74 69 6e 67 20 22 27 61 |transmit|ting "'a|
|00002b60| 64 64 6e 6f 64 65 2e 63 | 27 22 20 27 28 73 68 6f |ddnode.c|'" '(sho|
|00002b70| 75 6c 64 20 68 61 76 65 | 20 62 65 65 6e 20 36 35 |uld have| been 65|
|00002b80| 38 35 20 63 68 61 72 61 | 63 74 65 72 73 29 27 0a |85 chara|cters)'.|
|00002b90| 66 69 0a 66 69 0a 65 63 | 68 6f 20 73 68 61 72 3a |fi.fi.ec|ho shar:|
|00002ba0| 20 65 78 74 72 61 63 74 | 69 6e 67 20 22 27 65 78 | extract|ing "'ex|
|00002bb0| 74 65 72 6e 2e 63 27 22 | 20 27 28 36 35 30 20 63 |tern.c'"| '(650 c|
|00002bc0| 68 61 72 61 63 74 65 72 | 73 29 27 0a 69 66 20 74 |haracter|s)'.if t|
|00002bd0| 65 73 74 20 2d 66 20 27 | 65 78 74 65 72 6e 2e 63 |est -f '|extern.c|
|00002be0| 27 0a 74 68 65 6e 0a 09 | 65 63 68 6f 20 73 68 61 |'.then..|echo sha|
|00002bf0| 72 3a 20 77 69 6c 6c 20 | 6e 6f 74 20 6f 76 65 72 |r: will |not over|
|00002c00| 2d 77 72 69 74 65 20 65 | 78 69 73 74 69 6e 67 20 |-write e|xisting |
|00002c10| 66 69 6c 65 20 22 27 65 | 78 74 65 72 6e 2e 63 27 |file "'e|xtern.c'|
|00002c20| 22 0a 65 6c 73 65 0a 63 | 61 74 20 3c 3c 20 5c 53 |".else.c|at << \S|
|00002c30| 48 41 52 5f 45 4f 46 20 | 3e 20 27 65 78 74 65 72 |HAR_EOF |> 'exter|
|00002c40| 6e 2e 63 27 0a 2f 2a 20 | 70 61 74 68 61 6c 69 61 |n.c'./* |pathalia|
|00002c50| 73 20 2d 2d 20 62 79 20 | 73 74 65 76 65 20 62 65 |s -- by |steve be|
|00002c60| 6c 6c 6f 76 69 6e 2c 20 | 61 73 20 74 6f 6c 64 20 |llovin, |as told |
|00002c70| 74 6f 20 70 65 74 65 72 | 20 68 6f 6e 65 79 6d 61 |to peter| honeyma|
|00002c80| 6e 20 2a 2f 0a 23 69 66 | 6e 64 65 66 20 6c 69 6e |n */.#if|ndef lin|
|00002c90| 74 0a 73 74 61 74 69 63 | 20 63 68 61 72 09 2a 73 |t.static| char.*s|
|00002ca0| 63 63 73 69 64 20 3d 20 | 22 40 28 23 29 65 78 74 |ccsid = |"@(#)ext|
|00002cb0| 65 72 6e 2e 63 09 38 2e | 31 20 28 64 6f 77 6e 21 |ern.c.8.|1 (down!|
|00002cc0| 68 6f 6e 65 79 29 20 38 | 36 2f 30 31 2f 31 39 22 |honey) 8|6/01/19"|
|00002cd0| 3b 0a 23 65 6e 64 69 66 | 20 6c 69 6e 74 0a 0a 23 |;.#endif| lint..#|
|00002ce0| 69 6e 63 6c 75 64 65 20 | 22 64 65 66 2e 68 22 0a |include |"def.h".|
|00002cf0| 0a 6e 6f 64 65 09 2a 48 | 6f 6d 65 3b 0a 63 68 61 |.node.*H|ome;.cha|
|00002d00| 72 09 2a 43 66 69 6c 65 | 3b 0a 63 68 61 72 09 2a |r.*Cfile|;.char.*|
|00002d10| 2a 49 66 69 6c 65 73 3b | 0a 63 68 61 72 09 2a 50 |*Ifiles;|.char.*P|
|00002d20| 72 6f 67 4e 61 6d 65 3b | 0a 69 6e 74 09 56 66 6c |rogName;|.int.Vfl|
|00002d30| 61 67 3b 0a 69 6e 74 09 | 43 66 6c 61 67 3b 0a 69 |ag;.int.|Cflag;.i|
|00002d40| 6e 74 09 49 66 6c 61 67 | 3b 0a 69 6e 74 09 54 66 |nt.Iflag|;.int.Tf|
|00002d50| 6c 61 67 3b 0a 69 6e 74 | 09 4c 69 6e 65 6e 6f 20 |lag;.int|.Lineno |
|00002d60| 3d 20 31 3b 0a 63 68 61 | 72 09 2a 4e 65 74 63 68 |= 1;.cha|r.*Netch|
|00002d70| 61 72 73 20 3d 20 22 21 | 3a 40 25 22 3b 09 2f 2a |ars = "!|:@%";./*|
|00002d80| 20 73 70 61 72 73 65 2c | 20 62 75 74 20 73 75 66 | sparse,| but suf|
|00002d90| 66 69 63 69 65 6e 74 20 | 2a 2f 0a 69 6e 74 09 4e |ficient |*/.int.N|
|00002da0| 63 6f 75 6e 74 3b 0a 69 | 6e 74 09 4c 63 6f 75 6e |count;.i|nt.Lcoun|
|00002db0| 74 3b 0a 63 68 61 72 09 | 2a 47 72 61 70 68 6f 75 |t;.char.|*Graphou|
|00002dc0| 74 3b 0a 63 68 61 72 09 | 2a 4c 69 6e 6b 6f 75 74 |t;.char.|*Linkout|
|00002dd0| 3b 0a 6e 6f 64 65 09 2a | 2a 54 61 62 6c 65 3b 09 |;.node.*|*Table;.|
|00002de0| 09 2f 2a 20 68 61 73 68 | 20 74 61 62 6c 65 20 2b |./* hash| table +|
|00002df0| 20 70 72 69 6f 72 69 74 | 79 20 71 75 65 75 65 20 | priorit|y queue |
|00002e00| 2a 2f 0a 6c 6f 6e 67 09 | 54 61 62 73 69 7a 65 3b |*/.long.|Tabsize;|
|00002e10| 09 09 2f 2a 20 73 69 7a | 65 20 6f 66 20 54 61 62 |../* siz|e of Tab|
|00002e20| 6c 65 20 2a 2f 09 0a 6e | 6f 64 65 09 2a 50 72 69 |le */..n|ode.*Pri|
|00002e30| 76 61 74 65 3b 09 09 2f | 2a 20 6c 69 73 74 20 6f |vate;../|* list o|
|00002e40| 66 20 70 72 69 76 61 74 | 65 20 6e 6f 64 65 73 20 |f privat|e nodes |
|00002e50| 69 6e 20 74 68 69 73 20 | 66 69 6c 65 20 2a 2f 0a |in this |file */.|
|00002e60| 6c 6f 6e 67 09 48 61 73 | 68 70 61 72 74 3b 09 09 |long.Has|hpart;..|
|00002e70| 2f 2a 20 75 73 65 64 20 | 77 68 69 6c 65 20 6d 61 |/* used |while ma|
|00002e80| 70 70 69 6e 67 20 2d 2d | 20 61 62 6f 76 65 20 69 |pping --| above i|
|00002e90| 73 20 68 65 61 70 20 2a | 2f 0a 69 6e 74 09 53 63 |s heap *|/.int.Sc|
|00002ea0| 61 6e 73 74 61 74 65 20 | 3d 20 4e 45 57 4c 49 4e |anstate |= NEWLIN|
|00002eb0| 45 3b 09 2f 2a 20 73 63 | 61 6e 6e 65 72 20 28 79 |E;./* sc|anner (y|
|00002ec0| 79 6c 65 78 29 20 73 74 | 61 74 65 20 2a 2f 0a 53 |ylex) st|ate */.S|
|00002ed0| 48 41 52 5f 45 4f 46 0a | 69 66 20 74 65 73 74 20 |HAR_EOF.|if test |
|00002ee0| 36 35 30 20 2d 6e 65 20 | 22 60 77 63 20 2d 63 20 |650 -ne |"`wc -c |
|00002ef0| 3c 20 27 65 78 74 65 72 | 6e 2e 63 27 60 22 0a 74 |< 'exter|n.c'`".t|
|00002f00| 68 65 6e 0a 09 65 63 68 | 6f 20 73 68 61 72 3a 20 |hen..ech|o shar: |
|00002f10| 65 72 72 6f 72 20 74 72 | 61 6e 73 6d 69 74 74 69 |error tr|ansmitti|
|00002f20| 6e 67 20 22 27 65 78 74 | 65 72 6e 2e 63 27 22 20 |ng "'ext|ern.c'" |
|00002f30| 27 28 73 68 6f 75 6c 64 | 20 68 61 76 65 20 62 65 |'(should| have be|
|00002f40| 65 6e 20 36 35 30 20 63 | 68 61 72 61 63 74 65 72 |en 650 c|haracter|
|00002f50| 73 29 27 0a 66 69 0a 66 | 69 0a 65 63 68 6f 20 73 |s)'.fi.f|i.echo s|
|00002f60| 68 61 72 3a 20 65 78 74 | 72 61 63 74 69 6e 67 20 |har: ext|racting |
|00002f70| 22 27 6c 6f 63 61 6c 2e | 63 27 22 20 27 28 31 34 |"'local.|c'" '(14|
|00002f80| 32 36 20 63 68 61 72 61 | 63 74 65 72 73 29 27 0a |26 chara|cters)'.|
|00002f90| 69 66 20 74 65 73 74 20 | 2d 66 20 27 6c 6f 63 61 |if test |-f 'loca|
|00002fa0| 6c 2e 63 27 0a 74 68 65 | 6e 0a 09 65 63 68 6f 20 |l.c'.the|n..echo |
|00002fb0| 73 68 61 72 3a 20 77 69 | 6c 6c 20 6e 6f 74 20 6f |shar: wi|ll not o|
|00002fc0| 76 65 72 2d 77 72 69 74 | 65 20 65 78 69 73 74 69 |ver-writ|e existi|
|00002fd0| 6e 67 20 66 69 6c 65 20 | 22 27 6c 6f 63 61 6c 2e |ng file |"'local.|
|00002fe0| 63 27 22 0a 65 6c 73 65 | 0a 63 61 74 20 3c 3c 20 |c'".else|.cat << |
|00002ff0| 5c 53 48 41 52 5f 45 4f | 46 20 3e 20 27 6c 6f 63 |\SHAR_EO|F > 'loc|
|00003000| 61 6c 2e 63 27 0a 2f 2a | 20 70 61 74 68 61 6c 69 |al.c'./*| pathali|
|00003010| 61 73 20 2d 2d 20 62 79 | 20 73 74 65 76 65 20 62 |as -- by| steve b|
|00003020| 65 6c 6c 6f 76 69 6e 2c | 20 61 73 20 74 6f 6c 64 |ellovin,| as told|
|00003030| 20 74 6f 20 70 65 74 65 | 72 20 68 6f 6e 65 79 6d | to pete|r honeym|
|00003040| 61 6e 20 2a 2f 0a 23 69 | 66 6e 64 65 66 20 6c 69 |an */.#i|fndef li|
|00003050| 6e 74 0a 73 74 61 74 69 | 63 20 63 68 61 72 09 2a |nt.stati|c char.*|
|00003060| 73 63 63 73 69 64 20 3d | 20 22 40 28 23 29 6c 6f |sccsid =| "@(#)lo|
|00003070| 63 61 6c 2e 63 09 38 2e | 31 20 28 64 6f 77 6e 21 |cal.c.8.|1 (down!|
|00003080| 68 6f 6e 65 79 29 20 38 | 36 2f 30 31 2f 31 39 22 |honey) 8|6/01/19"|
|00003090| 3b 0a 23 65 6e 64 69 66 | 20 6c 69 6e 74 0a 0a 23 |;.#endif| lint..#|
|000030a0| 69 6e 63 6c 75 64 65 20 | 3c 73 74 64 69 6f 2e 68 |include |<stdio.h|
|000030b0| 3e 0a 23 69 6e 63 6c 75 | 64 65 20 22 63 6f 6e 66 |>.#inclu|de "conf|
|000030c0| 69 67 2e 68 22 0a 0a 23 | 69 66 64 65 66 09 55 4e |ig.h"..#|ifdef.UN|
|000030d0| 41 4d 45 0a 23 69 6e 63 | 6c 75 64 65 20 3c 73 79 |AME.#inc|lude <sy|
|000030e0| 73 2f 75 74 73 6e 61 6d | 65 2e 68 3e 0a 0a 63 68 |s/utsnam|e.h>..ch|
|000030f0| 61 72 09 2a 0a 6c 6f 63 | 61 6c 28 29 0a 7b 0a 09 |ar.*.loc|al().{..|
|00003100| 73 74 61 74 69 63 20 73 | 74 72 75 63 74 20 75 74 |static s|truct ut|
|00003110| 73 6e 61 6d 65 20 75 74 | 73 6e 61 6d 65 3b 0a 0a |sname ut|sname;..|
|00003120| 09 75 6e 61 6d 65 28 26 | 75 74 73 6e 61 6d 65 29 |.uname(&|utsname)|
|00003130| 3b 0a 09 72 65 74 75 72 | 6e 28 75 74 73 6e 61 6d |;..retur|n(utsnam|
|00003140| 65 2e 6e 6f 64 65 6e 61 | 6d 65 29 3b 0a 7d 0a 0a |e.nodena|me);.}..|
|00003150| 23 65 6c 73 65 20 21 55 | 4e 41 4d 45 0a 0a 63 68 |#else !U|NAME..ch|
|00003160| 61 72 09 2a 0a 6c 6f 63 | 61 6c 28 29 0a 7b 0a 09 |ar.*.loc|al().{..|
|00003170| 73 74 61 74 69 63 20 63 | 68 61 72 20 6c 6e 61 6d |static c|har lnam|
|00003180| 65 5b 36 34 5d 3b 0a 09 | 76 6f 69 64 09 67 65 74 |e[64];..|void.get|
|00003190| 68 6f 73 74 6e 61 6d 65 | 28 29 3b 0a 0a 09 67 65 |hostname|();...ge|
|000031a0| 74 68 6f 73 74 6e 61 6d | 65 28 6c 6e 61 6d 65 2c |thostnam|e(lname,|
|000031b0| 20 73 69 7a 65 6f 66 28 | 6c 6e 61 6d 65 29 29 3b | sizeof(|lname));|
|000031c0| 0a 09 72 65 74 75 72 6e | 28 6c 6e 61 6d 65 29 3b |..return|(lname);|
|000031d0| 0a 7d 0a 0a 23 69 66 6e | 64 65 66 20 47 45 54 48 |.}..#ifn|def GETH|
|000031e0| 4f 53 54 4e 41 4d 45 0a | 0a 73 74 61 74 69 63 20 |OSTNAME.|.static |
|000031f0| 76 6f 69 64 0a 67 65 74 | 68 6f 73 74 6e 61 6d 65 |void.get|hostname|
|00003200| 28 6e 61 6d 65 2c 20 6c | 65 6e 29 0a 63 68 61 72 |(name, l|en).char|
|00003210| 09 2a 6e 61 6d 65 3b 0a | 7b 0a 09 46 49 4c 45 09 |.*name;.|{..FILE.|
|00003220| 2a 77 68 6f 61 6d 69 2c | 20 2a 66 6f 70 65 6e 28 |*whoami,| *fopen(|
|00003230| 29 2c 20 2a 70 6f 70 65 | 6e 28 29 3b 0a 09 63 68 |), *pope|n();..ch|
|00003240| 61 72 09 2a 70 74 72 2c | 20 2a 69 6e 64 65 78 28 |ar.*ptr,| *index(|
|00003250| 29 3b 0a 0a 09 2a 6e 61 | 6d 65 20 3d 20 27 5c 30 |);...*na|me = '\0|
|00003260| 27 3b 0a 0a 09 2f 2a 20 | 74 72 79 20 2f 65 74 63 |';.../* |try /etc|
|00003270| 2f 77 68 6f 61 6d 69 20 | 2a 2f 0a 09 69 66 20 28 |/whoami |*/..if (|
|00003280| 28 77 68 6f 61 6d 69 20 | 3d 20 66 6f 70 65 6e 28 |(whoami |= fopen(|
|00003290| 22 2f 65 74 63 2f 77 68 | 6f 61 6d 69 22 2c 20 22 |"/etc/wh|oami", "|
|000032a0| 72 22 29 29 20 21 3d 20 | 30 29 20 7b 0a 09 09 28 |r")) != |0) {...(|
|000032b0| 76 6f 69 64 29 20 66 67 | 65 74 73 28 6e 61 6d 65 |void) fg|ets(name|
|000032c0| 2c 20 6c 65 6e 2c 20 77 | 68 6f 61 6d 69 29 3b 0a |, len, w|hoami);.|
|000032d0| 09 09 28 76 6f 69 64 29 | 20 66 63 6c 6f 73 65 28 |..(void)| fclose(|
|000032e0| 77 68 6f 61 6d 69 29 3b | 0a 09 09 69 66 20 28 28 |whoami);|...if ((|
|000032f0| 70 74 72 20 3d 20 69 6e | 64 65 78 28 6e 61 6d 65 |ptr = in|dex(name|
|00003300| 2c 20 27 5c 6e 27 29 29 | 20 21 3d 20 30 29 0a 09 |, '\n'))| != 0)..|
|00003310| 09 09 2a 70 74 72 20 3d | 20 27 5c 30 27 3b 0a 09 |..*ptr =| '\0';..|
|00003320| 7d 0a 09 69 66 20 28 2a | 6e 61 6d 65 29 0a 09 09 |}..if (*|name)...|
|00003330| 72 65 74 75 72 6e 3b 0a | 0a 09 2f 2a 20 74 72 79 |return;.|../* try|
|00003340| 20 2f 75 73 72 2f 69 6e | 63 6c 75 64 65 2f 77 68 | /usr/in|clude/wh|
|00003350| 6f 61 6d 69 2e 68 20 2a | 2f 0a 09 69 66 20 28 28 |oami.h *|/..if ((|
|00003360| 77 68 6f 61 6d 69 20 3d | 20 66 6f 70 65 6e 28 22 |whoami =| fopen("|
|00003370| 2f 75 73 72 2f 69 6e 63 | 6c 75 64 65 2f 77 68 6f |/usr/inc|lude/who|
|00003380| 61 6d 69 2e 68 22 2c 20 | 22 72 22 29 29 20 21 3d |ami.h", |"r")) !=|
|00003390| 20 30 29 20 7b 0a 09 09 | 77 68 69 6c 65 20 28 21 | 0) {...|while (!|
|000033a0| 66 65 6f 66 28 77 68 6f | 61 6d 69 29 29 20 7b 0a |feof(who|ami)) {.|
|000033b0| 09 09 09 63 68 61 72 09 | 62 75 66 5b 31 30 30 5d |...char.|buf[100]|
|000033c0| 3b 0a 0a 09 09 09 69 66 | 20 28 66 67 65 74 73 28 |;.....if| (fgets(|
|000033d0| 62 75 66 2c 20 31 30 30 | 2c 20 77 68 6f 61 6d 69 |buf, 100|, whoami|
|000033e0| 29 20 3d 3d 20 30 29 0a | 09 09 09 09 62 72 65 61 |) == 0).|....brea|
|000033f0| 6b 3b 0a 09 09 09 69 66 | 20 28 73 73 63 61 6e 66 |k;....if| (sscanf|
|00003400| 28 62 75 66 2c 20 22 23 | 64 65 66 69 6e 65 20 73 |(buf, "#|define s|
|00003410| 79 73 6e 61 6d 65 20 5c | 22 25 5b 5e 5c 22 5d 5c |ysname \|"%[^\"]\|
|00003420| 22 22 2c 20 6e 61 6d 65 | 29 29 0a 09 09 09 09 62 |"", name|)).....b|
|00003430| 72 65 61 6b 3b 0a 09 09 | 7d 0a 09 09 28 76 6f 69 |reak;...|}...(voi|
|00003440| 64 29 20 66 63 6c 6f 73 | 65 28 77 68 6f 61 6d 69 |d) fclos|e(whoami|
|00003450| 29 3b 0a 09 09 69 66 20 | 28 2a 6e 61 6d 65 29 0a |);...if |(*name).|
|00003460| 09 09 09 72 65 74 75 72 | 6e 3b 0a 09 7d 0a 0a 09 |...retur|n;..}...|
|00003470| 2f 2a 20 61 73 6b 20 75 | 75 63 70 20 2a 2f 0a 09 |/* ask u|ucp */..|
|00003480| 69 66 20 28 28 77 68 6f | 61 6d 69 20 3d 20 70 6f |if ((who|ami = po|
|00003490| 70 65 6e 28 22 75 75 6e | 61 6d 65 20 2d 6c 22 2c |pen("uun|ame -l",|
|000034a0| 20 22 72 22 29 29 20 21 | 3d 20 30 29 20 7b 0a 09 | "r")) !|= 0) {..|
|000034b0| 09 28 76 6f 69 64 29 20 | 66 67 65 74 73 28 6e 61 |.(void) |fgets(na|
|000034c0| 6d 65 2c 20 6c 65 6e 2c | 20 77 68 6f 61 6d 69 29 |me, len,| whoami)|
|000034d0| 3b 0a 09 09 28 76 6f 69 | 64 29 20 70 63 6c 6f 73 |;...(voi|d) pclos|
|000034e0| 65 28 77 68 6f 61 6d 69 | 29 3b 0a 09 09 69 66 20 |e(whoami|);...if |
|000034f0| 28 28 70 74 72 20 3d 20 | 69 6e 64 65 78 28 6e 61 |((ptr = |index(na|
|00003500| 6d 65 2c 20 27 5c 6e 27 | 29 29 20 21 3d 20 30 29 |me, '\n'|)) != 0)|
|00003510| 0a 09 09 09 2a 70 74 72 | 20 3d 20 27 5c 30 27 3b |....*ptr| = '\0';|
|00003520| 0a 09 7d 0a 09 69 66 20 | 28 2a 6e 61 6d 65 29 0a |..}..if |(*name).|
|00003530| 09 09 72 65 74 75 72 6e | 3b 0a 09 0a 09 2f 2a 20 |..return|;..../* |
|00003540| 61 77 20 68 65 6c 6c 2c | 20 69 20 67 69 76 65 20 |aw hell,| i give |
|00003550| 75 70 21 20 20 69 73 20 | 74 68 69 73 20 61 20 72 |up!  is |this a r|
|00003560| 65 61 6c 20 75 6e 69 78 | 3f 20 2a 2f 0a 09 72 65 |eal unix|? */..re|
|00003570| 74 75 72 6e 3b 0a 7d 0a | 23 65 6e 64 69 66 20 47 |turn;.}.|#endif G|
|00003580| 45 54 48 4f 53 54 4e 41 | 4d 45 0a 23 65 6e 64 69 |ETHOSTNA|ME.#endi|
|00003590| 66 20 55 4e 41 4d 45 0a | 53 48 41 52 5f 45 4f 46 |f UNAME.|SHAR_EOF|
|000035a0| 0a 69 66 20 74 65 73 74 | 20 31 34 32 36 20 2d 6e |.if test| 1426 -n|
|000035b0| 65 20 22 60 77 63 20 2d | 63 20 3c 20 27 6c 6f 63 |e "`wc -|c < 'loc|
|000035c0| 61 6c 2e 63 27 60 22 0a | 74 68 65 6e 0a 09 65 63 |al.c'`".|then..ec|
|000035d0| 68 6f 20 73 68 61 72 3a | 20 65 72 72 6f 72 20 74 |ho shar:| error t|
|000035e0| 72 61 6e 73 6d 69 74 74 | 69 6e 67 20 22 27 6c 6f |ransmitt|ing "'lo|
|000035f0| 63 61 6c 2e 63 27 22 20 | 27 28 73 68 6f 75 6c 64 |cal.c'" |'(should|
|00003600| 20 68 61 76 65 20 62 65 | 65 6e 20 31 34 32 36 20 | have be|en 1426 |
|00003610| 63 68 61 72 61 63 74 65 | 72 73 29 27 0a 66 69 0a |characte|rs)'.fi.|
|00003620| 66 69 0a 65 63 68 6f 20 | 73 68 61 72 3a 20 65 78 |fi.echo |shar: ex|
|00003630| 74 72 61 63 74 69 6e 67 | 20 22 27 6d 61 69 6e 2e |tracting| "'main.|
|00003640| 63 27 22 20 27 28 32 33 | 36 32 20 63 68 61 72 61 |c'" '(23|62 chara|
|00003650| 63 74 65 72 73 29 27 0a | 69 66 20 74 65 73 74 20 |cters)'.|if test |
|00003660| 2d 66 20 27 6d 61 69 6e | 2e 63 27 0a 74 68 65 6e |-f 'main|.c'.then|
|00003670| 0a 09 65 63 68 6f 20 73 | 68 61 72 3a 20 77 69 6c |..echo s|har: wil|
|00003680| 6c 20 6e 6f 74 20 6f 76 | 65 72 2d 77 72 69 74 65 |l not ov|er-write|
|00003690| 20 65 78 69 73 74 69 6e | 67 20 66 69 6c 65 20 22 | existin|g file "|
|000036a0| 27 6d 61 69 6e 2e 63 27 | 22 0a 65 6c 73 65 0a 63 |'main.c'|".else.c|
|000036b0| 61 74 20 3c 3c 20 5c 53 | 48 41 52 5f 45 4f 46 20 |at << \S|HAR_EOF |
|000036c0| 3e 20 27 6d 61 69 6e 2e | 63 27 0a 2f 2a 20 70 61 |> 'main.|c'./* pa|
|000036d0| 74 68 61 6c 69 61 73 20 | 2d 2d 20 62 79 20 73 74 |thalias |-- by st|
|000036e0| 65 76 65 20 62 65 6c 6c | 6f 76 69 6e 2c 20 61 73 |eve bell|ovin, as|
|000036f0| 20 74 6f 6c 64 20 74 6f | 20 70 65 74 65 72 20 68 | told to| peter h|
|00003700| 6f 6e 65 79 6d 61 6e 20 | 2a 2f 0a 23 69 66 6e 64 |oneyman |*/.#ifnd|
|00003710| 65 66 20 6c 69 6e 74 0a | 73 74 61 74 69 63 20 63 |ef lint.|static c|
|00003720| 68 61 72 09 2a 73 63 63 | 73 69 64 20 3d 20 22 40 |har.*scc|sid = "@|
|00003730| 28 23 29 6d 61 69 6e 2e | 63 09 38 2e 31 20 28 64 |(#)main.|c.8.1 (d|
|00003740| 6f 77 6e 21 68 6f 6e 65 | 79 29 20 38 36 2f 30 31 |own!hone|y) 86/01|
|00003750| 2f 31 39 22 3b 0a 23 65 | 6e 64 69 66 0a 0a 23 64 |/19";.#e|ndif..#d|
|00003760| 65 66 69 6e 65 20 4d 41 | 49 4e 09 2f 2a 20 66 6f |efine MA|IN./* fo|
|00003770| 72 20 73 63 63 73 69 64 | 20 69 6e 20 68 65 61 64 |r sccsid| in head|
|00003780| 65 72 20 66 69 6c 65 73 | 20 2a 2f 0a 0a 23 69 6e |er files| */..#in|
|00003790| 63 6c 75 64 65 20 22 64 | 65 66 2e 68 22 0a 0a 23 |clude "d|ef.h"..#|
|000037a0| 64 65 66 69 6e 65 20 55 | 53 41 47 45 20 22 75 73 |define U|SAGE "us|
|000037b0| 61 67 65 3a 20 25 73 20 | 5b 2d 76 63 69 5d 20 5b |age: %s |[-vci] [|
|000037c0| 2d 6c 20 6c 6f 63 61 6c | 6e 61 6d 65 5d 20 5b 2d |-l local|name] [-|
|000037d0| 64 20 64 65 61 64 6c 69 | 6e 6b 5d 20 5b 2d 74 20 |d deadli|nk] [-t |
|000037e0| 74 72 61 63 65 6c 69 6e | 6b 5d 20 5b 2d 67 20 66 |tracelin|k] [-g f|
|000037f0| 69 6c 65 5d 20 5b 2d 73 | 20 66 69 6c 65 5d 5c 6e |ile] [-s| file]\n|
|00003800| 22 0a 0a 6d 61 69 6e 28 | 61 72 67 63 2c 20 61 72 |"..main(|argc, ar|
|00003810| 67 76 29 20 0a 69 6e 74 | 09 61 72 67 63 3b 20 0a |gv) .int|.argc; .|
|00003820| 63 68 61 72 09 2a 61 72 | 67 76 5b 5d 3b 0a 7b 0a |char.*ar|gv[];.{.|
|00003830| 09 63 68 61 72 09 2a 6c | 6f 63 6e 61 6d 65 20 3d |.char.*l|ocname =|
|00003840| 20 30 3b 0a 09 69 6e 74 | 09 63 2c 20 65 72 72 66 | 0;..int|.c, errf|
|00003850| 6c 67 20 3d 20 30 3b 0a | 0a 09 50 72 6f 67 4e 61 |lg = 0;.|..ProgNa|
|00003860| 6d 65 20 3d 20 61 72 67 | 76 5b 30 5d 3b 0a 09 28 |me = arg|v[0];..(|
|00003870| 76 6f 69 64 29 20 61 6c | 6c 6f 63 61 74 69 6f 6e |void) al|location|
|00003880| 28 29 3b 09 2f 2a 20 69 | 6e 69 74 69 61 6c 69 7a |();./* i|nitializ|
|00003890| 65 20 64 61 74 61 20 73 | 70 61 63 65 20 6d 6f 6e |e data s|pace mon|
|000038a0| 69 74 6f 72 69 6e 67 20 | 2a 2f 0a 09 43 66 69 6c |itoring |*/..Cfil|
|000038b0| 65 20 3d 20 22 5b 64 65 | 61 64 6c 69 6e 6b 73 5d |e = "[de|adlinks]|
|000038c0| 22 3b 09 2f 2a 20 66 6f | 72 20 74 72 61 63 69 6e |";./* fo|r tracin|
|000038d0| 67 20 64 65 61 64 20 6c | 69 6e 6b 73 20 2a 2f 0a |g dead l|inks */.|
|000038e0| 09 77 68 69 6c 65 20 28 | 28 63 20 3d 20 67 65 74 |.while (|(c = get|
|000038f0| 6f 70 74 28 61 72 67 63 | 2c 20 61 72 67 76 2c 20 |opt(argc|, argv, |
|00003900| 22 63 64 3a 67 3a 69 6c | 3a 73 3a 74 3a 76 22 29 |"cd:g:il|:s:t:v")|
|00003910| 29 20 21 3d 20 45 4f 46 | 29 0a 09 09 73 77 69 74 |) != EOF|)...swit|
|00003920| 63 68 28 63 29 20 7b 0a | 09 09 63 61 73 65 20 27 |ch(c) {.|..case '|
|00003930| 63 27 3a 09 2f 2a 20 70 | 72 69 6e 74 20 63 6f 73 |c':./* p|rint cos|
|00003940| 74 20 69 6e 66 6f 20 2a | 2f 0a 09 09 09 43 66 6c |t info *|/....Cfl|
|00003950| 61 67 2b 2b 3b 0a 09 09 | 09 62 72 65 61 6b 3b 0a |ag++;...|.break;.|
|00003960| 09 09 63 61 73 65 20 27 | 64 27 3a 09 2f 2a 20 64 |..case '|d':./* d|
|00003970| 65 61 64 20 68 6f 73 74 | 20 6f 72 20 6c 69 6e 6b |ead host| or link|
|00003980| 20 2a 2f 0a 09 09 09 64 | 65 61 64 6c 69 6e 6b 28 | */....d|eadlink(|
|00003990| 6f 70 74 61 72 67 29 3b | 0a 09 09 09 62 72 65 61 |optarg);|....brea|
|000039a0| 6b 3b 0a 09 09 63 61 73 | 65 20 27 67 27 3a 09 2f |k;...cas|e 'g':./|
|000039b0| 2a 20 67 72 61 70 68 20 | 6f 75 74 70 75 74 20 66 |* graph |output f|
|000039c0| 69 6c 65 20 2a 2f 0a 09 | 09 09 47 72 61 70 68 6f |ile */..|..Grapho|
|000039d0| 75 74 20 3d 20 6f 70 74 | 61 72 67 3b 0a 09 09 09 |ut = opt|arg;....|
|000039e0| 62 72 65 61 6b 3b 0a 09 | 09 63 61 73 65 20 27 69 |break;..|.case 'i|
|000039f0| 27 3a 09 2f 2a 20 69 67 | 6e 6f 72 65 20 63 61 73 |':./* ig|nore cas|
|00003a00| 65 20 2a 2f 0a 09 09 09 | 49 66 6c 61 67 2b 2b 3b |e */....|Iflag++;|
|00003a10| 0a 09 09 09 62 72 65 61 | 6b 3b 0a 09 09 63 61 73 |....brea|k;...cas|
|00003a20| 65 20 27 6c 27 3a 09 2f | 2a 20 6c 6f 63 61 6c 20 |e 'l':./|* local |
|00003a30| 6e 61 6d 65 20 2a 2f 0a | 09 09 09 6c 6f 63 6e 61 |name */.|...locna|
|00003a40| 6d 65 20 3d 20 6f 70 74 | 61 72 67 3b 0a 09 09 09 |me = opt|arg;....|
|00003a50| 62 72 65 61 6b 3b 0a 09 | 09 63 61 73 65 20 27 73 |break;..|.case 's|
|00003a60| 27 3a 09 2f 2a 20 73 68 | 6f 77 20 73 68 6f 72 74 |':./* sh|ow short|
|00003a70| 65 73 74 20 70 61 74 68 | 20 74 72 65 65 20 2a 2f |est path| tree */|
|00003a80| 0a 09 09 09 4c 69 6e 6b | 6f 75 74 20 3d 20 6f 70 |....Link|out = op|
|00003a90| 74 61 72 67 3b 0a 09 09 | 09 62 72 65 61 6b 3b 0a |targ;...|.break;.|
|00003aa0| 09 09 63 61 73 65 20 27 | 74 27 3a 09 2f 2a 20 74 |..case '|t':./* t|
|00003ab0| 72 61 63 65 20 74 68 69 | 73 20 6c 69 6e 6b 20 2a |race thi|s link *|
|00003ac0| 2f 0a 09 09 09 69 66 20 | 28 74 72 61 63 65 6c 69 |/....if |(traceli|
|00003ad0| 6e 6b 28 6f 70 74 61 72 | 67 29 20 3c 20 30 29 20 |nk(optar|g) < 0) |
|00003ae0| 7b 0a 09 09 09 09 66 70 | 72 69 6e 74 66 28 73 74 |{.....fp|rintf(st|
|00003af0| 64 65 72 72 2c 20 22 25 | 73 3a 20 63 61 6e 20 74 |derr, "%|s: can t|
|00003b00| 72 61 63 65 20 6f 6e 6c | 79 20 25 64 20 6c 69 6e |race onl|y %d lin|
|00003b10| 6b 73 5c 6e 22 2c 20 50 | 72 6f 67 4e 61 6d 65 2c |ks\n", P|rogName,|
|00003b20| 20 4e 54 52 41 43 45 29 | 3b 0a 09 09 09 09 65 78 | NTRACE)|;.....ex|
|00003b30| 69 74 28 31 29 3b 0a 09 | 09 09 7d 0a 09 09 09 54 |it(1);..|..}....T|
|00003b40| 66 6c 61 67 20 3d 20 31 | 3b 0a 09 09 09 62 72 65 |flag = 1|;....bre|
|00003b50| 61 6b 3b 0a 09 09 63 61 | 73 65 20 27 76 27 3a 09 |ak;...ca|se 'v':.|
|00003b60| 2f 2a 20 76 65 72 62 6f | 73 65 20 73 74 64 65 72 |/* verbo|se stder|
|00003b70| 72 2c 20 6d 69 78 65 64 | 20 62 6c 65 73 73 69 6e |r, mixed| blessin|
|00003b80| 67 20 2a 2f 0a 09 09 09 | 56 66 6c 61 67 2b 2b 3b |g */....|Vflag++;|
|00003b90| 0a 09 09 09 62 72 65 61 | 6b 3b 0a 09 09 64 65 66 |....brea|k;...def|
|00003ba0| 61 75 6c 74 3a 0a 09 09 | 09 65 72 72 66 6c 67 2b |ault:...|.errflg+|
|00003bb0| 2b 3b 0a 09 09 7d 0a 0a | 09 69 66 20 28 65 72 72 |+;...}..|.if (err|
|00003bc0| 66 6c 67 29 20 7b 0a 09 | 09 66 70 72 69 6e 74 66 |flg) {..|.fprintf|
|00003bd0| 28 73 74 64 65 72 72 2c | 20 55 53 41 47 45 2c 20 |(stderr,| USAGE, |
|00003be0| 50 72 6f 67 4e 61 6d 65 | 29 3b 0a 09 09 65 78 69 |ProgName|);...exi|
|00003bf0| 74 28 31 29 3b 0a 09 7d | 0a 09 61 72 67 76 20 2b |t(1);..}|..argv +|
|00003c00| 3d 20 6f 70 74 69 6e 64 | 3b 09 09 2f 2a 20 6b 6c |= optind|;../* kl|
|00003c10| 75 64 67 65 20 66 6f 72 | 20 79 79 77 72 61 70 28 |udge for| yywrap(|
|00003c20| 29 20 2a 2f 0a 0a 09 69 | 66 20 28 2a 61 72 67 76 |) */...i|f (*argv|
|00003c30| 29 20 7b 0a 09 09 49 66 | 69 6c 65 73 20 3d 20 61 |) {...If|iles = a|
|00003c40| 72 67 76 3b 0a 09 09 66 | 72 65 6f 70 65 6e 28 22 |rgv;...f|reopen("|
|00003c50| 2f 64 65 76 2f 6e 75 6c | 6c 22 2c 20 22 72 22 2c |/dev/nul|l", "r",|
|00003c60| 20 73 74 64 69 6e 29 3b | 0a 09 7d 0a 0a 09 69 66 | stdin);|..}...if|
|00003c70| 20 28 21 6c 6f 63 6e 61 | 6d 65 29 20 0a 09 09 6c | (!locna|me) ...l|
|00003c80| 6f 63 6e 61 6d 65 20 3d | 20 6c 6f 63 61 6c 28 29 |ocname =| local()|
|00003c90| 3b 0a 09 69 66 20 28 2a | 6c 6f 63 6e 61 6d 65 20 |;..if (*|locname |
|00003ca0| 3d 3d 20 30 29 20 7b 0a | 09 09 6c 6f 63 6e 61 6d |== 0) {.|..locnam|
|00003cb0| 65 20 3d 20 22 6c 6f 73 | 74 69 6e 73 70 61 63 65 |e = "los|tinspace|
|00003cc0| 22 3b 0a 09 09 66 70 72 | 69 6e 74 66 28 73 74 64 |";...fpr|intf(std|
|00003cd0| 65 72 72 2c 20 22 25 73 | 3a 20 75 73 69 6e 67 20 |err, "%s|: using |
|00003ce0| 5c 22 25 73 5c 22 20 66 | 6f 72 20 6c 6f 63 61 6c |\"%s\" f|or local|
|00003cf0| 20 6e 61 6d 65 5c 6e 22 | 2c 0a 09 09 09 09 50 72 | name\n"|,.....Pr|
|00003d00| 6f 67 4e 61 6d 65 2c 20 | 6c 6f 63 6e 61 6d 65 29 |ogName, |locname)|
|00003d10| 3b 0a 09 7d 0a 0a 09 48 | 6f 6d 65 20 3d 20 61 64 |;..}...H|ome = ad|
|00003d20| 64 6e 6f 64 65 28 6c 6f | 63 6e 61 6d 65 29 3b 09 |dnode(lo|cname);.|
|00003d30| 2f 2a 20 61 64 64 20 68 | 6f 6d 65 20 6e 6f 64 65 |/* add h|ome node|
|00003d40| 20 2a 2f 0a 09 48 6f 6d | 65 2d 3e 6e 5f 63 6f 73 | */..Hom|e->n_cos|
|00003d50| 74 20 3d 20 30 3b 09 09 | 2f 2a 20 64 6f 65 73 6e |t = 0;..|/* doesn|
|00003d60| 27 74 20 63 6f 73 74 20 | 74 6f 20 67 65 74 20 68 |'t cost |to get h|
|00003d70| 65 72 65 20 2a 2f 0a 0a | 09 79 79 70 61 72 73 65 |ere */..|.yyparse|
|00003d80| 28 29 3b 09 09 09 2f 2a | 20 72 65 61 64 20 69 6e |();.../*| read in|
|00003d90| 20 6c 69 6e 6b 20 69 6e | 66 6f 20 2a 2f 0a 0a 09 | link in|fo */...|
|00003da0| 69 66 20 28 56 66 6c 61 | 67 20 3e 20 31 29 0a 09 |if (Vfla|g > 1)..|
|00003db0| 09 68 61 73 68 61 6e 61 | 6c 79 7a 65 28 29 3b 0a |.hashana|lyze();.|
|00003dc0| 09 76 70 72 69 6e 74 66 | 28 73 74 64 65 72 72 2c |.vprintf|(stderr,|
|00003dd0| 20 22 25 64 20 76 65 72 | 74 69 63 65 73 2c 20 25 | "%d ver|tices, %|
|00003de0| 64 20 65 64 67 65 73 5c | 6e 22 2c 20 4e 63 6f 75 |d edges\|n", Ncou|
|00003df0| 6e 74 2c 20 4c 63 6f 75 | 6e 74 29 3b 0a 09 76 70 |nt, Lcou|nt);..vp|
|00003e00| 72 69 6e 74 66 28 73 74 | 64 65 72 72 2c 20 22 61 |rintf(st|derr, "a|
|00003e10| 6c 6c 6f 63 61 74 69 6f | 6e 20 69 73 20 25 6c 64 |llocatio|n is %ld|
|00003e20| 6b 20 61 66 74 65 72 20 | 70 61 72 73 69 6e 67 5c |k after |parsing\|
|00003e30| 6e 22 2c 20 61 6c 6c 6f | 63 61 74 69 6f 6e 28 29 |n", allo|cation()|
|00003e40| 29 3b 0a 0a 09 43 66 69 | 6c 65 20 3d 20 22 5b 62 |);...Cfi|le = "[b|
|00003e50| 61 63 6b 6c 69 6e 6b 73 | 5d 22 3b 09 2f 2a 20 66 |acklinks|]";./* f|
|00003e60| 6f 72 20 74 72 61 63 69 | 6e 67 20 62 61 63 6b 20 |or traci|ng back |
|00003e70| 6c 69 6e 6b 73 20 2a 2f | 0a 09 4c 69 6e 65 6e 6f |links */|..Lineno|
|00003e80| 20 3d 20 30 3b 0a 0a 09 | 6d 61 70 69 74 28 29 3b | = 0;...|mapit();|
|00003e90| 09 09 09 2f 2a 20 63 6f | 6d 70 75 74 65 20 73 68 |.../* co|mpute sh|
|00003ea0| 6f 72 74 65 73 74 20 70 | 61 74 68 20 74 72 65 65 |ortest p|ath tree|
|00003eb0| 20 2a 2f 0a 09 76 70 72 | 69 6e 74 66 28 73 74 64 | */..vpr|intf(std|
|00003ec0| 65 72 72 2c 20 22 61 6c | 6c 6f 63 61 74 69 6f 6e |err, "al|location|
|00003ed0| 20 69 73 20 25 6c 64 6b | 20 61 66 74 65 72 20 6d | is %ldk| after m|
|00003ee0| 61 70 70 69 6e 67 5c 6e | 22 2c 20 61 6c 6c 6f 63 |apping\n|", alloc|
|00003ef0| 61 74 69 6f 6e 28 29 29 | 3b 0a 0a 09 70 72 69 6e |ation())|;...prin|
|00003f00| 74 69 74 28 29 3b 09 09 | 09 2f 2a 20 74 72 61 76 |tit();..|./* trav|
|00003f10| 65 72 73 65 20 74 72 65 | 65 20 61 6e 64 20 70 72 |erse tre|e and pr|
|00003f20| 69 6e 74 20 70 61 74 68 | 73 20 2a 2f 0a 09 76 70 |int path|s */..vp|
|00003f30| 72 69 6e 74 66 28 73 74 | 64 65 72 72 2c 20 22 61 |rintf(st|derr, "a|
|00003f40| 6c 6c 6f 63 61 74 69 6f | 6e 20 69 73 20 25 6c 64 |llocatio|n is %ld|
|00003f50| 6b 20 61 66 74 65 72 20 | 70 72 69 6e 74 69 6e 67 |k after |printing|
|00003f60| 5c 6e 22 2c 20 61 6c 6c | 6f 63 61 74 69 6f 6e 28 |\n", all|ocation(|
|00003f70| 29 29 3b 0a 0a 09 65 78 | 69 74 28 30 29 3b 0a 7d |));...ex|it(0);.}|
|00003f80| 0a 0a 62 61 64 6d 61 67 | 69 63 28 6e 29 0a 7b 0a |..badmag|ic(n).{.|
|00003f90| 09 69 66 20 28 6e 29 20 | 7b 0a 09 09 66 70 72 69 |.if (n) |{...fpri|
|00003fa0| 6e 74 66 28 73 74 64 65 | 72 72 2c 20 22 25 73 3a |ntf(stde|rr, "%s:|
|00003fb0| 20 63 61 6e 6e 6f 74 20 | 72 65 63 6f 76 65 72 21 | cannot |recover!|
|00003fc0| 5c 6e 22 2c 20 50 72 6f | 67 4e 61 6d 65 29 3b 0a |\n", Pro|gName);.|
|00003fd0| 23 69 66 64 65 66 20 44 | 45 42 55 47 0a 09 09 61 |#ifdef D|EBUG...a|
|00003fe0| 62 6f 72 74 28 29 3b 0a | 23 65 6c 73 65 0a 09 09 |bort();.|#else...|
|00003ff0| 65 78 69 74 28 6e 29 3b | 0a 23 65 6e 64 69 66 0a |exit(n);|.#endif.|
|00004000| 09 7d 0a 7d 0a 53 48 41 | 52 5f 45 4f 46 0a 69 66 |.}.}.SHA|R_EOF.if|
|00004010| 20 74 65 73 74 20 32 33 | 36 32 20 2d 6e 65 20 22 | test 23|62 -ne "|
|00004020| 60 77 63 20 2d 63 20 3c | 20 27 6d 61 69 6e 2e 63 |`wc -c <| 'main.c|
|00004030| 27 60 22 0a 74 68 65 6e | 0a 09 65 63 68 6f 20 73 |'`".then|..echo s|
|00004040| 68 61 72 3a 20 65 72 72 | 6f 72 20 74 72 61 6e 73 |har: err|or trans|
|00004050| 6d 69 74 74 69 6e 67 20 | 22 27 6d 61 69 6e 2e 63 |mitting |"'main.c|
|00004060| 27 22 20 27 28 73 68 6f | 75 6c 64 20 68 61 76 65 |'" '(sho|uld have|
|00004070| 20 62 65 65 6e 20 32 33 | 36 32 20 63 68 61 72 61 | been 23|62 chara|
|00004080| 63 74 65 72 73 29 27 0a | 66 69 0a 66 69 0a 65 63 |cters)'.|fi.fi.ec|
|00004090| 68 6f 20 73 68 61 72 3a | 20 65 78 74 72 61 63 74 |ho shar:| extract|
|000040a0| 69 6e 67 20 22 27 6d 61 | 6b 65 64 62 2e 63 27 22 |ing "'ma|kedb.c'"|
|000040b0| 20 27 28 32 33 34 38 20 | 63 68 61 72 61 63 74 65 | '(2348 |characte|
|000040c0| 72 73 29 27 0a 69 66 20 | 74 65 73 74 20 2d 66 20 |rs)'.if |test -f |
|000040d0| 27 6d 61 6b 65 64 62 2e | 63 27 0a 74 68 65 6e 0a |'makedb.|c'.then.|
|000040e0| 09 65 63 68 6f 20 73 68 | 61 72 3a 20 77 69 6c 6c |.echo sh|ar: will|
|000040f0| 20 6e 6f 74 20 6f 76 65 | 72 2d 77 72 69 74 65 20 | not ove|r-write |
|00004100| 65 78 69 73 74 69 6e 67 | 20 66 69 6c 65 20 22 27 |existing| file "'|
|00004110| 6d 61 6b 65 64 62 2e 63 | 27 22 0a 65 6c 73 65 0a |makedb.c|'".else.|
|00004120| 63 61 74 20 3c 3c 20 5c | 53 48 41 52 5f 45 4f 46 |cat << \|SHAR_EOF|
|00004130| 20 3e 20 27 6d 61 6b 65 | 64 62 2e 63 27 0a 2f 2a | > 'make|db.c'./*|
|00004140| 20 70 61 74 68 61 6c 69 | 61 73 20 2d 2d 20 62 79 | pathali|as -- by|
|00004150| 20 73 74 65 76 65 20 62 | 65 6c 6c 6f 76 69 6e 2c | steve b|ellovin,|
|00004160| 20 61 73 20 74 6f 6c 64 | 20 74 6f 20 70 65 74 65 | as told| to pete|
|00004170| 72 20 68 6f 6e 65 79 6d | 61 6e 20 2a 2f 0a 23 69 |r honeym|an */.#i|
|00004180| 66 6e 64 65 66 20 6c 69 | 6e 74 0a 73 74 61 74 69 |fndef li|nt.stati|
|00004190| 63 20 63 68 61 72 09 2a | 73 63 63 73 69 64 20 3d |c char.*|sccsid =|
|000041a0| 20 22 40 28 23 29 6d 61 | 6b 65 64 62 2e 63 09 38 | "@(#)ma|kedb.c.8|
|000041b0| 2e 31 20 28 64 6f 77 6e | 21 68 6f 6e 65 79 29 20 |.1 (down|!honey) |
|000041c0| 38 36 2f 30 31 2f 31 39 | 22 3b 0a 23 65 6e 64 69 |86/01/19|";.#endi|
|000041d0| 66 20 6c 69 6e 74 0a 0a | 23 69 6e 63 6c 75 64 65 |f lint..|#include|
|000041e0| 20 3c 73 74 64 69 6f 2e | 68 3e 0a 23 69 6e 63 6c | <stdio.|h>.#incl|
|000041f0| 75 64 65 20 22 63 6f 6e | 66 69 67 2e 68 22 0a 0a |ude "con|fig.h"..|
|00004200| 74 79 70 65 64 65 66 20 | 73 74 72 75 63 74 20 7b |typedef |struct {|
|00004210| 0a 09 63 68 61 72 20 2a | 64 70 74 72 3b 0a 09 69 |..char *|dptr;..i|
|00004220| 6e 74 20 64 73 69 7a 65 | 3b 0a 7d 20 64 61 74 75 |nt dsize|;.} datu|
|00004230| 6d 3b 0a 0a 63 68 61 72 | 20 2a 4f 66 69 6c 65 20 |m;..char| *Ofile |
|00004240| 3d 20 41 4c 49 41 53 44 | 42 2c 20 2a 50 72 6f 67 |= ALIASD|B, *Prog|
|00004250| 4e 61 6d 65 3b 0a 0a 23 | 64 65 66 69 6e 65 20 55 |Name;..#|define U|
|00004260| 53 41 47 45 20 22 25 73 | 20 5b 2d 6f 20 64 62 6d |SAGE "%s| [-o dbm|
|00004270| 6e 61 6d 65 5d 20 5b 2d | 61 5d 20 5b 66 69 6c 65 |name] [-|a] [file|
|00004280| 20 2e 2e 2e 5d 22 0a 0a | 6d 61 69 6e 28 61 72 67 | ...]"..|main(arg|
|00004290| 63 2c 20 61 72 67 76 29 | 0a 09 63 68 61 72 20 2a |c, argv)|..char *|
|000042a0| 61 72 67 76 5b 5d 3b 0a | 7b 09 63 68 61 72 20 2a |argv[];.|{.char *|
|000042b0| 6f 66 70 74 72 3b 0a 09 | 69 6e 74 20 63 2c 20 61 |ofptr;..|int c, a|
|000042c0| 70 70 65 6e 64 20 3d 20 | 30 3b 0a 09 65 78 74 65 |ppend = |0;..exte|
|000042d0| 72 6e 20 69 6e 74 20 6f | 70 74 69 6e 64 3b 0a 09 |rn int o|ptind;..|
|000042e0| 65 78 74 65 72 6e 20 63 | 68 61 72 20 2a 6f 70 74 |extern c|har *opt|
|000042f0| 61 72 67 3b 0a 0a 09 50 | 72 6f 67 4e 61 6d 65 20 |arg;...P|rogName |
|00004300| 3d 20 61 72 67 76 5b 30 | 5d 3b 0a 09 77 68 69 6c |= argv[0|];..whil|
|00004310| 65 20 28 28 63 20 3d 20 | 67 65 74 6f 70 74 28 61 |e ((c = |getopt(a|
|00004320| 72 67 63 2c 20 61 72 67 | 76 2c 20 22 6f 3a 61 76 |rgc, arg|v, "o:av|
|00004330| 22 29 29 20 21 3d 20 45 | 4f 46 29 0a 09 09 73 77 |")) != E|OF)...sw|
|00004340| 69 74 63 68 28 63 29 20 | 7b 0a 09 09 63 61 73 65 |itch(c) |{...case|
|00004350| 20 27 6f 27 3a 09 2f 2a | 20 64 62 6d 20 6f 75 74 | 'o':./*| dbm out|
|00004360| 70 75 74 20 66 69 6c 65 | 20 2a 2f 0a 09 09 09 4f |put file| */....O|
|00004370| 66 69 6c 65 20 3d 20 6f | 70 74 61 72 67 3b 0a 09 |file = o|ptarg;..|
|00004380| 09 09 62 72 65 61 6b 3b | 0a 0a 09 09 63 61 73 65 |..break;|....case|
|00004390| 20 27 61 27 3a 09 2f 2a | 20 61 70 70 65 6e 64 20 | 'a':./*| append |
|000043a0| 6d 6f 64 65 20 2a 2f 0a | 09 09 09 61 70 70 65 6e |mode */.|...appen|
|000043b0| 64 2b 2b 3b 0a 09 09 09 | 62 72 65 61 6b 3b 0a 0a |d++;....|break;..|
|000043c0| 09 09 64 65 66 61 75 6c | 74 3a 0a 09 09 09 66 70 |..defaul|t:....fp|
|000043d0| 72 69 6e 74 66 28 73 74 | 64 65 72 72 2c 20 55 53 |rintf(st|derr, US|
|000043e0| 41 47 45 2c 20 50 72 6f | 67 4e 61 6d 65 29 3b 0a |AGE, Pro|gName);.|
|000043f0| 09 09 09 65 78 69 74 28 | 31 29 3b 0a 09 09 09 62 |...exit(|1);....b|
|00004400| 72 65 61 6b 3b 0a 09 09 | 7d 0a 0a 0a 09 69 66 20 |reak;...|}....if |
|00004410| 28 28 6f 66 70 74 72 20 | 3d 20 72 69 6e 64 65 78 |((ofptr |= rindex|
|00004420| 28 4f 66 69 6c 65 2c 20 | 27 2f 27 29 29 20 21 3d |(Ofile, |'/')) !=|
|00004430| 20 30 29 0a 09 09 6f 66 | 70 74 72 2b 2b 3b 0a 09 | 0)...of|ptr++;..|
|00004440| 65 6c 73 65 0a 09 09 6f | 66 70 74 72 20 3d 20 4f |else...o|fptr = O|
|00004450| 66 69 6c 65 3b 0a 09 69 | 66 20 28 73 74 72 6c 65 |file;..i|f (strle|
|00004460| 6e 28 6f 66 70 74 72 29 | 20 3e 20 31 30 29 20 7b |n(ofptr)| > 10) {|
|00004470| 0a 09 09 6f 66 70 74 72 | 5b 31 30 5d 20 3d 20 30 |...ofptr|[10] = 0|
|00004480| 3b 0a 09 09 66 70 72 69 | 6e 74 66 28 73 74 64 65 |;...fpri|ntf(stde|
|00004490| 72 72 2c 20 22 25 73 3a | 20 75 73 69 6e 67 20 25 |rr, "%s:| using %|
|000044a0| 73 20 66 6f 72 20 64 62 | 6d 20 6f 75 74 70 75 74 |s for db|m output|
|000044b0| 5c 6e 22 2c 20 50 72 6f | 67 4e 61 6d 65 2c 20 4f |\n", Pro|gName, O|
|000044c0| 66 69 6c 65 29 3b 0a 09 | 7d 0a 0a 09 69 66 20 28 |file);..|}...if (|
|000044d0| 61 70 70 65 6e 64 20 3d | 3d 20 30 20 26 26 20 64 |append =|= 0 && d|
|000044e0| 62 66 69 6c 65 28 4f 66 | 69 6c 65 29 20 21 3d 20 |bfile(Of|ile) != |
|000044f0| 30 29 20 7b 0a 09 09 70 | 65 72 72 6f 72 5f 28 4f |0) {...p|error_(O|
|00004500| 66 69 6c 65 29 3b 0a 09 | 09 65 78 69 74 28 31 29 |file);..|.exit(1)|
|00004510| 3b 0a 09 7d 0a 0a 09 69 | 66 20 28 64 62 6d 69 6e |;..}...i|f (dbmin|
|00004520| 69 74 28 4f 66 69 6c 65 | 29 20 3c 20 30 29 20 7b |it(Ofile|) < 0) {|
|00004530| 0a 09 09 70 65 72 72 6f | 72 5f 28 4f 66 69 6c 65 |...perro|r_(Ofile|
|00004540| 29 3b 0a 09 09 65 78 69 | 74 28 31 29 3b 0a 09 7d |);...exi|t(1);..}|
|00004550| 0a 0a 09 69 66 20 28 6f | 70 74 69 6e 64 20 3d 3d |...if (o|ptind ==|
|00004560| 20 61 72 67 63 29 0a 09 | 09 6d 61 6b 65 64 62 28 | argc)..|.makedb(|
|00004570| 28 63 68 61 72 20 2a 29 | 20 30 29 3b 0a 09 65 6c |(char *)| 0);..el|
|00004580| 73 65 20 66 6f 72 20 28 | 20 3b 20 6f 70 74 69 6e |se for (| ; optin|
|00004590| 64 20 3c 20 61 72 67 63 | 3b 20 6f 70 74 69 6e 64 |d < argc|; optind|
|000045a0| 2b 2b 29 0a 09 09 6d 61 | 6b 65 64 62 28 61 72 67 |++)...ma|kedb(arg|
|000045b0| 76 5b 6f 70 74 69 6e 64 | 5d 29 3b 0a 09 65 78 69 |v[optind|]);..exi|
|000045c0| 74 28 30 29 3b 0a 7d 0a | 0a 64 62 66 69 6c 65 28 |t(0);.}.|.dbfile(|
|000045d0| 64 62 66 29 0a 09 63 68 | 61 72 20 2a 64 62 66 3b |dbf)..ch|ar *dbf;|
|000045e0| 0a 7b 0a 09 72 65 74 75 | 72 6e 20 28 64 62 63 72 |.{..retu|rn (dbcr|
|000045f0| 65 61 74 28 64 62 66 2c | 20 22 64 69 72 22 29 20 |eat(dbf,| "dir") |
|00004600| 21 3d 20 30 20 7c 7c 20 | 64 62 63 72 65 61 74 28 |!= 0 || |dbcreat(|
|00004610| 64 62 66 2c 20 22 70 61 | 67 22 29 20 21 3d 20 30 |dbf, "pa|g") != 0|
|00004620| 29 3b 0a 7d 0a 0a 64 62 | 63 72 65 61 74 28 64 62 |);.}..db|creat(db|
|00004630| 66 2c 20 73 75 66 66 69 | 78 29 0a 09 63 68 61 72 |f, suffi|x)..char|
|00004640| 20 2a 64 62 66 2c 20 2a | 73 75 66 66 69 78 3b 0a | *dbf, *|suffix;.|
|00004650| 7b 09 63 68 61 72 20 62 | 75 66 5b 42 55 46 53 49 |{.char b|uf[BUFSI|
|00004660| 5a 5d 3b 0a 09 69 6e 74 | 20 66 64 3b 0a 0a 09 28 |Z];..int| fd;...(|
|00004670| 76 6f 69 64 29 20 73 70 | 72 69 6e 74 66 28 62 75 |void) sp|rintf(bu|
|00004680| 66 2c 20 22 25 73 2e 25 | 73 22 2c 20 64 62 66 2c |f, "%s.%|s", dbf,|
|00004690| 20 73 75 66 66 69 78 29 | 3b 0a 09 69 66 20 28 28 | suffix)|;..if ((|
|000046a0| 66 64 20 3d 20 63 72 65 | 61 74 28 62 75 66 2c 20 |fd = cre|at(buf, |
|000046b0| 30 36 36 36 29 29 20 3c | 20 30 29 0a 09 09 72 65 |0666)) <| 0)...re|
|000046c0| 74 75 72 6e 28 2d 31 29 | 3b 0a 09 28 76 6f 69 64 |turn(-1)|;..(void|
|000046d0| 29 20 63 6c 6f 73 65 28 | 66 64 29 3b 0a 09 72 65 |) close(|fd);..re|
|000046e0| 74 75 72 6e 28 30 29 3b | 0a 7d 0a 0a 0a 6d 61 6b |turn(0);|.}...mak|
|000046f0| 65 64 62 28 69 66 69 6c | 65 29 0a 09 63 68 61 72 |edb(ifil|e)..char|
|00004700| 20 2a 69 66 69 6c 65 3b | 0a 7b 09 63 68 61 72 20 | *ifile;|.{.char |
|00004710| 6c 69 6e 65 5b 42 55 46 | 53 49 5a 5d 3b 0a 09 64 |line[BUF|SIZ];..d|
|00004720| 61 74 75 6d 20 6b 65 79 | 2c 20 76 61 6c 3b 0a 0a |atum key|, val;..|
|00004730| 09 69 66 20 28 69 66 69 | 6c 65 20 26 26 20 28 66 |.if (ifi|le && (f|
|00004740| 72 65 6f 70 65 6e 28 69 | 66 69 6c 65 2c 20 22 72 |reopen(i|file, "r|
|00004750| 22 2c 20 73 74 64 69 6e | 29 20 3d 3d 20 4e 55 4c |", stdin|) == NUL|
|00004760| 4c 29 29 20 7b 0a 09 09 | 70 65 72 72 6f 72 5f 28 |L)) {...|perror_(|
|00004770| 69 66 69 6c 65 29 3b 0a | 09 09 72 65 74 75 72 6e |ifile);.|..return|
|00004780| 3b 0a 09 7d 0a 0a 09 2f | 2a 0a 09 20 2a 20 6b 65 |;..}.../|*.. * ke|
|00004790| 79 73 20 61 6e 64 20 76 | 61 6c 75 65 73 20 61 72 |ys and v|alues ar|
|000047a0| 65 20 30 20 74 65 72 6d | 69 6e 61 74 65 64 2e 20 |e 0 term|inated. |
|000047b0| 20 74 68 69 73 20 77 61 | 73 74 65 73 20 74 69 6d | this wa|stes tim|
|000047c0| 65 20 61 6e 64 20 28 64 | 69 73 6b 29 20 73 70 61 |e and (d|isk) spa|
|000047d0| 63 65 2c 0a 09 20 2a 20 | 62 75 74 20 64 6f 65 73 |ce,.. * |but does|
|000047e0| 20 6c 65 6e 64 20 73 69 | 6d 70 6c 69 63 69 74 79 | lend si|mplicity|
|000047f0| 20 61 6e 64 20 62 61 63 | 6b 77 61 72 64 73 20 63 | and bac|kwards c|
|00004800| 6f 6d 70 61 74 69 62 69 | 6c 69 74 79 2e 0a 09 20 |ompatibi|lity... |
|00004810| 2a 2f 0a 09 6b 65 79 2e | 64 70 74 72 20 3d 20 6c |*/..key.|dptr = l|
|00004820| 69 6e 65 3b 0a 09 77 68 | 69 6c 65 20 28 66 67 65 |ine;..wh|ile (fge|
|00004830| 74 73 28 6c 69 6e 65 2c | 20 73 69 7a 65 6f 66 28 |ts(line,| sizeof(|
|00004840| 6c 69 6e 65 29 2c 20 73 | 74 64 69 6e 29 20 21 3d |line), s|tdin) !=|
|00004850| 20 4e 55 4c 4c 29 20 7b | 0a 09 09 63 68 61 72 20 | NULL) {|...char |
|00004860| 2a 6f 70 2c 20 2a 65 6e | 64 3b 0a 0a 09 09 65 6e |*op, *en|d;....en|
|00004870| 64 20 3d 20 6c 69 6e 65 | 20 2b 20 73 74 72 6c 65 |d = line| + strle|
|00004880| 6e 28 6c 69 6e 65 29 3b | 0a 09 09 65 6e 64 5b 2d |n(line);|...end[-|
|00004890| 31 5d 20 3d 20 30 3b 09 | 2f 2a 20 6b 69 6c 6c 20 |1] = 0;.|/* kill |
|000048a0| 6e 65 77 6c 69 6e 65 2c | 20 73 74 75 66 66 20 6e |newline,| stuff n|
|000048b0| 75 6c 6c 20 74 65 72 6d | 69 6e 61 74 6f 72 20 2a |ull term|inator *|
|000048c0| 2f 0a 09 09 6f 70 20 3d | 20 69 6e 64 65 78 28 6c |/...op =| index(l|
|000048d0| 69 6e 65 2c 20 27 5c 74 | 27 29 3b 0a 09 09 69 66 |ine, '\t|');...if|
|000048e0| 20 28 6f 70 20 21 3d 20 | 30 29 20 7b 0a 09 09 09 | (op != |0) {....|
|000048f0| 2a 6f 70 2b 2b 20 3d 20 | 30 3b 0a 09 09 09 6b 65 |*op++ = |0;....ke|
|00004900| 79 2e 64 73 69 7a 65 20 | 3d 20 6f 70 20 2d 20 6c |y.dsize |= op - l|
|00004910| 69 6e 65 3b 09 09 2f 2a | 20 30 20 74 65 72 6d 69 |ine;../*| 0 termi|
|00004920| 6e 61 74 65 64 20 2a 2f | 0a 09 09 09 76 61 6c 2e |nated */|....val.|
|00004930| 64 70 74 72 20 3d 20 6f | 70 3b 0a 09 09 09 76 61 |dptr = o|p;....va|
|00004940| 6c 2e 64 73 69 7a 65 20 | 3d 20 65 6e 64 20 2d 20 |l.dsize |= end - |
|00004950| 6f 70 3b 09 09 2f 2a 20 | 30 20 74 65 72 6d 69 6e |op;../* |0 termin|
|00004960| 61 74 65 64 20 2a 2f 0a | 09 09 7d 20 65 6c 73 65 |ated */.|..} else|
|00004970| 20 7b 0a 09 09 09 6b 65 | 79 2e 64 73 69 7a 65 20 | {....ke|y.dsize |
|00004980| 3d 20 65 6e 64 20 2d 20 | 6c 69 6e 65 3b 09 09 2f |= end - |line;../|
|00004990| 2a 20 30 20 74 65 72 6d | 69 6e 61 74 65 64 20 2a |* 0 term|inated *|
|000049a0| 2f 0a 09 09 09 76 61 6c | 2e 64 70 74 72 20 3d 20 |/....val|.dptr = |
|000049b0| 22 5c 30 22 3b 09 09 2f | 2a 20 77 68 79 20 6d 75 |"\0";../|* why mu|
|000049c0| 73 74 20 69 20 64 6f 20 | 74 68 69 73 3f 20 2a 2f |st i do |this? */|
|000049d0| 0a 09 09 09 76 61 6c 2e | 64 73 69 7a 65 20 3d 20 |....val.|dsize = |
|000049e0| 31 3b 0a 09 09 7d 0a 09 | 09 69 66 20 28 73 74 6f |1;...}..|.if (sto|
|000049f0| 72 65 28 6b 65 79 2c 20 | 76 61 6c 29 20 3c 20 30 |re(key, |val) < 0|
|00004a00| 29 0a 09 09 09 70 65 72 | 72 6f 72 5f 28 4f 66 69 |)....per|ror_(Ofi|
|00004a10| 6c 65 29 3b 0a 09 7d 0a | 7d 0a 0a 70 65 72 72 6f |le);..}.|}..perro|
|00004a20| 72 5f 28 73 74 72 29 0a | 09 63 68 61 72 09 2a 73 |r_(str).|.char.*s|
|00004a30| 74 72 3b 0a 7b 0a 09 66 | 70 72 69 6e 74 66 28 73 |tr;.{..f|printf(s|
|00004a40| 74 64 65 72 72 2c 20 22 | 25 73 3a 20 22 2c 20 50 |tderr, "|%s: ", P|
|00004a50| 72 6f 67 4e 61 6d 65 29 | 3b 0a 09 70 65 72 72 6f |rogName)|;..perro|
|00004a60| 72 28 73 74 72 29 3b 0a | 7d 0a 53 48 41 52 5f 45 |r(str);.|}.SHAR_E|
|00004a70| 4f 46 0a 69 66 20 74 65 | 73 74 20 32 33 34 38 20 |OF.if te|st 2348 |
|00004a80| 2d 6e 65 20 22 60 77 63 | 20 2d 63 20 3c 20 27 6d |-ne "`wc| -c < 'm|
|00004a90| 61 6b 65 64 62 2e 63 27 | 60 22 0a 74 68 65 6e 0a |akedb.c'|`".then.|
|00004aa0| 09 65 63 68 6f 20 73 68 | 61 72 3a 20 65 72 72 6f |.echo sh|ar: erro|
|00004ab0| 72 20 74 72 61 6e 73 6d | 69 74 74 69 6e 67 20 22 |r transm|itting "|
|00004ac0| 27 6d 61 6b 65 64 62 2e | 63 27 22 20 27 28 73 68 |'makedb.|c'" '(sh|
|00004ad0| 6f 75 6c 64 20 68 61 76 | 65 20 62 65 65 6e 20 32 |ould hav|e been 2|
|00004ae0| 33 34 38 20 63 68 61 72 | 61 63 74 65 72 73 29 27 |348 char|acters)'|
|00004af0| 0a 66 69 0a 66 69 0a 65 | 63 68 6f 20 73 68 61 72 |.fi.fi.e|cho shar|
|00004b00| 3a 20 65 78 74 72 61 63 | 74 69 6e 67 20 22 27 6d |: extrac|ting "'m|
|00004b10| 61 70 61 75 78 2e 63 27 | 22 20 27 28 35 31 36 38 |apaux.c'|" '(5168|
|00004b20| 20 63 68 61 72 61 63 74 | 65 72 73 29 27 0a 69 66 | charact|ers)'.if|
|00004b30| 20 74 65 73 74 20 2d 66 | 20 27 6d 61 70 61 75 78 | test -f| 'mapaux|
|00004b40| 2e 63 27 0a 74 68 65 6e | 0a 09 65 63 68 6f 20 73 |.c'.then|..echo s|
|00004b50| 68 61 72 3a 20 77 69 6c | 6c 20 6e 6f 74 20 6f 76 |har: wil|l not ov|
|00004b60| 65 72 2d 77 72 69 74 65 | 20 65 78 69 73 74 69 6e |er-write| existin|
|00004b70| 67 20 66 69 6c 65 20 22 | 27 6d 61 70 61 75 78 2e |g file "|'mapaux.|
|00004b80| 63 27 22 0a 65 6c 73 65 | 0a 63 61 74 20 3c 3c 20 |c'".else|.cat << |
|00004b90| 5c 53 48 41 52 5f 45 4f | 46 20 3e 20 27 6d 61 70 |\SHAR_EO|F > 'map|
|00004ba0| 61 75 78 2e 63 27 0a 2f | 2a 20 70 61 74 68 61 6c |aux.c'./|* pathal|
|00004bb0| 69 61 73 20 2d 2d 20 62 | 79 20 73 74 65 76 65 20 |ias -- b|y steve |
|00004bc0| 62 65 6c 6c 6f 76 69 6e | 2c 20 61 73 20 74 6f 6c |bellovin|, as tol|
|00004bd0| 64 20 74 6f 20 70 65 74 | 65 72 20 68 6f 6e 65 79 |d to pet|er honey|
|00004be0| 6d 61 6e 20 2a 2f 0a 23 | 69 66 6e 64 65 66 20 6c |man */.#|ifndef l|
|00004bf0| 69 6e 74 0a 73 74 61 74 | 69 63 20 63 68 61 72 09 |int.stat|ic char.|
|00004c00| 2a 73 63 63 73 69 64 20 | 3d 20 22 40 28 23 29 6d |*sccsid |= "@(#)m|
|00004c10| 61 70 61 75 78 2e 63 09 | 38 2e 31 20 28 64 6f 77 |apaux.c.|8.1 (dow|
|00004c20| 6e 21 68 6f 6e 65 79 29 | 20 38 36 2f 30 31 2f 31 |n!honey)| 86/01/1|
|00004c30| 39 22 3b 0a 23 65 6e 64 | 69 66 20 6c 69 6e 74 0a |9";.#end|if lint.|
|00004c40| 0a 23 69 6e 63 6c 75 64 | 65 20 22 64 65 66 2e 68 |.#includ|e "def.h|
|00004c50| 22 0a 0a 76 6f 69 64 09 | 70 61 63 6b 28 29 3b 0a |"..void.|pack();.|
|00004c60| 0a 76 6f 69 64 0a 70 61 | 63 6b 28 29 0a 7b 0a 09 |.void.pa|ck().{..|
|00004c70| 6c 6f 6e 67 09 68 6f 6c | 65 2c 20 6e 65 78 74 3b |long.hol|e, next;|
|00004c80| 0a 0a 09 2f 2a 20 66 69 | 6e 64 20 66 69 72 73 74 |.../* fi|nd first|
|00004c90| 20 22 68 6f 6c 65 20 22 | 20 2a 2f 0a 09 66 6f 72 | "hole "| */..for|
|00004ca0| 20 28 68 6f 6c 65 20 3d | 20 54 61 62 73 69 7a 65 | (hole =| Tabsize|
|00004cb0| 20 2d 20 31 3b 20 68 6f | 6c 65 20 3e 3d 20 30 20 | - 1; ho|le >= 0 |
|00004cc0| 26 26 20 54 61 62 6c 65 | 5b 68 6f 6c 65 5d 20 21 |&& Table|[hole] !|
|00004cd0| 3d 20 30 3b 20 2d 2d 68 | 6f 6c 65 29 0a 09 09 3b |= 0; --h|ole)...;|
|00004ce0| 0a 0a 09 2f 2a 20 72 65 | 70 65 61 74 65 64 6c 79 |.../* re|peatedly|
|00004cf0| 20 6d 6f 76 65 20 6e 65 | 78 74 20 66 69 6c 6c 65 | move ne|xt fille|
|00004d00| 64 20 65 6e 74 72 79 20 | 69 6e 74 6f 20 6c 61 73 |d entry |into las|
|00004d10| 74 20 68 6f 6c 65 20 2a | 2f 0a 09 66 6f 72 20 28 |t hole *|/..for (|
|00004d20| 6e 65 78 74 20 3d 20 68 | 6f 6c 65 20 2d 20 31 3b |next = h|ole - 1;|
|00004d30| 20 6e 65 78 74 20 3e 3d | 20 30 3b 20 2d 2d 6e 65 | next >=| 0; --ne|
|00004d40| 78 74 29 20 7b 0a 09 09 | 69 66 20 28 54 61 62 6c |xt) {...|if (Tabl|
|00004d50| 65 5b 6e 65 78 74 5d 20 | 21 3d 20 30 29 20 7b 0a |e[next] |!= 0) {.|
|00004d60| 09 09 09 54 61 62 6c 65 | 5b 68 6f 6c 65 5d 20 3d |...Table|[hole] =|
|00004d70| 20 54 61 62 6c 65 5b 6e | 65 78 74 5d 3b 0a 09 09 | Table[n|ext];...|
|00004d80| 09 54 61 62 6c 65 5b 68 | 6f 6c 65 5d 2d 3e 6e 5f |.Table[h|ole]->n_|
|00004d90| 74 6c 6f 63 20 3d 20 68 | 6f 6c 65 3b 0a 09 09 09 |tloc = h|ole;....|
|00004da0| 54 61 62 6c 65 5b 6e 65 | 78 74 5d 20 3d 20 30 3b |Table[ne|xt] = 0;|
|00004db0| 0a 09 09 09 77 68 69 6c | 65 20 28 54 61 62 6c 65 |....whil|e (Table|
|00004dc0| 5b 2d 2d 68 6f 6c 65 5d | 20 21 3d 20 30 29 09 2f |[--hole]| != 0)./|
|00004dd0| 2a 20 66 69 6e 64 20 6e | 65 78 74 20 68 6f 6c 65 |* find n|ext hole|
|00004de0| 20 2a 2f 0a 09 09 09 09 | 3b 0a 09 09 7d 0a 09 7d | */.....|;...}..}|
|00004df0| 0a 09 48 61 73 68 70 61 | 72 74 20 3d 20 68 6f 6c |..Hashpa|rt = hol|
|00004e00| 65 20 2b 20 31 3b 0a 7d | 0a 0a 46 49 4c 45 09 2a |e + 1;.}|..FILE.*|
|00004e10| 47 73 74 72 65 61 6d 3b | 0a 0a 64 75 6d 70 67 72 |Gstream;|..dumpgr|
|00004e20| 61 70 68 28 29 0a 7b 0a | 09 6c 6f 6e 67 09 69 3b |aph().{.|.long.i;|
|00004e30| 0a 09 6e 6f 64 65 09 2a | 6e 3b 0a 0a 09 69 66 20 |..node.*|n;...if |
|00004e40| 28 28 47 73 74 72 65 61 | 6d 20 3d 20 66 6f 70 65 |((Gstrea|m = fope|
|00004e50| 6e 28 47 72 61 70 68 6f | 75 74 2c 20 22 77 22 29 |n(Grapho|ut, "w")|
|00004e60| 29 20 3d 3d 20 4e 55 4c | 4c 29 20 7b 0a 09 09 66 |) == NUL|L) {...f|
|00004e70| 70 72 69 6e 74 66 28 73 | 74 64 65 72 72 2c 20 22 |printf(s|tderr, "|
|00004e80| 25 73 3a 20 22 2c 20 50 | 72 6f 67 4e 61 6d 65 29 |%s: ", P|rogName)|
|00004e90| 3b 0a 09 09 70 65 72 72 | 6f 72 28 47 72 61 70 68 |;...perr|or(Graph|
|00004ea0| 6f 75 74 29 3b 0a 09 7d | 0a 0a 09 75 6e 74 61 6e |out);..}|...untan|
|00004eb0| 67 6c 65 28 29 3b 09 2f | 2a 20 75 6e 74 61 6e 67 |gle();./|* untang|
|00004ec0| 6c 65 20 6e 65 74 20 63 | 79 63 6c 65 73 20 66 6f |le net c|ycles fo|
|00004ed0| 72 20 70 72 6f 70 65 72 | 20 6f 75 74 70 75 74 20 |r proper| output |
|00004ee0| 2a 2f 0a 0a 09 66 6f 72 | 20 28 69 20 3d 20 48 61 |*/...for| (i = Ha|
|00004ef0| 73 68 70 61 72 74 3b 20 | 69 20 3c 20 54 61 62 73 |shpart; |i < Tabs|
|00004f00| 69 7a 65 3b 20 69 2b 2b | 29 20 7b 0a 09 09 6e 20 |ize; i++|) {...n |
|00004f10| 3d 20 54 61 62 6c 65 5b | 69 5d 3b 0a 09 09 69 66 |= Table[|i];...if|
|00004f20| 20 28 6e 20 3d 3d 20 30 | 29 0a 09 09 09 63 6f 6e | (n == 0|)....con|
|00004f30| 74 69 6e 75 65 3b 09 2f | 2a 20 69 6d 70 6f 73 73 |tinue;./|* imposs|
|00004f40| 69 62 6c 65 2c 20 62 75 | 74 20 2e 2e 2e 20 2a 2f |ible, bu|t ... */|
|00004f50| 0a 09 09 2f 2a 20 61 20 | 6d 69 6e 6f 72 20 6f 70 |.../* a |minor op|
|00004f60| 74 69 6d 69 7a 61 74 69 | 6f 6e 20 2e 2e 2e 20 2a |timizati|on ... *|
|00004f70| 2f 0a 09 09 69 66 20 28 | 6e 2d 3e 6e 5f 6c 69 6e |/...if (|n->n_lin|
|00004f80| 6b 20 3d 3d 20 30 29 0a | 09 09 09 63 6f 6e 74 69 |k == 0).|...conti|
|00004f90| 6e 75 65 3b 0a 09 09 2f | 2a 20 70 61 74 68 70 61 |nue;.../|* pathpa|
|00004fa0| 72 73 65 20 64 6f 65 73 | 6e 27 74 20 6e 65 65 64 |rse does|n't need|
|00004fb0| 20 74 68 65 73 65 20 2a | 2f 0a 09 09 69 66 20 28 | these *|/...if (|
|00004fc0| 6e 2d 3e 6e 5f 66 6c 61 | 67 20 26 20 4e 4e 45 54 |n->n_fla|g & NNET|
|00004fd0| 29 0a 09 09 09 63 6f 6e | 74 69 6e 75 65 3b 0a 09 |)....con|tinue;..|
|00004fe0| 09 64 75 6d 70 6e 6f 64 | 65 28 6e 29 3b 0a 09 7d |.dumpnod|e(n);..}|
|00004ff0| 0a 7d 0a 0a 64 75 6d 70 | 6e 6f 64 65 28 66 72 6f |.}..dump|node(fro|
|00005000| 6d 29 0a 6e 6f 64 65 09 | 2a 66 72 6f 6d 3b 0a 7b |m).node.|*from;.{|
|00005010| 0a 09 6e 6f 64 65 09 2a | 74 6f 3b 0a 09 6c 69 6e |..node.*|to;..lin|
|00005020| 6b 09 2a 6c 3b 0a 09 63 | 68 61 72 09 6e 65 74 62 |k.*l;..c|har.netb|
|00005030| 75 66 5b 42 55 46 53 49 | 5a 5d 2c 20 2a 6e 70 74 |uf[BUFSI|Z], *npt|
|00005040| 72 20 3d 20 6e 65 74 62 | 75 66 3b 0a 0a 09 66 6f |r = netb|uf;...fo|
|00005050| 72 20 28 6c 20 3d 20 66 | 72 6f 6d 2d 3e 6e 5f 6c |r (l = f|rom->n_l|
|00005060| 69 6e 6b 20 3b 20 6c 3b | 20 6c 20 3d 20 6c 2d 3e |ink ; l;| l = l->|
|00005070| 6c 5f 6e 65 78 74 29 20 | 7b 0a 09 09 74 6f 20 3d |l_next) |{...to =|
|00005080| 20 6c 2d 3e 6c 5f 74 6f | 3b 0a 09 09 69 66 20 28 | l->l_to|;...if (|
|00005090| 66 72 6f 6d 20 3d 3d 20 | 74 6f 29 0a 09 09 09 63 |from == |to)....c|
|000050a0| 6f 6e 74 69 6e 75 65 3b | 09 2f 2a 20 6f 6f 70 73 |ontinue;|./* oops|
|000050b0| 20 2d 2d 20 69 74 27 73 | 20 6d 65 21 20 2a 2f 0a | -- it's| me! */.|
|000050c0| 0a 09 09 69 66 20 28 28 | 74 6f 2d 3e 6e 5f 66 6c |...if ((|to->n_fl|
|000050d0| 61 67 20 26 20 4e 4e 45 | 54 29 20 3d 3d 20 30 29 |ag & NNE|T) == 0)|
|000050e0| 20 7b 0a 09 09 09 2f 2a | 20 68 6f 73 74 20 2d 3e | {..../*| host ->|
|000050f0| 20 68 6f 73 74 20 2d 2d | 20 70 72 69 6e 74 20 68 | host --| print h|
|00005100| 6f 73 74 3e 68 6f 73 74 | 20 2a 2f 0a 09 09 09 69 |ost>host| */....i|
|00005110| 66 20 28 6c 2d 3e 6c 5f | 63 6f 73 74 20 3d 3d 20 |f (l->l_|cost == |
|00005120| 49 4e 46 29 0a 09 09 09 | 09 63 6f 6e 74 69 6e 75 |INF)....|.continu|
|00005130| 65 3b 09 2f 2a 20 70 68 | 6f 6e 65 79 20 6c 69 6e |e;./* ph|oney lin|
|00005140| 6b 20 2a 2f 0a 09 09 09 | 66 70 75 74 73 28 66 72 |k */....|fputs(fr|
|00005150| 6f 6d 2d 3e 6e 5f 6e 61 | 6d 65 2c 20 47 73 74 72 |om->n_na|me, Gstr|
|00005160| 65 61 6d 29 3b 0a 09 09 | 09 70 75 74 63 28 27 3e |eam);...|.putc('>|
|00005170| 27 2c 20 47 73 74 72 65 | 61 6d 29 3b 0a 09 09 09 |', Gstre|am);....|
|00005180| 66 70 75 74 73 28 74 6f | 2d 3e 6e 5f 6e 61 6d 65 |fputs(to|->n_name|
|00005190| 2c 20 47 73 74 72 65 61 | 6d 29 3b 0a 09 09 09 70 |, Gstrea|m);....p|
|000051a0| 75 74 63 28 27 5c 6e 27 | 2c 20 47 73 74 72 65 61 |utc('\n'|, Gstrea|
|000051b0| 6d 29 3b 0a 09 09 7d 20 | 65 6c 73 65 20 7b 0a 09 |m);...} |else {..|
|000051c0| 09 09 2f 2a 20 68 6f 73 | 74 20 2d 3e 20 6e 65 74 |../* hos|t -> net|
|000051d0| 20 2d 2d 20 6a 75 73 74 | 20 63 61 63 68 65 20 69 | -- just| cache i|
|000051e0| 74 20 66 6f 72 20 6e 6f | 77 20 2a 2f 0a 09 09 09 |t for no|w */....|
|000051f0| 77 68 69 6c 65 20 28 74 | 6f 2d 3e 6e 5f 72 6f 6f |while (t|o->n_roo|
|00005200| 74 20 26 26 20 74 6f 20 | 21 3d 20 74 6f 2d 3e 6e |t && to |!= to->n|
|00005210| 5f 72 6f 6f 74 29 0a 09 | 09 09 09 74 6f 20 3d 20 |_root)..|...to = |
|00005220| 74 6f 2d 3e 6e 5f 72 6f | 6f 74 3b 0a 09 09 09 2a |to->n_ro|ot;....*|
|00005230| 6e 70 74 72 2b 2b 20 3d | 20 27 2c 27 3b 0a 09 09 |nptr++ =| ',';...|
|00005240| 09 73 74 72 63 70 79 28 | 6e 70 74 72 2c 20 74 6f |.strcpy(|nptr, to|
|00005250| 2d 3e 6e 5f 6e 61 6d 65 | 29 3b 0a 09 09 09 6e 70 |->n_name|);....np|
|00005260| 74 72 20 2b 3d 20 73 74 | 72 6c 65 6e 28 6e 70 74 |tr += st|rlen(npt|
|00005270| 72 29 3b 0a 09 09 7d 0a | 09 7d 0a 0a 09 2f 2a 20 |r);...}.|.}.../* |
|00005280| 64 75 6d 70 20 6e 65 74 | 73 20 2a 2f 0a 09 69 66 |dump net|s */..if|
|00005290| 20 28 6e 70 74 72 20 21 | 3d 20 6e 65 74 62 75 66 | (nptr !|= netbuf|
|000052a0| 29 20 7b 0a 09 09 2f 2a | 20 6e 65 74 73 20 2d 2d |) {.../*| nets --|
|000052b0| 20 70 72 69 6e 74 20 68 | 6f 73 74 40 5c 74 6e 65 | print h|ost@\tne|
|000052c0| 74 2c 6e 65 74 2c 20 2e | 2e 2e 20 2a 2f 0a 09 09 |t,net, .|.. */...|
|000052d0| 2a 6e 70 74 72 20 3d 20 | 30 3b 0a 09 09 66 70 75 |*nptr = |0;...fpu|
|000052e0| 74 73 28 66 72 6f 6d 2d | 3e 6e 5f 6e 61 6d 65 2c |ts(from-|>n_name,|
|000052f0| 20 47 73 74 72 65 61 6d | 29 3b 0a 09 09 70 75 74 | Gstream|);...put|
|00005300| 63 28 27 40 27 2c 20 47 | 73 74 72 65 61 6d 29 3b |c('@', G|stream);|
|00005310| 0a 09 09 2a 6e 65 74 62 | 75 66 20 3d 20 27 5c 74 |...*netb|uf = '\t|
|00005320| 27 3b 09 2f 2a 20 69 6e | 73 65 72 74 20 74 61 62 |';./* in|sert tab|
|00005330| 20 62 79 20 6b 69 6c 6c | 69 6e 67 20 69 6e 69 74 | by kill|ing init|
|00005340| 69 61 6c 20 27 2c 27 20 | 2a 2f 0a 09 09 66 70 75 |ial ',' |*/...fpu|
|00005350| 74 73 28 6e 65 74 62 75 | 66 2c 20 47 73 74 72 65 |ts(netbu|f, Gstre|
|00005360| 61 6d 29 3b 09 2f 2a 20 | 73 6b 69 70 20 69 6e 69 |am);./* |skip ini|
|00005370| 74 69 61 6c 20 27 2c 27 | 20 2a 2f 0a 09 09 70 75 |tial ','| */...pu|
|00005380| 74 63 28 27 5c 6e 27 2c | 20 47 73 74 72 65 61 6d |tc('\n',| Gstream|
|00005390| 29 3b 0a 09 7d 0a 7d 0a | 0a 2f 2a 0a 20 2a 20 72 |);..}.}.|./*. * r|
|000053a0| 65 6d 6f 76 65 20 63 79 | 63 6c 65 73 20 69 6e 20 |emove cy|cles in |
|000053b0| 6e 65 74 20 64 65 66 69 | 6e 69 74 69 6f 6e 73 2e |net defi|nitions.|
|000053c0| 20 0a 20 2a 0a 20 2a 20 | 64 65 70 74 68 2d 66 69 | . *. * |depth-fi|
|000053d0| 72 73 74 20 73 65 61 72 | 63 68 0a 20 2a 0a 20 2a |rst sear|ch. *. *|
|000053e0| 20 66 6f 72 20 65 61 63 | 68 20 6e 65 74 2c 20 72 | for eac|h net, r|
|000053f0| 75 6e 20 64 66 73 20 6f | 6e 20 69 74 73 20 6e 65 |un dfs o|n its ne|
|00005400| 69 67 68 62 6f 72 73 20 | 28 6e 65 74 73 20 6f 6e |ighbors |(nets on|
|00005410| 6c 79 29 2e 20 20 69 66 | 20 77 65 20 72 65 74 75 |ly).  if| we retu|
|00005420| 72 6e 20 74 6f 0a 20 2a | 20 61 20 76 69 73 69 74 |rn to. *| a visit|
|00005430| 65 64 20 6e 6f 64 65 2c | 20 74 68 61 74 27 73 20 |ed node,| that's |
|00005440| 61 20 6e 65 74 20 63 79 | 63 6c 65 2e 20 20 6d 61 |a net cy|cle.  ma|
|00005450| 72 6b 20 74 68 65 20 63 | 79 63 6c 65 20 77 69 74 |rk the c|ycle wit|
|00005460| 68 20 61 20 70 6f 69 6e | 74 65 72 0a 20 2a 20 69 |h a poin|ter. * i|
|00005470| 6e 20 74 68 65 20 6e 5f | 72 6f 6f 74 20 66 69 65 |n the n_|root fie|
|00005480| 6c 64 20 28 77 68 69 63 | 68 20 67 65 74 73 20 75 |ld (whic|h gets u|
|00005490| 73 20 63 6c 6f 73 65 72 | 20 74 6f 20 74 68 65 20 |s closer| to the |
|000054a0| 72 6f 6f 74 20 6f 66 20 | 74 68 69 73 0a 20 2a 20 |root of |this. * |
|000054b0| 70 6f 72 74 69 6f 6e 20 | 6f 66 20 74 68 65 20 64 |portion |of the d|
|000054c0| 66 73 20 74 72 65 65 29 | 2e 0a 20 2a 2f 0a 75 6e |fs tree)|.. */.un|
|000054d0| 74 61 6e 67 6c 65 28 29 | 0a 7b 0a 09 6c 6f 6e 67 |tangle()|.{..long|
|000054e0| 09 69 3b 0a 09 6e 6f 64 | 65 09 2a 6e 3b 0a 0a 09 |.i;..nod|e.*n;...|
|000054f0| 66 6f 72 20 28 69 20 3d | 20 48 61 73 68 70 61 72 |for (i =| Hashpar|
|00005500| 74 3b 20 69 20 3c 20 54 | 61 62 73 69 7a 65 3b 20 |t; i < T|absize; |
|00005510| 69 2b 2b 29 20 7b 0a 09 | 09 6e 20 3d 20 54 61 62 |i++) {..|.n = Tab|
|00005520| 6c 65 5b 69 5d 3b 0a 09 | 09 69 66 20 28 6e 20 3d |le[i];..|.if (n =|
|00005530| 3d 20 30 20 7c 7c 20 28 | 6e 2d 3e 6e 5f 66 6c 61 |= 0 || (|n->n_fla|
|00005540| 67 20 26 20 4e 4e 45 54 | 29 20 3d 3d 20 30 20 7c |g & NNET|) == 0 ||
|00005550| 7c 20 6e 2d 3e 6e 5f 72 | 6f 6f 74 29 0a 09 09 09 || n->n_r|oot)....|
|00005560| 63 6f 6e 74 69 6e 75 65 | 3b 0a 09 09 64 66 73 28 |continue|;...dfs(|
|00005570| 6e 29 3b 0a 09 7d 0a 7d | 0a 0a 64 66 73 28 6e 29 |n);..}.}|..dfs(n)|
|00005580| 0a 6e 6f 64 65 09 2a 6e | 3b 0a 7b 0a 09 6c 69 6e |.node.*n|;.{..lin|
|00005590| 6b 09 2a 6c 3b 0a 09 6e | 6f 64 65 09 2a 6e 65 78 |k.*l;..n|ode.*nex|
|000055a0| 74 3b 0a 0a 09 6e 2d 3e | 6e 5f 66 6c 61 67 20 7c |t;...n->|n_flag ||
|000055b0| 3d 20 49 4e 44 46 53 3b | 0a 09 6e 2d 3e 6e 5f 72 |= INDFS;|..n->n_r|
|000055c0| 6f 6f 74 20 3d 20 6e 3b | 0a 09 66 6f 72 20 28 6c |oot = n;|..for (l|
|000055d0| 20 3d 20 6e 2d 3e 6e 5f | 6c 69 6e 6b 3b 20 6c 3b | = n->n_|link; l;|
|000055e0| 20 6c 20 3d 20 6c 2d 3e | 6c 5f 6e 65 78 74 29 20 | l = l->|l_next) |
|000055f0| 7b 0a 09 09 6e 65 78 74 | 20 3d 20 6c 2d 3e 6c 5f |{...next| = l->l_|
|00005600| 74 6f 3b 0a 09 09 69 66 | 20 28 28 6e 65 78 74 2d |to;...if| ((next-|
|00005610| 3e 6e 5f 66 6c 61 67 20 | 26 20 4e 4e 45 54 29 20 |>n_flag |& NNET) |
|00005620| 3d 3d 20 30 29 0a 09 09 | 09 63 6f 6e 74 69 6e 75 |== 0)...|.continu|
|00005630| 65 3b 0a 09 09 69 66 20 | 28 28 6e 65 78 74 2d 3e |e;...if |((next->|
|00005640| 6e 5f 66 6c 61 67 20 26 | 20 49 4e 44 46 53 29 20 |n_flag &| INDFS) |
|00005650| 3d 3d 20 30 29 20 7b 0a | 09 09 09 64 66 73 28 6e |== 0) {.|...dfs(n|
|00005660| 65 78 74 29 3b 0a 09 09 | 09 69 66 20 28 6e 65 78 |ext);...|.if (nex|
|00005670| 74 2d 3e 6e 5f 72 6f 6f | 74 20 21 3d 20 6e 65 78 |t->n_roo|t != nex|
|00005680| 74 29 0a 09 09 09 09 6e | 2d 3e 6e 5f 72 6f 6f 74 |t).....n|->n_root|
|00005690| 20 3d 20 6e 65 78 74 2d | 3e 6e 5f 72 6f 6f 74 3b | = next-|>n_root;|
|000056a0| 0a 09 09 7d 20 65 6c 73 | 65 0a 09 09 09 6e 2d 3e |...} els|e....n->|
|000056b0| 6e 5f 72 6f 6f 74 20 3d | 20 6e 65 78 74 2d 3e 6e |n_root =| next->n|
|000056c0| 5f 72 6f 6f 74 3b 0a 09 | 7d 0a 09 6e 2d 3e 6e 5f |_root;..|}..n->n_|
|000056d0| 66 6c 61 67 20 26 3d 20 | 7e 49 4e 44 46 53 3b 0a |flag &= |~INDFS;.|
|000056e0| 7d 0a 0a 73 68 6f 77 6c | 69 6e 6b 73 28 29 20 0a |}..showl|inks() .|
|000056f0| 7b 0a 09 6c 69 6e 6b 09 | 2a 6c 3b 0a 09 6e 6f 64 |{..link.|*l;..nod|
|00005700| 65 09 2a 6e 3b 0a 09 6c | 6f 6e 67 09 69 3b 0a 09 |e.*n;..l|ong.i;..|
|00005710| 46 49 4c 45 09 2a 65 73 | 74 72 65 61 6d 3b 0a 0a |FILE.*es|tream;..|
|00005720| 09 69 66 20 28 28 65 73 | 74 72 65 61 6d 20 3d 20 |.if ((es|tream = |
|00005730| 66 6f 70 65 6e 28 4c 69 | 6e 6b 6f 75 74 2c 20 22 |fopen(Li|nkout, "|
|00005740| 77 22 29 29 20 3d 3d 20 | 30 29 0a 09 09 72 65 74 |w")) == |0)...ret|
|00005750| 75 72 6e 3b 0a 0a 09 66 | 6f 72 20 28 69 20 3d 20 |urn;...f|or (i = |
|00005760| 48 61 73 68 70 61 72 74 | 3b 20 69 20 3c 20 54 61 |Hashpart|; i < Ta|
|00005770| 62 73 69 7a 65 3b 20 69 | 2b 2b 29 20 7b 0a 09 09 |bsize; i|++) {...|
|00005780| 6e 20 3d 20 54 61 62 6c | 65 5b 69 5d 3b 0a 09 09 |n = Tabl|e[i];...|
|00005790| 69 66 20 28 6e 20 3d 3d | 20 30 29 09 2f 2a 20 69 |if (n ==| 0)./* i|
|000057a0| 6d 70 6f 73 73 69 62 6c | 65 2c 20 62 75 74 20 2e |mpossibl|e, but .|
|000057b0| 2e 2e 20 2a 2f 0a 09 09 | 09 63 6f 6e 74 69 6e 75 |.. */...|.continu|
|000057c0| 65 3b 0a 09 09 69 66 20 | 28 6c 20 3d 20 6e 2d 3e |e;...if |(l = n->|
|000057d0| 6e 5f 6c 69 6e 6b 29 20 | 7b 0a 09 09 09 66 70 72 |n_link) |{....fpr|
|000057e0| 69 6e 74 66 28 65 73 74 | 72 65 61 6d 2c 20 22 25 |intf(est|ream, "%|
|000057f0| 73 5c 74 25 73 28 25 64 | 29 22 2c 20 6e 2d 3e 6e |s\t%s(%d|)", n->n|
|00005800| 5f 6e 61 6d 65 2c 0a 09 | 09 09 09 6c 2d 3e 6c 5f |_name,..|...l->l_|
|00005810| 74 6f 2d 3e 6e 5f 6e 61 | 6d 65 2c 0a 09 09 09 09 |to->n_na|me,.....|
|00005820| 6c 2d 3e 6c 5f 63 6f 73 | 74 20 3f 20 6c 2d 3e 6c |l->l_cos|t ? l->l|
|00005830| 5f 63 6f 73 74 20 3a 20 | 44 45 46 43 4f 53 54 29 |_cost : |DEFCOST)|
|00005840| 3b 0a 09 09 09 66 6f 72 | 20 28 6c 20 3d 20 6c 2d |;....for| (l = l-|
|00005850| 3e 6c 5f 6e 65 78 74 3b | 20 6c 3b 20 6c 20 3d 20 |>l_next;| l; l = |
|00005860| 6c 2d 3e 6c 5f 6e 65 78 | 74 29 0a 09 09 09 09 66 |l->l_nex|t).....f|
|00005870| 70 72 69 6e 74 66 28 65 | 73 74 72 65 61 6d 2c 20 |printf(e|stream, |
|00005880| 22 2c 5c 6e 5c 74 25 73 | 28 25 64 29 22 2c 20 6c |",\n\t%s|(%d)", l|
|00005890| 2d 3e 6c 5f 74 6f 2d 3e | 6e 5f 6e 61 6d 65 2c 0a |->l_to->|n_name,.|
|000058a0| 09 09 09 09 09 6c 2d 3e | 6c 5f 63 6f 73 74 20 3f |.....l->|l_cost ?|
|000058b0| 20 6c 2d 3e 6c 5f 63 6f | 73 74 20 3a 20 44 45 46 | l->l_co|st : DEF|
|000058c0| 43 4f 53 54 29 3b 0a 09 | 09 09 66 70 75 74 63 28 |COST);..|..fputc(|
|000058d0| 27 5c 6e 27 2c 20 65 73 | 74 72 65 61 6d 29 3b 0a |'\n', es|tream);.|
|000058e0| 09 09 7d 0a 09 7d 0a 09 | 28 76 6f 69 64 29 20 66 |..}..}..|(void) f|
|000058f0| 63 6c 6f 73 65 28 65 73 | 74 72 65 61 6d 29 3b 0a |close(es|tream);.|
|00005900| 7d 0a 0a 2f 2a 0a 20 2a | 20 6e 20 69 73 20 6e 6f |}../*. *| n is no|
|00005910| 64 65 20 69 6e 20 68 65 | 61 70 2c 20 6e 65 77 70 |de in he|ap, newp|
|00005920| 20 69 73 20 63 61 6e 64 | 69 64 61 74 65 20 66 6f | is cand|idate fo|
|00005930| 72 20 6e 65 77 20 70 61 | 72 65 6e 74 2e 0a 20 2a |r new pa|rent.. *|
|00005940| 20 63 68 6f 6f 73 65 20 | 62 65 74 77 65 65 6e 20 | choose |between |
|00005950| 6e 65 77 70 20 61 6e 64 | 20 6e 2d 3e 6e 5f 70 61 |newp and| n->n_pa|
|00005960| 72 65 6e 74 20 66 6f 72 | 20 70 61 72 65 6e 74 2e |rent for| parent.|
|00005970| 0a 20 2a 20 72 65 74 75 | 72 6e 20 30 20 74 6f 20 |. * retu|rn 0 to |
|00005980| 75 73 65 20 6e 65 77 70 | 2c 20 6e 6f 6e 2d 7a 65 |use newp|, non-ze|
|00005990| 72 6f 20 6f 2e 77 2e 0a | 20 2a 2f 0a 23 64 65 66 |ro o.w..| */.#def|
|000059a0| 69 6e 65 20 4e 45 57 50 | 20 30 0a 23 64 65 66 69 |ine NEWP| 0.#defi|
|000059b0| 6e 65 20 4f 4c 44 50 20 | 31 0a 74 69 65 62 72 65 |ne OLDP |1.tiebre|
|000059c0| 61 6b 65 72 28 6e 2c 20 | 6e 65 77 70 29 0a 6e 6f |aker(n, |newp).no|
|000059d0| 64 65 09 2a 6e 2c 20 2a | 6e 65 77 70 3b 0a 7b 0a |de.*n, *|newp;.{.|
|000059e0| 09 72 65 67 69 73 74 65 | 72 20 63 68 61 72 09 2a |.registe|r char.*|
|000059f0| 6f 70 6e 61 6d 65 2c 20 | 2a 6e 70 6e 61 6d 65 2c |opname, |*npname,|
|00005a00| 20 2a 6e 61 6d 65 3b 0a | 09 6e 6f 64 65 09 2a 6f | *name;.|.node.*o|
|00005a10| 6c 64 70 3b 0a 09 69 6e | 74 09 6d 65 74 72 69 63 |ldp;..in|t.metric|
|00005a20| 3b 0a 0a 09 6f 6c 64 70 | 20 3d 20 6e 2d 3e 6e 5f |;...oldp| = n->n_|
|00005a30| 70 61 72 65 6e 74 3b 0a | 0a 09 2f 2a 0a 09 20 2a |parent;.|../*.. *|
|00005a40| 20 67 69 76 65 6e 20 74 | 68 65 20 63 68 6f 69 63 | given t|he choic|
|00005a50| 65 20 6f 66 20 67 6f 69 | 6e 67 20 74 68 72 6f 75 |e of goi|ng throu|
|00005a60| 67 68 20 61 20 67 61 74 | 65 77 61 79 65 64 20 6e |gh a gat|ewayed n|
|00005a70| 6f 74 20 6f 72 20 6e 6f | 74 2c 0a 09 20 2a 20 63 |ot or no|t,.. * c|
|00005a80| 68 6f 6f 73 65 20 74 68 | 65 20 6c 61 74 74 65 72 |hoose th|e latter|
|00005a90| 2c 20 70 6c 61 63 61 74 | 69 6e 67 20 74 68 65 20 |, placat|ing the |
|00005aa0| 46 43 43 20 6f 72 20 77 | 68 61 74 65 76 65 72 2e |FCC or w|hatever.|
|00005ab0| 0a 09 20 2a 2f 0a 09 69 | 66 20 28 47 41 54 45 57 |.. */..i|f (GATEW|
|00005ac0| 41 59 45 44 28 6e 65 77 | 70 29 20 26 26 20 21 47 |AYED(new|p) && !G|
|00005ad0| 41 54 45 57 41 59 45 44 | 28 6f 6c 64 70 29 29 0a |ATEWAYED|(oldp)).|
|00005ae0| 09 09 72 65 74 75 72 6e | 28 6f 6c 64 70 29 3b 0a |..return|(oldp);.|
|00005af0| 09 69 66 20 28 21 47 41 | 54 45 57 41 59 45 44 28 |.if (!GA|TEWAYED(|
|00005b00| 6e 65 77 70 29 20 26 26 | 20 47 41 54 45 57 41 59 |newp) &&| GATEWAY|
|00005b10| 45 44 28 6f 6c 64 70 29 | 29 0a 09 09 72 65 74 75 |ED(oldp)|)...retu|
|00005b20| 72 6e 28 6e 65 77 70 29 | 3b 0a 0a 09 2f 2a 20 6c |rn(newp)|;.../* l|
|00005b30| 6f 6f 6b 20 61 74 20 72 | 65 61 6c 20 70 61 72 65 |ook at r|eal pare|
|00005b40| 6e 74 73 2c 20 6e 6f 74 | 20 6e 65 74 73 20 2a 2f |nts, not| nets */|
|00005b50| 0a 09 77 68 69 6c 65 20 | 28 6f 6c 64 70 2d 3e 6e |..while |(oldp->n|
|00005b60| 5f 66 6c 61 67 20 26 20 | 4e 4e 45 54 29 0a 09 09 |_flag & |NNET)...|
|00005b70| 6f 6c 64 70 20 3d 20 6f | 6c 64 70 2d 3e 6e 5f 70 |oldp = o|ldp->n_p|
|00005b80| 61 72 65 6e 74 3b 0a 09 | 77 68 69 6c 65 20 28 6e |arent;..|while (n|
|00005b90| 65 77 70 2d 3e 6e 5f 66 | 6c 61 67 20 26 20 4e 4e |ewp->n_f|lag & NN|
|00005ba0| 45 54 29 0a 09 09 6e 65 | 77 70 20 3d 20 6e 65 77 |ET)...ne|wp = new|
|00005bb0| 70 2d 3e 6e 5f 70 61 72 | 65 6e 74 3b 0a 0a 09 2f |p->n_par|ent;.../|
|00005bc0| 2a 20 75 73 65 20 66 65 | 77 65 72 20 68 6f 70 73 |* use fe|wer hops|
|00005bd0| 2c 20 69 66 20 70 6f 73 | 73 69 62 6c 65 20 2a 2f |, if pos|sible */|
|00005be0| 0a 09 6d 65 74 72 69 63 | 20 3d 20 68 65 69 67 68 |..metric| = heigh|
|00005bf0| 74 28 6f 6c 64 70 29 20 | 2d 20 68 65 69 67 68 74 |t(oldp) |- height|
|00005c00| 28 6e 65 77 70 29 3b 0a | 09 69 66 20 28 6d 65 74 |(newp);.|.if (met|
|00005c10| 72 69 63 20 3c 20 30 29 | 0a 09 09 72 65 74 75 72 |ric < 0)|...retur|
|00005c20| 6e 28 4f 4c 44 50 29 3b | 0a 09 69 66 20 28 6d 65 |n(OLDP);|..if (me|
|00005c30| 74 72 69 63 20 3e 20 30 | 29 0a 09 09 72 65 74 75 |tric > 0|)...retu|
|00005c40| 72 6e 28 4e 45 57 50 29 | 3b 0a 0a 09 2f 2a 20 63 |rn(NEWP)|;.../* c|
|00005c50| 6f 6d 70 61 72 65 20 6e | 61 6d 65 73 20 2a 2f 0a |ompare n|ames */.|
|00005c60| 09 6f 70 6e 61 6d 65 20 | 3d 20 6f 6c 64 70 2d 3e |.opname |= oldp->|
|00005c70| 6e 5f 6e 61 6d 65 3b 0a | 09 6e 70 6e 61 6d 65 20 |n_name;.|.npname |
|00005c80| 3d 20 6e 65 77 70 2d 3e | 6e 5f 6e 61 6d 65 3b 0a |= newp->|n_name;.|
|00005c90| 09 6e 61 6d 65 20 3d 20 | 6e 2d 3e 6e 5f 6e 61 6d |.name = |n->n_nam|
|00005ca0| 65 3b 0a 0a 09 2f 2a 20 | 66 69 6e 64 20 70 6f 69 |e;.../* |find poi|
|00005cb0| 6e 74 20 6f 66 20 64 65 | 70 61 72 74 75 72 65 20 |nt of de|parture |
|00005cc0| 2a 2f 0a 09 77 68 69 6c | 65 20 28 2a 6f 70 6e 61 |*/..whil|e (*opna|
|00005cd0| 6d 65 20 3d 3d 20 2a 6e | 70 6e 61 6d 65 20 26 26 |me == *n|pname &&|
|00005ce0| 20 2a 6e 70 6e 61 6d 65 | 20 3d 3d 20 2a 6e 61 6d | *npname| == *nam|
|00005cf0| 65 29 20 7b 0a 09 09 69 | 66 20 28 2a 6e 61 6d 65 |e) {...i|f (*name|
|00005d00| 20 3d 3d 20 30 29 20 7b | 0a 09 09 09 66 70 72 69 | == 0) {|....fpri|
|00005d10| 6e 74 66 28 73 74 64 65 | 72 72 2c 20 22 25 73 3a |ntf(stde|rr, "%s:|
|00005d20| 20 65 72 72 6f 72 20 69 | 6e 20 74 69 65 20 62 72 | error i|n tie br|
|00005d30| 65 61 6b 65 72 5c 6e 22 | 2c 20 50 72 6f 67 4e 61 |eaker\n"|, ProgNa|
|00005d40| 6d 65 29 3b 0a 09 09 09 | 62 61 64 6d 61 67 69 63 |me);....|badmagic|
|00005d50| 28 31 29 3b 0a 09 09 7d | 0a 09 09 6f 70 6e 61 6d |(1);...}|...opnam|
|00005d60| 65 2b 2b 3b 0a 09 09 6e | 70 6e 61 6d 65 2b 2b 3b |e++;...n|pname++;|
|00005d70| 0a 09 09 6e 61 6d 65 2b | 2b 3b 0a 09 7d 0a 0a 09 |...name+|+;..}...|
|00005d80| 2f 2a 20 75 73 65 20 6c | 6f 6e 67 65 73 74 20 6d |/* use l|ongest m|
|00005d90| 61 74 63 68 2c 20 69 66 | 20 61 70 70 6c 2e 20 2a |atch, if| appl. *|
|00005da0| 2f 0a 09 69 66 20 28 2a | 6f 70 6e 61 6d 65 20 3d |/..if (*|opname =|
|00005db0| 3d 20 2a 6e 61 6d 65 20 | 7c 7c 20 2a 6f 70 6e 61 |= *name ||| *opna|
|00005dc0| 6d 65 20 3d 3d 20 30 29 | 0a 09 09 72 65 74 75 72 |me == 0)|...retur|
|00005dd0| 6e 28 4f 4c 44 50 29 3b | 0a 09 69 66 20 28 2a 6e |n(OLDP);|..if (*n|
|00005de0| 70 6e 61 6d 65 20 3d 3d | 20 2a 6e 61 6d 65 20 7c |pname ==| *name ||
|00005df0| 7c 20 2a 6e 70 6e 61 6d | 65 20 3d 3d 20 30 29 0a || *npnam|e == 0).|
|00005e00| 09 09 72 65 74 75 72 6e | 28 4e 45 57 50 29 3b 0a |..return|(NEWP);.|
|00005e10| 0a 09 2f 2a 20 75 73 65 | 20 73 68 6f 72 74 65 72 |../* use| shorter|
|00005e20| 20 68 6f 73 74 20 6e 61 | 6d 65 2c 20 69 66 20 61 | host na|me, if a|
|00005e30| 70 70 6c 2e 20 2a 2f 0a | 09 6d 65 74 72 69 63 20 |ppl. */.|.metric |
|00005e40| 3d 20 73 74 72 6c 65 6e | 28 6f 70 6e 61 6d 65 29 |= strlen|(opname)|
|00005e50| 20 2d 20 73 74 72 6c 65 | 6e 28 6e 70 6e 61 6d 65 | - strle|n(npname|
|00005e60| 29 3b 0a 09 69 66 20 28 | 6d 65 74 72 69 63 20 3c |);..if (|metric <|
|00005e70| 20 30 29 0a 09 09 72 65 | 74 75 72 6e 28 4f 4c 44 | 0)...re|turn(OLD|
|00005e80| 50 29 3b 0a 09 69 66 20 | 28 6d 65 74 72 69 63 20 |P);..if |(metric |
|00005e90| 3e 20 30 29 0a 09 09 72 | 65 74 75 72 6e 28 4e 45 |> 0)...r|eturn(NE|
|00005ea0| 57 50 29 3b 0a 0a 09 2f | 2a 20 75 73 65 20 6c 61 |WP);.../|* use la|
|00005eb0| 72 67 65 72 20 6c 65 78 | 69 63 6f 67 72 61 70 68 |rger lex|icograph|
|00005ec0| 69 63 61 6c 6c 79 20 28 | 6e 6f 20 72 65 61 73 6f |ically (|no reaso|
|00005ed0| 6e 29 20 2a 2f 0a 09 6d | 65 74 72 69 63 20 3d 20 |n) */..m|etric = |
|00005ee0| 73 74 72 63 6d 70 28 6f | 70 6e 61 6d 65 2c 20 6e |strcmp(o|pname, n|
|00005ef0| 70 6e 61 6d 65 29 3b 0a | 09 69 66 20 28 6d 65 74 |pname);.|.if (met|
|00005f00| 72 69 63 20 3c 20 30 29 | 0a 09 09 72 65 74 75 72 |ric < 0)|...retur|
|00005f10| 6e 28 4e 45 57 50 29 3b | 0a 09 72 65 74 75 72 6e |n(NEWP);|..return|
|00005f20| 28 4f 4c 44 50 29 3b 0a | 7d 0a 0a 68 65 69 67 68 |(OLDP);.|}..heigh|
|00005f30| 74 28 6e 29 0a 72 65 67 | 69 73 74 65 72 20 6e 6f |t(n).reg|ister no|
|00005f40| 64 65 09 2a 6e 3b 0a 7b | 0a 09 72 65 67 69 73 74 |de.*n;.{|..regist|
|00005f50| 65 72 20 69 6e 74 20 69 | 20 3d 20 30 3b 0a 0a 09 |er int i| = 0;...|
|00005f60| 77 68 69 6c 65 20 28 28 | 6e 20 3d 20 6e 2d 3e 6e |while ((|n = n->n|
|00005f70| 5f 70 61 72 65 6e 74 29 | 20 21 3d 20 30 29 0a 09 |_parent)| != 0)..|
|00005f80| 09 69 66 20 28 28 6e 2d | 3e 6e 5f 66 6c 61 67 20 |.if ((n-|>n_flag |
|00005f90| 26 20 4e 4e 45 54 29 20 | 3d 3d 20 30 29 0a 09 09 |& NNET) |== 0)...|
|00005fa0| 09 69 2b 2b 3b 09 2f 2a | 20 73 68 6f 75 6c 64 20 |.i++;./*| should |
|00005fb0| 63 6f 75 6e 74 20 64 6f | 6d 61 69 6e 73 20 74 6f |count do|mains to|
|00005fc0| 6f 20 2e 2e 2e 20 2a 2f | 0a 09 72 65 74 75 72 6e |o ... */|..return|
|00005fd0| 28 69 29 3b 0a 7d 0a 53 | 48 41 52 5f 45 4f 46 0a |(i);.}.S|HAR_EOF.|
|00005fe0| 69 66 20 74 65 73 74 20 | 35 31 36 38 20 2d 6e 65 |if test |5168 -ne|
|00005ff0| 20 22 60 77 63 20 2d 63 | 20 3c 20 27 6d 61 70 61 | "`wc -c| < 'mapa|
|00006000| 75 78 2e 63 27 60 22 0a | 74 68 65 6e 0a 09 65 63 |ux.c'`".|then..ec|
|00006010| 68 6f 20 73 68 61 72 3a | 20 65 72 72 6f 72 20 74 |ho shar:| error t|
|00006020| 72 61 6e 73 6d 69 74 74 | 69 6e 67 20 22 27 6d 61 |ransmitt|ing "'ma|
|00006030| 70 61 75 78 2e 63 27 22 | 20 27 28 73 68 6f 75 6c |paux.c'"| '(shoul|
|00006040| 64 20 68 61 76 65 20 62 | 65 65 6e 20 35 31 36 38 |d have b|een 5168|
|00006050| 20 63 68 61 72 61 63 74 | 65 72 73 29 27 0a 66 69 | charact|ers)'.fi|
|00006060| 0a 66 69 0a 65 63 68 6f | 20 73 68 61 72 3a 20 65 |.fi.echo| shar: e|
|00006070| 78 74 72 61 63 74 69 6e | 67 20 22 27 6d 61 70 69 |xtractin|g "'mapi|
|00006080| 74 2e 63 27 22 20 27 28 | 31 30 34 36 39 20 63 68 |t.c'" '(|10469 ch|
|00006090| 61 72 61 63 74 65 72 73 | 29 27 0a 69 66 20 74 65 |aracters|)'.if te|
|000060a0| 73 74 20 2d 66 20 27 6d | 61 70 69 74 2e 63 27 0a |st -f 'm|apit.c'.|
|000060b0| 74 68 65 6e 0a 09 65 63 | 68 6f 20 73 68 61 72 3a |then..ec|ho shar:|
|000060c0| 20 77 69 6c 6c 20 6e 6f | 74 20 6f 76 65 72 2d 77 | will no|t over-w|
|000060d0| 72 69 74 65 20 65 78 69 | 73 74 69 6e 67 20 66 69 |rite exi|sting fi|
|000060e0| 6c 65 20 22 27 6d 61 70 | 69 74 2e 63 27 22 0a 65 |le "'map|it.c'".e|
|000060f0| 6c 73 65 0a 63 61 74 20 | 3c 3c 20 5c 53 48 41 52 |lse.cat |<< \SHAR|
|00006100| 5f 45 4f 46 20 3e 20 27 | 6d 61 70 69 74 2e 63 27 |_EOF > '|mapit.c'|
|00006110| 0a 2f 2a 20 70 61 74 68 | 61 6c 69 61 73 20 2d 2d |./* path|alias --|
|00006120| 20 62 79 20 73 74 65 76 | 65 20 62 65 6c 6c 6f 76 | by stev|e bellov|
|00006130| 69 6e 2c 20 61 73 20 74 | 6f 6c 64 20 74 6f 20 70 |in, as t|old to p|
|00006140| 65 74 65 72 20 68 6f 6e | 65 79 6d 61 6e 20 2a 2f |eter hon|eyman */|
|00006150| 0a 23 69 66 6e 64 65 66 | 20 6c 69 6e 74 0a 73 74 |.#ifndef| lint.st|
|00006160| 61 74 69 63 20 63 68 61 | 72 09 2a 73 63 63 73 69 |atic cha|r.*sccsi|
|00006170| 64 20 3d 20 22 40 28 23 | 29 6d 61 70 69 74 2e 63 |d = "@(#|)mapit.c|
|00006180| 09 38 2e 31 20 28 64 6f | 77 6e 21 68 6f 6e 65 79 |.8.1 (do|wn!honey|
|00006190| 29 20 38 36 2f 30 31 2f | 31 39 22 3b 0a 23 65 6e |) 86/01/|19";.#en|
|000061a0| 64 69 66 0a 0a 23 69 6e | 63 6c 75 64 65 20 22 64 |dif..#in|clude "d|
|000061b0| 65 66 2e 68 22 0a 0a 2f | 2a 20 70 72 69 76 61 74 |ef.h"../|* privat|
|000061c0| 65 73 20 2a 2f 0a 65 78 | 74 65 72 6e 20 76 6f 69 |es */.ex|tern voi|
|000061d0| 64 09 72 65 68 65 61 70 | 28 29 2c 20 69 6e 73 65 |d.reheap|(), inse|
|000061e0| 72 74 28 29 2c 20 68 65 | 61 70 73 77 61 70 28 29 |rt(), he|apswap()|
|000061f0| 3b 0a 65 78 74 65 72 6e | 20 6c 69 6e 6b 09 2a 6d |;.extern| link.*m|
|00006200| 69 6e 5f 6e 6f 64 65 28 | 29 2c 20 2a 72 6d 6c 69 |in_node(|), *rmli|
|00006210| 6e 6b 28 29 3b 0a 65 78 | 74 65 72 6e 20 43 6f 73 |nk();.ex|tern Cos|
|00006220| 74 09 63 6f 73 74 6f 66 | 28 29 3b 0a 0a 73 74 61 |t.costof|();..sta|
|00006230| 74 69 63 20 6c 6f 6e 67 | 09 4e 68 65 61 70 3b 0a |tic long|.Nheap;.|
|00006240| 73 74 61 74 69 63 20 6c | 6f 6e 67 09 48 65 61 70 |static l|ong.Heap|
|00006250| 68 69 67 68 77 61 74 65 | 72 3b 0a 73 74 61 74 69 |highwate|r;.stati|
|00006260| 63 20 6c 69 6e 6b 09 2a | 2a 48 65 61 70 3b 0a 0a |c link.*|*Heap;..|
|00006270| 0a 2f 2a 20 74 72 61 6e | 73 66 6f 72 6d 20 74 68 |./* tran|sform th|
|00006280| 65 20 67 72 61 70 68 20 | 74 6f 20 61 20 73 68 6f |e graph |to a sho|
|00006290| 72 74 65 73 74 2d 70 61 | 74 68 20 74 72 65 65 20 |rtest-pa|th tree |
|000062a0| 62 79 20 6d 61 72 6b 69 | 6e 67 20 74 72 65 65 20 |by marki|ng tree |
|000062b0| 65 64 67 65 73 20 2a 2f | 0a 0a 6d 61 70 69 74 28 |edges */|..mapit(|
|000062c0| 29 0a 7b 0a 09 72 65 67 | 69 73 74 65 72 20 6e 6f |).{..reg|ister no|
|000062d0| 64 65 20 2a 6e 2c 20 2a | 6e 65 78 74 3b 0a 09 72 |de *n, *|next;..r|
|000062e0| 65 67 69 73 74 65 72 20 | 6c 69 6e 6b 20 2a 6c 3b |egister |link *l;|
|000062f0| 0a 09 6c 69 6e 6b 09 2a | 6c 70 72 65 76 2c 20 2a |..link.*|lprev, *|
|00006300| 6c 6e 65 78 74 3b 0a 09 | 43 6f 73 74 20 63 6f 73 |lnext;..|Cost cos|
|00006310| 74 3b 0a 0a 09 2f 2a 0a | 09 20 2a 20 72 65 2d 75 |t;.../*.|. * re-u|
|00006320| 73 65 20 74 68 65 20 68 | 61 73 68 20 74 61 62 6c |se the h|ash tabl|
|00006330| 65 20 73 70 61 63 65 20 | 66 6f 72 20 74 68 65 20 |e space |for the |
|00006340| 68 65 61 70 2e 0a 09 20 | 2a 2f 0a 09 48 65 61 70 |heap... |*/..Heap|
|00006350| 20 3d 20 28 6c 69 6e 6b | 20 2a 2a 29 20 54 61 62 | = (link| **) Tab|
|00006360| 6c 65 3b 0a 0a 09 70 61 | 63 6b 28 29 3b 09 09 2f |le;...pa|ck();../|
|00006370| 2a 20 72 65 6d 6f 76 65 | 20 68 6f 6c 65 73 20 69 |* remove| holes i|
|00006380| 6e 20 74 68 65 20 54 61 | 62 6c 65 20 2a 2f 0a 09 |n the Ta|ble */..|
|00006390| 69 66 20 28 4c 69 6e 6b | 6f 75 74 20 26 26 20 2a |if (Link|out && *|
|000063a0| 4c 69 6e 6b 6f 75 74 29 | 09 2f 2a 20 64 75 6d 70 |Linkout)|./* dump|
|000063b0| 20 63 68 65 61 70 65 73 | 74 20 6c 69 6e 6b 73 20 | cheapes|t links |
|000063c0| 2a 2f 0a 09 09 73 68 6f | 77 6c 69 6e 6b 73 28 29 |*/...sho|wlinks()|
|000063d0| 3b 0a 09 69 66 20 28 47 | 72 61 70 68 6f 75 74 20 |;..if (G|raphout |
|000063e0| 26 26 20 2a 47 72 61 70 | 68 6f 75 74 29 09 2f 2a |&& *Grap|hout)./*|
|000063f0| 20 64 75 6d 70 20 74 68 | 65 20 65 64 67 65 20 6c | dump th|e edge l|
+--------+-------------------------+-------------------------+--------+--------+