diff options
author | cvs2svn <cvs2svn@FreeBSD.org> | 1998-01-10 23:00:07 +0000 |
---|---|---|
committer | cvs2svn <cvs2svn@FreeBSD.org> | 1998-01-10 23:00:07 +0000 |
commit | 7c6e96080c4fb49bf912942804477d202a53396c (patch) | |
tree | 876b1afcb203be407dbb2ddfc69653f78b8680c2 /lib/libc/db/docs/hash.usenix.ps | |
parent | 1a06f650e6ca43e02260e8d252597fbed2cea73e (diff) | |
download | FreeBSD-src-7c6e96080c4fb49bf912942804477d202a53396c.zip FreeBSD-src-7c6e96080c4fb49bf912942804477d202a53396c.tar.gz |
This commit was manufactured by cvs2svn to create branch 'JB'.
Diffstat (limited to 'lib/libc/db/docs/hash.usenix.ps')
-rw-r--r-- | lib/libc/db/docs/hash.usenix.ps | 12209 |
1 files changed, 0 insertions, 12209 deletions
diff --git a/lib/libc/db/docs/hash.usenix.ps b/lib/libc/db/docs/hash.usenix.ps deleted file mode 100644 index c884778..0000000 --- a/lib/libc/db/docs/hash.usenix.ps +++ /dev/null @@ -1,12209 +0,0 @@ -%!PS-Adobe-1.0 -%%Creator: utopia:margo (& Seltzer,608-13E,8072,) -%%Title: stdin (ditroff) -%%CreationDate: Tue Dec 11 15:06:45 1990 -%%EndComments -% @(#)psdit.pro 1.3 4/15/88 -% lib/psdit.pro -- prolog for psdit (ditroff) files -% Copyright (c) 1984, 1985 Adobe Systems Incorporated. All Rights Reserved. -% last edit: shore Sat Nov 23 20:28:03 1985 -% RCSID: $Header: psdit.pro,v 2.1 85/11/24 12:19:43 shore Rel $ - -% Changed by Edward Wang (edward@ucbarpa.berkeley.edu) to handle graphics, -% 17 Feb, 87. - -/$DITroff 140 dict def $DITroff begin -/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def -/xi{0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto - /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F - /pagesave save def}def -/PB{save /psv exch def currentpoint translate - resolution 72 div dup neg scale 0 0 moveto}def -/PE{psv restore}def -/arctoobig 90 def /arctoosmall .05 def -/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def -/tan{dup sin exch cos div}def -/point{resolution 72 div mul}def -/dround {transform round exch round exch itransform}def -/xT{/devname exch def}def -/xr{/mh exch def /my exch def /resolution exch def}def -/xp{}def -/xs{docsave restore end}def -/xt{}def -/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not - {fonts slotno fontname findfont put fontnames slotno fontname put}if}def -/xH{/fontheight exch def F}def -/xS{/fontslant exch def F}def -/s{/fontsize exch def /fontheight fontsize def F}def -/f{/fontnum exch def F}def -/F{fontheight 0 le{/fontheight fontsize def}if - fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore - fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if - makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def -/X{exch currentpoint exch pop moveto show}def -/N{3 1 roll moveto show}def -/Y{exch currentpoint pop exch moveto show}def -/S{show}def -/ditpush{}def/ditpop{}def -/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def -/AN{4 2 roll moveto 0 exch ashow}def -/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def -/AS{0 exch ashow}def -/MX{currentpoint exch pop moveto}def -/MY{currentpoint pop exch moveto}def -/MXY{moveto}def -/cb{pop}def % action on unknown char -- nothing for now -/n{}def/w{}def -/p{pop showpage pagesave restore /pagesave save def}def -/Dt{/Dlinewidth exch def}def 1 Dt -/Ds{/Ddash exch def}def -1 Ds -/Di{/Dstipple exch def}def 1 Di -/Dsetlinewidth{2 Dlinewidth mul setlinewidth}def -/Dsetdash{Ddash 4 eq{[8 12]}{Ddash 16 eq{[32 36]} - {Ddash 20 eq{[32 12 8 12]}{[]}ifelse}ifelse}ifelse 0 setdash}def -/Dstroke{gsave Dsetlinewidth Dsetdash 1 setlinecap stroke grestore - currentpoint newpath moveto}def -/Dl{rlineto Dstroke}def -/arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop - currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def - currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def -/Dc{dup arcellipse Dstroke}def -/De{arcellipse Dstroke}def -/Da{/endv exch def /endh exch def /centerv exch def /centerh exch def - /cradius centerv centerv mul centerh centerh mul add sqrt def - /eradius endv endv mul endh endh mul add sqrt def - /endang endv endh atan def - /startang centerv neg centerh neg atan def - /sweep startang endang sub dup 0 lt{360 add}if def - sweep arctoobig gt - {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def - /midh midang cos midrad mul def /midv midang sin midrad mul def - midh neg midv neg endh endv centerh centerv midh midv Da - Da} - {sweep arctoosmall ge - {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def - centerv neg controldelt mul centerh controldelt mul - endv neg controldelt mul centerh add endh add - endh controldelt mul centerv add endv add - centerh endh add centerv endv add rcurveto Dstroke} - {centerh endh add centerv endv add rlineto Dstroke} - ifelse} - ifelse}def -/Dpatterns[ -[%cf[widthbits] -[8<0000000000000010>] -[8<0411040040114000>] -[8<0204081020408001>] -[8<0000103810000000>] -[8<6699996666999966>] -[8<0000800100001008>] -[8<81c36666c3810000>] -[8<0f0e0c0800000000>] -[8<0000000000000010>] -[8<0411040040114000>] -[8<0204081020408001>] -[8<0000001038100000>] -[8<6699996666999966>] -[8<0000800100001008>] -[8<81c36666c3810000>] -[8<0f0e0c0800000000>] -[8<0042660000246600>] -[8<0000990000990000>] -[8<0804020180402010>] -[8<2418814242811824>] -[8<6699996666999966>] -[8<8000000008000000>] -[8<00001c3e363e1c00>] -[8<0000000000000000>] -[32<00000040000000c00000004000000040000000e0000000000000000000000000>] -[32<00000000000060000000900000002000000040000000f0000000000000000000>] -[32<000000000000000000e0000000100000006000000010000000e0000000000000>] -[32<00000000000000002000000060000000a0000000f00000002000000000000000>] -[32<0000000e0000000000000000000000000000000f000000080000000e00000001>] -[32<0000090000000600000000000000000000000000000007000000080000000e00>] -[32<00010000000200000004000000040000000000000000000000000000000f0000>] -[32<0900000006000000090000000600000000000000000000000000000006000000>]] -[%ug -[8<0000020000000000>] -[8<0000020000002000>] -[8<0004020000002000>] -[8<0004020000402000>] -[8<0004060000402000>] -[8<0004060000406000>] -[8<0006060000406000>] -[8<0006060000606000>] -[8<00060e0000606000>] -[8<00060e000060e000>] -[8<00070e000060e000>] -[8<00070e000070e000>] -[8<00070e020070e000>] -[8<00070e020070e020>] -[8<04070e020070e020>] -[8<04070e024070e020>] -[8<04070e064070e020>] -[8<04070e064070e060>] -[8<06070e064070e060>] -[8<06070e066070e060>] -[8<06070f066070e060>] -[8<06070f066070f060>] -[8<060f0f066070f060>] -[8<060f0f0660f0f060>] -[8<060f0f0760f0f060>] -[8<060f0f0760f0f070>] -[8<0e0f0f0760f0f070>] -[8<0e0f0f07e0f0f070>] -[8<0e0f0f0fe0f0f070>] -[8<0e0f0f0fe0f0f0f0>] -[8<0f0f0f0fe0f0f0f0>] -[8<0f0f0f0ff0f0f0f0>] -[8<1f0f0f0ff0f0f0f0>] -[8<1f0f0f0ff1f0f0f0>] -[8<1f0f0f8ff1f0f0f0>] -[8<1f0f0f8ff1f0f0f8>] -[8<9f0f0f8ff1f0f0f8>] -[8<9f0f0f8ff9f0f0f8>] -[8<9f0f0f9ff9f0f0f8>] -[8<9f0f0f9ff9f0f0f9>] -[8<9f8f0f9ff9f0f0f9>] -[8<9f8f0f9ff9f8f0f9>] -[8<9f8f1f9ff9f8f0f9>] -[8<9f8f1f9ff9f8f1f9>] -[8<bf8f1f9ff9f8f1f9>] -[8<bf8f1f9ffbf8f1f9>] -[8<bf8f1fdffbf8f1f9>] -[8<bf8f1fdffbf8f1fd>] -[8<ff8f1fdffbf8f1fd>] -[8<ff8f1fdffff8f1fd>] -[8<ff8f1ffffff8f1fd>] -[8<ff8f1ffffff8f1ff>] -[8<ff9f1ffffff8f1ff>] -[8<ff9f1ffffff9f1ff>] -[8<ff9f9ffffff9f1ff>] -[8<ff9f9ffffff9f9ff>] -[8<ffbf9ffffff9f9ff>] -[8<ffbf9ffffffbf9ff>] -[8<ffbfdffffffbf9ff>] -[8<ffbfdffffffbfdff>] -[8<ffffdffffffbfdff>] -[8<ffffdffffffffdff>] -[8<fffffffffffffdff>] -[8<ffffffffffffffff>]] -[%mg -[8<8000000000000000>] -[8<0822080080228000>] -[8<0204081020408001>] -[8<40e0400000000000>] -[8<66999966>] -[8<8001000010080000>] -[8<81c36666c3810000>] -[8<f0e0c08000000000>] -[16<07c00f801f003e007c00f800f001e003c007800f001f003e007c00f801f003e0>] -[16<1f000f8007c003e001f000f8007c003e001f800fc007e003f001f8007c003e00>] -[8<c3c300000000c3c3>] -[16<0040008001000200040008001000200040008000000100020004000800100020>] -[16<0040002000100008000400020001800040002000100008000400020001000080>] -[16<1fc03fe07df0f8f8f07de03fc01f800fc01fe03ff07df8f87df03fe01fc00f80>] -[8<80>] -[8<8040201000000000>] -[8<84cc000048cc0000>] -[8<9900009900000000>] -[8<08040201804020100800020180002010>] -[8<2418814242811824>] -[8<66999966>] -[8<8000000008000000>] -[8<70f8d8f870000000>] -[8<0814224180402010>] -[8<aa00440a11a04400>] -[8<018245aa45820100>] -[8<221c224180808041>] -[8<88000000>] -[8<0855800080550800>] -[8<2844004482440044>] -[8<0810204080412214>] -[8<00>]]]def -/Dfill{ - transform /maxy exch def /maxx exch def - transform /miny exch def /minx exch def - minx maxx gt{/minx maxx /maxx minx def def}if - miny maxy gt{/miny maxy /maxy miny def def}if - Dpatterns Dstipple 1 sub get exch 1 sub get - aload pop /stip exch def /stipw exch def /stiph 128 def - /imatrix[stipw 0 0 stiph 0 0]def - /tmatrix[stipw 0 0 stiph 0 0]def - /minx minx cvi stiph idiv stiph mul def - /miny miny cvi stipw idiv stipw mul def - gsave eoclip 0 setgray - miny stiph maxy{ - tmatrix exch 5 exch put - minx stipw maxx{ - tmatrix exch 4 exch put tmatrix setmatrix - stipw stiph true imatrix {stip} imagemask - }for - }for - grestore -}def -/Dp{Dfill Dstroke}def -/DP{Dfill currentpoint newpath moveto}def -end - -/ditstart{$DITroff begin - /nfonts 60 def % NFONTS makedev/ditroff dependent! - /fonts[nfonts{0}repeat]def - /fontnames[nfonts{()}repeat]def -/docsave save def -}def - -% character outcalls -/oc{ - /pswid exch def /cc exch def /name exch def - /ditwid pswid fontsize mul resolution mul 72000 div def - /ditsiz fontsize resolution mul 72 div def - ocprocs name known{ocprocs name get exec}{name cb}ifelse -}def -/fractm [.65 0 0 .6 0 0] def -/fraction{ - /fden exch def /fnum exch def gsave /cf currentfont def - cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto - fnum show rmoveto currentfont cf setfont(\244)show setfont fden show - grestore ditwid 0 rmoveto -}def -/oce{grestore ditwid 0 rmoveto}def -/dm{ditsiz mul}def -/ocprocs 50 dict def ocprocs begin -(14){(1)(4)fraction}def -(12){(1)(2)fraction}def -(34){(3)(4)fraction}def -(13){(1)(3)fraction}def -(23){(2)(3)fraction}def -(18){(1)(8)fraction}def -(38){(3)(8)fraction}def -(58){(5)(8)fraction}def -(78){(7)(8)fraction}def -(sr){gsave 0 .06 dm rmoveto(\326)show oce}def -(is){gsave 0 .15 dm rmoveto(\362)show oce}def -(->){gsave 0 .02 dm rmoveto(\256)show oce}def -(<-){gsave 0 .02 dm rmoveto(\254)show oce}def -(==){gsave 0 .05 dm rmoveto(\272)show oce}def -(uc){gsave currentpoint 400 .009 dm mul add translate - 8 -8 scale ucseal oce}def -end - -% an attempt at a PostScript FONT to implement ditroff special chars -% this will enable us to -% cache the little buggers -% generate faster, more compact PS out of psdit -% confuse everyone (including myself)! -50 dict dup begin -/FontType 3 def -/FontName /DIThacks def -/FontMatrix [.001 0 0 .001 0 0] def -/FontBBox [-260 -260 900 900] def% a lie but ... -/Encoding 256 array def -0 1 255{Encoding exch /.notdef put}for -Encoding - dup 8#040/space put %space - dup 8#110/rc put %right ceil - dup 8#111/lt put %left top curl - dup 8#112/bv put %bold vert - dup 8#113/lk put %left mid curl - dup 8#114/lb put %left bot curl - dup 8#115/rt put %right top curl - dup 8#116/rk put %right mid curl - dup 8#117/rb put %right bot curl - dup 8#120/rf put %right floor - dup 8#121/lf put %left floor - dup 8#122/lc put %left ceil - dup 8#140/sq put %square - dup 8#141/bx put %box - dup 8#142/ci put %circle - dup 8#143/br put %box rule - dup 8#144/rn put %root extender - dup 8#145/vr put %vertical rule - dup 8#146/ob put %outline bullet - dup 8#147/bu put %bullet - dup 8#150/ru put %rule - dup 8#151/ul put %underline - pop -/DITfd 100 dict def -/BuildChar{0 begin - /cc exch def /fd exch def - /charname fd /Encoding get cc get def - /charwid fd /Metrics get charname get def - /charproc fd /CharProcs get charname get def - charwid 0 fd /FontBBox get aload pop setcachedevice - 2 setlinejoin 40 setlinewidth - newpath 0 0 moveto gsave charproc grestore - end}def -/BuildChar load 0 DITfd put -/CharProcs 50 dict def -CharProcs begin -/space{}def -/.notdef{}def -/ru{500 0 rls}def -/rn{0 840 moveto 500 0 rls}def -/vr{0 800 moveto 0 -770 rls}def -/bv{0 800 moveto 0 -1000 rls}def -/br{0 840 moveto 0 -1000 rls}def -/ul{0 -140 moveto 500 0 rls}def -/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def -/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def -/sq{80 0 rmoveto currentpoint dround newpath moveto - 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def -/bx{80 0 rmoveto currentpoint dround newpath moveto - 640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def -/ci{500 360 rmoveto currentpoint newpath 333 0 360 arc - 50 setlinewidth stroke}def - -/lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def -/lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def -/rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def -/rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def -/lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub - 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def -/rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub - 0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def -/lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def -/rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def -/lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def -/rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def -end - -/Metrics 50 dict def Metrics begin -/.notdef 0 def -/space 500 def -/ru 500 def -/br 0 def -/lt 416 def -/lb 416 def -/rt 416 def -/rb 416 def -/lk 416 def -/rk 416 def -/rc 416 def -/lc 416 def -/rf 416 def -/lf 416 def -/bv 416 def -/ob 350 def -/bu 350 def -/ci 750 def -/bx 750 def -/sq 750 def -/rn 500 def -/ul 500 def -/vr 0 def -end - -DITfd begin -/s2 500 def /s4 250 def /s3 333 def -/a4p{arcto pop pop pop pop}def -/2cx{2 copy exch}def -/rls{rlineto stroke}def -/currx{currentpoint pop}def -/dround{transform round exch round exch itransform} def -end -end -/DIThacks exch definefont pop -ditstart -(psc)xT -576 1 1 xr -1(Times-Roman)xf 1 f -2(Times-Italic)xf 2 f -3(Times-Bold)xf 3 f -4(Times-BoldItalic)xf 4 f -5(Helvetica)xf 5 f -6(Helvetica-Bold)xf 6 f -7(Courier)xf 7 f -8(Courier-Bold)xf 8 f -9(Symbol)xf 9 f -10(DIThacks)xf 10 f -10 s -1 f -xi -%%EndProlog - -%%Page: 1 1 -10 s 10 xH 0 xS 1 f -3 f -22 s -1249 626(A)N -1420(N)X -1547(ew)X -1796(H)X -1933(ashing)X -2467(P)X -2574(ackage)X -3136(for)X -3405(U)X -3532(N)X -3659(IX)X -2 f -20 s -3855 562(1)N -1 f -12 s -1607 779(Margo)N -1887(Seltzer)X -9 f -2179(-)X -1 f -2256(University)X -2686(of)X -2790(California,)X -3229(Berkeley)X -2015 875(Ozan)N -2242(Yigit)X -9 f -2464(-)X -1 f -2541(York)X -2762(University)X -3 f -2331 1086(ABSTRACT)N -1 f -10 s -1152 1222(UNIX)N -1385(support)X -1657(of)X -1756(disk)X -1921(oriented)X -2216(hashing)X -2497(was)X -2654(originally)X -2997(provided)X -3314(by)X -2 f -3426(dbm)X -1 f -3595([ATT79])X -3916(and)X -1152 1310(subsequently)N -1595(improved)X -1927(upon)X -2112(in)X -2 f -2199(ndbm)X -1 f -2402([BSD86].)X -2735(In)X -2826(AT&T)X -3068(System)X -3327(V,)X -3429(in-memory)X -3809(hashed)X -1152 1398(storage)N -1420(and)X -1572(access)X -1814(support)X -2090(was)X -2251(added)X -2479(in)X -2577(the)X -2 f -2711(hsearch)X -1 f -3000(library)X -3249(routines)X -3542([ATT85].)X -3907(The)X -1152 1486(result)N -1367(is)X -1457(a)X -1530(system)X -1789(with)X -1968(two)X -2125(incompatible)X -2580(hashing)X -2865(schemes,)X -3193(each)X -3377(with)X -3555(its)X -3666(own)X -3840(set)X -3965(of)X -1152 1574(shortcomings.)N -1152 1688(This)N -1316(paper)X -1517(presents)X -1802(the)X -1922(design)X -2152(and)X -2289(performance)X -2717(characteristics)X -3198(of)X -3286(a)X -3343(new)X -3498(hashing)X -3768(package)X -1152 1776(providing)N -1483(a)X -1539(superset)X -1822(of)X -1909(the)X -2027(functionality)X -2456(provided)X -2761(by)X -2 f -2861(dbm)X -1 f -3019(and)X -2 f -3155(hsearch)X -1 f -3409(.)X -3469(The)X -3614(new)X -3768(package)X -1152 1864(uses)N -1322(linear)X -1537(hashing)X -1818(to)X -1912(provide)X -2189(ef\256cient)X -2484(support)X -2755(of)X -2853(both)X -3026(memory)X -3324(based)X -3538(and)X -3685(disk)X -3849(based)X -1152 1952(hash)N -1319(tables)X -1526(with)X -1688(performance)X -2115(superior)X -2398(to)X -2480(both)X -2 f -2642(dbm)X -1 f -2800(and)X -2 f -2936(hsearch)X -1 f -3210(under)X -3413(most)X -3588(conditions.)X -3 f -1380 2128(Introduction)N -1 f -892 2260(Current)N -1196(UNIX)X -1456(systems)X -1768(offer)X -1984(two)X -2163(forms)X -2409(of)X -720 2348(hashed)N -973(data)X -1137(access.)X -2 f -1413(Dbm)X -1 f -1599(and)X -1745(its)X -1850(derivatives)X -2231(provide)X -720 2436(keyed)N -939(access)X -1171(to)X -1259(disk)X -1418(resident)X -1698(data)X -1858(while)X -2 f -2062(hsearch)X -1 f -2342(pro-)X -720 2524(vides)N -929(access)X -1175(for)X -1309(memory)X -1616(resident)X -1910(data.)X -2124(These)X -2356(two)X -720 2612(access)N -979(methods)X -1302(are)X -1453(incompatible)X -1923(in)X -2037(that)X -2209(memory)X -720 2700(resident)N -1011(hash)X -1195(tables)X -1419(may)X -1593(not)X -1731(be)X -1843(stored)X -2075(on)X -2191(disk)X -2360(and)X -720 2788(disk)N -884(resident)X -1169(tables)X -1387(cannot)X -1632(be)X -1739(read)X -1909(into)X -2063(memory)X -2360(and)X -720 2876(accessed)N -1022(using)X -1215(the)X -1333(in-memory)X -1709(routines.)X -2 f -892 2990(Dbm)N -1 f -1091(has)X -1241(several)X -1512(shortcomings.)X -2026(Since)X -2247(data)X -2423(is)X -720 3078(assumed)N -1032(to)X -1130(be)X -1242(disk)X -1411(resident,)X -1721(each)X -1905(access)X -2146(requires)X -2440(a)X -720 3166(system)N -963(call,)X -1120(and)X -1257(almost)X -1491(certainly,)X -1813(a)X -1869(disk)X -2022(operation.)X -2365(For)X -720 3254(extremely)N -1072(large)X -1264(databases,)X -1623(where)X -1851(caching)X -2131(is)X -2214(unlikely)X -720 3342(to)N -810(be)X -914(effective,)X -1244(this)X -1386(is)X -1466(acceptable,)X -1853(however,)X -2177(when)X -2378(the)X -720 3430(database)N -1022(is)X -1100(small)X -1298(\(i.e.)X -1447(the)X -1569(password)X -1896(\256le\),)X -2069(performance)X -720 3518(improvements)N -1204(can)X -1342(be)X -1443(obtained)X -1744(through)X -2018(caching)X -2293(pages)X -720 3606(of)N -818(the)X -947(database)X -1255(in)X -1348(memory.)X -1685(In)X -1782(addition,)X -2 f -2094(dbm)X -1 f -2262(cannot)X -720 3694(store)N -902(data)X -1062(items)X -1261(whose)X -1492(total)X -1660(key)X -1802(and)X -1943(data)X -2102(size)X -2252(exceed)X -720 3782(the)N -850(page)X -1034(size)X -1191(of)X -1290(the)X -1420(hash)X -1599(table.)X -1827(Similarly,)X -2176(if)X -2257(two)X -2409(or)X -720 3870(more)N -907(keys)X -1076(produce)X -1357(the)X -1477(same)X -1664(hash)X -1833(value)X -2029(and)X -2166(their)X -2334(total)X -720 3958(size)N -876(exceeds)X -1162(the)X -1291(page)X -1474(size,)X -1650(the)X -1779(table)X -1966(cannot)X -2210(store)X -2396(all)X -720 4046(the)N -838(colliding)X -1142(keys.)X -892 4160(The)N -1050(in-memory)X -2 f -1439(hsearch)X -1 f -1725(routines)X -2015(have)X -2199(different)X -720 4248(shortcomings.)N -1219(First,)X -1413(the)X -1539(notion)X -1771(of)X -1865(a)X -1928(single)X -2146(hash)X -2320(table)X -720 4336(is)N -807(embedded)X -1171(in)X -1266(the)X -1397(interface,)X -1732(preventing)X -2108(an)X -2217(applica-)X -720 4424(tion)N -902(from)X -1116(accessing)X -1482(multiple)X -1806(tables)X -2050(concurrently.)X -720 4512(Secondly,)N -1063(the)X -1186(routine)X -1438(to)X -1525(create)X -1743(a)X -1804(hash)X -1976(table)X -2157(requires)X -2440(a)X -720 4600(parameter)N -1066(which)X -1286(declares)X -1573(the)X -1694(size)X -1842(of)X -1932(the)X -2053(hash)X -2223(table.)X -2422(If)X -720 4688(this)N -856(size)X -1001(is)X -1074(set)X -1183(too)X -1305(low,)X -1465(performance)X -1892(degradation)X -2291(or)X -2378(the)X -720 4776(inability)N -1008(to)X -1092(add)X -1230(items)X -1425(to)X -1509(the)X -1628(table)X -1805(may)X -1964(result.)X -2223(In)X -2311(addi-)X -720 4864(tion,)N -2 f -910(hsearch)X -1 f -1210(requires)X -1515(that)X -1681(the)X -1825(application)X -2226(allocate)X -720 4952(memory)N -1037(for)X -1181(the)X -1329(key)X -1495(and)X -1661(data)X -1845(items.)X -2108(Lastly,)X -2378(the)X -2 f -720 5040(hsearch)N -1 f -1013(routines)X -1310(provide)X -1594(no)X -1713(interface)X -2034(to)X -2135(store)X -2329(hash)X -720 5128(tables)N -927(on)X -1027(disk.)X -16 s -720 5593 MXY -864 0 Dl -2 f -8 s -760 5648(1)N -1 f -9 s -5673(UNIX)Y -990(is)X -1056(a)X -1106(registered)X -1408(trademark)X -1718(of)X -1796(AT&T.)X -10 s -2878 2128(The)N -3032(goal)X -3199(of)X -3295(our)X -3431(work)X -3625(was)X -3779(to)X -3870(design)X -4108(and)X -4253(imple-)X -2706 2216(ment)N -2900(a)X -2970(new)X -3138(package)X -3436(that)X -3590(provides)X -3899(a)X -3968(superset)X -4264(of)X -4364(the)X -2706 2304(functionality)N -3144(of)X -3240(both)X -2 f -3411(dbm)X -1 f -3578(and)X -2 f -3723(hsearch)X -1 f -3977(.)X -4045(The)X -4198(package)X -2706 2392(had)N -2871(to)X -2982(overcome)X -3348(the)X -3495(interface)X -3826(shortcomings)X -4306(cited)X -2706 2480(above)N -2930(and)X -3078(its)X -3185(implementation)X -3719(had)X -3867(to)X -3961(provide)X -4238(perfor-)X -2706 2568(mance)N -2942(equal)X -3142(or)X -3235(superior)X -3524(to)X -3612(that)X -3758(of)X -3851(the)X -3975(existing)X -4253(imple-)X -2706 2656(mentations.)N -3152(In)X -3274(order)X -3498(to)X -3614(provide)X -3913(a)X -4003(compact)X -4329(disk)X -2706 2744(representation,)N -3224(graceful)X -3531(table)X -3729(growth,)X -4018(and)X -4176(expected)X -2706 2832(constant)N -3033(time)X -3234(performance,)X -3720(we)X -3873(selected)X -4191(Litwin's)X -2706 2920(linear)N -2923(hashing)X -3206(algorithm)X -3551([LAR88,)X -3872(LIT80].)X -4178(We)X -4324(then)X -2706 3008(enhanced)N -3037(the)X -3161(algorithm)X -3498(to)X -3586(handle)X -3826(page)X -4004(over\257ows)X -4346(and)X -2706 3096(large)N -2900(key)X -3049(handling)X -3362(with)X -3537(a)X -3606(single)X -3830(mechanism,)X -4248(named)X -2706 3184(buddy-in-waiting.)N -3 f -2975 3338(Existing)N -3274(UNIX)X -3499(Hashing)X -3802(Techniques)X -1 f -2878 3470(Over)N -3076(the)X -3210(last)X -3357(decade,)X -3637(several)X -3901(dynamic)X -4213(hashing)X -2706 3558(schemes)N -3000(have)X -3174(been)X -3348(developed)X -3700(for)X -3816(the)X -3936(UNIX)X -4159(timeshar-)X -2706 3646(ing)N -2856(system,)X -3146(starting)X -3433(with)X -3622(the)X -3767(inclusion)X -4107(of)X -2 f -4221(dbm)X -1 f -4359(,)X -4426(a)X -2706 3734(minimal)N -3008(database)X -3321(library)X -3571(written)X -3834(by)X -3950(Ken)X -4120(Thompson)X -2706 3822([THOM90],)N -3141(in)X -3248(the)X -3391(Seventh)X -3694(Edition)X -3974(UNIX)X -4220(system.)X -2706 3910(Since)N -2916(then,)X -3106(an)X -3214(extended)X -3536(version)X -3804(of)X -3903(the)X -4032(same)X -4228(library,)X -2 f -2706 3998(ndbm)N -1 f -2884(,)X -2933(and)X -3078(a)X -3142(public-domain)X -3637(clone)X -3839(of)X -3934(the)X -4060(latter,)X -2 f -4273(sdbm)X -1 f -4442(,)X -2706 4086(have)N -2902(been)X -3098(developed.)X -3491(Another)X -3797 0.1645(interface-compatible)AX -2706 4174(library)N -2 f -2950(gdbm)X -1 f -3128(,)X -3178(was)X -3333(recently)X -3622(made)X -3826(available)X -4145(as)X -4241(part)X -4395(of)X -2706 4262(the)N -2829(Free)X -2997(Software)X -3312(Foundation's)X -3759(\(FSF\))X -3970(software)X -4271(distri-)X -2706 4350(bution.)N -2878 4464(All)N -3017(of)X -3121(these)X -3323(implementations)X -3893(are)X -4029(based)X -4248(on)X -4364(the)X -2706 4552(idea)N -2871(of)X -2969(revealing)X -3299(just)X -3445(enough)X -3711(bits)X -3856(of)X -3953(a)X -4019(hash)X -4196(value)X -4400(to)X -2706 4640(locate)N -2920(a)X -2978(page)X -3151(in)X -3234(a)X -3291(single)X -3503(access.)X -3770(While)X -2 f -3987(dbm/ndbm)X -1 f -4346(and)X -2 f -2706 4728(sdbm)N -1 f -2908(map)X -3079(the)X -3210(hash)X -3390(value)X -3597(directly)X -3874(to)X -3968(a)X -4036(disk)X -4201(address,)X -2 f -2706 4816(gdbm)N -1 f -2921(uses)X -3096(the)X -3231(hash)X -3414(value)X -3624(to)X -3722(index)X -3936(into)X -4096(a)X -2 f -4168(directory)X -1 f -2706 4904([ENB88])N -3020(containing)X -3378(disk)X -3531(addresses.)X -2878 5018(The)N -2 f -3033(hsearch)X -1 f -3317(routines)X -3605(in)X -3697(System)X -3962(V)X -4049(are)X -4177(designed)X -2706 5106(to)N -2804(provide)X -3085(memory-resident)X -3669(hash)X -3852(tables.)X -4115(Since)X -4328(data)X -2706 5194(access)N -2948(does)X -3131(not)X -3269(require)X -3533(disk)X -3702(access,)X -3964(simple)X -4213(hashing)X -2706 5282(schemes)N -3010(which)X -3238(may)X -3408(require)X -3667(multiple)X -3964(probes)X -4209(into)X -4364(the)X -2706 5370(table)N -2889(are)X -3015(used.)X -3209(A)X -3294(more)X -3486(interesting)X -3851(version)X -4114(of)X -2 f -4208(hsearch)X -1 f -2706 5458(is)N -2784(a)X -2845(public)X -3070(domain)X -3335(library,)X -2 f -3594(dynahash)X -1 f -3901(,)X -3945(that)X -4089(implements)X -2706 5546(Larson's)N -3036(in-memory)X -3440(adaptation)X -3822([LAR88])X -4164(of)X -4279(linear)X -2706 5634(hashing)N -2975([LIT80].)X -3 f -720 5960(USENIX)N -9 f -1042(-)X -3 f -1106(Winter)X -1371('91)X -9 f -1498(-)X -3 f -1562(Dallas,)X -1815(TX)X -1 f -4424(1)X - -2 p -%%Page: 2 2 -10 s 10 xH 0 xS 1 f -3 f -432 258(A)N -510(New)X -682(Hashing)X -985(Package)X -1290(for)X -1413(UNIX)X -3663(Seltzer)X -3920(&)X -4007(Yigit)X -2 f -1074 538(dbm)N -1 f -1232(and)X -2 f -1368(ndbm)X -1 f -604 670(The)N -2 f -760(dbm)X -1 f -928(and)X -2 f -1074(ndbm)X -1 f -1282(library)X -1526(implementations)X -2089(are)X -432 758(based)N -667(on)X -799(the)X -949(same)X -1166(algorithm)X -1529(by)X -1661(Ken)X -1846(Thompson)X -432 846([THOM90,)N -824(TOR88,)X -1113(WAL84],)X -1452(but)X -1582(differ)X -1789(in)X -1879(their)X -2054(pro-)X -432 934(grammatic)N -801(interfaces.)X -1160(The)X -1311(latter)X -1502(is)X -1581(a)X -1643(modi\256ed)X -1952(version)X -432 1022(of)N -533(the)X -665(former)X -918(which)X -1148(adds)X -1328(support)X -1601(for)X -1728(multiple)X -2027(data-)X -432 1110(bases)N -634(to)X -724(be)X -828(open)X -1011(concurrently.)X -1484(The)X -1636(discussion)X -1996(of)X -2090(the)X -432 1198(algorithm)N -774(that)X -925(follows)X -1196(is)X -1280(applicable)X -1640(to)X -1732(both)X -2 f -1904(dbm)X -1 f -2072(and)X -2 f -432 1286(ndbm)N -1 f -610(.)X -604 1400(The)N -760(basic)X -956(structure)X -1268(of)X -2 f -1366(dbm)X -1 f -1535(calls)X -1712(for)X -1836(\256xed-sized)X -432 1488(disk)N -612(blocks)X -868(\(buckets\))X -1214(and)X -1377(an)X -2 f -1499(access)X -1 f -1755(function)X -2068(that)X -432 1576(maps)N -623(a)X -681(key)X -819(to)X -902(a)X -959(bucket.)X -1234(The)X -1380(interface)X -1683(routines)X -1962(use)X -2090(the)X -2 f -432 1664(access)N -1 f -673(function)X -970(to)X -1062(obtain)X -1292(the)X -1420(appropriate)X -1816(bucket)X -2060(in)X -2152(a)X -432 1752(single)N -643(disk)X -796(access.)X -604 1866(Within)N -869(the)X -2 f -1010(access)X -1 f -1263(function,)X -1593(a)X -1672(bit-randomizing)X -432 1954(hash)N -610(function)X -2 f -8 s -877 1929(2)N -1 f -10 s -940 1954(is)N -1024(used)X -1202(to)X -1294(convert)X -1565(a)X -1631(key)X -1777(into)X -1931(a)X -1997(32-bit)X -432 2042(hash)N -605(value.)X -825(Out)X -971(of)X -1064(these)X -1254(32)X -1359(bits,)X -1519(only)X -1686(as)X -1778(many)X -1981(bits)X -2121(as)X -432 2130(necessary)N -773(are)X -900(used)X -1075(to)X -1165(determine)X -1514(the)X -1639(particular)X -1974(bucket)X -432 2218(on)N -533(which)X -750(a)X -807(key)X -944(resides.)X -1228(An)X -1347(in-memory)X -1724(bitmap)X -1967(is)X -2041(used)X -432 2306(to)N -533(determine)X -893(how)X -1070(many)X -1287(bits)X -1441(are)X -1579(required.)X -1905(Each)X -2104(bit)X -432 2394(indicates)N -746(whether)X -1033(its)X -1136(associated)X -1494(bucket)X -1736(has)X -1871(been)X -2051(split)X -432 2482(yet)N -562(\(a)X -657(0)X -728(indicating)X -1079(that)X -1230(the)X -1359(bucket)X -1604(has)X -1742(not)X -1875(yet)X -2004(split\).)X -432 2570(The)N -590(use)X -730(of)X -830(the)X -961(hash)X -1141(function)X -1441(and)X -1590(the)X -1720(bitmap)X -1974(is)X -2059(best)X -432 2658(described)N -769(by)X -878(stepping)X -1177(through)X -1454(database)X -1759(creation)X -2046(with)X -432 2746(multiple)N -718(invocations)X -1107(of)X -1194(a)X -2 f -1250(store)X -1 f -1430(operation.)X -604 2860(Initially,)N -906(the)X -1033(hash)X -1209(table)X -1394(contains)X -1690(a)X -1755(single)X -1974(bucket)X -432 2948(\(bucket)N -711(0\),)X -836(the)X -972(bit)X -1094(map)X -1270(contains)X -1575(a)X -1649(single)X -1878(bit)X -2000(\(bit)X -2148(0)X -432 3036(corresponding)N -913(to)X -997(bucket)X -1233(0\),)X -1342(and)X -1480(0)X -1542(bits)X -1699(of)X -1788(a)X -1846(hash)X -2014(value)X -432 3124(are)N -560(examined)X -901(to)X -992(determine)X -1342(where)X -1568(a)X -1633(key)X -1778(is)X -1860(placed)X -2099(\(in)X -432 3212(bucket)N -670(0\).)X -801(When)X -1017(bucket)X -1255(0)X -1319(is)X -1396(full,)X -1551(its)X -1650(bit)X -1758(in)X -1844(the)X -1966(bitmap)X -432 3300(\(bit)N -564(0\))X -652(is)X -726(set,)X -856(and)X -993(its)X -1089(contents)X -1377(are)X -1497(split)X -1655(between)X -1943(buckets)X -432 3388(0)N -499(and)X -641(1,)X -727(by)X -833(considering)X -1233(the)X -1357(0)X -2 f -7 s -3356(th)Y -10 s -1 f -1480 3388(bit)N -1590(\(the)X -1741(lowest)X -1976(bit)X -2086(not)X -432 3476(previously)N -800(examined\))X -1169(of)X -1266(the)X -1393(hash)X -1569(value)X -1772(for)X -1895(each)X -2072(key)X -432 3564(within)N -668(the)X -798(bucket.)X -1064(Given)X -1292(a)X -1359(well-designed)X -1840(hash)X -2018(func-)X -432 3652(tion,)N -613(approximately)X -1112(half)X -1273(of)X -1376(the)X -1510(keys)X -1693(will)X -1853(have)X -2041(hash)X -432 3740(values)N -666(with)X -837(the)X -964(0)X -2 f -7 s -3708(th)Y -10 s -1 f -1090 3740(bit)N -1203(set.)X -1341(All)X -1471(such)X -1646(keys)X -1821(and)X -1965(associ-)X -432 3828(ated)N -586(data)X -740(are)X -859(moved)X -1097(to)X -1179(bucket)X -1413(1,)X -1493(and)X -1629(the)X -1747(rest)X -1883(remain)X -2126(in)X -432 3916(bucket)N -666(0.)X -604 4030(After)N -804(this)X -949(split,)X -1135(the)X -1262(\256le)X -1393(now)X -1560(contains)X -1856(two)X -2005(buck-)X -432 4118(ets,)N -562(and)X -699(the)X -818(bitmap)X -1061(contains)X -1349(three)X -1530(bits:)X -1687(the)X -1805(0)X -2 f -7 s -4086(th)Y -10 s -1 f -1922 4118(bit)N -2026(is)X -2099(set)X -432 4206(to)N -525(indicate)X -810(a)X -876(bucket)X -1120(0)X -1190(split)X -1357(when)X -1561(no)X -1671(bits)X -1816(of)X -1913(the)X -2041(hash)X -432 4294(value)N -648(are)X -789(considered,)X -1199(and)X -1357(two)X -1519(more)X -1726(unset)X -1937(bits)X -2094(for)X -432 4382(buckets)N -706(0)X -775(and)X -920(1.)X -1029(The)X -1183(placement)X -1542(of)X -1638(an)X -1742(incoming)X -2072(key)X -432 4470(now)N -604(requires)X -897(examination)X -1327(of)X -1428(the)X -1560(0)X -2 f -7 s -4438(th)Y -10 s -1 f -1691 4470(bit)N -1809(of)X -1910(the)X -2041(hash)X -432 4558(value,)N -667(and)X -824(the)X -963(key)X -1119(is)X -1212(placed)X -1462(either)X -1685(in)X -1787(bucket)X -2041(0)X -2121(or)X -432 4646(bucket)N -674(1.)X -782(If)X -864(either)X -1075(bucket)X -1317(0)X -1385(or)X -1480(bucket)X -1722(1)X -1790(\256lls)X -1937(up,)X -2064(it)X -2135(is)X -432 4734(split)N -598(as)X -693(before,)X -947(its)X -1050(bit)X -1162(is)X -1243(set)X -1360(in)X -1450(the)X -1576(bitmap,)X -1846(and)X -1990(a)X -2054(new)X -432 4822(set)N -541(of)X -628(unset)X -817(bits)X -952(are)X -1071(added)X -1283(to)X -1365(the)X -1483(bitmap.)X -604 4936(Each)N -791(time)X -959(we)X -1079(consider)X -1376(a)X -1437(new)X -1596(bit)X -1705(\(bit)X -1841(n\),)X -1953(we)X -2072(add)X -432 5024(2)N -2 f -7 s -4992(n)Y -9 f -509(+)X -1 f -540(1)X -10 s -595 5024(bits)N -737(to)X -826(the)X -951(bitmap)X -1199(and)X -1341(obtain)X -1567(2)X -2 f -7 s -4992(n)Y -9 f -1644(+)X -1 f -1675(1)X -10 s -1729 5024(more)N -1920(address-)X -432 5112(able)N -595(buckets)X -869(in)X -960(the)X -1087(\256le.)X -1258(As)X -1376(a)X -1441(result,)X -1668(the)X -1795(bitmap)X -2045(con-)X -432 5200(tains)N -618(the)X -751(previous)X -1062(2)X -2 f -7 s -5168(n)Y -9 f -1139(+)X -1 f -1170(1)X -2 f -10 s -9 f -5200(-)Y -1 f -1242(1)X -1317(bits)X -1467(\(1)X -2 f -9 f -1534(+)X -1 f -1578(2)X -2 f -9 f -(+)S -1 f -1662(4)X -2 f -9 f -(+)S -1 f -1746(...)X -2 f -9 f -(+)S -1 f -1850(2)X -2 f -7 s -5168(n)Y -10 s -1 f -1931 5200(\))N -1992(which)X -432 5288(trace)N -649(the)X -807(entire)X -2 f -1050(split)X -1247(history)X -1 f -1529(of)X -1656(the)X -1813(addressable)X -16 s -432 5433 MXY -864 0 Dl -2 f -8 s -472 5488(2)N -1 f -9 s -523 5513(This)N -670(bit-randomizing)X -1153(property)X -1416(is)X -1482(important)X -1780(to)X -1854(obtain)X -2052(radi-)X -432 5593(cally)N -599(different)X -874(hash)X -1033(values)X -1244(for)X -1355(nearly)X -1562(identical)X -1836(keys,)X -2012(which)X -432 5673(in)N -506(turn)X -640(avoids)X -846(clustering)X -1148(of)X -1226(such)X -1376(keys)X -1526(in)X -1600(a)X -1650(single)X -1840(bucket.)X -10 s -2418 538(buckets.)N -2590 652(Given)N -2809(a)X -2868(key)X -3007(and)X -3146(the)X -3267(bitmap)X -3512(created)X -3768(by)X -3871(this)X -4009(algo-)X -2418 740(rithm,)N -2638(we)X -2759(\256rst)X -2910(examine)X -3209(bit)X -3320(0)X -3386(of)X -3479(the)X -3603(bitmap)X -3851(\(the)X -4002(bit)X -4112(to)X -2418 828(consult)N -2673(when)X -2871(0)X -2934(bits)X -3072(of)X -3162(the)X -3283(hash)X -3453(value)X -3650(are)X -3772(being)X -3973(exam-)X -2418 916(ined\).)N -2631(If)X -2713(it)X -2785(is)X -2866(set)X -2982(\(indicating)X -3356(that)X -3503(the)X -3628(bucket)X -3869(split\),)X -4080(we)X -2418 1004(begin)N -2617(considering)X -3012(the)X -3131(bits)X -3267(of)X -3355(the)X -3473(32-bit)X -3684(hash)X -3851(value.)X -4085(As)X -2418 1092(bit)N -2525(n)X -2587(is)X -2662(revealed,)X -2977(a)X -3035(mask)X -3226(equal)X -3422(to)X -3506(2)X -2 f -7 s -1060(n)Y -9 f -3583(+)X -1 f -3614(1)X -2 f -10 s -9 f -1092(-)Y -1 f -3686(1)X -3748(will)X -3894(yield)X -4076(the)X -2418 1180(current)N -2675(bucket)X -2918(address.)X -3228(Adding)X -3496(2)X -2 f -7 s -1148(n)Y -9 f -3573(+)X -1 f -3604(1)X -2 f -10 s -9 f -1180(-)Y -1 f -3676(1)X -3744(to)X -3834(the)X -3960(bucket)X -2418 1268(address)N -2701(identi\256es)X -3035(which)X -3272(bit)X -3397(in)X -3500(the)X -3639(bitmap)X -3902(must)X -4098(be)X -2418 1356(checked.)N -2743(We)X -2876(continue)X -3173(revealing)X -3493(bits)X -3628(of)X -3715(the)X -3833(hash)X -4000(value)X -2418 1444(until)N -2591(all)X -2698(set)X -2814(bits)X -2955(in)X -3043(the)X -3167(bitmap)X -3415(are)X -3540(exhausted.)X -3907(The)X -4058(fol-)X -2418 1532(lowing)N -2682(algorithm,)X -3055(a)X -3133(simpli\256cation)X -3614(of)X -3723(the)X -3863(algorithm)X -2418 1620(due)N -2565(to)X -2658(Ken)X -2823(Thompson)X -3196([THOM90,)X -3590(TOR88],)X -3908(uses)X -4076(the)X -2418 1708(hash)N -2625(value)X -2839(and)X -2995(the)X -3133(bitmap)X -3395(to)X -3497(calculate)X -3823(the)X -3960(bucket)X -2418 1796(address)N -2679(as)X -2766(discussed)X -3093(above.)X -0(Courier)xf 0 f -1 f -0 f -8 s -2418 2095(hash)N -2608(=)X -2684 -0.4038(calchash\(key\);)AX -2418 2183(mask)N -2608(=)X -2684(0;)X -2418 2271(while)N -2646 -0.4018(\(isbitset\(\(hash)AX -3254(&)X -3330(mask\))X -3558(+)X -3634(mask\)\))X -2706 2359(mask)N -2896(=)X -2972(\(mask)X -3200(<<)X -3314(1\))X -3428(+)X -3504(1;)X -2418 2447(bucket)N -2684(=)X -2760(hash)X -2950(&)X -3026(mask;)X -2 f -10 s -3211 2812(sdbm)N -1 f -2590 2944(The)N -2 f -2738(sdbm)X -1 f -2930(library)X -3167(is)X -3243(a)X -3302(public-domain)X -3791(clone)X -3987(of)X -4076(the)X -2 f -2418 3032(ndbm)N -1 f -2638(library,)X -2914(developed)X -3286(by)X -3408(Ozan)X -3620(Yigit)X -3826(to)X -3929(provide)X -2 f -2418 3120(ndbm)N -1 f -2596('s)X -2692(functionality)X -3139(under)X -3359(some)X -3565(versions)X -3869(of)X -3973(UNIX)X -2418 3208(that)N -2559(exclude)X -2830(it)X -2894(for)X -3008(licensing)X -3317(reasons)X -3578([YIG89].)X -3895(The)X -4040(pro-)X -2418 3296(grammer)N -2735(interface,)X -3064(and)X -3207(the)X -3332(basic)X -3524(structure)X -3832(of)X -2 f -3926(sdbm)X -1 f -4121(is)X -2418 3384(identical)N -2733(to)X -2 f -2834(ndbm)X -1 f -3051(but)X -3192(internal)X -3476(details)X -3723(of)X -3828(the)X -2 f -3964(access)X -1 f -2418 3472(function,)N -2726(such)X -2894(as)X -2982(the)X -3101(calculation)X -3474(of)X -3561(the)X -3679(bucket)X -3913(address,)X -2418 3560(and)N -2563(the)X -2690(use)X -2825(of)X -2920(different)X -3225(hash)X -3400(functions)X -3726(make)X -3928(the)X -4054(two)X -2418 3648(incompatible)N -2856(at)X -2934(the)X -3052(database)X -3349(level.)X -2590 3762(The)N -2 f -2740(sdbm)X -1 f -2934(library)X -3173(is)X -3251(based)X -3458(on)X -3562(a)X -3622(simpli\256ed)X -3965(imple-)X -2418 3850(mentation)N -2778(of)X -2885(Larson's)X -3206(1978)X -2 f -3406(dynamic)X -3717(hashing)X -1 f -4009(algo-)X -2418 3938(rithm)N -2616(including)X -2943(the)X -2 f -3066(re\256nements)X -3461(and)X -3605(variations)X -1 f -3953(of)X -4044(sec-)X -2418 4026(tion)N -2562(5)X -2622([LAR78].)X -2956(Larson's)X -3257(original)X -3526(algorithm)X -3857(calls)X -4024(for)X -4138(a)X -2418 4114(forest)N -2635(of)X -2736(binary)X -2975(hash)X -3156(trees)X -3341(that)X -3494(are)X -3626(accessed)X -3941(by)X -4054(two)X -2418 4202(hash)N -2586(functions.)X -2925(The)X -3071(\256rst)X -3216(hash)X -3384(function)X -3672(selects)X -3907(a)X -3964(partic-)X -2418 4290(ular)N -2571(tree)X -2720(within)X -2952(the)X -3078(forest.)X -3309(The)X -3462(second)X -3713(hash)X -3887(function,)X -2418 4378(which)N -2659(is)X -2757(required)X -3070(to)X -3177(be)X -3297(a)X -3377(boolean)X -3675(pseudo-random)X -2418 4466(number)N -2687(generator)X -3015(that)X -3159(is)X -3236(seeded)X -3479(by)X -3583(the)X -3705(key,)X -3865(is)X -3942(used)X -4112(to)X -2418 4554(traverse)N -2733(the)X -2890(tree)X -3070(until)X -3275(internal)X -3579(\(split\))X -3829(nodes)X -4075(are)X -2418 4642(exhausted)N -2763(and)X -2903(an)X -3003(external)X -3286(\(non-split\))X -3648(node)X -3827(is)X -3903(reached.)X -2418 4730(The)N -2571(bucket)X -2813(addresses)X -3149(are)X -3276(stored)X -3500(directly)X -3772(in)X -3861(the)X -3986(exter-)X -2418 4818(nal)N -2536(nodes.)X -2590 4932(Larson's)N -2903(re\256nements)X -3309(are)X -3440(based)X -3655(on)X -3767(the)X -3897(observa-)X -2418 5020(tion)N -2570(that)X -2718(the)X -2844(nodes)X -3059(can)X -3199(be)X -3303(represented)X -3702(by)X -3809(a)X -3872(single)X -4090(bit)X -2418 5108(that)N -2569(is)X -2653(set)X -2773(for)X -2898(internal)X -3174(nodes)X -3392(and)X -3539(not)X -3672(set)X -3791(for)X -3915(external)X -2418 5196(nodes,)N -2652(resulting)X -2959(in)X -3048(a)X -3111(radix)X -3303(search)X -3536(trie.)X -3709(Figure)X -3944(1)X -4010(illus-)X -2418 5284(trates)N -2621(this.)X -2804(Nodes)X -3037(A)X -3123(and)X -3267(B)X -3348(are)X -3475(internal)X -3748(\(split\))X -3967(nodes,)X -2418 5372(thus)N -2573(having)X -2813(no)X -2915(bucket)X -3151(addresses)X -3480(associated)X -3831(with)X -3994(them.)X -2418 5460(Instead,)N -2693(the)X -2814(external)X -3096(nodes)X -3306(\(C,)X -3429(D,)X -3530(and)X -3669(E\))X -3768(each)X -3938(need)X -4112(to)X -2418 5548(refer)N -2594(to)X -2679(a)X -2738(bucket)X -2975(address.)X -3279(These)X -3494(bucket)X -3731(addresses)X -4062(can)X -2418 5636(be)N -2529(stored)X -2760(in)X -2857(the)X -2990(trie)X -3132(itself)X -3327(where)X -3559(the)X -3691(subtries)X -3974(would)X -3 f -432 5960(2)N -2970(USENIX)X -9 f -3292(-)X -3 f -3356(Winter)X -3621('91)X -9 f -3748(-)X -3 f -3812(Dallas,)X -4065(TX)X - -3 p -%%Page: 3 3 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -720 258(Seltzer)N -977(&)X -1064(Yigit)X -3278(A)X -3356(New)X -3528(Hashing)X -3831(Package)X -4136(for)X -4259(UNIX)X -1 f -720 538(live)N -862(if)X -933(they)X -1092(existed)X -1340([KNU68].)X -1709(For)X -1841(example,)X -2154(if)X -2224(nodes)X -2432(F)X -720 626(and)N -858(G)X -938(were)X -1117(the)X -1237(children)X -1522(of)X -1610(node)X -1787(C,)X -1881(the)X -2000(bucket)X -2235(address)X -720 714(L00)N -886(could)X -1101(reside)X -1330(in)X -1429(the)X -1563(bits)X -1714(that)X -1870(will)X -2030(eventually)X -2400(be)X -720 802(used)N -887(to)X -969(store)X -1145(nodes)X -1352(F)X -1416(and)X -1552(G)X -1630(and)X -1766(all)X -1866(their)X -2033(children.)X -10 f -720 890 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -1894 2247(L1)N -784 1925(A)N -1431(E)X -1106 2247(D)N -1428 1281(C)N -1109 1603(B)N -1884 1930(L01)N -1879 1286(L00)N -1221 1814(1)N -903 2131(1)N -1221 1402(0)N -903 1714(0)N -1 Dt -1397 1821 MXY --8 -32 Dl --5 19 Dl --20 6 Dl -33 7 Dl --187 -182 Dl -1397 1322 MXY --33 7 Dl -20 6 Dl -5 19 Dl -8 -32 Dl --187 182 Dl -1069 1639 MXY --32 7 Dl -20 6 Dl -5 19 Dl -7 -32 Dl --186 182 Dl -1374 1891 MXY -185 Dc -1779 2133 MXY -0 161 Dl -322 0 Dl -0 -161 Dl --322 0 Dl -1811 MY -0 161 Dl -322 0 Dl -0 -161 Dl --322 0 Dl -1166 MY -0 161 Dl -322 0 Dl -0 -161 Dl --322 0 Dl -1052 2213 MXY -185 Dc -1569 MY -185 Dc -720 1881 MXY -185 Dc -1779 2213 MXY --28 -17 Dl -10 17 Dl --10 18 Dl -28 -18 Dl --543 0 Dl -1769 1891 MXY --28 -18 Dl -10 18 Dl --10 18 Dl -28 -18 Dl --201 0 Dl -1364 1247 MXY -185 Dc -1769 MX --28 -18 Dl -10 18 Dl --10 18 Dl -28 -18 Dl --201 0 Dl -1064 2143 MXY --7 -32 Dl --5 19 Dl --20 6 Dl -32 7 Dl --181 -181 Dl -3 Dt --1 Ds -8 s -720 2482(Figure)N -925(1:)X -1 f -1002(Radix)X -1179(search)X -1365(trie)X -1474(with)X -1612(internal)X -1831(nodes)X -2004(A)X -2074(and)X -2189(B,)X -2271(external)X -720 2570(nodes)N -891(C,)X -972(D,)X -1056(and)X -1170(E,)X -1247(and)X -1361(bucket)X -1553(addresses)X -1819(stored)X -1997(in)X -2069(the)X -2168(unused)X -2370(por-)X -720 2658(tion)N -836(of)X -905(the)X -999(trie.)X -10 s -10 f -720 2922 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -1 f -892 3124(Further)N -1153(simpli\256cations)X -1647(of)X -1738(the)X -1860(above)X -2076([YIG89])X -2377(are)X -720 3212(possible.)N -1038(Using)X -1265(a)X -1337(single)X -1564(radix)X -1765(trie)X -1908(to)X -2006(avoid)X -2219(the)X -2352(\256rst)X -720 3300(hash)N -904(function,)X -1227(replacing)X -1562(the)X -1696(pseudo-random)X -2231(number)X -720 3388(generator)N -1052(with)X -1222(a)X -1286(well)X -1452(designed,)X -1785(bit-randomizing)X -2329(hash)X -720 3476(function,)N -1053(and)X -1215(using)X -1434(the)X -1578(portion)X -1855(of)X -1967(the)X -2110(hash)X -2302(value)X -720 3564(exposed)N -1021(during)X -1268(the)X -1404(trie)X -1549(traversal)X -1864(as)X -1969(a)X -2042(direct)X -2262(bucket)X -720 3652(address)N -990(results)X -1228(in)X -1319(an)X -2 f -1424(access)X -1 f -1663(function)X -1959(that)X -2108(works)X -2333(very)X -720 3740(similar)N -974(to)X -1068(Thompson's)X -1499(algorithm)X -1841(above.)X -2084(The)X -2240(follow-)X -720 3828(ing)N -847(algorithm)X -1183(uses)X -1346(the)X -1469(hash)X -1641(value)X -1840(to)X -1927(traverse)X -2206(a)X -2266(linear-)X -720 3916(ized)N -874(radix)X -1059(trie)X -2 f -8 s -1166 3891(3)N -1 f -10 s -1218 3916(starting)N -1478(at)X -1556(the)X -1674(0)X -2 f -7 s -3884(th)Y -10 s -1 f -1791 3916(bit.)N -0 f -8 s -720 4215(tbit)N -910(=)X -986(0;)X -1296(/*)X -1410(radix)X -1638(trie)X -1828(index)X -2056(*/)X -720 4303(hbit)N -910(=)X -986(0;)X -1296(/*)X -1410(hash)X -1600(bit)X -1752(index)X -2056(*/)X -720 4391(mask)N -910(=)X -986(0;)X -720 4479(hash)N -910(=)X -986 -0.4038(calchash\(key\);)AX -720 4655(for)N -872(\(mask)X -1100(=)X -1176(0;)X -910 4743 -0.4018(isbitset\(tbit\);)AN -910 4831(mask)N -1100(=)X -1176(\(mask)X -1404(<<)X -1518(1\))X -1632(+)X -1708(1\))X -1008 4919(if)N -1122(\(hash)X -1350(&)X -1426(\(1)X -1540(<<)X -1654 -0.4219(hbit++\)\)\))AX -1160 5007(/*)N -1274(right)X -1502(son)X -1692(*/)X -1160 5095(tbit)N -1350(=)X -1426(2)X -1502(*)X -1578(tbit)X -1768(+)X -1844(2;)X -1008 5183(else)N -1 f -16 s -720 5353 MXY -864 0 Dl -2 f -8 s -760 5408(3)N -1 f -9 s -818 5433(A)N -896(linearized)X -1206(radix)X -1380(trie)X -1502(is)X -1576(merely)X -1802(an)X -1895(array)X -2068(representation)X -720 5513(of)N -800(the)X -908(radix)X -1076(search)X -1280(trie)X -1396(described)X -1692(above.)X -1920(The)X -2052(children)X -2308(of)X -2388(the)X -720 5593(node)N -885(with)X -1038(index)X -1223(i)X -1267(can)X -1391(be)X -1483(found)X -1675(at)X -1751(the)X -1863(nodes)X -2055(indexed)X -2307(2*i+1)X -720 5673(and)N -842(2*i+2.)X -0 f -8 s -3146 538(/*)N -3260(left)X -3450(son)X -3678(*/)X -3146 626(tbit)N -3336(=)X -3412(2)X -3488(*)X -3564(tbit)X -3754(+)X -3830(1;)X -2706 802(bucket)N -2972(=)X -3048(hash)X -3238(&)X -3314(mask;)X -2 f -10 s -3495 1167(gdbm)N -1 f -2878 1299(The)N -3027(gdbm)X -3233(\(GNU)X -3458(data)X -3616(base)X -3783(manager\))X -4111(library)X -4349(is)X -4426(a)X -2706 1387(UNIX)N -2933(database)X -3236(manager)X -3539(written)X -3792(by)X -3897(Philip)X -4112(A.)X -4215(Nelson,)X -2706 1475(and)N -2848(made)X -3048(available)X -3364(as)X -3457(a)X -3518(part)X -3668(of)X -3760(the)X -3883(FSF)X -4040(software)X -4342(dis-)X -2706 1563(tribution.)N -3052(The)X -3207(gdbm)X -3419(library)X -3663(provides)X -3969(the)X -4097(same)X -4292(func-)X -2706 1651(tionality)N -3028(of)X -3151(the)X -2 f -3304(dbm)X -1 f -3442(/)X -2 f -3464(ndbm)X -1 f -3697(libraries)X -4015([NEL90])X -4360(but)X -2706 1739(attempts)N -3018(to)X -3121(avoid)X -3340(some)X -3550(of)X -3658(their)X -3846(shortcomings.)X -4337(The)X -2706 1827(gdbm)N -2918(library)X -3162(allows)X -3401(for)X -3525(arbitrary-length)X -4059(data,)X -4242(and)X -4387(its)X -2706 1915(database)N -3027(is)X -3124(a)X -3203(singular,)X -3524(non-sparse)X -2 f -8 s -3872 1890(4)N -1 f -10 s -3947 1915(\256le.)N -4112(The)X -4280(gdbm)X -2706 2003(library)N -2947(also)X -3103(includes)X -2 f -3396(dbm)X -1 f -3560(and)X -2 f -3702(ndbm)X -1 f -3906(compatible)X -4288(inter-)X -2706 2091(faces.)N -2878 2205(The)N -3025(gdbm)X -3229(library)X -3465(is)X -3540(based)X -3745(on)X -2 f -3847(extensible)X -4189(hashing)X -1 f -4442(,)X -2706 2293(a)N -2766(dynamic)X -3066(hashing)X -3339(algorithm)X -3674(by)X -3778(Fagin)X -3984(et)X -4066(al)X -4148([FAG79].)X -2706 2381(This)N -2881(algorithm)X -3225(differs)X -3467(from)X -3655(the)X -3785(previously)X -4155(discussed)X -2706 2469(algorithms)N -3069(in)X -3152(that)X -3293(it)X -3358(uses)X -3517(a)X -2 f -3574(directory)X -1 f -3889(that)X -4030(is)X -4103(a)X -4159(collapsed)X -2706 2557(representation)N -3192([ENB88])X -3517(of)X -3615(the)X -3744(radix)X -3940(search)X -4177(trie)X -4315(used)X -2706 2645(by)N -2 f -2806(sdbm)X -1 f -2975(.)X -10 f -2706 2733 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -7 s -3572 3761(L1)N -1 Dt -3485 3738 MXY --20 -13 Dl -7 13 Dl --7 13 Dl -20 -13 Dl --400 0 Dl -3180 3027 MXY -136 Dc -2706 3494 MXY -136 Dc -2950 3264 MXY -136 Dc -3738 MY -136 Dc -3485 2968 MXY -0 118 Dl -238 0 Dl -0 -118 Dl --238 0 Dl -3442 MY -0 119 Dl -238 0 Dl -0 -119 Dl --238 0 Dl -3679 MY -0 119 Dl -238 0 Dl -0 -119 Dl --238 0 Dl -3187 3501 MXY -136 Dc -2963 3316 MXY --24 5 Dl -15 4 Dl -4 15 Dl -5 -24 Dl --137 134 Dl -3204 3083 MXY --24 5 Dl -15 4 Dl -3 14 Dl -6 -23 Dl --137 133 Dl -3204 3450 MXY --6 -24 Dl --3 14 Dl --15 5 Dl -24 5 Dl --137 -134 Dl -2842 3369(0)N -3075 3139(0)N -2842 3676(1)N -3075 3443(1)N -3562 3054(L00)N -3565 3528(L01)N -4197 2968 MXY -0 118 Dl -237 0 Dl -0 -118 Dl --237 0 Dl -3205 MY -0 119 Dl -237 0 Dl -0 -119 Dl --237 0 Dl -3561 MY -0 118 Dl -237 0 Dl -0 -118 Dl --237 0 Dl -3960 2909 MXY -0 237 Dl -118 0 Dl -0 -237 Dl --118 0 Dl -3146 MY -0 237 Dl -118 0 Dl -0 -237 Dl --118 0 Dl -3383 MY -0 237 Dl -118 0 Dl -0 -237 Dl --118 0 Dl -3620 MY -0 237 Dl -118 0 Dl -0 -237 Dl --118 0 Dl -4197 3027 MXY --21 -13 Dl -8 13 Dl --8 13 Dl -21 -13 Dl --119 0 Dl -4197 3264 MXY --21 -13 Dl -8 13 Dl --8 13 Dl -21 -13 Dl --119 0 Dl -3501 MY -59 0 Dl -0 89 Dl -4078 3738 MXY -59 0 Dl -0 -88 Dl -4197 3590 MXY --21 -13 Dl -8 13 Dl --8 13 Dl -21 -13 Dl --60 0 Dl -4197 3650 MXY --21 -13 Dl -8 13 Dl --8 13 Dl -21 -13 Dl --60 0 Dl -3991 3050(00)N -3991 3287(01)N -3991 3524(10)N -3991 3761(11)N -4269 3050(L00)N -4269 3287(L01)N -4283 3643(L1)N -3485 3501 MXY --20 -13 Dl -7 13 Dl --7 13 Dl -20 -13 Dl --155 0 Dl -3485 3027 MXY --20 -13 Dl -7 13 Dl --7 13 Dl -20 -13 Dl --163 0 Dl -2967 3687 MXY --5 -24 Dl --4 14 Dl --15 4 Dl -24 6 Dl --141 -141 Dl -3 Dt --1 Ds -8 s -2706 4033(Figure)N -2903(2:)X -1 f -2972(A)X -3034(radix)X -3181(search)X -3359(trie)X -3460(and)X -3568(a)X -3612(directory)X -3858(representing)X -4189(the)X -4283(trie.)X -10 s -10 f -2706 4209 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -1 f -2878 4411(In)N -2968(this)X -3106(algorithm,)X -3460(a)X -3519(directory)X -3832(consists)X -4108(of)X -4198(a)X -4256(search)X -2706 4499(trie)N -2847(of)X -2947(depth)X -2 f -3158(n)X -1 f -3211(,)X -3264(containing)X -3635(2)X -2 f -7 s -4467(n)Y -10 s -1 f -3749 4499(bucket)N -3996(addresses)X -4337(\(i.e.)X -2706 4587(each)N -2897(element)X -3194(of)X -3304(the)X -3445(trie)X -3594(is)X -3689(a)X -3767(bucket)X -4023(address\).)X -4373(To)X -2706 4675(access)N -2935(the)X -3056(hash)X -3226(table,)X -3425(a)X -3483(32-bit)X -3696(hash)X -3865(value)X -4061(is)X -4136(calculated)X -2706 4763(and)N -2 f -2861(n)X -1 f -2953(bits)X -3107(of)X -3213(the)X -3350(value)X -3563(are)X -3701(used)X -3886(to)X -3986(index)X -4202(into)X -4364(the)X -2706 4851(directory)N -3018(to)X -3102(obtain)X -3324(a)X -3382(bucket)X -3618(address.)X -3921(It)X -3992(is)X -4067(important)X -4400(to)X -2706 4939(note)N -2866(that)X -3008(multiple)X -3296(entries)X -3532(of)X -3620(this)X -3756(directory)X -4067(may)X -4226(contain)X -2706 5027(the)N -2833(same)X -3026(bucket)X -3268(address)X -3537(as)X -3632(a)X -3696(result)X -3902(of)X -3997(directory)X -4315(dou-)X -2706 5115(bling)N -2903(during)X -3145(bucket)X -3392(splitting.)X -3706(Figure)X -3948(2)X -4021(illustrates)X -4364(the)X -2706 5203(relationship)N -3126(between)X -3436(a)X -3513(typical)X -3772(\(skewed\))X -4108(search)X -4355(trie)X -2706 5291(and)N -2850(its)X -2953(directory)X -3271(representation.)X -3774(The)X -3927(formation)X -4270(of)X -4364(the)X -2706 5379(directory)N -3016(shown)X -3245(in)X -3327(the)X -3445(\256gure)X -3652(is)X -3725(as)X -3812(follows.)X -16 s -2706 5593 MXY -864 0 Dl -2 f -8 s -2746 5648(4)N -1 f -9 s -2796 5673(It)N -2858(does)X -3008(not)X -3118(contain)X -3348(holes.)X -3 f -10 s -720 5960(USENIX)N -9 f -1042(-)X -3 f -1106(Winter)X -1371('91)X -9 f -1498(-)X -3 f -1562(Dallas,)X -1815(TX)X -4424(3)X - -4 p -%%Page: 4 4 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -432 258(A)N -510(New)X -682(Hashing)X -985(Package)X -1290(for)X -1413(UNIX)X -3663(Seltzer)X -3920(&)X -4007(Yigit)X -1 f -604 538(Initially,)N -937(there)X -1158(is)X -1271(one)X -1446(slot)X -1620(in)X -1741(the)X -1898(directory)X -432 626(addressing)N -802(a)X -865(single)X -1083(bucket.)X -1364(The)X -1515(depth)X -1719(of)X -1812(the)X -1936(trie)X -2069(is)X -2148(0)X -432 714(and)N -577(0)X -646(bits)X -790(of)X -886(each)X -1063(hash)X -1239(value)X -1442(are)X -1570(examined)X -1910(to)X -2000(deter-)X -432 802(mine)N -624(in)X -718(which)X -946(bucket)X -1192(to)X -1286(place)X -1488(a)X -1556(key;)X -1726(all)X -1837(keys)X -2015(go)X -2126(in)X -432 890(bucket)N -682(0.)X -797(When)X -1024(this)X -1174(bucket)X -1423(is)X -1511(full,)X -1677(its)X -1787(contents)X -2089(are)X -432 978(divided)N -698(between)X -992(L0)X -1107(and)X -1249(L1)X -1363(as)X -1455(was)X -1605(done)X -1786(in)X -1873(the)X -1996(previ-)X -432 1066(ously)N -664(discussed)X -1030(algorithms.)X -1471(After)X -1700(this)X -1874(split,)X -2090(the)X -432 1154(address)N -710(of)X -814(the)X -948(second)X -1207(bucket)X -1457(must)X -1648(be)X -1760(stored)X -1992(in)X -2090(the)X -432 1242(directory.)N -796(To)X -939(accommodate)X -1438(the)X -1589(new)X -1776(address,)X -2090(the)X -432 1330(directory)N -752(is)X -835(split)X -2 f -8 s -972 1305(5)N -1 f -10 s -1330(,)Y -1054(by)X -1163(doubling)X -1476(it,)X -1569(thus)X -1731(increasing)X -2090(the)X -432 1418(depth)N -630(of)X -717(the)X -835(directory)X -1145(by)X -1245(one.)X -604 1532(After)N -813(this)X -967(split,)X -1163(a)X -1237(single)X -1466(bit)X -1588(of)X -1693(the)X -1829(hash)X -2014(value)X -432 1620(needs)N -663(to)X -773(be)X -896(examined)X -1255(to)X -1364(decide)X -1621(whether)X -1927(the)X -2072(key)X -432 1708(belongs)N -711(to)X -803(L0)X -922(or)X -1019(L1.)X -1158(Once)X -1358(one)X -1504(of)X -1601(these)X -1795(buckets)X -2069(\256lls)X -432 1796(\(L0)N -578(for)X -702(example\),)X -1051(it)X -1125(is)X -1208(split)X -1375(as)X -1472(before,)X -1728(and)X -1873(the)X -2000(direc-)X -432 1884(tory)N -585(is)X -662(split)X -823(again)X -1021(to)X -1107(make)X -1305(room)X -1498(for)X -1615(the)X -1736(address)X -2000(of)X -2090(the)X -432 1972(third)N -618(bucket.)X -927(This)X -1104(splitting)X -1400(causes)X -1645(the)X -1778(addresses)X -2121(of)X -432 2060(the)N -567(non-splitting)X -1012(bucket)X -1263(\(L1\))X -1443(to)X -1541(be)X -1653(duplicated.)X -2063(The)X -432 2148(directory)N -766(now)X -948(has)X -1099(four)X -1277(entries,)X -1555(a)X -1635(depth)X -1857(of)X -1968(2,)X -2072(and)X -432 2236(indexes)N -700(the)X -821(buckets)X -1089(L00,)X -1261(L01)X -1413(and)X -1552(L1,)X -1684(as)X -1774(shown)X -2006(in)X -2090(the)X -432 2324(Figure)N -661(2.)X -604 2438(The)N -756(crucial)X -1002(part)X -1154(of)X -1247(the)X -1371(algorithm)X -1708(is)X -1787(the)X -1911(observa-)X -432 2526(tion)N -580(that)X -724(L1)X -837(is)X -914(addressed)X -1255(twice)X -1453(in)X -1539(the)X -1661(directory.)X -1995(If)X -2073(this)X -432 2614(bucket)N -679(were)X -869(to)X -964(split)X -1134(now,)X -1324(the)X -1454(directory)X -1776(already)X -2045(con-)X -432 2702(tains)N -611(room)X -808(to)X -898(hold)X -1067(the)X -1192(address)X -1460(of)X -1554(the)X -1679(new)X -1840(bucket.)X -2121(In)X -432 2790(general,)N -711(the)X -831(relationship)X -1231(between)X -1521(the)X -1641(directory)X -1953(and)X -2090(the)X -432 2878(number)N -704(of)X -798(bucket)X -1039(addresses)X -1374(contained)X -1713(therein)X -1962(is)X -2041(used)X -432 2966(to)N -517(decide)X -750(when)X -947(to)X -1031(split)X -1190(the)X -1310(directory.)X -1662(Each)X -1845(bucket)X -2081(has)X -432 3054(a)N -505(depth,)X -740(\()X -2 f -767(n)X -7 s -3070(b)Y -10 s -1 f -848 3054(\),)N -932(associated)X -1299(with)X -1478(it)X -1558(and)X -1710(appears)X -1992(in)X -2090(the)X -432 3142(directory)N -744(exactly)X -998(2)X -2 f -7 s -3106(n)Y -9 f -1075(-)X -2 f -1106(n)X -4 s -3110(b)Y -7 s -1 f -10 s -1181 3142(times.)N -1396(When)X -1610(a)X -1668(bucket)X -1904(splits,)X -2113(its)X -432 3230(depth)N -638(increases)X -961(by)X -1069(one.)X -1253(The)X -1406(directory)X -1724(must)X -1907(split)X -2072(any)X -432 3318(time)N -602(a)X -665(bucket's)X -964(depth)X -1169(exceeds)X -1451(the)X -1576(depth)X -1781(of)X -1875(the)X -2000(direc-)X -432 3406(tory.)N -630(The)X -784(following)X -1123(code)X -1303(fragment)X -1621(helps)X -1818(to)X -1908(illustrate)X -432 3494(the)N -554(extendible)X -912(hashing)X -1185(algorithm)X -1520([FAG79])X -1838(for)X -1955(access-)X -432 3582(ing)N -554(individual)X -898(buckets)X -1163(and)X -1299(maintaining)X -1701(the)X -1819(directory.)X -0 f -8 s -432 3881(hash)N -622(=)X -698 -0.4038(calchash\(key\);)AX -432 3969(mask)N -622(=)X -698 -0.4018(maskvec[depth];)AX -432 4145(bucket)N -698(=)X -774 -0.4038(directory[hash)AX -1344(&)X -1420(mask];)X -432 4321(/*)N -546(Key)X -698 -0.4219(Insertion)AX -1078(*/)X -432 4409(if)N -546 -0.4038(\(store\(bucket,)AX -1116(key,)X -1306(data\))X -1534(==)X -1648(FAIL\))X -1876({)X -720 4497(newbl)N -948(=)X -1024 -0.4167(getpage\(\);)AX -720 4585 -0.4000(bucket->depth++;)AN -720 4673 -0.4091(newbl->depth)AN -1214(=)X -1290 -0.4038(bucket->depth;)AX -720 4761(if)N -834 -0.4038(\(bucket->depth)AX -1404(>)X -1480(depth\))X -1746({)X -1008 4849(/*)N -1122(double)X -1388 -0.4219(directory)AX -1768(*/)X -1008 4937(depth++;)N -1 f -16 s -432 5033 MXY -864 0 Dl -2 f -8 s -472 5088(5)N -1 f -9 s -534 5113(This)N -692(decision)X -962(to)X -1048(split)X -1202(the)X -1319(directory)X -1608(is)X -1685(based)X -1878(on)X -1979(a)X -2040(com-)X -432 5193(parison)N -666(of)X -748(the)X -858(depth)X -1040(of)X -1121(the)X -1230(page)X -1387(being)X -1568(split)X -1713(and)X -1838(the)X -1947(depth)X -2128(of)X -432 5273(the)N -543(trie.)X -698(In)X -781(Figure)X -992(2,)X -1069(the)X -1180(depths)X -1390(of)X -1472(both)X -1622(L00)X -1760(and)X -1886(L01)X -2024(are)X -2134(2,)X -432 5353(whereas)N -689(the)X -798(depth)X -979(of)X -1060(L1)X -1161(is)X -1230(1.)X -1323(Therefore,)X -1646(if)X -1710(L1)X -1810(were)X -1970(to)X -2046(split,)X -432 5433(the)N -543(directory)X -826(would)X -1029(not)X -1144(need)X -1303(to)X -1382(split.)X -1565(In)X -1648(reality,)X -1872(a)X -1926(bucket)X -2140(is)X -432 5513(allocated)N -727(for)X -846(the)X -969(directory)X -1264(at)X -1351(the)X -1474(time)X -1637(of)X -1732(\256le)X -1858(creation)X -2124(so)X -432 5593(although)N -707(the)X -818(directory)X -1100(splits)X -1274(logically,)X -1566(physical)X -1828(splits)X -2002(do)X -2096(not)X -432 5673(occur)N -610(until)X -760(the)X -866(\256le)X -976(becomes)X -1246(quite)X -1408(large.)X -0 f -8 s -2994 538 -0.4219(directory)AN -3374(=)X -3450 -0.3971(double\(directory\);)AX -2706 626(})N -2706 714 -0.3958(splitbucket\(bucket,)AN -3466(newbl\))X -2706 802(...)N -2418 890(})N -2 f -10 s -3169 1255(hsearch)N -1 f -2590 1387(Since)N -2 f -2807(hsearch)X -1 f -3100(does)X -3286(not)X -3427(have)X -3617(to)X -3717(translate)X -4027(hash)X -2418 1475(values)N -2659(into)X -2819(disk)X -2988(addresses,)X -3352(it)X -3432(can)X -3579(use)X -3721(much)X -3934(simpler)X -2418 1563(algorithms)N -2808(than)X -2994(those)X -3211(de\256ned)X -3495(above.)X -3775(System)X -4058(V's)X -2 f -2418 1651(hsearch)N -1 f -2708(constructs)X -3069(a)X -3141(\256xed-size)X -3489(hash)X -3671(table)X -3862(\(speci\256ed)X -2418 1739(by)N -2519(the)X -2637(user)X -2791(at)X -2869(table)X -3045(creation\).)X -3391(By)X -3504(default,)X -3767(a)X -3823(multiplica-)X -2418 1827(tive)N -2570(hash)X -2748(function)X -3046(based)X -3260(on)X -3371(that)X -3522(described)X -3861(in)X -3954(Knuth,)X -2418 1915(Volume)N -2710(3,)X -2804(section)X -3065(6.4)X -3199([KNU68])X -3541(is)X -3628(used)X -3809(to)X -3905(obtain)X -4138(a)X -2418 2003(primary)N -2694(bucket)X -2930(address.)X -3233(If)X -3309(this)X -3446(bucket)X -3681(is)X -3755(full,)X -3907(a)X -3964(secon-)X -2418 2091(dary)N -2593(multiplicative)X -3069(hash)X -3248(value)X -3454(is)X -3538(computed)X -3885(to)X -3978(de\256ne)X -2418 2179(the)N -2542(probe)X -2751(interval.)X -3062(The)X -3213(probe)X -3422(interval)X -3693(is)X -3772(added)X -3989(to)X -4076(the)X -2418 2267(original)N -2712(bucket)X -2971(address)X -3257(\(modulo)X -3573(the)X -3716(table)X -3916(size\))X -4112(to)X -2418 2355(obtain)N -2658(a)X -2734(new)X -2908(bucket)X -3162(address.)X -3483(This)X -3665(process)X -3946(repeats)X -2418 2443(until)N -2588(an)X -2688(empty)X -2911(bucket)X -3148(is)X -3224(found.)X -3474(If)X -3551(no)X -3654(bucket)X -3891(is)X -3967(found,)X -2418 2531(an)N -2514(insertion)X -2814(fails)X -2972(with)X -3134(a)X -3190(``table)X -3420(full'')X -3605(condition.)X -2590 2645(The)N -2768(basic)X -2986(algorithm)X -3350(may)X -3541(be)X -3670(modi\256ed)X -4006(by)X -4138(a)X -2418 2733(number)N -2705(of)X -2813(compile)X -3112(time)X -3295(options)X -3571(available)X -3902(to)X -4005(those)X -2418 2821(users)N -2604(with)X -2767(AT&T)X -3006(source)X -3237(code.)X -3450(First,)X -3637(the)X -3756(package)X -4040(pro-)X -2418 2909(vides)N -2638(two)X -2809(options)X -3094(for)X -3238(hash)X -3435(functions.)X -3803(Users)X -4036(may)X -2418 2997(specify)N -2690(their)X -2877(own)X -3055(hash)X -3242(function)X -3549(by)X -3669(compiling)X -4032(with)X -2418 3085(``USCR'')N -2757(de\256ned)X -3016(and)X -3155(declaring)X -3477(and)X -3616(de\256ning)X -3901(the)X -4022(vari-)X -2418 3173(able)N -2 f -2578(hcompar)X -1 f -2863(,)X -2909(a)X -2971(function)X -3263(taking)X -3488(two)X -3633(string)X -3840(arguments)X -2418 3261(and)N -2560(returning)X -2880(an)X -2982(integer.)X -3271(Users)X -3480(may)X -3643(also)X -3797(request)X -4054(that)X -2418 3349(hash)N -2587(values)X -2814(be)X -2912(computed)X -3250(simply)X -3489(by)X -3590(taking)X -3811(the)X -3930(modulo)X -2418 3437(of)N -2521(key)X -2673(\(using)X -2909(division)X -3201(rather)X -3424(than)X -3597(multiplication)X -4080(for)X -2418 3525(hash)N -2589(value)X -2787(calculation\).)X -3230(If)X -3308(this)X -3447(technique)X -3783(is)X -3859(used,)X -4049(col-)X -2418 3613(lisions)N -2651(are)X -2775(resolved)X -3072(by)X -3176(scanning)X -3485(sequentially)X -3896(from)X -4076(the)X -2418 3701(selected)N -2702(bucket)X -2941(\(linear)X -3176(probing\).)X -3517(This)X -3684(option)X -3913(is)X -3991(avail-)X -2418 3789(able)N -2572(by)X -2672(de\256ning)X -2954(the)X -3072(variable)X -3351(``DIV'')X -3622(at)X -3700(compile)X -3978(time.)X -2590 3903(A)N -2720(second)X -3015(option,)X -3311(based)X -3565(on)X -3716(an)X -3863(algorithm)X -2418 3991(discovered)N -2787(by)X -2888(Richard)X -3163(P.)X -3248(Brent,)X -3466(rearranges)X -3822(the)X -3940(table)X -4116(at)X -2418 4079(the)N -2549(time)X -2724(of)X -2824(insertion)X -3137(in)X -3232(order)X -3434(to)X -3528(speed)X -3743(up)X -3855(retrievals.)X -2418 4167(The)N -2571(basic)X -2764(idea)X -2926(is)X -3007(to)X -3097(shorten)X -3361(long)X -3531(probe)X -3741(sequences)X -4094(by)X -2418 4255(lengthening)N -2833(short)X -3030(probe)X -3249(sequences.)X -3651(Once)X -3857(the)X -3991(probe)X -2418 4343(chain)N -2613(has)X -2741(exceeded)X -3062(some)X -3252(threshold)X -3571(\(Brent)X -3796(suggests)X -4087(2\),)X -2418 4431(we)N -2541(attempt)X -2809(to)X -2899(shuf\257e)X -3145(any)X -3289(colliding)X -3601(keys)X -3776(\(keys)X -3978(which)X -2418 4519(appeared)N -2734(in)X -2821(the)X -2944(probe)X -3152(sequence)X -3471(of)X -3562(the)X -3684(new)X -3842(key\).)X -4049(The)X -2418 4607(details)N -2652(of)X -2744(this)X -2884(key)X -3025(shuf\257ing)X -3333(can)X -3469(be)X -3569(found)X -3780(in)X -3866([KNU68])X -2418 4695(and)N -2576([BRE73].)X -2946(This)X -3129(algorithm)X -3481(may)X -3660(be)X -3777(obtained)X -4094(by)X -2418 4783(de\256ning)N -2700(the)X -2818(variable)X -3097(``BRENT'')X -3487(at)X -3565(compile)X -3843(time.)X -2590 4897(A)N -2698(third)X -2899(set)X -3038(of)X -3154(options,)X -3458(obtained)X -3783(by)X -3912(de\256ning)X -2418 4985(``CHAINED'',)N -2943(use)X -3086(linked)X -3321(lists)X -3484(to)X -3581(resolve)X -3848(collisions.)X -2418 5073(Either)N -2647(of)X -2747(the)X -2878(primary)X -3164(hash)X -3343(function)X -3642(described)X -3982(above)X -2418 5161(may)N -2584(be)X -2688(used,)X -2882(but)X -3011(all)X -3118(collisions)X -3451(are)X -3577(resolved)X -3876(by)X -3983(build-)X -2418 5249(ing)N -2554(a)X -2623(linked)X -2856(list)X -2986(of)X -3086(entries)X -3333(from)X -3522(the)X -3653(primary)X -3940(bucket.)X -2418 5337(By)N -2542(default,)X -2816(new)X -2981(entries)X -3226(will)X -3381(be)X -3488(added)X -3711(to)X -3804(a)X -3871(bucket)X -4116(at)X -2418 5425(the)N -2541(beginning)X -2886(of)X -2978(the)X -3101(bucket)X -3339(chain.)X -3577(However,)X -3916(compile)X -2418 5513(options)N -2706(``SORTUP'')X -3173(or)X -3293(``SORTDOWN'')X -3908(may)X -4098(be)X -2418 5601(speci\256ed)N -2723(to)X -2805(order)X -2995(the)X -3113(hash)X -3280(chains)X -3505(within)X -3729(each)X -3897(bucket.)X -3 f -432 5960(4)N -2970(USENIX)X -9 f -3292(-)X -3 f -3356(Winter)X -3621('91)X -9 f -3748(-)X -3 f -3812(Dallas,)X -4065(TX)X - -5 p -%%Page: 5 5 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -720 258(Seltzer)N -977(&)X -1064(Yigit)X -3278(A)X -3356(New)X -3528(Hashing)X -3831(Package)X -4136(for)X -4259(UNIX)X -2 f -1444 538(dynahash)N -1 f -892 670(The)N -2 f -1054(dynahash)X -1 f -1398(library,)X -1669(written)X -1932(by)X -2048(Esmond)X -2346(Pitt,)X -720 758(implements)N -1183(Larson's)X -1554(linear)X -1827(hashing)X -2165(algorithm)X -720 846([LAR88])N -1097(with)X -1302(an)X -2 f -1440(hsearch)X -1 f -1756(compatible)X -2174(interface.)X -720 934(Intuitively,)N -1099(a)X -1161(hash)X -1334(table)X -1516(begins)X -1751(as)X -1844(a)X -1905(single)X -2121(bucket)X -2360(and)X -720 1022(grows)N -941(in)X -1028(generations,)X -1443(where)X -1665(a)X -1725(generation)X -2088(corresponds)X -720 1110(to)N -815(a)X -884(doubling)X -1201(in)X -1296(the)X -1427(size)X -1585(of)X -1685(the)X -1815(hash)X -1994(table.)X -2222(The)X -2379(0)X -2 f -7 s -1078(th)Y -10 s -1 f -720 1198(generation)N -1085(occurs)X -1321(as)X -1414(the)X -1538(table)X -1719(grows)X -1940(from)X -2121(one)X -2262(bucket)X -720 1286(to)N -814(two.)X -1006(In)X -1105(the)X -1235(next)X -1405(generation)X -1776(the)X -1906(table)X -2093(grows)X -2320(from)X -720 1374(two)N -862(to)X -946(four.)X -1122(During)X -1371(each)X -1541(generation,)X -1921(every)X -2121(bucket)X -2356(that)X -720 1462(existed)N -967(at)X -1045(the)X -1163(beginning)X -1503(of)X -1590(the)X -1708(generation)X -2067(is)X -2140(split.)X -892 1576(The)N -1041(table)X -1221(starts)X -1414(as)X -1505(a)X -1565(single)X -1780(bucket)X -2018(\(numbered)X -2389(0\),)X -720 1664(the)N -839(current)X -1088(split)X -1245(bucket)X -1479(is)X -1552(set)X -1661(to)X -1743(bucket)X -1977(0,)X -2057(and)X -2193(the)X -2311(max-)X -720 1752(imum)N -933(split)X -1097(point)X -1288(is)X -1368(set)X -1483(to)X -1571(twice)X -1771(the)X -1895(current)X -2149(split)X -2312(point)X -720 1840(\(0\).)N -863(When)X -1084(it)X -1157(is)X -1239(time)X -1410(for)X -1532(a)X -1596(bucket)X -1838(to)X -1928(split,)X -2113(the)X -2239(keys)X -2414(in)X -720 1928(the)N -872(current)X -1154(split)X -1345(bucket)X -1612(are)X -1764(divided)X -2057(between)X -2378(the)X -720 2016(current)N -981(split)X -1151(bucket)X -1397(and)X -1545(a)X -1613(new)X -1779(bucket)X -2025(whose)X -2262(bucket)X -720 2104(number)N -1000(is)X -1088(equal)X -1297(to)X -1394(1)X -1469(+)X -1549(current)X -1812(split)X -1984(bucket)X -2232(+)X -2311(max-)X -720 2192(imum)N -927(split)X -1085(point.)X -1310(We)X -1442(can)X -1574(determine)X -1915(which)X -2131(keys)X -2298(move)X -720 2280(to)N -807(the)X -929(new)X -1087(bucket)X -1325(by)X -1429(examining)X -1791(the)X -2 f -1913(n)X -7 s -1962 2248(th)N -10 s -1 f -2043 2280(bit)N -2151(of)X -2242(a)X -2302(key's)X -720 2368(hash)N -899(value)X -1105(where)X -1334(n)X -1406(is)X -1491(the)X -1620(generation)X -1990(number.)X -2306(After)X -720 2456(the)N -846(bucket)X -1088(at)X -1174(the)X -1300(maximum)X -1651(split)X -1815(point)X -2006(has)X -2140(been)X -2319(split,)X -720 2544(the)N -839(generation)X -1198(number)X -1463(is)X -1536(incremented,)X -1973(the)X -2091(current)X -2339(split)X -720 2632(point)N -908(is)X -985(set)X -1098(back)X -1274(to)X -1360(zero,)X -1543(and)X -1683(the)X -1805(maximum)X -2152(split)X -2312(point)X -720 2720(is)N -815(set)X -946(to)X -1050(the)X -1190(number)X -1477(of)X -1586(the)X -1725(last)X -1877(bucket)X -2132(in)X -2235(the)X -2374(\256le)X -720 2808(\(which)N -971(is)X -1052(equal)X -1253(to)X -1342(twice)X -1543(the)X -1668(old)X -1797(maximum)X -2148(split)X -2312(point)X -720 2896(plus)N -873(1\).)X -892 3010(To)N -1031(facilitate)X -1361(locating)X -1668(keys,)X -1884(we)X -2027(maintain)X -2356(two)X -720 3098(masks.)N -989(The)X -1143(low)X -1291(mask)X -1488(is)X -1569(equal)X -1771(to)X -1861(the)X -1987(maximum)X -2339(split)X -720 3186(bucket)N -967(and)X -1116(the)X -1247(high)X -1422(mask)X -1624(is)X -1710(equal)X -1917(to)X -2011(the)X -2141(next)X -2311(max-)X -720 3274(imum)N -931(split)X -1093(bucket.)X -1372(To)X -1486(locate)X -1703(a)X -1764(speci\256c)X -2033(key,)X -2193(we)X -2311(com-)X -720 3362(pute)N -881(a)X -940(32-bit)X -1154(hash)X -1324(value)X -1520(using)X -1715(a)X -1773(bit-randomizing)X -2311(algo-)X -720 3450(rithm)N -932(such)X -1118(as)X -1224(the)X -1361(one)X -1516(described)X -1862(in)X -1962([LAR88].)X -2334(This)X -720 3538(hash)N -893(value)X -1093(is)X -1172(then)X -1336(masked)X -1607(with)X -1775(the)X -1898(high)X -2065(mask.)X -2299(If)X -2378(the)X -720 3626(resulting)N -1026(number)X -1297(is)X -1376(greater)X -1626(than)X -1790(the)X -1913(maximum)X -2262(bucket)X -720 3714(in)N -823(the)X -962(table)X -1159(\(current)X -1455(split)X -1633(bucket)X -1888(+)X -1974(maximum)X -2339(split)X -720 3802(point\),)N -962(the)X -1091(hash)X -1269(value)X -1474(is)X -1558(masked)X -1834(with)X -2007(the)X -2136(low)X -2287(mask.)X -720 3890(In)N -825(either)X -1046(case,)X -1242(the)X -1377(result)X -1592(of)X -1696(the)X -1831(mask)X -2037(is)X -2127(the)X -2262(bucket)X -720 3978(number)N -989(for)X -1107(the)X -1229(given)X -1431(key.)X -1611(The)X -1759(algorithm)X -2093(below)X -2312(illus-)X -720 4066(trates)N -914(this)X -1049(process.)X -0 f -8 s -720 4365(h)N -796(=)X -872 -0.4038(calchash\(key\);)AX -720 4453(bucket)N -986(=)X -1062(h)X -1138(&)X -1214 -0.4167(high_mask;)AX -720 4541(if)N -834(\()X -910(bucket)X -1176(>)X -1252 -0.4167(max_bucket)AX -1670(\))X -1008 4629(bucket)N -1274(=)X -1350(h)X -1426(&)X -1502 -0.4219(low_mask;)AX -720 4717 -0.4018(return\(bucket\);)AN -1 f -10 s -892 5042(In)N -1013(order)X -1237(to)X -1353(decide)X -1617(when)X -1845(to)X -1961(split)X -2152(a)X -2242(bucket,)X -2 f -720 5130(dynahash)N -1 f -1050(uses)X -2 f -1210(controlled)X -1561(splitting)X -1 f -1822(.)X -1884(A)X -1964(hash)X -2133(table)X -2311(has)X -2440(a)X -720 5218(\256ll)N -837(factor)X -1054(which)X -1279(is)X -1361(expressed)X -1707(in)X -1798(terms)X -2004(of)X -2099(the)X -2225(average)X -720 5306(number)N -990(of)X -1082(keys)X -1253(in)X -1339(each)X -1511(bucket.)X -1789(Each)X -1974(time)X -2140(the)X -2262(table's)X -720 5394(total)N -885(number)X -1153(of)X -1243(keys)X -1413(divided)X -1676(by)X -1778(its)X -1875(number)X -2142(of)X -2231(buckets)X -720 5482(exceeds)N -995(this)X -1130(\256ll)X -1238(factor,)X -1466(a)X -1522(bucket)X -1756(is)X -1829(split.)X -2878 538(Since)N -3079(the)X -2 f -3200(hsearch)X -1 f -3477(create)X -3693(interface)X -3998(\()X -2 f -4025(hcreate)X -1 f -4266(\))X -4315(calls)X -2706 626(for)N -2842(an)X -2960(estimate)X -3269(of)X -3378(the)X -3518(\256nal)X -3702(size)X -3869(of)X -3978(the)X -4118(hash)X -4306(table)X -2706 714(\()N -2 f -2733(nelem)X -1 f -2925(\),)X -2 f -3007(dynahash)X -1 f -3349(uses)X -3522(this)X -3672(information)X -4085(to)X -4182(initialize)X -2706 802(the)N -2848(table.)X -3088(The)X -3257(initial)X -3486(number)X -3774(of)X -3884(buckets)X -4172(is)X -4268(set)X -4400(to)X -2 f -2706 890(nelem)N -1 f -2926(rounded)X -3217(to)X -3306(the)X -3431(next)X -3596(higher)X -3828(power)X -4056(of)X -4150(two.)X -4337(The)X -2706 978(current)N -2958(split)X -3118(point)X -3305(is)X -3381(set)X -3493(to)X -3578(0)X -3641(and)X -3780(the)X -3901(maximum)X -4248(bucket)X -2706 1066(and)N -2842(maximum)X -3186(split)X -3343(point)X -3527(are)X -3646(set)X -3755(to)X -3837(this)X -3972(rounded)X -4255(value.)X -3 f -3148 1220(The)N -3301(New)X -3473(Implementation)X -1 f -2878 1352(Our)N -3042(implementation)X -3583(is)X -3675(also)X -3842(based)X -4063(on)X -4181(Larson's)X -2706 1440(linear)N -2939(hashing)X -3238([LAR88])X -3582(algorithm)X -3943(as)X -4060(well)X -4248(as)X -4364(the)X -2 f -2706 1528(dynahash)N -1 f -3047(implementation.)X -3623(The)X -2 f -3782(dbm)X -1 f -3954(family)X -4197(of)X -4297(algo-)X -2706 1616(rithms)N -2942(decide)X -3184(dynamically)X -3612(which)X -3840(bucket)X -4085(to)X -4178(split)X -4346(and)X -2706 1704(when)N -2914(to)X -3010(split)X -3180(it)X -3257(\(when)X -3491(it)X -3568(over\257ows\))X -3944(while)X -2 f -4155(dynahash)X -1 f -2706 1792(splits)N -2933(in)X -3054(a)X -3149(prede\256ned)X -3547(order)X -3776(\(linearly\))X -4134(and)X -4309(at)X -4426(a)X -2706 1880(prede\256ned)N -3116(time)X -3328(\(when)X -3599(the)X -3767(table)X -3993(\256ll)X -4151(factor)X -4409(is)X -2706 1968(exceeded\).)N -3121(We)X -3280(use)X -3434(a)X -3517(hybrid)X -3773(of)X -3887(these)X -4099(techniques.)X -2706 2056(Splits)N -2913(occur)X -3118(in)X -3206(the)X -3330(prede\256ned)X -3695(order)X -3891(of)X -3984(linear)X -4193(hashing,)X -2706 2144(but)N -2845(the)X -2980(time)X -3159(at)X -3253(which)X -3485(pages)X -3704(are)X -3839(split)X -4012(is)X -4101(determined)X -2706 2232(both)N -2869(by)X -2970(page)X -3143(over\257ows)X -3480(\()X -2 f -3507(uncontrolled)X -3937(splitting)X -1 f -4198(\))X -4246(and)X -4382(by)X -2706 2320(exceeding)N -3052(the)X -3170(\256ll)X -3278(factor)X -3486(\()X -2 f -3513(controlled)X -3862(splitting)X -1 f -4123(\))X -2878 2434(A)N -2962(hash)X -3135(table)X -3317(is)X -3395(parameterized)X -3876(by)X -3981(both)X -4148(its)X -4248(bucket)X -2706 2522(size)N -2904(\()X -2 f -2931(bsize)X -1 f -(\))S -3191(and)X -3380(\256ll)X -3541(factor)X -3801(\()X -2 f -3828(ffactor)X -1 f -4041(\).)X -4180(Whereas)X -2 f -2706 2610(dynahash's)N -1 f -3095(buckets)X -3364(can)X -3500(be)X -3599(represented)X -3993(as)X -4083(a)X -4142(linked)X -4365(list)X -2706 2698(of)N -2798(elements)X -3108(in)X -3195(memory,)X -3507(our)X -3639(package)X -3928(needs)X -4136(to)X -4222(support)X -2706 2786(disk)N -2874(access,)X -3135(and)X -3286(must)X -3476(represent)X -3806(buckets)X -4086(in)X -4183(terms)X -4395(of)X -2706 2874(pages.)N -2955(The)X -2 f -3106(bsize)X -1 f -3291(is)X -3369(the)X -3492(size)X -3642(\(in)X -3756(bytes\))X -3977(of)X -4069(these)X -4259(pages.)X -2706 2962(As)N -2833(in)X -2933(linear)X -3154(hashing,)X -3461(the)X -3597(number)X -3879(of)X -3983(buckets)X -4265(in)X -4364(the)X -2706 3050(table)N -2906(is)X -3003(equal)X -3221(to)X -3327(the)X -3469(number)X -3758(of)X -3869(keys)X -4060(in)X -4165(the)X -4306(table)X -2706 3138(divided)N -2988(by)X -2 f -3110(ffactor)X -1 f -3323(.)X -2 f -8 s -3113(6)Y -1 f -10 s -3417 3138(The)N -3584(controlled)X -3950(splitting)X -4252(occurs)X -2706 3226(each)N -2878(time)X -3044(the)X -3166(number)X -3435(of)X -3526(keys)X -3697(in)X -3783(the)X -3905(table)X -4085(exceeds)X -4364(the)X -2706 3314(\256ll)N -2814(factor)X -3022(multiplied)X -3370(by)X -3470(the)X -3588(number)X -3853(of)X -3940(buckets.)X -2878 3428(Inserting)N -3187(keys)X -3358(and)X -3498(splitting)X -3783(buckets)X -4051(is)X -4127(performed)X -2706 3516(precisely)N -3018(as)X -3107(described)X -3437(previously)X -3796(for)X -2 f -3911(dynahash)X -1 f -4218(.)X -4279(How-)X -2706 3604(ever,)N -2897(since)X -3094(buckets)X -3371(are)X -3502(now)X -3671(comprised)X -4036(of)X -4134(pages,)X -4368(we)X -2706 3692(must)N -2883(be)X -2981(prepared)X -3284(to)X -3367(handle)X -3602(cases)X -3793(where)X -4011(the)X -4130(size)X -4276(of)X -4364(the)X -2706 3780(keys)N -2873(and)X -3009(data)X -3163(in)X -3245(a)X -3301(bucket)X -3535(exceed)X -3779(the)X -3897(bucket)X -4131(size.)X -3 f -3318 3934(Over\257ow)N -3654(Pages)X -1 f -2878 4066(There)N -3095(are)X -3223(two)X -3372(cases)X -3571(where)X -3797(a)X -3862(key)X -4007(may)X -4174(not)X -4305(\256t)X -4400(in)X -2706 4154(its)N -2802(designated)X -3166(bucket.)X -3441(In)X -3529(the)X -3647(\256rst)X -3791(case,)X -3970(the)X -4088(total)X -4250(size)X -4395(of)X -2706 4242(the)N -2833(key)X -2978(and)X -3123(data)X -3286(may)X -3453(exceed)X -3706(the)X -3833(bucket)X -4076(size.)X -4269(In)X -4364(the)X -2706 4330(second,)N -3008(addition)X -3328(of)X -3453(a)X -3547(new)X -3739(key)X -3913(could)X -4149(cause)X -4386(an)X -2706 4418(over\257ow,)N -3068(but)X -3227(the)X -3382(bucket)X -3652(in)X -3770(question)X -4097(is)X -4206(not)X -4364(yet)X -2706 4506(scheduled)N -3049(to)X -3133(be)X -3230(split.)X -3428(In)X -3516(existing)X -3790(implementations,)X -4364(the)X -2706 4594(second)N -2953(case)X -3115(never)X -3317(arises)X -3523(\(since)X -3738(buckets)X -4006(are)X -4128(split)X -4288(when)X -2706 4682(they)N -2871(over\257ow\))X -3210(and)X -3352(the)X -3476(\256rst)X -3626(case)X -3791(is)X -3870(not)X -3998(handled)X -4278(at)X -4362(all.)X -2706 4770(Although)N -3036(large)X -3225(key/data)X -3525(pair)X -3678(handling)X -3986(is)X -4066(dif\256cult)X -4346(and)X -2706 4858(expensive,)N -3083(it)X -3163(is)X -3252(essential.)X -3604(In)X -3706(a)X -3777(linear)X -3995(hashed)X -4253(imple-)X -2706 4946(mentation,)N -3087(over\257ow)X -3413(pages)X -3636(are)X -3775(required)X -4083(for)X -4217(buckets)X -2706 5034(which)N -2935(over\257ow)X -3253(before)X -3492(they)X -3662(are)X -3793(split,)X -3982(so)X -4085(we)X -4211(can)X -4355(use)X -2706 5122(the)N -2833(same)X -3027(mechanism)X -3421(for)X -3544(large)X -3734(key/data)X -4035(pairs)X -4220(that)X -4368(we)X -2706 5210(use)N -2837(for)X -2955(over\257ow)X -3264(pages.)X -3511(Logically,)X -3862(we)X -3980(chain)X -4177(over\257ow)X -16 s -2706 5353 MXY -864 0 Dl -2 f -8 s -2746 5408(6)N -1 f -9 s -2801 5433(This)N -2952(is)X -3023(not)X -3138(strictly)X -3361(true.)X -3532(The)X -3667(\256le)X -3782(does)X -3937(not)X -4052(contract)X -4306(when)X -2706 5513(keys)N -2861(are)X -2972(deleted,)X -3221(so)X -3308(the)X -3419(number)X -3662(of)X -3744(buckets)X -3986(is)X -4056(actually)X -4306(equal)X -2706 5593(to)N -2782(the)X -2890(maximum)X -3202(number)X -3441(of)X -3520(keys)X -3671(ever)X -3814(present)X -4041(in)X -4116(the)X -4223(table)X -4382(di-)X -2706 5673(vided)N -2884(by)X -2974(the)X -3080(\256ll)X -3178(factor.)X -3 f -10 s -720 5960(USENIX)N -9 f -1042(-)X -3 f -1106(Winter)X -1371('91)X -9 f -1498(-)X -3 f -1562(Dallas,)X -1815(TX)X -4424(5)X - -6 p -%%Page: 6 6 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -432 258(A)N -510(New)X -682(Hashing)X -985(Package)X -1290(for)X -1413(UNIX)X -3663(Seltzer)X -3920(&)X -4007(Yigit)X -1 f -432 538(pages)N -639(to)X -725(the)X -847(buckets)X -1116(\(also)X -1296(called)X -1512(primary)X -1789(pages\).)X -2062(In)X -2152(a)X -432 626(memory)N -730(based)X -943(representation,)X -1448(over\257ow)X -1763(pages)X -1976(do)X -2086(not)X -432 714(pose)N -628(any)X -792(special)X -1063(problems)X -1409(because)X -1712(we)X -1854(can)X -2014(chain)X -432 802(over\257ow)N -776(pages)X -1017(to)X -1137(primary)X -1449(pages)X -1690(using)X -1921(memory)X -432 890(pointers.)N -776(However,)X -1137(mapping)X -1463(these)X -1674(over\257ow)X -2005(pages)X -432 978(into)N -584(a)X -648(disk)X -809(\256le)X -939(is)X -1019(more)X -1211(of)X -1305(a)X -1368(challenge,)X -1723(since)X -1915(we)X -2036(need)X -432 1066(to)N -547(be)X -675(able)X -861(to)X -975(address)X -1268(both)X -1462(bucket)X -1728(pages,)X -1983(whose)X -432 1154(numbers)N -729(are)X -849(growing)X -1137(linearly,)X -1422(and)X -1558(some)X -1747(indeterminate)X -432 1242(number)N -715(of)X -820(over\257ow)X -1143(pages)X -1364(without)X -1646(reorganizing)X -2090(the)X -432 1330(\256le.)N -604 1444(One)N -789(simple)X -1053(solution)X -1361(would)X -1612(be)X -1739(to)X -1852(allocate)X -2152(a)X -432 1532(separate)N -737(\256le)X -880(for)X -1015(over\257ow)X -1341(pages.)X -1604(The)X -1769(disadvantage)X -432 1620(with)N -605(such)X -783(a)X -850(technique)X -1193(is)X -1276(that)X -1426(it)X -1500(requires)X -1789(an)X -1895(extra)X -2086(\256le)X -432 1708(descriptor,)N -794(an)X -891(extra)X -1073(system)X -1316(call)X -1453(on)X -1554(open)X -1731(and)X -1867(close,)X -2072(and)X -432 1796(logically)N -739(associating)X -1122(two)X -1269(independent)X -1687(\256les.)X -1886(For)X -2023(these)X -432 1884(reasons,)N -728(we)X -857(wanted)X -1123(to)X -1219(map)X -1391(both)X -1567(primary)X -1855(pages)X -2072(and)X -432 1972(over\257ow)N -737(pages)X -940(into)X -1084(the)X -1202(same)X -1387(\256le)X -1509(space.)X -604 2086(The)N -799(buddy-in-waiting)X -1425(algorithm)X -1806(provides)X -2152(a)X -432 2174(mechanism)N -851(to)X -966(support)X -1259(multiple)X -1578(pages)X -1814(per)X -1970(logical)X -432 2262(bucket)N -685(while)X -902(retaining)X -1226(the)X -1362(simple)X -1613(split)X -1788(sequence)X -2121(of)X -432 2350(linear)N -681(hashing.)X -1015(Over\257ow)X -1383(pages)X -1631(are)X -1795(preallocated)X -432 2438(between)N -781(generations)X -1232(of)X -1379(primary)X -1713(pages.)X -1996(These)X -432 2526(over\257ow)N -759(pages)X -984(are)X -1125(used)X -1314(by)X -1436(any)X -1594(bucket)X -1850(containing)X -432 2614(more)N -646(keys)X -842(than)X -1029(\256t)X -1144(on)X -1273(the)X -1420(primary)X -1723(page)X -1924(and)X -2089(are)X -432 2702(reclaimed,)N -808(if)X -896(possible,)X -1217(when)X -1430(the)X -1567(bucket)X -1819(later)X -2000(splits.)X -432 2790(Figure)N -687(3)X -773(depicts)X -1045(the)X -1188(layout)X -1433(of)X -1545(primary)X -1844(pages)X -2072(and)X -432 2878(over\257ow)N -752(pages)X -970(within)X -1209(the)X -1342(same)X -1542(\256le.)X -1699(Over\257ow)X -2036(page)X -432 2966(use)N -586(information)X -1011(is)X -1111(recorded)X -1440(in)X -1548(bitmaps)X -1847(which)X -2089(are)X -432 3054(themselves)N -819(stored)X -1046(on)X -1157(over\257ow)X -1472(pages.)X -1725(The)X -1880(addresses)X -432 3142(of)N -520(the)X -639(bitmap)X -882(pages)X -1086(and)X -1223(the)X -1342(number)X -1608(of)X -1695(pages)X -1898(allocated)X -432 3230(at)N -515(each)X -688(split)X -850(point)X -1039(are)X -1163(stored)X -1384(in)X -1470(the)X -1592(\256le)X -1718(header.)X -1997(Using)X -432 3318(this)N -577(information,)X -1005(both)X -1177(over\257ow)X -1492(addresses)X -1829(and)X -1974(bucket)X -432 3406(addresses)N -764(can)X -900(be)X -999(mapped)X -1276(to)X -1361(disk)X -1517(addresses)X -1848(by)X -1951(the)X -2072(fol-)X -432 3494(lowing)N -674(calculation:)X -0 f -8 s -432 3793(int)N -736(bucket;)X -1192(/*)X -1306(bucket)X -1572(address)X -1876(*/)X -432 3881(u_short)N -736(oaddr;)X -1192(/*)X -1306(OVERFLOW)X -1648(address)X -1952(*/)X -432 3969(int)N -736 -0.4125(nhdr_pages;)AX -1192(/*)X -1306(npages)X -1572(in)X -1686 -112.4062(\256le)AX -1838(header)X -2104(*/)X -432 4057(int)N -736 -0.4125(spares[32];)AX -1192(/*)X -1306(npages)X -1572(at)X -1686(each)X -1876(split)X -2104(*/)X -432 4145(int)N -736(log2\(\);)X -1198(/*)X -1312(ceil\(log)X -1654(base)X -1844(2\))X -1958(*/)X -432 4321(#DEFINE)N -736 -0.3929(BUCKET_TO_PAGE\(bucket\))AX -1610(\\)X -584 4409(bucket)N -850(+)X -926 -0.4167(nhdr_pages)AX -1344(+)X -1420(\\)X -584 4497 -0.3894(\(bucket?spares[logs2\(bucket)AN -1648(+)X -1724(1\)-1]:0\))X -432 4673(#DEFINE)N -736 -0.3947(OADDR_TO_PAGE\(oaddr\))AX -1534(\\)X -584 4761 -0.3984(BUCKET_TO_PAGE\(\(1)AN -1268(<<)X -1382 -0.4091(\(oaddr>>11\)\))AX -1876(-)X -1952(1\))X -2066(+)X -2142(\\)X -584 4849(oaddr)N -812(&)X -888(0x7ff;)X -1 f -10 s -604 5262(An)N -728(over\257ow)X -1039(page)X -1217(is)X -1295(addressed)X -1637(by)X -1742(its)X -1842(split)X -2004(point,)X -432 5350(identifying)N -858(the)X -1031(generations)X -1476(between)X -1819(which)X -2090(the)X -432 5438(over\257ow)N -740(page)X -915(is)X -991(allocated,)X -1324(and)X -1463(its)X -1561(page)X -1736(number,)X -2023(iden-)X -432 5526(tifying)N -665(the)X -783(particular)X -1111(page)X -1283(within)X -1507(the)X -1625(split)X -1782(point.)X -1986(In)X -2073(this)X -432 5614(implementation,)N -983(offsets)X -1225(within)X -1457(pages)X -1668(are)X -1795(16)X -1903(bits)X -2046(long)X -432 5702(\(limiting)N -732(the)X -851(maximum)X -1196(page)X -1368(size)X -1513(to)X -1595(32K\),)X -1800(so)X -1891(we)X -2005(select)X -2418 538(an)N -2535(over\257ow)X -2860(page)X -3052(addressing)X -3435(algorithm)X -3786(that)X -3946(can)X -4098(be)X -2418 626(expressed)N -2760(in)X -2847(16)X -2952(bits)X -3091(and)X -3231(which)X -3451(allows)X -3684(quick)X -3886(retrieval.)X -2418 714(The)N -2568(top)X -2695(\256ve)X -2840(bits)X -2980(indicate)X -3258(the)X -3380(split)X -3541(point)X -3729(and)X -3869(the)X -3991(lower)X -2418 802(eleven)N -2650(indicate)X -2926(the)X -3046(page)X -3220(number)X -3487(within)X -3713(the)X -3832(split)X -3990(point.)X -2418 890(Since)N -2633(\256ve)X -2789(bits)X -2940(are)X -3075(reserved)X -3384(for)X -3514(the)X -3648(split)X -3821(point,)X -4041(\256les)X -2418 978(may)N -2578(split)X -2737(32)X -2839(times)X -3034(yielding)X -3318(a)X -3376(maximum)X -3721(\256le)X -3844(size)X -3990(of)X -4078(2)X -7 s -946(32)Y -10 s -2418 1066(buckets)N -2698(and)X -2849(32)X -2 f -(*)S -1 f -2982(2)X -7 s -1034(11)Y -10 s -3113 1066(over\257ow)N -3433(pages.)X -3691(The)X -3850(maximum)X -2418 1154(page)N -2597(size)X -2749(is)X -2829(2)X -7 s -1122(15)Y -10 s -1154(,)Y -2971(yielding)X -3259(a)X -3321(maximum)X -3671(\256le)X -3799(size)X -3950(greater)X -2418 1242(than)N -2601(131,000)X -2906(GB)X -3061(\(on)X -3212(\256le)X -3358(systems)X -3655(supporting)X -4041(\256les)X -2418 1330(larger)N -2626(than)X -2784(4GB\).)X -10 f -2418 1418 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -1 Dt -4014 2275 MXY -0 133 Dl -3881 2275 MXY -0 133 Dl -3748 2275 MXY -0 133 Dl -3083 2275 MXY -0 133 Dl -5 s -1 f -3523 2475(2/3)N -3390(2/2)X -3257(2/1)X -2859(1/2)X -2726(1/1)X -5 Dt -3814 1743 MXY -0 133 Dl -3282 1743 MXY -0 133 Dl -3017 1743 MXY -0 133 Dl -2884 1743 MXY -0 133 Dl -1 Dt -3681 1743 MXY -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3548 MX -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3415 MX -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3282 MX -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3150 MX -0 133 Dl -132 0 Dl -0 -133 Dl --132 0 Dl -3017 MX -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -2884 MX -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3 f -8 s -3017 2601(Over\257ow)N -3285(Addresses)X -3515 2833(Over\257ow)N -3783(Pages)X -2850(Buckets)X -1 Di -3349 2740 MXY - 3349 2740 lineto - 3482 2740 lineto - 3482 2873 lineto - 3349 2873 lineto - 3349 2740 lineto -closepath 3 3349 2740 3482 2873 Dp -2684 MX -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -5 Dt -4146 2275 MXY -0 133 Dl -3216 2275 MXY -0 133 Dl -2684 2275 MXY -0 133 Dl -2551 2275 MXY -0 133 Dl -1 f -3798 1963(3)N -3266 1980(2)N -3001(1)X -2868(0)X -1 Dt -2751 1743 MXY -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3548 2275 MXY --15 -22 Dl -2 16 Dl --13 11 Dl -26 -5 Dl --282 -117 Dl -3432 2275 MXY --10 -25 Dl --2 16 Dl --15 8 Dl -27 1 Dl --166 -117 Dl -3282 2275 MXY -12 -25 Dl --14 10 Dl --15 -6 Dl -17 21 Dl --16 -117 Dl -2884 2275 MXY -26 7 Dl --12 -12 Dl -3 -16 Dl --17 21 Dl -382 -117 Dl -2751 2275 MXY -25 9 Dl --11 -12 Dl -5 -17 Dl --19 20 Dl -515 -117 Dl -3 f -3070 2152(Over\257ow)N -3338(Pages)X -3482 2275 MXY - 3482 2275 lineto - 3615 2275 lineto - 3615 2408 lineto - 3482 2408 lineto - 3482 2275 lineto -closepath 3 3482 2275 3615 2408 Dp -3349 MX - 3349 2275 lineto - 3482 2275 lineto - 3482 2408 lineto - 3349 2408 lineto - 3349 2275 lineto -closepath 3 3349 2275 3482 2408 Dp -3216 MX - 3216 2275 lineto - 3349 2275 lineto - 3349 2408 lineto - 3216 2408 lineto - 3216 2275 lineto -closepath 3 3216 2275 3349 2408 Dp -2817 MX - 2817 2275 lineto - 2950 2275 lineto - 2950 2408 lineto - 2817 2408 lineto - 2817 2275 lineto -closepath 3 2817 2275 2950 2408 Dp -2684 MX - 2684 2275 lineto - 2817 2275 lineto - 2817 2408 lineto - 2684 2408 lineto - 2684 2275 lineto -closepath 3 2684 2275 2817 2408 Dp -3615 MX -0 133 Dl -531 0 Dl -0 -133 Dl --531 0 Dl -2950 MX -0 133 Dl -266 0 Dl -0 -133 Dl --266 0 Dl -2551 MX -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3798 1726 MXY --21 -18 Dl -6 16 Dl --10 13 Dl -25 -11 Dl --599 -99 Dl -3266 1726 MXY --1 -27 Dl --7 15 Dl --17 1 Dl -25 11 Dl --67 -99 Dl -3033 1726 MXY -27 1 Dl --14 -8 Dl --1 -17 Dl --12 24 Dl -166 -99 Dl -2900 1726 MXY -27 7 Dl --13 -11 Dl -3 -17 Dl --17 21 Dl -299 -99 Dl -3058 1621(Split)N -3203(Points)X -2418 2275 MXY -0 133 Dl -133 0 Dl -0 -133 Dl --133 0 Dl -3 Dt --1 Ds -3137(Figure)Y -2619(3:)X -1 f -2691(Split)X -2832(points)X -3008(occur)X -3168(between)X -3399(generations)X -3712(and)X -3823(are)X -3919(numbered)X -2418 3225(from)N -2560(0.)X -2642(In)X -2713(this)X -2824(\256gure)X -2991(there)X -3136(are)X -3231(two)X -3345(over\257ow)X -3590(pages)X -3753(allocated)X -4000(at)X -4063(split)X -2418 3313(point)N -2566(1)X -2614(and)X -2722(three)X -2865(allocated)X -3111(at)X -3173(split)X -3300(point)X -3448(2.)X -10 s -10 f -2418 3489 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -2949 3731(Buffer)N -3192(Management)X -1 f -2590 3863(The)N -2744(hash)X -2920(table)X -3105(is)X -3187(stored)X -3412(in)X -3502(memory)X -3797(as)X -3892(a)X -3956(logical)X -2418 3951(array)N -2633(of)X -2749(bucket)X -3012(pointers.)X -3359(Physically,)X -3761(the)X -3907(array)X -4121(is)X -2418 4039(arranged)N -2728(in)X -2818(segments)X -3144(of)X -3239(256)X -3387(pointers.)X -3713(Initially,)X -4013(there)X -2418 4127(is)N -2530(space)X -2767(to)X -2887(allocate)X -3195(256)X -3373(segments.)X -3769(Reallocation)X -2418 4215(occurs)N -2651(when)X -2847(the)X -2967(number)X -3234(of)X -3323(buckets)X -3590(exceeds)X -3867(32K)X -4027(\(256)X -2418 4303(*)N -2508(256\).)X -2745(Primary)X -3053(pages)X -3286(may)X -3473(be)X -3598(accessed)X -3929(directly)X -2418 4391(through)N -2711(the)X -2853(array)X -3062(by)X -3185(bucket)X -3442(number)X -3730(and)X -3889(over\257ow)X -2418 4479(pages)N -2628(are)X -2754 0.4028(referenced)AX -3122(logically)X -3429(by)X -3536(their)X -3710(over\257ow)X -4022(page)X -2418 4567(address.)N -2726(For)X -2864(small)X -3063(hash)X -3236(tables,)X -3469(it)X -3539(is)X -3618(desirable)X -3934(to)X -4022(keep)X -2418 4655(all)N -2525(pages)X -2735(in)X -2823(main)X -3009(memory)X -3302(while)X -3506(on)X -3612(larger)X -3826(tables,)X -4059(this)X -2418 4743(is)N -2523(probably)X -2860(impossible.)X -3298(To)X -3438(satisfy)X -3698(both)X -3891(of)X -4009(these)X -2418 4831(requirements,)N -2900(the)X -3041(package)X -3348(includes)X -3658(buffer)X -3897(manage-)X -2418 4919(ment)N -2598(with)X -2760(LRU)X -2940(\(least)X -3134(recently)X -3413(used\))X -3607(replacement.)X -2590 5033(By)N -2730(default,)X -3020(the)X -3165(package)X -3475(allocates)X -3802(up)X -3928(to)X -4036(64K)X -2418 5121(bytes)N -2616(of)X -2712(buffered)X -3014(pages.)X -3246(All)X -3377(pages)X -3589(in)X -3680(the)X -3807(buffer)X -4032(pool)X -2418 5209(are)N -2542(linked)X -2766(in)X -2852(LRU)X -3036(order)X -3230(to)X -3316(facilitate)X -3621(fast)X -3761(replacement.)X -2418 5297(Whereas)N -2724(ef\256cient)X -3011(access)X -3241(to)X -3327(primary)X -3605(pages)X -3812(is)X -3889(provided)X -2418 5385(by)N -2521(the)X -2642(bucket)X -2879(array,)X -3087(ef\256cient)X -3372(access)X -3600(to)X -3684(over\257ow)X -3991(pages)X -2418 5473(is)N -2501(provided)X -2816(by)X -2926(linking)X -3182(over\257ow)X -3497(page)X -3679(buffers)X -3936(to)X -4027(their)X -2418 5561(predecessor)N -2827(page)X -3008(\(either)X -3247(the)X -3374(primary)X -3657(page)X -3838(or)X -3933(another)X -2418 5649(over\257ow)N -2742(page\).)X -3000(This)X -3181(means)X -3425(that)X -3584(an)X -3699(over\257ow)X -4022(page)X -3 f -432 5960(6)N -2970(USENIX)X -9 f -3292(-)X -3 f -3356(Winter)X -3621('91)X -9 f -3748(-)X -3 f -3812(Dallas,)X -4065(TX)X - -7 p -%%Page: 7 7 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -720 258(Seltzer)N -977(&)X -1064(Yigit)X -3278(A)X -3356(New)X -3528(Hashing)X -3831(Package)X -4136(for)X -4259(UNIX)X -1 f -720 538(cannot)N -955(be)X -1052(present)X -1305(in)X -1388(the)X -1507(buffer)X -1724(pool)X -1886(if)X -1955(its)X -2050(primary)X -2324(page)X -720 626(is)N -804(not)X -937(present.)X -1240(This)X -1413(does)X -1591(not)X -1724(impact)X -1972(performance)X -2409(or)X -720 714(functionality,)N -1209(because)X -1524(an)X -1660(over\257ow)X -2005(page)X -2217(will)X -2400(be)X -720 802(accessed)N -1048(only)X -1236(after)X -1430(its)X -1550(predecessor)X -1975(page)X -2172(has)X -2324(been)X -720 890(accessed.)N -1068(Figure)X -1303(4)X -1369(depicts)X -1622(the)X -1746(data)X -1905(structures)X -2242(used)X -2414(to)X -720 978(manage)N -990(the)X -1108(buffer)X -1325(pool.)X -892 1092(The)N -1040(in-memory)X -1419(bucket)X -1656(array)X -1845(contains)X -2134(pointers)X -2414(to)X -720 1180(buffer)N -975(header)X -1248(structures)X -1617(which)X -1870(represent)X -2222(primary)X -720 1268(pages.)N -968(Buffer)X -1203(headers)X -1474(contain)X -1735(modi\256ed)X -2043(bits,)X -2202(the)X -2324(page)X -720 1356(address)N -995(of)X -1096(the)X -1228(buffer,)X -1479(a)X -1548(pointer)X -1808(to)X -1903(the)X -2034(actual)X -2259(buffer,)X -720 1444(and)N -875(a)X -950(pointer)X -1216(to)X -1317(the)X -1454(buffer)X -1690(header)X -1944(for)X -2077(an)X -2191(over\257ow)X -720 1532(page)N -901(if)X -979(it)X -1052(exists,)X -1283(in)X -1374(addition)X -1665(to)X -1756(the)X -1883(LRU)X -2072(links.)X -2296(If)X -2378(the)X -720 1620(buffer)N -950(corresponding)X -1442(to)X -1537(a)X -1606(particular)X -1947(bucket)X -2194(is)X -2280(not)X -2414(in)X -720 1708(memory,)N -1048(its)X -1164(pointer)X -1432(is)X -1526(NULL.)X -1801(In)X -1909(effect,)X -2154(pages)X -2377(are)X -720 1796(linked)N -950(in)X -1042(three)X -1233(ways.)X -1468(Using)X -1689(the)X -1817(buffer)X -2043(headers,)X -2338(they)X -720 1884(are)N -851(linked)X -1083(physically)X -1444(through)X -1725(the)X -1854(LRU)X -2045(links)X -2231(and)X -2378(the)X -720 1972(over\257ow)N -1036(links.)X -1241(Using)X -1462(the)X -1590(pages)X -1803(themselves,)X -2209(they)X -2377(are)X -720 2060(linked)N -943(logically)X -1246(through)X -1518(the)X -1639(over\257ow)X -1946(addresses)X -2276(on)X -2378(the)X -720 2148(page.)N -948(Since)X -1162(over\257ow)X -1482(pages)X -1700(are)X -1834(accessed)X -2151(only)X -2328(after)X -720 2236(their)N -904(predecessor)X -1321(pages,)X -1560(they)X -1734(are)X -1869(removed)X -2186(from)X -2378(the)X -720 2324(buffer)N -937(pool)X -1099(when)X -1293(their)X -1460(primary)X -1734(is)X -1807(removed.)X -10 f -720 2412 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -1 Dt -2309 3177 MXY -24 15 Dl --8 -15 Dl -8 -15 Dl --24 15 Dl -52 0 Dl -789 3160 MXY --35 0 Dl -0 -156 Dl -1607 0 Dl -0 173 Dl -789 3091 MXY --24 -15 Dl -9 15 Dl --9 15 Dl -24 -15 Dl --69 0 Dl -2309 3125 MXY -104 0 Dl -0 -155 Dl --1693 0 Dl -0 121 Dl -927 3160 MXY -24 15 Dl --9 -15 Dl -9 -15 Dl --24 15 Dl -553 0 Dl -1618 3177 MXY -8 27 Dl -4 -17 Dl -16 -6 Dl --28 -4 Dl -138 121 Dl -1895 3315 MXY -28 3 Dl --15 -9 Dl -1 -18 Dl --14 24 Dl -276 -138 Dl -3108 MY --28 -3 Dl -15 10 Dl --1 17 Dl -14 -24 Dl --276 138 Dl -1756 3229 MXY --8 -27 Dl --3 17 Dl --16 6 Dl -27 4 Dl --138 -121 Dl -1480 MX --24 -15 Dl -9 15 Dl --9 15 Dl -24 -15 Dl --553 0 Dl -3 f -5 s -1083 3073(LRU)N -1178(chain)X -4 Ds -1402 3851 MXY - 1402 3851 lineto - 1471 3851 lineto - 1471 3920 lineto - 1402 3920 lineto - 1402 3851 lineto -closepath 19 1402 3851 1471 3920 Dp -1445 3747(Over\257ow)N -1613(Address)X -1549 3609 MXY -0 69 Dl -1756 MX --23 -15 Dl -8 15 Dl --8 15 Dl -23 -15 Dl --207 0 Dl --1 Ds -3 Dt -1756 3419 MXY --6 -28 Dl --4 17 Dl --17 5 Dl -27 6 Dl --138 -138 Dl -2240 3471 MXY -15 -24 Dl --15 9 Dl --15 -9 Dl -15 24 Dl -0 -138 Dl -1826 3609 MXY -15 -24 Dl --15 9 Dl --16 -9 Dl -16 24 Dl -0 -138 Dl -1549 MX -15 -24 Dl --15 9 Dl --15 -9 Dl -15 24 Dl -0 -138 Dl -858 3471 MXY -15 -24 Dl --15 9 Dl --15 -9 Dl -15 24 Dl -0 -138 Dl -2240 3056 MXY -15 -24 Dl --15 9 Dl --15 -9 Dl -15 24 Dl -0 -138 Dl -1549 3056 MXY -15 -24 Dl --15 9 Dl --15 -9 Dl -15 24 Dl -0 -138 Dl -858 3056 MXY -15 -24 Dl --15 9 Dl --15 -9 Dl -15 24 Dl -0 -138 Dl -1 Dt -2171 3471 MXY - 2171 3471 lineto - 2448 3471 lineto - 2448 3609 lineto - 2171 3609 lineto - 2171 3471 lineto -closepath 19 2171 3471 2448 3609 Dp -1756 3609 MXY - 1756 3609 lineto - 2033 3609 lineto - 2033 3747 lineto - 1756 3747 lineto - 1756 3609 lineto -closepath 3 1756 3609 2033 3747 Dp -1480 3471 MXY - 1480 3471 lineto - 1756 3471 lineto - 1756 3609 lineto - 1480 3609 lineto - 1480 3471 lineto -closepath 19 1480 3471 1756 3609 Dp -789 MX - 789 3471 lineto - 1065 3471 lineto - 1065 3609 lineto - 789 3609 lineto - 789 3471 lineto -closepath 19 789 3471 1065 3609 Dp -962 3903(Buffer)N -1083(Header)X -849 3851 MXY - 849 3851 lineto - 918 3851 lineto - 918 3920 lineto - 849 3920 lineto - 849 3851 lineto -closepath 14 849 3851 918 3920 Dp -1756 3194 MXY - 1756 3194 lineto - 1895 3194 lineto - 1895 3471 lineto - 1756 3471 lineto - 1756 3194 lineto -closepath 14 1756 3194 1895 3471 Dp -2171 3056 MXY - 2171 3056 lineto - 2309 3056 lineto - 2309 3333 lineto - 2171 3333 lineto - 2171 3056 lineto -closepath 14 2171 3056 2309 3333 Dp -1480 MX - 1480 3056 lineto - 1618 3056 lineto - 1618 3333 lineto - 1480 3333 lineto - 1480 3056 lineto -closepath 14 1480 3056 1618 3333 Dp -789 MX - 789 3056 lineto - 927 3056 lineto - 927 3333 lineto - 789 3333 lineto - 789 3056 lineto -closepath 14 789 3056 927 3333 Dp -2780 MY -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -927 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -1065 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -1203 MX -0 138 Dl -139 0 Dl -0 -138 Dl --139 0 Dl -1342 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -1480 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -1618 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -1756 MX -0 138 Dl -139 0 Dl -0 -138 Dl --139 0 Dl -1895 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -2033 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -2171 MX -0 138 Dl -138 0 Dl -0 -138 Dl --138 0 Dl -2309 MX -0 138 Dl -139 0 Dl -0 -138 Dl --139 0 Dl -13 s -1048 2720(In)N -1173(Memory)X -1580(Bucket)X -1918(Array)X -867 3584(B0)N -1558(B5)X -2223(B10)X -1788 3722(O1/1)N -5 s -1515 3903(Primay)N -1651(Buffer)X -4 Ds -1990 3851 MXY - 1990 3851 lineto - 2059 3851 lineto - 2059 3920 lineto - 1990 3920 lineto - 1990 3851 lineto -closepath 3 1990 3851 2059 3920 Dp -2102 3903(Over\257ow)N -2270(Buffer)X -3 Dt --1 Ds -8 s -720 4184(Figure)N -922(4:)X -1 f -996(Three)X -1164(primary)X -1386(pages)X -1551(\(B0,)X -1683(B5,)X -1794(B10\))X -1942(are)X -2039(accessed)X -2281(directly)X -720 4272(from)N -862(the)X -958(bucket)X -1146(array.)X -1326(The)X -1443(one)X -1553(over\257ow)X -1798(page)X -1935(\(O1/1\))X -2122(is)X -2182(linked)X -2359(phy-)X -720 4360(sically)N -915(from)X -1067(its)X -1155(primary)X -1384(page's)X -1577(buffer)X -1759(header)X -1955(as)X -2035(well)X -2172(as)X -2252(logically)X -720 4448(from)N -860(its)X -937(predecessor)X -1253(page)X -1389(buffer)X -1560(\(B5\).)X -10 s -10 f -720 4624 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -1191 4954(Table)N -1406(Parameterization)X -1 f -892 5086(When)N -1107(a)X -1166(hash)X -1336(table)X -1515(is)X -1590(created,)X -1865(the)X -1985(bucket)X -2221(size,)X -2388(\256ll)X -720 5174(factor,)N -953(initial)X -1164(number)X -1434(of)X -1526(elements,)X -1856(number)X -2125(of)X -2216(bytes)X -2409(of)X -720 5262(main)N -919(memory)X -1225(used)X -1411(for)X -1543(caching,)X -1851(and)X -2005(a)X -2079(user-de\256ned)X -720 5350(hash)N -892(function)X -1184(may)X -1347(be)X -1448(speci\256ed.)X -1797(The)X -1946(bucket)X -2184(size)X -2333(\(and)X -720 5438(page)N -906(size)X -1064(for)X -1191(over\257ow)X -1509(pages\))X -1752(defaults)X -2039(to)X -2134(256)X -2287(bytes.)X -720 5526(For)N -858(tables)X -1072(with)X -1241(large)X -1429(data)X -1590(items,)X -1810(it)X -1881(may)X -2046(be)X -2149(preferable)X -720 5614(to)N -803(increase)X -1088(the)X -1207(page)X -1380(size,)X -1545(and,)X -1701(conversely,)X -2089(applications)X -720 5702(storing)N -1002(small)X -1235(items)X -1467(exclusively)X -1891(in)X -2012(memory)X -2338(may)X -2706 538(bene\256t)N -2966(from)X -3164(a)X -3242(smaller)X -3520(bucket)X -3776(size.)X -3983(A)X -4082(bucket)X -4337(size)X -2706 626(smaller)N -2962(than)X -3120(64)X -3220(bytes)X -3409(is)X -3482(not)X -3604(recommended.)X -2878 740(The)N -3031(\256ll)X -3147(factor)X -3363(indicates)X -3676(a)X -3740(desired)X -4000(density)X -4258(within)X -2706 828(the)N -2833(hash)X -3009(table.)X -3234(It)X -3312(is)X -3394(an)X -3499(approximation)X -3995(of)X -4091(the)X -4217(number)X -2706 916(of)N -2815(keys)X -3004(allowed)X -3300(to)X -3404(accumulate)X -3811(in)X -3914(any)X -4071(one)X -4228(bucket,)X -2706 1004(determining)N -3119(when)X -3319(the)X -3442(hash)X -3614(table)X -3795(grows.)X -4056(Its)X -4161(default)X -4409(is)X -2706 1092(eight.)N -2953(If)X -3054(the)X -3199(user)X -3380(knows)X -3636(the)X -3781(average)X -4079(size)X -4251(of)X -4364(the)X -2706 1180(key/data)N -3008(pairs)X -3194(being)X -3402(stored)X -3627(in)X -3718(the)X -3845(table,)X -4050(near)X -4218(optimal)X -2706 1268(bucket)N -2943(sizes)X -3122(and)X -3261(\256ll)X -3372(factors)X -3614(may)X -3775(be)X -3874(selected)X -4155(by)X -4257(apply-)X -2706 1356(ing)N -2828(the)X -2946(equation:)X -0 f -8 s -2706 1655(\(1\))N -2994 -0.3938(\(\(average_pair_length)AX -3830(+)X -3906(4\))X -4020(*)X -3032 1743(ffactor\))N -3374(>=)X -3488(bsize)X -1 f -10 s -2706 2042(For)N -2859(highly)X -3104(time)X -3287(critical)X -3551(applications,)X -3999(experimenting)X -2706 2130(with)N -2919(different)X -3266(bucket)X -3550(sizes)X -3776(and)X -3962(\256ll)X -4120(factors)X -4409(is)X -2706 2218(encouraged.)N -2878 2332(Figures)N -3144(5a,b,)X -3326(and)X -3468(c)X -3530(illustrate)X -3836(the)X -3960(effects)X -4200(of)X -4292(vary-)X -2706 2420(ing)N -2841(page)X -3026(sizes)X -3215(and)X -3363(\256ll)X -3483(factors)X -3734(for)X -3860(the)X -3990(same)X -4187(data)X -4353(set.)X -2706 2508(The)N -2864(data)X -3031(set)X -3152(consisted)X -3482(of)X -3581(24474)X -3813(keys)X -3992(taken)X -4198(from)X -4386(an)X -2706 2596(online)N -2931(dictionary.)X -3301(The)X -3451(data)X -3609(value)X -3807(for)X -3925(each)X -4097(key)X -4237(was)X -4386(an)X -2706 2684(ASCII)N -2938(string)X -3143(for)X -3260(an)X -3359(integer)X -3605(from)X -3784(1)X -3847(to)X -3931(24474)X -4153(inclusive.)X -2706 2772(The)N -2867(test)X -3013(run)X -3155(consisted)X -3488(of)X -3590(creating)X -3884(a)X -3955(new)X -4124(hash)X -4306(table)X -2706 2860(\(where)N -2966(the)X -3100(ultimate)X -3398(size)X -3559(of)X -3662(the)X -3796(table)X -3987(was)X -4147(known)X -4400(in)X -2706 2948(advance\),)N -3054(entering)X -3354(each)X -3539(key/data)X -3848(pair)X -4010(into)X -4171(the)X -4306(table)X -2706 3036(and)N -2849(then)X -3014(retrieving)X -3353(each)X -3528(key/data)X -3827(pair)X -3979(from)X -4162(the)X -4286(table.)X -2706 3124(Each)N -2898(of)X -2996(the)X -3125(graphs)X -3369(shows)X -3599(the)X -3727(timings)X -3996(resulting)X -4306(from)X -2706 3212(varying)N -2973(the)X -3093(pagesize)X -3392(from)X -3570(128)X -3712(bytes)X -3903(to)X -3986(1M)X -4118(and)X -4255(the)X -4374(\256ll)X -2706 3300(factor)N -2929(from)X -3120(1)X -3195(to)X -3292(128.)X -3486(For)X -3631(each)X -3813(run,)X -3974(the)X -4106(buffer)X -4337(size)X -2706 3388(was)N -2874(set)X -3006(at)X -3106(1M.)X -3299(The)X -3466(tests)X -3650(were)X -3849(all)X -3971(run)X -4120(on)X -4242(an)X -4360(HP)X -2706 3476(9000/370)N -3077(\(33.3)X -3312(Mhz)X -3527(MC68030\),)X -3966(with)X -4176(16M)X -4395(of)X -2706 3564(memory,)N -3042(64K)X -3228(physically)X -3605(addressed)X -3970(cache,)X -4222(and)X -4386(an)X -2706 3652(HP7959S)N -3055(disk)X -3231(drive,)X -3459(running)X -3751(4.3BSD-Reno)X -4244(single-)X -2706 3740(user.)N -2878 3854(Both)N -3066(system)X -3321(time)X -3496(\(Figure)X -3764(5a\))X -3899(and)X -4047(elapsed)X -4320(time)X -2706 3942(\(Figure)N -2966(5b\))X -3097(show)X -3290(that)X -3434(for)X -3552(all)X -3655(bucket)X -3892(sizes,)X -4091(the)X -4212(greatest)X -2706 4030(performance)N -3137(gains)X -3329(are)X -3451(made)X -3648(by)X -3751(increasing)X -4104(the)X -4225(\256ll)X -4336(fac-)X -2706 4118(tor)N -2822(until)X -2995(equation)X -3298(1)X -3365(is)X -3445(satis\256ed.)X -3774(The)X -3925(user)X -4085(time)X -4253(shown)X -2706 4206(in)N -2791(Figure)X -3023(5c)X -3122(gives)X -3314(a)X -3373(more)X -3561(detailed)X -3838(picture)X -4083(of)X -4172(how)X -4332(per-)X -2706 4294(formance)N -3054(varies.)X -3330(The)X -3499(smaller)X -3778(bucket)X -4035(sizes)X -4234(require)X -2706 4382(fewer)N -2921(keys)X -3099(per)X -3233(page)X -3416(to)X -3509(satisfy)X -3749(equation)X -4056(1)X -4127(and)X -4274(there-)X -2706 4470(fore)N -2860(incur)X -3049(fewer)X -3257(collisions.)X -3607(However,)X -3946(when)X -4144(the)X -4265(buffer)X -2706 4558(pool)N -2884(size)X -3045(is)X -3134(\256xed,)X -3349(smaller)X -3620(pages)X -3838(imply)X -4059(more)X -4259(pages.)X -2706 4646(An)N -2830(increased)X -3160(number)X -3430(of)X -3522(pages)X -3730(means)X -3960(more)X -2 f -4150(malloc\(3\))X -1 f -2706 4734(calls)N -2879(and)X -3021(more)X -3212(overhead)X -3533(in)X -3621(the)X -3745(hash)X -3918(package's)X -4265(buffer)X -2706 4822(manager)N -3003(to)X -3085(manage)X -3355(the)X -3473(additional)X -3813(pages.)X -2878 4936(The)N -3028(tradeoff)X -3308(works)X -3529(out)X -3655(most)X -3834(favorably)X -4166(when)X -4364(the)X -2706 5024(page)N -2886(size)X -3039(is)X -3120(256)X -3268(and)X -3412(the)X -3538(\256ll)X -3654(factor)X -3870(is)X -3950(8.)X -4057(Similar)X -4319(con-)X -2706 5112(clusions)N -3009(were)X -3207(obtained)X -3524(if)X -3614(the)X -3753(test)X -3905(was)X -4071(run)X -4218(without)X -2706 5200(knowing)N -3007(the)X -3126(\256nal)X -3289(table)X -3466(size)X -3612(in)X -3695(advance.)X -4020(If)X -4095(the)X -4214(\256le)X -4337(was)X -2706 5288(closed)N -2942(and)X -3088(written)X -3345(to)X -3437(disk,)X -3620(the)X -3748(conclusions)X -4156(were)X -4343(still)X -2706 5376(the)N -2832(same.)X -3065(However,)X -3408(rereading)X -3740(the)X -3865(\256le)X -3994(from)X -4177(disk)X -4337(was)X -2706 5464(slightly)N -2983(faster)X -3199(if)X -3285(a)X -3358(larger)X -3583(bucket)X -3834(size)X -3996(and)X -4149(\256ll)X -4274(factor)X -2706 5552(were)N -2898(used)X -3079(\(1K)X -3238(bucket)X -3486(size)X -3645(and)X -3795(32)X -3909(\256ll)X -4031(factor\).)X -4320(This)X -2706 5640(follows)N -2987(intuitively)X -3356(from)X -3553(the)X -3691(improved)X -4038(ef\256ciency)X -4395(of)X -3 f -720 5960(USENIX)N -9 f -1042(-)X -3 f -1106(Winter)X -1371('91)X -9 f -1498(-)X -3 f -1562(Dallas,)X -1815(TX)X -4424(7)X - -8 p -%%Page: 8 8 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -432 258(A)N -510(New)X -682(Hashing)X -985(Package)X -1290(for)X -1413(UNIX)X -3663(Seltzer)X -3920(&)X -4007(Yigit)X -1 f -432 538(performing)N -830(1K)X -965(reads)X -1172(from)X -1365(the)X -1500(disk)X -1670(rather)X -1894(than)X -2068(256)X -432 626(byte)N -609(reads.)X -857(In)X -962(general,)X -1257(performance)X -1702(for)X -1834(disk)X -2005(based)X -432 714(tables)N -639(is)X -712(best)X -861(when)X -1055(the)X -1173(page)X -1345(size)X -1490(is)X -1563(approximately)X -2046(1K.)X -10 f -432 802 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -619 2380 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -629 2437 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -648 2504 MXY --12 25 Dl -24 0 Dl --12 -25 Dl -686 2515 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -762 2516 MXY --12 24 Dl -25 0 Dl --13 -24 Dl -916 2515 MXY --13 24 Dl -25 0 Dl --12 -24 Dl -1222 2516 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -1834 2515 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -1 Dt -619 2392 MXY -10 57 Dl -19 67 Dl -38 11 Dl -76 1 Dl -154 -1 Dl -306 1 Dl -612 -1 Dl -8 s -1 f -1628 2522(128)N -3 Dt -607 2245 MXY -24 Dc -617 2375 MXY -23 Dc -635 2442 MXY -24 Dc -674 2525 MXY -23 Dc -750 2529 MXY -24 Dc -904 2527 MXY -23 Dc -1210 MX -23 Dc -1822 2528 MXY -23 Dc -20 Ds -1 Dt -619 2245 MXY -10 130 Dl -19 67 Dl -38 83 Dl -76 4 Dl -154 -2 Dl -306 0 Dl -612 1 Dl -678 2482(256)N --1 Ds -3 Dt -619 2127 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -629 2191 MXY -0 25 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -648 2334 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -686 2409 MXY -0 25 Dl -0 -13 Dl -12 0 Dl --24 0 Dl -762 2516 MXY -0 25 Dl -0 -12 Dl -13 0 Dl --25 0 Dl -916 2516 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --25 0 Dl -1222 2515 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -1834 2515 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -5 Dt -619 2139 MXY -10 65 Dl -19 142 Dl -38 75 Dl -76 108 Dl -154 -1 Dl -306 -1 Dl -612 0 Dl -694 2401(512)N -3 Dt -631 2064 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -641 2077 MXY --24 25 Dl -12 -12 Dl --12 -13 Dl -24 25 Dl -660 2132 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -698 2292 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -775 2382 MXY --25 24 Dl -12 -12 Dl --12 -12 Dl -25 24 Dl -928 2516 MXY --25 24 Dl -13 -12 Dl --13 -12 Dl -25 24 Dl -1234 2516 MXY --24 25 Dl -12 -12 Dl --12 -13 Dl -24 25 Dl -1846 2516 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -16 Ds -1 Dt -619 2076 MXY -10 14 Dl -19 54 Dl -38 160 Dl -76 90 Dl -154 134 Dl -306 1 Dl -612 -1 Dl -694 2257(1024)N --1 Ds -3 Dt -619 1877 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -629 1855 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -648 1838 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -686 1860 MXY -12 -25 Dl --24 0 Dl -12 25 Dl -762 1923 MXY -13 -24 Dl --25 0 Dl -12 24 Dl -916 2087 MXY -12 -24 Dl --25 0 Dl -13 24 Dl -1222 2256 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -1834 2541 MXY -12 -25 Dl --24 0 Dl -12 25 Dl -619 1865 MXY -10 -22 Dl -19 -17 Dl -38 21 Dl -76 64 Dl -154 164 Dl -306 169 Dl -612 285 Dl -1645 2427(4096)N -619 1243 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -629 1196 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -648 1146 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -686 1174 MXY -0 25 Dl -0 -13 Dl -12 0 Dl --24 0 Dl -762 1249 MXY -0 24 Dl -0 -12 Dl -13 0 Dl --25 0 Dl -916 1371 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --25 0 Dl -1222 1680 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -1834 1999 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -619 1255 MXY -10 -47 Dl -19 -50 Dl -38 28 Dl -76 75 Dl -154 122 Dl -306 309 Dl -612 319 Dl -1741 1934(8192)N -5 Dt -609 2531 MXY -1225 0 Dl -609 MX -0 -1553 Dl -2531 MY -0 16 Dl -4 Ds -1 Dt -2531 MY -0 -1553 Dl -593 2625(0)N --1 Ds -5 Dt -916 2531 MXY -0 16 Dl -4 Ds -1 Dt -2531 MY -0 -1553 Dl -884 2625(32)N --1 Ds -5 Dt -1222 2531 MXY -0 16 Dl -4 Ds -1 Dt -2531 MY -0 -1553 Dl -1190 2625(64)N --1 Ds -5 Dt -1528 2531 MXY -0 16 Dl -4 Ds -1 Dt -2531 MY -0 -1553 Dl -1496 2625(96)N --1 Ds -5 Dt -1834 2531 MXY -0 16 Dl -4 Ds -1 Dt -2531 MY -0 -1553 Dl -1786 2625(128)N --1 Ds -5 Dt -609 2531 MXY --16 0 Dl -4 Ds -1 Dt -609 MX -1225 0 Dl -545 2558(0)N --1 Ds -5 Dt -609 2013 MXY --16 0 Dl -4 Ds -1 Dt -609 MX -1225 0 Dl -481 2040(100)N --1 Ds -5 Dt -609 1496 MXY --16 0 Dl -4 Ds -1 Dt -609 MX -1225 0 Dl -481 1523(200)N --1 Ds -5 Dt -609 978 MXY --16 0 Dl -4 Ds -1 Dt -609 MX -1225 0 Dl -481 1005(300)N -1088 2724(Fill)N -1194(Factor)X -422 1611(S)N -426 1667(e)N -426 1724(c)N -424 1780(o)N -424 1837(n)N -424 1893(d)N -428 1949(s)N -3 Dt --1 Ds -3 f -432 2882(Figure)N -636(5a:)X -1 f -744(System)X -956(Time)X -1113(for)X -1209(dictionary)X -1490(data)X -1618(set)X -1711(with)X -1847(1M)X -1958(of)X -2033(buffer)X -432 2970(space)N -594(and)X -707(varying)X -923(bucket)X -1114(sizes)X -1259(and)X -1372(\256ll)X -1465(factors.)X -1675(Each)X -1823(line)X -1940(is)X -2004(labeled)X -432 3058(with)N -562(its)X -639(bucket)X -825(size.)X -10 s -10 f -432 3234 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -8 s -1 f -428 4381(s)N -424 4325(d)N -424 4269(n)N -424 4212(o)N -426 4156(c)N -426 4099(e)N -422 4043(S)N -1116 5156(Fill)N -1222(Factor)X -506 3437(3200)N -4 Ds -1 Dt -666 3410 MXY -1168 0 Dl --1 Ds -5 Dt -666 MX --16 0 Dl -506 3825(2400)N -4 Ds -1 Dt -666 3799 MXY -1168 0 Dl --1 Ds -5 Dt -666 MX --16 0 Dl -506 4214(1600)N -4 Ds -1 Dt -666 4186 MXY -1168 0 Dl --1 Ds -5 Dt -666 MX --16 0 Dl -538 4602(800)N -4 Ds -1 Dt -666 4575 MXY -1168 0 Dl --1 Ds -5 Dt -666 MX --16 0 Dl -602 4990(0)N -4 Ds -1 Dt -666 4963 MXY -1168 0 Dl --1 Ds -5 Dt -666 MX --16 0 Dl -1786 5057(128)N -4 Ds -1 Dt -1834 4963 MXY -0 -1553 Dl --1 Ds -5 Dt -4963 MY -0 16 Dl -1510 5057(96)N -4 Ds -1 Dt -1542 4963 MXY -0 -1553 Dl --1 Ds -5 Dt -4963 MY -0 16 Dl -1218 5057(64)N -4 Ds -1 Dt -1250 4963 MXY -0 -1553 Dl --1 Ds -5 Dt -4963 MY -0 16 Dl -926 5057(32)N -4 Ds -1 Dt -958 4963 MXY -0 -1553 Dl --1 Ds -5 Dt -4963 MY -0 16 Dl -650 5057(0)N -4 Ds -1 Dt -666 4963 MXY -0 -1553 Dl --1 Ds -5 Dt -4963 MY -0 16 Dl -4963 MY -0 -1553 Dl -4963 MY -1168 0 Dl -1741 4752(8192)N -3 Dt -675 3732 MXY -9 -172 Dl -18 -118 Dl -37 128 Dl -73 -121 Dl -146 623 Dl -292 497 Dl -584 245 Dl -4802 MY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -1250 4557 MXY -0 25 Dl -0 -13 Dl -12 0 Dl --24 0 Dl -958 4060 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -812 3437 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -739 3558 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -702 3430 MXY -0 25 Dl -0 -13 Dl -13 0 Dl --25 0 Dl -684 3548 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -675 3720 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -1637 4912(4096)N -675 4307 MXY -9 -58 Dl -18 30 Dl -37 89 Dl -73 144 Dl -146 235 Dl -292 122 Dl -584 89 Dl -4970 MY -12 -24 Dl --24 0 Dl -12 24 Dl -1250 4881 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -958 4759 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -812 4524 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -739 4380 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -702 4291 MXY -13 -24 Dl --25 0 Dl -12 24 Dl -684 4261 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -675 4319 MXY -12 -24 Dl --24 0 Dl -12 24 Dl -734 4662(1024)N -16 Ds -1 Dt -675 4352 MXY -9 60 Dl -18 134 Dl -37 266 Dl -73 117 Dl -146 30 Dl -292 0 Dl -584 -1 Dl --1 Ds -3 Dt -1846 4946 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -1262 4946 MXY --24 25 Dl -12 -12 Dl --12 -13 Dl -24 25 Dl -970 4947 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -824 4917 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -751 4800 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -715 4534 MXY --25 25 Dl -12 -13 Dl --12 -12 Dl -25 25 Dl -696 4400 MXY --24 24 Dl -12 -12 Dl --12 -12 Dl -24 24 Dl -687 4339 MXY --24 25 Dl -12 -12 Dl --12 -13 Dl -24 25 Dl -718 4792(512)N -5 Dt -675 4422 MXY -9 137 Dl -18 278 Dl -37 105 Dl -73 18 Dl -146 -1 Dl -292 0 Dl -584 -1 Dl -3 Dt -4946 MY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -1250 4946 MXY -0 25 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -958 4947 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -812 4948 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -739 4930 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -702 4824 MXY -0 25 Dl -0 -12 Dl -13 0 Dl --25 0 Dl -684 4547 MXY -0 24 Dl -0 -12 Dl -12 0 Dl --24 0 Dl -675 4410 MXY -0 25 Dl -0 -13 Dl -12 0 Dl --24 0 Dl -750 4921(256)N -20 Ds -1 Dt -675 4597 MXY -9 246 Dl -18 106 Dl -37 10 Dl -73 0 Dl -146 0 Dl -292 0 Dl -584 -1 Dl --1 Ds -3 Dt -1822 MX -23 Dc -1238 4959 MXY -23 Dc -946 MX -23 Dc -800 MX -23 Dc -727 MX -23 Dc -691 4949 MXY -23 Dc -672 4843 MXY -24 Dc -663 4597 MXY -24 Dc -1395 4961(128)N -1 Dt -675 4855 MXY -9 93 Dl -18 10 Dl -37 1 Dl -73 0 Dl -146 -1 Dl -292 0 Dl -584 0 Dl -3 Dt -4946 MY --12 24 Dl -24 0 Dl --12 -24 Dl -1250 MX --12 24 Dl -24 0 Dl --12 -24 Dl -958 MX --12 24 Dl -24 0 Dl --12 -24 Dl -812 MX --12 25 Dl -24 0 Dl --12 -25 Dl -739 4947 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -702 4946 MXY --12 24 Dl -25 0 Dl --13 -24 Dl -684 4936 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -675 4843 MXY --12 24 Dl -24 0 Dl --12 -24 Dl -3 Dt --1 Ds -3 f -432 5314(Figure)N -634(5b:)X -1 f -744(Elapsed)X -967(Time)X -1123(for)X -1218(dictionary)X -1498(data)X -1625(set)X -1717(with)X -1851(1M)X -1960(of)X -2033(buffer)X -432 5402(space)N -593(and)X -705(varying)X -920(bucket)X -1110(sizes)X -1254(and)X -1366(\256ll)X -1457(factors.)X -1681(Each)X -1827(line)X -1942(is)X -2004(labeled)X -432 5490(with)N -562(its)X -639(bucket)X -825(size.)X -10 s -2590 538(If)N -2677(an)X -2785(approximation)X -3284(of)X -3383(the)X -3513(number)X -3790(of)X -3889(elements)X -2418 626(ultimately)N -2773(to)X -2866(be)X -2973(stored)X -3200(in)X -3293(the)X -3422(hash)X -3599(table)X -3785(is)X -3868(known)X -4116(at)X -2418 714(the)N -2564(time)X -2754(of)X -2869(creation,)X -3196(the)X -3342(hash)X -3536(package)X -3847(takes)X -4059(this)X -2418 802(number)N -2688(as)X -2779(a)X -2839(parameter)X -3185(and)X -3325(uses)X -3487(it)X -3555(to)X -3641(hash)X -3812(entries)X -4050(into)X -2418 890(the)N -2541(full)X -2677(sized)X -2867(table)X -3048(rather)X -3261(than)X -3424(growing)X -3716(the)X -3838(table)X -4018(from)X -2418 978(a)N -2477(single)X -2691(bucket.)X -2968(If)X -3044(this)X -3181(number)X -3448(is)X -3523(not)X -3647(known,)X -3907(the)X -4027(hash)X -2418 1066(table)N -2632(starts)X -2859(with)X -3059(a)X -3153(single)X -3402(bucket)X -3674(and)X -3848(gracefully)X -2418 1154(expands)N -2707(as)X -2800(elements)X -3111(are)X -3236(added,)X -3474(although)X -3780(a)X -3842(slight)X -4044(per-)X -2418 1242(formance)N -2747(degradation)X -3151(may)X -3313(be)X -3413(noticed.)X -3713(Figure)X -3946(6)X -4010(illus-)X -2418 1330(trates)N -2625(the)X -2756(difference)X -3116(in)X -3211(performance)X -3651(between)X -3952(storing)X -2418 1418(keys)N -2588(in)X -2673(a)X -2732(\256le)X -2857(when)X -3054(the)X -3174(ultimate)X -3458(size)X -3605(is)X -3680(known)X -3920(\(the)X -4067(left)X -2418 1506(bars)N -2581(in)X -2672(each)X -2849(set\),)X -3014(compared)X -3360(to)X -3450(building)X -3744(the)X -3870(\256le)X -4000(when)X -2418 1594(the)N -2550(ultimate)X -2846(size)X -3005(is)X -3091(unknown)X -3422(\(the)X -3580(right)X -3764(bars)X -3931(in)X -4026(each)X -2418 1682(set\).)N -2609(Once)X -2814(the)X -2947(\256ll)X -3069(factor)X -3291(is)X -3378(suf\256ciently)X -3772(high)X -3948(for)X -4076(the)X -2418 1770(page)N -2596(size)X -2747(\(8\),)X -2887(growing)X -3180(the)X -3304(table)X -3486(dynamically)X -3908(does)X -4081(lit-)X -2418 1858(tle)N -2518(to)X -2600(degrade)X -2875(performance.)X -10 f -2418 1946 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -9 s -1 f -2413 3238(s)N -2409 3173(d)N -2409 3108(n)N -2409 3043(o)N -2411 2979(c)N -2411 2914(e)N -2407 2849(S)N -3143 4129(Fill)N -3261(Factor)X -2448 2152(15)N -4 Ds -1 Dt -2557 2122 MXY -1473 0 Dl --1 Ds -5 Dt -2557 MX --19 0 Dl -2448 2747(10)N -4 Ds -1 Dt -2557 2717 MXY -1473 0 Dl --1 Ds -5 Dt -2557 MX --19 0 Dl -2484 3343(5)N -4 Ds -1 Dt -2557 3313 MXY -1473 0 Dl --1 Ds -5 Dt -2557 MX --19 0 Dl -2484 3938(0)N -4 Ds -1 Dt -2557 3908 MXY -1473 0 Dl --1 Ds -5 Dt -2557 MX --19 0 Dl -3976 4015(128)N -4 Ds -1 Dt -4030 3908 MXY -0 -1786 Dl --1 Ds -5 Dt -3908 MY -0 19 Dl -3626 4015(96)N -4 Ds -1 Dt -3662 3908 MXY -0 -1786 Dl --1 Ds -5 Dt -3908 MY -0 19 Dl -3258 4015(64)N -4 Ds -1 Dt -3294 3908 MXY -0 -1786 Dl --1 Ds -5 Dt -3908 MY -0 19 Dl -2889 4015(32)N -4 Ds -1 Dt -2925 3908 MXY -0 -1786 Dl --1 Ds -5 Dt -3908 MY -0 19 Dl -2539 4015(0)N -4 Ds -1 Dt -2557 3908 MXY -0 -1786 Dl --1 Ds -5 Dt -3908 MY -0 19 Dl -3908 MY -0 -1786 Dl -3908 MY -1473 0 Dl -4053 2378(8192)N -3 Dt -2569 2277 MXY -11 0 Dl -23 48 Dl -46 -167 Dl -92 35 Dl -184 12 Dl -369 143 Dl -736 0 Dl -2334 MY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -3294 2334 MXY -0 28 Dl -0 -14 Dl -13 0 Dl --27 0 Dl -2925 2192 MXY -0 27 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2741 2180 MXY -0 27 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2649 2144 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2603 2311 MXY -0 27 Dl -0 -13 Dl -14 0 Dl --28 0 Dl -2580 2263 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2569 2263 MXY -0 28 Dl -0 -14 Dl -13 0 Dl --27 0 Dl -4053 2591(4096)N -2569 2348 MXY -11 -11 Dl -23 -96 Dl -46 71 Dl -92 72 Dl -184 226 Dl -369 48 Dl -736 -60 Dl -2612 MY -14 -28 Dl --28 0 Dl -14 28 Dl -3294 2672 MXY -13 -28 Dl --27 0 Dl -14 28 Dl -2925 2624 MXY -14 -28 Dl --28 0 Dl -14 28 Dl -2741 2398 MXY -14 -28 Dl --28 0 Dl -14 28 Dl -2649 2326 MXY -14 -27 Dl --28 0 Dl -14 27 Dl -2603 2255 MXY -14 -28 Dl --28 0 Dl -14 28 Dl -2580 2350 MXY -14 -27 Dl --28 0 Dl -14 27 Dl -2569 2362 MXY -13 -28 Dl --27 0 Dl -14 28 Dl -4053 2681(1024)N -16 Ds -1 Dt -2569 2300 MXY -11 48 Dl -23 96 Dl -46 95 Dl -92 274 Dl -184 202 Dl -369 -155 Dl -736 -190 Dl --1 Ds -3 Dt -4044 2656 MXY --28 28 Dl -14 -14 Dl --14 -14 Dl -28 28 Dl -3307 2846 MXY --27 28 Dl -14 -14 Dl --14 -14 Dl -27 28 Dl -2939 3001 MXY --28 28 Dl -14 -14 Dl --14 -14 Dl -28 28 Dl -2755 2799 MXY --28 28 Dl -14 -14 Dl --14 -14 Dl -28 28 Dl -2663 2525 MXY --28 28 Dl -14 -14 Dl --14 -14 Dl -28 28 Dl -2617 2430 MXY --28 28 Dl -14 -14 Dl --14 -14 Dl -28 28 Dl -2594 2334 MXY --28 28 Dl -14 -14 Dl --14 -14 Dl -28 28 Dl -2582 2287 MXY --27 27 Dl -14 -14 Dl --14 -13 Dl -27 27 Dl -4053 2851(512)N -5 Dt -2569 2372 MXY -11 -24 Dl -23 405 Dl -46 83 Dl -92 227 Dl -184 -72 Dl -369 -119 Dl -736 -107 Dl -3 Dt -2751 MY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -3294 2858 MXY -0 28 Dl -0 -14 Dl -13 0 Dl --27 0 Dl -2925 2977 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2741 3049 MXY -0 27 Dl -0 -13 Dl -14 0 Dl --28 0 Dl -2649 2823 MXY -0 27 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2603 2739 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2580 2334 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2569 2358 MXY -0 28 Dl -0 -14 Dl -13 0 Dl --27 0 Dl -4053 2795(256)N -20 Ds -1 Dt -2569 2456 MXY -11 285 Dl -23 95 Dl -46 251 Dl -92 -60 Dl -184 -84 Dl -369 -107 Dl -736 -71 Dl --1 Ds -3 Dt -4016 MX -27 Dc -3280 2836 MXY -27 Dc -2912 2943 MXY -27 Dc -2728 3027 MXY -27 Dc -2635 3087 MXY -28 Dc -2589 2836 MXY -28 Dc -2566 2741 MXY -27 Dc -2554 2456 MXY -28 Dc -4053 2741(128)N -1 Dt -2569 2729 MXY -11 203 Dl -23 131 Dl -46 -60 Dl -92 -119 Dl -184 -60 Dl -369 -83 Dl -736 -12 Dl -3 Dt -2716 MY --14 27 Dl -28 0 Dl --14 -27 Dl -3294 2727 MXY --14 28 Dl -27 0 Dl --13 -28 Dl -2925 2811 MXY --14 27 Dl -28 0 Dl --14 -27 Dl -2741 2870 MXY --14 28 Dl -28 0 Dl --14 -28 Dl -2649 2989 MXY --14 28 Dl -28 0 Dl --14 -28 Dl -2603 3049 MXY --14 27 Dl -28 0 Dl --14 -27 Dl -2580 2918 MXY --14 28 Dl -28 0 Dl --14 -28 Dl -2569 2716 MXY --14 27 Dl -27 0 Dl --13 -27 Dl -3 Dt --1 Ds -3 f -8 s -2418 4286(Figure)N -2628(5c:)X -1 f -2738(User)X -2887(Time)X -3051(for)X -3154(dictionary)X -3442(data)X -3577(set)X -3677(with)X -3820(1M)X -3938(of)X -4019(buffer)X -2418 4374(space)N -2579(and)X -2691(varying)X -2906(bucket)X -3096(sizes)X -3240(and)X -3352(\256ll)X -3443(factors.)X -3667(Each)X -3813(line)X -3928(is)X -3990(labeled)X -2418 4462(with)N -2548(its)X -2625(bucket)X -2811(size.)X -10 s -10 f -2418 4638 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -1 f -2590 4840(Since)N -2796(no)X -2904(known)X -3150(hash)X -3325(function)X -3620(performs)X -3938(equally)X -2418 4928(well)N -2589(on)X -2702(all)X -2815(possible)X -3110(data,)X -3297(the)X -3428(user)X -3595(may)X -3766(\256nd)X -3923(that)X -4076(the)X -2418 5016(built-in)N -2678(hash)X -2849(function)X -3140(does)X -3311(poorly)X -3544(on)X -3648(a)X -3708(particular)X -4040(data)X -2418 5104(set.)N -2548(In)X -2636(this)X -2771(case,)X -2950(a)X -3006(hash)X -3173(function,)X -3480(taking)X -3700(two)X -3840(arguments)X -2418 5192(\(a)N -2507(pointer)X -2760(to)X -2848(a)X -2910(byte)X -3074(string)X -3282(and)X -3424(a)X -3486(length\))X -3739(and)X -3880(returning)X -2418 5280(an)N -2517(unsigned)X -2829(long)X -2993(to)X -3077(be)X -3175(used)X -3344(as)X -3433(the)X -3553(hash)X -3722(value,)X -3938(may)X -4098(be)X -2418 5368(speci\256ed)N -2731(at)X -2817(hash)X -2992(table)X -3176(creation)X -3463(time.)X -3673(When)X -3893(an)X -3996(exist-)X -2418 5456(ing)N -2570(hash)X -2767(table)X -2973(is)X -3076(opened)X -3358(and)X -3524(a)X -3609(hash)X -3805(function)X -4121(is)X -2418 5544(speci\256ed,)N -2752(the)X -2879(hash)X -3054(package)X -3346(will)X -3498(try)X -3615(to)X -3705(determine)X -4054(that)X -2418 5632(the)N -2546(hash)X -2723(function)X -3020(supplied)X -3321(is)X -3404(the)X -3532(one)X -3678(with)X -3850(which)X -4076(the)X -2418 5720(table)N -2630(was)X -2811(created.)X -3139(There)X -3382(are)X -3536(a)X -3627(variety)X -3905(of)X -4027(hash)X -3 f -432 5960(8)N -2970(USENIX)X -9 f -3292(-)X -3 f -3356(Winter)X -3621('91)X -9 f -3748(-)X -3 f -3812(Dallas,)X -4065(TX)X - -9 p -%%Page: 9 9 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -720 258(Seltzer)N -977(&)X -1064(Yigit)X -3278(A)X -3356(New)X -3528(Hashing)X -3831(Package)X -4136(for)X -4259(UNIX)X -1 f -720 538(functions)N -1065(provided)X -1397(with)X -1586(the)X -1731(package.)X -2082(The)X -2253(default)X -720 626(function)N -1014(for)X -1135(the)X -1260(package)X -1551(is)X -1631(the)X -1755(one)X -1897(which)X -2119(offered)X -2378(the)X -720 714(best)N -875(performance)X -1308(in)X -1396(terms)X -1600(of)X -1693(cycles)X -1920(executed)X -2232(per)X -2360(call)X -720 802(\(it)N -827(did)X -965(not)X -1103(produce)X -1398(the)X -1531(fewest)X -1776(collisions)X -2117(although)X -2432(it)X -720 890(was)N -866(within)X -1091(a)X -1148(small)X -1341(percentage)X -1710(of)X -1797(the)X -1915(function)X -2202(that)X -2342(pro-)X -720 978(duced)N -947(the)X -1080(fewest)X -1324(collisions\).)X -1731(Again,)X -1981(in)X -2077(time)X -2253(critical)X -720 1066(applications,)N -1152(users)X -1342(are)X -1466(encouraged)X -1862(to)X -1949(experiment)X -2334(with)X -720 1154(a)N -783(variety)X -1032(of)X -1125(hash)X -1298(functions)X -1622(to)X -1710(achieve)X -1982(optimal)X -2252(perfor-)X -720 1242(mance.)N -10 f -720 1330 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -7 s -1038 2925(Full)N -1149(size)X -1251(table)X -1384(\(left\))X -1547 2718(Fill)N -1643(Factor)X -2268 2662(64)N -1964(32)X -1674(16)X -1384(8)X -1093(4)X -4 Ds -1 Dt -900 2280 MXY -1548 0 Dl -900 1879 MXY -1548 0 Dl -900 1506 MXY -1548 0 Dl -1563 2902 MXY -111 0 Dl --1 Ds -900 MX -110 0 Dl -1425 2828(System)N -983(User)X -1895 2778 MXY - 1895 2778 lineto - 1950 2778 lineto - 1950 2833 lineto - 1895 2833 lineto - 1895 2778 lineto -closepath 21 1895 2778 1950 2833 Dp -1342 MX - 1342 2778 lineto - 1397 2778 lineto - 1397 2833 lineto - 1342 2833 lineto - 1342 2778 lineto -closepath 14 1342 2778 1397 2833 Dp -900 MX - 900 2778 lineto - 955 2778 lineto - 955 2833 lineto - 900 2833 lineto - 900 2778 lineto -closepath 3 900 2778 955 2833 Dp -5 Dt -2283 2211 MXY -96 0 Dl -1992 MX -97 0 Dl -1702 MX -97 0 Dl -1411 2252 MXY -97 0 Dl -4 Ds -1 Dt -2283 2211 MXY - 2283 2211 lineto - 2379 2211 lineto - 2379 2252 lineto - 2283 2252 lineto - 2283 2211 lineto -closepath 14 2283 2211 2379 2252 Dp -1992 MX - 1992 2211 lineto - 2089 2211 lineto - 2089 2252 lineto - 1992 2252 lineto - 1992 2211 lineto -closepath 14 1992 2211 2089 2252 Dp -1702 MX - 1702 2211 lineto - 1799 2211 lineto - 1799 2252 lineto - 1702 2252 lineto - 1702 2211 lineto -closepath 14 1702 2211 1799 2252 Dp -1411 2252 MXY - 1411 2252 lineto - 1508 2252 lineto - 1508 2294 lineto - 1411 2294 lineto - 1411 2252 lineto -closepath 14 1411 2252 1508 2294 Dp -2283 MX - 2283 2252 lineto - 2379 2252 lineto - 2379 2612 lineto - 2283 2612 lineto - 2283 2252 lineto -closepath 3 2283 2252 2379 2612 Dp -1992 MX - 1992 2252 lineto - 2089 2252 lineto - 2089 2612 lineto - 1992 2612 lineto - 1992 2252 lineto -closepath 3 1992 2252 2089 2612 Dp -1702 MX - 1702 2252 lineto - 1799 2252 lineto - 1799 2612 lineto - 1702 2612 lineto - 1702 2252 lineto -closepath 3 1702 2252 1799 2612 Dp -1411 2294 MXY - 1411 2294 lineto - 1508 2294 lineto - 1508 2612 lineto - 1411 2612 lineto - 1411 2294 lineto -closepath 3 1411 2294 1508 2612 Dp --1 Ds -2158 2238 MXY - 2158 2238 lineto - 2255 2238 lineto - 2255 2252 lineto - 2158 2252 lineto - 2158 2238 lineto -closepath 21 2158 2238 2255 2252 Dp -1868 MX - 1868 2238 lineto - 1965 2238 lineto - 1965 2280 lineto - 1868 2280 lineto - 1868 2238 lineto -closepath 21 1868 2238 1965 2280 Dp -1577 MX - 1577 2238 lineto - 1674 2238 lineto - 1674 2308 lineto - 1577 2308 lineto - 1577 2238 lineto -closepath 21 1577 2238 1674 2308 Dp -1287 2308 MXY - 1287 2308 lineto - 1287 2280 lineto - 1384 2280 lineto - 1384 2308 lineto - 1287 2308 lineto -closepath 21 1287 2280 1384 2308 Dp -2158 2280 MXY - 2158 2280 lineto - 2158 2252 lineto - 2255 2252 lineto - 2255 2280 lineto - 2158 2280 lineto -closepath 14 2158 2252 2255 2280 Dp -1868 2308 MXY - 1868 2308 lineto - 1868 2280 lineto - 1965 2280 lineto - 1965 2308 lineto - 1868 2308 lineto -closepath 14 1868 2280 1965 2308 Dp -1577 2335 MXY - 1577 2335 lineto - 1577 2308 lineto - 1674 2308 lineto - 1674 2335 lineto - 1577 2335 lineto -closepath 14 1577 2308 1674 2335 Dp -1287 2363 MXY - 1287 2363 lineto - 1287 2308 lineto - 1384 2308 lineto - 1384 2363 lineto - 1287 2363 lineto -closepath 14 1287 2308 1384 2363 Dp -2158 2280 MXY - 2158 2280 lineto - 2255 2280 lineto - 2255 2612 lineto - 2158 2612 lineto - 2158 2280 lineto -closepath 3 2158 2280 2255 2612 Dp -1868 2308 MXY - 1868 2308 lineto - 1965 2308 lineto - 1965 2612 lineto - 1868 2612 lineto - 1868 2308 lineto -closepath 3 1868 2308 1965 2612 Dp -1577 2335 MXY - 1577 2335 lineto - 1674 2335 lineto - 1674 2612 lineto - 1577 2612 lineto - 1577 2335 lineto -closepath 3 1577 2335 1674 2612 Dp -1287 2363 MXY - 1287 2363 lineto - 1384 2363 lineto - 1384 2612 lineto - 1287 2612 lineto - 1287 2363 lineto -closepath 3 1287 2363 1384 2612 Dp -4 Ds -1121 2066 MXY - 1121 2066 lineto - 1218 2066 lineto - 1224 2080 lineto - 1127 2080 lineto - 1121 2066 lineto -closepath 21 1121 2066 1224 2080 Dp -2080 MY - 1121 2080 lineto - 1218 2080 lineto - 1218 2273 lineto - 1121 2273 lineto - 1121 2080 lineto -closepath 14 1121 2080 1218 2273 Dp -2273 MY - 1121 2273 lineto - 1218 2273 lineto - 1218 2612 lineto - 1121 2612 lineto - 1121 2273 lineto -closepath 3 1121 2273 1218 2612 Dp --1 Ds -997 1589 MXY - 997 1589 lineto - 1093 1589 lineto - 1093 1644 lineto - 997 1644 lineto - 997 1589 lineto -closepath 21 997 1589 1093 1644 Dp -1644 MY - 997 1644 lineto - 1093 1644 lineto - 1093 2280 lineto - 997 2280 lineto - 997 1644 lineto -closepath 14 997 1644 1093 2280 Dp -2280 MY - 997 2280 lineto - 1093 2280 lineto - 1093 2612 lineto - 997 2612 lineto - 997 2280 lineto -closepath 3 997 2280 1093 2612 Dp -10 s -719 2093(s)N -712 2037(d)N -712 1982(n)N -714 1927(o)N -716 1872(c)N -716 1816(e)N -712 1761(S)N -804 2286(10)N -804 1899(20)N -804 1540(30)N -3 Dt -900 1506 MXY -0 1106 Dl -1548 0 Dl -7 s -1978 2828(Elapsed)N -1701 2925(Dynamically)N -2018(grown)X -2184(table)X -2317(\(right\))X -3 Dt --1 Ds -8 s -720 3180(Figure)N -934(6:)X -1 f -1020(The)X -1152(total)X -1299(regions)X -1520(indicate)X -1755(the)X -1865(difference)X -2154(between)X -2398(the)X -720 3268(elapsed)N -931(time)X -1065(and)X -1177(the)X -1275(sum)X -1402(of)X -1475(the)X -1573(system)X -1771(and)X -1883(user)X -2008(time.)X -2173(The)X -2291(left)X -2395(bar)X -720 3356(of)N -798(each)X -939(set)X -1035(depicts)X -1241(the)X -1344(timing)X -1537(of)X -1615(the)X -1718(test)X -1831(run)X -1940(when)X -2102(the)X -2204(number)X -2423(of)X -720 3444(entries)N -910(is)X -973(known)X -1167(in)X -1237(advance.)X -1496(The)X -1614(right)X -1754(bars)X -1879(depict)X -2054(the)X -2151(timing)X -2338(when)X -720 3532(the)N -814(\256le)X -912(is)X -971(grown)X -1150(from)X -1290(a)X -1334(single)X -1503(bucket.)X -10 s -10 f -720 3708 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -1 f -892 3910(Since)N -1131(this)X -1307(hashing)X -1617(package)X -1942(provides)X -2279(buffer)X -720 3998(management,)N -1188(the)X -1323(amount)X -1600(of)X -1704(space)X -1920(allocated)X -2247(for)X -2378(the)X -720 4086(buffer)N -948(pool)X -1121(may)X -1290(be)X -1397(speci\256ed)X -1713(by)X -1824(the)X -1953(user.)X -2157(Using)X -2378(the)X -720 4174(same)N -910(data)X -1069(set)X -1183(and)X -1324(test)X -1459(procedure)X -1805(as)X -1896(used)X -2067(to)X -2153(derive)X -2378(the)X -720 4262(graphs)N -962(in)X -1052(Figures)X -1320(5a-c,)X -1507(Figure)X -1744(7)X -1812(shows)X -2039(the)X -2164(impact)X -2409(of)X -720 4350(varying)N -997(the)X -1126(size)X -1282(of)X -1380(the)X -1509(buffer)X -1737(pool.)X -1950(The)X -2106(bucket)X -2351(size)X -720 4438(was)N -873(set)X -989(to)X -1078(256)X -1225(bytes)X -1421(and)X -1564(the)X -1689(\256ll)X -1804(factor)X -2019(was)X -2171(set)X -2287(to)X -2376(16.)X -720 4526(The)N -869(buffer)X -1090(pool)X -1256(size)X -1404(was)X -1552(varied)X -1776(from)X -1955(0)X -2018(\(the)X -2166(minimum)X -720 4614(number)N -986(of)X -1074(pages)X -1277(required)X -1565(to)X -1647(be)X -1743(buffered\))X -2063(to)X -2145(1M.)X -2316(With)X -720 4702(1M)N -854(of)X -944(buffer)X -1164(space,)X -1386(the)X -1507(package)X -1794(performed)X -2151(no)X -2253(I/O)X -2382(for)X -720 4790(this)N -871(data)X -1040(set.)X -1204(As)X -1328(Figure)X -1572(7)X -1647(illustrates,)X -2013(increasing)X -2378(the)X -720 4878(buffer)N -944(pool)X -1113(size)X -1265(can)X -1404(have)X -1583(a)X -1646(dramatic)X -1954(affect)X -2165(on)X -2271(result-)X -720 4966(ing)N -842(performance.)X -2 f -8 s -1269 4941(7)N -1 f -16 s -720 5353 MXY -864 0 Dl -2 f -8 s -760 5408(7)N -1 f -9 s -826 5433(Some)N -1024(allocators)X -1338(are)X -1460(extremely)X -1782(inef\256cient)X -2107(at)X -2192(allocating)X -720 5513(memory.)N -1029(If)X -1110(you)X -1251(\256nd)X -1396(that)X -1536(applications)X -1916(are)X -2036(running)X -2292(out)X -2416(of)X -720 5593(memory)N -1005(before)X -1234(you)X -1386(think)X -1578(they)X -1746(should,)X -2000(try)X -2124(varying)X -2388(the)X -720 5673(pagesize)N -986(to)X -1060(get)X -1166(better)X -1348(utilization)X -1658(from)X -1816(the)X -1922(memory)X -2180(allocator.)X -10 s -2830 1975 MXY -0 -28 Dl -28 0 Dl -0 28 Dl --28 0 Dl -2853 2004 MXY -0 -27 Dl -28 0 Dl -0 27 Dl --28 0 Dl -2876 2016 MXY -0 -27 Dl -27 0 Dl -0 27 Dl --27 0 Dl -2922 1998 MXY -0 -27 Dl -27 0 Dl -0 27 Dl --27 0 Dl -2967 2025 MXY -0 -28 Dl -28 0 Dl -0 28 Dl --28 0 Dl -3013 2031 MXY -0 -28 Dl -28 0 Dl -0 28 Dl --28 0 Dl -3059 MX -0 -28 Dl -27 0 Dl -0 28 Dl --27 0 Dl -3196 2052 MXY -0 -28 Dl -27 0 Dl -0 28 Dl --27 0 Dl -3561 2102 MXY -0 -28 Dl -28 0 Dl -0 28 Dl --28 0 Dl -4292 2105 MXY -0 -28 Dl -27 0 Dl -0 28 Dl --27 0 Dl -4 Ds -1 Dt -2844 1961 MXY -23 30 Dl -23 12 Dl -45 -18 Dl -46 26 Dl -46 6 Dl -45 0 Dl -137 21 Dl -366 50 Dl -730 3 Dl -9 s -4227 2158(User)N --1 Ds -3 Dt -2830 1211 MXY -27 Dc -2853 1261 MXY -27 Dc -2876 1267 MXY -27 Dc -2921 1341 MXY -27 Dc -2967 1385 MXY -27 Dc -3013 1450 MXY -27 Dc -3059 1497 MXY -27 Dc -3196 1686 MXY -27 Dc -3561 2109 MXY -27 Dc -4292 2295 MXY -27 Dc -20 Ds -1 Dt -2844 1211 MXY -23 50 Dl -23 6 Dl -45 74 Dl -46 44 Dl -46 65 Dl -45 47 Dl -137 189 Dl -366 423 Dl -730 186 Dl -4181 2270(System)N --1 Ds -3 Dt -2844 583 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2867 672 MXY -0 27 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -2890 701 MXY -0 28 Dl -0 -14 Dl -13 0 Dl --27 0 Dl -2935 819 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --27 0 Dl -2981 849 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -3027 908 MXY -0 27 Dl -0 -13 Dl -14 0 Dl --28 0 Dl -3072 1026 MXY -0 27 Dl -0 -13 Dl -14 0 Dl --27 0 Dl -3209 1292 MXY -0 27 Dl -0 -14 Dl -14 0 Dl --27 0 Dl -3575 1823 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --28 0 Dl -4305 2059 MXY -0 28 Dl -0 -14 Dl -14 0 Dl --27 0 Dl -5 Dt -2844 597 MXY -23 88 Dl -23 30 Dl -45 118 Dl -46 30 Dl -46 59 Dl -45 118 Dl -137 265 Dl -366 532 Dl -730 236 Dl -4328 2103(Total)N -2844 2310 MXY -1461 0 Dl -2844 MX -0 -1772 Dl -2310 MY -0 18 Dl -4 Ds -1 Dt -2310 MY -0 -1772 Dl -2826 2416(0)N --1 Ds -5 Dt -3209 2310 MXY -0 18 Dl -4 Ds -1 Dt -2310 MY -0 -1772 Dl -3155 2416(256)N --1 Ds -5 Dt -3575 2310 MXY -0 18 Dl -4 Ds -1 Dt -2310 MY -0 -1772 Dl -3521 2416(512)N --1 Ds -5 Dt -3940 2310 MXY -0 18 Dl -4 Ds -1 Dt -2310 MY -0 -1772 Dl -3886 2416(768)N --1 Ds -5 Dt -4305 2310 MXY -0 18 Dl -4 Ds -1 Dt -2310 MY -0 -1772 Dl -4233 2416(1024)N --1 Ds -5 Dt -2844 2310 MXY --18 0 Dl -4 Ds -1 Dt -2844 MX -1461 0 Dl -2771 2340(0)N --1 Ds -5 Dt -2844 2014 MXY --18 0 Dl -2844 1719 MXY --18 0 Dl -4 Ds -1 Dt -2844 MX -1461 0 Dl -2735 1749(20)N --1 Ds -5 Dt -2844 1423 MXY --18 0 Dl -2844 1128 MXY --18 0 Dl -4 Ds -1 Dt -2844 MX -1461 0 Dl -2735 1158(40)N --1 Ds -5 Dt -2844 833 MXY --18 0 Dl -2844 538 MXY --18 0 Dl -4 Ds -1 Dt -2844 MX -1461 0 Dl -2735 568(60)N -3239 2529(Buffer)N -3445(Pool)X -3595(Size)X -3737(\(in)X -3835(K\))X -2695 1259(S)N -2699 1324(e)N -2699 1388(c)N -2697 1452(o)N -2697 1517(n)N -2697 1581(d)N -2701 1645(s)N -3 Dt --1 Ds -3 f -8 s -2706 2773(Figure)N -2908(7:)X -1 f -2982(User)X -3123(time)X -3258(is)X -3322(virtually)X -3560(insensitive)X -3854(to)X -3924(the)X -4022(amount)X -4234(of)X -4307(buffer)X -2706 2861(pool)N -2852(available,)X -3130(however,)X -3396(both)X -3541(system)X -3750(time)X -3895(and)X -4018(elapsed)X -4240(time)X -4385(are)X -2706 2949(inversely)N -2960(proportional)X -3296(to)X -3366(the)X -3464(size)X -3583(of)X -3656(the)X -3753(buffer)X -3927(pool.)X -4092(Even)X -4242(for)X -4335(large)X -2706 3037(data)N -2831(sets)X -2946(where)X -3120(one)X -3230(expects)X -3439(few)X -3552(collisions,)X -3832(specifying)X -4116(a)X -4162(large)X -4307(buffer)X -2706 3125(pool)N -2836(dramatically)X -3171(improves)X -3425(performance.)X -10 s -10 f -2706 3301 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -3175 3543(Enhanced)N -3536(Functionality)X -1 f -2878 3675(This)N -3046(hashing)X -3320(package)X -3609(provides)X -3910(a)X -3971(set)X -4085(of)X -4177(compati-)X -2706 3763(bility)N -2895(routines)X -3174(to)X -3257(implement)X -3620(the)X -2 f -3739(ndbm)X -1 f -3937(interface.)X -4279(How-)X -2706 3851(ever,)N -2893(when)X -3095(the)X -3220(native)X -3443(interface)X -3752(is)X -3832(used,)X -4026(the)X -4151(following)X -2706 3939(additional)N -3046(functionality)X -3475(is)X -3548(provided:)X -10 f -2798 4071(g)N -1 f -2946(Inserts)X -3197(never)X -3413(fail)X -3556(because)X -3847(too)X -3985(many)X -4199(keys)X -2946 4159(hash)N -3113(to)X -3195(the)X -3313(same)X -3498(value.)X -10 f -2798 4247(g)N -1 f -2946(Inserts)X -3187(never)X -3393(fail)X -3527(because)X -3808(key)X -3950(and/or)X -4181(asso-)X -2946 4335(ciated)N -3158(data)X -3312(is)X -3385(too)X -3507(large)X -10 f -2798 4423(g)N -1 f -2946(Hash)X -3131(functions)X -3449(may)X -3607(be)X -3703(user-speci\256ed.)X -10 f -2798 4511(g)N -1 f -2946(Multiple)X -3268(pages)X -3498(may)X -3683(be)X -3806(cached)X -4077(in)X -4186(main)X -2946 4599(memory.)N -2706 4731(It)N -2801(also)X -2976(provides)X -3298(a)X -3380(set)X -3514(of)X -3626(compatibility)X -4097(routines)X -4400(to)X -2706 4819(implement)N -3087(the)X -2 f -3224(hsearch)X -1 f -3516(interface.)X -3876(Again,)X -4130(the)X -4266(native)X -2706 4907(interface)N -3008(offers)X -3216(enhanced)X -3540(functionality:)X -10 f -2798 5039(g)N -1 f -2946(Files)X -3121(may)X -3279(grow)X -3464(beyond)X -2 f -3720(nelem)X -1 f -3932(elements.)X -10 f -2798 5127(g)N -1 f -2946(Multiple)X -3247(hash)X -3420(tables)X -3632(may)X -3795(be)X -3896(accessed)X -4203(con-)X -2946 5215(currently.)N -10 f -2798 5303(g)N -1 f -2946(Hash)X -3134(tables)X -3344(may)X -3505(be)X -3604(stored)X -3823(and)X -3962(accessed)X -4266(on)X -2946 5391(disk.)N -10 f -2798 5479(g)N -1 f -2946(Hash)X -3155(functions)X -3497(may)X -3679(be)X -3799(user-speci\256ed)X -4288(at)X -2946 5567(runtime.)N -3 f -720 5960(USENIX)N -9 f -1042(-)X -3 f -1106(Winter)X -1371('91)X -9 f -1498(-)X -3 f -1562(Dallas,)X -1815(TX)X -4424(9)X - -10 p -%%Page: 10 10 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -432 258(A)N -510(New)X -682(Hashing)X -985(Package)X -1290(for)X -1413(UNIX)X -3663(Seltzer)X -3920(&)X -4007(Yigit)X -459 538(Relative)N -760(Performance)X -1227(of)X -1314(the)X -1441(New)X -1613(Implementation)X -1 f -604 670(The)N -761(performance)X -1200(testing)X -1445(of)X -1544(the)X -1674(new)X -1840(package)X -2135(is)X -432 758(divided)N -711(into)X -874(two)X -1033(test)X -1183(suites.)X -1424(The)X -1588(\256rst)X -1751(suite)X -1941(of)X -2046(tests)X -432 846(requires)N -727(that)X -882(the)X -1015(tables)X -1237(be)X -1348(read)X -1522(from)X -1713(and)X -1864(written)X -2126(to)X -432 934(disk.)N -640(In)X -742(these)X -942(tests,)X -1139(the)X -1272(basis)X -1467(for)X -1595(comparison)X -2003(is)X -2090(the)X -432 1022(4.3BSD-Reno)N -908(version)X -1169(of)X -2 f -1260(ndbm)X -1 f -1438(.)X -1502(Based)X -1722(on)X -1826(the)X -1948(designs)X -432 1110(of)N -2 f -521(sdbm)X -1 f -712(and)X -2 f -850(gdbm)X -1 f -1028(,)X -1070(they)X -1230(are)X -1351(expected)X -1659(to)X -1743(perform)X -2024(simi-)X -432 1198(larly)N -605(to)X -2 f -693(ndbm)X -1 f -871(,)X -917(and)X -1059(we)X -1179(do)X -1285(not)X -1413(show)X -1608(their)X -1781(performance)X -432 1286(numbers.)N -800(The)X -977(second)X -1252(suite)X -1454(contains)X -1772(the)X -1921(memory)X -432 1374(resident)N -712(test)X -849(which)X -1071(does)X -1243(not)X -1370(require)X -1623(that)X -1768(the)X -1891(\256les)X -2049(ever)X -432 1462(be)N -533(written)X -784(to)X -870(disk,)X -1047(only)X -1213(that)X -1357(hash)X -1528(tables)X -1739(may)X -1901(be)X -2001(mani-)X -432 1550(pulated)N -692(in)X -778(main)X -961(memory.)X -1291(In)X -1381(this)X -1519(test,)X -1673(we)X -1790(compare)X -2090(the)X -432 1638(performance)N -859(to)X -941(that)X -1081(of)X -1168(the)X -2 f -1286(hsearch)X -1 f -1560(routines.)X -604 1752(For)N -760(both)X -947(suites,)X -1194(two)X -1358(different)X -1679(databases)X -2031(were)X -432 1840(used.)N -656(The)X -818(\256rst)X -979(is)X -1069(the)X -1204(dictionary)X -1566(database)X -1880(described)X -432 1928(previously.)N -836(The)X -987(second)X -1236(was)X -1386(constructed)X -1781(from)X -1962(a)X -2023(pass-)X -432 2016(word)N -647(\256le)X -799(with)X -990(approximately)X -1502(300)X -1671(accounts.)X -2041(Two)X -432 2104(records)N -700(were)X -887(constructed)X -1287(for)X -1411(each)X -1589(account.)X -1909(The)X -2064(\256rst)X -432 2192(used)N -604(the)X -727(logname)X -1028(as)X -1120(the)X -1243(key)X -1384(and)X -1525(the)X -1648(remainder)X -1999(of)X -2090(the)X -432 2280(password)N -768(entry)X -965(for)X -1091(the)X -1221(data.)X -1427(The)X -1584(second)X -1839(was)X -1996(keyed)X -432 2368(by)N -541(uid)X -672(and)X -817(contained)X -1157(the)X -1283(entire)X -1494(password)X -1825(entry)X -2018(as)X -2113(its)X -432 2456(data)N -589(\256eld.)X -794(The)X -942(tests)X -1107(were)X -1287(all)X -1389(run)X -1518(on)X -1620(the)X -1740(HP)X -1864(9000)X -2046(with)X -432 2544(the)N -574(same)X -783(con\256guration)X -1254(previously)X -1636(described.)X -2027(Each)X -432 2632(test)N -576(was)X -734(run)X -874(\256ve)X -1027(times)X -1232(and)X -1380(the)X -1510(timing)X -1750(results)X -1991(of)X -2090(the)X -432 2720(runs)N -602(were)X -791(averaged.)X -1154(The)X -1311(variance)X -1616(across)X -1849(the)X -1979(5)X -2050(runs)X -432 2808(was)N -591(approximately)X -1088(1%)X -1229(of)X -1330(the)X -1462(average)X -1746(yielding)X -2041(95%)X -432 2896(con\256dence)N -800(intervals)X -1096(of)X -1183(approximately)X -1666(2%.)X -3 f -1021 3050(Disk)N -1196(Based)X -1420(Tests)X -1 f -604 3182(In)N -693(these)X -880(tests,)X -1064(we)X -1180(use)X -1308(a)X -1365(bucket)X -1600(size)X -1746(of)X -1834(1024)X -2015(and)X -2152(a)X -432 3270(\256ll)N -540(factor)X -748(of)X -835(32.)X -3 f -432 3384(create)N -663(test)X -1 f -547 3498(The)N -703(keys)X -881(are)X -1011(entered)X -1279(into)X -1433(the)X -1561(hash)X -1738(table,)X -1944(and)X -2090(the)X -547 3586(\256le)N -669(is)X -742(\257ushed)X -993(to)X -1075(disk.)X -3 f -432 3700(read)N -608(test)X -1 f -547 3814(A)N -640(lookup)X -897(is)X -984(performed)X -1353(for)X -1481(each)X -1663(key)X -1813(in)X -1909(the)X -2041(hash)X -547 3902(table.)N -3 f -432 4016(verify)N -653(test)X -1 f -547 4130(A)N -640(lookup)X -897(is)X -984(performed)X -1353(for)X -1481(each)X -1663(key)X -1813(in)X -1909(the)X -2041(hash)X -547 4218(table,)N -759(and)X -911(the)X -1045(data)X -1215(returned)X -1519(is)X -1608(compared)X -1961(against)X -547 4306(that)N -687(originally)X -1018(stored)X -1234(in)X -1316(the)X -1434(hash)X -1601(table.)X -3 f -432 4420(sequential)N -798(retrieve)X -1 f -547 4534(All)N -674(keys)X -846(are)X -970(retrieved)X -1281(in)X -1367(sequential)X -1716(order)X -1910(from)X -2090(the)X -547 4622(hash)N -724(table.)X -950(The)X -2 f -1105(ndbm)X -1 f -1313(interface)X -1625(allows)X -1863(sequential)X -547 4710(retrieval)N -848(of)X -948(the)X -1079(keys)X -1259(from)X -1448(the)X -1578(database,)X -1907(but)X -2041(does)X -547 4798(not)N -701(return)X -945(the)X -1094(data)X -1279(associated)X -1660(with)X -1853(each)X -2052(key.)X -547 4886(Therefore,)N -929(we)X -1067(compare)X -1388(the)X -1530(performance)X -1980(of)X -2090(the)X -547 4974(new)N -703(package)X -989(to)X -1073(two)X -1215(different)X -1514(runs)X -1674(of)X -2 f -1763(ndbm)X -1 f -1941(.)X -2002(In)X -2090(the)X -547 5062(\256rst)N -697(case,)X -2 f -882(ndbm)X -1 f -1086(returns)X -1335(only)X -1503(the)X -1627(keys)X -1800(while)X -2003(in)X -2090(the)X -547 5150(second,)N -2 f -823(ndbm)X -1 f -1034(returns)X -1290(both)X -1465(the)X -1596(keys)X -1776(and)X -1924(the)X -2054(data)X -547 5238(\(requiring)N -894(a)X -956(second)X -1204(call)X -1345(to)X -1432(the)X -1555(library\).)X -1861(There)X -2074(is)X -2152(a)X -547 5326(single)N -764(run)X -897(for)X -1017(the)X -1141(new)X -1300(library)X -1539(since)X -1729(it)X -1798(returns)X -2046(both)X -547 5414(the)N -665(key)X -801(and)X -937(the)X -1055(data.)X -3 f -3014 538(In-Memory)N -3431(Test)X -1 f -2590 670(This)N -2757(test)X -2892(uses)X -3054(a)X -3114(bucket)X -3352(size)X -3501(of)X -3592(256)X -3736(and)X -3876(a)X -3936(\256ll)X -4048(fac-)X -2418 758(tor)N -2527(of)X -2614(8.)X -3 f -2418 872(create/read)N -2827(test)X -1 f -2533 986(In)N -2627(this)X -2769(test,)X -2927(a)X -2989(hash)X -3162(table)X -3344(is)X -3423(created)X -3682(by)X -3788(inserting)X -4094(all)X -2533 1074(the)N -2660(key/data)X -2961(pairs.)X -3186(Then)X -3380(a)X -3445(keyed)X -3666(retrieval)X -3963(is)X -4044(per-)X -2533 1162(formed)N -2801(for)X -2931(each)X -3115(pair,)X -3295(and)X -3446(the)X -3579(hash)X -3761(table)X -3952(is)X -4040(des-)X -2533 1250(troyed.)N -3 f -2938 1404(Performance)N -3405(Results)X -1 f -2590 1536(Figures)N -2866(8a)X -2978(and)X -3130(8b)X -3246(show)X -3451(the)X -3585(user)X -3755(time,)X -3952(system)X -2418 1624(time,)N -2608(and)X -2752(elapsed)X -3021(time)X -3191(for)X -3312(each)X -3487(test)X -3625(for)X -3746(both)X -3915(the)X -4040(new)X -2418 1712(implementation)N -2951(and)X -3098(the)X -3227(old)X -3360(implementation)X -3893(\()X -2 f -3920(hsearch)X -1 f -2418 1800(or)N -2 f -2528(ndbm)X -1 f -2706(,)X -2769(whichever)X -3147(is)X -3243(appropriate\))X -3678(as)X -3787(well)X -3967(as)X -4076(the)X -2418 1888(improvement.)N -2929(The)X -3098(improvement)X -3569(is)X -3666(expressed)X -4027(as)X -4138(a)X -2418 1976(percentage)N -2787(of)X -2874(the)X -2992(old)X -3114(running)X -3383(time:)X -0 f -8 s -2418 2275(%)N -2494(=)X -2570(100)X -2722(*)X -2798 -0.4219(\(old_time)AX -3178(-)X -3254 -0.4219(new_time\))AX -3634(/)X -3710(old_time)X -1 f -10 s -2590 2600(In)N -2700(nearly)X -2944(all)X -3067(cases,)X -3299(the)X -3439(new)X -3615(routines)X -3915(perform)X -2418 2688(better)N -2628(than)X -2793(the)X -2918(old)X -3047(routines)X -3332(\(both)X -2 f -3527(hsearch)X -1 f -3807(and)X -2 f -3949(ndbm)X -1 f -4127(\).)X -2418 2776(Although)N -2755(the)X -3 f -2888(create)X -1 f -3134(tests)X -3311(exhibit)X -3567(superior)X -3864(user)X -4032(time)X -2418 2864(performance,)N -2869(the)X -2991(test)X -3126(time)X -3292(is)X -3369(dominated)X -3731(by)X -3834(the)X -3955(cost)X -4107(of)X -2418 2952(writing)N -2677(the)X -2803(actual)X -3023(\256le)X -3153(to)X -3243(disk.)X -3444(For)X -3583(the)X -3709(large)X -3897(database)X -2418 3040(\(the)N -2564(dictionary\),)X -2957(this)X -3093(completely)X -3470(overwhelmed)X -3927(the)X -4045(sys-)X -2418 3128(tem)N -2570(time.)X -2783(However,)X -3129(for)X -3254(the)X -3383(small)X -3587(data)X -3752(base,)X -3946(we)X -4071(see)X -2418 3216(that)N -2569(differences)X -2958(in)X -3051(both)X -3224(user)X -3389(and)X -3536(system)X -3788(time)X -3960(contri-)X -2418 3304(bute)N -2576(to)X -2658(the)X -2776(superior)X -3059(performance)X -3486(of)X -3573(the)X -3691(new)X -3845(package.)X -2590 3418(The)N -3 f -2764(read)X -1 f -2920(,)X -3 f -2989(verify)X -1 f -3190(,)X -3259(and)X -3 f -3424(sequential)X -1 f -3818(results)X -4075(are)X -2418 3506(deceptive)N -2758(for)X -2883(the)X -3012(small)X -3216(database)X -3524(since)X -3720(the)X -3849(entire)X -4063(test)X -2418 3594(ran)N -2551(in)X -2643(under)X -2856(a)X -2922(second.)X -3215(However,)X -3560(on)X -3669(the)X -3796(larger)X -4013(data-)X -2418 3682(base)N -2590(the)X -3 f -2716(read)X -1 f -2900(and)X -3 f -3044(verify)X -1 f -3273(tests)X -3443(bene\256t)X -3689(from)X -3873(the)X -3999(cach-)X -2418 3770(ing)N -2546(of)X -2639(buckets)X -2910(in)X -2998(the)X -3122(new)X -3282(package)X -3571(to)X -3658(improve)X -3950(perfor-)X -2418 3858(mance)N -2666(by)X -2784(over)X -2965(80%.)X -3169(Since)X -3384(the)X -3519(\256rst)X -3 f -3680(sequential)X -1 f -4063(test)X -2418 3946(does)N -2598(not)X -2733(require)X -2 f -2994(ndbm)X -1 f -3205(to)X -3299(return)X -3523(the)X -3653(data)X -3819(values,)X -4076(the)X -2418 4034(user)N -2573(time)X -2735(is)X -2808(lower)X -3011(than)X -3169(for)X -3283(the)X -3401(new)X -3555(package.)X -3879(However)X -2418 4122(when)N -2613(we)X -2728(require)X -2977(both)X -3139(packages)X -3454(to)X -3536(return)X -3748(data,)X -3922(the)X -4040(new)X -2418 4210(package)N -2702(excels)X -2923(in)X -3005(all)X -3105(three)X -3286(timings.)X -2590 4324(The)N -2773(small)X -3003(database)X -3337(runs)X -3532(so)X -3660(quickly)X -3957(in)X -4076(the)X -2418 4412(memory-resident)N -3000(case)X -3173(that)X -3326(the)X -3457(results)X -3699(are)X -3831(uninterest-)X -2418 4500(ing.)N -2589(However,)X -2933(for)X -3056(the)X -3183(larger)X -3400(database)X -3706(the)X -3833(new)X -3995(pack-)X -2418 4588(age)N -2567(pays)X -2751(a)X -2824(small)X -3033(penalty)X -3305(in)X -3403(system)X -3661(time)X -3839(because)X -4130(it)X -2418 4676(limits)N -2636(its)X -2748(main)X -2944(memory)X -3247(utilization)X -3607(and)X -3759(swaps)X -3991(pages)X -2418 4764(out)N -2550(to)X -2642(temporary)X -3002(storage)X -3264(in)X -3356(the)X -3484(\256le)X -3616(system)X -3868(while)X -4076(the)X -2 f -2418 4852(hsearch)N -1 f -2698(package)X -2988(requires)X -3273(that)X -3419(the)X -3543(application)X -3924(allocate)X -2418 4940(enough)N -2692(space)X -2909(for)X -3041(all)X -3159(key/data)X -3468(pair.)X -3670(However,)X -4022(even)X -2418 5028(with)N -2600(the)X -2738(system)X -3000(time)X -3182(penalty,)X -3477(the)X -3614(resulting)X -3933(elapsed)X -2418 5116(time)N -2580(improves)X -2898(by)X -2998(over)X -3161(50%.)X -3 f -432 5960(10)N -2970(USENIX)X -9 f -3292(-)X -3 f -3356(Winter)X -3621('91)X -9 f -3748(-)X -3 f -3812(Dallas,)X -4065(TX)X - -11 p -%%Page: 11 11 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -720 258(Seltzer)N -977(&)X -1064(Yigit)X -3278(A)X -3356(New)X -3528(Hashing)X -3831(Package)X -4136(for)X -4259(UNIX)X -1 f -10 f -908 454(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2 f -1379 546(hash)N -1652(ndbm)X -1950(%change)X -1 f -10 f -908 550(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -948 642(CREATE)N -10 f -908 646(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -1125 738(user)N -1424(6.4)X -1671(12.2)X -2073(48)X -1157 826(sys)N -1384(32.5)X -1671(34.7)X -2113(6)X -3 f -1006 914(elapsed)N -10 f -1310 922(c)N -890(c)Y -810(c)Y -730(c)Y -3 f -1384 914(90.4)N -10 f -1581 922(c)N -890(c)Y -810(c)Y -730(c)Y -3 f -1671 914(99.6)N -10 f -1883 922(c)N -890(c)Y -810(c)Y -730(c)Y -3 f -2113 914(9)N -1 f -10 f -908 910(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -908 926(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -948 1010(READ)N -10 f -908 1014(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -1125 1106(user)N -1424(3.4)X -1711(6.1)X -2073(44)X -1157 1194(sys)N -1424(1.2)X -1671(15.3)X -2073(92)X -3 f -1006 1282(elapsed)N -10 f -1310 1290(c)N -1258(c)Y -1178(c)Y -1098(c)Y -3 f -1424 1282(4.0)N -10 f -1581 1290(c)N -1258(c)Y -1178(c)Y -1098(c)Y -3 f -1671 1282(21.2)N -10 f -1883 1290(c)N -1258(c)Y -1178(c)Y -1098(c)Y -3 f -2073 1282(81)N -1 f -10 f -908 1278(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -908 1294(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -948 1378(VERIFY)N -10 f -908 1382(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -1125 1474(user)N -1424(3.5)X -1711(6.3)X -2073(44)X -1157 1562(sys)N -1424(1.2)X -1671(15.3)X -2073(92)X -3 f -1006 1650(elapsed)N -10 f -1310 1658(c)N -1626(c)Y -1546(c)Y -1466(c)Y -3 f -1424 1650(4.0)N -10 f -1581 1658(c)N -1626(c)Y -1546(c)Y -1466(c)Y -3 f -1671 1650(21.2)N -10 f -1883 1658(c)N -1626(c)Y -1546(c)Y -1466(c)Y -3 f -2073 1650(81)N -1 f -10 f -908 1646(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -908 1662(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -948 1746(SEQUENTIAL)N -10 f -908 1750(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -1125 1842(user)N -1424(2.7)X -1711(1.9)X -2046(-42)X -1157 1930(sys)N -1424(0.7)X -1711(3.9)X -2073(82)X -3 f -1006 2018(elapsed)N -10 f -1310 2026(c)N -1994(c)Y -1914(c)Y -1834(c)Y -3 f -1424 2018(3.0)N -10 f -1581 2026(c)N -1994(c)Y -1914(c)Y -1834(c)Y -3 f -1711 2018(5.0)N -10 f -1883 2026(c)N -1994(c)Y -1914(c)Y -1834(c)Y -3 f -2073 2018(40)N -1 f -10 f -908 2014(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -908 2030(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -948 2114(SEQUENTIAL)N -1467(\(with)X -1656(data)X -1810(retrieval\))X -10 f -908 2118(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -1125 2210(user)N -1424(2.7)X -1711(8.2)X -2073(67)X -1157 2298(sys)N -1424(0.7)X -1711(4.3)X -2073(84)X -3 f -1006 2386(elapsed)N -1424(3.0)X -1671(12.0)X -2073(75)X -1 f -10 f -908 2390(i)N -927(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -899 2394(c)N -2378(c)Y -2298(c)Y -2218(c)Y -2138(c)Y -2058(c)Y -1978(c)Y -1898(c)Y -1818(c)Y -1738(c)Y -1658(c)Y -1578(c)Y -1498(c)Y -1418(c)Y -1338(c)Y -1258(c)Y -1178(c)Y -1098(c)Y -1018(c)Y -938(c)Y -858(c)Y -778(c)Y -698(c)Y -618(c)Y -538(c)Y -1310 2394(c)N -2362(c)Y -2282(c)Y -2202(c)Y -1581 2394(c)N -2362(c)Y -2282(c)Y -2202(c)Y -1883 2394(c)N -2362(c)Y -2282(c)Y -2202(c)Y -2278 2394(c)N -2378(c)Y -2298(c)Y -2218(c)Y -2138(c)Y -2058(c)Y -1978(c)Y -1898(c)Y -1818(c)Y -1738(c)Y -1658(c)Y -1578(c)Y -1498(c)Y -1418(c)Y -1338(c)Y -1258(c)Y -1178(c)Y -1098(c)Y -1018(c)Y -938(c)Y -858(c)Y -778(c)Y -698(c)Y -618(c)Y -538(c)Y -905 2574(i)N -930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2 f -1318 2666(hash)N -1585(hsearch)X -1953(%change)X -1 f -10 f -905 2670(i)N -930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -945 2762(CREATE/READ)N -10 f -905 2766(i)N -930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -1064 2858(user)N -1343(6.6)X -1642(17.2)X -2096(62)X -1096 2946(sys)N -1343(1.1)X -1682(0.3)X -2029(-266)X -3 f -945 3034(elapsed)N -1343(7.8)X -1642(17.0)X -2096(54)X -1 f -10 f -905 3038(i)N -930(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -896 3050(c)N -2978(c)Y -2898(c)Y -2818(c)Y -2738(c)Y -2658(c)Y -1249 3034(c)N -3010(c)Y -2930(c)Y -2850(c)Y -1520 3034(c)N -3010(c)Y -2930(c)Y -2850(c)Y -1886 3034(c)N -3010(c)Y -2930(c)Y -2850(c)Y -2281 3050(c)N -2978(c)Y -2898(c)Y -2818(c)Y -2738(c)Y -2658(c)Y -3 f -720 3174(Figure)N -967(8a:)X -1 f -1094(Timing)X -1349(results)X -1578(for)X -1692(the)X -1810(dictionary)X -2155(database.)X -10 f -720 3262 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -1407 3504(Conclusion)N -1 f -892 3636(This)N -1063(paper)X -1271(has)X -1407(presented)X -1744(the)X -1871(design,)X -2129(implemen-)X -720 3724(tation)N -928(and)X -1070(performance)X -1503(of)X -1596(a)X -1658(new)X -1818(hashing)X -2093(package)X -2382(for)X -720 3812(UNIX.)N -993(The)X -1150(new)X -1316(package)X -1612(provides)X -1919(a)X -1986(superset)X -2280(of)X -2378(the)X -720 3900(functionality)N -1159(of)X -1255(existing)X -1537(hashing)X -1815(packages)X -2139(and)X -2284(incor-)X -720 3988(porates)N -975(additional)X -1318(features)X -1596(such)X -1766(as)X -1855(large)X -2038(key)X -2176(handling,)X -720 4076(user)N -876(de\256ned)X -1134(hash)X -1302(functions,)X -1641(multiple)X -1928(hash)X -2096(tables,)X -2324(vari-)X -720 4164(able)N -894(sized)X -1099(pages,)X -1342(and)X -1498(linear)X -1721(hashing.)X -2050(In)X -2156(nearly)X -2396(all)X -720 4252(cases,)N -954(the)X -1096(new)X -1274(package)X -1582(provides)X -1902(improved)X -2252(perfor-)X -720 4340(mance)N -974(on)X -1098(the)X -1240(order)X -1454(of)X -1565(50-80%)X -1863(for)X -2001(the)X -2142(workloads)X -720 4428(shown.)N -990(Applications)X -1420(such)X -1588(as)X -1676(the)X -1794(loader,)X -2035(compiler,)X -2360(and)X -720 4516(mail,)N -921(which)X -1156(currently)X -1485(implement)X -1866(their)X -2051(own)X -2227(hashing)X -720 4604(routines,)N -1032(should)X -1279(be)X -1389(modi\256ed)X -1706(to)X -1801(use)X -1941(the)X -2072(generic)X -2342(rou-)X -720 4692(tines.)N -892 4806(This)N -1087(hashing)X -1389(package)X -1705(is)X -1810(one)X -1978(access)X -2236(method)X -720 4894(which)N -953(is)X -1043(part)X -1205(of)X -1309(a)X -1382(generic)X -1656(database)X -1970(access)X -2212(package)X -720 4982(being)N -955(developed)X -1342(at)X -1457(the)X -1612(University)X -2007(of)X -2131(California,)X -720 5070(Berkeley.)N -1089(It)X -1177(will)X -1340(include)X -1614(a)X -1688(btree)X -1887(access)X -2131(method)X -2409(as)X -720 5158(well)N -916(as)X -1041(\256xed)X -1259(and)X -1433(variable)X -1750(length)X -2007(record)X -2270(access)X -720 5246(methods)N -1024(in)X -1119(addition)X -1414(to)X -1509(the)X -1640(hashed)X -1896(support)X -2168(presented)X -720 5334(here.)N -948(All)X -1099(of)X -1215(the)X -1361(access)X -1615(methods)X -1934(are)X -2081(based)X -2312(on)X -2440(a)X -720 5422(key/data)N -1037(pair)X -1207(interface)X -1533(and)X -1693(appear)X -1952(identical)X -2272(to)X -2378(the)X -720 5510(application)N -1121(layer,)X -1347(allowing)X -1671(application)X -2071(implementa-)X -720 5598(tions)N -906(to)X -999(be)X -1106(largely)X -1360(independent)X -1783(of)X -1881(the)X -2010(database)X -2318(type.)X -720 5686(The)N -873(package)X -1165(is)X -1246(expected)X -1560(to)X -1650(be)X -1754(an)X -1858(integral)X -2131(part)X -2284(of)X -2378(the)X -2706 538(4.4BSD)N -3006(system,)X -3293(with)X -3479(various)X -3759(standard)X -4075(applications)X -2706 626(such)N -2879(as)X -2972(more\(1\),)X -3277(sort\(1\))X -3517(and)X -3659(vi\(1\))X -3841(based)X -4050(on)X -4156(it.)X -4266(While)X -2706 714(the)N -2833(current)X -3089(design)X -3326(does)X -3501(not)X -3631(support)X -3899(multi-user)X -4256(access)X -2706 802(or)N -2804(transactions,)X -3238(they)X -3407(could)X -3616(be)X -3723(incorporated)X -4159(relatively)X -2706 890(easily.)N -10 f -2894 938(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2 f -3365 1030(hash)N -3638(ndbm)X -3936(%change)X -1 f -10 f -2894 1034(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -2934 1126(CREATE)N -10 f -2894 1130(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -3111 1222(user)N -3390(0.2)X -3677(0.4)X -4079(50)X -3143 1310(sys)N -3390(0.1)X -3677(1.0)X -4079(90)X -3 f -2992 1398(elapsed)N -10 f -3296 1406(c)N -1374(c)Y -1294(c)Y -1214(c)Y -3 f -3390 1398(0)N -10 f -3567 1406(c)N -1374(c)Y -1294(c)Y -1214(c)Y -3 f -3677 1398(3.2)N -10 f -3869 1406(c)N -1374(c)Y -1294(c)Y -1214(c)Y -3 f -4039 1398(100)N -1 f -10 f -2894 1394(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2894 1410(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -2934 1494(READ)N -10 f -2894 1498(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -3111 1590(user)N -3390(0.1)X -3677(0.1)X -4119(0)X -3143 1678(sys)N -3390(0.1)X -3677(0.4)X -4079(75)X -3 f -2992 1766(elapsed)N -10 f -3296 1774(c)N -1742(c)Y -1662(c)Y -1582(c)Y -3 f -3390 1766(0.0)N -10 f -3567 1774(c)N -1742(c)Y -1662(c)Y -1582(c)Y -3 f -3677 1766(0.0)N -10 f -3869 1774(c)N -1742(c)Y -1662(c)Y -1582(c)Y -3 f -4119 1766(0)N -1 f -10 f -2894 1762(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2894 1778(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -2934 1862(VERIFY)N -10 f -2894 1866(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -3111 1958(user)N -3390(0.1)X -3677(0.2)X -4079(50)X -3143 2046(sys)N -3390(0.1)X -3677(0.3)X -4079(67)X -3 f -2992 2134(elapsed)N -10 f -3296 2142(c)N -2110(c)Y -2030(c)Y -1950(c)Y -3 f -3390 2134(0.0)N -10 f -3567 2142(c)N -2110(c)Y -2030(c)Y -1950(c)Y -3 f -3677 2134(0.0)N -10 f -3869 2142(c)N -2110(c)Y -2030(c)Y -1950(c)Y -3 f -4119 2134(0)N -1 f -10 f -2894 2130(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2894 2146(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -2934 2230(SEQUENTIAL)N -10 f -2894 2234(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -3111 2326(user)N -3390(0.1)X -3677(0.0)X -4012(-100)X -3143 2414(sys)N -3390(0.1)X -3677(0.1)X -4119(0)X -3 f -2992 2502(elapsed)N -10 f -3296 2510(c)N -2478(c)Y -2398(c)Y -2318(c)Y -3 f -3390 2502(0.0)N -10 f -3567 2510(c)N -2478(c)Y -2398(c)Y -2318(c)Y -3 f -3677 2502(0.0)N -10 f -3869 2510(c)N -2478(c)Y -2398(c)Y -2318(c)Y -3 f -4119 2502(0)N -1 f -10 f -2894 2498(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2894 2514(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -2934 2598(SEQUENTIAL)N -3453(\(with)X -3642(data)X -3796(retrieval\))X -10 f -2894 2602(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -3111 2694(user)N -3390(0.1)X -3677(0.1)X -4119(0)X -3143 2782(sys)N -3390(0.1)X -3677(0.1)X -4119(0)X -3 f -2992 2870(elapsed)N -3390(0.0)X -3677(0.0)X -4119(0)X -1 f -10 f -2894 2874(i)N -2913(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2885 2878(c)N -2862(c)Y -2782(c)Y -2702(c)Y -2622(c)Y -2542(c)Y -2462(c)Y -2382(c)Y -2302(c)Y -2222(c)Y -2142(c)Y -2062(c)Y -1982(c)Y -1902(c)Y -1822(c)Y -1742(c)Y -1662(c)Y -1582(c)Y -1502(c)Y -1422(c)Y -1342(c)Y -1262(c)Y -1182(c)Y -1102(c)Y -1022(c)Y -3296 2878(c)N -2846(c)Y -2766(c)Y -2686(c)Y -3567 2878(c)N -2846(c)Y -2766(c)Y -2686(c)Y -3869 2878(c)N -2846(c)Y -2766(c)Y -2686(c)Y -4264 2878(c)N -2862(c)Y -2782(c)Y -2702(c)Y -2622(c)Y -2542(c)Y -2462(c)Y -2382(c)Y -2302(c)Y -2222(c)Y -2142(c)Y -2062(c)Y -1982(c)Y -1902(c)Y -1822(c)Y -1742(c)Y -1662(c)Y -1582(c)Y -1502(c)Y -1422(c)Y -1342(c)Y -1262(c)Y -1182(c)Y -1102(c)Y -1022(c)Y -2891 3058(i)N -2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2 f -3304 3150(hash)N -3571(hsearch)X -3939(%change)X -1 f -10 f -2891 3154(i)N -2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -2931 3246(CREATE/READ)N -10 f -2891 3250(i)N -2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -1 f -3050 3342(user)N -3329(0.3)X -3648(0.4)X -4048(25)X -3082 3430(sys)N -3329(0.0)X -3648(0.0)X -4088(0)X -3 f -2931 3518(elapsed)N -3329(0.0)X -3648(0.0)X -4088(0)X -1 f -10 f -2891 3522(i)N -2916(iiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiii)X -2882 3534(c)N -3462(c)Y -3382(c)Y -3302(c)Y -3222(c)Y -3142(c)Y -3235 3518(c)N -3494(c)Y -3414(c)Y -3334(c)Y -3506 3518(c)N -3494(c)Y -3414(c)Y -3334(c)Y -3872 3518(c)N -3494(c)Y -3414(c)Y -3334(c)Y -4267 3534(c)N -3462(c)Y -3382(c)Y -3302(c)Y -3222(c)Y -3142(c)Y -3 f -2706 3658(Figure)N -2953(8b:)X -1 f -3084(Timing)X -3339(results)X -3568(for)X -3682(the)X -3800(password)X -4123(database.)X -10 f -2706 3746 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN -3 f -3396 3988(References)N -1 f -2706 4120([ATT79])N -3058(AT&T,)X -3358(DBM\(3X\),)X -2 f -3773(Unix)X -3990(Programmer's)X -2878 4208(Manual,)N -3194(Seventh)X -3491(Edition,)X -3793(Volume)X -4085(1)X -1 f -(,)S -4192(January,)X -2878 4296(1979.)N -2706 4472([ATT85])N -3027(AT&T,)X -3296(HSEARCH\(BA_LIB\),)X -2 f -4053(Unix)X -4239(System)X -2878 4560(User's)N -3112(Manual,)X -3401(System)X -3644(V.3)X -1 f -3753(,)X -3793(pp.)X -3913(506-508,)X -4220(1985.)X -2706 4736([BRE73])N -3025(Brent,)X -3253(Richard)X -3537(P.,)X -3651(``Reducing)X -4041(the)X -4168(Retrieval)X -2878 4824(Time)N -3071(of)X -3162(Scatter)X -3409(Storage)X -3678(Techniques'',)X -2 f -4146(Commun-)X -2878 4912(ications)N -3175(of)X -3281(the)X -3422(ACM)X -1 f -3591(,)X -3654(Volume)X -3955(16,)X -4098(No.)X -4259(2,)X -4362(pp.)X -2878 5000(105-109,)N -3185(February,)X -3515(1973.)X -2706 5176([BSD86])N -3055(NDBM\(3\),)X -2 f -3469(4.3BSD)X -3775(Unix)X -3990(Programmer's)X -2878 5264(Manual)N -3155(Reference)X -3505(Guide)X -1 f -3701(,)X -3749(University)X -4114(of)X -4208(Califor-)X -2878 5352(nia,)N -3016(Berkeley,)X -3346(1986.)X -2706 5528([ENB88])N -3025(Enbody,)X -3319(R.)X -3417(J.,)X -3533(Du,)X -3676(H.)X -3779(C.,)X -3897(``Dynamic)X -4270(Hash-)X -2878 5616(ing)N -3034(Schemes'',)X -2 f -3427(ACM)X -3630(Computing)X -4019(Surveys)X -1 f -4269(,)X -4322(Vol.)X -2878 5704(20,)N -2998(No.)X -3136(2,)X -3216(pp.)X -3336(85-113,)X -3603(June)X -3770(1988.)X -3 f -720 5960(USENIX)N -9 f -1042(-)X -3 f -1106(Winter)X -1371('91)X -9 f -1498(-)X -3 f -1562(Dallas,)X -1815(TX)X -4384(11)X - -12 p -%%Page: 12 12 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -432 258(A)N -510(New)X -682(Hashing)X -985(Package)X -1290(for)X -1413(UNIX)X -3663(Seltzer)X -3920(&)X -4007(Yigit)X -1 f -432 538([FAG79])N -776(Ronald)X -1057(Fagin,)X -1308(Jurg)X -1495(Nievergelt,)X -1903(Nicholas)X -604 626(Pippenger,)N -1003(H.)X -1135(Raymond)X -1500(Strong,)X -1787(``Extendible)X -604 714(Hashing)N -901(--)X -985(A)X -1073(Fast)X -1236(Access)X -1493(Method)X -1771(for)X -1894(Dynamic)X -604 802(Files'',)N -2 f -855(ACM)X -1046(Transactions)X -1485(on)X -1586(Database)X -1914(Systems)X -1 f -2168(,)X -604 890(Volume)N -882(4,)X -962(No.)X -1100(3.,)X -1200(September)X -1563(1979,)X -1763(pp)X -1863(315-34)X -432 1066([KNU68],)N -802(Knuth,)X -1064(D.E.,)X -2 f -1273(The)X -1434(Art)X -1577(of)X -1680(Computer)X -2041(Pro-)X -604 1154(gramming)N -971(Vol.)X -1140(3:)X -1245(Sorting)X -1518(and)X -1676(Searching)X -1 f -2001(,)X -2058(sec-)X -604 1242(tions)N -779(6.3-6.4,)X -1046(pp)X -1146(481-550.)X -432 1418([LAR78])N -747(Larson,)X -1011(Per-Ake,)X -1319(``Dynamic)X -1687(Hashing'',)X -2 f -2048(BIT)X -1 f -(,)S -604 1506(Vol.)N -764(18,)X -884(1978,)X -1084(pp.)X -1204(184-201.)X -432 1682([LAR88])N -752(Larson,)X -1021(Per-Ake,)X -1335(``Dynamic)X -1709(Hash)X -1900(Tables'',)X -2 f -604 1770(Communications)N -1183(of)X -1281(the)X -1415(ACM)X -1 f -1584(,)X -1640(Volume)X -1934(31,)X -2070(No.)X -604 1858(4.,)N -704(April)X -893(1988,)X -1093(pp)X -1193(446-457.)X -432 2034([LIT80])N -731(Witold,)X -1013(Litwin,)X -1286(``Linear)X -1590(Hashing:)X -1939(A)X -2036(New)X -604 2122(Tool)N -786(for)X -911(File)X -1065(and)X -1211(Table)X -1424(Addressing'',)X -2 f -1893(Proceed-)X -604 2210(ings)N -761(of)X -847(the)X -969(6th)X -1095(International)X -1540(Conference)X -1933(on)X -2036(Very)X -604 2298(Large)N -815(Databases)X -1 f -1153(,)X -1193(1980.)X -432 2474([NEL90])N -743(Nelson,)X -1011(Philip)X -1222(A.,)X -2 f -1341(Gdbm)X -1558(1.4)X -1679(source)X -1913(distribu-)X -604 2562(tion)N -748(and)X -888(README)X -1 f -1209(,)X -1249(August)X -1500(1990.)X -432 2738([THOM90])N -840(Ken)X -1011(Thompson,)X -1410(private)X -1670(communication,)X -604 2826(Nov.)N -782(1990.)X -432 3002([TOR87])N -790(Torek,)X -1066(C.,)X -1222(``Re:)X -1470(dbm.a)X -1751(and)X -1950(ndbm.a)X -604 3090(archives'',)N -2 f -966(USENET)X -1279(newsgroup)X -1650(comp.unix)X -1 f -2002(1987.)X -432 3266([TOR88])N -760(Torek,)X -1006(C.,)X -1133(``Re:)X -1351(questions)X -1686(regarding)X -2027(data-)X -604 3354(bases)N -826(created)X -1106(with)X -1295(dbm)X -1484(and)X -1647(ndbm)X -1876(routines'')X -2 f -604 3442(USENET)N -937(newsgroup)X -1328(comp.unix.questions)X -1 f -1982(,)X -2041(June)X -604 3530(1988.)N -432 3706([WAL84])N -773(Wales,)X -1018(R.,)X -1135(``Discussion)X -1564(of)X -1655("dbm")X -1887(data)X -2045(base)X -604 3794(system'',)N -2 f -973(USENET)X -1339(newsgroup)X -1762(unix.wizards)X -1 f -2168(,)X -604 3882(January,)N -894(1984.)X -432 4058([YIG89])N -751(Ozan)X -963(S.)X -1069(Yigit,)X -1294(``How)X -1545(to)X -1648(Roll)X -1826(Your)X -2032(Own)X -604 4146(Dbm/Ndbm'',)N -2 f -1087(unpublished)X -1504(manuscript)X -1 f -(,)S -1910(Toronto,)X -604 4234(July,)N -777(1989)X -3 f -432 5960(12)N -2970(USENIX)X -9 f -3292(-)X -3 f -3356(Winter)X -3621('91)X -9 f -3748(-)X -3 f -3812(Dallas,)X -4065(TX)X - -13 p -%%Page: 13 13 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -720 258(Seltzer)N -977(&)X -1064(Yigit)X -3278(A)X -3356(New)X -3528(Hashing)X -3831(Package)X -4136(for)X -4259(UNIX)X -1 f -720 538(Margo)N -960(I.)X -1033(Seltzer)X -1282(is)X -1361(a)X -1423(Ph.D.)X -1631(student)X -1887(in)X -1974(the)X -2097(Department)X -720 626(of)N -823(Electrical)X -1167(Engineering)X -1595(and)X -1747(Computer)X -2102(Sciences)X -2418(at)X -720 714(the)N -850(University)X -1220(of)X -1318(California,)X -1694(Berkeley.)X -2055(Her)X -2207(research)X -720 802(interests)N -1017(include)X -1283(\256le)X -1415(systems,)X -1718(databases,)X -2076(and)X -2221(transac-)X -720 890(tion)N -896(processing)X -1291(systems.)X -1636(She)X -1807(spent)X -2027(several)X -2306(years)X -720 978(working)N -1026(at)X -1123(startup)X -1380(companies)X -1762(designing)X -2112(and)X -2267(imple-)X -720 1066(menting)N -1048(\256le)X -1216(systems)X -1535(and)X -1716(transaction)X -2133(processing)X -720 1154(software)N -1026(and)X -1170(designing)X -1509(microprocessors.)X -2103(Ms.)X -2253(Seltzer)X -720 1242(received)N -1057(her)X -1223(AB)X -1397(in)X -1522(Applied)X -1843(Mathematics)X -2320(from)X -720 1330 0.1953(Harvard/Radcliffe)AN -1325(College)X -1594(in)X -1676(1983.)X -720 1444(In)N -810(her)X -936(spare)X -1129(time,)X -1313(Margo)X -1549(can)X -1683(usually)X -1936(be)X -2034(found)X -2243(prepar-)X -720 1532(ing)N -868(massive)X -1171(quantities)X -1527(of)X -1639(food)X -1831(for)X -1970(hungry)X -2242(hoards,)X -720 1620(studying)N -1022(Japanese,)X -1355(or)X -1449(playing)X -1716(soccer)X -1948(with)X -2116(an)X -2218(exciting)X -720 1708(Bay)N -912(Area)X -1132(Women's)X -1507(Soccer)X -1788(team,)X -2026(the)X -2186(Berkeley)X -720 1796(Bruisers.)N -720 1910(Ozan)N -915(\()X -3 f -942(Oz)X -1 f -1040(\))X -1092(Yigit)X -1281(is)X -1358(currently)X -1672(a)X -1732(software)X -2033(engineer)X -2334(with)X -720 1998(the)N -886(Communications)X -1499(Research)X -1861(and)X -2044(Development)X -720 2086(group,)N -948(Computing)X -1328(Services,)X -1641(York)X -1826(University.)X -2224(His)X -2355(for-)X -720 2174(mative)N -967(years)X -1166(were)X -1352(also)X -1510(spent)X -1708(at)X -1795(York,)X -2009(where)X -2234(he)X -2338(held)X -720 2262(system)N -985(programmer)X -1425(and)X -1583(administrator)X -2052(positions)X -2382(for)X -720 2350(various)N -995(mixtures)X -1314(of)X -1420(of)X -1526(UNIX)X -1765(systems)X -2056(starting)X -2334(with)X -720 2438(Berkeley)N -1031(4.1)X -1151(in)X -1233(1982,)X -1433(while)X -1631(at)X -1709(the)X -1827(same)X -2012(time)X -2174(obtaining)X -720 2526(a)N -776(degree)X -1011(in)X -1093(Computer)X -1433(Science.)X -720 2640(In)N -813(his)X -931(copious)X -1205(free)X -1356(time,)X -1543(Oz)X -1662(enjoys)X -1896(working)X -2188(on)X -2293(what-)X -720 2728(ever)N -890(software)X -1197(looks)X -1400(interesting,)X -1788(which)X -2014(often)X -2209(includes)X -720 2816(language)N -1044(interpreters,)X -1464(preprocessors,)X -1960(and)X -2110(lately,)X -2342(pro-)X -720 2904(gram)N -905(generators)X -1260(and)X -1396(expert)X -1617(systems.)X -720 3018(Oz)N -836(has)X -964(authored)X -1266(several)X -1515(public-domain)X -2003(software)X -2301(tools,)X -720 3106(including)N -1069(an)X -1191(nroff-like)X -1545(text)X -1711(formatter)X -2 f -2056(proff)X -1 f -2257(that)X -2423(is)X -720 3194(apparently)N -1083(still)X -1226(used)X -1397(in)X -1483(some)X -1676(basement)X -2002(PCs.)X -2173(His)X -2307(latest)X -720 3282(obsessions)N -1143(include)X -1460(the)X -1639(incredible)X -2040(programming)X -720 3370(language)N -1030(Scheme,)X -1324(and)X -1460(Chinese)X -1738(Brush)X -1949(painting.)X -3 f -720 5960(USENIX)N -9 f -1042(-)X -3 f -1106(Winter)X -1371('91)X -9 f -1498(-)X -3 f -1562(Dallas,)X -1815(TX)X -4384(13)X - -14 p -%%Page: 14 14 -0(Courier)xf 0 f -10 s 10 xH 0 xS 0 f -3 f -432 5960(14)N -2970(USENIX)X -9 f -3292(-)X -3 f -3356(Winter)X -3621('91)X -9 f -3748(-)X -3 f -3812(Dallas,)X -4065(TX)X - -14 p -%%Trailer -xt - -xs |