diff options
Diffstat (limited to 'ext/SDBM_File/sdbm/readme.ps')
| -rw-r--r-- | ext/SDBM_File/sdbm/readme.ps | 2225 |
1 files changed, 2225 insertions, 0 deletions
diff --git a/ext/SDBM_File/sdbm/readme.ps b/ext/SDBM_File/sdbm/readme.ps new file mode 100644 index 0000000000..2b0c675595 --- /dev/null +++ b/ext/SDBM_File/sdbm/readme.ps @@ -0,0 +1,2225 @@ +%!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 |