path: root/ext/SDBM_File/sdbm/readme.ps

%!PS-Adobe-1.0
%%Creator: yetti:oz (Ozan Yigit)
%%Title: stdin (ditroff)
%%CreationDate: Thu Dec 13 15:56:08 1990
%%EndComments
% lib/psdit.pro -- prolog for psdit (ditroff) files
% Copyright (c) 1984, 1985 Adobe Systems Incorporated. All Rights Reserved.
% last edit: shore Sat Nov 23 20:28:03 1985
% RCSID: $Header: psdit.pro,v 2.1 85/11/24 12:19:43 shore Rel $

/$DITroff 140 dict def $DITroff begin
/fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
/xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
  /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
  /pagesave save def}def
/PB{save /psv exch def currentpoint translate 
  resolution 72 div dup neg scale 0 0 moveto}def
/PE{psv restore}def
/arctoobig 90 def /arctoosmall .05 def
/m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
/tan{dup sin exch cos div}def
/point{resolution 72 div mul}def
/dround	{transform round exch round exch itransform}def
/xT{/devname exch def}def
/xr{/mh exch def /my exch def /resolution exch def}def
/xp{}def
/xs{docsave restore end}def
/xt{}def
/xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
 {fonts slotno fontname findfont put fontnames slotno fontname put}if}def
/xH{/fontheight exch def F}def
/xS{/fontslant exch def F}def
/s{/fontsize exch def /fontheight fontsize def F}def
/f{/fontnum exch def F}def
/F{fontheight 0 le {/fontheight fontsize def}if
   fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
   fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
   makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def
/X{exch currentpoint exch pop moveto show}def
/N{3 1 roll moveto show}def
/Y{exch currentpoint pop exch moveto show}def
/S{show}def
/ditpush{}def/ditpop{}def
/AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def
/AN{4 2 roll moveto 0 exch ashow}def
/AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def
/AS{0 exch ashow}def
/MX{currentpoint exch pop moveto}def
/MY{currentpoint pop exch moveto}def
/MXY{moveto}def
/cb{pop}def	% action on unknown char -- nothing for now
/n{}def/w{}def
/p{pop showpage pagesave restore /pagesave save def}def
/abspoint{currentpoint exch pop add exch currentpoint pop add exch}def
/distance{dup mul exch dup mul add sqrt}def
/dstroke{currentpoint stroke moveto}def
/Dl{2 copy gsave rlineto stroke grestore rmoveto}def
/arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop
 currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
 currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def
/Dc{dup arcellipse dstroke}def
/De{arcellipse dstroke}def
/Da{/endv exch def /endh exch def /centerv exch def /centerh exch def
 /cradius centerv centerv mul centerh centerh mul add sqrt def
 /eradius endv endv mul endh endh mul add sqrt def
 /endang endv endh atan def
 /startang centerv neg centerh neg atan def
 /sweep startang endang sub dup 0 lt{360 add}if def
 sweep arctoobig gt
 {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def
  /midh midang cos midrad mul def /midv midang sin midrad mul def
  midh neg midv neg endh endv centerh centerv midh midv Da
  currentpoint moveto Da}
 {sweep arctoosmall ge
  {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def
  centerv neg controldelt mul centerh controldelt mul
  endv neg controldelt mul centerh add endh add
  endh controldelt mul centerv add endv add
  centerh endh add centerv endv add rcurveto dstroke}
 {centerh endh add centerv endv add rlineto dstroke}ifelse}ifelse}def

/Barray 200 array def % 200 values in a wiggle
/D~{mark}def
/D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop
 /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and
 {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def
  Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put
  Bcontrol Blen 2 sub 2 copy get 2 mul put
  Bcontrol Blen 1 sub 2 copy get 2 mul put
  /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub
  {/i exch def
   Bcontrol i get 3 div Bcontrol i 1 add get 3 div
   Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div
   Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div
   /Xbi Xcont Bcontrol i 2 add get 2 div add def
   /Ybi Ycont Bcontrol i 3 add get 2 div add def
   /Xcont Xcont Bcontrol i 2 add get add def
   /Ycont Ycont Bcontrol i 3 add get add def
   Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto
  }for dstroke}if}def
end
/ditstart{$DITroff begin
 /nfonts 60 def			% NFONTS makedev/ditroff dependent!
 /fonts[nfonts{0}repeat]def
 /fontnames[nfonts{()}repeat]def
/docsave save def
}def

% character outcalls
/oc {/pswid exch def /cc exch def /name exch def
   /ditwid pswid fontsize mul resolution mul 72000 div def
   /ditsiz fontsize resolution mul 72 div def
   ocprocs name known{ocprocs name get exec}{name cb}
   ifelse}def
/fractm [.65 0 0 .6 0 0] def
/fraction
 {/fden exch def /fnum exch def gsave /cf currentfont def
  cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
  fnum show rmoveto currentfont cf setfont(\244)show setfont fden show 
  grestore ditwid 0 rmoveto} def
/oce {grestore ditwid 0 rmoveto}def
/dm {ditsiz mul}def
/ocprocs 50 dict def ocprocs begin
(14){(1)(4)fraction}def
(12){(1)(2)fraction}def
(34){(3)(4)fraction}def
(13){(1)(3)fraction}def
(23){(2)(3)fraction}def
(18){(1)(8)fraction}def
(38){(3)(8)fraction}def
(58){(5)(8)fraction}def
(78){(7)(8)fraction}def
(sr){gsave 0 .06 dm rmoveto(\326)show oce}def
(is){gsave 0 .15 dm rmoveto(\362)show oce}def
(->){gsave 0 .02 dm rmoveto(\256)show oce}def
(<-){gsave 0 .02 dm rmoveto(\254)show oce}def
(==){gsave 0 .05 dm rmoveto(\272)show oce}def
end

