Usenet 1994 January/usenetsourcesnewsgroupsinfomagicjanuary1994.iso/sources/unix/volume26/db-1.6/part09

Text File | 1993-07-05 | 90.0 KB | 6,179 lines

Newsgroups: comp.sources.unix
From: [e-mail] (Keith Bostic)
Subject: v26i288: db-1.6 - A New Hashing Package for UNIX(tm) (updates dbm/ndbm), Part09/09
Sender: [e-mail]
Approved: [e-mail]

Submitted-By: [e-mail] (Keith Bostic)
Posting-Number: Volume 26, Issue 288
Archive-Name: db-1.6/part09

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 9 (of 9)."
# Contents:  doc/hash.ps.01
# Wrapped by [e-mail] on Mon Jul  5 15:27:31 1993
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'doc/hash.ps.01' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'doc/hash.ps.01'\"
else
echo shar: Extracting \"'doc/hash.ps.01'\" \(84295 characters\)
sed "s/^X//" >'doc/hash.ps.01' <<'END_OF_FILE'
X%!PS-Adobe-1.0
X%%Creator: utopia:margo (& Seltzer,608-13E,8072,)
X%%Title: stdin (ditroff)
X%%CreationDate: Tue Dec 11 15:06:45 1990
X%%EndComments
X%    @(#)psdit.pro    1.3 4/15/88
X% lib/psdit.pro -- prolog for psdit (ditroff) files
X% Copyright (c) 1984, 1985 Adobe Systems Incorporated. All Rights Reserved.
X% last edit: shore Sat Nov 23 20:28:03 1985
X% RCSID: $Header: psdit.pro,v 2.1 85/11/24 12:19:43 shore Rel $
X
X% Changed by Edward Wang ([e-mail]) to handle graphics,
X% 17 Feb, 87.
X
X/$DITroff 140 dict def $DITroff begin
X/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
X/xi{0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
X /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
X /pagesave save def}def
X/PB{save /psv exch def currentpoint translate
X resolution 72 div dup neg scale 0 0 moveto}def
X/PE{psv restore}def
X/arctoobig 90 def /arctoosmall .05 def
X/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
X/tan{dup sin exch cos div}def
X/point{resolution 72 div mul}def
X/dround    {transform round exch round exch itransform}def
X/xT{/devname exch def}def
X/xr{/mh exch def /my exch def /resolution exch def}def
X/xp{}def
X/xs{docsave restore end}def
X/xt{}def
X/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
X {fonts slotno fontname findfont put fontnames slotno fontname put}if}def
X/xH{/fontheight exch def F}def
X/xS{/fontslant exch def F}def
X/s{/fontsize exch def /fontheight fontsize def F}def
X/f{/fontnum exch def F}def
X/F{fontheight 0 le{/fontheight fontsize def}if
X fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
X fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
X makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def
X/X{exch currentpoint exch pop moveto show}def
X/N{3 1 roll moveto show}def
X/Y{exch currentpoint pop exch moveto show}def
X/S{show}def
X/ditpush{}def/ditpop{}def
X/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def
X/AN{4 2 roll moveto 0 exch ashow}def
X/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def
X/AS{0 exch ashow}def
X/MX{currentpoint exch pop moveto}def
X/MY{currentpoint pop exch moveto}def
X/MXY{moveto}def
X/cb{pop}def    % action on unknown char -- nothing for now
X/n{}def/w{}def
X/p{pop showpage pagesave restore /pagesave save def}def
X/Dt{/Dlinewidth exch def}def 1 Dt
X/Ds{/Ddash exch def}def -1 Ds
X/Di{/Dstipple exch def}def 1 Di
X/Dsetlinewidth{2 Dlinewidth mul setlinewidth}def
X/Dsetdash{Ddash 4 eq{[8 12]}{Ddash 16 eq{[32 36]}
X {Ddash 20 eq{[32 12 8 12]}{[]}ifelse}ifelse}ifelse 0 setdash}def
X/Dstroke{gsave Dsetlinewidth Dsetdash 1 setlinecap stroke grestore
X currentpoint newpath moveto}def
X/Dl{rlineto Dstroke}def
X/arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop
X currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
X currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def
X/Dc{dup arcellipse Dstroke}def
X/De{arcellipse Dstroke}def
X/Da{/endv exch def /endh exch def /centerv exch def /centerh exch def
X /cradius centerv centerv mul centerh centerh mul add sqrt def
X /eradius endv endv mul endh endh mul add sqrt def
X /endang endv endh atan def
X /startang centerv neg centerh neg atan def
X /sweep startang endang sub dup 0 lt{360 add}if def
X sweep arctoobig gt
X {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def
X  /midh midang cos midrad mul def /midv midang sin midrad mul def
X  midh neg midv neg endh endv centerh centerv midh midv Da
X  Da}
X {sweep arctoosmall ge
X  {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def
X   centerv neg controldelt mul centerh controldelt mul
X   endv neg controldelt mul centerh add endh add
X   endh controldelt mul centerv add endv add
X   centerh endh add centerv endv add rcurveto Dstroke}
X  {centerh endh add centerv endv add rlineto Dstroke}
X  ifelse}
X ifelse}def
X/Dpatterns[
X[%cf[widthbits]
X[8<0000000000000010>]
X[8<0411040040114000>]
X[8<0204081020408001>]
X[8<0000103810000000>]
X[8<6699996666999966>]
X[8<0000800100001008>]
X[8<81c36666c3810000>]
X[8<0f0e0c0800000000>]
X[8<0000000000000010>]
X[8<0411040040114000>]
X[8<0204081020408001>]
X[8<0000001038100000>]
X[8<6699996666999966>]
X[8<0000800100001008>]
X[8<81c36666c3810000>]
X[8<0f0e0c0800000000>]
X[8<0042660000246600>]
X[8<0000990000990000>]
X[8<0804020180402010>]
X[8<2418814242811824>]
X[8<6699996666999966>]
X[8<8000000008000000>]
X[8<00001c3e363e1c00>]
X[8<0000000000000000>]
X[32<00000040000000c00000004000000040000000e0000000000000000000000000>]
X[32<00000000000060000000900000002000000040000000f0000000000000000000>]
X[32<000000000000000000e0000000100000006000000010000000e0000000000000>]
X[32<00000000000000002000000060000000a0000000f00000002000000000000000>]
X[32<0000000e0000000000000000000000000000000f000000080000000e00000001>]
X[32<0000090000000600000000000000000000000000000007000000080000000e00>]
X[32<00010000000200000004000000040000000000000000000000000000000f0000>]
X[32<0900000006000000090000000600000000000000000000000000000006000000>]]
X[%ug
X[8<0000020000000000>]
X[8<0000020000002000>]
X[8<0004020000002000>]
X[8<0004020000402000>]
X[8<0004060000402000>]
X[8<0004060000406000>]
X[8<0006060000406000>]
X[8<0006060000606000>]
X[8<00060e0000606000>]
X[8<00060e000060e000>]
X[8<00070e000060e000>]
X[8<00070e000070e000>]
X[8<00070e020070e000>]
X[8<00070e020070e020>]
X[8<04070e020070e020>]
X[8<04070e024070e020>]
X[8<04070e064070e020>]
X[8<04070e064070e060>]
X[8<06070e064070e060>]
X[8<06070e066070e060>]
X[8<06070f066070e060>]
X[8<06070f066070f060>]
X[8<060f0f066070f060>]
X[8<060f0f0660f0f060>]
X[8<060f0f0760f0f060>]
X[8<060f0f0760f0f070>]
X[8<0e0f0f0760f0f070>]
X[8<0e0f0f07e0f0f070>]
X[8<0e0f0f0fe0f0f070>]
X[8<0e0f0f0fe0f0f0f0>]
X[8<0f0f0f0fe0f0f0f0>]
X[8<0f0f0f0ff0f0f0f0>]
X[8<1f0f0f0ff0f0f0f0>]
X[8<1f0f0f0ff1f0f0f0>]
X[8<1f0f0f8ff1f0f0f0>]
X[8<1f0f0f8ff1f0f0f8>]
X[8<9f0f0f8ff1f0f0f8>]
X[8<9f0f0f8ff9f0f0f8>]
X[8<9f0f0f9ff9f0f0f8>]
X[8<9f0f0f9ff9f0f0f9>]
X[8<9f8f0f9ff9f0f0f9>]
X[8<9f8f0f9ff9f8f0f9>]
X[8<9f8f1f9ff9f8f0f9>]
X[8<9f8f1f9ff9f8f1f9>]
X[8<bf8f1f9ff9f8f1f9>]
X[8<bf8f1f9ffbf8f1f9>]
X[8<bf8f1fdffbf8f1f9>]
X[8<bf8f1fdffbf8f1fd>]
X[8<ff8f1fdffbf8f1fd>]
X[8<ff8f1fdffff8f1fd>]
X[8<ff8f1ffffff8f1fd>]
X[8<ff8f1ffffff8f1ff>]
X[8<ff9f1ffffff8f1ff>]
X[8<ff9f1ffffff9f1ff>]
X[8<ff9f9ffffff9f1ff>]
X[8<ff9f9ffffff9f9ff>]
X[8<ffbf9ffffff9f9ff>]
X[8<ffbf9ffffffbf9ff>]
X[8<ffbfdffffffbf9ff>]
X[8<ffbfdffffffbfdff>]
X[8<ffffdffffffbfdff>]
X[8<ffffdffffffffdff>]
X[8<fffffffffffffdff>]
X[8<ffffffffffffffff>]]
X[%mg
X[8<8000000000000000>]
X[8<0822080080228000>]
X[8<0204081020408001>]
X[8<40e0400000000000>]
X[8<66999966>]
X[8<8001000010080000>]
X[8<81c36666c3810000>]
X[8<f0e0c08000000000>]
X[16<07c00f801f003e007c00f800f001e003c007800f001f003e007c00f801f003e0>]
X[16<1f000f8007c003e001f000f8007c003e001f800fc007e003f001f8007c003e00>]
X[8<c3c300000000c3c3>]
X[16<0040008001000200040008001000200040008000000100020004000800100020>]
X[16<0040002000100008000400020001800040002000100008000400020001000080>]
X[16<1fc03fe07df0f8f8f07de03fc01f800fc01fe03ff07df8f87df03fe01fc00f80>]
X[8<80>]
X[8<8040201000000000>]
X[8<84cc000048cc0000>]
X[8<9900009900000000>]
X[8<08040201804020100800020180002010>]
X[8<2418814242811824>]
X[8<66999966>]
X[8<8000000008000000>]
X[8<70f8d8f870000000>]
X[8<0814224180402010>]
X[8<aa00440a11a04400>]
X[8<018245aa45820100>]
X[8<221c224180808041>]
X[8<88000000>]
X[8<0855800080550800>]
X[8<2844004482440044>]
X[8<0810204080412214>]
X[8<00>]]]def
X/Dfill{
X transform /maxy exch def /maxx exch def
X transform /miny exch def /minx exch def
X minx maxx gt{/minx maxx /maxx minx def def}if
X miny maxy gt{/miny maxy /maxy miny def def}if
X Dpatterns Dstipple 1 sub get exch 1 sub get
X aload pop /stip exch def /stipw exch def /stiph 128 def
X /imatrix[stipw 0 0 stiph 0 0]def
X /tmatrix[stipw 0 0 stiph 0 0]def
X /minx minx cvi stiph idiv stiph mul def
X /miny miny cvi stipw idiv stipw mul def
X gsave eoclip 0 setgray
X miny stiph maxy{
X  tmatrix exch 5 exch put
X  minx stipw maxx{
X   tmatrix exch 4 exch put tmatrix setmatrix
X   stipw stiph true imatrix {stip} imagemask
X  }for
X }for
X grestore
X}def
X/Dp{Dfill Dstroke}def
X/DP{Dfill currentpoint newpath moveto}def
Xend
X
X/ditstart{$DITroff begin
X /nfonts 60 def            % NFONTS makedev/ditroff dependent!
X /fonts[nfonts{0}repeat]def
X /fontnames[nfonts{()}repeat]def
X/docsave save def
X}def
X
X% character outcalls
X/oc{
X /pswid exch def /cc exch def /name exch def
X /ditwid pswid fontsize mul resolution mul 72000 div def
X /ditsiz fontsize resolution mul 72 div def
X ocprocs name known{ocprocs name get exec}{name cb}ifelse
X}def
X/fractm [.65 0 0 .6 0 0] def
X/fraction{
X /fden exch def /fnum exch def gsave /cf currentfont def
X cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
X fnum show rmoveto currentfont cf setfont(\244)show setfont fden show
X grestore ditwid 0 rmoveto
X}def
X/oce{grestore ditwid 0 rmoveto}def
X/dm{ditsiz mul}def
X/ocprocs 50 dict def ocprocs begin
X(14){(1)(4)fraction}def
X(12){(1)(2)fraction}def
X(34){(3)(4)fraction}def
X(13){(1)(3)fraction}def
X(23){(2)(3)fraction}def
X(18){(1)(8)fraction}def
X(38){(3)(8)fraction}def
X(58){(5)(8)fraction}def
X(78){(7)(8)fraction}def
X(sr){gsave 0 .06 dm rmoveto(\326)show oce}def
X(is){gsave 0 .15 dm rmoveto(\362)show oce}def
X(->){gsave 0 .02 dm rmoveto(\256)show oce}def
X(<-){gsave 0 .02 dm rmoveto(\254)show oce}def
X(==){gsave 0 .05 dm rmoveto(\272)show oce}def
X(uc){gsave currentpoint 400 .009 dm mul add translate
X     8 -8 scale ucseal oce}def
Xend
X
X% an attempt at a PostScript FONT to implement ditroff special chars
X% this will enable us to
X%    cache the little buggers
X%    generate faster, more compact PS out of psdit
X%    confuse everyone (including myself)!
X50 dict dup begin
X/FontType 3 def
X/FontName /DIThacks def
X/FontMatrix [.001 0 0 .001 0 0] def
X/FontBBox [-260 -260 900 900] def% a lie but ...
X/Encoding 256 array def
X0 1 255{Encoding exch /.notdef put}for
XEncoding
X dup 8#040/space put %space
X dup 8#110/rc put %right ceil
X dup 8#111/lt put %left  top curl
X dup 8#112/bv put %bold vert
X dup 8#113/lk put %left  mid curl
X dup 8#114/lb put %left  bot curl
X dup 8#115/rt put %right top curl
X dup 8#116/rk put %right mid curl
X dup 8#117/rb put %right bot curl
X dup 8#120/rf put %right floor
X dup 8#121/lf put %left  floor
X dup 8#122/lc put %left  ceil
X dup 8#140/sq put %square
X dup 8#141/bx put %box
X dup 8#142/ci put %circle
X dup 8#143/br put %box rule
X dup 8#144/rn put %root extender
X dup 8#145/vr put %vertical rule
X dup 8#146/ob put %outline bullet
X dup 8#147/bu put %bullet
X dup 8#150/ru put %rule
X dup 8#151/ul put %underline
X pop
X/DITfd 100 dict def
X/BuildChar{0 begin
X /cc exch def /fd exch def
X /charname fd /Encoding get cc get def
X /charwid fd /Metrics get charname get def
X /charproc fd /CharProcs get charname get def
X charwid 0 fd /FontBBox get aload pop setcachedevice
X 2 setlinejoin 40 setlinewidth
X newpath 0 0 moveto gsave charproc grestore
X end}def
X/BuildChar load 0 DITfd put
X/CharProcs 50 dict def
XCharProcs begin
X/space{}def
X/.notdef{}def
X/ru{500 0 rls}def
X/rn{0 840 moveto 500 0 rls}def
X/vr{0 800 moveto 0 -770 rls}def
X/bv{0 800 moveto 0 -1000 rls}def
X/br{0 840 moveto 0 -1000 rls}def
X/ul{0 -140 moveto 500 0 rls}def
X/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
X/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
X/sq{80 0 rmoveto currentpoint dround newpath moveto
X    640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
X/bx{80 0 rmoveto currentpoint dround newpath moveto
X    640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
X/ci{500 360 rmoveto currentpoint newpath 333 0 360 arc
X    50 setlinewidth stroke}def
X
X/lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
X/lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
X/rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
X/rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
X/lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub
X    0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
X/rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub
X    0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
X/lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def
X/rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
X/lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def
X/rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
Xend
X
X/Metrics 50 dict def Metrics begin
X/.notdef 0 def
X/space 500 def
X/ru 500 def
X/br 0 def
X/lt 416 def
X/lb 416 def
X/rt 416 def
X/rb 416 def
X/lk 416 def
X/rk 416 def
X/rc 416 def
X/lc 416 def
X/rf 416 def
X/lf 416 def
X/bv 416 def
X/ob 350 def
X/bu 350 def
X/ci 750 def
X/bx 750 def
X/sq 750 def
X/rn 500 def
X/ul 500 def
X/vr 0 def
Xend
X
XDITfd begin
X/s2 500 def /s4 250 def /s3 333 def
X/a4p{arcto pop pop pop pop}def
X/2cx{2 copy exch}def
X/rls{rlineto stroke}def
X/currx{currentpoint pop}def
X/dround{transform round exch round exch itransform} def
Xend
Xend
X/DIThacks exch definefont pop
Xditstart
X(psc)xT
X576 1 1 xr
X1(Times-Roman)xf 1 f
X2(Times-Italic)xf 2 f
X3(Times-Bold)xf 3 f
X4(Times-BoldItalic)xf 4 f
X5(Helvetica)xf 5 f
X6(Helvetica-Bold)xf 6 f
X7(Courier)xf 7 f
X8(Courier-Bold)xf 8 f
X9(Symbol)xf 9 f
X10(DIThacks)xf 10 f
X10 s
X1 f
Xxi
X%%EndProlog
X
X%%Page: 1 1
X10 s 10 xH 0 xS 1 f
X3 f
X22 s
X1249 626(A)N
X1420(N)X
X1547(ew)X
X1796(H)X
X1933(ashing)X
X2467(P)X
X2574(ackage)X
X3136(for)X
X3405(U)X
X3532(N)X
X3659(IX)X
X2 f
X20 s
X3855 562(1)N
X1 f
X12 s
X1607 779(Margo)N
X1887(Seltzer)X
X9 f
X2179(-)X
X1 f
X2256(University)X
X2686(of)X
X2790(California,)X
X3229(Berkeley)X
X2015 875(Ozan)N
X2242(Yigit)X
X9 f
X2464(-)X
X1 f
X2541(York)X
X2762(University)X
X3 f
X2331 1086(ABSTRACT)N
X1 f
X10 s
X1152 1222(UNIX)N
X1385(support)X
X1657(of)X
X1756(disk)X
X1921(oriented)X
X2216(hashing)X
X2497(was)X
X2654(originally)X
X2997(provided)X
X3314(by)X
X2 f
X3426(dbm)X
X1 f
X3595([ATT79])X
X3916(and)X
X1152 1310(subsequently)N
X1595(improved)X
X1927(upon)X
X2112(in)X
X2 f
X2199(ndbm)X
X1 f
X2402([BSD86].)X
X2735(In)X
X2826(AT&T)X
X3068(System)X
X3327(V,)X
X3429(in-memory)X
X3809(hashed)X
X1152 1398(storage)N
X1420(and)X
X1572(access)X
X1814(support)X
X2090(was)X
X2251(added)X
X2479(in)X
X2577(the)X
X2 f
X2711(hsearch)X
X1 f
X3000(library)X
X3249(routines)X
X3542([ATT85].)X
X3907(The)X
X1152 1486(result)N
X1367(is)X
X1457(a)X
X1530(system)X
X1789(with)X
X1968(two)X
X2125(incompatible)X
X2580(hashing)X
X2865(schemes,)X
X3193(each)X
X3377(with)X
X3555(its)X
X3666(own)X
X3840(set)X
X3965(of)X
X1152 1574(shortcomings.)N
X1152 1688(This)N
X1316(paper)X
X1517(presents)X
X1802(the)X
X1922(design)X
X2152(and)X
X2289(performance)X
X2717(characteristics)X
X3198(of)X
X3286(a)X
X3343(new)X
X3498(hashing)X
X3768(package)X
X1152 1776(providing)N
X1483(a)X
X1539(superset)X
X1822(of)X
X1909(the)X
X2027(functionality)X
X2456(provided)X
X2761(by)X
X2 f
X2861(dbm)X
X1 f
X3019(and)X
X2 f
X3155(hsearch)X
X1 f
X3409(.)X
X3469(The)X
X3614(new)X
X3768(package)X
X1152 1864(uses)N
X1322(linear)X
X1537(hashing)X
X1818(to)X
X1912(provide)X
X2189(ef\256cient)X
X2484(support)X
X2755(of)X
X2853(both)X
X3026(memory)X
X3324(based)X
X3538(and)X
X3685(disk)X
X3849(based)X
X1152 1952(hash)N
X1319(tables)X
X1526(with)X
X1688(performance)X
X2115(superior)X
X2398(to)X
X2480(both)X
X2 f
X2642(dbm)X
X1 f
X2800(and)X
X2 f
X2936(hsearch)X
X1 f
X3210(under)X
X3413(most)X
X3588(conditions.)X
X3 f
X1380 2128(Introduction)N
X1 f
X892 2260(Current)N
X1196(UNIX)X
X1456(systems)X
X1768(offer)X
X1984(two)X
X2163(forms)X
X2409(of)X
X720 2348(hashed)N
X973(data)X
X1137(access.)X
X2 f
X1413(Dbm)X
X1 f
X1599(and)X
X1745(its)X
X1850(derivatives)X
X2231(provide)X
X720 2436(keyed)N
X939(access)X
X1171(to)X
X1259(disk)X
X1418(resident)X
X1698(data)X
X1858(while)X
X2 f
X2062(hsearch)X
X1 f
X2342(pro-)X
X720 2524(vides)N
X929(access)X
X1175(for)X
X1309(memory)X
X1616(resident)X
X1910(data.)X
X2124(These)X
X2356(two)X
X720 2612(access)N
X979(methods)X
X1302(are)X
X1453(incompatible)X
X1923(in)X
X2037(that)X
X2209(memory)X
X720 2700(resident)N
X1011(hash)X
X1195(tables)X
X1419(may)X
X1593(not)X
X1731(be)X
X1843(stored)X
X2075(on)X
X2191(disk)X
X2360(and)X
X720 2788(disk)N
X884(resident)X
X1169(tables)X
X1387(cannot)X
X1632(be)X
X1739(read)X
X1909(into)X
X2063(memory)X
X2360(and)X
X720 2876(accessed)N
X1022(using)X
X1215(the)X
X1333(in-memory)X
X1709(routines.)X
X2 f
X892 2990(Dbm)N
X1 f
X1091(has)X
X1241(several)X
X1512(shortcomings.)X
X2026(Since)X
X2247(data)X
X2423(is)X
X720 3078(assumed)N
X1032(to)X
X1130(be)X
X1242(disk)X
X1411(resident,)X
X1721(each)X
X1905(access)X
X2146(requires)X
X2440(a)X
X720 3166(system)N
X963(call,)X
X1120(and)X
X1257(almost)X
X1491(certainly,)X
X1813(a)X
X1869(disk)X
X2022(operation.)X
X2365(For)X
X720 3254(extremely)N
X1072(large)X
X1264(databases,)X
X1623(where)X
X1851(caching)X
X2131(is)X
X2214(unlikely)X
X720 3342(to)N
X810(be)X
X914(effective,)X
X1244(this)X
X1386(is)X
X1466(acceptable,)X
X1853(however,)X
X2177(when)X
X2378(the)X
X720 3430(database)N
X1022(is)X
X1100(small)X
X1298(\(i.e.)X
X1447(the)X
X1569(password)X
X1896(\256le\),)X
X2069(performance)X
X720 3518(improvements)N
X1204(can)X
X1342(be)X
X1443(obtained)X
X1744(through)X
X2018(caching)X
X2293(pages)X
X720 3606(of)N
X818(the)X
X947(database)X
X1255(in)X
X1348(memory.)X
X1685(In)X
X1782(addition,)X
X2 f
X2094(dbm)X
X1 f
X2262(cannot)X
X720 3694(store)N
X902(data)X
X1062(items)X
X1261(whose)X
X1492(total)X
X1660(key)X
X1802(and)X
X1943(data)X
X2102(size)X
X2252(exceed)X
X720 3782(the)N
X850(page)X
X1034(size)X
X1191(of)X
X1290(the)X
X1420(hash)X
X1599(table.)X
X1827(Similarly,)X
X2176(if)X
X2257(two)X
X2409(or)X
X720 3870(more)N
X907(keys)X
X1076(produce)X
X1357(the)X
X1477(same)X
X1664(hash)X
X1833(value)X
X2029(and)X
X2166(their)X
X2334(total)X
X720 3958(size)N
X876(exceeds)X
X1162(the)X
X1291(page)X
X1474(size,)X
X1650(the)X
X1779(table)X
X1966(cannot)X
X2210(store)X
X2396(all)X
X720 4046(the)N
X838(colliding)X
X1142(keys.)X
X892 4160(The)N
X1050(in-memory)X
X2 f
X1439(hsearch)X
X1 f
X1725(routines)X
X2015(have)X
X2199(different)X
X720 4248(shortcomings.)N
X1219(First,)X
X1413(the)X
X1539(notion)X
X1771(of)X
X1865(a)X
X1928(single)X
X2146(hash)X
X2320(table)X
X720 4336(is)N
X807(embedded)X
X1171(in)X
X1266(the)X
X1397(interface,)X
X1732(preventing)X
X2108(an)X
X2217(applica-)X
X720 4424(tion)N
X902(from)X
X1116(accessing)X
X1482(multiple)X
X1806(tables)X
X2050(concurrently.)X
X720 4512(Secondly,)N
X1063(the)X
X1186(routine)X
X1438(to)X
X1525(create)X
X1743(a)X
X1804(hash)X
X1976(table)X
X2157(requires)X
X2440(a)X
X720 4600(parameter)N
X1066(which)X
X1286(declares)X
X1573(the)X
X1694(size)X
X1842(of)X
X1932(the)X
X2053(hash)X
X2223(table.)X
X2422(If)X
X720 4688(this)N
X856(size)X
X1001(is)X
X1074(set)X
X1183(too)X
X1305(low,)X
X1465(performance)X
X1892(degradation)X
X2291(or)X
X2378(the)X
X720 4776(inability)N
X1008(to)X
X1092(add)X
X1230(items)X
X1425(to)X
X1509(the)X
X1628(table)X
X1805(may)X
X1964(result.)X
X2223(In)X
X2311(addi-)X
X720 4864(tion,)N
X2 f
X910(hsearch)X
X1 f
X1210(requires)X
X1515(that)X
X1681(the)X
X1825(application)X
X2226(allocate)X
X720 4952(memory)N
X1037(for)X
X1181(the)X
X1329(key)X
X1495(and)X
X1661(data)X
X1845(items.)X
X2108(Lastly,)X
X2378(the)X
X2 f
X720 5040(hsearch)N
X1 f
X1013(routines)X
X1310(provide)X
X1594(no)X
X1713(interface)X
X2034(to)X
X2135(store)X
X2329(hash)X
X720 5128(tables)N
X927(on)X
X1027(disk.)X
X16 s
X720 5593 MXY
X864 0 Dl
X2 f
X8 s
X760 5648(1)N
X1 f
X9 s
X5673(UNIX)Y
X990(is)X
X1056(a)X
X1106(registered)X
X1408(trademark)X
X1718(of)X
X1796(AT&T.)X
X10 s
X2878 2128(The)N
X3032(goal)X
X3199(of)X
X3295(our)X
X3431(work)X
X3625(was)X
X3779(to)X
X3870(design)X
X4108(and)X
X4253(imple-)X
X2706 2216(ment)N
X2900(a)X
X2970(new)X
X3138(package)X
X3436(that)X
X3590(provides)X
X3899(a)X
X3968(superset)X
X4264(of)X
X4364(the)X
X2706 2304(functionality)N
X3144(of)X
X3240(both)X
X2 f
X3411(dbm)X
X1 f
X3578(and)X
X2 f
X3723(hsearch)X
X1 f
X3977(.)X
X4045(The)X
X4198(package)X
X2706 2392(had)N
X2871(to)X
X2982(overcome)X
X3348(the)X
X3495(interface)X
X3826(shortcomings)X
X4306(cited)X
X2706 2480(above)N
X2930(and)X
X3078(its)X
X3185(implementation)X
X3719(had)X
X3867(to)X
X3961(provide)X
X4238(perfor-)X
X2706 2568(mance)N
X2942(equal)X
X3142(or)X
X3235(superior)X
X3524(to)X
X3612(that)X
X3758(of)X
X3851(the)X
X3975(existing)X
X4253(imple-)X
X2706 2656(mentations.)N
X3152(In)X
X3274(order)X
X3498(to)X
X3614(provide)X
X3913(a)X
X4003(compact)X
X4329(disk)X
X2706 2744(representation,)N
X3224(graceful)X
X3531(table)X
X3729(growth,)X
X4018(and)X
X4176(expected)X
X2706 2832(constant)N
X3033(time)X
X3234(performance,)X
X3720(we)X
X3873(selected)X
X4191(Litwin's)X
X2706 2920(linear)N
X2923(hashing)X
X3206(algorithm)X
X3551([LAR88,)X
X3872(LIT80].)X
X4178(We)X
X4324(then)X
X2706 3008(enhanced)N
X3037(the)X
X3161(algorithm)X
X3498(to)X
X3586(handle)X
X3826(page)X
X4004(over\257ows)X
X4346(and)X
X2706 3096(large)N
X2900(key)X
X3049(handling)X
X3362(with)X
X3537(a)X
X3606(single)X
X3830(mechanism,)X
X4248(named)X
X2706 3184(buddy-in-waiting.)N
X3 f
X2975 3338(Existing)N
X3274(UNIX)X
X3499(Hashing)X
X3802(Techniques)X
X1 f
X2878 3470(Over)N
X3076(the)X
X3210(last)X
X3357(decade,)X
X3637(several)X
X3901(dynamic)X
X4213(hashing)X
X2706 3558(schemes)N
X3000(have)X
X3174(been)X
X3348(developed)X
X3700(for)X
X3816(the)X
X3936(UNIX)X
X4159(timeshar-)X
X2706 3646(ing)N
X2856(system,)X
X3146(starting)X
X3433(with)X
X3622(the)X
X3767(inclusion)X
X4107(of)X
X2 f
X4221(dbm)X
X1 f
X4359(,)X
X4426(a)X
X2706 3734(minimal)N
X3008(database)X
X3321(library)X
X3571(written)X
X3834(by)X
X3950(Ken)X
X4120(Thompson)X
X2706 3822([THOM90],)N
X3141(in)X
X3248(the)X
X3391(Seventh)X
X3694(Edition)X
X3974(UNIX)X
X4220(system.)X
X2706 3910(Since)N
X2916(then,)X
X3106(an)X
X3214(extended)X
X3536(version)X
X3804(of)X
X3903(the)X
X4032(same)X
X4228(library,)X
X2 f
X2706 3998(ndbm)N
X1 f
X2884(,)X
X2933(and)X
X3078(a)X
X3142(public-domain)X
X3637(clone)X
X3839(of)X
X3934(the)X
X4060(latter,)X
X2 f
X4273(sdbm)X
X1 f
X4442(,)X
X2706 4086(have)N
X2902(been)X
X3098(developed.)X
X3491(Another)X
X3797 0.1645(interface-compatible)AX
X2706 4174(library)N
X2 f
X2950(gdbm)X
X1 f
X3128(,)X
X3178(was)X
X3333(recently)X
X3622(made)X
X3826(available)X
X4145(as)X
X4241(part)X
X4395(of)X
X2706 4262(the)N
X2829(Free)X
X2997(Software)X
X3312(Foundation's)X
X3759(\(FSF\))X
X3970(software)X
X4271(distri-)X
X2706 4350(bution.)N
X2878 4464(All)N
X3017(of)X
X3121(these)X
X3323(implementations)X
X3893(are)X
X4029(based)X
X4248(on)X
X4364(the)X
X2706 4552(idea)N
X2871(of)X
X2969(revealing)X
X3299(just)X
X3445(enough)X
X3711(bits)X
X3856(of)X
X3953(a)X
X4019(hash)X
X4196(value)X
X4400(to)X
X2706 4640(locate)N
X2920(a)X
X2978(page)X
X3151(in)X
X3234(a)X
X3291(single)X
X3503(access.)X
X3770(While)X
X2 f
X3987(dbm/ndbm)X
X1 f
X4346(and)X
X2 f
X2706 4728(sdbm)N
X1 f
X2908(map)X
X3079(the)X
X3210(hash)X
X3390(value)X
X3597(directly)X
X3874(to)X
X3968(a)X
X4036(disk)X
X4201(address,)X
X2 f
X2706 4816(gdbm)N
X1 f
X2921(uses)X
X3096(the)X
X3231(hash)X
X3414(value)X
X3624(to)X
X3722(index)X
X3936(into)X
X4096(a)X
X2 f
X4168(directory)X
X1 f
X2706 4904([ENB88])N
X3020(containing)X
X3378(disk)X
X3531(addresses.)X
X2878 5018(The)N
X2 f
X3033(hsearch)X
X1 f
X3317(routines)X
X3605(in)X
X3697(System)X
X3962(V)X
X4049(are)X
X4177(designed)X
X2706 5106(to)N
X2804(provide)X
X3085(memory-resident)X
X3669(hash)X
X3852(tables.)X
X4115(Since)X
X4328(data)X
X2706 5194(access)N
X2948(does)X
X3131(not)X
X3269(require)X
X3533(disk)X
X3702(access,)X
X3964(simple)X
X4213(hashing)X
X2706 5282(schemes)N
X3010(which)X
X3238(may)X
X3408(require)X
X3667(multiple)X
X3964(probes)X
X4209(into)X
X4364(the)X
X2706 5370(table)N
X2889(are)X
X3015(used.)X
X3209(A)X
X3294(more)X
X3486(interesting)X
X3851(version)X
X4114(of)X
X2 f
X4208(hsearch)X
X1 f
X2706 5458(is)N
X2784(a)X
X2845(public)X
X3070(domain)X
X3335(library,)X
X2 f
X3594(dynahash)X
X1 f
X3901(,)X
X3945(that)X
X4089(implements)X
X2706 5546(Larson's)N
X3036(in-memory)X
X3440(adaptation)X
X3822([LAR88])X
X4164(of)X
X4279(linear)X
X2706 5634(hashing)N
X2975([LIT80].)X
X3 f
X720 5960(USENIX)N
X9 f
X1042(-)X
X3 f
X1106(Winter)X
X1371('91)X
X9 f
X1498(-)X
X3 f
X1562(Dallas,)X
X1815(TX)X
X1 f
X4424(1)X
X
X2 p
X%%Page: 2 2
X10 s 10 xH 0 xS 1 f
X3 f
X432 258(A)N
X510(New)X
X682(Hashing)X
X985(Package)X
X1290(for)X
X1413(UNIX)X
X3663(Seltzer)X
X3920(&)X
X4007(Yigit)X
X2 f
X1074 538(dbm)N
X1 f
X1232(and)X
X2 f
X1368(ndbm)X
X1 f
X604 670(The)N
X2 f
X760(dbm)X
X1 f
X928(and)X
X2 f
X1074(ndbm)X
X1 f
X1282(library)X
X1526(implementations)X
X2089(are)X
X432 758(based)N
X667(on)X
X799(the)X
X949(same)X
X1166(algorithm)X
X1529(by)X
X1661(Ken)X
X1846(Thompson)X
X432 846([THOM90,)N
X824(TOR88,)X
X1113(WAL84],)X
X1452(but)X
X1582(differ)X
X1789(in)X
X1879(their)X
X2054(pro-)X
X432 934(grammatic)N
X801(interfaces.)X
X1160(The)X
X1311(latter)X
X1502(is)X
X1581(a)X
X1643(modi\256ed)X
X1952(version)X
X432 1022(of)N
X533(the)X
X665(former)X
X918(which)X
X1148(adds)X
X1328(support)X
X1601(for)X
X1728(multiple)X
X2027(data-)X
X432 1110(bases)N
X634(to)X
X724(be)X
X828(open)X
X1011(concurrently.)X
X1484(The)X
X1636(discussion)X
X1996(of)X
X2090(the)X
X432 1198(algorithm)N
X774(that)X
X925(follows)X
X1196(is)X
X1280(applicable)X
X1640(to)X
X1732(both)X
X2 f
X1904(dbm)X
X1 f
X2072(and)X
X2 f
X432 1286(ndbm)N
X1 f
X610(.)X
X604 1400(The)N
X760(basic)X
X956(structure)X
X1268(of)X
X2 f
X1366(dbm)X
X1 f
X1535(calls)X
X1712(for)X
X1836(\256xed-sized)X
X432 1488(disk)N
X612(blocks)X
X868(\(buckets\))X
X1214(and)X
X1377(an)X
X2 f
X1499(access)X
X1 f
X1755(function)X
X2068(that)X
X432 1576(maps)N
X623(a)X
X681(key)X
X819(to)X
X902(a)X
X959(bucket.)X
X1234(The)X
X1380(interface)X
X1683(routines)X
X1962(use)X
X2090(the)X
X2 f
X432 1664(access)N
X1 f
X673(function)X
X970(to)X
X1062(obtain)X
X1292(the)X
X1420(appropriate)X
X1816(bucket)X
X2060(in)X
X2152(a)X
X432 1752(single)N
X643(disk)X
X796(access.)X
X604 1866(Within)N
X869(the)X
X2 f
X1010(access)X
X1 f
X1263(function,)X
X1593(a)X
X1672(bit-randomizing)X
X432 1954(hash)N
X610(function)X
X2 f
X8 s
X877 1929(2)N
X1 f
X10 s
X940 1954(is)N
X1024(used)X
X1202(to)X
X1294(convert)X
X1565(a)X
X1631(key)X
X1777(into)X
X1931(a)X
X1997(32-bit)X
X432 2042(hash)N
X605(value.)X
X825(Out)X
X971(of)X
X1064(these)X
X1254(32)X
X1359(bits,)X
X1519(only)X
X1686(as)X
X1778(many)X
X1981(bits)X
X2121(as)X
X432 2130(necessary)N
X773(are)X
X900(used)X
X1075(to)X
X1165(determine)X
X1514(the)X
X1639(particular)X
X1974(bucket)X
X432 2218(on)N
X533(which)X
X750(a)X
X807(key)X
X944(resides.)X
X1228(An)X
X1347(in-memory)X
X1724(bitmap)X
X1967(is)X
X2041(used)X
X432 2306(to)N
X533(determine)X
X893(how)X
X1070(many)X
X1287(bits)X
X1441(are)X
X1579(required.)X
X1905(Each)X
X2104(bit)X
X432 2394(indicates)N
X746(whether)X
X1033(its)X
X1136(associated)X
X1494(bucket)X
X1736(has)X
X1871(been)X
X2051(split)X
X432 2482(yet)N
X562(\(a)X
X657(0)X
X728(indicating)X
X1079(that)X
X1230(the)X
X1359(bucket)X
X1604(has)X
X1742(not)X
X1875(yet)X
X2004(split\).)X
X432 2570(The)N
X590(use)X
X730(of)X
X830(the)X
X961(hash)X
X1141(function)X
X1441(and)X
X1590(the)X
X1720(bitmap)X
X1974(is)X
X2059(best)X
X432 2658(described)N
X769(by)X
X878(stepping)X
X1177(through)X
X1454(database)X
X1759(creation)X
X2046(with)X
X432 2746(multiple)N
X718(invocations)X
X1107(of)X
X1194(a)X
X2 f
X1250(store)X
X1 f
X1430(operation.)X
X604 2860(Initially,)N
X906(the)X
X1033(hash)X
X1209(table)X
X1394(contains)X
X1690(a)X
X1755(single)X
X1974(bucket)X
X432 2948(\(bucket)N
X711(0\),)X
X836(the)X
X972(bit)X
X1094(map)X
X1270(contains)X
X1575(a)X
X1649(single)X
X1878(bit)X
X2000(\(bit)X
X2148(0)X
X432 3036(corresponding)N
X913(to)X
X997(bucket)X
X1233(0\),)X
X1342(and)X
X1480(0)X
X1542(bits)X
X1699(of)X
X1788(a)X
X1846(hash)X
X2014(value)X
X432 3124(are)N
X560(examined)X
X901(to)X
X992(determine)X
X1342(where)X
X1568(a)X
X1633(key)X
X1778(is)X
X1860(placed)X
X2099(\(in)X
X432 3212(bucket)N
X670(0\).)X
X801(When)X
X1017(bucket)X
X1255(0)X
X1319(is)X
X1396(full,)X
X1551(its)X
X1650(bit)X
X1758(in)X
X1844(the)X
X1966(bitmap)X
X432 3300(\(bit)N
X564(0\))X
X652(is)X
X726(set,)X
X856(and)X
X993(its)X
X1089(contents)X
X1377(are)X
X1497(split)X
X1655(between)X
X1943(buckets)X
X432 3388(0)N
X499(and)X
X641(1,)X
X727(by)X
X833(considering)X
X1233(the)X
X1357(0)X
X2 f
X7 s
X3356(th)Y
X10 s
X1 f
X1480 3388(bit)N
X1590(\(the)X
X1741(lowest)X
X1976(bit)X
X2086(not)X
X432 3476(previously)N
X800(examined\))X
X1169(of)X
X1266(the)X
X1393(hash)X
X1569(value)X
X1772(for)X
X1895(each)X
X2072(key)X
X432 3564(within)N
X668(the)X
X798(bucket.)X
X1064(Given)X
X1292(a)X
X1359(well-designed)X
X1840(hash)X
X2018(func-)X
X432 3652(tion,)N
X613(approximately)X
X1112(half)X
X1273(of)X
X1376(the)X
X1510(keys)X
X1693(will)X
X1853(have)X
X2041(hash)X
X432 3740(values)N
X666(with)X
X837(the)X
X964(0)X
X2 f
X7 s
X3708(th)Y
X10 s
X1 f
X1090 3740(bit)N
X1203(set.)X
X1341(All)X
X1471(such)X
X1646(keys)X
X1821(and)X
X1965(associ-)X
X432 3828(ated)N
X586(data)X
X740(are)X
X859(moved)X
X1097(to)X
X1179(bucket)X
X1413(1,)X
X1493(and)X
X1629(the)X
X1747(rest)X
X1883(remain)X
X2126(in)X
X432 3916(bucket)N
X666(0.)X
X604 4030(After)N
X804(this)X
X949(split,)X
X1135(the)X
X1262(\256le)X
X1393(now)X
X1560(contains)X
X1856(two)X
X2005(buck-)X
X432 4118(ets,)N
X562(and)X
X699(the)X
X818(bitmap)X
X1061(contains)X
X1349(three)X
X1530(bits:)X
X1687(the)X
X1805(0)X
X2 f
X7 s
X4086(th)Y
X10 s
X1 f
X1922 4118(bit)N
X2026(is)X
X2099(set)X
X432 4206(to)N
X525(indicate)X
X810(a)X
X876(bucket)X
X1120(0)X
X1190(split)X
X1357(when)X
X1561(no)X
X1671(bits)X
X1816(of)X
X1913(the)X
X2041(hash)X
X432 4294(value)N
X648(are)X
X789(considered,)X
X1199(and)X
X1357(two)X
X1519(more)X
X1726(unset)X
X1937(bits)X
X2094(for)X
X432 4382(buckets)N
X706(0)X
X775(and)X
X920(1.)X
X1029(The)X
X1183(placement)X
X1542(of)X
X1638(an)X
X1742(incoming)X
X2072(key)X
X432 4470(now)N
X604(requires)X
X897(examination)X
X1327(of)X
X1428(the)X
X1560(0)X
X2 f
X7 s
X4438(th)Y
X10 s
X1 f
X1691 4470(bit)N
X1809(of)X
X1910(the)X
X2041(hash)X
X432 4558(value,)N
X667(and)X
X824(the)X
X963(key)X
X1119(is)X
X1212(placed)X
X1462(either)X
X1685(in)X
X1787(bucket)X
X2041(0)X
X2121(or)X
X432 4646(bucket)N
X674(1.)X
X782(If)X
X864(either)X
X1075(bucket)X
X1317(0)X
X1385(or)X
X1480(bucket)X
X1722(1)X
X1790(\256lls)X
X1937(up,)X
X2064(it)X
X2135(is)X
X432 4734(split)N
X598(as)X
X693(before,)X
X947(its)X
X1050(bit)X
X1162(is)X
X1243(set)X
X1360(in)X
X1450(the)X
X1576(bitmap,)X
X1846(and)X
X1990(a)X
X2054(new)X
X432 4822(set)N
X541(of)X
X628(unset)X
X817(bits)X
X952(are)X
X1071(added)X
X1283(to)X
X1365(the)X
X1483(bitmap.)X
X604 4936(Each)N
X791(time)X
X959(we)X
X1079(consider)X
X1376(a)X
X1437(new)X
X1596(bit)X
X1705(\(bit)X
X1841(n\),)X
X1953(we)X
X2072(add)X
X432 5024(2)N
X2 f
X7 s
X4992(n)Y
X9 f
X509(+)X
X1 f
X540(1)X
X10 s
X595 5024(bits)N
X737(to)X
X826(the)X
X951(bitmap)X
X1199(and)X
X1341(obtain)X
X1567(2)X
X2 f
X7 s
X4992(n)Y
X9 f
X1644(+)X
X1 f
X1675(1)X
X10 s
X1729 5024(more)N
X1920(address-)X
X432 5112(able)N
X595(buckets)X
X869(in)X
X960(the)X
X1087(\256le.)X
X1258(As)X
X1376(a)X
X1441(result,)X
X1668(the)X
X1795(bitmap)X
X2045(con-)X
X432 5200(tains)N
X618(the)X
X751(previous)X
X1062(2)X
X2 f
X7 s
X5168(n)Y
X9 f
X1139(+)X
X1 f
X1170(1)X
X2 f
X10 s
X9 f
X5200(-)Y
X1 f
X1242(1)X
X1317(bits)X
X1467(\(1)X
X2 f
X9 f
X1534(+)X
X1 f
X1578(2)X
X2 f
X9 f
X(+)S
X1 f
X1662(4)X
X2 f
X9 f
X(+)S
X1 f
X1746(...)X
X2 f
X9 f
X(+)S
X1 f
X1850(2)X
X2 f
X7 s
X5168(n)Y
X10 s
X1 f
X1931 5200(\))N
X1992(which)X
X432 5288(trace)N
X649(the)X
X807(entire)X
X2 f
X1050(split)X
X1247(history)X
X1 f
X1529(of)X
X1656(the)X
X1813(addressable)X
X16 s
X432 5433 MXY
X864 0 Dl
X2 f
X8 s
X472 5488(2)N
X1 f
X9 s
X523 5513(This)N
X670(bit-randomizing)X
X1153(property)X
X1416(is)X
X1482(important)X
X1780(to)X
X1854(obtain)X
X2052(radi-)X
X432 5593(cally)N
X599(different)X
X874(hash)X
X1033(values)X
X1244(for)X
X1355(nearly)X
X1562(identical)X
X1836(keys,)X
X2012(which)X
X432 5673(in)N
X506(turn)X
X640(avoids)X
X846(clustering)X
X1148(of)X
X1226(such)X
X1376(keys)X
X1526(in)X
X1600(a)X
X1650(single)X
X1840(bucket.)X
X10 s
X2418 538(buckets.)N
X2590 652(Given)N
X2809(a)X
X2868(key)X
X3007(and)X
X3146(the)X
X3267(bitmap)X
X3512(created)X
X3768(by)X
X3871(this)X
X4009(algo-)X
X2418 740(rithm,)N
X2638(we)X
X2759(\256rst)X
X2910(examine)X
X3209(bit)X
X3320(0)X
X3386(of)X
X3479(the)X
X3603(bitmap)X
X3851(\(the)X
X4002(bit)X
X4112(to)X
X2418 828(consult)N
X2673(when)X
X2871(0)X
X2934(bits)X
X3072(of)X
X3162(the)X
X3283(hash)X
X3453(value)X
X3650(are)X
X3772(being)X
X3973(exam-)X
X2418 916(ined\).)N
X2631(If)X
X2713(it)X
X2785(is)X
X2866(set)X
X2982(\(indicating)X
X3356(that)X
X3503(the)X
X3628(bucket)X
X3869(split\),)X
X4080(we)X
X2418 1004(begin)N
X2617(considering)X
X3012(the)X
X3131(bits)X
X3267(of)X
X3355(the)X
X3473(32-bit)X
X3684(hash)X
X3851(value.)X
X4085(As)X
X2418 1092(bit)N
X2525(n)X
X2587(is)X
X2662(revealed,)X
X2977(a)X
X3035(mask)X
X3226(equal)X
X3422(to)X
X3506(2)X
X2 f
X7 s
X1060(n)Y
X9 f
X3583(+)X
X1 f
X3614(1)X
X2 f
X10 s
X9 f
X1092(-)Y
X1 f
X3686(1)X
X3748(will)X
X3894(yield)X
X4076(the)X
X2418 1180(current)N
X2675(bucket)X
X2918(address.)X
X3228(Adding)X
X3496(2)X
X2 f
X7 s
X1148(n)Y
X9 f
X3573(+)X
X1 f
X3604(1)X
X2 f
X10 s
X9 f
X1180(-)Y
X1 f
X3676(1)X
X3744(to)X
X3834(the)X
X3960(bucket)X
X2418 1268(address)N
X2701(identi\256es)X
X3035(which)X
X3272(bit)X
X3397(in)X
X3500(the)X
X3639(bitmap)X
X3902(must)X
X4098(be)X
X2418 1356(checked.)N
X2743(We)X
X2876(continue)X
X3173(revealing)X
X3493(bits)X
X3628(of)X
X3715(the)X
X3833(hash)X
X4000(value)X
X2418 1444(until)N
X2591(all)X
X2698(set)X
X2814(bits)X
X2955(in)X
X3043(the)X
X3167(bitmap)X
X3415(are)X
X3540(exhausted.)X
X3907(The)X
X4058(fol-)X
X2418 1532(lowing)N
X2682(algorithm,)X
X3055(a)X
X3133(simpli\256cation)X
X3614(of)X
X3723(the)X
X3863(algorithm)X
X2418 1620(due)N
X2565(to)X
X2658(Ken)X
X2823(Thompson)X
X3196([THOM90,)X
X3590(TOR88],)X
X3908(uses)X
X4076(the)X
X2418 1708(hash)N
X2625(value)X
X2839(and)X
X2995(the)X
X3133(bitmap)X
X3395(to)X
X3497(calculate)X
X3823(the)X
X3960(bucket)X
X2418 1796(address)N
X2679(as)X
X2766(discussed)X
X3093(above.)X
X0(Courier)xf 0 f
X1 f
X0 f
X8 s
X2418 2095(hash)N
X2608(=)X
X2684 -0.4038(calchash\(key\);)AX
X2418 2183(mask)N
X2608(=)X
X2684(0;)X
X2418 2271(while)N
X2646 -0.4018(\(isbitset\(\(hash)AX
X3254(&)X
X3330(mask\))X
X3558(+)X
X3634(mask\)\))X
X2706 2359(mask)N
X2896(=)X
X2972(\(mask)X
X3200(<<)X
X3314(1\))X
X3428(+)X
X3504(1;)X
X2418 2447(bucket)N
X2684(=)X
X2760(hash)X
X2950(&)X
X3026(mask;)X
X2 f
X10 s
X3211 2812(sdbm)N
X1 f
X2590 2944(The)N
X2 f
X2738(sdbm)X
X1 f
X2930(library)X
X3167(is)X
X3243(a)X
X3302(public-domain)X
X3791(clone)X
X3987(of)X
X4076(the)X
X2 f
X2418 3032(ndbm)N
X1 f
X2638(library,)X
X2914(developed)X
X3286(by)X
X3408(Ozan)X
X3620(Yigit)X
X3826(to)X
X3929(provide)X
X2 f
X2418 3120(ndbm)N
X1 f
X2596('s)X
X2692(functionality)X
X3139(under)X
X3359(some)X
X3565(versions)X
X3869(of)X
X3973(UNIX)X
X2418 3208(that)N
X2559(exclude)X
X2830(it)X
X2894(for)X
X3008(licensing)X
X3317(reasons)X
X3578([YIG89].)X
X3895(The)X
X4040(pro-)X
X2418 3296(grammer)N
X2735(interface,)X
X3064(and)X
X3207(the)X
X3332(basic)X
X3524(structure)X
X3832(of)X
X2 f
X3926(sdbm)X
X1 f
X4121(is)X
X2418 3384(identical)N
X2733(to)X
X2 f
X2834(ndbm)X
X1 f
X3051(but)X
X3192(internal)X
X3476(details)X
X3723(of)X
X3828(the)X
X2 f
X3964(access)X
X1 f
X2418 3472(function,)N
X2726(such)X
X2894(as)X
X2982(the)X
X3101(calculation)X
X3474(of)X
X3561(the)X
X3679(bucket)X
X3913(address,)X
X2418 3560(and)N
X2563(the)X
X2690(use)X
X2825(of)X
X2920(different)X
X3225(hash)X
X3400(functions)X
X3726(make)X
X3928(the)X
X4054(two)X
X2418 3648(incompatible)N
X2856(at)X
X2934(the)X
X3052(database)X
X3349(level.)X
X2590 3762(The)N
X2 f
X2740(sdbm)X
X1 f
X2934(library)X
X3173(is)X
X3251(based)X
X3458(on)X
X3562(a)X
X3622(simpli\256ed)X
X3965(imple-)X
X2418 3850(mentation)N
X2778(of)X
X2885(Larson's)X
X3206(1978)X
X2 f
X3406(dynamic)X
X3717(hashing)X
X1 f
X4009(algo-)X
X2418 3938(rithm)N
X2616(including)X
X2943(the)X
X2 f
X3066(re\256nements)X
X3461(and)X
X3605(variations)X
X1 f
X3953(of)X
X4044(sec-)X
X2418 4026(tion)N
X2562(5)X
X2622([LAR78].)X
X2956(Larson's)X
X3257(original)X
X3526(algorithm)X
X3857(calls)X
X4024(for)X
X4138(a)X
X2418 4114(forest)N
X2635(of)X
X2736(binary)X
X2975(hash)X
X3156(trees)X
X3341(that)X
X3494(are)X
X3626(accessed)X
X3941(by)X
X4054(two)X
X2418 4202(hash)N
X2586(functions.)X
X2925(The)X
X3071(\256rst)X
X3216(hash)X
X3384(function)X
X3672(selects)X
X3907(a)X
X3964(partic-)X
X2418 4290(ular)N
X2571(tree)X
X2720(within)X
X2952(the)X
X3078(forest.)X
X3309(The)X
X3462(second)X
X3713(hash)X
X3887(function,)X
X2418 4378(which)N
X2659(is)X
X2757(required)X
X3070(to)X
X3177(be)X
X3297(a)X
X3377(boolean)X
X3675(pseudo-random)X
X2418 4466(number)N
X2687(generator)X
X3015(that)X
X3159(is)X
X3236(seeded)X
X3479(by)X
X3583(the)X
X3705(key,)X
X3865(is)X
X3942(used)X
X4112(to)X
X2418 4554(traverse)N
X2733(the)X
X2890(tree)X
X3070(until)X
X3275(internal)X
X3579(\(split\))X
X3829(nodes)X
X4075(are)X
X2418 4642(exhausted)N
X2763(and)X
X2903(an)X
X3003(external)X
X3286(\(non-split\))X
X3648(node)X
X3827(is)X
X3903(reached.)X
X2418 4730(The)N
X2571(bucket)X
X2813(addresses)X
X3149(are)X
X3276(stored)X
X3500(directly)X
X3772(in)X
X3861(the)X
X3986(exter-)X
X2418 4818(nal)N
X2536(nodes.)X
X2590 4932(Larson's)N
X2903(re\256nements)X
X3309(are)X
X3440(based)X
X3655(on)X
X3767(the)X
X3897(observa-)X
X2418 5020(tion)N
X2570(that)X
X2718(the)X
X2844(nodes)X
X3059(can)X
X3199(be)X
X3303(represented)X
X3702(by)X
X3809(a)X
X3872(single)X
X4090(bit)X
X2418 5108(that)N
X2569(is)X
X2653(set)X
X2773(for)X
X2898(internal)X
X3174(nodes)X
X3392(and)X
X3539(not)X
X3672(set)X
X3791(for)X
X3915(external)X
X2418 5196(nodes,)N
X2652(resulting)X
X2959(in)X
X3048(a)X
X3111(radix)X
X3303(search)X
X3536(trie.)X
X3709(Figure)X
X3944(1)X
X4010(illus-)X
X2418 5284(trates)N
X2621(this.)X
X2804(Nodes)X
X3037(A)X
X3123(and)X
X3267(B)X
X3348(are)X
X3475(internal)X
X3748(\(split\))X
X3967(nodes,)X
X2418 5372(thus)N
X2573(having)X
X2813(no)X
X2915(bucket)X
X3151(addresses)X
X3480(associated)X
X3831(with)X
X3994(them.)X
X2418 5460(Instead,)N
X2693(the)X
X2814(external)X
X3096(nodes)X
X3306(\(C,)X
X3429(D,)X
X3530(and)X
X3669(E\))X
X3768(each)X
X3938(need)X
X4112(to)X
X2418 5548(refer)N
X2594(to)X
X2679(a)X
X2738(bucket)X
X2975(address.)X
X3279(These)X
X3494(bucket)X
X3731(addresses)X
X4062(can)X
X2418 5636(be)N
X2529(stored)X
X2760(in)X
X2857(the)X
X2990(trie)X
X3132(itself)X
X3327(where)X
X3559(the)X
X3691(subtries)X
X3974(would)X
X3 f
X432 5960(2)N
X2970(USENIX)X
X9 f
X3292(-)X
X3 f
X3356(Winter)X
X3621('91)X
X9 f
X3748(-)X
X3 f
X3812(Dallas,)X
X4065(TX)X
X
X3 p
X%%Page: 3 3
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X720 258(Seltzer)N
X977(&)X
X1064(Yigit)X
X3278(A)X
X3356(New)X
X3528(Hashing)X
X3831(Package)X
X4136(for)X
X4259(UNIX)X
X1 f
X720 538(live)N
X862(if)X
X933(they)X
X1092(existed)X
X1340([KNU68].)X
X1709(For)X
X1841(example,)X
X2154(if)X
X2224(nodes)X
X2432(F)X
X720 626(and)N
X858(G)X
X938(were)X
X1117(the)X
X1237(children)X
X1522(of)X
X1610(node)X
X1787(C,)X
X1881(the)X
X2000(bucket)X
X2235(address)X
X720 714(L00)N
X886(could)X
X1101(reside)X
X1330(in)X
X1429(the)X
X1563(bits)X
X1714(that)X
X1870(will)X
X2030(eventually)X
X2400(be)X
X720 802(used)N
X887(to)X
X969(store)X
X1145(nodes)X
X1352(F)X
X1416(and)X
X1552(G)X
X1630(and)X
X1766(all)X
X1866(their)X
X2033(children.)X
X10 f
X720 890 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X1894 2247(L1)N
X784 1925(A)N
X1431(E)X
X1106 2247(D)N
X1428 1281(C)N
X1109 1603(B)N
X1884 1930(L01)N
X1879 1286(L00)N
X1221 1814(1)N
X903 2131(1)N
X1221 1402(0)N
X903 1714(0)N
X1 Dt
X1397 1821 MXY
X-8 -32 Dl
X-5 19 Dl
X-20 6 Dl
X33 7 Dl
X-187 -182 Dl
X1397 1322 MXY
X-33 7 Dl
X20 6 Dl
X5 19 Dl
X8 -32 Dl
X-187 182 Dl
X1069 1639 MXY
X-32 7 Dl
X20 6 Dl
X5 19 Dl
X7 -32 Dl
X-186 182 Dl
X1374 1891 MXY
X185 Dc
X1779 2133 MXY
X0 161 Dl
X322 0 Dl
X0 -161 Dl
X-322 0 Dl
X1811 MY
X0 161 Dl
X322 0 Dl
X0 -161 Dl
X-322 0 Dl
X1166 MY
X0 161 Dl
X322 0 Dl
X0 -161 Dl
X-322 0 Dl
X1052 2213 MXY
X185 Dc
X1569 MY
X185 Dc
X720 1881 MXY
X185 Dc
X1779 2213 MXY
X-28 -17 Dl
X10 17 Dl
X-10 18 Dl
X28 -18 Dl
X-543 0 Dl
X1769 1891 MXY
X-28 -18 Dl
X10 18 Dl
X-10 18 Dl
X28 -18 Dl
X-201 0 Dl
X1364 1247 MXY
X185 Dc
X1769 MX
X-28 -18 Dl
X10 18 Dl
X-10 18 Dl
X28 -18 Dl
X-201 0 Dl
X1064 2143 MXY
X-7 -32 Dl
X-5 19 Dl
X-20 6 Dl
X32 7 Dl
X-181 -181 Dl
X3 Dt
X-1 Ds
X8 s
X720 2482(Figure)N
X925(1:)X
X1 f
X1002(Radix)X
X1179(search)X
X1365(trie)X
X1474(with)X
X1612(internal)X
X1831(nodes)X
X2004(A)X
X2074(and)X
X2189(B,)X
X2271(external)X
X720 2570(nodes)N
X891(C,)X
X972(D,)X
X1056(and)X
X1170(E,)X
X1247(and)X
X1361(bucket)X
X1553(addresses)X
X1819(stored)X
X1997(in)X
X2069(the)X
X2168(unused)X
X2370(por-)X
X720 2658(tion)N
X836(of)X
X905(the)X
X999(trie.)X
X10 s
X10 f
X720 2922 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X1 f
X892 3124(Further)N
X1153(simpli\256cations)X
X1647(of)X
X1738(the)X
X1860(above)X
X2076([YIG89])X
X2377(are)X
X720 3212(possible.)N
X1038(Using)X
X1265(a)X
X1337(single)X
X1564(radix)X
X1765(trie)X
X1908(to)X
X2006(avoid)X
X2219(the)X
X2352(\256rst)X
X720 3300(hash)N
X904(function,)X
X1227(replacing)X
X1562(the)X
X1696(pseudo-random)X
X2231(number)X
X720 3388(generator)N
X1052(with)X
X1222(a)X
X1286(well)X
X1452(designed,)X
X1785(bit-randomizing)X
X2329(hash)X
X720 3476(function,)N
X1053(and)X
X1215(using)X
X1434(the)X
X1578(portion)X
X1855(of)X
X1967(the)X
X2110(hash)X
X2302(value)X
X720 3564(exposed)N
X1021(during)X
X1268(the)X
X1404(trie)X
X1549(traversal)X
X1864(as)X
X1969(a)X
X2042(direct)X
X2262(bucket)X
X720 3652(address)N
X990(results)X
X1228(in)X
X1319(an)X
X2 f
X1424(access)X
X1 f
X1663(function)X
X1959(that)X
X2108(works)X
X2333(very)X
X720 3740(similar)N
X974(to)X
X1068(Thompson's)X
X1499(algorithm)X
X1841(above.)X
X2084(The)X
X2240(follow-)X
X720 3828(ing)N
X847(algorithm)X
X1183(uses)X
X1346(the)X
X1469(hash)X
X1641(value)X
X1840(to)X
X1927(traverse)X
X2206(a)X
X2266(linear-)X
X720 3916(ized)N
X874(radix)X
X1059(trie)X
X2 f
X8 s
X1166 3891(3)N
X1 f
X10 s
X1218 3916(starting)N
X1478(at)X
X1556(the)X
X1674(0)X
X2 f
X7 s
X3884(th)Y
X10 s
X1 f
X1791 3916(bit.)N
X0 f
X8 s
X720 4215(tbit)N
X910(=)X
X986(0;)X
X1296(/*)X
X1410(radix)X
X1638(trie)X
X1828(index)X
X2056(*/)X
X720 4303(hbit)N
X910(=)X
X986(0;)X
X1296(/*)X
X1410(hash)X
X1600(bit)X
X1752(index)X
X2056(*/)X
X720 4391(mask)N
X910(=)X
X986(0;)X
X720 4479(hash)N
X910(=)X
X986 -0.4038(calchash\(key\);)AX
X720 4655(for)N
X872(\(mask)X
X1100(=)X
X1176(0;)X
X910 4743 -0.4018(isbitset\(tbit\);)AN
X910 4831(mask)N
X1100(=)X
X1176(\(mask)X
X1404(<<)X
X1518(1\))X
X1632(+)X
X1708(1\))X
X1008 4919(if)N
X1122(\(hash)X
X1350(&)X
X1426(\(1)X
X1540(<<)X
X1654 -0.4219(hbit++\)\)\))AX
X1160 5007(/*)N
X1274(right)X
X1502(son)X
X1692(*/)X
X1160 5095(tbit)N
X1350(=)X
X1426(2)X
X1502(*)X
X1578(tbit)X
X1768(+)X
X1844(2;)X
X1008 5183(else)N
X1 f
X16 s
X720 5353 MXY
X864 0 Dl
X2 f
X8 s
X760 5408(3)N
X1 f
X9 s
X818 5433(A)N
X896(linearized)X
X1206(radix)X
X1380(trie)X
X1502(is)X
X1576(merely)X
X1802(an)X
X1895(array)X
X2068(representation)X
X720 5513(of)N
X800(the)X
X908(radix)X
X1076(search)X
X1280(trie)X
X1396(described)X
X1692(above.)X
X1920(The)X
X2052(children)X
X2308(of)X
X2388(the)X
X720 5593(node)N
X885(with)X
X1038(index)X
X1223(i)X
X1267(can)X
X1391(be)X
X1483(found)X
X1675(at)X
X1751(the)X
X1863(nodes)X
X2055(indexed)X
X2307(2*i+1)X
X720 5673(and)N
X842(2*i+2.)X
X0 f
X8 s
X3146 538(/*)N
X3260(left)X
X3450(son)X
X3678(*/)X
X3146 626(tbit)N
X3336(=)X
X3412(2)X
X3488(*)X
X3564(tbit)X
X3754(+)X
X3830(1;)X
X2706 802(bucket)N
X2972(=)X
X3048(hash)X
X3238(&)X
X3314(mask;)X
X2 f
X10 s
X3495 1167(gdbm)N
X1 f
X2878 1299(The)N
X3027(gdbm)X
X3233(\(GNU)X
X3458(data)X
X3616(base)X
X3783(manager\))X
X4111(library)X
X4349(is)X
X4426(a)X
X2706 1387(UNIX)N
X2933(database)X
X3236(manager)X
X3539(written)X
X3792(by)X
X3897(Philip)X
X4112(A.)X
X4215(Nelson,)X
X2706 1475(and)N
X2848(made)X
X3048(available)X
X3364(as)X
X3457(a)X
X3518(part)X
X3668(of)X
X3760(the)X
X3883(FSF)X
X4040(software)X
X4342(dis-)X
X2706 1563(tribution.)N
X3052(The)X
X3207(gdbm)X
X3419(library)X
X3663(provides)X
X3969(the)X
X4097(same)X
X4292(func-)X
X2706 1651(tionality)N
X3028(of)X
X3151(the)X
X2 f
X3304(dbm)X
X1 f
X3442(/)X
X2 f
X3464(ndbm)X
X1 f
X3697(libraries)X
X4015([NEL90])X
X4360(but)X
X2706 1739(attempts)N
X3018(to)X
X3121(avoid)X
X3340(some)X
X3550(of)X
X3658(their)X
X3846(shortcomings.)X
X4337(The)X
X2706 1827(gdbm)N
X2918(library)X
X3162(allows)X
X3401(for)X
X3525(arbitrary-length)X
X4059(data,)X
X4242(and)X
X4387(its)X
X2706 1915(database)N
X3027(is)X
X3124(a)X
X3203(singular,)X
X3524(non-sparse)X
X2 f
X8 s
X3872 1890(4)N
X1 f
X10 s
X3947 1915(\256le.)N
X4112(The)X
X4280(gdbm)X
X2706 2003(library)N
X2947(also)X
X3103(includes)X
X2 f
X3396(dbm)X
X1 f
X3560(and)X
X2 f
X3702(ndbm)X
X1 f
X3906(compatible)X
X4288(inter-)X
X2706 2091(faces.)N
X2878 2205(The)N
X3025(gdbm)X
X3229(library)X
X3465(is)X
X3540(based)X
X3745(on)X
X2 f
X3847(extensible)X
X4189(hashing)X
X1 f
X4442(,)X
X2706 2293(a)N
X2766(dynamic)X
X3066(hashing)X
X3339(algorithm)X
X3674(by)X
X3778(Fagin)X
X3984(et)X
X4066(al)X
X4148([FAG79].)X
X2706 2381(This)N
X2881(algorithm)X
X3225(differs)X
X3467(from)X
X3655(the)X
X3785(previously)X
X4155(discussed)X
X2706 2469(algorithms)N
X3069(in)X
X3152(that)X
X3293(it)X
X3358(uses)X
X3517(a)X
X2 f
X3574(directory)X
X1 f
X3889(that)X
X4030(is)X
X4103(a)X
X4159(collapsed)X
X2706 2557(representation)N
X3192([ENB88])X
X3517(of)X
X3615(the)X
X3744(radix)X
X3940(search)X
X4177(trie)X
X4315(used)X
X2706 2645(by)N
X2 f
X2806(sdbm)X
X1 f
X2975(.)X
X10 f
X2706 2733 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X7 s
X3572 3761(L1)N
X1 Dt
X3485 3738 MXY
X-20 -13 Dl
X7 13 Dl
X-7 13 Dl
X20 -13 Dl
X-400 0 Dl
X3180 3027 MXY
X136 Dc
X2706 3494 MXY
X136 Dc
X2950 3264 MXY
X136 Dc
X3738 MY
X136 Dc
X3485 2968 MXY
X0 118 Dl
X238 0 Dl
X0 -118 Dl
X-238 0 Dl
X3442 MY
X0 119 Dl
X238 0 Dl
X0 -119 Dl
X-238 0 Dl
X3679 MY
X0 119 Dl
X238 0 Dl
X0 -119 Dl
X-238 0 Dl
X3187 3501 MXY
X136 Dc
X2963 3316 MXY
X-24 5 Dl
X15 4 Dl
X4 15 Dl
X5 -24 Dl
X-137 134 Dl
X3204 3083 MXY
X-24 5 Dl
X15 4 Dl
X3 14 Dl
X6 -23 Dl
X-137 133 Dl
X3204 3450 MXY
X-6 -24 Dl
X-3 14 Dl
X-15 5 Dl
X24 5 Dl
X-137 -134 Dl
X2842 3369(0)N
X3075 3139(0)N
X2842 3676(1)N
X3075 3443(1)N
X3562 3054(L00)N
X3565 3528(L01)N
X4197 2968 MXY
X0 118 Dl
X237 0 Dl
X0 -118 Dl
X-237 0 Dl
X3205 MY
X0 119 Dl
X237 0 Dl
X0 -119 Dl
X-237 0 Dl
X3561 MY
X0 118 Dl
X237 0 Dl
X0 -118 Dl
X-237 0 Dl
X3960 2909 MXY
X0 237 Dl
X118 0 Dl
X0 -237 Dl
X-118 0 Dl
X3146 MY
X0 237 Dl
X118 0 Dl
X0 -237 Dl
X-118 0 Dl
X3383 MY
X0 237 Dl
X118 0 Dl
X0 -237 Dl
X-118 0 Dl
X3620 MY
X0 237 Dl
X118 0 Dl
X0 -237 Dl
X-118 0 Dl
X4197 3027 MXY
X-21 -13 Dl
X8 13 Dl
X-8 13 Dl
X21 -13 Dl
X-119 0 Dl
X4197 3264 MXY
X-21 -13 Dl
X8 13 Dl
X-8 13 Dl
X21 -13 Dl
X-119 0 Dl
X3501 MY
X59 0 Dl
X0 89 Dl
X4078 3738 MXY
X59 0 Dl
X0 -88 Dl
X4197 3590 MXY
X-21 -13 Dl
X8 13 Dl
X-8 13 Dl
X21 -13 Dl
X-60 0 Dl
X4197 3650 MXY
X-21 -13 Dl
X8 13 Dl
X-8 13 Dl
X21 -13 Dl
X-60 0 Dl
X3991 3050(00)N
X3991 3287(01)N
X3991 3524(10)N
X3991 3761(11)N
X4269 3050(L00)N
X4269 3287(L01)N
X4283 3643(L1)N
X3485 3501 MXY
X-20 -13 Dl
X7 13 Dl
X-7 13 Dl
X20 -13 Dl
X-155 0 Dl
X3485 3027 MXY
X-20 -13 Dl
X7 13 Dl
X-7 13 Dl
X20 -13 Dl
X-163 0 Dl
X2967 3687 MXY
X-5 -24 Dl
X-4 14 Dl
X-15 4 Dl
X24 6 Dl
X-141 -141 Dl
X3 Dt
X-1 Ds
X8 s
X2706 4033(Figure)N
X2903(2:)X
X1 f
X2972(A)X
X3034(radix)X
X3181(search)X
X3359(trie)X
X3460(and)X
X3568(a)X
X3612(directory)X
X3858(representing)X
X4189(the)X
X4283(trie.)X
X10 s
X10 f
X2706 4209 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X1 f
X2878 4411(In)N
X2968(this)X
X3106(algorithm,)X
X3460(a)X
X3519(directory)X
X3832(consists)X
X4108(of)X
X4198(a)X
X4256(search)X
X2706 4499(trie)N
X2847(of)X
X2947(depth)X
X2 f
X3158(n)X
X1 f
X3211(,)X
X3264(containing)X
X3635(2)X
X2 f
X7 s
X4467(n)Y
X10 s
X1 f
X3749 4499(bucket)N
X3996(addresses)X
X4337(\(i.e.)X
X2706 4587(each)N
X2897(element)X
X3194(of)X
X3304(the)X
X3445(trie)X
X3594(is)X
X3689(a)X
X3767(bucket)X
X4023(address\).)X
X4373(To)X
X2706 4675(access)N
X2935(the)X
X3056(hash)X
X3226(table,)X
X3425(a)X
X3483(32-bit)X
X3696(hash)X
X3865(value)X
X4061(is)X
X4136(calculated)X
X2706 4763(and)N
X2 f
X2861(n)X
X1 f
X2953(bits)X
X3107(of)X
X3213(the)X
X3350(value)X
X3563(are)X
X3701(used)X
X3886(to)X
X3986(index)X
X4202(into)X
X4364(the)X
X2706 4851(directory)N
X3018(to)X
X3102(obtain)X
X3324(a)X
X3382(bucket)X
X3618(address.)X
X3921(It)X
X3992(is)X
X4067(important)X
X4400(to)X
X2706 4939(note)N
X2866(that)X
X3008(multiple)X
X3296(entries)X
X3532(of)X
X3620(this)X
X3756(directory)X
X4067(may)X
X4226(contain)X
X2706 5027(the)N
X2833(same)X
X3026(bucket)X
X3268(address)X
X3537(as)X
X3632(a)X
X3696(result)X
X3902(of)X
X3997(directory)X
X4315(dou-)X
X2706 5115(bling)N
X2903(during)X
X3145(bucket)X
X3392(splitting.)X
X3706(Figure)X
X3948(2)X
X4021(illustrates)X
X4364(the)X
X2706 5203(relationship)N
X3126(between)X
X3436(a)X
X3513(typical)X
X3772(\(skewed\))X
X4108(search)X
X4355(trie)X
X2706 5291(and)N
X2850(its)X
X2953(directory)X
X3271(representation.)X
X3774(The)X
X3927(formation)X
X4270(of)X
X4364(the)X
X2706 5379(directory)N
X3016(shown)X
X3245(in)X
X3327(the)X
X3445(\256gure)X
X3652(is)X
X3725(as)X
X3812(follows.)X
X16 s
X2706 5593 MXY
X864 0 Dl
X2 f
X8 s
X2746 5648(4)N
X1 f
X9 s
X2796 5673(It)N
X2858(does)X
X3008(not)X
X3118(contain)X
X3348(holes.)X
X3 f
X10 s
X720 5960(USENIX)N
X9 f
X1042(-)X
X3 f
X1106(Winter)X
X1371('91)X
X9 f
X1498(-)X
X3 f
X1562(Dallas,)X
X1815(TX)X
X4424(3)X
X
X4 p
X%%Page: 4 4
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X432 258(A)N
X510(New)X
X682(Hashing)X
X985(Package)X
X1290(for)X
X1413(UNIX)X
X3663(Seltzer)X
X3920(&)X
X4007(Yigit)X
X1 f
X604 538(Initially,)N
X937(there)X
X1158(is)X
X1271(one)X
X1446(slot)X
X1620(in)X
X1741(the)X
X1898(directory)X
X432 626(addressing)N
X802(a)X
X865(single)X
X1083(bucket.)X
X1364(The)X
X1515(depth)X
X1719(of)X
X1812(the)X
X1936(trie)X
X2069(is)X
X2148(0)X
X432 714(and)N
X577(0)X
X646(bits)X
X790(of)X
X886(each)X
X1063(hash)X
X1239(value)X
X1442(are)X
X1570(examined)X
X1910(to)X
X2000(deter-)X
X432 802(mine)N
X624(in)X
X718(which)X
X946(bucket)X
X1192(to)X
X1286(place)X
X1488(a)X
X1556(key;)X
X1726(all)X
X1837(keys)X
X2015(go)X
X2126(in)X
X432 890(bucket)N
X682(0.)X
X797(When)X
X1024(this)X
X1174(bucket)X
X1423(is)X
X1511(full,)X
X1677(its)X
X1787(contents)X
X2089(are)X
X432 978(divided)N
X698(between)X
X992(L0)X
X1107(and)X
X1249(L1)X
X1363(as)X
X1455(was)X
X1605(done)X
X1786(in)X
X1873(the)X
X1996(previ-)X
X432 1066(ously)N
X664(discussed)X
X1030(algorithms.)X
X1471(After)X
X1700(this)X
X1874(split,)X
X2090(the)X
X432 1154(address)N
X710(of)X
X814(the)X
X948(second)X
X1207(bucket)X
X1457(must)X
X1648(be)X
X1760(stored)X
X1992(in)X
X2090(the)X
X432 1242(directory.)N
X796(To)X
X939(accommodate)X
X1438(the)X
X1589(new)X
X1776(address,)X
X2090(the)X
X432 1330(directory)N
X752(is)X
X835(split)X
X2 f
X8 s
X972 1305(5)N
X1 f
X10 s
X1330(,)Y
X1054(by)X
X1163(doubling)X
X1476(it,)X
X1569(thus)X
X1731(increasing)X
X2090(the)X
X432 1418(depth)N
X630(of)X
X717(the)X
X835(directory)X
X1145(by)X
X1245(one.)X
X604 1532(After)N
X813(this)X
X967(split,)X
X1163(a)X
X1237(single)X
X1466(bit)X
X1588(of)X
X1693(the)X
X1829(hash)X
X2014(value)X
X432 1620(needs)N
X663(to)X
X773(be)X
X896(examined)X
X1255(to)X
X1364(decide)X
X1621(whether)X
X1927(the)X
X2072(key)X
X432 1708(belongs)N
X711(to)X
X803(L0)X
X922(or)X
X1019(L1.)X
X1158(Once)X
X1358(one)X
X1504(of)X
X1601(these)X
X1795(buckets)X
X2069(\256lls)X
X432 1796(\(L0)N
X578(for)X
X702(example\),)X
X1051(it)X
X1125(is)X
X1208(split)X
X1375(as)X
X1472(before,)X
X1728(and)X
X1873(the)X
X2000(direc-)X
X432 1884(tory)N
X585(is)X
X662(split)X
X823(again)X
X1021(to)X
X1107(make)X
X1305(room)X
X1498(for)X
X1615(the)X
X1736(address)X
X2000(of)X
X2090(the)X
X432 1972(third)N
X618(bucket.)X
X927(This)X
X1104(splitting)X
X1400(causes)X
X1645(the)X
X1778(addresses)X
X2121(of)X
X432 2060(the)N
X567(non-splitting)X
X1012(bucket)X
X1263(\(L1\))X
X1443(to)X
X1541(be)X
X1653(duplicated.)X
X2063(The)X
X432 2148(directory)N
X766(now)X
X948(has)X
X1099(four)X
X1277(entries,)X
X1555(a)X
X1635(depth)X
X1857(of)X
X1968(2,)X
X2072(and)X
X432 2236(indexes)N
X700(the)X
X821(buckets)X
X1089(L00,)X
X1261(L01)X
X1413(and)X
X1552(L1,)X
X1684(as)X
X1774(shown)X
X2006(in)X
X2090(the)X
X432 2324(Figure)N
X661(2.)X
X604 2438(The)N
X756(crucial)X
X1002(part)X
X1154(of)X
X1247(the)X
X1371(algorithm)X
X1708(is)X
X1787(the)X
X1911(observa-)X
X432 2526(tion)N
X580(that)X
X724(L1)X
X837(is)X
X914(addressed)X
X1255(twice)X
X1453(in)X
X1539(the)X
X1661(directory.)X
X1995(If)X
X2073(this)X
X432 2614(bucket)N
X679(were)X
X869(to)X
X964(split)X
X1134(now,)X
X1324(the)X
X1454(directory)X
X1776(already)X
X2045(con-)X
X432 2702(tains)N
X611(room)X
X808(to)X
X898(hold)X
X1067(the)X
X1192(address)X
X1460(of)X
X1554(the)X
X1679(new)X
X1840(bucket.)X
X2121(In)X
X432 2790(general,)N
X711(the)X
X831(relationship)X
X1231(between)X
X1521(the)X
X1641(directory)X
X1953(and)X
X2090(the)X
X432 2878(number)N
X704(of)X
X798(bucket)X
X1039(addresses)X
X1374(contained)X
X1713(therein)X
X1962(is)X
X2041(used)X
X432 2966(to)N
X517(decide)X
X750(when)X
X947(to)X
X1031(split)X
X1190(the)X
X1310(directory.)X
X1662(Each)X
X1845(bucket)X
X2081(has)X
X432 3054(a)N
X505(depth,)X
X740(\()X
X2 f
X767(n)X
X7 s
X3070(b)Y
X10 s
X1 f
X848 3054(\),)N
X932(associated)X
X1299(with)X
X1478(it)X
X1558(and)X
X1710(appears)X
X1992(in)X
X2090(the)X
X432 3142(directory)N
X744(exactly)X
X998(2)X
X2 f
X7 s
X3106(n)Y
X9 f
X1075(-)X
X2 f
X1106(n)X
X4 s
X3110(b)Y
X7 s
X1 f
X10 s
X1181 3142(times.)N
X1396(When)X
X1610(a)X
X1668(bucket)X
X1904(splits,)X
X2113(its)X
X432 3230(depth)N
X638(increases)X
X961(by)X
X1069(one.)X
X1253(The)X
X1406(directory)X
X1724(must)X
X1907(split)X
X2072(any)X
X432 3318(time)N
X602(a)X
X665(bucket's)X
X964(depth)X
X1169(exceeds)X
X1451(the)X
X1576(depth)X
X1781(of)X
X1875(the)X
X2000(direc-)X
X432 3406(tory.)N
X630(The)X
X784(following)X
X1123(code)X
X1303(fragment)X
X1621(helps)X
X1818(to)X
X1908(illustrate)X
X432 3494(the)N
X554(extendible)X
X912(hashing)X
X1185(algorithm)X
X1520([FAG79])X
X1838(for)X
X1955(access-)X
X432 3582(ing)N
X554(individual)X
X898(buckets)X
X1163(and)X
X1299(maintaining)X
X1701(the)X
X1819(directory.)X
X0 f
X8 s
X432 3881(hash)N
X622(=)X
X698 -0.4038(calchash\(key\);)AX
X432 3969(mask)N
X622(=)X
X698 -0.4018(maskvec[depth];)AX
X432 4145(bucket)N
X698(=)X
X774 -0.4038(directory[hash)AX
X1344(&)X
X1420(mask];)X
X432 4321(/*)N
X546(Key)X
X698 -0.4219(Insertion)AX
X1078(*/)X
X432 4409(if)N
X546 -0.4038(\(store\(bucket,)AX
X1116(key,)X
X1306(data\))X
X1534(==)X
X1648(FAIL\))X
X1876({)X
X720 4497(newbl)N
X948(=)X
X1024 -0.4167(getpage\(\);)AX
X720 4585 -0.4000(bucket->depth++;)AN
X720 4673 -0.4091(newbl->depth)AN
X1214(=)X
X1290 -0.4038(bucket->depth;)AX
X720 4761(if)N
X834 -0.4038(\(bucket->depth)AX
X1404(>)X
X1480(depth\))X
X1746({)X
X1008 4849(/*)N
X1122(double)X
X1388 -0.4219(directory)AX
X1768(*/)X
X1008 4937(depth++;)N
X1 f
X16 s
X432 5033 MXY
X864 0 Dl
X2 f
X8 s
X472 5088(5)N
X1 f
X9 s
X534 5113(This)N
X692(decision)X
X962(to)X
X1048(split)X
X1202(the)X
X1319(directory)X
X1608(is)X
X1685(based)X
X1878(on)X
X1979(a)X
X2040(com-)X
X432 5193(parison)N
X666(of)X
X748(the)X
X858(depth)X
X1040(of)X
X1121(the)X
X1230(page)X
X1387(being)X
X1568(split)X
X1713(and)X
X1838(the)X
X1947(depth)X
X2128(of)X
X432 5273(the)N
X543(trie.)X
X698(In)X
X781(Figure)X
X992(2,)X
X1069(the)X
X1180(depths)X
X1390(of)X
X1472(both)X
X1622(L00)X
X1760(and)X
X1886(L01)X
X2024(are)X
X2134(2,)X
X432 5353(whereas)N
X689(the)X
X798(depth)X
X979(of)X
X1060(L1)X
X1161(is)X
X1230(1.)X
X1323(Therefore,)X
X1646(if)X
X1710(L1)X
X1810(were)X
X1970(to)X
X2046(split,)X
X432 5433(the)N
X543(directory)X
X826(would)X
X1029(not)X
X1144(need)X
X1303(to)X
X1382(split.)X
X1565(In)X
X1648(reality,)X
X1872(a)X
X1926(bucket)X
X2140(is)X
X432 5513(allocated)N
X727(for)X
X846(the)X
X969(directory)X
X1264(at)X
X1351(the)X
X1474(time)X
X1637(of)X
X1732(\256le)X
X1858(creation)X
X2124(so)X
X432 5593(although)N
X707(the)X
X818(directory)X
X1100(splits)X
X1274(logically,)X
X1566(physical)X
X1828(splits)X
X2002(do)X
X2096(not)X
X432 5673(occur)N
X610(until)X
X760(the)X
X866(\256le)X
X976(becomes)X
X1246(quite)X
X1408(large.)X
X0 f
X8 s
X2994 538 -0.4219(directory)AN
X3374(=)X
X3450 -0.3971(double\(directory\);)AX
X2706 626(})N
X2706 714 -0.3958(splitbucket\(bucket,)AN
X3466(newbl\))X
X2706 802(...)N
X2418 890(})N
X2 f
X10 s
X3169 1255(hsearch)N
X1 f
X2590 1387(Since)N
X2 f
X2807(hsearch)X
X1 f
X3100(does)X
X3286(not)X
X3427(have)X
X3617(to)X
X3717(translate)X
X4027(hash)X
X2418 1475(values)N
X2659(into)X
X2819(disk)X
X2988(addresses,)X
X3352(it)X
X3432(can)X
X3579(use)X
X3721(much)X
X3934(simpler)X
X2418 1563(algorithms)N
X2808(than)X
X2994(those)X
X3211(de\256ned)X
X3495(above.)X
X3775(System)X
X4058(V's)X
X2 f
X2418 1651(hsearch)N
X1 f
X2708(constructs)X
X3069(a)X
X3141(\256xed-size)X
X3489(hash)X
X3671(table)X
X3862(\(speci\256ed)X
X2418 1739(by)N
X2519(the)X
X2637(user)X
X2791(at)X
X2869(table)X
X3045(creation\).)X
X3391(By)X
X3504(default,)X
X3767(a)X
X3823(multiplica-)X
X2418 1827(tive)N
X2570(hash)X
X2748(function)X
X3046(based)X
X3260(on)X
X3371(that)X
X3522(described)X
X3861(in)X
X3954(Knuth,)X
X2418 1915(Volume)N
X2710(3,)X
X2804(section)X
X3065(6.4)X
X3199([KNU68])X
X3541(is)X
X3628(used)X
X3809(to)X
X3905(obtain)X
X4138(a)X
X2418 2003(primary)N
X2694(bucket)X
X2930(address.)X
X3233(If)X
X3309(this)X
X3446(bucket)X
X3681(is)X
X3755(full,)X
X3907(a)X
X3964(secon-)X
X2418 2091(dary)N
X2593(multiplicative)X
X3069(hash)X
X3248(value)X
X3454(is)X
X3538(computed)X
X3885(to)X
X3978(de\256ne)X
X2418 2179(the)N
X2542(probe)X
X2751(interval.)X
X3062(The)X
X3213(probe)X
X3422(interval)X
X3693(is)X
X3772(added)X
X3989(to)X
X4076(the)X
X2418 2267(original)N
X2712(bucket)X
X2971(address)X
X3257(\(modulo)X
X3573(the)X
X3716(table)X
X3916(size\))X
X4112(to)X
X2418 2355(obtain)N
X2658(a)X
X2734(new)X
X2908(bucket)X
X3162(address.)X
X3483(This)X
X3665(process)X
X3946(repeats)X
X2418 2443(until)N
X2588(an)X
X2688(empty)X
X2911(bucket)X
X3148(is)X
X3224(found.)X
X3474(If)X
X3551(no)X
X3654(bucket)X
X3891(is)X
X3967(found,)X
X2418 2531(an)N
X2514(insertion)X
X2814(fails)X
X2972(with)X
X3134(a)X
X3190(``table)X
X3420(full'')X
X3605(condition.)X
X2590 2645(The)N
X2768(basic)X
X2986(algorithm)X
X3350(may)X
X3541(be)X
X3670(modi\256ed)X
X4006(by)X
X4138(a)X
X2418 2733(number)N
X2705(of)X
X2813(compile)X
X3112(time)X
X3295(options)X
X3571(available)X
X3902(to)X
X4005(those)X
X2418 2821(users)N
X2604(with)X
X2767(AT&T)X
X3006(source)X
X3237(code.)X
X3450(First,)X
X3637(the)X
X3756(package)X
X4040(pro-)X
X2418 2909(vides)N
X2638(two)X
X2809(options)X
X3094(for)X
X3238(hash)X
X3435(functions.)X
X3803(Users)X
X4036(may)X
X2418 2997(specify)N
X2690(their)X
X2877(own)X
X3055(hash)X
X3242(function)X
X3549(by)X
X3669(compiling)X
X4032(with)X
X2418 3085(``USCR'')N
X2757(de\256ned)X
X3016(and)X
X3155(declaring)X
X3477(and)X
X3616(de\256ning)X
X3901(the)X
X4022(vari-)X
X2418 3173(able)N
X2 f
X2578(hcompar)X
X1 f
X2863(,)X
X2909(a)X
X2971(function)X
X3263(taking)X
X3488(two)X
X3633(string)X
X3840(arguments)X
X2418 3261(and)N
X2560(returning)X
X2880(an)X
X2982(integer.)X
X3271(Users)X
X3480(may)X
X3643(also)X
X3797(request)X
X4054(that)X
X2418 3349(hash)N
X2587(values)X
X2814(be)X
X2912(computed)X
X3250(simply)X
X3489(by)X
X3590(taking)X
X3811(the)X
X3930(modulo)X
X2418 3437(of)N
X2521(key)X
X2673(\(using)X
X2909(division)X
X3201(rather)X
X3424(than)X
X3597(multiplication)X
X4080(for)X
X2418 3525(hash)N
X2589(value)X
X2787(calculation\).)X
X3230(If)X
X3308(this)X
X3447(technique)X
X3783(is)X
X3859(used,)X
X4049(col-)X
X2418 3613(lisions)N
X2651(are)X
X2775(resolved)X
X3072(by)X
X3176(scanning)X
X3485(sequentially)X
X3896(from)X
X4076(the)X
X2418 3701(selected)N
X2702(bucket)X
X2941(\(linear)X
X3176(probing\).)X
X3517(This)X
X3684(option)X
X3913(is)X
X3991(avail-)X
X2418 3789(able)N
X2572(by)X
X2672(de\256ning)X
X2954(the)X
X3072(variable)X
X3351(``DIV'')X
X3622(at)X
X3700(compile)X
X3978(time.)X
X2590 3903(A)N
X2720(second)X
X3015(option,)X
X3311(based)X
X3565(on)X
X3716(an)X
X3863(algorithm)X
X2418 3991(discovered)N
X2787(by)X
X2888(Richard)X
X3163(P.)X
X3248(Brent,)X
X3466(rearranges)X
X3822(the)X
X3940(table)X
X4116(at)X
X2418 4079(the)N
X2549(time)X
X2724(of)X
X2824(insertion)X
X3137(in)X
X3232(order)X
X3434(to)X
X3528(speed)X
X3743(up)X
X3855(retrievals.)X
X2418 4167(The)N
X2571(basic)X
X2764(idea)X
X2926(is)X
X3007(to)X
X3097(shorten)X
X3361(long)X
X3531(probe)X
X3741(sequences)X
X4094(by)X
X2418 4255(lengthening)N
X2833(short)X
X3030(probe)X
X3249(sequences.)X
X3651(Once)X
X3857(the)X
X3991(probe)X
X2418 4343(chain)N
X2613(has)X
X2741(exceeded)X
X3062(some)X
X3252(threshold)X
X3571(\(Brent)X
X3796(suggests)X
X4087(2\),)X
X2418 4431(we)N
X2541(attempt)X
X2809(to)X
X2899(shuf\257e)X
X3145(any)X
X3289(colliding)X
X3601(keys)X
X3776(\(keys)X
X3978(which)X
X2418 4519(appeared)N
X2734(in)X
X2821(the)X
X2944(probe)X
X3152(sequence)X
X3471(of)X
X3562(the)X
X3684(new)X
X3842(key\).)X
X4049(The)X
X2418 4607(details)N
X2652(of)X
X2744(this)X
X2884(key)X
X3025(shuf\257ing)X
X3333(can)X
X3469(be)X
X3569(found)X
X3780(in)X
X3866([KNU68])X
X2418 4695(and)N
X2576([BRE73].)X
X2946(This)X
X3129(algorithm)X
X3481(may)X
X3660(be)X
X3777(obtained)X
X4094(by)X
X2418 4783(de\256ning)N
X2700(the)X
X2818(variable)X
X3097(``BRENT'')X
X3487(at)X
X3565(compile)X
X3843(time.)X
X2590 4897(A)N
X2698(third)X
X2899(set)X
X3038(of)X
X3154(options,)X
X3458(obtained)X
X3783(by)X
X3912(de\256ning)X
X2418 4985(``CHAINED'',)N
X2943(use)X
X3086(linked)X
X3321(lists)X
X3484(to)X
X3581(resolve)X
X3848(collisions.)X
X2418 5073(Either)N
X2647(of)X
X2747(the)X
X2878(primary)X
X3164(hash)X
X3343(function)X
X3642(described)X
X3982(above)X
X2418 5161(may)N
X2584(be)X
X2688(used,)X
X2882(but)X
X3011(all)X
X3118(collisions)X
X3451(are)X
X3577(resolved)X
X3876(by)X
X3983(build-)X
X2418 5249(ing)N
X2554(a)X
X2623(linked)X
X2856(list)X
X2986(of)X
X3086(entries)X
X3333(from)X
X3522(the)X
X3653(primary)X
X3940(bucket.)X
X2418 5337(By)N
X2542(default,)X
X2816(new)X
X2981(entries)X
X3226(will)X
X3381(be)X
X3488(added)X
X3711(to)X
X3804(a)X
X3871(bucket)X
X4116(at)X
X2418 5425(the)N
X2541(beginning)X
X2886(of)X
X2978(the)X
X3101(bucket)X
X3339(chain.)X
X3577(However,)X
X3916(compile)X
X2418 5513(options)N
X2706(``SORTUP'')X
X3173(or)X
X3293(``SORTDOWN'')X
X3908(may)X
X4098(be)X
X2418 5601(speci\256ed)N
X2723(to)X
X2805(order)X
X2995(the)X
X3113(hash)X
X3280(chains)X
X3505(within)X
X3729(each)X
X3897(bucket.)X
X3 f
X432 5960(4)N
X2970(USENIX)X
X9 f
X3292(-)X
X3 f
X3356(Winter)X
X3621('91)X
X9 f
X3748(-)X
X3 f
X3812(Dallas,)X
X4065(TX)X
X
X5 p
X%%Page: 5 5
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X720 258(Seltzer)N
X977(&)X
X1064(Yigit)X
X3278(A)X
X3356(New)X
X3528(Hashing)X
X3831(Package)X
X4136(for)X
X4259(UNIX)X
X2 f
X1444 538(dynahash)N
X1 f
X892 670(The)N
X2 f
X1054(dynahash)X
X1 f
X1398(library,)X
X1669(written)X
X1932(by)X
X2048(Esmond)X
X2346(Pitt,)X
X720 758(implements)N
X1183(Larson's)X
X1554(linear)X
X1827(hashing)X
X2165(algorithm)X
X720 846([LAR88])N
X1097(with)X
X1302(an)X
X2 f
X1440(hsearch)X
X1 f
X1756(compatible)X
X2174(interface.)X
X720 934(Intuitively,)N
X1099(a)X
X1161(hash)X
X1334(table)X
X1516(begins)X
X1751(as)X
X1844(a)X
X1905(single)X
X2121(bucket)X
X2360(and)X
X720 1022(grows)N
X941(in)X
X1028(generations,)X
X1443(where)X
X1665(a)X
X1725(generation)X
X2088(corresponds)X
X720 1110(to)N
X815(a)X
X884(doubling)X
X1201(in)X
X1296(the)X
X1427(size)X
X1585(of)X
X1685(the)X
X1815(hash)X
X1994(table.)X
X2222(The)X
X2379(0)X
X2 f
X7 s
X1078(th)Y
X10 s
X1 f
X720 1198(generation)N
X1085(occurs)X
X1321(as)X
X1414(the)X
X1538(table)X
X1719(grows)X
X1940(from)X
X2121(one)X
X2262(bucket)X
X720 1286(to)N
X814(two.)X
X1006(In)X
X1105(the)X
X1235(next)X
X1405(generation)X
X1776(the)X
X1906(table)X
X2093(grows)X
X2320(from)X
X720 1374(two)N
X862(to)X
X946(four.)X
X1122(During)X
X1371(each)X
X1541(generation,)X
X1921(every)X
X2121(bucket)X
X2356(that)X
X720 1462(existed)N
X967(at)X
X1045(the)X
X1163(beginning)X
X1503(of)X
X1590(the)X
X1708(generation)X
X2067(is)X
X2140(split.)X
X892 1576(The)N
X1041(table)X
X1221(starts)X
X1414(as)X
X1505(a)X
X1565(single)X
X1780(bucket)X
X2018(\(numbered)X
X2389(0\),)X
X720 1664(the)N
X839(current)X
X1088(split)X
X1245(bucket)X
X1479(is)X
X1552(set)X
X1661(to)X
X1743(bucket)X
X1977(0,)X
X2057(and)X
X2193(the)X
X2311(max-)X
X720 1752(imum)N
X933(split)X
X1097(point)X
X1288(is)X
X1368(set)X
X1483(to)X
X1571(twice)X
X1771(the)X
X1895(current)X
X2149(split)X
X2312(point)X
X720 1840(\(0\).)N
X863(When)X
X1084(it)X
X1157(is)X
X1239(time)X
X1410(for)X
X1532(a)X
X1596(bucket)X
X1838(to)X
X1928(split,)X
X2113(the)X
X2239(keys)X
X2414(in)X
X720 1928(the)N
X872(current)X
X1154(split)X
X1345(bucket)X
X1612(are)X
X1764(divided)X
X2057(between)X
X2378(the)X
X720 2016(current)N
X981(split)X
X1151(bucket)X
X1397(and)X
X1545(a)X
X1613(new)X
X1779(bucket)X
X2025(whose)X
X2262(bucket)X
X720 2104(number)N
X1000(is)X
X1088(equal)X
X1297(to)X
X1394(1)X
X1469(+)X
X1549(current)X
X1812(split)X
X1984(bucket)X
X2232(+)X
X2311(max-)X
X720 2192(imum)N
X927(split)X
X1085(point.)X
X1310(We)X
X1442(can)X
X1574(determine)X
X1915(which)X
X2131(keys)X
X2298(move)X
X720 2280(to)N
X807(the)X
X929(new)X
X1087(bucket)X
X1325(by)X
X1429(examining)X
X1791(the)X
X2 f
X1913(n)X
X7 s
X1962 2248(th)N
X10 s
X1 f
X2043 2280(bit)N
X2151(of)X
X2242(a)X
X2302(key's)X
X720 2368(hash)N
X899(value)X
X1105(where)X
X1334(n)X
X1406(is)X
X1491(the)X
X1620(generation)X
X1990(number.)X
X2306(After)X
X720 2456(the)N
X846(bucket)X
X1088(at)X
X1174(the)X
X1300(maximum)X
X1651(split)X
X1815(point)X
X2006(has)X
X2140(been)X
X2319(split,)X
X720 2544(the)N
X839(generation)X
X1198(number)X
X1463(is)X
X1536(incremented,)X
X1973(the)X
X2091(current)X
X2339(split)X
X720 2632(point)N
X908(is)X
X985(set)X
X1098(back)X
X1274(to)X
X1360(zero,)X
X1543(and)X
X1683(the)X
X1805(maximum)X
X2152(split)X
X2312(point)X
X720 2720(is)N
X815(set)X
X946(to)X
X1050(the)X
X1190(number)X
X1477(of)X
X1586(the)X
X1725(last)X
X1877(bucket)X
X2132(in)X
X2235(the)X
X2374(\256le)X
X720 2808(\(which)N
X971(is)X
X1052(equal)X
X1253(to)X
X1342(twice)X
X1543(the)X
X1668(old)X
X1797(maximum)X
X2148(split)X
X2312(point)X
X720 2896(plus)N
X873(1\).)X
X892 3010(To)N
X1031(facilitate)X
X1361(locating)X
X1668(keys,)X
X1884(we)X
X2027(maintain)X
X2356(two)X
X720 3098(masks.)N
X989(The)X
X1143(low)X
X1291(mask)X
X1488(is)X
X1569(equal)X
X1771(to)X
X1861(the)X
X1987(maximum)X
X2339(split)X
X720 3186(bucket)N
X967(and)X
X1116(the)X
X1247(high)X
X1422(mask)X
X1624(is)X
X1710(equal)X
X1917(to)X
X2011(the)X
X2141(next)X
X2311(max-)X
X720 3274(imum)N
X931(split)X
X1093(bucket.)X
X1372(To)X
X1486(locate)X
X1703(a)X
X1764(speci\256c)X
X2033(key,)X
X2193(we)X
X2311(com-)X
X720 3362(pute)N
X881(a)X
X940(32-bit)X
X1154(hash)X
X1324(value)X
X1520(using)X
X1715(a)X
X1773(bit-randomizing)X
X2311(algo-)X
X720 3450(rithm)N
X932(such)X
X1118(as)X
X1224(the)X
X1361(one)X
X1516(described)X
X1862(in)X
X1962([LAR88].)X
X2334(This)X
X720 3538(hash)N
X893(value)X
X1093(is)X
X1172(then)X
X1336(masked)X
X1607(with)X
X1775(the)X
X1898(high)X
X2065(mask.)X
X2299(If)X
X2378(the)X
X720 3626(resulting)N
X1026(number)X
X1297(is)X
X1376(greater)X
X1626(than)X
X1790(the)X
X1913(maximum)X
X2262(bucket)X
X720 3714(in)N
X823(the)X
X962(table)X
X1159(\(current)X
X1455(split)X
X1633(bucket)X
X1888(+)X
X1974(maximum)X
X2339(split)X
X720 3802(point\),)N
X962(the)X
X1091(hash)X
X1269(value)X
X1474(is)X
X1558(masked)X
X1834(with)X
X2007(the)X
X2136(low)X
X2287(mask.)X
X720 3890(In)N
X825(either)X
X1046(case,)X
X1242(the)X
X1377(result)X
X1592(of)X
X1696(the)X
X1831(mask)X
X2037(is)X
X2127(the)X
X2262(bucket)X
X720 3978(number)N
X989(for)X
X1107(the)X
X1229(given)X
X1431(key.)X
X1611(The)X
X1759(algorithm)X
X2093(below)X
X2312(illus-)X
X720 4066(trates)N
X914(this)X
X1049(process.)X
X0 f
X8 s
X720 4365(h)N
X796(=)X
X872 -0.4038(calchash\(key\);)AX
X720 4453(bucket)N
X986(=)X
X1062(h)X
X1138(&)X
X1214 -0.4167(high_mask;)AX
X720 4541(if)N
X834(\()X
X910(bucket)X
X1176(>)X
X1252 -0.4167(max_bucket)AX
X1670(\))X
X1008 4629(bucket)N
X1274(=)X
X1350(h)X
X1426(&)X
X1502 -0.4219(low_mask;)AX
X720 4717 -0.4018(return\(bucket\);)AN
X1 f
X10 s
X892 5042(In)N
X1013(order)X
X1237(to)X
X1353(decide)X
X1617(when)X
X1845(to)X
X1961(split)X
X2152(a)X
X2242(bucket,)X
X2 f
X720 5130(dynahash)N
X1 f
X1050(uses)X
X2 f
X1210(controlled)X
X1561(splitting)X
X1 f
X1822(.)X
X1884(A)X
X1964(hash)X
X2133(table)X
X2311(has)X
X2440(a)X
X720 5218(\256ll)N
X837(factor)X
X1054(which)X
X1279(is)X
X1361(expressed)X
X1707(in)X
X1798(terms)X
X2004(of)X
X2099(the)X
X2225(average)X
X720 5306(number)N
X990(of)X
X1082(keys)X
X1253(in)X
X1339(each)X
X1511(bucket.)X
X1789(Each)X
X1974(time)X
X2140(the)X
X2262(table's)X
X720 5394(total)N
X885(number)X
X1153(of)X
X1243(keys)X
X1413(divided)X
X1676(by)X
X1778(its)X
X1875(number)X
X2142(of)X
X2231(buckets)X
X720 5482(exceeds)N
X995(this)X
X1130(\256ll)X
X1238(factor,)X
X1466(a)X
X1522(bucket)X
X1756(is)X
X1829(split.)X
X2878 538(Since)N
X3079(the)X
X2 f
X3200(hsearch)X
X1 f
X3477(create)X
X3693(interface)X
X3998(\()X
X2 f
X4025(hcreate)X
X1 f
X4266(\))X
X4315(calls)X
X2706 626(for)N
X2842(an)X
X2960(estimate)X
X3269(of)X
X3378(the)X
X3518(\256nal)X
X3702(size)X
X3869(of)X
X3978(the)X
X4118(hash)X
X4306(table)X
X2706 714(\()N
X2 f
X2733(nelem)X
X1 f
X2925(\),)X
X2 f
X3007(dynahash)X
X1 f
X3349(uses)X
X3522(this)X
X3672(information)X
X4085(to)X
X4182(initialize)X
X2706 802(the)N
X2848(table.)X
X3088(The)X
X3257(initial)X
X3486(number)X
X3774(of)X
X3884(buckets)X
X4172(is)X
X4268(set)X
X4400(to)X
X2 f
X2706 890(nelem)N
X1 f
X2926(rounded)X
X3217(to)X
X3306(the)X
X3431(next)X
X3596(higher)X
X3828(power)X
X4056(of)X
X4150(two.)X
X4337(The)X
X2706 978(current)N
X2958(split)X
X3118(point)X
X3305(is)X
X3381(set)X
X3493(to)X
X3578(0)X
X3641(and)X
X3780(the)X
X3901(maximum)X
X4248(bucket)X
X2706 1066(and)N
X2842(maximum)X
X3186(split)X
X3343(point)X
X3527(are)X
X3646(set)X
X3755(to)X
X3837(this)X
X3972(rounded)X
X4255(value.)X
X3 f
X3148 1220(The)N
X3301(New)X
X3473(Implementation)X
X1 f
X2878 1352(Our)N
X3042(implementation)X
X3583(is)X
X3675(also)X
X3842(based)X
X4063(on)X
X4181(Larson's)X
X2706 1440(linear)N
X2939(hashing)X
X3238([LAR88])X
X3582(algorithm)X
X3943(as)X
X4060(well)X
X4248(as)X
X4364(the)X
X2 f
X2706 1528(dynahash)N
X1 f
X3047(implementation.)X
X3623(The)X
X2 f
X3782(dbm)X
X1 f
X3954(family)X
X4197(of)X
X4297(algo-)X
X2706 1616(rithms)N
X2942(decide)X
X3184(dynamically)X
X3612(which)X
X3840(bucket)X
X4085(to)X
X4178(split)X
X4346(and)X
X2706 1704(when)N
X2914(to)X
X3010(split)X
X3180(it)X
X3257(\(when)X
X3491(it)X
X3568(over\257ows\))X
X3944(while)X
X2 f
X4155(dynahash)X
X1 f
X2706 1792(splits)N
X2933(in)X
X3054(a)X
X3149(prede\256ned)X
X3547(order)X
X3776(\(linearly\))X
X4134(and)X
X4309(at)X
X4426(a)X
X2706 1880(prede\256ned)N
X3116(time)X
X3328(\(when)X
X3599(the)X
X3767(table)X
X3993(\256ll)X
X4151(factor)X
X4409(is)X
X2706 1968(exceeded\).)N
X3121(We)X
X3280(use)X
X3434(a)X
X3517(hybrid)X
X3773(of)X
X3887(these)X
X4099(techniques.)X
X2706 2056(Splits)N
X2913(occur)X
X3118(in)X
X3206(the)X
X3330(prede\256ned)X
X3695(order)X
X3891(of)X
X3984(linear)X
X4193(hashing,)X
X2706 2144(but)N
X2845(the)X
X2980(time)X
X3159(at)X
X3253(which)X
X3485(pages)X
X3704(are)X
X3839(split)X
X4012(is)X
X4101(determined)X
X2706 2232(both)N
X2869(by)X
X2970(page)X
X3143(over\257ows)X
X3480(\()X
X2 f
X3507(uncontrolled)X
X3937(splitting)X
X1 f
X4198(\))X
X4246(and)X
X4382(by)X
X2706 2320(exceeding)N
X3052(the)X
X3170(\256ll)X
X3278(factor)X
X3486(\()X
X2 f
X3513(controlled)X
X3862(splitting)X
X1 f
X4123(\))X
X2878 2434(A)N
X2962(hash)X
X3135(table)X
X3317(is)X
X3395(parameterized)X
X3876(by)X
X3981(both)X
X4148(its)X
X4248(bucket)X
X2706 2522(size)N
X2904(\()X
X2 f
X2931(bsize)X
X1 f
X(\))S
X3191(and)X
X3380(\256ll)X
X3541(factor)X
X3801(\()X
X2 f
X3828(ffactor)X
X1 f
X4041(\).)X
X4180(Whereas)X
X2 f
X2706 2610(dynahash's)N
X1 f
X3095(buckets)X
X3364(can)X
X3500(be)X
X3599(represented)X
X3993(as)X
X4083(a)X
X4142(linked)X
X4365(list)X
X2706 2698(of)N
X2798(elements)X
X3108(in)X
X3195(memory,)X
X3507(our)X
X3639(package)X
X3928(needs)X
X4136(to)X
X4222(support)X
X2706 2786(disk)N
X2874(access,)X
X3135(and)X
X3286(must)X
X3476(represent)X
X3806(buckets)X
X4086(in)X
X4183(terms)X
X4395(of)X
X2706 2874(pages.)N
X2955(The)X
X2 f
X3106(bsize)X
X1 f
X3291(is)X
X3369(the)X
X3492(size)X
X3642(\(in)X
X3756(bytes\))X
X3977(of)X
X4069(these)X
X4259(pages.)X
X2706 2962(As)N
X2833(in)X
X2933(linear)X
X3154(hashing,)X
X3461(the)X
X3597(number)X
X3879(of)X
X3983(buckets)X
X4265(in)X
X4364(the)X
X2706 3050(table)N
X2906(is)X
X3003(equal)X
X3221(to)X
X3327(the)X
X3469(number)X
X3758(of)X
X3869(keys)X
X4060(in)X
X4165(the)X
X4306(table)X
X2706 3138(divided)N
X2988(by)X
X2 f
X3110(ffactor)X
X1 f
X3323(.)X
X2 f
X8 s
X3113(6)Y
X1 f
X10 s
X3417 3138(The)N
X3584(controlled)X
X3950(splitting)X
X4252(occurs)X
X2706 3226(each)N
X2878(time)X
X3044(the)X
X3166(number)X
X3435(of)X
X3526(keys)X
X3697(in)X
X3783(the)X
X3905(table)X
X4085(exceeds)X
X4364(the)X
X2706 3314(\256ll)N
X2814(factor)X
X3022(multiplied)X
X3370(by)X
X3470(the)X
X3588(number)X
X3853(of)X
X3940(buckets.)X
X2878 3428(Inserting)N
X3187(keys)X
X3358(and)X
X3498(splitting)X
X3783(buckets)X
X4051(is)X
X4127(performed)X
X2706 3516(precisely)N
X3018(as)X
X3107(described)X
X3437(previously)X
X3796(for)X
X2 f
X3911(dynahash)X
X1 f
X4218(.)X
X4279(How-)X
X2706 3604(ever,)N
X2897(since)X
X3094(buckets)X
X3371(are)X
X3502(now)X
X3671(comprised)X
X4036(of)X
X4134(pages,)X
X4368(we)X
X2706 3692(must)N
X2883(be)X
X2981(prepared)X
X3284(to)X
X3367(handle)X
X3602(cases)X
X3793(where)X
X4011(the)X
X4130(size)X
X4276(of)X
X4364(the)X
X2706 3780(keys)N
X2873(and)X
X3009(data)X
X3163(in)X
X3245(a)X
X3301(bucket)X
X3535(exceed)X
X3779(the)X
X3897(bucket)X
X4131(size.)X
X3 f
X3318 3934(Over\257ow)N
X3654(Pages)X
X1 f
X2878 4066(There)N
X3095(are)X
X3223(two)X
X3372(cases)X
X3571(where)X
X3797(a)X
X3862(key)X
X4007(may)X
X4174(not)X
X4305(\256t)X
X4400(in)X
X2706 4154(its)N
X2802(designated)X
X3166(bucket.)X
X3441(In)X
X3529(the)X
X3647(\256rst)X
X3791(case,)X
X3970(the)X
X4088(total)X
X4250(size)X
X4395(of)X
X2706 4242(the)N
X2833(key)X
X2978(and)X
X3123(data)X
X3286(may)X
X3453(exceed)X
X3706(the)X
X3833(bucket)X
X4076(size.)X
X4269(In)X
X4364(the)X
X2706 4330(second,)N
X3008(addition)X
X3328(of)X
X3453(a)X
X3547(new)X
X3739(key)X
X3913(could)X
X4149(cause)X
X4386(an)X
X2706 4418(over\257ow,)N
X3068(but)X
X3227(the)X
X3382(bucket)X
X3652(in)X
X3770(question)X
X4097(is)X
X4206(not)X
X4364(yet)X
X2706 4506(scheduled)N
X3049(to)X
X3133(be)X
X3230(split.)X
X3428(In)X
X3516(existing)X
X3790(implementations,)X
X4364(the)X
X2706 4594(second)N
X2953(case)X
X3115(never)X
X3317(arises)X
X3523(\(since)X
X3738(buckets)X
X4006(are)X
X4128(split)X
X4288(when)X
X2706 4682(they)N
X2871(over\257ow\))X
X3210(and)X
X3352(the)X
X3476(\256rst)X
X3626(case)X
X3791(is)X
X3870(not)X
X3998(handled)X
X4278(at)X
X4362(all.)X
X2706 4770(Although)N
X3036(large)X
X3225(key/data)X
X3525(pair)X
X3678(handling)X
X3986(is)X
X4066(dif\256cult)X
X4346(and)X
X2706 4858(expensive,)N
X3083(it)X
X3163(is)X
X3252(essential.)X
X3604(In)X
X3706(a)X
X3777(linear)X
X3995(hashed)X
X4253(imple-)X
X2706 4946(mentation,)N
X3087(over\257ow)X
X3413(pages)X
X3636(are)X
X3775(required)X
X4083(for)X
X4217(buckets)X
X2706 5034(which)N
X2935(over\257ow)X
X3253(before)X
X3492(they)X
X3662(are)X
X3793(split,)X
X3982(so)X
X4085(we)X
X4211(can)X
X4355(use)X
X2706 5122(the)N
X2833(same)X
X3027(mechanism)X
X3421(for)X
X3544(large)X
X3734(key/data)X
X4035(pairs)X
X4220(that)X
X4368(we)X
X2706 5210(use)N
X2837(for)X
X2955(over\257ow)X
X3264(pages.)X
X3511(Logically,)X
X3862(we)X
X3980(chain)X
X4177(over\257ow)X
X16 s
X2706 5353 MXY
X864 0 Dl
X2 f
X8 s
X2746 5408(6)N
X1 f
X9 s
X2801 5433(This)N
X2952(is)X
X3023(not)X
X3138(strictly)X
X3361(true.)X
X3532(The)X
X3667(\256le)X
X3782(does)X
X3937(not)X
X4052(contract)X
X4306(when)X
X2706 5513(keys)N
X2861(are)X
X2972(deleted,)X
X3221(so)X
X3308(the)X
X3419(number)X
X3662(of)X
X3744(buckets)X
X3986(is)X
X4056(actually)X
X4306(equal)X
X2706 5593(to)N
X2782(the)X
X2890(maximum)X
X3202(number)X
X3441(of)X
X3520(keys)X
X3671(ever)X
X3814(present)X
X4041(in)X
X4116(the)X
X4223(table)X
X4382(di-)X
X2706 5673(vided)N
X2884(by)X
X2974(the)X
X3080(\256ll)X
X3178(factor.)X
X3 f
X10 s
X720 5960(USENIX)N
X9 f
X1042(-)X
X3 f
X1106(Winter)X
X1371('91)X
X9 f
X1498(-)X
X3 f
X1562(Dallas,)X
X1815(TX)X
X4424(5)X
X
X6 p
X%%Page: 6 6
X0(Courier)xf 0 f
X10 s 10 xH 0 xS 0 f
X3 f
X432 258(A)N
X510(New)X
X682(Hashing)X
X985(Package)X
X1290(for)X
X1413(UNIX)X
X3663(Seltzer)X
X3920(&)X
X4007(Yigit)X
X1 f
X432 538(pages)N
X639(to)X
X725(the)X
X847(buckets)X
X1116(\(also)X
X1296(called)X
X1512(primary)X
X1789(pages\).)X
X2062(In)X
X2152(a)X
X432 626(memory)N
X730(based)X
X943(representation,)X
X1448(over\257ow)X
X1763(pages)X
X1976(do)X
X2086(not)X
X432 714(pose)N
X628(any)X
X792(special)X
X1063(problems)X
X1409(because)X
X1712(we)X
X1854(can)X
X2014(chain)X
X432 802(over\257ow)N
X776(pages)X
X1017(to)X
X1137(primary)X
X1449(pages)X
X1690(using)X
X1921(memory)X
X432 890(pointers.)N
X776(However,)X
X1137(mapping)X
X1463(these)X
X1674(over\257ow)X
X2005(pages)X
X432 978(into)N
X584(a)X
X648(disk)X
X809(\256le)X
X939(is)X
X1019(more)X
X1211(of)X
X1305(a)X
X1368(challenge,)X
X1723(since)X
X1915(we)X
X2036(need)X
X432 1066(to)N
X547(be)X
X675(able)X
X861(to)X
X975(address)X
X1268(both)X
X1462(bucket)X
X1728(pages,)X
X1983(whose)X
X432 1154(numbers)N
X729(are)X
X849(growing)X
X1137(linearly,)X
X1422(and)X
X1558(some)X
X1747(indeterminate)X
X432 1242(number)N
X715(of)X
X820(over\257ow)X
X1143(pages)X
X1364(without)X
X1646(reorganizing)X
X2090(the)X
X432 1330(\256le.)N
X604 1444(One)N
X789(simple)X
X1053(solution)X
X1361(would)X
X1612(be)X
X1739(to)X
X1852(allocate)X
X2152(a)X
X432 1532(separate)N
X737(\256le)X
X880(for)X
X1015(over\257ow)X
X1341(pages.)X
X1604(The)X
X1769(disadvantage)X
X432 1620(with)N
X605(such)X
X783(a)X
X850(technique)X
X1193(is)X
X1276(that)X
X1426(it)X
X1500(requires)X
X1789(an)X
X1895(extra)X
X2086(\256le)X
X432 1708(descriptor,)N
X794(an)X
X891(extra)X
X1073(system)X
X1316(call)X
X1453(on)X
X1554(open)X
X1731(and)X
X1867(close,)X
X2072(and)X
X432 1796(logically)N
X739(associating)X
X1122(two)X
X1269(independent)X
X1687(\256les.)X
X1886(For)X
X2023(these)X
X432 1884(reasons,)N
X728(we)X
X857(wanted)X
X1123(to)X
X1219(map)X
X1391(both)X
X1567(primary)X
X1855(pages)X
X2072(and)X
X432 1972(over\257ow)N
X737(pages)X
X940(into)X
X1084(the)X
X1202(same)X
X1387(\256le)X
X1509(space.)X
X604 2086(The)N
X799(buddy-in-waiting)X
X1425(algorithm)X
X1806(provides)X
X2152(a)X
X432 2174(mechanism)N
X851(to)X
X966(support)X
X1259(multiple)X
X1578(pages)X
X1814(per)X
X1970(logical)X
X432 2262(bucket)N
X685(while)X
X902(retaining)X
X1226(the)X
X1362(simple)X
X1613(split)X
X1788(sequence)X
X2121(of)X
X432 2350(linear)N
X681(hashing.)X
X1015(Over\257ow)X
X1383(pages)X
X1631(are)X
X1795(preallocated)X
X432 2438(between)N
X781(generations)X
X1232(of)X
X1379(primary)X
X1713(pages.)X
X1996(These)X
X432 2526(over\257ow)N
X759(pages)X
X984(are)X
X1125(used)X
X1314(by)X
X1436(any)X
X1594(bucket)X
X1850(containing)X
X432 2614(more)N
X646(keys)X
X842(than)X
X1029(\256t)X
X1144(on)X
X1273(the)X
X1420(primary)X
X1723(page)X
X1924(and)X
X2089(are)X
X432 2702(reclaimed,)N
X808(if)X
X896(possible,)X
X1217(when)X
X1430(the)X
X1567(bucket)X
X1819(later)X
X2000(splits.)X
X432 2790(Figure)N
X687(3)X
X773(depicts)X
X1045(the)X
X1188(layout)X
X1433(of)X
X1545(primary)X
X1844(pages)X
X2072(and)X
X432 2878(over\257ow)N
X752(pages)X
X970(within)X
X1209(the)X
X1342(same)X
X1542(\256le.)X
X1699(Over\257ow)X
X2036(page)X
X432 2966(use)N
X586(information)X
X1011(is)X
X1111(recorded)X
X1440(in)X
X1548(bitmaps)X
X1847(which)X
X2089(are)X
X432 3054(themselves)N
X819(stored)X
X1046(on)X
X1157(over\257ow)X
X1472(pages.)X
X1725(The)X
X1880(addresses)X
X432 3142(of)N
X520(the)X
X639(bitmap)X
X882(pages)X
X1086(and)X
X1223(the)X
X1342(number)X
X1608(of)X
X1695(pages)X
X1898(allocated)X
X432 3230(at)N
X515(each)X
X688(split)X
X850(point)X
X1039(are)X
X1163(stored)X
X1384(in)X
X1470(the)X
X1592(\256le)X
X1718(header.)X
X1997(Using)X
X432 3318(this)N
X577(information,)X
X1005(both)X
X1177(over\257ow)X
X1492(addresses)X
X1829(and)X
X1974(bucket)X
X432 3406(addresses)N
X764(can)X
X900(be)X
X999(mapped)X
X1276(to)X
X1361(disk)X
X1517(addresses)X
X1848(by)X
X1951(the)X
X2072(fol-)X
X432 3494(lowing)N
X674(calculation:)X
X0 f
X8 s
X432 3793(int)N
X736(bucket;)X
X1192(/*)X
X1306(bucket)X
X1572(address)X
X1876(*/)X
X432 3881(u_short)N
X736(oaddr;)X
X1192(/*)X
X1306(OVERFLOW)X
X1648(address)X
X1952(*/)X
X432 3969(int)N
X736 -0.4125(nhdr_pages;)AX
X1192(/*)X
X1306(npages)X
X1572(in)X
X1686 -112.4062(\256le)AX
X1838(header)X
X2104(*/)X
X432 4057(int)N
X736 -0.4125(spares[32];)AX
X1192(/*)X
X1306(npages)X
X1572(at)X
X1686(each)X
X1876(split)X
X2104(*/)X
X432 4145(int)N
X736(log2\(\);)X
X1198(/*)X
X1312(ceil\(log)X
X1654(base)X
X1844(2\))X
X1958(*/)X
X432 4321(#DEFINE)N
X736 -0.3929(BUCKET_TO_PAGE\(bucket\))AX
X1610(\\)X
X584 4409(bucket)N
X850(+)X
X926 -0.4167(nhdr_pages)AX
X1344(+)X
X1420(\\)X
X584 4497 -0.3894(\(bucket?spares[logs2\(bucket)AN
X1648(+)X
X1724(1\)-1]:0\))X
X432 4673(#DEFINE)N
X736 -0.3947(OADDR_TO_PAGE\(oaddr\))AX
X1534(\\)X
X584 4761 -0.3984(BUCKET_TO_PAGE\(\(1)AN
X1268(<<)X
X1382 -0.4091(\(oaddr>>11\)\))AX
X1876(-)X
X1952(1\))X
X2066(+)X
X2142(\\)X
X584 4849(oaddr)N
X812(&)X
X888(0x7ff;)X
X1 f
X10 s
X604 5262(An)N
X728(over\257ow)X
X1039(page)X
X1217(is)X
X1295(addressed)X
X1637(by)X
X1742(its)X
X1842(split)X
X2004(point,)X
X432 5350(identifying)N
X858(the)X
X1031(generations)X
X1476(between)X
X1819(which)X
X2090(the)X
X432 5438(over\257ow)N
X740(page)X
X915(is)X
X991(allocated,)X
X1324(and)X
X1463(its)X
X1561(page)X
X1736(number,)X
X2023(iden-)X
X432 5526(tifying)N
X665(the)X
X783(particular)X
X1111(page)X
X1283(within)X
X1507(the)X
X1625(split)X
X1782(point.)X
X1986(In)X
X2073(this)X
X432 5614(implementation,)N
X983(offsets)X
X1225(within)X
X1457(pages)X
X1668(are)X
X1795(16)X
X1903(bits)X
X2046(long)X
X432 5702(\(limiting)N
X732(the)X
X851(maximum)X
X1196(page)X
X1368(size)X
X1513(to)X
X1595(32K\),)X
X1800(so)X
X1891(we)X
X2005(select)X
X2418 538(an)N
X2535(over\257ow)X
X2860(page)X
X3052(addressing)X
X3435(algorithm)X
X3786(that)X
X3946(can)X
X4098(be)X
X2418 626(expressed)N
X2760(in)X
X2847(16)X
X2952(bits)X
X3091(and)X
X3231(which)X
X3451(allows)X
X3684(quick)X
X3886(retrieval.)X
X2418 714(The)N
X2568(top)X
X2695(\256ve)X
X2840(bits)X
X2980(indicate)X
X3258(the)X
X3380(split)X
X3541(point)X
X3729(and)X
X3869(the)X
X3991(lower)X
X2418 802(eleven)N
X2650(indicate)X
X2926(the)X
X3046(page)X
X3220(number)X
X3487(within)X
X3713(the)X
X3832(split)X
X3990(point.)X
X2418 890(Since)N
X2633(\256ve)X
X2789(bits)X
X2940(are)X
X3075(reserved)X
X3384(for)X
X3514(the)X
X3648(split)X
X3821(point,)X
X4041(\256les)X
X2418 978(may)N
X2578(split)X
X2737(32)X
X2839(times)X
X3034(yielding)X
X3318(a)X
X3376(maximum)X
X3721(\256le)X
X3844(size)X
X3990(of)X
X4078(2)X
X7 s
X946(32)Y
X10 s
X2418 1066(buckets)N
X2698(and)X
X2849(32)X
X2 f
X(*)S
X1 f
X2982(2)X
X7 s
X1034(11)Y
X10 s
X3113 1066(over\257ow)N
X3433(pages.)X
X3691(The)X
X3850(maximum)X
X2418 1154(page)N
X2597(size)X
X2749(is)X
X2829(2)X
X7 s
X1122(15)Y
X10 s
X1154(,)Y
X2971(yielding)X
X3259(a)X
X3321(maximum)X
X3671(\256le)X
X3799(size)X
X3950(greater)X
X2418 1242(than)N
X2601(131,000)X
X2906(GB)X
X3061(\(on)X
X3212(\256le)X
X3358(systems)X
X3655(supporting)X
X4041(\256les)X
X2418 1330(larger)N
X2626(than)X
X2784(4GB\).)X
X10 f
X2418 1418 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X1 Dt
X4014 2275 MXY
X0 133 Dl
X3881 2275 MXY
X0 133 Dl
X3748 2275 MXY
X0 133 Dl
X3083 2275 MXY
X0 133 Dl
X5 s
X1 f
X3523 2475(2/3)N
X3390(2/2)X
X3257(2/1)X
X2859(1/2)X
X2726(1/1)X
X5 Dt
X3814 1743 MXY
X0 133 Dl
X3282 1743 MXY
X0 133 Dl
X3017 1743 MXY
X0 133 Dl
X2884 1743 MXY
X0 133 Dl
X1 Dt
X3681 1743 MXY
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3548 MX
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3415 MX
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3282 MX
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3150 MX
X0 133 Dl
X132 0 Dl
X0 -133 Dl
X-132 0 Dl
X3017 MX
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X2884 MX
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3 f
X8 s
X3017 2601(Over\257ow)N
X3285(Addresses)X
X3515 2833(Over\257ow)N
X3783(Pages)X
X2850(Buckets)X
X1 Di
X3349 2740 MXY
X 3349 2740 lineto
X 3482 2740 lineto
X 3482 2873 lineto
X 3349 2873 lineto
X 3349 2740 lineto
Xclosepath 3 3349 2740 3482 2873 Dp
X2684 MX
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X5 Dt
X4146 2275 MXY
X0 133 Dl
X3216 2275 MXY
X0 133 Dl
X2684 2275 MXY
X0 133 Dl
X2551 2275 MXY
X0 133 Dl
X1 f
X3798 1963(3)N
X3266 1980(2)N
X3001(1)X
X2868(0)X
X1 Dt
X2751 1743 MXY
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3548 2275 MXY
X-15 -22 Dl
X2 16 Dl
X-13 11 Dl
X26 -5 Dl
X-282 -117 Dl
X3432 2275 MXY
X-10 -25 Dl
X-2 16 Dl
X-15 8 Dl
X27 1 Dl
X-166 -117 Dl
X3282 2275 MXY
X12 -25 Dl
X-14 10 Dl
X-15 -6 Dl
X17 21 Dl
X-16 -117 Dl
X2884 2275 MXY
X26 7 Dl
X-12 -12 Dl
X3 -16 Dl
X-17 21 Dl
X382 -117 Dl
X2751 2275 MXY
X25 9 Dl
X-11 -12 Dl
X5 -17 Dl
X-19 20 Dl
X515 -117 Dl
X3 f
X3070 2152(Over\257ow)N
X3338(Pages)X
X3482 2275 MXY
X 3482 2275 lineto
X 3615 2275 lineto
X 3615 2408 lineto
X 3482 2408 lineto
X 3482 2275 lineto
Xclosepath 3 3482 2275 3615 2408 Dp
X3349 MX
X 3349 2275 lineto
X 3482 2275 lineto
X 3482 2408 lineto
X 3349 2408 lineto
X 3349 2275 lineto
Xclosepath 3 3349 2275 3482 2408 Dp
X3216 MX
X 3216 2275 lineto
X 3349 2275 lineto
X 3349 2408 lineto
X 3216 2408 lineto
X 3216 2275 lineto
Xclosepath 3 3216 2275 3349 2408 Dp
X2817 MX
X 2817 2275 lineto
X 2950 2275 lineto
X 2950 2408 lineto
X 2817 2408 lineto
X 2817 2275 lineto
Xclosepath 3 2817 2275 2950 2408 Dp
X2684 MX
X 2684 2275 lineto
X 2817 2275 lineto
X 2817 2408 lineto
X 2684 2408 lineto
X 2684 2275 lineto
Xclosepath 3 2684 2275 2817 2408 Dp
X3615 MX
X0 133 Dl
X531 0 Dl
X0 -133 Dl
X-531 0 Dl
X2950 MX
X0 133 Dl
X266 0 Dl
X0 -133 Dl
X-266 0 Dl
X2551 MX
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3798 1726 MXY
X-21 -18 Dl
X6 16 Dl
X-10 13 Dl
X25 -11 Dl
X-599 -99 Dl
X3266 1726 MXY
X-1 -27 Dl
X-7 15 Dl
X-17 1 Dl
X25 11 Dl
X-67 -99 Dl
X3033 1726 MXY
X27 1 Dl
X-14 -8 Dl
X-1 -17 Dl
X-12 24 Dl
X166 -99 Dl
X2900 1726 MXY
X27 7 Dl
X-13 -11 Dl
X3 -17 Dl
X-17 21 Dl
X299 -99 Dl
X3058 1621(Split)N
X3203(Points)X
X2418 2275 MXY
X0 133 Dl
X133 0 Dl
X0 -133 Dl
X-133 0 Dl
X3 Dt
X-1 Ds
X3137(Figure)Y
X2619(3:)X
X1 f
X2691(Split)X
X2832(points)X
X3008(occur)X
X3168(between)X
X3399(generations)X
X3712(and)X
X3823(are)X
X3919(numbered)X
X2418 3225(from)N
X2560(0.)X
X2642(In)X
X2713(this)X
X2824(\256gure)X
X2991(there)X
X3136(are)X
X3231(two)X
X3345(over\257ow)X
X3590(pages)X
X3753(allocated)X
X4000(at)X
X4063(split)X
X2418 3313(point)N
X2566(1)X
X2614(and)X
X2722(three)X
X2865(allocated)X
X3111(at)X
X3173(split)X
X3300(point)X
X3448(2.)X
X10 s
X10 f
X2418 3489 -0.0930(hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh)AN
X3 f
X2949 3731(Buffer)N
X3192(Management)X
X1 f
X2590 3863(The)N
X2744(hash)X
X2920(table)X
X3105(is)X
X3187(stored)X
X3412(in)X
X3502(memory)X
X3797(as)X
X3892(a)X
X3956(logical)X
X2418 3951(array)N
X2633(of)X
X2749(bucket)X
X3012(pointers.)X
X3359(Physically,)X
X3761(the)X
X3907(array)X
X4121(is)X
X2418 4039(arranged)N
X2728(in)X
X2818(segments)X
X3144(of)X
X3239(256)X
X3387(pointers.)X
X3713(Initially,)X
X4013(there)X
X2418 4127(is)N
X2530(space)X
X2767(to)X
X2887(allocate)X
X3195(256)X
X3373(segments.)X
X3769(Reallocation)X
X2418 4215(occurs)N
X2651(when)X
X2847(the)X
X2967(number)X
X3234(of)X
X3323(buckets)X
X3590(exceeds)X
X3867(32K)X
X4027(\(256)X
X2418 4303(*)N
X2508(256\).)X
X2745(Primary)X
X3053(pages)X
X3286(may)X
X3473(be)X
X3598(accessed)X
X3929(directly)X
X2418 4391(through)N
X2711(the)X
X2853(array)X
X3062(by)X
X3185(bucket)X
X3442(number)X
X3730(and)X
X3889(over\257ow)X
X2418 4479(pages)N
X2628(are)X
X2754 0.4028(referenced)AX
X3122(logically)X
X3429(by)X
X3536(their)X
X3710(over\257ow)X
X4022(page)X
X2418 4567(address.)N
X2726(For)X
X2864(small)X
X3063(hash)X
X3236(tables,)X
X3469(it)X
X3539(is)X
X3618(desirable)X
X3934(to)X
X4022(keep)X
X2418 4655(all)N
X2525(pages)X
X2735(in)X
X2823(main)X
X3009(memory)X
X3302(while)X
X3506(on)X
X3612(larger)X
X3826(tables,)X
X4059(this)X
X2418 4743(is)N
X2523(probably)X
X2860(impossible.)X
X3298(To)X
X3438(satisfy)X
X3698(both)X
X3891(of)X
X4009(these)X
X2418 4831(requirements,)N
X2900(the)X
X3041(package)X
X3348(includes)X
X3658(buffer)X
X3897(manage-)X
X2418 4919(ment)N
X2598(with)X
X2760(LRU)X
X2940(\(least)X
X3134(recently)X
X3413(used\))X
X3607(replacement.)X
X2590 5033(By)N
X2730(default,)X
X3020(the)X
X3165(package)X
X3475(allocates)X
X3802(up)X
X3928(to)X
X4036(64K)X
X2418 5121(bytes)N
X2616(of)X
X2712(buffered)X
X3014(pages.)X
X3246(All)X
X3377(pages)X
X3589(in)X
X3680(the)X
X3807(buffer)X
X4032(pool)X
X2418 5209(are)N
X2542(linked)X
X2766(in)X
X2852(LRU)X
X3036(order)X
X3230(to)X
X3316(facilitate)X
X3621(fast)X
X3761(replacement.)X
X2418 5297(Whereas)N
X2724(ef\256cient)X
X3011(access)X
X3241(to)X
X3327(primary)X
X3605(pages)X
X3812(is)X
X3889(provided)X
X2418 5385(by)N
X2521(the)X
X2642(bucket)X
X2879(array,)X
X3087(ef\256cient)X
X3372(access)X
X3600(to)X
X3684(over\257ow)X
X3991(pages)X
X2418 5473(is)N
X2501(provided)X
X2816(by)X
X2926(linking)X
X3182(over\257ow)X
X3497(page)X
X3679(buffers)X
X3936(to)X
X4027(their)X
X2418 5561(predecessor)N
X2827(page)X
X3008(\(either)X
X3247(the)X
X3374(primary)X
X3657(page)X
X3838(or)X
X3933(another)X
X2418 5649(over\257ow)N
X2742(page\).)X
X3000(This)X
X3181(means)X
X3425(that)X
X3584(an)X
X3699(over\257ow)X
X4022(page)X
X3 f
X432 5960(6)N
X2970(USENIX)X
X9 f
X3292(-)X
X3 f
X3356(Winter)X
X3621('91)X
X9 f
X3748(-)X
X3 f
X3812(Dallas,)X
X4065(TX)X
X
X7 p
END_OF_FILE
if test 84295 -ne `wc -c <'doc/hash.ps.01'`; then
    echo shar: \"'doc/hash.ps.01'\" unpacked with wrong size!
fi
# end of 'doc/hash.ps.01'
fi
echo shar: End of archive 9 \(of 9\).
cp /dev/null ark9isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 9 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 9 archives.
    rm -f ark[1-9]isdone ark[1-9][0-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0