MySQL数据库

开发平台：

Visual C++

hash_usenix.ps：源码内容

%!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
% 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(ef256cient)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(over257ows)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(modi256ed)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(identi256es)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(simpli256cation)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(simpli256ed)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(re256nements)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(re256nements)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(simpli256cations)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(de256ned)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((speci256ed)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(de256ne)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(modi256ed)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(de256ned)X
3016(and)X
3155(declaring)X
3477(and)X
3616(de256ning)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(de256ning)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(shuf257e)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(shuf257ing)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(de256ning)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(de256ning)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(speci256ed)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(speci256c)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(over257ows))X
3944(while)X
2 f
4155(dynahash)X
1 f
2706 1792(splits)N
2933(in)X
3054(a)X
3149(prede256ned)X
3547(order)X
3776((linearly))X
4134(and)X
4309(at)X
4426(a)X
2706 1880(prede256ned)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(prede256ned)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(over257ows)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(Over257ow)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(over257ow,)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(over257ow))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(dif256cult)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(over257ow)X
3413(pages)X
3636(are)X
3775(required)X
4083(for)X
4217(buckets)X
2706 5034(which)N
2935(over257ow)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(over257ow)X
3264(pages.)X
3511(Logically,)X
3862(we)X
3980(chain)X
4177(over257ow)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(over257ow)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(over257ow)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(over257ow)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(over257ow)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(over257ow)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(over257ow)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(Over257ow)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(over257ow)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(over257ow)N
752(pages)X
970(within)X
1209(the)X
1342(same)X
1542(256le.)X
1699(Over257ow)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(over257ow)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(over257ow)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(over257ow)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(over257ow)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(over257ow)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(over257ow)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(Over257ow)N
3285(Addresses)X
3515 2833(Over257ow)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(Over257ow)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(over257ow)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(over257ow)X
2418 4479(pages)N
2628(are)X
2754 0.4028(referenced)AX
3122(logically)X
3429(by)X
3536(their)X
3710(over257ow)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(ef256cient)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(ef256cient)X
3372(access)X
3600(to)X
3684(over257ow)X
3991(pages)X
2418 5473(is)N
2501(provided)X
2816(by)X
2926(linking)X
3182(over257ow)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