% an attempt at a PostScript FONT to implement ditroff special chars
% this will enable us to 
%	cache the little buggers
%	generate faster, more compact PS out of psdit
%	confuse everyone (including myself)!
50 dict dup begin
/FontType 3 def
/FontName /DIThacks def
/FontMatrix [.001 0 0 .001 0 0] def
/FontBBox [-260 -260 900 900] def% a lie but ...
/Encoding 256 array def
0 1 255{Encoding exch /.notdef put}for
Encoding
 dup 8#040/space put %space
 dup 8#110/rc put %right ceil
 dup 8#111/lt put %left  top curl
 dup 8#112/bv put %bold vert
 dup 8#113/lk put %left  mid curl
 dup 8#114/lb put %left  bot curl
 dup 8#115/rt put %right top curl
 dup 8#116/rk put %right mid curl
 dup 8#117/rb put %right bot curl
 dup 8#120/rf put %right floor
 dup 8#121/lf put %left  floor
 dup 8#122/lc put %left  ceil
 dup 8#140/sq put %square
 dup 8#141/bx put %box
 dup 8#142/ci put %circle
 dup 8#143/br put %box rule
 dup 8#144/rn put %root extender
 dup 8#145/vr put %vertical rule
 dup 8#146/ob put %outline bullet
 dup 8#147/bu put %bullet
 dup 8#150/ru put %rule
 dup 8#151/ul put %underline
 pop
/DITfd 100 dict def
/BuildChar{0 begin
 /cc exch def /fd exch def
 /charname fd /Encoding get cc get def
 /charwid fd /Metrics get charname get def
 /charproc fd /CharProcs get charname get def
 charwid 0 fd /FontBBox get aload pop setcachedevice
 2 setlinejoin 40 setlinewidth
 newpath 0 0 moveto gsave charproc grestore
 end}def
