ext/SDBM_File/sdbm/readme.ps

   1 %!PS-Adobe-1.0
   2 %%Creator: yetti:oz (Ozan Yigit)
   3 %%Title: stdin (ditroff)
   4 %%CreationDate: Thu Dec 13 15:56:08 1990
   5 %%EndComments
   6 % lib/psdit.pro -- prolog for psdit (ditroff) files
   7 % Copyright (c) 1984, 1985 Adobe Systems Incorporated. All Rights Reserved.
   8 % last edit: shore Sat Nov 23 20:28:03 1985
   9 % RCSID: $Header: psdit.pro,v 2.1 85/11/24 12:19:43 shore Rel $
  10
  11 /$DITroff 140 dict def $DITroff begin
  12 /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def
  13 /xi {0 72 11 mul translate 72 resolution div dup neg scale 0 0 moveto
  14   /fontnum 1 def /fontsize 10 def /fontheight 10 def /fontslant 0 def F
  15   /pagesave save def}def
  16 /PB{save /psv exch def currentpoint translate
  17   resolution 72 div dup neg scale 0 0 moveto}def
  18 /PE{psv restore}def
  19 /arctoobig 90 def /arctoosmall .05 def
  20 /m1 matrix def /m2 matrix def /m3 matrix def /oldmat matrix def
  21 /tan{dup sin exch cos div}def
  22 /point{resolution 72 div mul}def
  23 /dround {transform round exch round exch itransform}def
  24 /xT{/devname exch def}def
  25 /xr{/mh exch def /my exch def /resolution exch def}def
  26 /xp{}def
  27 /xs{docsave restore end}def
  28 /xt{}def
  29 /xf{/fontname exch def /slotno exch def fontnames slotno get fontname eq not
  30  {fonts slotno fontname findfont put fontnames slotno fontname put}if}def
  31 /xH{/fontheight exch def F}def
  32 /xS{/fontslant exch def F}def
  33 /s{/fontsize exch def /fontheight fontsize def F}def
  34 /f{/fontnum exch def F}def
  35 /F{fontheight 0 le {/fontheight fontsize def}if
  36    fonts fontnum get fontsize point 0 0 fontheight point neg 0 0 m1 astore
  37    fontslant 0 ne{1 0 fontslant tan 1 0 0 m2 astore m3 concatmatrix}if
  38    makefont setfont .04 fontsize point mul 0 dround pop setlinewidth}def
  39 /X{exch currentpoint exch pop moveto show}def
  40 /N{3 1 roll moveto show}def
  41 /Y{exch currentpoint pop exch moveto show}def
  42 /S{show}def
  43 /ditpush{}def/ditpop{}def
  44 /AX{3 -1 roll currentpoint exch pop moveto 0 exch ashow}def
  45 /AN{4 2 roll moveto 0 exch ashow}def
  46 /AY{3 -1 roll currentpoint pop exch moveto 0 exch ashow}def
  47 /AS{0 exch ashow}def
  48 /MX{currentpoint exch pop moveto}def
  49 /MY{currentpoint pop exch moveto}def
  50 /MXY{moveto}def
  51 /cb{pop}def     % action on unknown char -- nothing for now
  52 /n{}def/w{}def
  53 /p{pop showpage pagesave restore /pagesave save def}def
  54 /abspoint{currentpoint exch pop add exch currentpoint pop add exch}def
  55 /distance{dup mul exch dup mul add sqrt}def
  56 /dstroke{currentpoint stroke moveto}def
  57 /Dl{2 copy gsave rlineto stroke grestore rmoveto}def
  58 /arcellipse{/diamv exch def /diamh exch def oldmat currentmatrix pop
  59  currentpoint translate 1 diamv diamh div scale /rad diamh 2 div def
  60  currentpoint exch rad add exch rad -180 180 arc oldmat setmatrix}def
  61 /Dc{dup arcellipse dstroke}def
  62 /De{arcellipse dstroke}def
  63 /Da{/endv exch def /endh exch def /centerv exch def /centerh exch def
  64  /cradius centerv centerv mul centerh centerh mul add sqrt def
  65  /eradius endv endv mul endh endh mul add sqrt def
  66  /endang endv endh atan def
  67  /startang centerv neg centerh neg atan def
  68  /sweep startang endang sub dup 0 lt{360 add}if def
  69  sweep arctoobig gt
  70  {/midang startang sweep 2 div sub def /midrad cradius eradius add 2 div def
  71   /midh midang cos midrad mul def /midv midang sin midrad mul def
  72   midh neg midv neg endh endv centerh centerv midh midv Da
  73   currentpoint moveto Da}
  74  {sweep arctoosmall ge
  75   {/controldelt 1 sweep 2 div cos sub 3 sweep 2 div sin mul div 4 mul def
  76   centerv neg controldelt mul centerh controldelt mul
  77   endv neg controldelt mul centerh add endh add
  78   endh controldelt mul centerv add endv add
  79   centerh endh add centerv endv add rcurveto dstroke}
  80  {centerh endh add centerv endv add rlineto dstroke}ifelse}ifelse}def
  81
  82 /Barray 200 array def % 200 values in a wiggle
  83 /D~{mark}def
  84 /D~~{counttomark Barray exch 0 exch getinterval astore /Bcontrol exch def pop
  85  /Blen Bcontrol length def Blen 4 ge Blen 2 mod 0 eq and
  86  {Bcontrol 0 get Bcontrol 1 get abspoint /Ycont exch def /Xcont exch def
  87   Bcontrol 0 2 copy get 2 mul put Bcontrol 1 2 copy get 2 mul put
  88   Bcontrol Blen 2 sub 2 copy get 2 mul put
  89   Bcontrol Blen 1 sub 2 copy get 2 mul put
  90   /Ybi /Xbi currentpoint 3 1 roll def def 0 2 Blen 4 sub
  91   {/i exch def
  92    Bcontrol i get 3 div Bcontrol i 1 add get 3 div
  93    Bcontrol i get 3 mul Bcontrol i 2 add get add 6 div
  94    Bcontrol i 1 add get 3 mul Bcontrol i 3 add get add 6 div
  95    /Xbi Xcont Bcontrol i 2 add get 2 div add def
  96    /Ybi Ycont Bcontrol i 3 add get 2 div add def
  97    /Xcont Xcont Bcontrol i 2 add get add def
  98    /Ycont Ycont Bcontrol i 3 add get add def
  99    Xbi currentpoint pop sub Ybi currentpoint exch pop sub rcurveto
 100   }for dstroke}if}def
 101 end
 102 /ditstart{$DITroff begin
 103  /nfonts 60 def                 % NFONTS makedev/ditroff dependent!
 104  /fonts[nfonts{0}repeat]def
 105  /fontnames[nfonts{()}repeat]def
 106 /docsave save def
 107 }def
 108
 109 % character outcalls
 110 /oc {/pswid exch def /cc exch def /name exch def
 111    /ditwid pswid fontsize mul resolution mul 72000 div def
 112    /ditsiz fontsize resolution mul 72 div def
 113    ocprocs name known{ocprocs name get exec}{name cb}
 114    ifelse}def
 115 /fractm [.65 0 0 .6 0 0] def
 116 /fraction
 117  {/fden exch def /fnum exch def gsave /cf currentfont def
 118   cf fractm makefont setfont 0 .3 dm 2 copy neg rmoveto
 119   fnum show rmoveto currentfont cf setfont(\244)show setfont fden show
 120   grestore ditwid 0 rmoveto} def
 121 /oce {grestore ditwid 0 rmoveto}def
 122 /dm {ditsiz mul}def
 123 /ocprocs 50 dict def ocprocs begin
 124 (14){(1)(4)fraction}def
 125 (12){(1)(2)fraction}def
 126 (34){(3)(4)fraction}def
 127 (13){(1)(3)fraction}def
 128 (23){(2)(3)fraction}def
 129 (18){(1)(8)fraction}def
 130 (38){(3)(8)fraction}def
 131 (58){(5)(8)fraction}def
 132 (78){(7)(8)fraction}def
 133 (sr){gsave 0 .06 dm rmoveto(\326)show oce}def
 134 (is){gsave 0 .15 dm rmoveto(\362)show oce}def
 135 (->){gsave 0 .02 dm rmoveto(\256)show oce}def
 136 (<-){gsave 0 .02 dm rmoveto(\254)show oce}def
 137 (==){gsave 0 .05 dm rmoveto(\272)show oce}def
 138 end
 139
 140 % an attempt at a PostScript FONT to implement ditroff special chars
 141 % this will enable us to
 142 %       cache the little buggers
 143 %       generate faster, more compact PS out of psdit
 144 %       confuse everyone (including myself)!
 145 50 dict dup begin
 146 /FontType 3 def
 147 /FontName /DIThacks def
 148 /FontMatrix [.001 0 0 .001 0 0] def
 149 /FontBBox [-260 -260 900 900] def% a lie but ...
 150 /Encoding 256 array def
 151 0 1 255{Encoding exch /.notdef put}for
 152 Encoding
 153  dup 8#040/space put %space
 154  dup 8#110/rc put %right ceil
 155  dup 8#111/lt put %left  top curl
 156  dup 8#112/bv put %bold vert
 157  dup 8#113/lk put %left  mid curl
 158  dup 8#114/lb put %left  bot curl
 159  dup 8#115/rt put %right top curl
 160  dup 8#116/rk put %right mid curl
 161  dup 8#117/rb put %right bot curl
 162  dup 8#120/rf put %right floor
 163  dup 8#121/lf put %left  floor
 164  dup 8#122/lc put %left  ceil
 165  dup 8#140/sq put %square
 166  dup 8#141/bx put %box
 167  dup 8#142/ci put %circle
 168  dup 8#143/br put %box rule
 169  dup 8#144/rn put %root extender
 170  dup 8#145/vr put %vertical rule
 171  dup 8#146/ob put %outline bullet
 172  dup 8#147/bu put %bullet
 173  dup 8#150/ru put %rule
 174  dup 8#151/ul put %underline
 175  pop
 176 /DITfd 100 dict def
 177 /BuildChar{0 begin
 178  /cc exch def /fd exch def
 179  /charname fd /Encoding get cc get def
 180  /charwid fd /Metrics get charname get def
 181  /charproc fd /CharProcs get charname get def
 182  charwid 0 fd /FontBBox get aload pop setcachedevice
 183  2 setlinejoin 40 setlinewidth
 184  newpath 0 0 moveto gsave charproc grestore
 185  end}def
 186 /BuildChar load 0 DITfd put
 187 %/UniqueID 5 def
 188 /CharProcs 50 dict def
 189 CharProcs begin
 190 /space{}def
 191 /.notdef{}def
 192 /ru{500 0 rls}def
 193 /rn{0 840 moveto 500 0 rls}def
 194 /vr{0 800 moveto 0 -770 rls}def
 195 /bv{0 800 moveto 0 -1000 rls}def
 196 /br{0 750 moveto 0 -1000 rls}def
 197 /ul{0 -140 moveto 500 0 rls}def
 198 /ob{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath stroke}def
 199 /bu{200 250 rmoveto currentpoint newpath 200 0 360 arc closepath fill}def
 200 /sq{80 0 rmoveto currentpoint dround newpath moveto
 201     640 0 rlineto 0 640 rlineto -640 0 rlineto closepath stroke}def
 202 /bx{80 0 rmoveto currentpoint dround newpath moveto
 203     640 0 rlineto 0 640 rlineto -640 0 rlineto closepath fill}def
 204 /ci{500 360 rmoveto currentpoint newpath 333 0 360 arc
 205     50 setlinewidth stroke}def
 206
 207 /lt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 add exch s4 a4p stroke}def
 208 /lb{0 800 moveto 0 -550 rlineto currx -200 2cx s4 add exch s4 a4p stroke}def
 209 /rt{0 -200 moveto 0 550 rlineto currx 800 2cx s4 sub exch s4 a4p stroke}def
 210 /rb{0 800 moveto 0 -500 rlineto currx -200 2cx s4 sub exch s4 a4p stroke}def
 211 /lk{0 800 moveto 0 300 -300 300 s4 arcto pop pop 1000 sub
 212     0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
 213 /rk{0 800 moveto 0 300 s2 300 s4 arcto pop pop 1000 sub
 214     0 300 4 2 roll s4 a4p 0 -200 lineto stroke}def
 215 /lf{0 800 moveto 0 -1000 rlineto s4 0 rls}def
 216 /rf{0 800 moveto 0 -1000 rlineto s4 neg 0 rls}def
 217 /lc{0 -200 moveto 0 1000 rlineto s4 0 rls}def
 218 /rc{0 -200 moveto 0 1000 rlineto s4 neg 0 rls}def
 219 end
 220
 221 /Metrics 50 dict def Metrics begin
 222 /.notdef 0 def
 223 /space 500 def
 224 /ru 500 def
 225 /br 0 def
 226 /lt 416 def
 227 /lb 416 def
 228 /rt 416 def
 229 /rb 416 def
 230 /lk 416 def
 231 /rk 416 def
 232 /rc 416 def
 233 /lc 416 def
 234 /rf 416 def
 235 /lf 416 def
 236 /bv 416 def
 237 /ob 350 def
 238 /bu 350 def
 239 /ci 750 def
 240 /bx 750 def
 241 /sq 750 def
 242 /rn 500 def
 243 /ul 500 def
 244 /vr 0 def
 245 end
 246
 247 DITfd begin
 248 /s2 500 def /s4 250 def /s3 333 def
 249 /a4p{arcto pop pop pop pop}def
 250 /2cx{2 copy exch}def
 251 /rls{rlineto stroke}def
 252 /currx{currentpoint pop}def
 253 /dround{transform round exch round exch itransform} def
 254 end
 255 end
 256 /DIThacks exch definefont pop
 257 ditstart
 258 (psc)xT
 259 576 1 1 xr
 260 1(Times-Roman)xf 1 f
 261 2(Times-Italic)xf 2 f
 262 3(Times-Bold)xf 3 f
 263 4(Times-BoldItalic)xf 4 f
 264 5(Helvetica)xf 5 f
 265 6(Helvetica-Bold)xf 6 f
 266 7(Courier)xf 7 f
 267 8(Courier-Bold)xf 8 f
 268 9(Symbol)xf 9 f
 269 10(DIThacks)xf 10 f
 270 10 s
 271 1 f
 272 xi
 273 %%EndProlog
 274
 275 %%Page: 1 1
 276 10 s 0 xH 0 xS 1 f
 277 8 s
 278 2 f
 279 12 s
 280 1778 672(sdbm)N
 281 3 f
 282 2004(\320)X
 283 2124(Substitute)X
 284 2563(DBM)X
 285 2237 768(or)N
 286 1331 864(Berkeley)N
 287 2 f
 288 1719(ndbm)X
 289 3 f
 290 1956(for)X
 291 2103(Every)X
 292 2373(UN*X)X
 293 1 f
 294 10 s
 295 2628 832(1)N
 296 3 f
 297 12 s
 298 2692 864(Made)N
 299 2951(Simple)X
 300 2 f
 301 10 s
 302 2041 1056(Ozan)N
 303 2230(\(oz\))X
 304 2375(Yigit)X
 305 1 f
 306 1658 1200(The)N
 307 1803(Guild)X
 308 2005(of)X
 309 2092(PD)X
 310 2214(Software)X
 311 2524(Toolmakers)X
 312 2000 1296(Toronto)N
 313 2278(-)X
 314 2325(Canada)X
 315 1965 1488(oz@nexus.yorku.ca)N
 316 2 f
 317 555 1804(Implementation)N
 318 1078(is)X
 319 1151(the)X
 320 1269(sincerest)X
 321 1574(form)X
 322 1745(of)X
 323 1827(\257attery.)X
 324 2094(\320)X
 325 2185(L.)X
 326 2269(Peter)X
 327 2463(Deutsch)X
 328 3 f
 329 555 1996(A)N
 330 633(The)X
 331 786(Clone)X
 332 1006(of)X
 333 1093(the)X
 334 2 f
 335 1220(ndbm)X
 336 3 f
 337 1418(library)X
 338 1 f
 339 755 2120(The)N
 340 903(sources)X
 341 1167(accompanying)X
 342 1658(this)X
 343 1796(notice)X
 344 2015(\320)X
 345 2 f
 346 2118(sdbm)X
 347 1 f
 348 2309(\320)X
 349 2411(constitute)X
 350 2744(the)X
 351 2864(\256rst)X
 352 3010(public)X
 353 3232(release)X
 354 3478(\(Dec.)X
 355 3677(1990\))X
 356 3886(of)X
 357 3975(a)X
 358 555 2216(complete)N
 359 874(clone)X
 360 1073(of)X
 361 1165(the)X
 362 1288(Berkeley)X
 363 1603(UN*X)X
 364 2 f
 365 1842(ndbm)X
 366 1 f
 367 2045(library.)X
 368 2304(The)X
 369 2 f
 370 2454(sdbm)X
 371 1 f
 372 2648(library)X
 373 2887(is)X
 374 2965(meant)X
 375 3186(to)X
 376 3273(clone)X
 377 3472(the)X
 378 3594(proven)X
 379 3841(func-)X
 380 555 2312(tionality)N
 381 846(of)X
 382 2 f
 383 938(ndbm)X
 384 1 f
 385 1141(as)X
 386 1233(closely)X
 387 1485(as)X
 388 1576(possible,)X
 389 1882(including)X
 390 2208(a)X
 391 2268(few)X
 392 2413(improvements.)X
 393 2915(It)X
 394 2988(is)X
 395 3065(practical,)X
 396 3386(easy)X
 397 3553(to)X
 398 3639(understand,)X
 399 555 2408(and)N
 400 691(compatible.)X
 401 1107(The)X
 402 2 f
 403 1252(sdbm)X
 404 1 f
 405 1441(library)X
 406 1675(is)X
 407 1748(not)X
 408 1870(derived)X
 409 2131(from)X
 410 2307(any)X
 411 2443(licensed,)X
 412 2746(proprietary)X
 413 3123(or)X
 414 3210(copyrighted)X
 415 3613(software.)X
 416 755 2532(The)N
 417 2 f
 418 910(sdbm)X
 419 1 f
 420 1109(implementation)X
 421 1641(is)X
 422 1723(based)X
 423 1935(on)X
 424 2044(a)X
 425 2109(1978)X
 426 2298(algorithm)X
 427 2638([Lar78])X
 428 2913(by)X
 429 3022(P.-A.)X
 430 3220(\(Paul\))X
 431 3445(Larson)X
 432 3697(known)X
 433 3944(as)X
 434 555 2628(``Dynamic)N
 435 934(Hashing''.)X
 436 1326(In)X
 437 1424(the)X
 438 1553(course)X
 439 1794(of)X
 440 1892(searching)X
 441 2231(for)X
 442 2355(a)X
 443 2421(substitute)X
 444 2757(for)X
 445 2 f
 446 2881(ndbm)X
 447 1 f
 448 3059(,)X
 449 3109(I)X
 450 3166(prototyped)X
 451 3543(three)X
 452 3734(different)X
 453 555 2724(external-hashing)N
 454 1119(algorithms)X
 455 1490([Lar78,)X
 456 1758(Fag79,)X
 457 2007(Lit80])X
 458 2236(and)X
 459 2381(ultimately)X
 460 2734(chose)X
 461 2946(Larson's)X
 462 3256(algorithm)X
 463 3596(as)X
 464 3692(a)X
 465 3756(basis)X
 466 3944(of)X
 467 555 2820(the)N
 468 2 f
 469 680(sdbm)X
 470 1 f
 471 875(implementation.)X
 472 1423(The)X
 473 1574(Bell)X
 474 1733(Labs)X
 475 2 f
 476 1915(dbm)X
 477 1 f
 478 2079(\(and)X
 479 2248(therefore)X
 480 2 f
 481 2565(ndbm)X
 482 1 f
 483 2743(\))X
 484 2796(is)X
 485 2875(based)X
 486 3084(on)X
 487 3190(an)X
 488 3292(algorithm)X
 489 3629(invented)X
 490 3931(by)X
 491 555 2916(Ken)N
 492 709(Thompson,)X
 493 1091([Tho90,)X
 494 1367(Tor87])X
 495 1610(and)X
 496 1746(predates)X
 497 2034(Larson's)X
 498 2335(work.)X
 499 755 3040(The)N
 500 2 f
 501 903(sdbm)X
 502 1 f
 503 1095(programming)X
 504 1553(interface)X
 505 1857(is)X
 506 1932(totally)X
 507 2158(compatible)X
 508 2536(with)X
 509 2 f
 510 2700(ndbm)X
 511 1 f
 512 2900(and)X
 513 3038(includes)X
 514 3327(a)X
 515 3385(slight)X
 516 3584(improvement)X
 517 555 3136(in)N
 518 641(database)X
 519 942(initialization.)X
 520 1410(It)X
 521 1483(is)X
 522 1560(also)X
 523 1713(expected)X
 524 2023(to)X
 525 2109(be)X
 526 2208(binary-compatible)X
 527 2819(under)X
 528 3025(most)X
 529 3203(UN*X)X
 530 3440(versions)X
 531 3730(that)X
 532 3873(sup-)X
 533 555 3232(port)N
 534 704(the)X
 535 2 f
 536 822(ndbm)X
 537 1 f
 538 1020(library.)X
 539 755 3356(The)N
 540 2 f
 541 909(sdbm)X
 542 1 f
 543 1107(implementation)X
 544 1638(shares)X
 545 1868(the)X
 546 1995(shortcomings)X
 547 2455(of)X
 548 2551(the)X
 549 2 f
 550 2678(ndbm)X
 551 1 f
 552 2885(library,)X
 553 3148(as)X
 554 3244(a)X
 555 3309(side)X
 556 3467(effect)X
 557 3680(of)X
 558 3775(various)X
 559 555 3452(simpli\256cations)N
 560 1046(to)X
 561 1129(the)X
 562 1248(original)X
 563 1518(Larson)X
 564 1762(algorithm.)X
 565 2114(It)X
 566 2183(does)X
 567 2350(produce)X
 568 2 f
 569 2629(holes)X
 570 1 f
 571 2818(in)X
 572 2900(the)X
 573 3018(page)X
 574 3190(\256le)X
 575 3312(as)X
 576 3399(it)X
 577 3463(writes)X
 578 3679(pages)X
 579 3882(past)X
 580 555 3548(the)N
 581 680(end)X
 582 823(of)X
 583 917(\256le.)X
 584 1066(\(Larson's)X
 585 1400(paper)X
 586 1605(include)X
 587 1867(a)X
 588 1929(clever)X
 589 2152(solution)X
 590 2435(to)X
 591 2523(this)X
 592 2664(problem)X
 593 2957(that)X
 594 3103(is)X
 595 3182(a)X
 596 3244(result)X
 597 3448(of)X
 598 3541(using)X
 599 3740(the)X
 600 3864(hash)X
 601 555 3644(value)N
 602 758(directly)X
 603 1032(as)X
 604 1128(a)X
 605 1193(block)X
 606 1400(address.\))X
 607 1717(On)X
 608 1844(the)X
 609 1971(other)X
 610 2165(hand,)X
 611 2370(extensive)X
 612 2702(tests)X
 613 2873(seem)X
 614 3067(to)X
 615 3158(indicate)X
 616 3441(that)X
 617 2 f
 618 3590(sdbm)X
 619 1 f
 620 3787(creates)X
 621 555 3740(fewer)N
 622 762(holes)X
 623 954(in)X
 624 1039(general,)X
 625 1318(and)X
 626 1456(the)X
 627 1576(resulting)X
 628 1878(page\256les)X
 629 2185(are)X
 630 2306(smaller.)X
 631 2584(The)X
 632 2 f
 633 2731(sdbm)X
 634 1 f
 635 2922(implementation)X
 636 3446(is)X
 637 3521(also)X
 638 3672(faster)X
 639 3873(than)X
 640 2 f
 641 555 3836(ndbm)N
 642 1 f
 643 757(in)X
 644 843(database)X
 645 1144(creation.)X
 646 1467(Unlike)X
 647 1709(the)X
 648 2 f
 649 1831(ndbm)X
 650 1 f
 651 2009(,)X
 652 2053(the)X
 653 2 f
 654 2175(sdbm)X
 655 7 f
 656 2396(store)X
 657 1 f
 658 2660(operation)X
 659 2987(will)X
 660 3134(not)X
 661 3259(``wander)X
 662 3573(away'')X
 663 3820(trying)X
 664 555 3932(to)N
 665 642(split)X
 666 804(its)X
 667 904(data)X
 668 1063(pages)X
 669 1271(to)X
 670 1358(insert)X
 671 1561(a)X
 672 1622(datum)X
 673 1847(that)X
 674 2 f
 675 1992(cannot)X
 676 1 f
 677 2235(\(due)X
 678 2403(to)X
 679 2490(elaborate)X
 680 2810(worst-case)X
 681 3179(situations\))X
 682 3537(be)X
 683 3637(inserted.)X
 684 3935(\(It)X
 685 555 4028(will)N
 686 699(fail)X
 687 826(after)X
 688 994(a)X
 689 1050(pre-de\256ned)X
 690 1436(number)X
 691 1701(of)X
 692 1788(attempts.\))X
 693 3 f
 694 555 4220(Important)N
 695 931(Compatibility)X
 696 1426(Warning)X
 697 1 f
 698 755 4344(The)N
 699 2 f
 700 904(sdbm)X
 701 1 f
 702 1097(and)X
 703 2 f
 704 1237(ndbm)X
 705 1 f
 706 1439(libraries)X
 707 2 f
 708 1726(cannot)X
 709 1 f
 710 1968(share)X
 711 2162(databases:)X
 712 2515(one)X
 713 2654(cannot)X
 714 2891(read)X
 715 3053(the)X
 716 3174(\(dir/pag\))X
 717 3478(database)X
 718 3778(created)X
 719 555 4440(by)N
 720 657(the)X
 721 777(other.)X
 722 984(This)X
 723 1148(is)X
 724 1222(due)X
 725 1359(to)X
 726 1442(the)X
 727 1561(differences)X
 728 1940(between)X
 729 2229(the)X
 730 2 f
 731 2348(ndbm)X
 732 1 f
 733 2547(and)X
 734 2 f
 735 2684(sdbm)X
 736 1 f
 737 2874(algorithms)X
 738 8 s
 739 3216 4415(2)N
 740 10 s
 741 4440(,)Y
 742 3289(and)X
 743 3426(the)X
 744 3545(hash)X
 745 3713(functions)X
 746 555 4536(used.)N
 747 769(It)X
 748 845(is)X
 749 925(easy)X
 750 1094(to)X
 751 1182(convert)X
 752 1449(between)X
 753 1743(the)X
 754 2 f
 755 1867(dbm/ndbm)X
 756 1 f
 757 2231(databases)X
 758 2565(and)X
 759 2 f
 760 2707(sdbm)X
 761 1 f
 762 2902(by)X
 763 3008(ignoring)X
 764 3305(the)X
 765 3429(index)X
 766 3633(completely:)X
 767 555 4632(see)N
 768 7 f
 769 706(dbd)X
 770 1 f
 771 (,)S
 772 7 f
 773 918(dbu)X
 774 1 f
 775 1082(etc.)X
 776 3 f
 777 555 4852(Notice)N
 778 794(of)X
 779 881(Intellectual)X
 780 1288(Property)X
 781 2 f
 782 555 4976(The)N
 783 696(entire)X
 784 1 f
 785 904(sdbm)X
 786 2 f
 787 1118(library)X
 788 1361(package,)X
 789 1670(as)X
 790 1762(authored)X
 791 2072(by)X
 792 2169(me,)X
 793 1 f
 794 2304(Ozan)X
 795 2495(S.)X
 796 2580(Yigit,)X
 797 2 f
 798 2785(is)X
 799 2858(hereby)X
 800 3097(placed)X
 801 3331(in)X
 802 3413(the)X
 803 3531(public)X
 804 3751(domain.)X
 805 1 f
 806 555 5072(As)N
 807 670(such,)X
 808 863(the)X
 809 987(author)X
 810 1218(is)X
 811 1297(not)X
 812 1425(responsible)X
 813 1816(for)X
 814 1936(the)X
 815 2060(consequences)X
 816 2528(of)X
 817 2621(use)X
 818 2754(of)X
 819 2847(this)X
 820 2988(software,)X
 821 3310(no)X
 822 3415(matter)X
 823 3645(how)X
 824 3808(awful,)X
 825 555 5168(even)N
 826 727(if)X
 827 796(they)X
 828 954(arise)X
 829 1126(from)X
 830 1302(defects)X
 831 1550(in)X
 832 1632(it.)X
 833 1716(There)X
 834 1924(is)X
 835 1997(no)X
 836 2097(expressed)X
 837 2434(or)X
 838 2521(implied)X
 839 2785(warranty)X
 840 3091(for)X
 841 3205(the)X
 842 2 f
 843 3323(sdbm)X
 844 1 f
 845 3512(library.)X
 846 8 s
 847 10 f
 848 555 5316(hhhhhhhhhhhhhhhhhh)N
 849 6 s
 850 1 f
 851 635 5391(1)N
 852 8 s
 853 691 5410(UN*X)N
 854 877(is)X
 855 936(not)X
 856 1034(a)X
 857 1078(trademark)X
 858 1352(of)X
 859 1421(any)X
 860 1529(\(dis\)organization.)X
 861 6 s
 862 635 5485(2)N
 863 8 s
 864 691 5504(Torek's)N
 865 908(discussion)X
 866 1194([Tor87])X
 867 1411(indicates)X
 868 1657(that)X
 869 2 f
 870 1772(dbm/ndbm)X
 871 1 f
 872 2061(implementations)X
 873 2506(use)X
 874 2609(the)X
 875 2705(hash)X
 876 2840(value)X
 877 2996(to)X
 878 3064(traverse)X
 879 3283(the)X
 880 3379(radix)X
 881 3528(trie)X
 882 3631(dif-)X
 883 555 5584(ferently)N
 884 772(than)X
 885 2 f
 886 901(sdbm)X
 887 1 f
 888 1055(and)X
 889 1166(as)X
 890 1238(a)X
 891 1285(result,)X
 892 1462(the)X
 893 1559(page)X
 894 1698(indexes)X
 895 1912(are)X
 896 2008(generated)X
 897 2274(in)X
 898 2 f
 899 2343(different)X
 900 1 f
 901 2579(order.)X
 902 2764(For)X
 903 2872(more)X
 904 3021(information,)X
 905 3357(send)X
 906 3492(e-mail)X
 907 3673(to)X
 908 555 5664(the)N
 909 649(author.)X
 910
 911 2 p
 912 %%Page: 2 2
 913 8 s 0 xH 0 xS 1 f
 914 10 s
 915 2216 384(-)N
 916 2263(2)X
 917 2323(-)X
 918 755 672(Since)N
 919 971(the)X
 920 2 f
 921 1107(sdbm)X
 922 1 f
 923 1314(library)X
 924 1566(package)X
 925 1868(is)X
 926 1959(in)X
 927 2058(the)X
 928 2193(public)X
 929 2430(domain,)X
 930 2727(this)X
 931 2 f
 932 2879(original)X
 933 1 f
 934 3173(release)X
 935 3434(or)X
 936 3538(any)X
 937 3691(additional)X
 938 555 768(public-domain)N
 939 1045(releases)X
 940 1323(of)X
 941 1413(the)X
 942 1534(modi\256ed)X
 943 1841(original)X
 944 2112(cannot)X
 945 2348(possibly)X
 946 2636(\(by)X
 947 2765(de\256nition\))X
 948 3120(be)X
 949 3218(withheld)X
 950 3520(from)X
 951 3698(you.)X
 952 3860(Also)X
 953 555 864(by)N
 954 659(de\256nition,)X
 955 1009(You)X
 956 1170(\(singular\))X
 957 1505(have)X
 958 1680(all)X
 959 1783(the)X
 960 1904(rights)X
 961 2109(to)X
 962 2194(this)X
 963 2332(code)X
 964 2507(\(including)X
 965 2859(the)X
 966 2980(right)X
 967 3154(to)X
 968 3239(sell)X
 969 3373(without)X
 970 3640(permission,)X
 971 555 960(the)N
 972 679(right)X
 973 856(to)X
 974 944(hoard)X
 975 8 s
 976 1127 935(3)N
 977 10 s
 978 1185 960(and)N
 979 1327(the)X
 980 1451(right)X
 981 1628(to)X
 982 1716(do)X
 983 1821(other)X
 984 2011(icky)X
 985 2174(things)X
 986 2394(as)X
 987 2486(you)X
 988 2631(see)X
 989 2759(\256t\))X
 990 2877(but)X
 991 3004(those)X
 992 3198(rights)X
 993 3405(are)X
 994 3529(also)X
 995 3683(granted)X
 996 3949(to)X
 997 555 1056(everyone)N
 998 870(else.)X
 999 755 1180(Please)N
1000 997(note)X
1001 1172(that)X
1002 1329(all)X
1003 1446(previous)X
1004 1759(distributions)X
1005 2195(of)X
1006 2298(this)X
1007 2449(software)X
1008 2762(contained)X
1009 3110(a)X
1010 3182(copyright)X
1011 3525(\(which)X
1012 3784(is)X
1013 3873(now)X
1014 555 1276(dropped\))N
1015 868(to)X
1016 953(protect)X
1017 1199(its)X
1018 1297(origins)X
1019 1542(and)X
1020 1681(its)X
1021 1779(current)X
1022 2030(public)X
1023 2253(domain)X
1024 2516(status)X
1025 2721(against)X
1026 2970(any)X
1027 3108(possible)X
1028 3392(claims)X
1029 3623(and/or)X
1030 3850(chal-)X
1031 555 1372(lenges.)N
1032 3 f
1033 555 1564(Acknowledgments)N
1034 1 f
1035 755 1688(Many)N
1036 966(people)X
1037 1204(have)X
1038 1380(been)X
1039 1556(very)X
1040 1723(helpful)X
1041 1974(and)X
1042 2114(supportive.)X
1043 2515(A)X
1044 2596(partial)X
1045 2824(list)X
1046 2944(would)X
1047 3167(necessarily)X
1048 3547(include)X
1049 3806(Rayan)X
1050 555 1784(Zacherissen)N
1051 963(\(who)X
1052 1152(contributed)X
1053 1541(the)X
1054 1663(man)X
1055 1824(page,)X
1056 2019(and)X
1057 2158(also)X
1058 2310(hacked)X
1059 2561(a)X
1060 2620(MMAP)X
1061 2887(version)X
1062 3146(of)X
1063 2 f
1064 3236(sdbm)X
1065 1 f
1066 3405(\),)X
1067 3475(Arnold)X
1068 3725(Robbins,)X
1069 555 1880(Chris)N
1070 763(Lewis,)X
1071 1013(Bill)X
1072 1166(Davidsen,)X
1073 1523(Henry)X
1074 1758(Spencer,)X
1075 2071(Geoff)X
1076 2293(Collyer,)X
1077 2587(Rich)X
1078 2772(Salz)X
1079 2944(\(who)X
1080 3143(got)X
1081 3279(me)X
1082 3411(started)X
1083 3659(in)X
1084 3755(the)X
1085 3887(\256rst)X
1086 555 1976(place\),)N
1087 792(Johannes)X
1088 1106(Ruschein)X
1089 1424(\(who)X
1090 1609(did)X
1091 1731(the)X
1092 1849(minix)X
1093 2055(port\))X
1094 2231(and)X
1095 2367(David)X
1096 2583(Tilbrook.)X
1097 2903(I)X
1098 2950(thank)X
1099 3148(you)X
1100 3288(all.)X
1101 3 f
1102 555 2168(Distribution)N
1103 992(Manifest)X
1104 1315(and)X
1105 1463(Notes)X
1106 1 f
1107 555 2292(This)N
1108 717(distribution)X
1109 1105(of)X
1110 2 f
1111 1192(sdbm)X
1112 1 f
1113 1381(includes)X
1114 1668(\(at)X
1115 1773(least\))X
1116 1967(the)X
1117 2085(following:)X
1118 7 f
1119 747 2436(CHANGES)N
1120 1323(change)X
1121 1659(log)X
1122 747 2532(README)N
1123 1323(this)X
1124 1563(file.)X
1125 747 2628(biblio)N
1126 1323(a)X
1127 1419(small)X
1128 1707(bibliography)X
1129 2331(on)X
1130 2475(external)X
1131 2907(hashing)X
1132 747 2724(dba.c)N
1133 1323(a)X
1134 1419(crude)X
1135 1707(\(n/s\)dbm)X
1136 2139(page)X
1137 2379(file)X
1138 2619(analyzer)X
1139 747 2820(dbd.c)N
1140 1323(a)X
1141 1419(crude)X
1142 1707(\(n/s\)dbm)X
1143 2139(page)X
1144 2379(file)X
1145 2619(dumper)X
1146 2955(\(for)X
1147 3195(conversion\))X
1148 747 2916(dbe.1)N
1149 1323(man)X
1150 1515(page)X
1151 1755(for)X
1152 1947(dbe.c)X
1153 747 3012(dbe.c)N
1154 1323(Janick's)X
1155 1755(database)X
1156 2187(editor)X
1157 747 3108(dbm.c)N
1158 1323(a)X
1159 1419(dbm)X
1160 1611(library)X
1161 1995(emulation)X
1162 2475(wrapper)X
1163 2859(for)X
1164 3051(ndbm/sdbm)X
1165 747 3204(dbm.h)N
1166 1323(header)X
1167 1659(file)X
1168 1899(for)X
1169 2091(the)X
1170 2283(above)X
1171 747 3300(dbu.c)N
1172 1323(a)X
1173 1419(crude)X
1174 1707(db)X
1175 1851(management)X
1176 2379(utility)X
1177 747 3396(hash.c)N
1178 1323(hashing)X
1179 1707(function)X
1180 747 3492(makefile)N
1181 1323(guess.)X
1182 747 3588(pair.c)N
1183 1323(page-level)X
1184 1851(routines)X
1185 2283(\(posted)X
1186 2667(earlier\))X
1187 747 3684(pair.h)N
1188 1323(header)X
1189 1659(file)X
1190 1899(for)X
1191 2091(the)X
1192 2283(above)X
1193 747 3780(readme.ms)N
1194 1323(troff)X
1195 1611(source)X
1196 1947(for)X
1197 2139(the)X
1198 2331(README)X
1199 2667(file)X
1200 747 3876(sdbm.3)N
1201 1323(man)X
1202 1515(page)X
1203 747 3972(sdbm.c)N
1204 1323(the)X
1205 1515(real)X
1206 1755(thing)X
1207 747 4068(sdbm.h)N
1208 1323(header)X
1209 1659(file)X
1210 1899(for)X
1211 2091(the)X
1212 2283(above)X
1213 747 4164(tune.h)N
1214 1323(place)X
1215 1611(for)X
1216 1803(tuning)X
1217 2139(&)X
1218 2235(portability)X
1219 2811(thingies)X
1220 747 4260(util.c)N
1221 1323(miscellaneous)X
1222 755 4432(dbu)N
1223 1 f
1224 924(is)X
1225 1002(a)X
1226 1063(simple)X
1227 1301(database)X
1228 1603(manipulation)X
1229 2050(program)X
1230 8 s
1231 2322 4407(4)N
1232 10 s
1233 2379 4432(that)N
1234 2524(tries)X
1235 2687(to)X
1236 2774(look)X
1237 2941(like)X
1238 3086(Bell)X
1239 3244(Labs')X
1240 7 f
1241 3480(cbt)X
1242 1 f
1243 3649(utility.)X
1244 3884(It)X
1245 3958(is)X
1246 555 4528(currently)N
1247 867(incomplete)X
1248 1245(in)X
1249 1329(functionality.)X
1250 1800(I)X
1251 1849(use)X
1252 7 f
1253 2006(dbu)X
1254 1 f
1255 2172(to)X
1256 2255(test)X
1257 2387(out)X
1258 2510(the)X
1259 2629(routines:)X
1260 2930(it)X
1261 2995(takes)X
1262 3181(\(from)X
1263 3385(stdin\))X
1264 3588(tab)X
1265 3707(separated)X
1266 555 4624(key/value)N
1267 898(pairs)X
1268 1085(for)X
1269 1210(commands)X
1270 1587(like)X
1271 7 f
1272 1765(build)X
1273 1 f
1274 2035(or)X
1275 7 f
1276 2160(insert)X
1277 1 f
1278 2478(or)X
1279 2575(takes)X
1280 2770(keys)X
1281 2947(for)X
1282 3071(commands)X
1283 3448(like)X
1284 7 f
1285 3626(delete)X
1286 1 f
1287 3944(or)X
1288 7 f
1289 555 4720(look)N
1290 1 f
1291 (.)S
1292 7 f
1293 747 4864(dbu)N
1294 939(<build|creat|look|insert|cat|delete>)X
1295 2715(dbmfile)X
1296 755 5036(dba)N
1297 1 f
1298 927(is)X
1299 1008(a)X
1300 1072(crude)X
1301 1279(analyzer)X
1302 1580(of)X
1303 2 f
1304 1675(dbm/sdbm/ndbm)X
1305 1 f
1306 2232(page)X
1307 2412(\256les.)X
1308 2593(It)X
1309 2670(scans)X
1310 2872(the)X
1311 2998(entire)X
1312 3209(page)X
1313 3389(\256le,)X
1314 3538(reporting)X
1315 3859(page)X
1316 555 5132(level)N
1317 731(statistics,)X
1318 1046(and)X
1319 1182(totals)X
1320 1375(at)X
1321 1453(the)X
1322 1571(end.)X
1323 7 f
1324 755 5256(dbd)N
1325 1 f
1326 925(is)X
1327 1004(a)X
1328 1066(crude)X
1329 1271(dump)X
1330 1479(program)X
1331 1777(for)X
1332 2 f
1333 1897(dbm/ndbm/sdbm)X
1334 1 f
1335 2452(databases.)X
1336 2806(It)X
1337 2881(ignores)X
1338 3143(the)X
1339 3267(bitmap,)X
1340 3534(and)X
1341 3675(dumps)X
1342 3913(the)X
1343 555 5352(data)N
1344 717(pages)X
1345 928(in)X
1346 1018(sequence.)X
1347 1361(It)X
1348 1437(can)X
1349 1576(be)X
1350 1679(used)X
1351 1853(to)X
1352 1942(create)X
1353 2162(input)X
1354 2353(for)X
1355 2474(the)X
1356 7 f
1357 2627(dbu)X
1358 1 f
1359 2798(utility.)X
1360 3055(Note)X
1361 3238(that)X
1362 7 f
1363 3413(dbd)X
1364 1 f
1365 3584(will)X
1366 3735(skip)X
1367 3895(any)X
1368 8 s
1369 10 f
1370 555 5432(hhhhhhhhhhhhhhhhhh)N
1371 6 s
1372 1 f
1373 635 5507(3)N
1374 8 s
1375 691 5526(You)N
1376 817(cannot)X
1377 1003(really)X
1378 1164(hoard)X
1379 1325(something)X
1380 1608(that)X
1381 1720(is)X
1382 1779(available)X
1383 2025(to)X
1384 2091(the)X
1385 2185(public)X
1386 2361(at)X
1387 2423(large,)X
1388 2582(but)X
1389 2680(try)X
1390 2767(if)X
1391 2822(it)X
1392 2874(makes)X
1393 3053(you)X
1394 3165(feel)X
1395 3276(any)X
1396 3384(better.)X
1397 6 s
1398 635 5601(4)N
1399 8 s
1400 691 5620(The)N
1401 7 f
1402 829(dbd)X
1403 1 f
1404 943(,)X
1405 7 f
1406 998(dba)X
1407 1 f
1408 1112(,)X
1409 7 f
1410 1167(dbu)X
1411 1 f
1412 1298(utilities)X
1413 1508(are)X
1414 1602(quick)X
1415 1761(hacks)X
1416 1923(and)X
1417 2032(are)X
1418 2126(not)X
1419 2225(\256t)X
1420 2295(for)X
1421 2385(production)X
1422 2678(use.)X
1423 2795(They)X
1424 2942(were)X
1425 3081(developed)X
1426 3359(late)X
1427 3467(one)X
1428 3575(night,)X
1429 555 5700(just)N
1430 664(to)X
1431 730(test)X
1432 835(out)X
1433 2 f
1434 933(sdbm)X
1435 1 f
1436 1068(,)X
1437 1100(and)X
1438 1208(convert)X
1439 1415(some)X
1440 1566(databases.)X
1441
1442 3 p
1443 %%Page: 3 3
1444 8 s 0 xH 0 xS 1 f
1445 10 s
1446 2216 384(-)N
1447 2263(3)X
1448 2323(-)X
1449 555 672(NULLs)N
1450 821(in)X
1451 903(the)X
1452 1021(key)X
1453 1157(and)X
1454 1293(data)X
1455 1447(\256elds,)X
1456 1660(thus)X
1457 1813(is)X
1458 1886(unsuitable)X
1459 2235(to)X
1460 2317(convert)X
1461 2578(some)X
1462 2767(peculiar)X
1463 3046(databases)X
1464 3374(that)X
1465 3514(insist)X
1466 3702(in)X
1467 3784(includ-)X
1468 555 768(ing)N
1469 677(the)X
1470 795(terminating)X
1471 1184(null.)X
1472 755 892(I)N
1473 841(have)X
1474 1052(also)X
1475 1240(included)X
1476 1575(a)X
1477 1670(copy)X
1478 1885(of)X
1479 2011(the)X
1480 7 f
1481 2195(dbe)X
1482 1 f
1483 2397(\()X
1484 2 f
1485 2424(ndbm)X
1486 1 f
1487 2660(DataBase)X
1488 3026(Editor\))X
1489 3311(by)X
1490 3449(Janick)X
1491 3712(Bergeron)X
1492 555 988([janick@bnr.ca])N
1493 1098(for)X
1494 1212(your)X
1495 1379(pleasure.)X
1496 1687(You)X
1497 1845(may)X
1498 2003(\256nd)X
1499 2147(it)X
1500 2211(more)X
1501 2396(useful)X
1502 2612(than)X
1503 2770(the)X
1504 2888(little)X
1505 7 f
1506 3082(dbu)X
1507 1 f
1508 3246(utility.)X
1509 7 f
1510 755 1112(dbm.[ch])N
1511 1 f
1512 1169(is)X
1513 1252(a)X
1514 2 f
1515 1318(dbm)X
1516 1 f
1517 1486(library)X
1518 1730(emulation)X
1519 2079(on)X
1520 2188(top)X
1521 2319(of)X
1522 2 f
1523 2415(ndbm)X
1524 1 f
1525 2622(\(and)X
1526 2794(hence)X
1527 3011(suitable)X
1528 3289(for)X
1529 2 f
1530 3412(sdbm)X
1531 1 f
1532 3581(\).)X
1533 3657(Written)X
1534 3931(by)X
1535 555 1208(Robert)N
1536 793(Elz.)X
1537 755 1332(The)N
1538 2 f
1539 901(sdbm)X
1540 1 f
1541 1090(library)X
1542 1324(has)X
1543 1451(been)X
1544 1623(around)X
1545 1866(in)X
1546 1948(beta)X
1547 2102(test)X
1548 2233(for)X
1549 2347(quite)X
1550 2527(a)X
1551 2583(long)X
1552 2745(time,)X
1553 2927(and)X
1554 3063(from)X
1555 3239(whatever)X
1556 3554(little)X
1557 3720(feedback)X
1558 555 1428(I)N
1559 609(received)X
1560 909(\(maybe)X
1561 1177(no)X
1562 1284(news)X
1563 1476(is)X
1564 1555(good)X
1565 1741(news\),)X
1566 1979(I)X
1567 2032(believe)X
1568 2290(it)X
1569 2360(has)X
1570 2493(been)X
1571 2671(functioning)X
1572 3066(without)X
1573 3336(any)X
1574 3478(signi\256cant)X
1575 3837(prob-)X
1576 555 1524(lems.)N
1577 752(I)X
1578 805(would,)X
1579 1051(of)X
1580 1144(course,)X
1581 1400(appreciate)X
1582 1757(all)X
1583 1863(\256xes)X
1584 2040(and/or)X
1585 2271(improvements.)X
1586 2774(Portability)X
1587 3136(enhancements)X
1588 3616(would)X
1589 3841(espe-)X
1590 555 1620(cially)N
1591 753(be)X
1592 849(useful.)X
1593 3 f
1594 555 1812(Implementation)N
1595 1122(Issues)X
1596 1 f
1597 755 1936(Hash)N
1598 944(functions:)X
1599 1288(The)X
1600 1437(algorithm)X
1601 1772(behind)X
1602 2 f
1603 2014(sdbm)X
1604 1 f
1605 2207(implementation)X
1606 2733(needs)X
1607 2939(a)X
1608 2998(good)X
1609 3181(bit-scrambling)X
1610 3671(hash)X
1611 3841(func-)X
1612 555 2032(tion)N
1613 702(to)X
1614 787(be)X
1615 886(effective.)X
1616 1211(I)X
1617 1261(ran)X
1618 1387(into)X
1619 1534(a)X
1620 1593(set)X
1621 1705(of)X
1622 1795(constants)X
1623 2116(for)X
1624 2233(a)X
1625 2292(simple)X
1626 2528(hash)X
1627 2698(function)X
1628 2988(that)X
1629 3130(seem)X
1630 3317(to)X
1631 3401(help)X
1632 2 f
1633 3561(sdbm)X
1634 1 f
1635 3752(perform)X
1636 555 2128(better)N
1637 758(than)X
1638 2 f
1639 916(ndbm)X
1640 1 f
1641 1114(for)X
1642 1228(various)X
1643 1484(inputs:)X
1644 7 f
1645 747 2272(/*)N
1646 795 2368(*)N
1647 891(polynomial)X
1648 1419(conversion)X
1649 1947(ignoring)X
1650 2379(overflows)X
1651 795 2464(*)N
1652 891(65599)X
1653 1179(nice.)X
1654 1467(65587)X
1655 1755(even)X
1656 1995(better.)X
1657 795 2560(*/)N
1658 747 2656(long)N
1659 747 2752(dbm_hash\(char)N
1660 1419(*str,)X
1661 1707(int)X
1662 1899(len\))X
1663 2139({)X
1664 939 2848(register)N
1665 1371(unsigned)X
1666 1803(long)X
1667 2043(n)X
1668 2139(=)X
1669 2235(0;)X
1670 939 3040(while)N
1671 1227(\(len--\))X
1672 1131 3136(n)N
1673 1227(=)X
1674 1323(n)X
1675 1419(*)X
1676 1515(65599)X
1677 1803(+)X
1678 1899(*str++;)X
1679 939 3232(return)N
1680 1275(n;)X
1681 747 3328(})N
1682 1 f
1683 755 3500(There)N
1684 975(may)X
1685 1145(be)X
1686 1253(better)X
1687 1467(hash)X
1688 1645(functions)X
1689 1974(for)X
1690 2099(the)X
1691 2228(purposes)X
1692 2544(of)X
1693 2642(dynamic)X
1694 2949(hashing.)X
1695 3269(Try)X
1696 3416(your)X
1697 3594(favorite,)X
1698 3895(and)X
1699 555 3596(check)N
1700 766(the)X
1701 887(page\256le.)X
1702 1184(If)X
1703 1261(it)X
1704 1328(contains)X
1705 1618(too)X
1706 1743(many)X
1707 1944(pages)X
1708 2150(with)X
1709 2315(too)X
1710 2440(many)X
1711 2641(holes,)X
1712 2853(\(in)X
1713 2965(relation)X
1714 3233(to)X
1715 3318(this)X
1716 3456(one)X
1717 3595(for)X
1718 3712(example\))X
1719 555 3692(or)N
1720 656(if)X
1721 2 f
1722 739(sdbm)X
1723 1 f
1724 942(simply)X
1725 1193(stops)X
1726 1391(working)X
1727 1692(\(fails)X
1728 1891(after)X
1729 7 f
1730 2101(SPLTMAX)X
1731 1 f
1732 2471(attempts)X
1733 2776(to)X
1734 2872(split\))X
1735 3070(when)X
1736 3278(you)X
1737 3432(feed)X
1738 3604(your)X
1739 3784(NEWS)X
1740 7 f
1741 555 3788(history)N
1742 1 f
1743 912(\256le)X
1744 1035(to)X
1745 1118(it,)X
1746 1203(you)X
1747 1344(probably)X
1748 1650(do)X
1749 1751(not)X
1750 1874(have)X
1751 2047(a)X
1752 2104(good)X
1753 2285(hashing)X
1754 2555(function.)X
1755 2883(If)X
1756 2958(you)X
1757 3099(do)X
1758 3200(better)X
1759 3404(\(for)X
1760 3545(different)X
1761 3842(types)X
1762 555 3884(of)N
1763 642(input\),)X
1764 873(I)X
1765 920(would)X
1766 1140(like)X
1767 1280(to)X
1768 1362(know)X
1769 1560(about)X
1770 1758(the)X
1771 1876(function)X
1772 2163(you)X
1773 2303(use.)X
1774 755 4008(Block)N
1775 967(sizes:)X
1776 1166(It)X
1777 1236(seems)X
1778 1453(\(from)X
1779 1657(various)X
1780 1914(tests)X
1781 2077(on)X
1782 2178(a)X
1783 2235(few)X
1784 2377(machines\))X
1785 2727(that)X
1786 2867(a)X
1787 2923(page)X
1788 3095(\256le)X
1789 3217(block)X
1790 3415(size)X
1791 7 f
1792 3588(PBLKSIZ)X
1793 1 f
1794 3944(of)X
1795 555 4104(1024)N
1796 738(is)X
1797 814(by)X
1798 917(far)X
1799 1030(the)X
1800 1150(best)X
1801 1301(for)X
1802 1417(performance,)X
1803 1866(but)X
1804 1990(this)X
1805 2127(also)X
1806 2278(happens)X
1807 2563(to)X
1808 2647(limit)X
1809 2819(the)X
1810 2939(size)X
1811 3086(of)X
1812 3175(a)X
1813 3233(key/value)X
1814 3567(pair.)X
1815 3734(Depend-)X
1816 555 4200(ing)N
1817 681(on)X
1818 785(your)X
1819 956(needs,)X
1820 1183(you)X
1821 1327(may)X
1822 1489(wish)X
1823 1663(to)X
1824 1748(increase)X
1825 2035(the)X
1826 2156(page)X
1827 2331(size,)X
1828 2499(and)X
1829 2638(also)X
1830 2790(adjust)X
1831 7 f
1832 3032(PAIRMAX)X
1833 1 f
1834 3391(\(the)X
1835 3539(maximum)X
1836 3886(size)X
1837 555 4296(of)N
1838 648(a)X
1839 710(key/value)X
1840 1048(pair)X
1841 1199(allowed:)X
1842 1501(should)X
1843 1740(always)X
1844 1989(be)X
1845 2090(at)X
1846 2173(least)X
1847 2345(three)X
1848 2531(words)X
1849 2752(smaller)X
1850 3013(than)X
1851 7 f
1852 3204(PBLKSIZ)X
1853 1 f
1854 (.\))S
1855 3612(accordingly.)X
1856 555 4392(The)N
1857 706(system-wide)X
1858 1137(version)X
1859 1399(of)X
1860 1492(the)X
1861 1616(library)X
1862 1856(should)X
1863 2095(probably)X
1864 2406(be)X
1865 2508(con\256gured)X
1866 2877(with)X
1867 3044(1024)X
1868 3229(\(distribution)X
1869 3649(default\),)X
1870 3944(as)X
1871 555 4488(this)N
1872 690(appears)X
1873 956(to)X
1874 1038(be)X
1875 1134(suf\256cient)X
1876 1452(for)X
1877 1566(most)X
1878 1741(common)X
1879 2041(uses)X
1880 2199(of)X
1881 2 f
1882 2286(sdbm)X
1883 1 f
1884 2455(.)X
1885 3 f
1886 555 4680(Portability)N
1887 1 f
1888 755 4804(This)N
1889 917(package)X
1890 1201(has)X
1891 1328(been)X
1892 1500(tested)X
1893 1707(in)X
1894 1789(many)X
1895 1987(different)X
1896 2284(UN*Xes)X
1897 2585(even)X
1898 2757(including)X
1899 3079(minix,)X
1900 3305(and)X
1901 3441(appears)X
1902 3707(to)X
1903 3789(be)X
1904 3885(rea-)X
1905 555 4900(sonably)N
1906 824(portable.)X
1907 1127(This)X
1908 1289(does)X
1909 1456(not)X
1910 1578(mean)X
1911 1772(it)X
1912 1836(will)X
1913 1980(port)X
1914 2129(easily)X
1915 2336(to)X
1916 2418(non-UN*X)X
1917 2799(systems.)X
1918 3 f
1919 555 5092(Notes)N
1920 767(and)X
1921 915(Miscellaneous)X
1922 1 f
1923 755 5216(The)N
1924 2 f
1925 913(sdbm)X
1926 1 f
1927 1115(is)X
1928 1201(not)X
1929 1336(a)X
1930 1405(very)X
1931 1581(complicated)X
1932 2006(package,)X
1933 2323(at)X
1934 2414(least)X
1935 2594(not)X
1936 2729(after)X
1937 2910(you)X
1938 3063(familiarize)X
1939 3444(yourself)X
1940 3739(with)X
1941 3913(the)X
1942 555 5312(literature)N
1943 879(on)X
1944 993(external)X
1945 1286(hashing.)X
1946 1589(There)X
1947 1811(are)X
1948 1944(other)X
1949 2143(interesting)X
1950 2514(algorithms)X
1951 2889(in)X
1952 2984(existence)X
1953 3316(that)X
1954 3469(ensure)X
1955 3712(\(approxi-)X
1956 555 5408(mately\))N
1957 825(single-read)X
1958 1207(access)X
1959 1438(to)X
1960 1525(a)X
1961 1586(data)X
1962 1745(value)X
1963 1944(associated)X
1964 2299(with)X
1965 2466(any)X
1966 2607(key.)X
1967 2768(These)X
1968 2984(are)X
1969 3107(directory-less)X
1970 3568(schemes)X
1971 3864(such)X
1972 555 5504(as)N
1973 2 f
1974 644(linear)X
1975 857(hashing)X
1976 1 f
1977 1132([Lit80])X
1978 1381(\(+)X
1979 1475(Larson)X
1980 1720(variations\),)X
1981 2 f
1982 2105(spiral)X
1983 2313(storage)X
1984 1 f
1985 2575([Mar79])X
1986 2865(or)X
1987 2954(directory)X
1988 3265(schemes)X
1989 3558(such)X
1990 3726(as)X
1991 2 f
1992 3814(exten-)X
1993 555 5600(sible)N
1994 731(hashing)X
1995 1 f
1996 1009([Fag79])X
1997 1288(by)X
1998 1393(Fagin)X
1999 1600(et)X
2000 1683(al.)X
2001 1786(I)X
2002 1838(do)X
2003 1943(hope)X
2004 2124(these)X
2005 2314(sources)X
2006 2579(provide)X
2007 2848(a)X
2008 2908(reasonable)X
2009 3276(playground)X
2010 3665(for)X
2011 3783(experi-)X
2012 555 5696(mentation)N
2013 907(with)X
2014 1081(other)X
2015 1277(algorithms.)X
2016 1690(See)X
2017 1837(the)X
2018 1966(June)X
2019 2144(1988)X
2020 2335(issue)X
2021 2526(of)X
2022 2624(ACM)X
2023 2837(Computing)X
2024 3227(Surveys)X
2025 3516([Enb88])X
2026 3810(for)X
2027 3935(an)X
2028 555 5792(excellent)N
2029 865(overview)X
2030 1184(of)X
2031 1271(the)X
2032 1389(\256eld.)X
2033
2034 4 p
2035 %%Page: 4 4
2036 10 s 0 xH 0 xS 1 f
2037 2216 384(-)N
2038 2263(4)X
2039 2323(-)X
2040 3 f
2041 555 672(References)N
2042 1 f
2043 555 824([Lar78])N
2044 875(P.-A.)X
2045 1064(Larson,)X
2046 1327(``Dynamic)X
2047 1695(Hashing'',)X
2048 2 f
2049 2056(BIT)X
2050 1 f
2051 (,)S
2052 2216(vol.)X
2053 2378(18,)X
2054 2518(pp.)X
2055 2638(184-201,)X
2056 2945(1978.)X
2057 555 948([Tho90])N
2058 875(Ken)X
2059 1029(Thompson,)X
2060 2 f
2061 1411(private)X
2062 1658(communication)X
2063 1 f
2064 2152(,)X
2065 2192(Nov.)X
2066 2370(1990)X
2067 555 1072([Lit80])N
2068 875(W.)X
2069 992(Litwin,)X
2070 1246(``)X
2071 1321(Linear)X
2072 1552(Hashing:)X
2073 1862(A)X
2074 1941(new)X
2075 2096(tool)X
2076 2261(for)X
2077 2396(\256le)X
2078 2539(and)X
2079 2675(table)X
2080 2851(addressing'',)X
2081 2 f
2082 3288(Proceedings)X
2083 3709(of)X
2084 3791(the)X
2085 3909(6th)X
2086 875 1168(Conference)N
2087 1269(on)X
2088 1373(Very)X
2089 1548(Large)X
2090 1782(Dabatases)X
2091 2163(\(Montreal\))X
2092 1 f
2093 2515(,)X
2094 2558(pp.)X
2095 2701(212-223,)X
2096 3031(Very)X
2097 3215(Large)X
2098 3426(Database)X
2099 3744(Founda-)X
2100 875 1264(tion,)N
2101 1039(Saratoga,)X
2102 1360(Calif.,)X
2103 1580(1980.)X
2104 555 1388([Fag79])N
2105 875(R.)X
2106 969(Fagin,)X
2107 1192(J.)X
2108 1284(Nievergelt,)X
2109 1684(N.)X
2110 1803(Pippinger,)X
2111 2175(and)X
2112 2332(H.)X
2113 2451(R.)X
2114 2544(Strong,)X
2115 2797(``Extendible)X
2116 3218(Hashing)X
2117 3505(-)X
2118 3552(A)X
2119 3630(Fast)X
2120 3783(Access)X
2121 875 1484(Method)N
2122 1144(for)X
2123 1258(Dynamic)X
2124 1572(Files'',)X
2125 2 f
2126 1821(ACM)X
2127 2010(Trans.)X
2128 2236(Database)X
2129 2563(Syst.)X
2130 1 f
2131 2712(,)X
2132 2752(vol.)X
2133 2894(4,)X
2134 2994(no.3,)X
2135 3174(pp.)X
2136 3294(315-344,)X
2137 3601(Sept.)X
2138 3783(1979.)X
2139 555 1608([Wal84])N
2140 875(Rich)X
2141 1055(Wales,)X
2142 1305(``Discussion)X
2143 1739(of)X
2144 1835("dbm")X
2145 2072(data)X
2146 2235(base)X
2147 2406(system'',)X
2148 2 f
2149 2730(USENET)X
2150 3051(newsgroup)X
2151 3430(unix.wizards)X
2152 1 f
2153 3836(,)X
2154 3884(Jan.)X
2155 875 1704(1984.)N
2156 555 1828([Tor87])N
2157 875(Chris)X
2158 1068(Torek,)X
2159 1300(``Re:)X
2160 1505(dbm.a)X
2161 1743(and)X
2162 1899(ndbm.a)X
2163 2177(archives'',)X
2164 2 f
2165 2539(USENET)X
2166 2852(newsgroup)X
2167 3223(comp.unix)X
2168 1 f
2169 3555(,)X
2170 3595(1987.)X
2171 555 1952([Mar79])N
2172 875(G.)X
2173 974(N.)X
2174 1073(Martin,)X
2175 1332(``Spiral)X
2176 1598(Storage:)X
2177 1885(Incrementally)X
2178 2371(Augmentable)X
2179 2843(Hash)X
2180 3048(Addressed)X
2181 3427(Storage'',)X
2182 2 f
2183 3766(Techni-)X
2184 875 2048(cal)N
2185 993(Report)X
2186 1231(#27)X
2187 1 f
2188 (,)S
2189 1391(University)X
2190 1749(of)X
2191 1836(Varwick,)X
2192 2153(Coventry,)X
2193 2491(U.K.,)X
2194 2687(1979.)X
2195 555 2172([Enb88])N
2196 875(R.)X
2197 977(J.)X
2198 1057(Enbody)X
2199 1335(and)X
2200 1480(H.)X
2201 1586(C.)X
2202 1687(Du,)X
2203 1833(``Dynamic)X
2204 2209(Hashing)X
2205 2524(Schemes'',)X
2206 2 f
2207 2883(ACM)X
2208 3080(Computing)X
2209 3463(Surveys)X
2210 1 f
2211 3713(,)X
2212 3761(vol.)X
2213 3911(20,)X
2214 875 2268(no.)N
2215 995(2,)X
2216 1075(pp.)X
2217 1195(85-113,)X
2218 1462(June)X
2219 1629(1988.)X
2220
2221 4 p
2222 %%Trailer
2223 xt
2224
2225 xs