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: $Header: /pub/NetBSD/misc/repositories/cvsroot/src/lib/libc/db/hash/Attic/hash.ps,v 1.1 1993/03/21 09:50:53 cgd Exp $
12 % Changed by Edward Wang (edward@ucbarpa.berkeley.edu) to handle graphics,
15 /$DITroff 140 dict def $DITroff begin
16 /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
17 /xi{0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
18 /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
19 /pagesave save def}def
20 /PB{save /psv exch def currentpoint translate
21 resolution 72 div dup neg scale 0 0 moveto}def
23 /arctoobig 90 def /arctoosmall .05 def
24 /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
25 /tan{dup sin exch cos div}def
26 /point{resolution 72 div mul}def
27 /dround {transform round exch round exch itransform}def
28 /xT{/devname exch def}def
29 /xr{/mh exch def /my exch def /resolution exch def}def
31 /xs{docsave restore end}def
33 /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
34 {fonts slotno fontname findfont put fontnames slotno fontname put}if}def
35 /xH{/fontheight exch def F}def
36 /xS{/fontslant exch def F}def
37 /s{/fontsize exch def /fontheight fontsize def F}def
38 /f{/fontnum exch def F}def
39 /F{fontheight 0 le{/fontheight fontsize def}if
40 fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
41 fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
42 makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def
43 /X{exch currentpoint exch pop moveto show}def
44 /N{3 1 roll moveto show}def
45 /Y{exch currentpoint pop exch moveto show}def
47 /ditpush{}def/ditpop{}def
48 /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def
49 /AN{4 2 roll moveto 0 exch ashow}def
50 /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def
52 /MX{currentpoint exch pop moveto}def
53 /MY{currentpoint pop exch moveto}def
55 /cb{pop}def % action on unknown char -- nothing for now
57 /p{pop showpage pagesave restore /pagesave save def}def
58 /Dt{/Dlinewidth exch def}def 1 Dt
59 /Ds{/Ddash exch def}def -1 Ds
60 /Di{/Dstipple exch def}def 1 Di
61 /Dsetlinewidth{2 Dlinewidth mul setlinewidth}def
62 /Dsetdash{Ddash 4 eq{[8 12]}{Ddash 16 eq{[32 36]}
63 {Ddash 20 eq{[32 12 8 12]}{[]}ifelse}ifelse}ifelse 0 setdash}def
64 /Dstroke{gsave Dsetlinewidth Dsetdash 1 setlinecap stroke grestore
65 currentpoint newpath moveto}def
66 /Dl{rlineto Dstroke}def
67 /arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop
68 currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
69 currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def
70 /Dc{dup arcellipse Dstroke}def
71 /De{arcellipse Dstroke}def
72 /Da{/endv exch def /endh exch def /centerv exch def /centerh exch def
73 /cradius centerv centerv mul centerh centerh mul add sqrt def
74 /eradius endv endv mul endh endh mul add sqrt def
75 /endang endv endh atan def
76 /startang centerv neg centerh neg atan def
77 /sweep startang endang sub dup 0 lt{360 add}if def
79 {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def
80 /midh midang cos midrad mul def /midv midang sin midrad mul def
81 midh neg midv neg endh endv centerh centerv midh midv Da
84 {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def
85 centerv neg controldelt mul centerh controldelt mul
86 endv neg controldelt mul centerh add endh add
87 endh controldelt mul centerv add endv add
88 centerh endh add centerv endv add rcurveto Dstroke}
89 {centerh endh add centerv endv add rlineto Dstroke}
100 [8<81c36666c3810000>]
101 [8<0f0e0c0800000000>]
102 [8<0000000000000010>]
103 [8<0411040040114000>]
104 [8<0204081020408001>]
105 [8<0000001038100000>]
106 [8<6699996666999966>]
107 [8<0000800100001008>]
108 [8<81c36666c3810000>]
109 [8<0f0e0c0800000000>]
110 [8<0042660000246600>]
111 [8<0000990000990000>]
112 [8<0804020180402010>]
113 [8<2418814242811824>]
114 [8<6699996666999966>]
115 [8<8000000008000000>]
116 [8<00001c3e363e1c00>]
117 [8<0000000000000000>]
118 [32<00000040000000c00000004000000040000000e0000000000000000000000000>]
119 [32<00000000000060000000900000002000000040000000f0000000000000000000>]
120 [32<000000000000000000e0000000100000006000000010000000e0000000000000>]
121 [32<00000000000000002000000060000000a0000000f00000002000000000000000>]
122 [32<0000000e0000000000000000000000000000000f000000080000000e00000001>]
123 [32<0000090000000600000000000000000000000000000007000000080000000e00>]
124 [32<00010000000200000004000000040000000000000000000000000000000f0000>]
125 [32<0900000006000000090000000600000000000000000000000000000006000000>]]
127 [8<0000020000000000>]
128 [8<0000020000002000>]
129 [8<0004020000002000>]
130 [8<0004020000402000>]
131 [8<0004060000402000>]
132 [8<0004060000406000>]
133 [8<0006060000406000>]
134 [8<0006060000606000>]
135 [8<00060e0000606000>]
136 [8<00060e000060e000>]
137 [8<00070e000060e000>]
138 [8<00070e000070e000>]
139 [8<00070e020070e000>]
140 [8<00070e020070e020>]
141 [8<04070e020070e020>]
142 [8<04070e024070e020>]
143 [8<04070e064070e020>]
144 [8<04070e064070e060>]
145 [8<06070e064070e060>]
146 [8<06070e066070e060>]
147 [8<06070f066070e060>]
148 [8<06070f066070f060>]
149 [8<060f0f066070f060>]
150 [8<060f0f0660f0f060>]
151 [8<060f0f0760f0f060>]
152 [8<060f0f0760f0f070>]
153 [8<0e0f0f0760f0f070>]
154 [8<0e0f0f07e0f0f070>]
155 [8<0e0f0f0fe0f0f070>]
156 [8<0e0f0f0fe0f0f0f0>]
157 [8<0f0f0f0fe0f0f0f0>]
158 [8<0f0f0f0ff0f0f0f0>]
159 [8<1f0f0f0ff0f0f0f0>]
160 [8<1f0f0f0ff1f0f0f0>]
161 [8<1f0f0f8ff1f0f0f0>]
162 [8<1f0f0f8ff1f0f0f8>]
163 [8<9f0f0f8ff1f0f0f8>]
164 [8<9f0f0f8ff9f0f0f8>]
165 [8<9f0f0f9ff9f0f0f8>]
166 [8<9f0f0f9ff9f0f0f9>]
167 [8<9f8f0f9ff9f0f0f9>]
168 [8<9f8f0f9ff9f8f0f9>]
169 [8<9f8f1f9ff9f8f0f9>]
170 [8<9f8f1f9ff9f8f1f9>]
171 [8<bf8f1f9ff9f8f1f9>]
172 [8<bf8f1f9ffbf8f1f9>]
173 [8<bf8f1fdffbf8f1f9>]
174 [8<bf8f1fdffbf8f1fd>]
175 [8<ff8f1fdffbf8f1fd>]
176 [8<ff8f1fdffff8f1fd>]
177 [8<ff8f1ffffff8f1fd>]
178 [8<ff8f1ffffff8f1ff>]
179 [8<ff9f1ffffff8f1ff>]
180 [8<ff9f1ffffff9f1ff>]
181 [8<ff9f9ffffff9f1ff>]
182 [8<ff9f9ffffff9f9ff>]
183 [8<ffbf9ffffff9f9ff>]
184 [8<ffbf9ffffffbf9ff>]
185 [8<ffbfdffffffbf9ff>]
186 [8<ffbfdffffffbfdff>]
187 [8<ffffdffffffbfdff>]
188 [8<ffffdffffffffdff>]
189 [8<fffffffffffffdff>]
190 [8<ffffffffffffffff>]]
192 [8<8000000000000000>]
193 [8<0822080080228000>]
194 [8<0204081020408001>]
195 [8<40e0400000000000>]
197 [8<8001000010080000>]
198 [8<81c36666c3810000>]
199 [8<f0e0c08000000000>]
200 [16<07c00f801f003e007c00f800f001e003c007800f001f003e007c00f801f003e0>]
201 [16<1f000f8007c003e001f000f8007c003e001f800fc007e003f001f8007c003e00>]
202 [8<c3c300000000c3c3>]
203 [16<0040008001000200040008001000200040008000000100020004000800100020>]
204 [16<0040002000100008000400020001800040002000100008000400020001000080>]
205 [16<1fc03fe07df0f8f8f07de03fc01f800fc01fe03ff07df8f87df03fe01fc00f80>]
207 [8<8040201000000000>]
208 [8<84cc000048cc0000>]
209 [8<9900009900000000>]
210 [8<08040201804020100800020180002010>]
211 [8<2418814242811824>]
213 [8<8000000008000000>]
214 [8<70f8d8f870000000>]
215 [8<0814224180402010>]
216 [8<aa00440a11a04400>]
217 [8<018245aa45820100>]
218 [8<221c224180808041>]
220 [8<0855800080550800>]
221 [8<2844004482440044>]
222 [8<0810204080412214>]
225 transform /maxy exch def /maxx exch def
226 transform /miny exch def /minx exch def
227 minx maxx gt{/minx maxx /maxx minx def def}if
228 miny maxy gt{/miny maxy /maxy miny def def}if
229 Dpatterns Dstipple 1 sub get exch 1 sub get
230 aload pop /stip exch def /stipw exch def /stiph 128 def
231 /imatrix[stipw 0 0 stiph 0 0]def
232 /tmatrix[stipw 0 0 stiph 0 0]def
233 /minx minx cvi stiph idiv stiph mul def
234 /miny miny cvi stipw idiv stipw mul def
235 gsave eoclip 0 setgray
237 tmatrix exch 5 exch put
239 tmatrix exch 4 exch put tmatrix setmatrix
240 stipw stiph true imatrix {stip} imagemask
245 /Dp{Dfill Dstroke}def
246 /DP{Dfill currentpoint newpath moveto}def
249 /ditstart{$DITroff begin
250 /nfonts 60 def % NFONTS makedev/ditroff dependent!
251 /fonts[nfonts{0}repeat]def
252 /fontnames[nfonts{()}repeat]def
258 /pswid exch def /cc exch def /name exch def
259 /ditwid pswid fontsize mul resolution mul 72000 div def
260 /ditsiz fontsize resolution mul 72 div def
261 ocprocs name known{ocprocs name get exec}{name cb}ifelse
263 /fractm [.65 0 0 .6 0 0] def
265 /fden exch def /fnum exch def gsave /cf currentfont def
266 cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
267 fnum show rmoveto currentfont cf setfont(\244)show setfont fden show
268 grestore ditwid 0 rmoveto
270 /oce{grestore ditwid 0 rmoveto}def
272 /ocprocs 50 dict def ocprocs begin
273 (14){(1)(4)fraction}def
274 (12){(1)(2)fraction}def
275 (34){(3)(4)fraction}def
276 (13){(1)(3)fraction}def
277 (23){(2)(3)fraction}def
278 (18){(1)(8)fraction}def
279 (38){(3)(8)fraction}def
280 (58){(5)(8)fraction}def
281 (78){(7)(8)fraction}def
282 (sr){gsave 0 .06 dm rmoveto(\326)show oce}def
283 (is){gsave 0 .15 dm rmoveto(\362)show oce}def
284 (->){gsave 0 .02 dm rmoveto(\256)show oce}def
285 (<-){gsave 0 .02 dm rmoveto(\254)show oce}def
286 (==){gsave 0 .05 dm rmoveto(\272)show oce}def
287 (uc){gsave currentpoint 400 .009 dm mul add translate
288 8 -8 scale ucseal oce}def
291 % an attempt at a PostScript FONT to implement ditroff special chars
292 % this will enable us to
293 % cache the little buggers
294 % generate faster, more compact PS out of psdit
295 % confuse everyone (including myself)!
298 /FontName /DIThacks def
299 /FontMatrix [.001 0 0 .001 0 0] def
300 /FontBBox [-260 -260 900 900] def% a lie but ...
301 /Encoding 256 array def
302 0 1 255{Encoding exch /.notdef put}for
304 dup 8#040/space put %space
305 dup 8#110/rc put %right ceil
306 dup 8#111/lt put %left top curl
307 dup 8#112/bv put %bold vert
308 dup 8#113/lk put %left mid curl
309 dup 8#114/lb put %left bot curl
310 dup 8#115/rt put %right top curl
311 dup 8#116/rk put %right mid curl
312 dup 8#117/rb put %right bot curl
313 dup 8#120/rf put %right floor
314 dup 8#121/lf put %left floor
315 dup 8#122/lc put %left ceil
316 dup 8#140/sq put %square
317 dup 8#141/bx put %box
318 dup 8#142/ci put %circle
319 dup 8#143/br put %box rule
320 dup 8#144/rn put %root extender
321 dup 8#145/vr put %vertical rule
322 dup 8#146/ob put %outline bullet
323 dup 8#147/bu put %bullet
324 dup 8#150/ru put %rule
325 dup 8#151/ul put %underline
329 /cc exch def /fd exch def
330 /charname fd /Encoding get cc get def
331 /charwid fd /Metrics get charname get def
332 /charproc fd /CharProcs get charname get def
333 charwid 0 fd /FontBBox get aload pop setcachedevice
334 2 setlinejoin 40 setlinewidth
335 newpath 0 0 moveto gsave charproc grestore
337 /BuildChar load 0 DITfd put
338 /CharProcs 50 dict def
343 /rn{0 840 moveto 500 0 rls}def
344 /vr{0 800 moveto 0 -770 rls}def
345 /bv{0 800 moveto 0 -1000 rls}def
346 /br{0 840 moveto 0 -1000 rls}def
347 /ul{0 -140 moveto 500 0 rls}def
348 /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
349 /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
350 /sq{80 0 rmoveto currentpoint dround newpath moveto
351 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
352 /bx{80 0 rmoveto currentpoint dround newpath moveto
353 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
354 /ci{500 360 rmoveto currentpoint newpath 333 0 360 arc
355 50 setlinewidth stroke}def
357 /lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
358 /lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
359 /rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
360 /rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
361 /lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub
362 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
363 /rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub
364 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
365 /lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def
366 /rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
367 /lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def
368 /rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
371 /Metrics 50 dict def Metrics begin
398 /s2 500 def /s4 250 def /s3 333 def
399 /a4p{arcto pop pop pop pop}def
401 /rls{rlineto stroke}def
402 /currx{currentpoint pop}def
403 /dround{transform round exch round exch itransform} def
406 /DIThacks exch definefont pop
411 2(Times-Italic)xf 2 f
413 4(Times-BoldItalic)xf 4 f
415 6(Helvetica-Bold)xf 6 f
417 8(Courier-Bold)xf 8 f
480 1152 1310(subsequently)N
524 1152 1574(shortcomings.)N
532 2717(characteristics)X
538 1152 1776(providing)N
589 1380 2128(Introduction)N
709 720 3518(improvements)N
779 720 4248(shortcomings.)N
910 2706 2304(functionality)N
933 3185(implementation)X
948 2706 2656(mentations.)N
956 2706 2744(representation,)N
991 2706 3184(buddy-in-waiting.)N
1032 2706 3822([THOM90],)N
1054 3142(public-domain)X
1067 3797 0.1645(interface-compatible)AX
1091 3323(implementations)X
1161 3085(memory-resident)X
1204 2706 5546(Larson's)N
1256 1526(implementations)X
1295 1011(concurrently.)X
1300 432 1198(algorithm)N
1324 1836(\256xed-sized)X
1367 1672(bit-randomizing)X
1396 432 2130(necessary)N
1423 432 2394(indicates)N
1453 432 2658(described)N
1468 604 2860(Initially,)N
1487 432 3036(corresponding)N
1548 432 3476(previously)N
1562 1359(well-designed)X
1835 670(bit-randomizing)X
1973 2418 1356(checked.)N
1996 3133(simpli\256cation)X
2027 2684 -0.4038(calchash\(key\);)AX
2032 2646 -0.4018(\(isbitset\(\(hash)AX
2060 3302(public-domain)X
2078 2692(functionality)X
2104 2418 3384(identical)N
2117 2418 3472(function,)N
2136 2418 3648(incompatible)N
2152 2418 3850(mentation)N
2165 3066(re\256nements)X
2215 3675(pseudo-random)X
2227 2418 4554(traverse)N
2235 2418 4642(exhausted)N
2239 3286(\(non-split\))X
2254 2590 4932(Larson's)N
2255 2903(re\256nements)X
2311 2418 5460(Instead,)N
2413 720 890 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
2530 720 2922 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
2533 1153(simpli\256cations)X
2539 720 3212(possible.)N
2553 1696(pseudo-random)X
2555 720 3388(generator)N
2560 1785(bit-randomizing)X
2562 720 3476(function,)N
2616 1218 3916(starting)N
2649 986 -0.4038(calchash\(key\);)AX
2654 910 4743 -0.4018(isbitset\(tbit\);)AN
2667 1654 -0.4219(hbit++\)\)\))AX
2697 2068(representation)X
2773 2706 1563(tribution.)N
2781 2706 1651(tionality)N
2794 2706 1739(attempts)N
2800 3846(shortcomings.)X
2806 3525(arbitrary-length)X
2810 2706 1915(database)N
2863 2706 2469(algorithms)N
2876 2706 2557(representation)N
2890 2706 2733 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
3058 2706 4209 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
3120 2706 4851(directory)N
3157 2706 5203(relationship)N
3167 3271(representation.)X
3172 2706 5379(directory)N
3223 604 538(Initially,)N
3231 432 626(addressing)N
3303 432 1242(directory.)N
3310 432 1330(directory)N
3400 432 2148(directory)N
3506 432 3142(directory)N
3572 698 -0.4038(calchash\(key\);)AX
3575 698 -0.4018(maskvec[depth];)AX
3578 774 -0.4038(directory[hash)AX
3583 698 -0.4219(Insertion)AX
3586 546 -0.4038(\(store\(bucket,)AX
3594 1024 -0.4167(getpage\(\);)AX
3595 720 4585 -0.4000(bucket->depth++;)AN
3596 720 4673 -0.4091(newbl->depth)AN
3598 1290 -0.4038(bucket->depth;)AX
3600 834 -0.4038(\(bucket->depth)AX
3606 1388 -0.4219(directory)AX
3608 1008 4937(depth++;)N
3681 432 5513(allocated)N
3710 2994 538 -0.4219(directory)AN
3712 3450 -0.3971(double\(directory\);)AX
3714 2706 714 -0.3958(splitbucket\(bucket,)AN
3741 2418 1563(algorithms)N
3756 3862(\(speci\256ed)X
3797 2593(multiplicative)X
3814 2418 2267(original)N
3890 2418 3085(``USCR'')N
3933 3597(multiplication)X
3937 2787(calculation\).)X
3952 2418 3701(selected)N
3976 2418 3991(discovered)N
4005 2418 4255(lengthening)N
4029 2418 4519(appeared)N
4057 2418 4783(de\256ning)N
4072 2418 4985(``CHAINED'',)N
4132 2418 5601(speci\256ed)N
4181 720 758(implements)N
4194 720 934(Intuitively,)N
4228 720 1198(generation)N
4471 1773(bit-randomizing)X
4493 720 3626(resulting)N
4547 872 -0.4038(calchash\(key\);)AX
4552 1214 -0.4167(high_mask;)AX
4557 1252 -0.4167(max_bucket)AX
4563 1502 -0.4219(low_mask;)AX
4564 720 4717 -0.4018(return\(bucket\);)AN
4711 3473(Implementation)X
4714 3042(implementation)X
4729 2706 1528(dynahash)N
4731 3047(implementation.)X
4753 3568(over\257ows\))X
4767 2706 1880(prede\256ned)N
4775 2706 1968(exceeded\).)N
4814 2706 2320(exceeding)N
4828 3395(parameterized)X
4849 2706 2610(dynahash's)N
4945 2878 3428(Inserting)N
4952 2706 3516(precisely)N
4993 3318 3934(Over\257ow)N
5038 2706 4418(over\257ow,)N
5047 2706 4506(scheduled)N
5053 3790(implementations,)X
5075 2706 4770(Although)N
5083 2706 4858(expensive,)N
5092 2706 4946(mentation,)N
5215 943(representation,)X
5228 432 802(over\257ow)N
5268 1747(indeterminate)X
5303 432 1708(descriptor,)N
5313 432 1796(logically)N
5329 432 1972(over\257ow)N
5337 799(buddy-in-waiting)X
5341 432 2174(mechanism)N
5368 432 2526(over\257ow)N
5386 432 2702(reclaimed,)N
5403 432 2878(over\257ow)N
5419 432 3054(themselves)N
5454 432 3406(addresses)N
5481 736 -0.4125(nhdr_pages;)AX
5485 1686 -112.4062(\256le)AX
5489 736 -0.4125(spares[32];)AX
5504 736 -0.3929(BUCKET_TO_PAGE\(bucket\))AX
5508 926 -0.4167(nhdr_pages)AX
5511 584 4497 -0.3894(\(bucket?spares[logs2\(bucket)AN
5515 736 -0.3947(OADDR_TO_PAGE\(oaddr\))AX
5517 584 4761 -0.3984(BUCKET_TO_PAGE\(\(1)AN
5519 1382 -0.4091(\(oaddr>>11\)\))AX
5538 432 5350(identifying)N
5544 432 5438(over\257ow)N
5563 432 5614(implementation,)N
5571 432 5702(\(limiting)N
5589 2418 626(expressed)N
5652 3113 1066(over\257ow)N
5682 2418 1418 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
5746 3017 2601(Over\257ow)N
5748 3515 2833(Over\257ow)N
5758 closepath 3 3349 2740 3482 2873 Dp
5815 3070 2152(Over\257ow)N
5823 closepath 3 3482 2275 3615 2408 Dp
5830 closepath 3 3349 2275 3482 2408 Dp
5837 closepath 3 3216 2275 3349 2408 Dp
5844 closepath 3 2817 2275 2950 2408 Dp
5851 closepath 3 2684 2275 2817 2408 Dp
5935 2418 3489 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
5958 2418 4039(arranged)N
6000 2754 0.4028(referenced)AX
6006 2418 4567(address.)N
6034 2418 4831(requirements,)N
6100 2418 5561(predecessor)N
6108 2418 5649(over\257ow)N
6165 720 714(functionality,)N
6282 720 1972(over\257ow)N
6322 720 2412 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
6393 closepath 19 1402 3851 1471 3920 Dp
6394 1445 3747(Over\257ow)N
6461 closepath 19 2171 3471 2448 3609 Dp
6468 closepath 3 1756 3609 2033 3747 Dp
6475 closepath 19 1480 3471 1756 3609 Dp
6482 closepath 19 789 3471 1065 3609 Dp
6491 closepath 14 849 3851 918 3920 Dp
6498 closepath 14 1756 3194 1895 3471 Dp
6505 closepath 14 2171 3056 2309 3333 Dp
6512 closepath 14 1480 3056 1618 3333 Dp
6519 closepath 14 789 3056 927 3333 Dp
6599 closepath 3 1990 3851 2059 3920 Dp
6600 2102 3903(Over\257ow)N
6648 720 4624 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
6651 1406(Parameterization)X
6679 2079(user-de\256ned)X
6723 2706 538(bene\256t)N
6753 3499(approximation)X
6766 2706 1004(determining)N
6785 2706 1180(key/data)N
6810 2994 -0.3938(\(\(average_pair_length)AX
6814 3032 1743(ffactor\))N
6823 3551(applications,)X
6824 3999(experimenting)X
6833 2706 2218(encouraged.)N
6904 2706 2948(advance\),)N
6964 2706 3476(9000/370)N
6993 2706 3942(\(Figure)N
7003 2706 4030(performance)N
7033 2706 4294(formance)N
7112 2706 5112(clusions)N
7150 2706 5464(slightly)N
7206 432 538(performing)N
7231 1563(approximately)X
7234 432 802 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
7630 432 3234 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8038 2785(approximation)X
8044 2418 626(ultimately)N
8113 2418 1242(formance)N
8166 3378(suf\256ciently)X
8184 2418 1946 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8583 2418 4638 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8603 2418 5016(built-in)N
8645 2418 5368(speci\256ed)N
8664 2418 5544(speci\256ed,)N
8769 1324(collisions\).)X
8774 720 1066(applications,)N
8792 720 1330 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
8827 closepath 21 1895 2778 1950 2833 Dp
8834 closepath 14 1342 2778 1397 2833 Dp
8841 closepath 3 900 2778 955 2833 Dp
8859 closepath 14 2283 2211 2379 2252 Dp
8866 closepath 14 1992 2211 2089 2252 Dp
8873 closepath 14 1702 2211 1799 2252 Dp
8880 closepath 14 1411 2252 1508 2294 Dp
8887 closepath 3 2283 2252 2379 2612 Dp
8894 closepath 3 1992 2252 2089 2612 Dp
8901 closepath 3 1702 2252 1799 2612 Dp
8908 closepath 3 1411 2294 1508 2612 Dp
8916 closepath 21 2158 2238 2255 2252 Dp
8923 closepath 21 1868 2238 1965 2280 Dp
8930 closepath 21 1577 2238 1674 2308 Dp
8937 closepath 21 1287 2280 1384 2308 Dp
8944 closepath 14 2158 2252 2255 2280 Dp
8951 closepath 14 1868 2280 1965 2308 Dp
8958 closepath 14 1577 2308 1674 2335 Dp
8965 closepath 14 1287 2308 1384 2363 Dp
8972 closepath 3 2158 2280 2255 2612 Dp
8979 closepath 3 1868 2308 1965 2612 Dp
8986 closepath 3 1577 2335 1674 2612 Dp
8993 closepath 3 1287 2363 1384 2612 Dp
9001 closepath 21 1121 2066 1224 2080 Dp
9008 closepath 14 1121 2080 1218 2273 Dp
9015 closepath 3 1121 2273 1218 2612 Dp
9023 closepath 21 997 1589 1093 1644 Dp
9030 closepath 14 997 1644 1093 2280 Dp
9037 closepath 3 997 2280 1093 2612 Dp
9055 1701 2925(Dynamically)N
9123 720 3708 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
9131 720 3998(management,)N
9260 1782(inef\256cient)X
9583 2706 2949(inversely)N
9612 2706 3301 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
9614 3175 3543(Enhanced)N
9615 3536(Functionality)X
9644 2706 3939(additional)N
9645 3046(functionality)X
9685 3703(user-speci\256ed.)X
9703 3626(compatibility)X
9706 2706 4819(implement)N
9715 2706 4907(interface)N
9718 3540(functionality:)X
9740 2946 5215(currently.)N
9760 3799(user-speci\256ed)X
9762 2946 5567(runtime.)N
9796 1613(Implementation)X
9836 432 1022(4.3BSD-Reno)N
9913 432 1638(performance)N
9937 432 1928(previously.)N
10004 783(con\256guration)X
10029 591(approximately)X
10036 432 2896(con\256dence)N
10039 1183(approximately)X
10126 432 4420(sequential)N
10147 547 4710(retrieval)N
10164 547 4886(Therefore,)N
10207 547 5238(\(requiring)N
10233 3014 538(In-Memory)N
10252 2418 872(create/read)N
10285 2533 1250(troyed.)N
10287 2938 1404(Performance)N
10290 2590 1536(Figures)N
10310 2418 1712(implementation)N
10314 3360(implementation)X
10326 3243(appropriate\))X
10331 2418 1888(improvement.)N
10338 2418 1976(percentage)N
10350 2798 -0.4219(\(old_time)AX
10352 3254 -0.4219(new_time\))AX
10379 2418 2776(Although)N
10389 2418 2864(performance,)N
10399 2418 2952(writing)N
10410 2564(dictionary\),)X
10459 2418 3506(deceptive)N
10545 2418 4210(package)N
10559 2418 4412(memory-resident)N
10604 2418 4852(hsearch)N
10650 10 s 10 xH 0 xS 0 f
10664 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10672 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10677 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10713 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10715 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10720 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10731 1006 1282(elapsed)N
10756 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10758 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10763 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10774 1006 1650(elapsed)N
10799 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10801 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10803 948 1746(SEQUENTIAL)N
10806 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10817 1006 2018(elapsed)N
10842 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10844 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10846 948 2114(SEQUENTIAL)N
10852 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10863 1006 2386(elapsed)N
10870 927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10934 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10942 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10944 945 2762(CREATE/READ)N
10947 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
10965 930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11001 720 3262 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
11003 1407 3504(Conclusion)N
11030 720 3900(functionality)N
11093 720 4604(routines,)N
11126 720 5070(Berkeley.)N
11161 720 5422(key/data)N
11169 720 5510(application)N
11199 4075(applications)X
11219 2804(transactions,)X
11223 3723(incorporated)X
11228 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11236 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11241 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11252 2992 1398(elapsed)N
11277 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11279 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11284 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11295 2992 1766(elapsed)N
11320 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11322 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11327 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11338 2992 2134(elapsed)N
11363 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11365 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11367 2934 2230(SEQUENTIAL)N
11370 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11381 2992 2502(elapsed)N
11406 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11408 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11410 2934 2598(SEQUENTIAL)N
11416 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11427 2992 2870(elapsed)N
11434 2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11498 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11506 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11508 2931 3246(CREATE/READ)N
11511 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11522 2931 3518(elapsed)N
11529 2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X
11565 2706 3746 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
11567 3396 3988(References)N
11569 2706 4120([ATT79])N
11574 3990(Programmer's)X
11575 2878 4208(Manual,)N
11584 2706 4472([ATT85])N
11586 3296(HSEARCH\(BA_LIB\),)X
11599 2706 4736([BRE73])N
11610 3678(Techniques'',)X
11613 2878 4912(ications)N
11624 2878 5000(105-109,)N
11627 2706 5176([BSD86])N
11632 3990(Programmer's)X
11644 2706 5528([ENB88])N
11686 10 s 10 xH 0 xS 0 f
11704 604 626(Pippenger,)N
11708 1787(``Extendible)X
11720 1046(Transactions)X
11734 432 1066([KNU68],)N
11743 604 1154(gramming)N
11777 604 1770(Communications)N
11803 1424(Addressing'',)X
11810 1095(International)X
11835 432 2738([THOM90])N
11839 1670(communication,)X
11849 604 3090(archives'',)N
11873 1328(comp.unix.questions)X
11881 1135(``Discussion)X
11886 604 3794(system'',)N
11890 1762(unix.wizards)X
11893 604 3882(January,)N
11904 604 4146(Dbm/Ndbm'',)N
11930 10 s 10 xH 0 xS 0 f
11966 720 802(interests)N
11993 720 1154(software)N
11996 1509(microprocessors.)X
11999 720 1242(received)N
12006 720 1330 0.1953(Harvard/Radcliffe)AN
12028 720 1620(studying)N
12043 720 1796(Bruisers.)N
12058 886(Communications)X
12082 1583(administrator)X
12093 720 2438(Berkeley)N
12121 1400(interesting,)X
12125 720 2816(language)N
12126 1044(interpreters,)X
12127 1464(preprocessors,)X
12140 1515(public-domain)X
12143 720 3106(including)N
12153 720 3194(apparently)N
12162 720 3282(obsessions)N
12167 720 3370(language)N
12190 10 s 10 xH 0 xS 0 f