2 %%Creator: utopia:margo (& Seltzer,608-13E,8072,)
3 %%Title: stdin (ditroff)
4 %%CreationDate: Tue Dec 11 15:06:45 1990
6 % @(#)psdit.pro 1.3 4/15/88
7 % lib/psdit.pro -- prolog for psdit (ditroff) files
8 % Copyright (c) 1984, 1985 Adobe Systems Incorporated. All Rights Reserved.
9 % last edit: shore Sat Nov 23 20:28:03 1985
10 % RCSID: $FreeBSD: src/lib/libc/db/docs/hash.usenix.ps,v 1.2 1999/08/28 05:03:14 peter Exp $
11 % RCSID: $DragonFly: src/lib/libc/db/docs/hash.usenix.ps,v 1.2 2003/06/17 04:26:41 dillon Exp $
13 % Changed by Edward Wang (edward@ucbarpa.berkeley.edu) to handle graphics,
16 /$DITroff 140 dict def $DITroff begin
17 /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
18 /xi{0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
19 /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
20 /pagesave save def}def
21 /PB{save /psv exch def currentpoint translate
22 resolution 72 div dup neg scale 0 0 moveto}def
24 /arctoobig 90 def /arctoosmall .05 def
25 /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
26 /tan{dup sin exch cos div}def
27 /point{resolution 72 div mul}def
28 /dround {transform round exch round exch itransform}def
29 /xT{/devname exch def}def
30 /xr{/mh exch def /my exch def /resolution exch def}def
32 /xs{docsave restore end}def
34 /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
35 {fonts slotno fontname findfont put fontnames slotno fontname put}if}def
36 /xH{/fontheight exch def F}def
37 /xS{/fontslant exch def F}def
38 /s{/fontsize exch def /fontheight fontsize def F}def
39 /f{/fontnum exch def F}def
40 /F{fontheight 0 le{/fontheight fontsize def}if
41 fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
42 fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
43 makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def
44 /X{exch currentpoint exch pop moveto show}def
45 /N{3 1 roll moveto show}def
46 /Y{exch currentpoint pop exch moveto show}def
48 /ditpush{}def/ditpop{}def
49 /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def
50 /AN{4 2 roll moveto 0 exch ashow}def
51 /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def
53 /MX{currentpoint exch pop moveto}def
54 /MY{currentpoint pop exch moveto}def
56 /cb{pop}def % action on unknown char -- nothing for now
58 /p{pop showpage pagesave restore /pagesave save def}def
59 /Dt{/Dlinewidth exch def}def 1 Dt
60 /Ds{/Ddash exch def}def -1 Ds
61 /Di{/Dstipple exch def}def 1 Di
62 /Dsetlinewidth{2 Dlinewidth mul setlinewidth}def
63 /Dsetdash{Ddash 4 eq{[8 12]}{Ddash 16 eq{[32 36]}
64 {Ddash 20 eq{[32 12 8 12]}{[]}ifelse}ifelse}ifelse 0 setdash}def
65 /Dstroke{gsave Dsetlinewidth Dsetdash 1 setlinecap stroke grestore
66 currentpoint newpath moveto}def
67 /Dl{rlineto Dstroke}def
68 /arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop
69 currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
70 currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def
71 /Dc{dup arcellipse Dstroke}def
72 /De{arcellipse Dstroke}def
73 /Da{/endv exch def /endh exch def /centerv exch def /centerh exch def
74 /cradius centerv centerv mul centerh centerh mul add sqrt def
75 /eradius endv endv mul endh endh mul add sqrt def
76 /endang endv endh atan def
77 /startang centerv neg centerh neg atan def
78 /sweep startang endang sub dup 0 lt{360 add}if def
80 {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def
81 /midh midang cos midrad mul def /midv midang sin midrad mul def
82 midh neg midv neg endh endv centerh centerv midh midv Da
85 {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def
86 centerv neg controldelt mul centerh controldelt mul
87 endv neg controldelt mul centerh add endh add
88 endh controldelt mul centerv add endv add
89 centerh endh add centerv endv add rcurveto Dstroke}
90 {centerh endh add centerv endv add rlineto Dstroke}
100 [8<0000800100001008>]
101 [8<81c36666c3810000>]
102 [8<0f0e0c0800000000>]
103 [8<0000000000000010>]
104 [8<0411040040114000>]
105 [8<0204081020408001>]
106 [8<0000001038100000>]
107 [8<6699996666999966>]
108 [8<0000800100001008>]
109 [8<81c36666c3810000>]
110 [8<0f0e0c0800000000>]
111 [8<0042660000246600>]
112 [8<0000990000990000>]
113 [8<0804020180402010>]
114 [8<2418814242811824>]
115 [8<6699996666999966>]
116 [8<8000000008000000>]
117 [8<00001c3e363e1c00>]
118 [8<0000000000000000>]
119 [32<00000040000000c00000004000000040000000e0000000000000000000000000>]
120 [32<00000000000060000000900000002000000040000000f0000000000000000000>]
121 [32<000000000000000000e0000000100000006000000010000000e0000000000000>]
122 [32<00000000000000002000000060000000a0000000f00000002000000000000000>]
123 [32<0000000e0000000000000000000000000000000f000000080000000e00000001>]
124 [32<0000090000000600000000000000000000000000000007000000080000000e00>]
125 [32<00010000000200000004000000040000000000000000000000000000000f0000>]
126 [32<0900000006000000090000000600000000000000000000000000000006000000>]]
128 [8<0000020000000000>]
129 [8<0000020000002000>]
130 [8<0004020000002000>]
131 [8<0004020000402000>]
132 [8<0004060000402000>]
133 [8<0004060000406000>]
134 [8<0006060000406000>]
135 [8<0006060000606000>]
136 [8<00060e0000606000>]
137 [8<00060e000060e000>]
138 [8<00070e000060e000>]
139 [8<00070e000070e000>]
140 [8<00070e020070e000>]
141 [8<00070e020070e020>]
142 [8<04070e020070e020>]
143 [8<04070e024070e020>]
144 [8<04070e064070e020>]
145 [8<04070e064070e060>]
146 [8<06070e064070e060>]
147 [8<06070e066070e060>]
148 [8<06070f066070e060>]
149 [8<06070f066070f060>]
150 [8<060f0f066070f060>]
151 [8<060f0f0660f0f060>]
152 [8<060f0f0760f0f060>]
153 [8<060f0f0760f0f070>]
154 [8<0e0f0f0760f0f070>]
155 [8<0e0f0f07e0f0f070>]
156 [8<0e0f0f0fe0f0f070>]
157 [8<0e0f0f0fe0f0f0f0>]
158 [8<0f0f0f0fe0f0f0f0>]
159 [8<0f0f0f0ff0f0f0f0>]
160 [8<1f0f0f0ff0f0f0f0>]
161 [8<1f0f0f0ff1f0f0f0>]
162 [8<1f0f0f8ff1f0f0f0>]
163 [8<1f0f0f8ff1f0f0f8>]
164 [8<9f0f0f8ff1f0f0f8>]
165 [8<9f0f0f8ff9f0f0f8>]
166 [8<9f0f0f9ff9f0f0f8>]
167 [8<9f0f0f9ff9f0f0f9>]
168 [8<9f8f0f9ff9f0f0f9>]
169 [8<9f8f0f9ff9f8f0f9>]
170 [8<9f8f1f9ff9f8f0f9>]
171 [8<9f8f1f9ff9f8f1f9>]
172 [8<bf8f1f9ff9f8f1f9>]
173 [8<bf8f1f9ffbf8f1f9>]
174 [8<bf8f1fdffbf8f1f9>]
175 [8<bf8f1fdffbf8f1fd>]
176 [8<ff8f1fdffbf8f1fd>]
177 [8<ff8f1fdffff8f1fd>]
178 [8<ff8f1ffffff8f1fd>]
179 [8<ff8f1ffffff8f1ff>]
180 [8<ff9f1ffffff8f1ff>]
181 [8<ff9f1ffffff9f1ff>]
182 [8<ff9f9ffffff9f1ff>]
183 [8<ff9f9ffffff9f9ff>]
184 [8<ffbf9ffffff9f9ff>]
185 [8<ffbf9ffffffbf9ff>]
186 [8<ffbfdffffffbf9ff>]
187 [8<ffbfdffffffbfdff>]
188 [8<ffffdffffffbfdff>]
189 [8<ffffdffffffffdff>]
190 [8<fffffffffffffdff>]
191 [8<ffffffffffffffff>]]
193 [8<8000000000000000>]
194 [8<0822080080228000>]
195 [8<0204081020408001>]
196 [8<40e0400000000000>]
198 [8<8001000010080000>]
199 [8<81c36666c3810000>]
200 [8<f0e0c08000000000>]
201 [16<07c00f801f003e007c00f800f001e003c007800f001f003e007c00f801f003e0>]
202 [16<1f000f8007c003e001f000f8007c003e001f800fc007e003f001f8007c003e00>]
203 [8<c3c300000000c3c3>]
204 [16<0040008001000200040008001000200040008000000100020004000800100020>]
205 [16<0040002000100008000400020001800040002000100008000400020001000080>]
206 [16<1fc03fe07df0f8f8f07de03fc01f800fc01fe03ff07df8f87df03fe01fc00f80>]
208 [8<8040201000000000>]
209 [8<84cc000048cc0000>]
210 [8<9900009900000000>]
211 [8<08040201804020100800020180002010>]
212 [8<2418814242811824>]
214 [8<8000000008000000>]
215 [8<70f8d8f870000000>]
216 [8<0814224180402010>]
217 [8<aa00440a11a04400>]
218 [8<018245aa45820100>]
219 [8<221c224180808041>]
221 [8<0855800080550800>]
222 [8<2844004482440044>]
223 [8<0810204080412214>]
226 transform /maxy exch def /maxx exch def
227 transform /miny exch def /minx exch def
228 minx maxx gt{/minx maxx /maxx minx def def}if
229 miny maxy gt{/miny maxy /maxy miny def def}if
230 Dpatterns Dstipple 1 sub get exch 1 sub get
231 aload pop /stip exch def /stipw exch def /stiph 128 def
232 /imatrix[stipw 0 0 stiph 0 0]def
233 /tmatrix[stipw 0 0 stiph 0 0]def
234 /minx minx cvi stiph idiv stiph mul def
235 /miny miny cvi stipw idiv stipw mul def
236 gsave eoclip 0 setgray
238 tmatrix exch 5 exch put
240 tmatrix exch 4 exch put tmatrix setmatrix
241 stipw stiph true imatrix {stip} imagemask
246 /Dp{Dfill Dstroke}def
247 /DP{Dfill currentpoint newpath moveto}def
250 /ditstart{$DITroff begin
251 /nfonts 60 def % NFONTS makedev/ditroff dependent!
252 /fonts[nfonts{0}repeat]def
253 /fontnames[nfonts{()}repeat]def
259 /pswid exch def /cc exch def /name exch def
260 /ditwid pswid fontsize mul resolution mul 72000 div def
261 /ditsiz fontsize resolution mul 72 div def
262 ocprocs name known{ocprocs name get exec}{name cb}ifelse
264 /fractm [.65 0 0 .6 0 0] def
266 /fden exch def /fnum exch def gsave /cf currentfont def
267 cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
268 fnum show rmoveto currentfont cf setfont(\244)show setfont fden show
269 grestore ditwid 0 rmoveto
271 /oce{grestore ditwid 0 rmoveto}def
273 /ocprocs 50 dict def ocprocs begin
274 (14){(1)(4)fraction}def
275 (12){(1)(2)fraction}def
276 (34){(3)(4)fraction}def
277 (13){(1)(3)fraction}def
278 (23){(2)(3)fraction}def
279 (18){(1)(8)fraction}def
280 (38){(3)(8)fraction}def
281 (58){(5)(8)fraction}def
282 (78){(7)(8)fraction}def
283 (sr){gsave 0 .06 dm rmoveto(\326)show oce}def
284 (is){gsave 0 .15 dm rmoveto(\362)show oce}def
285 (->){gsave 0 .02 dm rmoveto(\256)show oce}def
286 (<-){gsave 0 .02 dm rmoveto(\254)show oce}def
287 (==){gsave 0 .05 dm rmoveto(\272)show oce}def
288 (uc){gsave currentpoint 400 .009 dm mul add translate
289 8 -8 scale ucseal oce}def
292 % an attempt at a PostScript FONT to implement ditroff special chars
293 % this will enable us to
294 % cache the little buggers
295 % generate faster, more compact PS out of psdit
296 % confuse everyone (including myself)!
299 /FontName /DIThacks def
300 /FontMatrix [.001 0 0 .001 0 0] def
301 /FontBBox [-260 -260 900 900] def% a lie but ...
302 /Encoding 256 array def
303 0 1 255{Encoding exch /.notdef put}for
305 dup 8#040/space put %space
306 dup 8#110/rc put %right ceil
307 dup 8#111/lt put %left top curl
308 dup 8#112/bv put %bold vert
309 dup 8#113/lk put %left mid curl
310 dup 8#114/lb put %left bot curl
311 dup 8#115/rt put %right top curl
312 dup 8#116/rk put %right mid curl
313 dup 8#117/rb put %right bot curl
314 dup 8#120/rf put %right floor
315 dup 8#121/lf put %left floor
316 dup 8#122/lc put %left ceil
317 dup 8#140/sq put %square
318 dup 8#141/bx put %box
319 dup 8#142/ci put %circle
320 dup 8#143/br put %box rule
321 dup 8#144/rn put %root extender
322 dup 8#145/vr put %vertical rule
323 dup 8#146/ob put %outline bullet
324 dup 8#147/bu put %bullet
325 dup 8#150/ru put %rule
326 dup 8#151/ul put %underline
330 /cc exch def /fd exch def
331 /charname fd /Encoding get cc get def
332 /charwid fd /Metrics get charname get def
333 /charproc fd /CharProcs get charname get def
334 charwid 0 fd /FontBBox get aload pop setcachedevice
335 2 setlinejoin 40 setlinewidth
336 newpath 0 0 moveto gsave charproc grestore
338 /BuildChar load 0 DITfd put
339 /CharProcs 50 dict def
344 /rn{0 840 moveto 500 0 rls}def
345 /vr{0 800 moveto 0 -770 rls}def
346 /bv{0 800 moveto 0 -1000 rls}def
347 /br{0 840 moveto 0 -1000 rls}def
348 /ul{0 -140 moveto 500 0 rls}def
349 /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
350 /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
351 /sq{80 0 rmoveto currentpoint dround newpath moveto
352 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
353 /bx{80 0 rmoveto currentpoint dround newpath moveto
354 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
355 /ci{500 360 rmoveto currentpoint newpath 333 0 360 arc
356 50 setlinewidth stroke}def
358 /lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
359 /lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
360 /rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
361 /rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
362 /lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub
363 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
364 /rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub
365 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
366 /lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def
367 /rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
368 /lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def
369 /rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
372 /Metrics 50 dict def Metrics begin
399 /s2 500 def /s4 250 def /s3 333 def
400 /a4p{arcto pop pop pop pop}def
402 /rls{rlineto stroke}def
403 /currx{currentpoint pop}def
404 /dround{transform round exch round exch itransform} def
407 /DIThacks exch definefont pop
412 2(Times-Italic)xf 2 f
414 4(Times-BoldItalic)xf 4 f
416 6(Helvetica-Bold)xf 6 f
418 8(Courier-Bold)xf 8 f
481 1152 1310(subsequently)N
525 1152 1574(shortcomings.)N
533 2717(characteristics)X
539 1152 1776(providing)N
590 1380 2128(Introduction)N
710 720 3518(improvements)N
780 720 4248(shortcomings.)N
911 2706 2304(functionality)N
934 3185(implementation)X
949 2706 2656(mentations.)N
957 2706 2744(representation,)N
992 2706 3184(buddy-in-waiting.)N
1033 2706 3822([THOM90],)N
1055 3142(public-domain)X
1068 3797 0.1645(interface-compatible)AX
1092 3323(implementations)X
1162 3085(memory-resident)X
1205 2706 5546(Larson's)N
1257 1526(implementations)X
1296 1011(concurrently.)X
1301 432 1198(algorithm)N
1325 1836(\256xed-sized)X
1368 1672(bit-randomizing)X
1397 432 2130(necessary)N
1424 432 2394(indicates)N
1454 432 2658(described)N
1469 604 2860(Initially,)N
1488 432 3036(corresponding)N
1549 432 3476(previously)N
1563 1359(well-designed)X
1836 670(bit-randomizing)X
1974 2418 1356(checked.)N
1997 3133(simpli\256cation)X
2028 2684 -0.4038(calchash\(key\);)AX
2033 2646 -0.4018(\(isbitset\(\(hash)AX
2061 3302(public-domain)X
2079 2692(functionality)X
2105 2418 3384(identical)N
2118 2418 3472(function,)N
2137 2418 3648(incompatible)N
2153 2418 3850(mentation)N
2166 3066(re\256nements)X
2216 3675(pseudo-random)X
2228 2418 4554(traverse)N
2236 2418 4642(exhausted)N
2240 3286(\(non-split\))X
2255 2590 4932(Larson's)N
2256 2903(re\256nements)X
2312 2418 5460(Instead,)N
2414 720 890 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
2531 720 2922 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
2534 1153(simpli\256cations)X
2540 720 3212(possible.)N
2554 1696(pseudo-random)X
2556 720 3388(generator)N
2561 1785(bit-randomizing)X
2563 720 3476(function,)N
2617 1218 3916(starting)N
2650 986 -0.4038(calchash\(key\);)AX
2655 910 4743 -0.4018(isbitset\(tbit\);)AN
2668 1654 -0.4219(hbit++\)\)\))AX
2698 2068(representation)X
2774 2706 1563(tribution.)N
2782 2706 1651(tionality)N
2795 2706 1739(attempts)N
2801 3846(shortcomings.)X
2807 3525(arbitrary-length)X
2811 2706 1915(database)N
2864 2706 2469(algorithms)N
2877 2706 2557(representation)N
2891 2706 2733 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
3059 2706 4209 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
3121 2706 4851(directory)N
3158 2706 5203(relationship)N
3168 3271(representation.)X
3173 2706 5379(directory)N
3224 604 538(Initially,)N
3232 432 626(addressing)N
3304 432 1242(directory.)N
3311 432 1330(directory)N
3401 432 2148(directory)N
3507 432 3142(directory)N
3573 698 -0.4038(calchash\(key\);)AX
3576 698 -0.4018(maskvec[depth];)AX
3579 774 -0.4038(directory[hash)AX
3584 698 -0.4219(Insertion)AX
3587 546 -0.4038(\(store\(bucket,)AX
3595 1024 -0.4167(getpage\(\);)AX
3596 720 4585 -0.4000(bucket->depth++;)AN
3597 720 4673 -0.4091(newbl->depth)AN
3599 1290 -0.4038(bucket->depth;)AX
3601 834 -0.4038(\(bucket->depth)AX
3607 1388 -0.4219(directory)AX
3609 1008 4937(depth++;)N
3682 432 5513(allocated)N
3711 2994 538 -0.4219(directory)AN
3713 3450 -0.3971(double\(directory\);)AX
3715 2706 714 -0.3958(splitbucket\(bucket,)AN
3742 2418 1563(algorithms)N
3757 3862(\(speci\256ed)X
3798 2593(multiplicative)X
3815 2418 2267(original)N
3891 2418 3085(``USCR'')N
3934 3597(multiplication)X
3938 2787(calculation\).)X
3953 2418 3701(selected)N
3977 2418 3991(discovered)N
4006 2418 4255(lengthening)N
4030 2418 4519(appeared)N
4058 2418 4783(de\256ning)N
4073 2418 4985(``CHAINED'',)N
4133 2418 5601(speci\256ed)N
4182 720 758(implements)N
4195 720 934(Intuitively,)N
4229 720 1198(generation)N
4472 1773(bit-randomizing)X
4494 720 3626(resulting)N
4548 872 -0.4038(calchash\(key\);)AX
4553 1214 -0.4167(high_mask;)AX
4558 1252 -0.4167(max_bucket)AX
4564 1502 -0.4219(low_mask;)AX
4565 720 4717 -0.4018(return\(bucket\);)AN
4712 3473(Implementation)X
4715 3042(implementation)X
4730 2706 1528(dynahash)N
4732 3047(implementation.)X
4754 3568(over\257ows\))X
4768 2706 1880(prede\256ned)N
4776 2706 1968(exceeded\).)N
4815 2706 2320(exceeding)N
4829 3395(parameterized)X
4850 2706 2610(dynahash's)N
4946 2878 3428(Inserting)N
4953 2706 3516(precisely)N
4994 3318 3934(Over\257ow)N
5039 2706 4418(over\257ow,)N
5048 2706 4506(scheduled)N
5054 3790(implementations,)X
5076 2706 4770(Although)N
5084 2706 4858(expensive,)N
5093 2706 4946(mentation,)N
5216 943(representation,)X
5229 432 802(over\257ow)N
5269 1747(indeterminate)X
5304 432 1708(descriptor,)N
5314 432 1796(logically)N
5330 432 1972(over\257ow)N
5338 799(buddy-in-waiting)X
5342 432 2174(mechanism)N
5369 432 2526(over\257ow)N
5387 432 2702(reclaimed,)N
5404 432 2878(over\257ow)N
5420 432 3054(themselves)N
5455 432 3406(addresses)N
5482 736 -0.4125(nhdr_pages;)AX
5486 1686 -112.4062(\256le)AX
5490 736 -0.4125(spares[32];)AX
5505 736 -0.3929(BUCKET_TO_PAGE\(bucket\))AX
5509 926 -0.4167(nhdr_pages)AX
5512 584 4497 -0.3894(\(bucket?spares[logs2\(bucket)AN
5516 736 -0.3947(OADDR_TO_PAGE\(oaddr\))AX
5518 584 4761 -0.3984(BUCKET_TO_PAGE\(\(1)AN
5520 1382 -0.4091(\(oaddr>>11\)\))AX
5539 432 5350(identifying)N
5545 432 5438(over\257ow)N
5564 432 5614(implementation,)N
5572 432 5702(\(limiting)N
5590 2418 626(expressed)N
5653 3113 1066(over\257ow)N
5683 2418 1418 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
5747 3017 2601(Over\257ow)N
5749 3515 2833(Over\257ow)N
5759 closepath 3 3349 2740 3482 2873 Dp
5816 3070 2152(Over\257ow)N
5824 closepath 3 3482 2275 3615 2408 Dp
5831 closepath 3 3349 2275 3482 2408 Dp
5838 closepath 3 3216 2275 3349 2408 Dp
5845 closepath 3 2817 2275 2950 2408 Dp
5852 closepath 3 2684 2275 2817 2408 Dp
5936 2418 3489 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
5959 2418 4039(arranged)N
6001 2754 0.4028(referenced)AX
6007 2418 4567(address.)N
6035 2418 4831(requirements,)N
6101 2418 5561(predecessor)N
6109 2418 5649(over\257ow)N
6166 720 714(functionality,)N
6283 720 1972(over\257ow)N
6323 720 2412 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
6394 closepath 19 1402 3851 1471 3920 Dp
6395 1445 3747(Over\257ow)N
6462 closepath 19 2171 3471 2448 3609 Dp
6469 closepath 3 1756 3609 2033 3747 Dp
6476 closepath 19 1480 3471 1756 3609 Dp
6483 closepath 19 789 3471 1065 3609 Dp
6492 closepath 14 849 3851 918 3920 Dp
6499 closepath 14 1756 3194 1895 3471 Dp
6506 closepath 14 2171 3056 2309 3333 Dp
6513 closepath 14 1480 3056 1618 3333 Dp
6520 closepath 14 789 3056 927 3333 Dp
6600 closepath 3 1990 3851 2059 3920 Dp
6601 2102 3903(Over\257ow)N
6649 720 4624 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
6652 1406(Parameterization)X
6680 2079(user-de\256ned)X
6724 2706 538(bene\256t)N
6754 3499(approximation)X
6767 2706 1004(determining)N
6786 2706 1180(key/data)N
6811 2994 -0.3938(\(\(average_pair_length)AX
6815 3032 1743(ffactor\))N
6824 3551(applications,)X
6825 3999(experimenting)X
6834 2706 2218(encouraged.)N
6905 2706 2948(advance\),)N
6965 2706 3476(9000/370)N
6994 2706 3942(\(Figure)N
7004 2706 4030(performance)N
7034 2706 4294(formance)N
7113 2706 5112(clusions)N
7151 2706 5464(slightly)N
7207 432 538(performing)N
7232 1563(approximately)X
7235 432 802 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
7631 432 3234 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8039 2785(approximation)X
8045 2418 626(ultimately)N
8114 2418 1242(formance)N
8167 3378(suf\256ciently)X
8185 2418 1946 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8584 2418 4638 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8604 2418 5016(built-in)N
8646 2418 5368(speci\256ed)N
8665 2418 5544(speci\256ed,)N
8770 1324(collisions\).)X
8775 720 1066(applications,)N
8793 720 1330 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8828 closepath 21 1895 2778 1950 2833 Dp
8835 closepath 14 1342 2778 1397 2833 Dp
8842 closepath 3 900 2778 955 2833 Dp
8860 closepath 14 2283 2211 2379 2252 Dp
8867 closepath 14 1992 2211 2089 2252 Dp
8874 closepath 14 1702 2211 1799 2252 Dp
8881 closepath 14 1411 2252 1508 2294 Dp
8888 closepath 3 2283 2252 2379 2612 Dp
8895 closepath 3 1992 2252 2089 2612 Dp
8902 closepath 3 1702 2252 1799 2612 Dp
8909 closepath 3 1411 2294 1508 2612 Dp
8917 closepath 21 2158 2238 2255 2252 Dp
8924 closepath 21 1868 2238 1965 2280 Dp
8931 closepath 21 1577 2238 1674 2308 Dp
8938 closepath 21 1287 2280 1384 2308 Dp
8945 closepath 14 2158 2252 2255 2280 Dp
8952 closepath 14 1868 2280 1965 2308 Dp
8959 closepath 14 1577 2308 1674 2335 Dp
8966 closepath 14 1287 2308 1384 2363 Dp
8973 closepath 3 2158 2280 2255 2612 Dp
8980 closepath 3 1868 2308 1965 2612 Dp
8987 closepath 3 1577 2335 1674 2612 Dp
8994 closepath 3 1287 2363 1384 2612 Dp
9002 closepath 21 1121 2066 1224 2080 Dp
9009 closepath 14 1121 2080 1218 2273 Dp
9016 closepath 3 1121 2273 1218 2612 Dp
9024 closepath 21 997 1589 1093 1644 Dp
9031 closepath 14 997 1644 1093 2280 Dp
9038 closepath 3 997 2280 1093 2612 Dp
9056 1701 2925(Dynamically)N
9124 720 3708 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
9132 720 3998(management,)N
9261 1782(inef\256cient)X
9584 2706 2949(inversely)N
9613 2706 3301 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
9615 3175 3543(Enhanced)N
9616 3536(Functionality)X
9645 2706 3939(additional)N
9646 3046(functionality)X
9686 3703(user-speci\256ed.)X
9704 3626(compatibility)X
9707 2706 4819(implement)N
9716 2706 4907(interface)N
9719 3540(functionality:)X
9741 2946 5215(currently.)N
9761 3799(user-speci\256ed)X
9763 2946 5567(runtime.)N
9797 1613(Implementation)X
9837 432 1022(4.3BSD-Reno)N
9914 432 1638(performance)N
9938 432 1928(previously.)N
10005 783(con\256guration)X
10030 591(approximately)X
10037 432 2896(con\256dence)N
10040 1183(approximately)X
10127 432 4420(sequential)N
10148 547 4710(retrieval)N
10165 547 4886(Therefore,)N
10208 547 5238(\(requiring)N
10234 3014 538(In-Memory)N
10253 2418 872(create/read)N
10286 2533 1250(troyed.)N
10288 2938 1404(Performance)N
10291 2590 1536(Figures)N
10311 2418 1712(implementation)N
10315 3360(implementation)X
10327 3243(appropriate\))X
10332 2418 1888(improvement.)N
10339 2418 1976(percentage)N
10351 2798 -0.4219(\(old_time)AX
10353 3254 -0.4219(new_time\))AX
10380 2418 2776(Although)N
10390 2418 2864(performance,)N
10400 2418 2952(writing)N
10411 2564(dictionary\),)X
10460 2418 3506(deceptive)N
10546 2418 4210(package)N
10560 2418 4412(memory-resident)N
10605 2418 4852(hsearch)N
10651 10 s 10 xH 0 xS 0 f
10665 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10673 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10678 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10714 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10716 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10721 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10732 1006 1282(elapsed)N
10757 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10759 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10764 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10775 1006 1650(elapsed)N
10800 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10802 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10804 948 1746(SEQUENTIAL)N
10807 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10818 1006 2018(elapsed)N
10843 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10845 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10847 948 2114(SEQUENTIAL)N
10853 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10864 1006 2386(elapsed)N
10871 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10935 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10943 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10945 945 2762(CREATE/READ)N
10948 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10966 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11002 720 3262 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
11004 1407 3504(Conclusion)N
11031 720 3900(functionality)N
11094 720 4604(routines,)N
11127 720 5070(Berkeley.)N
11162 720 5422(key/data)N
11170 720 5510(application)N
11200 4075(applications)X
11220 2804(transactions,)X
11224 3723(incorporated)X
11229 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11237 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11242 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11253 2992 1398(elapsed)N
11278 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11280 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11285 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11296 2992 1766(elapsed)N
11321 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11323 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11328 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11339 2992 2134(elapsed)N
11364 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11366 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11368 2934 2230(SEQUENTIAL)N
11371 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11382 2992 2502(elapsed)N
11407 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11409 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11411 2934 2598(SEQUENTIAL)N
11417 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11428 2992 2870(elapsed)N
11435 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11499 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11507 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11509 2931 3246(CREATE/READ)N
11512 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11523 2931 3518(elapsed)N
11530 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11566 2706 3746 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
11568 3396 3988(References)N
11570 2706 4120([ATT79])N
11575 3990(Programmer's)X
11576 2878 4208(Manual,)N
11585 2706 4472([ATT85])N
11587 3296(HSEARCH\(BA_LIB\),)X
11600 2706 4736([BRE73])N
11611 3678(Techniques'',)X
11614 2878 4912(ications)N
11625 2878 5000(105-109,)N
11628 2706 5176([BSD86])N
11633 3990(Programmer's)X
11645 2706 5528([ENB88])N
11687 10 s 10 xH 0 xS 0 f
11705 604 626(Pippenger,)N
11709 1787(``Extendible)X
11721 1046(Transactions)X
11735 432 1066([KNU68],)N
11744 604 1154(gramming)N
11778 604 1770(Communications)N
11804 1424(Addressing'',)X
11811 1095(International)X
11836 432 2738([THOM90])N
11840 1670(communication,)X
11850 604 3090(archives'',)N
11874 1328(comp.unix.questions)X
11882 1135(``Discussion)X
11887 604 3794(system'',)N
11891 1762(unix.wizards)X
11894 604 3882(January,)N
11905 604 4146(Dbm/Ndbm'',)N
11931 10 s 10 xH 0 xS 0 f
11967 720 802(interests)N
11994 720 1154(software)N
11997 1509(microprocessors.)X
12000 720 1242(received)N
12007 720 1330 0.1953(Harvard/Radcliffe)AN
12029 720 1620(studying)N
12044 720 1796(Bruisers.)N
12059 886(Communications)X
12083 1583(administrator)X
12094 720 2438(Berkeley)N
12122 1400(interesting,)X
12126 720 2816(language)N
12127 1044(interpreters,)X
12128 1464(preprocessors,)X
12141 1515(public-domain)X
12144 720 3106(including)N
12154 720 3194(apparently)N
12163 720 3282(obsessions)N
12168 720 3370(language)N
12191 10 s 10 xH 0 xS 0 f