/BuildChar load 0 DITfd put
%/UniqueID 5 def
/CharProcs 50 dict def
CharProcs begin
/space{}def
/.notdef{}def
/ru{500 0 rls}def
/rn{0 840 moveto 500 0 rls}def
/vr{0 800 moveto 0 -770 rls}def
/bv{0 800 moveto 0 -1000 rls}def
/br{0 750 moveto 0 -1000 rls}def
/ul{0 -140 moveto 500 0 rls}def
/ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
/bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
/sq{80 0 rmoveto currentpoint dround newpath moveto
    640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
/bx{80 0 rmoveto currentpoint dround newpath moveto
    640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
/ci{500 360 rmoveto currentpoint newpath 333 0 360 arc
    50 setlinewidth stroke}def

/lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
/lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
/rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
/rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
/lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub
    0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
/rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub
    0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
/lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def
/rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
/lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def
/rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
end

/Metrics 50 dict def Metrics begin
/.notdef 0 def
/space 500 def
/ru 500 def
/br 0 def
/lt 416 def
/lb 416 def
/rt 416 def
/rb 416 def
/lk 416 def
/rk 416 def
/rc 416 def
/lc 416 def
/rf 416 def
/lf 416 def
/bv 416 def
/ob 350 def
/bu 350 def
/ci 750 def
/bx 750 def
/sq 750 def
/rn 500 def
/ul 500 def
/vr 0 def
end

DITfd begin
/s2 500 def /s4 250 def /s3 333 def
/a4p{arcto pop pop pop pop}def
/2cx{2 copy exch}def
/rls{rlineto stroke}def
/currx{currentpoint pop}def
/dround{transform round exch round exch itransform} def
end
end
/DIThacks exch definefont pop
ditstart
(psc)xT
576 1 1 xr
1(Times-Roman)xf 1 f
2(Times-Italic)xf 2 f
3(Times-Bold)xf 3 f
4(Times-BoldItalic)xf 4 f
5(Helvetica)xf 5 f
6(Helvetica-Bold)xf 6 f
7(Courier)xf 7 f
8(Courier-Bold)xf 8 f
9(Symbol)xf 9 f
10(DIThacks)xf 10 f
10 s
1 f
xi
%%EndProlog

%%Page: 1 1
10 s 0 xH 0 xS 1 f
8 s
2 f
12 s
1778 672(sdbm)N
3 f
2004(\320)X
2124(Substitute)X
2563(DBM)X
2237 768(or)N
1331 864(Berkeley)N
2 f
1719(ndbm)X
3 f
1956(for)X
2103(Every)X
2373(UN*X)X
1 f
10 s
2628 832(1)N
3 f
12 s
2692 864(Made)N
2951(Simple)X
2 f
10 s
2041 1056(Ozan)N
2230(\(oz\))X
2375(Yigit)X
1 f
1658 1200(The)N
1803(Guild)X
2005(of)X
2092(PD)X
2214(Software)X
2524(Toolmakers)X
2000 1296(Toronto)N
2278(-)X
2325(Canada)X
1965 1488(oz@nexus.yorku.ca)N
2 f
555 1804(Implementation)N
1078(is)X
1151(the)X
1269(sincerest)X
1574(form)X
1745(of)X
1827(\257attery.)X
2094(\320)X
2185(L.)X
2269(Peter)X
2463(Deutsch)X
3 f
555 1996(A)N
633(The)X
786(Clone)X
1006(of)X
1093(the)X
2 f
1220(ndbm)X
3 f
1418(library)X
1 f
755 2120(The)N
903(sources)X
1167(accompanying)X
1658(this)X
1796(notice)X
2015(\320)X
2 f
2118(sdbm)X
1 f
2309(\320)X
2411(constitute)X
2744(the)X
2864(\256rst)X
3010(public)X
3232(release)X
3478(\(Dec.)X
3677(1990\))X
3886(of)X
3975(a)X
555 2216(complete)N
874(clone)X
1073(of)X
1165(the)X
1288(Berkeley)X
1603(UN*X)X
2 f
1842(ndbm)X
1 f
2045(library.)X
2304(The)X
2 f
2454(sdbm)X
1 f
2648(library)X
2887(is)X
2965(meant)X
3186(to)X
3273(clone)X
3472(the)X
3594(proven)X
3841(func-)X
555 2312(tionality)N
846(of)X
2 f
938(ndbm)X
1 f
1141(as)X
1233(closely)X
1485(as)X
1576(possible,)X
1882(including)X
2208(a)X
2268(few)X
2413(improvements.)X
2915(It)X
2988(is)X
3065(practical,)X
3386(easy)X
3553(to)X
3639(understand,)X
555 2408(and)N
691(compatible.)X
1107(The)X
2 f
1252(sdbm)X
1 f
1441(library)X
1675(is)X
1748(not)X
1870(derived)X
2131(from)X
2307(any)X
2443(licensed,)X
2746(proprietary)X
3123(or)X
3210(copyrighted)X
3613(software.)X
755 2532(The)N
2 f
910(sdbm)X
1 f
1109(implementation)X
1641(is)X
1723(based)X
1935(on)X
2044(a)X
2109(1978)X
2298(algorithm)X
2638([Lar78])X
2913(by)X
3022(P.-A.)X
3220(\(Paul\))X
3445(Larson)X
3697(known)X
3944(as)X
555 2628(``Dynamic)N
934(Hashing''.)X
1326(In)X
1424(the)X
1553(course)X
1794(of)X
1892(searching)X
2231(for)X
2355(a)X
2421(substitute)X
2757(for)X
2 f
2881(ndbm)X
1 f
3059(,)X
3109(I)X
3166(prototyped)X
3543(three)X
3734(different)X
555 2724(external-hashing)N
1119(algorithms)X
1490([Lar78,)X
1758(Fag79,)X
2007(Lit80])X
2236(and)X
2381(ultimately)X
2734(chose)X
2946(Larson's)X
3256(algorithm)X
3596(as)X
3692(a)X
3756(basis)X
3944(of)X
555 2820(the)N
2 f
680(sdbm)X
1 f
875(implementation.)X
1423(The)X
1574(Bell)X
1733(Labs)X
2 f
1915(dbm)X
1 f
2079(\(and)X
2248(therefore)X
2 f
2565(ndbm)X
1 f
2743(\))X
2796(is)X
2875(based)X
3084(on)X
3190(an)X
3292(algorithm)X
3629(invented)X
3931(by)X
555 2916(Ken)N
709(Thompson,)X
1091([Tho90,)X
1367(Tor87])X
1610(and)X
1746(predates)X
2034(Larson's)X
2335(work.)X
755 3040(The)N
2 f
903(sdbm)X
1 f
1095(programming)X
1553(interface)X
1857(is)X
1932(totally)X
2158(compatible)X
2536(with)X
2 f
2700(ndbm)X
1 f
2900(and)X
3038(includes)X
3327(a)X
3385(slight)X
3584(improvement)X
555 3136(in)N
641(database)X
942(initialization.)X
1410(It)X
1483(is)X
1560(also)X
1713(expected)X
2023(to)X
2109(be)X
2208(binary-compatible)X
2819(under)X
3025(most)X
3203(UN*X)X
3440(versions)X
3730(that)X
3873(sup-)X
555 3232(port)N
704(the)X
2 f
822(ndbm)X
1 f
1020(library.)X
755 3356(The)N
2 f
909(sdbm)X
1 f
1107(implementation)X
1638(shares)X
1868(the)X
1995(shortcomings)X
2455(of)X
2551(the)X
2 f
2678(ndbm)X
1 f
2885(library,)X
3148(as)X
3244(a)X
3309(side)X
3467(effect)X
3680(of)X
3775(various)X
555 3452(simpli\256cations)N
1046(to)X
1129(the)X
1248(original)X
1518(Larson)X
1762(algorithm.)X
2114(It)X
2183(does)X
2350(produce)X
2 f
2629(holes)X
1 f
2818(in)X
2900(the)X
3018(page)X
3190(\256le)X
3312(as)X
3399(it)X
3463(writes)X
3679(pages)X
3882(past)X
555 3548(the)N
680(end)X
823(of)X
917(\256le.)X
1066(\(Larson's)X
1400(paper)X
1605(include)X
1867(a)X
1929(clever)X
2152(solution)X
2435(to)X
2523(this)X
2664(problem)X
2957(that)X
3103(is)X
3182(a)X
3244(result)X
3448(of)X
3541(using)X
3740(the)X
3864(hash)X
555 3644(value)N
758(directly)X
1032(as)X
1128(a)X
1193(block)X
1400(address.\))X
1717(On)X
1844(the)X
1971(other)X
2165(hand,)X
2370(extensive)X
2702(tests)X
2873(seem)X
3067(to)X
3158(indicate)X
3441(that)X
2 f
3590(sdbm)X
1 f
3787(creates)X
555 3740(fewer)N
762(holes)X
954(in)X
1039(general,)X
1318(and)X
1456(the)X
1576(resulting)X
1878(page\256les)X
2185(are)X
2306(smaller.)X
2584(The)X
2 f
2731(sdbm)X
1 f
2922(implementation)X
3446(is)X
3521(also)X
3672(faster)X
3873(than)X
2 f
555 3836(ndbm)N
1 f
757(in)X
843(database)X
1144(creation.)X
1467(Unlike)X
1709(the)X
2 f
1831(ndbm)X
1 f
2009(,)X
2053(the)X
2 f
2175(sdbm)X
7 f
2396(store)X
1 f
2660(operation)X
2987(will)X
3134(not)X
3259(``wander)X
3573(away'')X
3820(trying)X
555 3932(to)N
642(split)X
804(its)X
904(data)X
1063(pages)X
1271(to)X
1358(insert)X
1561(a)X
1622(datum)X
1847(that)X
2 f
1992(cannot)X
1 f
2235(\(due)X
2403(to)X
2490(elaborate)X
2810(worst-case)X
3179(situations\))X
3537(be)X
3637(inserted.)X
3935(\(It)X
555 4028(will)N
699(fail)X
826(after)X
994(a)X
1050(pre-de\256ned)X
1436(number)X
1701(of)X
1788(attempts.\))X
3 f
555 4220(Important)N
931(Compatibility)X
1426(Warning)X
1 f
755 4344(The)N
2 f
904(sdbm)X
1 f
1097(and)X
2 f
1237(ndbm)X
1 f
1439(libraries)X
2 f
1726(cannot)X
1 f
1968(share)X
2162(databases:)X
2515(one)X
2654(cannot)X
2891(read)X
3053(the)X
3174(\(dir/pag\))X
3478(database)X
3778(created)X
555 4440(by)N
657(the)X
777(other.)X
984(This)X
1148(is)X
1222(due)X
1359(to)X
1442(the)X
1561(differences)X
1940(between)X
2229(the)X
2 f
2348(ndbm)X
1 f
2547(and)X
2 f
2684(sdbm)X
1 f
2874(algorithms)X
8 s
3216 4415(2)N
10 s
4440(,)Y
3289(and)X
3426(the)X
3545(hash)X
3713(functions)X
555 4536(used.)N
769(It)X
845(is)X
925(easy)X
1094(to)X
1182(convert)X
1449(between)X
1743(the)X
2 f
1867(dbm/ndbm)X
1 f
2231(databases)X
2565(and)X
2 f
2707(sdbm)X
1 f
2902(by)X
3008(ignoring)X
3305(the)X
3429(index)X
3633(completely:)X
555 4632(see)N
7 f
706(dbd)X
1 f
(,)S
7 f
918(dbu)X
1 f
1082(etc.)X
3 f
555 4852(Notice)N
794(of)X
881(Intellectual)X
1288(Property)X
2 f
555 4976(The)N
696(entire)X
1 f
904(sdbm)X
2 f
1118(library)X
1361(package,)X
1670(as)X
1762(authored)X
2072(by)X
2169(me,)X
1 f
2304(Ozan)X
2495(S.)X
2580(Yigit,)X
2 f
2785(is)X
2858(hereby)X
3097(placed)X
3331(in)X
3413(the)X
3531(public)X
3751(domain.)X
1 f
555 5072(As)N
670(such,)X
863(the)X
987(author)X
1218(is)X
1297(not)X
1425(responsible)X
1816(for)X
1936(the)X
2060(consequences)X
2528(of)X
2621(use)X
2754(of)X
2847(this)X
2988(software,)X
3310(no)X
3415(matter)X
3645(how)X
3808(awful,)X
555 5168(even)N
727(if)X
796(they)X
954(arise)X
1126(from)X
1302(defects)X
1550(in)X
1632(it.)X
1716(There)X
1924(is)X
1997(no)X
2097(expressed)X
2434(or)X
2521(implied)X
2785(warranty)X
3091(for)X
3205(the)X
2 f
3323(sdbm)X
1 f
3512(library.)X
8 s
10 f
555 5316(hhhhhhhhhhhhhhhhhh)N
6 s
1 f
635 5391(1)N
8 s
691 5410(UN*X)N
877(is)X
936(not)X
1034(a)X
1078(trademark)X
1352(of)X
1421(any)X
1529(\(dis\)organization.)X
6 s
635 5485(2)N
8 s
691 5504(Torek's)N
908(discussion)X
1194([Tor87])X
1411(indicates)X
1657(that)X
2 f
1772(dbm/ndbm)X
1 f
2061(implementations)X
2506(use)X
2609(the)X
2705(hash)X
2840(value)X
2996(to)X
3064(traverse)X
3283(the)X
3379(radix)X
3528(trie)X
3631(dif-)X
555 5584(ferently)N
772(than)X
2 f
901(sdbm)X
1 f
1055(and)X
1166(as)X
1238(a)X
1285(result,)X
1462(the)X
1559(page)X
1698(indexes)X
1912(are)X
2008(generated)X
2274(in)X
2 f
2343(different)X
1 f
2579(order.)X
2764(For)X
2872(more)X
3021(information,)X
3357(send)X
3492(e-mail)X
3673(to)X
555 5664(the)N
649(author.)X

2 p
%%Page: 2 2
8 s 0 xH 0 xS 1 f
10 s
2216 384(-)N
2263(2)X
2323(-)X
755 672(Since)N
971(the)X
2 f
1107(sdbm)X
1 f
1314(library)X
1566(package)X
1868(is)X
1959(in)X
2058(the)X
2193(public)X
2430(domain,)X
2727(this)X
2 f
2879(original)X
1 f
3173(release)X
3434(or)X
3538(any)X
3691(additional)X
555 768(public-domain)N
1045(releases)X
1323(of)X
1413(the)X
1534(modi\256ed)X
1841(original)X
2112(cannot)X
2348(possibly)X
2636(\(by)X
2765(de\256nition\))X
3120(be)X
3218(withheld)X
3520(from)X
3698(you.)X
3860(Also)X
555 864(by)N
659(de\256nition,)X
1009(You)X
1170(\(singular\))X
1505(have)X
1680(all)X
1783(the)X
1904(rights)X
2109(to)X
2194(this)X
2332(code)X
2507(\(including)X
2859(the)X
2980(right)X
3154(to)X
3239(sell)X
3373(without)X
3640(permission,)X
555 960(the)N
679(right)X
856(to)X
944(hoard)X
8 s
1127 935(3)N
10 s
1185 960(and)N
1327(the)X
1451(right)X
1628(to)X
1716(do)X
1821(other)X
2011(icky)X
2174(things)X
2394(as)X
2486(you)X
2631(see)X
2759(\256t\))X
2877(but)X
3004(those)X
3198(rights)X
3405(are)X
3529(also)X
3683(granted)X
3949(to)X
555 1056(everyone)N
870(else.)X
755 1180(Please)N
997(note)X
1172(that)X
1329(all)X
1446(previous)X
1759(distributions)X
2195(of)X
2298(this)X
2449(software)X
2762(contained)X
3110(a)X
3182(copyright)X
3525(\(which)X
3784(is)X
3873(now)X
555 1276(dropped\))N
868(to)X
953(protect)X
1199(its)X
1297(origins)X
1542(and)X
1681(its)X
1779(current)X
2030(public)X
2253(domain)X
2516(status)X
2721(against)X
2970(any)X
3108(possible)X
3392(claims)X
3623(and/or)X
3850(chal-)X
555 1372(lenges.)N
3 f
555 1564(Acknowledgments)N
1 f
755 1688(Many)N
966(people)X
1204(have)X
1380(been)X
1556(very)X
1723(helpful)X
1974(and)X
2114(supportive.)X
2515(A)X
2596(partial)X
2824(list)X
2944(would)X
3167(necessarily)X
3547(include)X
3806(Rayan)X
555 1784(Zacherissen)N
963(\(who)X
1152(contributed)X
1541(the)X
1663(man)X
1824(page,)X
2019(and)X
2158(also)X
2310(hacked)X
2561(a)X
2620(MMAP)X
2887(version)X
3146(of)X
2 f
3236(sdbm)X
1 f
3405(\),)X
3475(Arnold)X
3725(Robbins,)X
555 1880(Chris)N
763(Lewis,)X
1013(Bill)X
1166(Davidsen,)X
1523(Henry)X
1758(Spencer,)X
2071(Geoff)X
2293(Collyer,)X
2587(Rich)X
2772(Salz)X
2944(\(who)X
3143(got)X
3279(me)X
3411(started)X
3659(in)X
3755(the)X
3887(\256rst)X
555 1976(place\),)N
792(Johannes)X
1106(Ruschein)X
1424(\(who)X
1609(did)X
1731(the)X
1849(minix)X
2055(port\))X
2231(and)X
2367(David)X
2583(Tilbrook.)X
2903(I)X
2950(thank)X
3148(you)X
3288(all.)X
3 f
555 2168(Distribution)N
992(Manifest)X
1315(and)X
1463(Notes)X
1 f
555 2292(This)N
717(distribution)X
1105(of)X
2 f
1192(sdbm)X
1 f
1381(includes)X
1668(\(at)X
1773(least\))X
1967(the)X
2085(following:)X
7 f
747 2436(CHANGES)N
1323(change)X
1659(log)X
747 2532(README)N
1323(this)X
1563(file.)X
747 2628(biblio)N
1323(a)X
1419(small)X
1707(bibliography)X
2331(on)X
2475(external)X
2907(hashing)X
747 2724(dba.c)N
1323(a)X
1419(crude)X
1707(\(n/s\)dbm)X
2139(page)X
2379(file)X
2619(analyzer)X
747 2820(dbd.c)N
1323(a)X
1419(crude)X
1707(\(n/s\)dbm)X
2139(page)X
2379(file)X
2619(dumper)X
2955(\(for)X
3195(conversion\))X
747 2916(dbe.1)N
1323(man)X
1515(page)X
1755(for)X
1947(dbe.c)X
747 3012(dbe.c)N
1323(Janick's)X
1755(database)X
2187(editor)X
747 3108(dbm.c)N
1323(a)X
1419(dbm)X
1611(library)X
1995(emulation)X
2475(wrapper)X
2859(for)X
3051(ndbm/sdbm)X
747 3204(dbm.h)N
1323(header)X
1659(file)X
1899(for)X
2091(the)X
2283(above)X
747 3300(dbu.c)N
1323(a)X
1419(crude)X
1707(db)X
1851(management)X
2379(utility)X
747 3396(hash.c)N
1323(hashing)X
1707(function)X
747 3492(makefile)N
1323(guess.)X
747 3588(pair.c)N
1323(page-level)X
1851(routines)X
2283(\(posted)X
2667(earlier\))X
747 3684(pair.h)N
1323(header)X
1659(file)X
1899(for)X
2091(the)X
2283(above)X
747 3780(readme.ms)N
1323(troff)X
1611(source)X
1947(for)X
2139(the)X
2331(README)X
2667(file)X
747 3876(sdbm.3)N
1323(man)X
1515(page)X
747 3972(sdbm.c)N
1323(the)X
1515(real)X
1755(thing)X
747 4068(sdbm.h)N
1323(header)X
1659(file)X
1899(for)X
2091(the)X
2283(above)X
747 4164(tune.h)N
1323(place)X
1611(for)X
1803(tuning)X
2139(&)X
2235(portability)X
2811(thingies)X
747 4260(util.c)N
1323(miscellaneous)X
755 4432(dbu)N
1 f
924(is)X
1002(a)X
1063(simple)X
1301(database)X
1603(manipulation)X
2050(program)X
8 s
2322 4407(4)N
10 s
2379 4432(that)N
2524(tries)X
2687(to)X
2774(look)X
2941(like)X
3086(Bell)X
3244(Labs')X
7 f
3480(cbt)X
1 f
3649(utility.)X
3884(It)X
3958(is)X
555 4528(currently)N
867(incomplete)X
1245(in)X
1329(functionality.)X
1800(I)X
1849(use)X
7 f
2006(dbu)X
1 f
2172(to)X
2255(test)X
2387(out)X
2510(the)X
2629(routines:)X
2930(it)X
2995(takes)X
3181(\(from)X
3385(stdin\))X
3588(tab)X
3707(separated)X
555 4624(key/value)N
898(pairs)X
1085(for)X
1210(commands)X
1587(like)X
7 f
1765(build)X
1 f
2035(or)X
7 f
2160(insert)X
1 f
2478(or)X
2575(takes)X
2770(keys)X
2947(for)X
3071(commands)X
3448(like)X
7 f
3626(delete)X
1 f
3944(or)X
7 f
555 4720(look)N
1 f
(.)S
7 f
747 4864(dbu)N
939(<build|creat|look|insert|cat|delete>)X
2715(dbmfile)X
755 5036(dba)N
1 f
927(is)X
1008(a)X
1072(crude)X
1279(analyzer)X
1580(of)X
2 f
1675(dbm/sdbm/ndbm)X
1 f
2232(page)X
2412(\256les.)X
2593(It)X
2670(scans)X
2872(the)X
2998(entire)X
3209(page)X
3389(\256le,)X
3538(reporting)X
3859(page)X
555 5132(level)N
731(statistics,)X
1046(and)X
1182(totals)X
1375(at)X
1453(the)X
1571(end.)X
7 f
755 5256(dbd)N
1 f
925(is)X
1004(a)X
1066(crude)X
1271(dump)X
1479(program)X
1777(for)X
2 f
1897(dbm/ndbm/sdbm)X
1 f
2452(databases.)X
2806(It)X
2881(ignores)X
3143(the)X
3267(bitmap,)X
3534(and)X
3675(dumps)X
3913(the)X
555 5352(data)N
717(pages)X
928(in)X
1018(sequence.)X
1361(It)X
1437(can)X
1576(be)X
1679(used)X
1853(to)X
1942(create)X
2162(input)X
2353(for)X
2474(the)X
7 f
2627(dbu)X
1 f
2798(utility.)X
3055(Note)X
3238(that)X
7 f
3413(dbd)X
1 f
3584(will)X
3735(skip)X
3895(any)X
8 s
10 f
555 5432(hhhhhhhhhhhhhhhhhh)N
6 s
1 f
635 5507(3)N
8 s
691 5526(You)N
817(cannot)X
1003(really)X
1164(hoard)X
1325(something)X
1608(that)X
1720(is)X
1779(available)X
2025(to)X
2091(the)X
2185(public)X
2361(at)X
2423(large,)X
2582(but)X
2680(try)X
2767(if)X
2822(it)X
2874(makes)X
3053(you)X
3165(feel)X
3276(any)X
3384(better.)X
6 s
635 5601(4)N
8 s
691 5620(The)N
7 f
829(dbd)X
1 f
943(,)X
7 f
998(dba)X
1 f
1112(,)X
7 f
1167(dbu)X
1 f
1298(utilities)X
1508(are)X
1602(quick)X
1761(hacks)X
1923(and)X
2032(are)X
2126(not)X
2225(\256t)X
2295(for)X
2385(production)X
2678(use.)X
2795(They)X
2942(were)X
3081(developed)X
3359(late)X
3467(one)X
3575(night,)X
555 5700(just)N
664(to)X
730(test)X
835(out)X
2 f
933(sdbm)X
1 f
1068(,)X
1100(and)X
1208(convert)X
1415(some)X
1566(databases.)X

3 p
%%Page: 3 3
8 s 0 xH 0 xS 1 f
10 s
2216 384(-)N
2263(3)X
2323(-)X
555 672(NULLs)N
821(in)X
903(the)X
1021(key)X
1157(and)X
1293(data)X
1447(\256elds,)X
1660(thus)X
1813(is)X
1886(unsuitable)X
2235(to)X
2317(convert)X
2578(some)X
2767(peculiar)X
3046(databases)X
3374(that)X
3514(insist)X
3702(in)X
3784(includ-)X
555 768(ing)N
677(the)X
795(terminating)X
1184(null.)X
755 892(I)N
841(have)X
1052(also)X
1240(included)X
1575(a)X
1670(copy)X
1885(of)X
2011(the)X
7 f
2195(dbe)X
1 f
2397(\()X
2 f
2424(ndbm)X
1 f
2660(DataBase)X
3026(Editor\))X
3311(by)X
3449(Janick)X
3712(Bergeron)X
555 988([janick@bnr.ca])N
1098(for)X
1212(your)X
1379(pleasure.)X
1687(You)X
1845(may)X
2003(\256nd)X
2147(it)X
2211(more)X
2396(useful)X
2612(than)X
2770(the)X
2888(little)X
7 f
3082(dbu)X
1 f
3246(utility.)X
7 f
755 1112(dbm.[ch])N
1 f
1169(is)X
1252(a)X
2 f
1318(dbm)X
1 f
1486(library)X
1730(emulation)X
2079(on)X
2188(top)X
2319(of)X
2 f
2415(ndbm)X
1 f
2622(\(and)X
2794(hence)X
3011(suitable)X
3289(for)X
2 f
3412(sdbm)X
1 f
3581(\).)X
3657(Written)X
3931(by)X
555 1208(Robert)N
793(Elz.)X
755 1332(The)N
2 f
901(sdbm)X
1 f
1090(library)X
1324(has)X
1451(been)X
1623(around)X
1866(in)X
1948(beta)X
2102(test)X
2233(for)X
2347(quite)X
2527(a)X
2583(long)X
2745(time,)X
2927(and)X
3063(from)X
3239(whatever)X
3554(little)X
3720(feedback)X
555 1428(I)N
609(received)X
909(\(maybe)X
1177(no)X
1284(news)X
1476(is)X
1555(good)X
1741(news\),)X
1979(I)X
2032(believe)X
2290(it)X
2360(has)X
2493(been)X
2671(functioning)X
3066(without)X
3336(any)X
3478(signi\256cant)X
3837(prob-)X
555 1524(lems.)N
752(I)X
805(would,)X
1051(of)X
1144(course,)X
1400(appreciate)X
1757(all)X
1863(\256xes)X
2040(and/or)X
2271(improvements.)X
2774(Portability)X
3136(enhancements)X
3616(would)X
3841(espe-)X
555 1620(cially)N
753(be)X
849(useful.)X
3 f
555 1812(Implementation)N
1122(Issues)X
1 f
755 1936(Hash)N
944(functions:)X
1288(The)X
1437(algorithm)X
1772(behind)X
2 f
2014(sdbm)X
1 f
2207(implementation)X
2733(needs)X
2939(a)X
2998(good)X
3181(bit-scrambling)X
3671(hash)X
3841(func-)X
555 2032(tion)N
702(to)X
787(be)X
886(effective.)X
1211(I)X
1261(ran)X
1387(into)X
1534(a)X
1593(set)X
1705(of)X
1795(constants)X
2116(for)X
2233(a)X
2292(simple)X
2528(hash)X
2698(function)X
2988(that)X
3130(seem)X
3317(to)X
3401(help)X
2 f
3561(sdbm)X
1 f
3752(perform)X
555 2128(better)N
758(than)X
2 f
916(ndbm)X
1 f
1114(for)X
1228(various)X
1484(inputs:)X
7 f
747 2272(/*)N
795 2368(*)N
891(polynomial)X
1419(conversion)X
1947(ignoring)X
2379(overflows)X
795 2464(*)N
891(65599)X
1179(nice.)X
1467(65587)X
1755(even)X
1995(better.)X
795 2560(*/)N
747 2656(long)N
747 2752(dbm_hash\(char)N
1419(*str,)X
1707(int)X
1899(len\))X
2139({)X
939 2848(register)N
1371(unsigned)X
1803(long)X
2043(n)X
2139(=)X
2235(0;)X
939 3040(while)N
1227(\(len--\))X
1131 3136(n)N
1227(=)X
1323(n)X
1419(*)X
1515(65599)X
1803(+)X
1899(*str++;)X
939 3232(return)N
1275(n;)X
747 3328(})N
1 f
755 3500(There)N
975(may)X
1145(be)X
1253(better)X
1467(hash)X
1645(functions)X
1974(for)X
2099(the)X
2228(purposes)X
2544(of)X
2642(dynamic)X
2949(hashing.)X
3269(Try)X
3416(your)X
3594(favorite,)X
3895(and)X
555 3596(check)N
766(the)X
887(page\256le.)X
1184(If)X
1261(it)X
1328(contains)X
1618(too)X
1743(many)X
1944(pages)X
2150(with)X
2315(too)X
2440(many)X
2641(holes,)X
2853(\(in)X
2965(relation)X
3233(to)X
3318(this)X
3456(one)X
3595(for)X
3712(example\))X
555 3692(or)N
656(if)X
2 f
739(sdbm)X
1 f
942(simply)X
1193(stops)X
1391(working)X
1692(\(fails)X
1891(after)X
7 f
2101(SPLTMAX)X
1 f
2471(attempts)X
2776(to)X
2872(split\))X
3070(when)X
3278(you)X
3432(feed)X
3604(your)X
3784(NEWS)X
7 f
555 3788(history)N
1 f
912(\256le)X
1035(to)X
1118(it,)X
1203(you)X
1344(probably)X
1650(do)X
1751(not)X
1874(have)X
2047(a)X
2104(good)X
2285(hashing)X
2555(function.)X
2883(If)X
2958(you)X
3099(do)X
3200(better)X
3404(\(for)X
3545(different)X
3842(types)X
555 3884(of)N
642(input\),)X
873(I)X
920(would)X
1140(like)X
1280(to)X
1362(know)X
1560(about)X
1758(the)X
1876(function)X
2163(you)X
2303(use.)X
755 4008(Block)N
967(sizes:)X
1166(It)X
1236(seems)X
1453(\(from)X
1657(various)X
1914(tests)X
2077(on)X
2178(a)X
2235(few)X
2377(machines\))X
2727(that)X
2867(a)X
2923(page)X
3095(\256le)X
3217(block)X
3415(size)X
7 f
3588(PBLKSIZ)X
1 f
3944(of)X
555 4104(1024)N
738(is)X
814(by)X
917(far)X
1030(the)X
1150(best)X
1301(for)X
1417(performance,)X
1866(but)X
1990(this)X
2127(also)X
2278(happens)X
2563(to)X
2647(limit)X
2819(the)X
2939(size)X
3086(of)X
3175(a)X
3233(key/value)X
3567(pair.)X
3734(Depend-)X
555 4200(ing)N
681(on)X
785(your)X
956(needs,)X
1183(you)X
1327(may)X
1489(wish)X
1663(to)X
1748(increase)X
2035(the)X
2156(page)X
2331(size,)X
2499(and)X
2638(also)X
2790(adjust)X
7 f
3032(PAIRMAX)X
1 f
3391(\(the)X
3539(maximum)X
3886(size)X
555 4296(of)N
648(a)X
710(key/value)X
1048(pair)X
1199(allowed:)X
1501(should)X
1740(always)X
1989(be)X
2090(at)X
2173(least)X
2345(three)X
2531(words)X
2752(smaller)X
3013(than)X
7 f
3204(PBLKSIZ)X
1 f
(.\))S
3612(accordingly.)X
555 4392(The)N
706(system-wide)X
1137(version)X
1399(of)X
1492(the)X
1616(library)X
1856(should)X
2095(probably)X
2406(be)X
2508(con\256gured)X
2877(with)X
3044(1024)X
3229(\(distribution)X
3649(default\),)X
3944(as)X
555 4488(this)N
690(appears)X
956(to)X
1038(be)X
1134(suf\256cient)X
1452(for)X
1566(most)X
1741(common)X
2041(uses)X
2199(of)X
2 f
2286(sdbm)X
1 f
2455(.)X
3 f
555 4680(Portability)N
1 f
755 4804(This)N
917(package)X
1201(has)X
1328(been)X
1500(tested)X
1707(in)X
1789(many)X
1987(different)X
2284(UN*Xes)X
2585(even)X
2757(including)X
3079(minix,)X
3305(and)X
3441(appears)X
3707(to)X
3789(be)X
3885(rea-)X
555 4900(sonably)N
824(portable.)X
1127(This)X
1289(does)X
1456(not)X
1578(mean)X
1772(it)X
1836(will)X
1980(port)X
2129(easily)X
2336(to)X
2418(non-UN*X)X
2799(systems.)X
3 f
555 5092(Notes)N
767(and)X
915(Miscellaneous)X
1 f
755 5216(The)N
2 f
913(sdbm)X
1 f
1115(is)X
1201(not)X
1336(a)X
1405(very)X
1581(complicated)X
2006(package,)X
2323(at)X
2414(least)X
2594(not)X
2729(after)X
2910(you)X
3063(familiarize)X
3444(yourself)X
3739(with)X
3913(the)X
555 5312(literature)N
879(on)X
993(external)X
1286(hashing.)X
1589(There)X
1811(are)X
1944(other)X
2143(interesting)X
2514(algorithms)X
2889(in)X
2984(existence)X
3316(that)X
3469(ensure)X
3712(\(approxi-)X
555 5408(mately\))N
825(single-read)X
1207(access)X
1438(to)X
1525(a)X
1586(data)X
1745(value)X
1944(associated)X
2299(with)X
2466(any)X
2607(key.)X
2768(These)X
2984(are)X
3107(directory-less)X
3568(schemes)X
3864(such)X
555 5504(as)N
2 f
644(linear)X
857(hashing)X
1 f
1132([Lit80])X
1381(\(+)X
1475(Larson)X
1720(variations\),)X
2 f
2105(spiral)X
2313(storage)X
1 f
2575([Mar79])X
2865(or)X
2954(directory)X
3265(schemes)X
3558(such)X
3726(as)X
2 f
3814(exten-)X
555 5600(sible)N
731(hashing)X
1 f
1009([Fag79])X
1288(by)X
1393(Fagin)X
1600(et)X
1683(al.)X
1786(I)X
1838(do)X
1943(hope)X
2124(these)X
2314(sources)X
2579(provide)X
2848(a)X
2908(reasonable)X
3276(playground)X
3665(for)X
3783(experi-)X
555 5696(mentation)N
907(with)X
1081(other)X
1277(algorithms.)X
1690(See)X
1837(the)X
1966(June)X
2144(1988)X
2335(issue)X
2526(of)X
2624(ACM)X
2837(Computing)X
3227(Surveys)X
3516([Enb88])X
3810(for)X
3935(an)X
555 5792(excellent)N
865(overview)X
1184(of)X
1271(the)X
1389(\256eld.)X

4 p
%%Page: 4 4
10 s 0 xH 0 xS 1 f
2216 384(-)N
2263(4)X
2323(-)X
3 f
555 672(References)N
1 f
555 824([Lar78])N
875(P.-A.)X
1064(Larson,)X
1327(``Dynamic)X
1695(Hashing'',)X
2 f
2056(BIT)X
1 f
(,)S
2216(vol.)X
2378(18,)X
2518(pp.)X
2638(184-201,)X
2945(1978.)X
555 948([Tho90])N
875(Ken)X
1029(Thompson,)X
2 f
1411(private)X
1658(communication)X
1 f
2152(,)X
2192(Nov.)X
2370(1990)X
555 1072([Lit80])N
875(W.)X
992(Litwin,)X
1246(``)X
1321(Linear)X
1552(Hashing:)X
1862(A)X
1941(new)X
2096(tool)X
2261(for)X
2396(\256le)X
2539(and)X
2675(table)X
2851(addressing'',)X
2 f
3288(Proceedings)X
3709(of)X
3791(the)X
3909(6th)X
875 1168(Conference)N
1269(on)X
1373(Very)X
1548(Large)X
1782(Dabatases)X
2163(\(Montreal\))X
1 f
2515(,)X
2558(pp.)X
2701(212-223,)X
3031(Very)X
3215(Large)X
3426(Database)X
3744(Founda-)X
875 1264(tion,)N
1039(Saratoga,)X
1360(Calif.,)X
1580(1980.)X
555 1388([Fag79])N
875(R.)X
969(Fagin,)X
1192(J.)X
1284(Nievergelt,)X
1684(N.)X
1803(Pippinger,)X
2175(and)X
2332(H.)X
2451(R.)X
2544(Strong,)X
2797(``Extendible)X
3218(Hashing)X
3505(-)X
3552(A)X
3630(Fast)X
3783(Access)X
875 1484(Method)N
1144(for)X
1258(Dynamic)X
1572(Files'',)X
2 f
1821(ACM)X
2010(Trans.)X
2236(Database)X
2563(Syst.)X
1 f
2712(,)X
2752(vol.)X
2894(4,)X
2994(no.3,)X
3174(pp.)X
3294(315-344,)X
3601(Sept.)X
3783(1979.)X
555 1608([Wal84])N
875(Rich)X
1055(Wales,)X
1305(``Discussion)X
1739(of)X
1835("dbm")X
2072(data)X
2235(base)X
2406(system'',)X
2 f
2730(USENET)X
3051(newsgroup)X
3430(unix.wizards)X
1 f
3836(,)X
3884(Jan.)X
875 1704(1984.)N
555 1828([Tor87])N
875(Chris)X
1068(Torek,)X
1300(``Re:)X
1505(dbm.a)X
1743(and)X
1899(ndbm.a)X
2177(archives'',)X
2 f
2539(USENET)X
2852(newsgroup)X
3223(comp.unix)X
1 f
3555(,)X
3595(1987.)X
555 1952([Mar79])N
875(G.)X
974(N.)X
1073(Martin,)X
1332(``Spiral)X
1598(Storage:)X
1885(Incrementally)X
2371(Augmentable)X
2843(Hash)X
3048(Addressed)X
3427(Storage'',)X
2 f
3766(Techni-)X
875 2048(cal)N
993(Report)X
1231(#27)X
1 f
(,)S
1391(University)X
1749(of)X
1836(Varwick,)X
2153(Coventry,)X
2491(U.K.,)X
2687(1979.)X
555 2172([Enb88])N
875(R.)X
977(J.)X
1057(Enbody)X
1335(and)X
1480(H.)X
1586(C.)X
1687(Du,)X
1833(``Dynamic)X
2209(Hashing)X
2524(Schemes'',)X
2 f
2883(ACM)X
3080(Computing)X
3463(Surveys)X
1 f
3713(,)X
3761(vol.)X
3911(20,)X
875 2268(no.)N
995(2,)X
1075(pp.)X
1195(85-113,)X
1462(June)X
1629(1988.)X

4 p
%%Trailer
xt

xs