Usenet 1994 January

home *** CD-ROM | disk | FTP | other *** search

/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume26 / db-1.6 / part07 < prev next >

Wrap

Text File | 1993-07-05 | 75.8 KB | 2,496 lines

Newsgroups: comp.sources.unix From: bostic@cs.berkeley.edu (Keith Bostic) Subject: v26i286: db-1.6 - A New Hashing Package for UNIX(tm) (updates dbm/ndbm), Part07/09 Sender: unix-sources-moderator@gw.home.vix.com Approved: vixie@gw.home.vix.com Submitted-By: bostic@cs.berkeley.edu (Keith Bostic) Posting-Number: Volume 26, Issue 286 Archive-Name: db-1.6/part07 #! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh <file", e.g.. If this archive is complete, you # will see the following message at the end: # "End of archive 7 (of 9)." # Contents: doc/dbopen.3.ps hash/hash.c hash/hash_page.c # Wrapped by vixie@gw.home.vix.com on Mon Jul 5 15:27:28 1993 PATH=/bin:/usr/bin:/usr/ucb ; export PATH if test -f 'doc/dbopen.3.ps' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'doc/dbopen.3.ps'\" else echo shar: Extracting \"'doc/dbopen.3.ps'\" $25656 characters$ sed "s/^X//" >'doc/dbopen.3.ps' <<'END_OF_FILE' X%!PS-Adobe-3.0 X%%Creator: groff version 1.08 X%%DocumentNeededResources: font Times-Roman X%%+ font Times-Bold X%%+ font Times-Italic X%%DocumentSuppliedResources: procset grops 1.08 0 X%%Pages: 4 X%%PageOrder: Ascend X%%Orientation: Portrait X%%EndComments X%%BeginProlog X%%BeginResource: procset grops 1.08 0 X/setpacking where{ Xpop Xcurrentpacking Xtrue setpacking X}if X/grops 120 dict dup begin X/SC 32 def X/A/show load def X/B{0 SC 3 -1 roll widthshow}bind def X/C{0 exch ashow}bind def X/D{0 exch 0 SC 5 2 roll awidthshow}bind def X/E{0 rmoveto show}bind def X/F{0 rmoveto 0 SC 3 -1 roll widthshow}bind def X/G{0 rmoveto 0 exch ashow}bind def X/H{0 rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/I{0 exch rmoveto show}bind def X/J{0 exch rmoveto 0 SC 3 -1 roll widthshow}bind def X/K{0 exch rmoveto 0 exch ashow}bind def X/L{0 exch rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/M{rmoveto show}bind def X/N{rmoveto 0 SC 3 -1 roll widthshow}bind def X/O{rmoveto 0 exch ashow}bind def X/P{rmoveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/Q{moveto show}bind def X/R{moveto 0 SC 3 -1 roll widthshow}bind def X/S{moveto 0 exch ashow}bind def X/T{moveto 0 exch 0 SC 5 2 roll awidthshow}bind def X/SF{ Xfindfont exch X[exch dup 0 exch 0 exch neg 0 0]makefont Xdup setfont X[exch/setfont cvx]cvx bind def X}bind def X/MF{ Xfindfont X[5 2 roll X0 3 1 roll Xneg 0 0]makefont Xdup setfont X[exch/setfont cvx]cvx bind def X}bind def X/level0 0 def X/RES 0 def X/PL 0 def X/LS 0 def X/PLG{ Xgsave newpath clippath pathbbox grestore Xexch pop add exch pop X}bind def X/BP{ X/level0 save def X1 setlinecap X1 setlinejoin X72 RES div dup scale XLS{ X90 rotate X}{ X0 PL translate X}ifelse X1 -1 scale X}bind def X/EP{ Xlevel0 restore Xshowpage X}bind def X/DA{ Xnewpath arcn stroke X}bind def X/SN{ Xtransform X.25 sub exch .25 sub exch Xround .25 add exch round .25 add exch Xitransform X}bind def X/DL{ XSN Xmoveto XSN Xlineto stroke X}bind def X/DC{ Xnewpath 0 360 arc closepath X}bind def X/TM matrix def X/DE{ XTM currentmatrix pop Xtranslate scale newpath 0 0 .5 0 360 arc closepath XTM setmatrix X}bind def X/RC/rcurveto load def X/RL/rlineto load def X/ST/stroke load def X/MT/moveto load def X/CL/closepath load def X/FL{ Xcurrentgray exch setgray fill setgray X}bind def X/BL/fill load def X/LW/setlinewidth load def X/RE{ Xfindfont Xdup maxlength 1 index/FontName known not{1 add}if dict begin X{ X1 index/FID ne{def}{pop pop}ifelse X}forall X/Encoding exch def Xdup/FontName exch def Xcurrentdict end definefont pop X}bind def X/DEFS 0 def X/EBEGIN{ Xmoveto XDEFS begin X}bind def X/EEND/end load def X/CNT 0 def X/level1 0 def X/PBEGIN{ X/level1 save def Xtranslate Xdiv 3 1 roll div exch scale Xneg exch neg exch translate X0 setgray X0 setlinecap X1 setlinewidth X0 setlinejoin X10 setmiterlimit X[]0 setdash X/setstrokeadjust where{ Xpop Xfalse setstrokeadjust X}if X/setoverprint where{ Xpop Xfalse setoverprint X}if Xnewpath X/CNT countdictstack def Xuserdict begin X/showpage{}def X}bind def X/PEND{ Xclear Xcountdictstack CNT sub{end}repeat Xlevel1 restore X}bind def Xend def X/setpacking where{ Xpop Xsetpacking X}if X%%EndResource X%%IncludeResource: font Times-Roman X%%IncludeResource: font Times-Bold X%%IncludeResource: font Times-Italic Xgrops begin/DEFS 1 dict def DEFS begin/u{.001 mul}bind def end/RES 72 def/PL X792 def/LS false def/ENC0[/asciicircum/asciitilde/Scaron/Zcaron/scaron/zcaron X/Ydieresis/trademark/quotesingle/.notdef/.notdef/.notdef/.notdef/.notdef X/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef X/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/.notdef/space X/exclam/quotedbl/numbersign/dollar/percent/ampersand/quoteright/parenleft X/parenright/asterisk/plus/comma/hyphen/period/slash/zero/one/two/three/four X/five/six/seven/eight/nine/colon/semicolon/less/equal/greater/question/at/A/B/C X/D/E/F/G/H/I/J/K/L/M/N/O/P/Q/R/S/T/U/V/W/X/Y/Z/bracketleft/backslash X/bracketright/circumflex/underscore/quoteleft/a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q X/r/s/t/u/v/w/x/y/z/braceleft/bar/braceright/tilde/.notdef/quotesinglbase X/guillemotleft/guillemotright/bullet/florin/fraction/perthousand/dagger X/daggerdbl/endash/emdash/ff/fi/fl/ffi/ffl/dotlessi/dotlessj/grave/hungarumlaut X/dotaccent/breve/caron/ring/ogonek/quotedblleft/quotedblright/oe/lslash X/quotedblbase/OE/Lslash/.notdef/exclamdown/cent/sterling/currency/yen/brokenbar X/section/dieresis/copyright/ordfeminine/guilsinglleft/logicalnot/minus X/registered/macron/degree/plusminus/twosuperior/threesuperior/acute/mu X/paragraph/periodcentered/cedilla/onesuperior/ordmasculine/guilsinglright X/onequarter/onehalf/threequarters/questiondown/Agrave/Aacute/Acircumflex/Atilde X/Adieresis/Aring/AE/Ccedilla/Egrave/Eacute/Ecircumflex/Edieresis/Igrave/Iacute X/Icircumflex/Idieresis/Eth/Ntilde/Ograve/Oacute/Ocircumflex/Otilde/Odieresis X/multiply/Oslash/Ugrave/Uacute/Ucircumflex/Udieresis/Yacute/Thorn/germandbls X/agrave/aacute/acircumflex/atilde/adieresis/aring/ae/ccedilla/egrave/eacute X/ecircumflex/edieresis/igrave/iacute/icircumflex/idieresis/eth/ntilde/ograve X/oacute/ocircumflex/otilde/odieresis/divide/oslash/ugrave/uacute/ucircumflex X/udieresis/yacute/thorn/ydieresis]def/Times-Italic@0 ENC0/Times-Italic RE X/Times-Bold@0 ENC0/Times-Bold RE/Times-Roman@0 ENC0/Times-Roman RE X%%EndProlog X%%Page: 1 1 X%%BeginPageSetup XBP X%%EndPageSetup X/F0 10/Times-Roman@0 SF 169.84(DBOPEN$3$ 1993 DBOPEN$3$)72 48 R/F1 9 X/Times-Bold@0 SF -.18(NA)72 84 S(ME).18 E F0 X(dbopen \255 database access methods)108 96 Q F1(SYNOPSIS)72 112.8 Q/F2 10 X/Times-Bold@0 SF(#include <sys/types.h>)108 124.8 Q(#include <limits.h>)108 X136.8 Q(#include <db)108 148.8 Q(.h>)-.4 E(DB *)108 172.8 Q X(dbopen$const char *\214le, int \215ags, int mode, DBTYPE type,)108 184.8 Q X(const v)158 196.8 Q(oid *openinf)-.1 E(o$;)-.25 E F1(DESCRIPTION)72 213.6 Q X/F3 10/Times-Italic@0 SF(Dbopen)108 225.6 Q F0 .032(is the library interf)2.532 XF .031(ace to database \214les.)-.1 F .031 X(The supported \214le formats are btree, hashed and UNIX \214le)5.031 F 2.82 X(oriented. The)108 237.6 R .32 X(btree format is a representation of a sorted, balanced tree structure.)2.82 F X.321(The hashed format is an)5.321 F -.15(ex)108 249.6 S .424 X(tensible, dynamic hashing scheme.).15 F .423 X(The \215at-\214le format is a byte stream \214le with \214x)5.423 F .423 X(ed or v)-.15 F .423(ariable length)-.25 F 2.906(records. The)108 261.6 R .407 X(formats and \214le format speci\214c information are described in detail in t\ Xheir respecti)2.906 F .707 -.15(ve m)-.25 H(anual).15 E(pages)108 273.6 Q F3 X(btr)2.5 E(ee)-.37 E F0($3$,).18 E F3(hash)2.5 E F0($3$ and).28 E F3 -.37 X(re)2.5 G(cno).37 E F0($3$.).18 E .433(Dbopen opens)108 290.4 R F3(\214le) X2.933 E F0 .433(for reading and/or writing.)2.933 F .433(Files ne)5.433 F -.15 X(ve)-.25 G 2.933(ri).15 G .433(ntended to be preserv)346.737 290.4 R .433 X(ed on disk may be created)-.15 F(by setting the \214le parameter to NULL.)108 X302.4 Q(The)108 319.2 Q F3<8d61>4.661 E(gs)-.1 E F0(and)4.661 E F3 2.161 X(mode ar)4.661 F(guments)-.37 E F0 2.161(are as speci\214ed to the)4.661 F F3 X(open)4.661 E F0 2.162($2$ routine, ho).24 F(we)-.25 E -.15(ve)-.25 G 2.962 X-.4(r, o).15 H 2.162(nly the O_CREA).4 F -.74(T,)-1.11 G 2.597 X(O_EXCL, O_EXLOCK, O_RDONL)108 331.2 R 5.177 -1.29(Y, O)-1 H(_RD)1.29 E 2.597 X(WR, O_SHLOCK and O_TR)-.3 F 2.596(UNC \215ags are meaningful.)-.4 F X($Note, opening a database \214le O_WR)108 343.2 Q(ONL)-.4 E 2.5(Yi)-1 G 2.5 X(sn)289.62 343.2 S(ot possible.$)301.01 343.2 Q(The)108 360 Q F3(type)5.337 E XF0(ar)5.337 E 2.837(gument is of type DBTYPE $as de\214ned in the <db)-.18 F X2.838(.h> include \214le$ and may be set to)-.4 F X(DB_BTREE, DB_HASH or DB_RECNO.)108 372 Q(The)108 388.8 Q F3(openinfo)2.85 E F0 X(ar)2.85 E .349(gument is a pointer to an access method speci\214c structure d\ Xescribed in the access method')-.18 F(s)-.55 E .03(manual page.)108 400.8 R(If) X5.03 E F3(openinfo)2.53 E F0 .031(is NULL, each access method will use def)2.53 XF .031(aults appropriate for the system and the)-.1 F(access method.)108 412.8 XQ F3(Dbopen)108 429.6 Q F0 .416 X(returns a pointer to a DB structure on success and NULL on error)2.917 F 5.416 X(.T)-.55 G .416(he DB structure is de\214ned in)423.21 429.6 R(the <db)108 X441.6 Q(.h> include \214le, and contains at least the follo)-.4 E X(wing \214elds:)-.25 E(typedef struct {)108 465.6 Q(DBTYPE type;)144 477.6 Q X(int $*close$$const DB *db$;)144 489.6 Q X(int $*del$$const DB *db, const DBT *k)144 501.6 Q -.15(ey)-.1 G 2.5(,u)-.5 XG(_int \215ags$;)318.92 501.6 Q(int $*fd$$const DB *db$;)144 513.6 Q X(int $*get$$const DB *db, DBT *k)144 525.6 Q -.15(ey)-.1 G 2.5(,D)-.5 G X(BT *data, u_int \215ags$;)297.53 525.6 Q(int $*put$$const DB *db, DBT *k) X144 537.6 Q -.15(ey)-.1 G 2.5(,c)-.5 G(onst DBT *data,)295.31 537.6 Q X(u_int \215ags$;)194 549.6 Q(int $*sync$$const DB *db, u_int \215ags$;)144 X561.6 Q(int $*seq$$const DB *db, DBT *k)144 573.6 Q -.15(ey)-.1 G 2.5(,D)-.5 XG(BT *data, u_int \215ags$;)298.64 573.6 Q 2.5(}D)108 585.6 S(B;)122.52 585.6 XQ .101 X(These elements describe a database type and a set of functions performing v) X108 602.4 R .101(arious actions.)-.25 F .101(These functions)5.101 F(tak)108 X614.4 Q 3.039(eap)-.1 G .539(ointer to a structure as returned by)140.078 614.4 XR F3(dbopen)3.038 E F0 3.038(,a).24 G .538 X(nd sometimes one or more pointers to k)323.196 614.4 R -.15(ey)-.1 G .538 X(/data struc-).15 F(tures and a \215ag v)108 626.4 Q(alue.)-.25 E 16.28 X(type The)108 643.2 R X(type of the underlying access method $and \214le format$.)2.5 E 12.95 X(close A)108 660 R .988(pointer to a routine to \215ush an)3.488 F 3.489(yc) X-.15 G .989(ached information to disk, free an)293.968 660 R 3.489(ya)-.15 G X.989(llocated resources, and)446.662 660 R .112 X(close the underlying \214le$s$.)144 672 R .111(Since k)5.112 F -.15(ey)-.1 G X.111(/data pairs may be cached in memory).15 F 2.611(,f)-.65 G .111 X(ailing to sync the \214le)455.666 672 R .494(with a)144 684 R F3(close)2.994 E XF0(or)2.994 E F3(sync)2.994 E F0 .495 X(function may result in inconsistent or lost information.)2.994 F F3(Close) X5.495 E F0 .495(routines return)2.995 F(-1 on error $setting)144 696 Q F3 X(errno)2.5 E F0 2.5($a).18 G(nd 0 on success.)254.43 696 Q 21.28(del A)108 X712.8 R(pointer to a routine to remo)2.5 E .3 -.15(ve k)-.15 H -.15(ey).05 G X(/data pairs from the database.).15 E 209.835(24, May)72 768 R(1)535 768 Q EP X%%Page: 2 2 X%%BeginPageSetup XBP X%%EndPageSetup X/F0 10/Times-Roman@0 SF 169.84(DBOPEN$3$ 1993 DBOPEN$3$)72 48 R X(The parameter)144 84 Q/F1 10/Times-Italic@0 SF<8d61>2.5 E(g)-.1 E F0 X(may be set to the follo)2.5 E(wing v)-.25 E(alue:)-.25 E(R_CURSOR)144 100.8 Q X.289(Delete the record referenced by the cursor)180 112.8 R 5.288(.T)-.55 G X.288(he cursor must ha)363.342 112.8 R .588 -.15(ve p)-.2 H(re).15 E .288 X(viously been initial-)-.25 F(ized.)180 124.8 Q F1(Delete)144 141.6 Q F0 .03 X(routines return -1 on error $setting)2.53 F F1(errno)2.53 E F0 .03 X($, 0 on success, and 1 if the speci\214ed).18 F F1 -.1(ke)2.53 G(y)-.2 E F0 X-.1(wa)2.53 G 2.53(sn).1 G .03(ot in)521.91 141.6 R(the \214le.)144 153.6 Q X25.17(fd A)108 170.4 R .451 X(pointer to a routine which returns a \214le descriptor representati)2.951 F X.75 -.15(ve o)-.25 H 2.95(ft).15 G .45(he underlying database.)431.73 170.4 R X(A)5.45 E .942(\214le descriptor referencing the same \214le will be returned \ Xto all processes which call)144 182.4 R F1(dbopen)3.442 E F0(with)3.442 E 1.629 X(the same)144 194.4 R F1(\214le)4.129 E F0 4.129(name. This)4.129 F 1.628 X(\214le descriptor may be safely used as a ar)4.128 F 1.628(gument to the)-.18 XF F1(fcntl)4.128 E F0 1.628($2$ and).51 F F1(\215oc)144 206.4 Q(k)-.2 E F0 X.425($2$ locking functions.).67 F .425 X(The \214le descriptor is not necessarily associated with an)5.425 F 2.925(yo) X-.15 G 2.925(ft)492.7 206.4 S .425(he under)501.735 206.4 R(-)-.2 E .198 X(lying \214les used by the access method.)144 218.4 R .198 X(No \214le descriptor is a)5.198 F -.25(va)-.2 G .198 X(ilable for in memory databases.).25 F F1(Fd)5.198 E F0 X(routines return -1 on error $setting)144 230.4 Q F1(errno)2.5 E F0 X($, and the \214le descriptor on success.).18 E 21.28(get A)108 247.2 R X(pointer to a routine which is the interf)2.5 E .001(ace for k)-.1 F -.15(ey) X-.1 G .001(ed retrie).15 F -.25(va)-.25 G 2.501(lf).25 G .001 X(rom the database.)399.755 247.2 R .001(The address and)5.001 F .061 X(length of the data associated with the speci\214ed)144 259.2 R F1 -.1(ke)2.561 XG(y)-.2 E F0 .06(are returned in the structure referenced by)2.561 F F1(data) X2.56 E F0(.).26 E F1(Get)144 271.2 Q F0(routines return -1 on error $setting) X2.5 E F1(errno)2.5 E F0($, 0 on success, and 1 if the).18 E F1 -.1(ke)2.5 G(y) X-.2 E F0 -.1(wa)2.5 G 2.5(sn).1 G(ot in the \214le.)471.66 271.2 Q 20.72(put A) X108 288 R(pointer to a routine to store k)2.5 E -.15(ey)-.1 G X(/data pairs in the database.).15 E(The parameter)144 304.8 Q F1<8d61>2.5 E(g) X-.1 E F0(may be set to one of the follo)2.5 E(wing v)-.25 E(alues:)-.25 E X(R_CURSOR)144 321.6 Q .051(Replace the k)180 333.6 R -.15(ey)-.1 G .051 X(/data pair referenced by the cursor).15 F 5.052(.T)-.55 G .052 X(he cursor must ha)393.98 333.6 R .352 -.15(ve p)-.2 H(re).15 E .052 X(viously been)-.25 F(initialized.)180 345.6 Q(R_IAFTER)144 362.4 Q 1.165 X(Append the data immediately after the data referenced by)180 374.4 R F1 -.1 X(ke)3.664 G(y)-.2 E F0 3.664(,c).32 G 1.164(reating a ne)446.758 374.4 R 3.664 X(wk)-.25 G -.15(ey)511.27 374.4 S(/data).15 E(pair)180 386.4 Q 6.065(.T)-.55 G X1.065(he record number of the appended k)209.675 386.4 R -.15(ey)-.1 G 1.065 X(/data pair is returned in the).15 F F1 -.1(ke)3.565 G(y)-.2 E F0(structure.) X3.565 E($Applicable only to the DB_RECNO access method.$)180 398.4 Q X(R_IBEFORE)144 415.2 Q 1.293 X(Insert the data immediately before the data referenced by)180 427.2 R F1 -.1 X(ke)3.793 G(y)-.2 E F0 3.793(,c).32 G 1.293(reating a ne)446.371 427.2 R 3.793 X(wk)-.25 G -.15(ey)511.27 427.2 S(/data).15 E(pair)180 439.2 Q 6.54(.T)-.55 G X1.54(he record number of the inserted k)210.15 439.2 R -.15(ey)-.1 G 1.541 X(/data pair is returned in the).15 F F1 -.1(ke)4.041 G(y)-.2 E F0(structure.) X4.041 E($Applicable only to the DB_RECNO access method.$)180 451.2 Q(R_NOO) X144 468 Q(VER)-.5 E(WRITE)-.55 E(Enter the ne)180 480 Q 2.5(wk)-.25 G -.15(ey) X242.69 480 S(/data pair only if the k).15 E .3 -.15(ey d)-.1 H(oes not pre).15 XE(viously e)-.25 E(xist.)-.15 E(R_SETCURSOR)144 496.8 Q 1.36(Store the k)180 X508.8 R -.15(ey)-.1 G 1.36(/data pair).15 F 3.86(,s)-.4 G 1.359 X(etting or initializing the position of the cursor to reference it.)283.94 X508.8 R($Applicable only to the DB_BTREE and DB_RECNO access methods.$)180 X520.8 Q .563(R_SETCURSOR is a)144 537.6 R -.25(va)-.2 G .564 X(ilable only for the DB_BTREE and DB_RECNO access methods because).25 F X(it implies that the k)144 549.6 Q -.15(ey)-.1 G 2.5(sh).15 G -2.25 -.2(av e) X241.81 549.6 T(an inherent order which does not change.)2.7 E .416 X(R_IAFTER and R_IBEFORE are a)144 566.4 R -.25(va)-.2 G .416 X(ilable only for the DB_RECNO access method because the).25 F(y)-.15 E 1.221 X(each imply that the access method is able to create ne)144 578.4 R 3.722(wk) X-.25 G -.15(ey)385.644 578.4 S 3.722(s. This).15 F 1.222(is only true if the k) X3.722 F -.15(ey)-.1 G 3.722(sa).15 G(re)532.23 578.4 Q X(ordered and independent, record numbers for e)144 590.4 Q(xample.)-.15 E .289 X(The def)144 607.2 R .289(ault beha)-.1 F .289(vior of the)-.2 F F1(put)2.789 E XF0 .289(routines is to enter the ne)2.789 F 2.789(wk)-.25 G -.15(ey)388.998 X607.2 S .288(/data pair).15 F 2.788(,r)-.4 G .288(eplacing an)444.284 607.2 R X2.788(yp)-.15 G(re)503.03 607.2 Q(viously)-.25 E -.15(ex)144 619.2 S(isting k) X.15 E -.15(ey)-.1 G(.)-.5 E F1(Put)144 636 Q F0 .37 X(routines return -1 on error $setting)2.87 F F1(errno)2.87 E F0 .37 X($, 0 on success, and 1 if the R_NOO).18 F(VER)-.5 E(WRITE)-.55 E F1<8d61>2.87 XE(g)-.1 E F0 -.1(wa)144 648 S 2.5(ss).1 G(et and the k)165.84 648 Q .3 -.15 X(ey a)-.1 H(lready e).15 E(xists in the \214le.)-.15 E 20.17(seq A)108 664.8 R X.002(pointer to a routine which is the interf)2.502 F .002 X(ace for sequential retrie)-.1 F -.25(va)-.25 G 2.502(lf).25 G .002 X(rom the database.)416.694 664.8 R .001(The address)5.001 F .219 X(and length of the k)144 676.8 R .519 -.15(ey a)-.1 H .219 X(re returned in the structure referenced by).15 F F1 -.1(ke)2.72 G(y)-.2 E F0 X2.72(,a).32 G .22(nd the address and length of)426.42 676.8 R X(the data are returned in the structure referenced by)144 688.8 Q F1(data)2.5 E XF0(.).26 E .937(Sequential k)144 705.6 R -.15(ey)-.1 G .937(/data pair retrie) X.15 F -.25(va)-.25 G 3.437(lm).25 G .936(ay be)289.748 705.6 R .936(gin at an) X-.15 F 3.436(yt)-.15 G .936(ime, and the position of the `)359.292 705.6 R X(`cursor')-.74 E 3.436('i)-.74 G 3.436(sn)519.894 705.6 S(ot)532.22 705.6 Q(af) X144 717.6 Q 1.585(fected by calls to the)-.25 F F1(del)4.085 E F0(,).51 E F1 X-.1(ge)4.085 G(t).1 E F0(,).68 E F1(put)4.086 E F0 4.086(,o).68 G(r)308.452 X717.6 Q F1(sync)4.086 E F0 4.086(routines. Modi\214cations)4.086 F 1.586 X(to the database during a)4.086 F 1.404(sequential scan will be re\215ected in\ X the scan, i.e. records inserted behind the cursor will not be)144 729.6 R X209.835(24, May)72 768 R(2)535 768 Q EP X%%Page: 3 3 X%%BeginPageSetup XBP X%%EndPageSetup X/F0 10/Times-Roman@0 SF 169.84(DBOPEN$3$ 1993 DBOPEN$3$)72 48 R X(returned while records inserted in front of the cursor will be returned.)144 X84 Q(The \215ag v)144 100.8 Q(alue)-.25 E/F1 10/Times-Bold@0 SF(must)2.5 E F0 X(be set to one of the follo)2.5 E(wing v)-.25 E(alues:)-.25 E(R_CURSOR)144 X117.6 Q .523(The data associated with the speci\214ed k)180 129.6 R .824 -.15 X(ey i)-.1 H 3.024(sr).15 G 3.024(eturned. This)367.236 129.6 R(dif)3.024 E .524 X(fers from the)-.25 F/F2 10/Times-Italic@0 SF -.1(ge)3.024 G(t).1 E F0 X(routines)3.024 E 1.143 X(in that it sets or initializes the cursor to the location of the k)180 141.6 R X1.443 -.15(ey a)-.1 H 3.642(sw).15 G 3.642(ell. $Note,)464.924 141.6 R 1.142 X(for the)3.642 F 1.275(DB_BTREE access method, the returned k)180 153.6 R 1.575 X-.15(ey i)-.1 H 3.775(sn).15 G 1.276(ot necessarily an e)386.425 153.6 R 1.276 X(xact match for the)-.15 F .598(speci\214ed k)180 165.6 R -.15(ey)-.1 G 5.598 X(.T)-.5 G .598(he returned k)246.396 165.6 R .898 -.15(ey i)-.1 H 3.098(st).15 XG .598(he smallest k)325.188 165.6 R .898 -.15(ey g)-.1 H .598 X(reater than or equal to the speci\214ed).15 F -.1(ke)180 177.6 S 1.3 -.65 X(y, p)-.05 H(ermitting partial k).65 E .3 -.15(ey m)-.1 H X(atches and range searches.$).15 E(R_FIRST)144 194.4 Q 1.043(The \214rst k)180 X206.4 R -.15(ey)-.1 G 1.044(/data pair of the database is returned, and the cu\ Xrsor is set or initialized to).15 F(reference it.)180 218.4 Q(R_LAST)144 235.2 XQ .085(The last k)180 247.2 R -.15(ey)-.1 G .085(/data pair of the database is\ X returned, and the cursor is set or initialized to ref-).15 F(erence it.)180 X259.2 Q($Applicable only to the DB_BTREE and DB_RECNO access methods.$)5 E X(R_NEXT)144 276 Q(Retrie)180 288 Q .604 -.15(ve t)-.25 H .304(he k).15 F -.15 X(ey)-.1 G .304(/data pair immediately after the cursor).15 F 5.304(.I)-.55 G X2.804(ft)410.622 288 S .305(he cursor is not yet set, this is)419.536 288 R X(the same as the R_FIRST \215ag.)180 300 Q(R_PREV)144 316.8 Q(Retrie)180 328.8 XQ .755 -.15(ve t)-.25 H .455(he k).15 F -.15(ey)-.1 G .455 X(/data pair immediately before the cursor).15 F 5.455(.I)-.55 G 2.955(ft)419.05 X328.8 S .454(he cursor is not yet set, this)428.115 328.8 R .62 X(is the same as the R_LAST \215ag.)180 340.8 R .621 X($Applicable only to the DB_BTREE and DB_RECNO)5.621 F(access methods.$)180 X352.8 Q .911(R_LAST and R_PREV are a)144 369.6 R -.25(va)-.2 G .911 X(ilable only for the DB_BTREE and DB_RECNO access methods).25 F(because the)144 X381.6 Q 2.5(ye)-.15 G(ach imply that the k)202.16 381.6 Q -.15(ey)-.1 G 2.5(sh) X.15 G -2.25 -.2(av e)302.18 381.6 T(an inherent order which does not change.) X2.7 E F2(Seq)144 398.4 Q F0 .061(routines return -1 on error $setting)2.561 F XF2(errno)2.561 E F0 .061($, 0 on success and 1 if there are no k).18 F -.15 X(ey)-.1 G .061(/data pairs less).15 F .35 X(than or greater than the speci\214ed or current k)144 410.4 R -.15(ey)-.1 G X5.349(.I)-.5 G 2.849(ft)346.467 410.4 S .349 X(he DB_RECNO access method is being used,)355.426 410.4 R .025 X(and if the database \214le is a character special \214le and no complete k)144 X422.4 R -.15(ey)-.1 G .025(/data pairs are currently a).15 F -.25(va)-.2 G(il-) X.25 E(able, the)144 434.4 Q F2(seq)2.5 E F0(routines return 2.)2.5 E 15.17 X(sync A)108 451.2 R .458(pointer to a routine to \215ush an)2.958 F 2.957(yc) X-.15 G .457(ached information to disk.)289.72 451.2 R .457 X(If the database is in memory only)5.457 F(,)-.65 E(the)144 463.2 Q F2(sync)2.5 XE F0(routine has no ef)2.5 E(fect and will al)-.25 E -.1(wa)-.1 G(ys succeed.) X.1 E(The \215ag v)144 480 Q(alue may be set to the follo)-.25 E(wing v)-.25 E X(alue:)-.25 E(R_RECNOSYNC)144 496.8 Q .077(If the DB_RECNO access method is be\ Xing used, this \215ag causes the sync routine to apply)180 508.8 R .75(to the \ Xbtree \214le which underlies the recno \214le, not the recno \214le itself.)180 X520.8 R .75($See the)5.75 F F2(bfname)3.25 E F0(\214eld of the)180 532.8 Q F2 X-.37(re)2.5 G(cno).37 E F0(\(3$ manual page for more information.\)).18 E F2 X(Sync)144 549.6 Q F0(routines return -1 on error $setting)2.5 E F2(errno)2.5 E XF0 2.5($a).18 G(nd 0 on success.)336.91 549.6 Q/F3 9/Times-Bold@0 SF(KEY/D)72 X566.4 Q -1.35 -.855(AT A)-.315 H -.666(PA)3.105 G(IRS).666 E F0 .134 X(Access to all \214le types is based on k)108 578.4 R -.15(ey)-.1 G .134 X(/data pairs.).15 F .134(Both k)5.134 F -.15(ey)-.1 G 2.634(sa).15 G .134 X(nd data are represented by the follo)359.078 578.4 R .135(wing data)-.25 F X(structure:)108 590.4 Q(typedef struct {)108 607.2 Q -.2(vo)144 619.2 S X(id *data;).2 E(size_t size;)144 631.2 Q 2.5(}D)108 643.2 S(BT)122.52 643.2 Q X(;)-.55 E(The elements of the DBT structure are de\214ned as follo)108 660 Q X(ws:)-.25 E 16.84(data A)108 676.8 R(pointer to a byte string.)2.5 E 17.95 X(size The)108 693.6 R(length of the byte string.)2.5 E -2.15 -.25(Ke y)108 X710.4 T .829(and data byte strings may reference strings of essentially unlimi\ Xted length although an)3.579 F 3.328(yt)-.15 G 1.028 -.1(wo o)492.894 710.4 T X3.328(ft).1 G(hem)522.78 710.4 Q 1.133(must \214t into a)108 722.4 R -.25(va) X-.2 G 1.134(ilable memory at the same time.).25 F 1.134 X(It should be noted that the access methods pro)6.134 F 1.134(vide no)-.15 F X209.835(24, May)72 768 R(3)535 768 Q EP X%%Page: 4 4 X%%BeginPageSetup XBP X%%EndPageSetup X/F0 10/Times-Roman@0 SF 169.84(DBOPEN$3$ 1993 DBOPEN$3$)72 48 R X(guarantees about byte string alignment.)108 84 Q/F1 9/Times-Bold@0 SF(ERR)72 X100.8 Q(ORS)-.27 E F0(The)108 112.8 Q/F2 10/Times-Italic@0 SF(dbopen)3.389 E F0 X.889(routine may f)3.389 F .889(ail and set)-.1 F F2(errno)3.388 E F0 .888 X(for an)3.388 F 3.388(yo)-.15 G 3.388(ft)324.376 112.8 S .888 X(he errors speci\214ed for the library routines)333.874 112.8 R F2(open)3.388 E XF0($2$).24 E(and)108 124.8 Q F2(malloc)2.5 E F0($3$ or the follo).31 E X(wing:)-.25 E([EFTYPE])108 141.6 Q 2.5<418c>144 153.6 S X(le is incorrectly formatted.)159.28 153.6 Q([EINV)108 170.4 Q(AL])-1.35 E X2.812(Ap)144 182.4 S .313(arameter has been speci\214ed $hash function, pad b\ Xyte etc.$ that is incompatible with the current)159.032 182.4 R .406 X(\214le speci\214cation or which is not meaningful for the function $for e)144 X194.4 R .405(xample, use of the cursor with-)-.15 F .099 X(out prior initialization$ or there is a mismatch between the v)144 206.4 R .1 X(ersion number of \214le and the softw)-.15 F(are.)-.1 E(The)108 223.2 Q F2 X(close)3.469 E F0 .969(routines may f)3.469 F .969(ail and set)-.1 F F2(errno) X3.469 E F0 .969(for an)3.469 F 3.469(yo)-.15 G 3.469(ft)320.18 223.2 S .969 X(he errors speci\214ed for the library routines)329.759 223.2 R F2(close)3.468 XE F0($2$,).18 E F2 -.37(re)108 235.2 S(ad).37 E F0($2$,).77 E F2(write)2.5 XE F0($2$,).18 E F2(fr)2.5 E(ee)-.37 E F0($3$, or).18 E F2(fsync)2.5 E F0 X($2$.).31 E(The)108 252 Q F2(del)2.969 E F0(,).51 E F2 -.1(ge)2.969 G(t).1 E XF0(,).68 E F2(put)2.969 E F0(and)2.969 E F2(seq)2.969 E F0 .469(routines may f) X2.969 F .469(ail and set)-.1 F F2(errno)2.97 E F0 .47(for an)2.97 F 2.97(yo) X-.15 G 2.97(ft)377.59 252 S .47(he errors speci\214ed for the library rou-) X386.67 252 R(tines)108 264 Q F2 -.37(re)2.5 G(ad).37 E F0($2$,).77 E F2 X(write)2.5 E F0($2$,).18 E F2(fr)2.5 E(ee)-.37 E F0($3$ or).18 E F2(malloc) X2.5 E F0($3$.).31 E(The)108 280.8 Q F2(fd)2.5 E F0(routines will f)2.5 E X(ail and set)-.1 E F2(errno)2.5 E F0(to ENOENT for in memory databases.)2.5 E X(The)108 297.6 Q F2(sync)2.5 E F0(routines may f)2.5 E(ail and set)-.1 E F2 X(errno)2.5 E F0(for an)2.5 E 2.5(yo)-.15 G 2.5(ft)307.71 297.6 S X(he errors speci\214ed for the library routine)316.32 297.6 Q F2(fsync)2.5 E F0 X($2$.).31 E F1(SEE ALSO)72 314.4 Q F2(btr)108 326.4 Q(ee)-.37 E F0($3$,).18 XE F2(hash)2.5 E F0($3$,).28 E F2(mpool)2.5 E F0($3$,).51 E F2 -.37(re)2.5 G X(cno).37 E F0($3$).18 E F1 -.09(BU)72 343.2 S(GS).09 E F0 .399 X(The typedef DBT is a mnemonic for `)108 355.2 R .399(`data base thang')-.74 F X.399(', and w)-.74 F .399(as used because noone could think of a rea-)-.1 F X(sonable name that w)108 367.2 Q(asn')-.1 E 2.5(ta)-.18 G(lready used.)216.03 X367.2 Q(The \214le descriptor interf)108 384 Q X(ace is a kluge and will be deleted in a future v)-.1 E(ersion of the interf) X-.15 E(ace.)-.1 E(None of the access methods pro)108 400.8 Q(vide an)-.15 E 2.5 X(yf)-.15 G(orm of concurrent access, locking, or transactions.)275.16 400.8 Q X209.835(24, May)72 768 R(4)535 768 Q EP X%%Trailer Xend X%%EOF END_OF_FILE if test 25656 -ne `wc -c <'doc/dbopen.3.ps'`; then echo shar: \"'doc/dbopen.3.ps'\" unpacked with wrong size! fi # end of 'doc/dbopen.3.ps' fi if test -f 'hash/hash.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'hash/hash.c'\" else echo shar: Extracting \"'hash/hash.c'\" $23885 characters$ sed "s/^X//" >'hash/hash.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)hash.c 8.1 (Berkeley) 6/6/93"; X#endif /* LIBC_SCCS and not lint */ X X#include <sys/param.h> X#include <sys/stat.h> X X#include <errno.h> X#include <fcntl.h> X#include <stdio.h> X#include <stdlib.h> X#include <string.h> X#include <unistd.h> X#ifdef DEBUG X#include <assert.h> X#endif X X#include <db.h> X#include "hash.h" X#include "page.h" X#include "extern.h" X Xstatic int alloc_segs __P((HTAB *, int)); Xstatic int flush_meta __P((HTAB *)); Xstatic int hash_access __P((HTAB *, ACTION, DBT *, DBT *)); Xstatic int hash_close __P((DB *)); Xstatic int hash_delete __P((const DB *, const DBT *, u_int)); Xstatic int hash_fd __P((const DB *)); Xstatic int hash_get __P((const DB *, const DBT *, DBT *, u_int)); Xstatic int hash_put __P((const DB *, DBT *, const DBT *, u_int)); Xstatic void *hash_realloc __P((SEGMENT **, int, int)); Xstatic int hash_seq __P((const DB *, DBT *, DBT *, u_int)); Xstatic int hash_sync __P((const DB *, u_int)); Xstatic int hdestroy __P((HTAB *)); Xstatic HTAB *init_hash __P((HTAB *, const char *, HASHINFO *)); Xstatic int init_htab __P((HTAB *, int)); X#if BYTE_ORDER == LITTLE_ENDIAN Xstatic void swap_header __P((HTAB *)); Xstatic void swap_header_copy __P((HASHHDR *, HASHHDR *)); X#endif X X/* Fast arithmetic, relying on powers of 2, */ X#define MOD(x, y) ((x) & ((y) - 1)) X X#define RETURN_ERROR(ERR, LOC) { save_errno = ERR; goto LOC; } X X/* Return values */ X#define SUCCESS (0) X#define ERROR (-1) X#define ABNORMAL (1) X X#ifdef HASH_STATISTICS Xlong hash_accesses, hash_collisions, hash_expansions, hash_overflows; X#endif X X/************************** INTERFACE ROUTINES ***************************/ X/* OPEN/CLOSE */ X Xextern DB * X__hash_open(file, flags, mode, info) X const char *file; X int flags, mode; X const HASHINFO *info; /* Special directives for create */ X{ X HTAB *hashp; X struct stat statbuf; X DB *dbp; X int bpages, hdrsize, new_table, nsegs, save_errno; X X if ((flags & O_ACCMODE) == O_WRONLY) { X errno = EINVAL; X return (NULL); X } X X if (!(hashp = calloc(1, sizeof(HTAB)))) X return (NULL); X hashp->fp = -1; X /* X * Select flags relevant to us. Even if user wants write only, we need X * to be able to read the actual file, so we need to open it read/write. X * But, the field in the hashp structure needs to be accurate so that X * we can check accesses. X */ X hashp->flags = flags = flags & __USE_OPEN_FLAGS; X X new_table = 0; X if (!file || (flags & O_TRUNC) || X (stat(file, &statbuf) && (errno == ENOENT))) { X if (errno == ENOENT) X errno = 0; /* Just in case someone looks at errno */ X new_table = 1; X } X if (file) { X if ((hashp->fp = open(file, flags, mode)) == -1) X RETURN_ERROR(errno, error0); X (void)fcntl(hashp->fp, F_SETFD, 1); X } X if (new_table) { X if (!(hashp = init_hash(hashp, file, (HASHINFO *)info))) X RETURN_ERROR(errno, error1); X } else { X /* Table already exists */ X if (info && info->hash) X hashp->hash = info->hash; X else X hashp->hash = __default_hash; X X hdrsize = read(hashp->fp, &hashp->hdr, sizeof(HASHHDR)); X#if BYTE_ORDER == LITTLE_ENDIAN X swap_header(hashp); X#endif X if (hdrsize == -1) X RETURN_ERROR(errno, error1); X if (hdrsize != sizeof(HASHHDR)) X RETURN_ERROR(EFTYPE, error1); X /* Verify file type, versions and hash function */ X if (hashp->MAGIC != HASHMAGIC) X RETURN_ERROR(EFTYPE, error1); X if (hashp->VERSION != HASHVERSION) X RETURN_ERROR(EFTYPE, error1); X if (hashp->hash(CHARKEY, sizeof(CHARKEY)) != hashp->H_CHARKEY) X RETURN_ERROR(EFTYPE, error1); X /* X * Figure out how many segments we need. Max_Bucket is the X * maximum bucket number, so the number of buckets is X * max_bucket + 1. X */ X nsegs = (hashp->MAX_BUCKET + 1 + hashp->SGSIZE - 1) / X hashp->SGSIZE; X hashp->nsegs = 0; X if (alloc_segs(hashp, nsegs)) X /* X * If alloc_segs fails, table will have been destroyed X * and errno will have been set. X */ X return (NULL); X /* Read in bitmaps */ X bpages = (hashp->SPARES[hashp->OVFL_POINT] + X (hashp->BSIZE << BYTE_SHIFT) - 1) >> X (hashp->BSHIFT + BYTE_SHIFT); X X hashp->nmaps = bpages; X (void)memset(&hashp->mapp[0], 0, bpages * sizeof(u_long *)); X } X X /* Initialize Buffer Manager */ X if (info && info->cachesize) X __buf_init(hashp, info->cachesize); X else X __buf_init(hashp, DEF_BUFSIZE); X X hashp->new_file = new_table; X hashp->save_file = file && (hashp->flags & O_RDWR); X hashp->cbucket = -1; X if (!(dbp = malloc(sizeof(DB)))) { X save_errno = errno; X hdestroy(hashp); X errno = save_errno; X return (NULL); X } X dbp->internal = hashp; X dbp->close = hash_close; X dbp->del = hash_delete; X dbp->fd = hash_fd; X dbp->get = hash_get; X dbp->put = hash_put; X dbp->seq = hash_seq; X dbp->sync = hash_sync; X dbp->type = DB_HASH; X X#ifdef DEBUG X (void)fprintf(stderr, X"%s\n%s%x\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%d\n%s%x\n%s%x\n%s%d\n%s%d\n", X "init_htab:", X "TABLE POINTER ", hashp, X "BUCKET SIZE ", hashp->BSIZE, X "BUCKET SHIFT ", hashp->BSHIFT, X "DIRECTORY SIZE ", hashp->DSIZE, X "SEGMENT SIZE ", hashp->SGSIZE, X "SEGMENT SHIFT ", hashp->SSHIFT, X "FILL FACTOR ", hashp->FFACTOR, X "MAX BUCKET ", hashp->MAX_BUCKET, X "OVFL POINT ", hashp->OVFL_POINT, X "LAST FREED ", hashp->LAST_FREED, X "HIGH MASK ", hashp->HIGH_MASK, X "LOW MASK ", hashp->LOW_MASK, X "NSEGS ", hashp->nsegs, X "NKEYS ", hashp->NKEYS); X#endif X#ifdef HASH_STATISTICS X hash_overflows = hash_accesses = hash_collisions = hash_expansions = 0; X#endif X return (dbp); X Xerror1: X if (hashp != NULL) X (void)close(hashp->fp); X Xerror0: X free(hashp); X errno = save_errno; X return (NULL); X} X Xstatic int Xhash_close(dbp) X DB *dbp; X{ X HTAB *hashp; X int retval; X X if (!dbp) X return (ERROR); X X hashp = (HTAB *)dbp->internal; X retval = hdestroy(hashp); X free(dbp); X return (retval); X} X Xstatic int Xhash_fd(dbp) X const DB *dbp; X{ X HTAB *hashp; X X if (!dbp) X return (ERROR); X X hashp = (HTAB *)dbp->internal; X if (hashp->fp == -1) { X errno = ENOENT; X return (-1); X } X return (hashp->fp); X} X X/************************** LOCAL CREATION ROUTINES **********************/ Xstatic HTAB * Xinit_hash(hashp, file, info) X HTAB *hashp; X const char *file; X HASHINFO *info; X{ X struct stat statbuf; X int nelem; X X nelem = 1; X hashp->NKEYS = 0; X hashp->LORDER = BYTE_ORDER; X hashp->BSIZE = DEF_BUCKET_SIZE; X hashp->BSHIFT = DEF_BUCKET_SHIFT; X hashp->SGSIZE = DEF_SEGSIZE; X hashp->SSHIFT = DEF_SEGSIZE_SHIFT; X hashp->DSIZE = DEF_DIRSIZE; X hashp->FFACTOR = DEF_FFACTOR; X hashp->hash = __default_hash; X memset(hashp->SPARES, 0, sizeof(hashp->SPARES)); X memset(hashp->BITMAPS, 0, sizeof (hashp->BITMAPS)); X X /* Fix bucket size to be optimal for file system */ X if (file != NULL) { X if (stat(file, &statbuf)) X return (NULL); X hashp->BSIZE = statbuf.st_blksize; X hashp->BSHIFT = __log2(hashp->BSIZE); X } X X if (info) { X if (info->bsize) { X /* Round pagesize up to power of 2 */ X hashp->BSHIFT = __log2(info->bsize); X hashp->BSIZE = 1 << hashp->BSHIFT; X if (hashp->BSIZE > MAX_BSIZE) { X errno = EINVAL; X return (NULL); X } X } X if (info->ffactor) X hashp->FFACTOR = info->ffactor; X if (info->hash) X hashp->hash = info->hash; X if (info->nelem) X nelem = info->nelem; X if (info->lorder) { X if (info->lorder != BIG_ENDIAN && X info->lorder != LITTLE_ENDIAN) { X errno = EINVAL; X return (NULL); X } X hashp->LORDER = info->lorder; X } X } X /* init_htab should destroy the table and set errno if it fails */ X if (init_htab(hashp, nelem)) X return (NULL); X else X return (hashp); X} X/* X * This calls alloc_segs which may run out of memory. Alloc_segs will destroy X * the table and set errno, so we just pass the error information along. X * X * Returns 0 on No Error X */ Xstatic int Xinit_htab(hashp, nelem) X HTAB *hashp; X int nelem; X{ X register int nbuckets, nsegs; X int l2; X X /* X * Divide number of elements by the fill factor and determine a X * desired number of buckets. Allocate space for the next greater X * power of two number of buckets. X */ X nelem = (nelem - 1) / hashp->FFACTOR + 1; X X l2 = __log2(MAX(nelem, 2)); X nbuckets = 1 << l2; X X hashp->SPARES[l2] = l2 + 1; X hashp->SPARES[l2 + 1] = l2 + 1; X hashp->OVFL_POINT = l2; X hashp->LAST_FREED = 2; X X /* First bitmap page is at: splitpoint l2 page offset 1 */ X if (__init_bitmap(hashp, OADDR_OF(l2, 1), l2 + 1, 0)) X return (-1); X X hashp->MAX_BUCKET = hashp->LOW_MASK = nbuckets - 1; X hashp->HIGH_MASK = (nbuckets << 1) - 1; X hashp->HDRPAGES = ((MAX(sizeof(HASHHDR), MINHDRSIZE) - 1) >> X hashp->BSHIFT) + 1; X X nsegs = (nbuckets - 1) / hashp->SGSIZE + 1; X nsegs = 1 << __log2(nsegs); X X if (nsegs > hashp->DSIZE) X hashp->DSIZE = nsegs; X return (alloc_segs(hashp, nsegs)); X} X X/********************** DESTROY/CLOSE ROUTINES ************************/ X X/* X * Flushes any changes to the file if necessary and destroys the hashp X * structure, freeing all allocated space. X */ Xstatic int Xhdestroy(hashp) X HTAB *hashp; X{ X int i, save_errno; X X save_errno = 0; X X#ifdef HASH_STATISTICS X (void)fprintf(stderr, "hdestroy: accesses %ld collisions %ld\n", X hash_accesses, hash_collisions); X (void)fprintf(stderr, "hdestroy: expansions %ld\n", X hash_expansions); X (void)fprintf(stderr, "hdestroy: overflows %ld\n", X hash_overflows); X (void)fprintf(stderr, "keys %ld maxp %d segmentcount %d\n", X hashp->NKEYS, hashp->MAX_BUCKET, hashp->nsegs); X X for (i = 0; i < NCACHED; i++) X (void)fprintf(stderr, X "spares[%d] = %d\n", i, hashp->SPARES[i]); X#endif X /* X * Call on buffer manager to free buffers, and if required, X * write them to disk. X */ X if (__buf_free(hashp, 1, hashp->save_file)) X save_errno = errno; X if (hashp->dir) { X free(*hashp->dir); /* Free initial segments */ X /* Free extra segments */ X while (hashp->exsegs--) X free(hashp->dir[--hashp->nsegs]); X free(hashp->dir); X } X if (flush_meta(hashp) && !save_errno) X save_errno = errno; X /* Free Bigmaps */ X for (i = 0; i < hashp->nmaps; i++) X if (hashp->mapp[i]) X free(hashp->mapp[i]); X X if (hashp->fp != -1) X (void)close(hashp->fp); X X if (save_errno) { X errno = save_errno; X return (ERROR); X } X return (SUCCESS); X} X/* X * Write modified pages to disk X * X * Returns: X * 0 == OK X * -1 ERROR X */ Xstatic int Xhash_sync(dbp, flags) X const DB *dbp; X u_int flags; X{ X HTAB *hashp; X X if (flags != 0) { X errno = EINVAL; X return (ERROR); X } X X if (!dbp) X return (ERROR); X X hashp = (HTAB *)dbp->internal; X if (!hashp->save_file) X return (0); X if (__buf_free(hashp, 0, 1) || flush_meta(hashp)) X return (ERROR); X hashp->new_file = 0; X return (0); X} X X/* X * Returns: X * 0 == OK X * -1 indicates that errno should be set X */ Xstatic int Xflush_meta(hashp) X HTAB *hashp; X{ X HASHHDR *whdrp; X#if BYTE_ORDER == LITTLE_ENDIAN X HASHHDR whdr; X#endif X int fp, i, wsize; X X if (!hashp->save_file) X return (0); X hashp->MAGIC = HASHMAGIC; X hashp->VERSION = HASHVERSION; X hashp->H_CHARKEY = hashp->hash(CHARKEY, sizeof(CHARKEY)); X X fp = hashp->fp; X whdrp = &hashp->hdr; X#if BYTE_ORDER == LITTLE_ENDIAN X whdrp = &whdr; X swap_header_copy(&hashp->hdr, whdrp); X#endif X if ((lseek(fp, (off_t)0, SEEK_SET) == -1) || X ((wsize = write(fp, whdrp, sizeof(HASHHDR))) == -1)) X return (-1); X else X if (wsize != sizeof(HASHHDR)) { X errno = EFTYPE; X hashp->errno = errno; X return (-1); X } X for (i = 0; i < NCACHED; i++) X if (hashp->mapp[i]) X if (__put_page(hashp, (char *)hashp->mapp[i], X hashp->BITMAPS[i], 0, 1)) X return (-1); X return (0); X} X X/*******************************SEARCH ROUTINES *****************************/ X/* X * All the access routines return X * X * Returns: X * 0 on SUCCESS X * 1 to indicate an external ERROR (i.e. key not found, etc) X * -1 to indicate an internal ERROR (i.e. out of memory, etc) X */ Xstatic int Xhash_get(dbp, key, data, flag) X const DB *dbp; X const DBT *key; X DBT *data; X u_int flag; X{ X HTAB *hashp; X X hashp = (HTAB *)dbp->internal; X if (flag) { X hashp->errno = errno = EINVAL; X return (ERROR); X } X return (hash_access(hashp, HASH_GET, (DBT *)key, data)); X} X Xstatic int Xhash_put(dbp, key, data, flag) X const DB *dbp; X DBT *key; X const DBT *data; X u_int flag; X{ X HTAB *hashp; X X hashp = (HTAB *)dbp->internal; X if (flag && flag != R_NOOVERWRITE) { X hashp->errno = errno = EINVAL; X return (ERROR); X } X if ((hashp->flags & O_ACCMODE) == O_RDONLY) { X hashp->errno = errno = EPERM; X return (ERROR); X } X return (hash_access(hashp, flag == R_NOOVERWRITE ? X HASH_PUTNEW : HASH_PUT, (DBT *)key, (DBT *)data)); X} X Xstatic int Xhash_delete(dbp, key, flag) X const DB *dbp; X const DBT *key; X u_int flag; /* Ignored */ X{ X HTAB *hashp; X X hashp = (HTAB *)dbp->internal; X if (flag && flag != R_CURSOR) { X hashp->errno = errno = EINVAL; X return (ERROR); X } X if ((hashp->flags & O_ACCMODE) == O_RDONLY) { X hashp->errno = errno = EPERM; X return (ERROR); X } X return (hash_access(hashp, HASH_DELETE, (DBT *)key, NULL)); X} X X/* X * Assume that hashp has been set in wrapper routine. X */ Xstatic int Xhash_access(hashp, action, key, val) X HTAB *hashp; X ACTION action; X DBT *key, *val; X{ X register BUFHEAD *rbufp; X BUFHEAD *bufp, *save_bufp; X register u_short *bp; X register int n, ndx, off, size; X register char *kp; X u_short pageno; X X#ifdef HASH_STATISTICS X hash_accesses++; X#endif X X off = hashp->BSIZE; X size = key->size; X kp = (char *)key->data; X rbufp = __get_buf(hashp, __call_hash(hashp, kp, size), NULL, 0); X if (!rbufp) X return (ERROR); X save_bufp = rbufp; X X /* Pin the bucket chain */ X rbufp->flags |= BUF_PIN; X for (bp = (u_short *)rbufp->page, n = *bp++, ndx = 1; ndx < n;) X if (bp[1] >= REAL_KEY) { X /* Real key/data pair */ X if (size == off - *bp && X memcmp(kp, rbufp->page + *bp, size) == 0) X goto found; X off = bp[1]; X#ifdef HASH_STATISTICS X hash_collisions++; X#endif X bp += 2; X ndx += 2; X } else if (bp[1] == OVFLPAGE) { X rbufp = __get_buf(hashp, *bp, rbufp, 0); X if (!rbufp) { X save_bufp->flags &= ~BUF_PIN; X return (ERROR); X } X /* FOR LOOP INIT */ X bp = (u_short *)rbufp->page; X n = *bp++; X ndx = 1; X off = hashp->BSIZE; X } else if (bp[1] < REAL_KEY) { X if ((ndx = X __find_bigpair(hashp, rbufp, ndx, kp, size)) > 0) X goto found; X if (ndx == -2) { X bufp = rbufp; X if (!(pageno = X __find_last_page(hashp, &bufp))) { X ndx = 0; X rbufp = bufp; X break; /* FOR */ X } X rbufp = __get_buf(hashp, pageno, bufp, 0); X if (!rbufp) { X save_bufp->flags &= ~BUF_PIN; X return (ERROR); X } X /* FOR LOOP INIT */ X bp = (u_short *)rbufp->page; X n = *bp++; X ndx = 1; X off = hashp->BSIZE; X } else { X save_bufp->flags &= ~BUF_PIN; X return (ERROR); X } X } X X /* Not found */ X switch (action) { X case HASH_PUT: X case HASH_PUTNEW: X if (__addel(hashp, rbufp, key, val)) { X save_bufp->flags &= ~BUF_PIN; X return (ERROR); X } else { X save_bufp->flags &= ~BUF_PIN; X return (SUCCESS); X } X case HASH_GET: X case HASH_DELETE: X default: X save_bufp->flags &= ~BUF_PIN; X return (ABNORMAL); X } X Xfound: X switch (action) { X case HASH_PUTNEW: X save_bufp->flags &= ~BUF_PIN; X return (ABNORMAL); X case HASH_GET: X bp = (u_short *)rbufp->page; X if (bp[ndx + 1] < REAL_KEY) { X if (__big_return(hashp, rbufp, ndx, val, 0)) X return (ERROR); X } else { X val->data = (u_char *)rbufp->page + (int)bp[ndx + 1]; X val->size = bp[ndx] - bp[ndx + 1]; X } X break; X case HASH_PUT: X if ((__delpair(hashp, rbufp, ndx)) || X (__addel(hashp, rbufp, key, val))) { X save_bufp->flags &= ~BUF_PIN; X return (ERROR); X } X break; X case HASH_DELETE: X if (__delpair(hashp, rbufp, ndx)) X return (ERROR); X break; X default: X abort(); X } X save_bufp->flags &= ~BUF_PIN; X return (SUCCESS); X} X Xstatic int Xhash_seq(dbp, key, data, flag) X const DB *dbp; X DBT *key, *data; X u_int flag; X{ X register u_int bucket; X register BUFHEAD *bufp; X HTAB *hashp; X u_short *bp, ndx; X X hashp = (HTAB *)dbp->internal; X if (flag && flag != R_FIRST && flag != R_NEXT) { X hashp->errno = errno = EINVAL; X return (ERROR); X } X#ifdef HASH_STATISTICS X hash_accesses++; X#endif X if ((hashp->cbucket < 0) || (flag == R_FIRST)) { X hashp->cbucket = 0; X hashp->cndx = 1; X hashp->cpage = NULL; X } X X for (bp = NULL; !bp || !bp[0]; ) { X if (!(bufp = hashp->cpage)) { X for (bucket = hashp->cbucket; X bucket <= hashp->MAX_BUCKET; X bucket++, hashp->cndx = 1) { X bufp = __get_buf(hashp, bucket, NULL, 0); X if (!bufp) X return (ERROR); X hashp->cpage = bufp; X bp = (u_short *)bufp->page; X if (bp[0]) X break; X } X hashp->cbucket = bucket; X if (hashp->cbucket > hashp->MAX_BUCKET) { X hashp->cbucket = -1; X return (ABNORMAL); X } X } else X bp = (u_short *)hashp->cpage->page; X X#ifdef DEBUG X assert(bp); X assert(bufp); X#endif X while (bp[hashp->cndx + 1] == OVFLPAGE) { X bufp = hashp->cpage = X __get_buf(hashp, bp[hashp->cndx], bufp, 0); X if (!bufp) X return (ERROR); X bp = (u_short *)(bufp->page); X hashp->cndx = 1; X } X if (!bp[0]) { X hashp->cpage = NULL; X ++hashp->cbucket; X } X } X ndx = hashp->cndx; X if (bp[ndx + 1] < REAL_KEY) { X if (__big_keydata(hashp, bufp, key, data, 1)) X return (ERROR); X } else { X key->data = (u_char *)hashp->cpage->page + bp[ndx]; X key->size = (ndx > 1 ? bp[ndx - 1] : hashp->BSIZE) - bp[ndx]; X data->data = (u_char *)hashp->cpage->page + bp[ndx + 1]; X data->size = bp[ndx] - bp[ndx + 1]; X ndx += 2; X if (ndx > bp[0]) { X hashp->cpage = NULL; X hashp->cbucket++; X hashp->cndx = 1; X } else X hashp->cndx = ndx; X } X return (SUCCESS); X} X X/********************************* UTILITIES ************************/ X X/* X * Returns: X * 0 ==> OK X * -1 ==> Error X */ Xextern int X__expand_table(hashp) X HTAB *hashp; X{ X u_int old_bucket, new_bucket; X int dirsize, new_segnum, spare_ndx; X X#ifdef HASH_STATISTICS X hash_expansions++; X#endif X new_bucket = ++hashp->MAX_BUCKET; X old_bucket = (hashp->MAX_BUCKET & hashp->LOW_MASK); X X new_segnum = new_bucket >> hashp->SSHIFT; X X /* Check if we need a new segment */ X if (new_segnum >= hashp->nsegs) { X /* Check if we need to expand directory */ X if (new_segnum >= hashp->DSIZE) { X /* Reallocate directory */ X dirsize = hashp->DSIZE * sizeof(SEGMENT *); X if (!hash_realloc(&hashp->dir, dirsize, dirsize << 1)) X return (-1); X hashp->DSIZE = dirsize << 1; X } X if (!(hashp->dir[new_segnum] = X calloc(hashp->SGSIZE, sizeof(SEGMENT)))) X return (-1); X hashp->exsegs++; X hashp->nsegs++; X } X /* X * If the split point is increasing (MAX_BUCKET's log base 2 X * * increases), we need to copy the current contents of the spare X * split bucket to the next bucket. X */ X spare_ndx = __log2(hashp->MAX_BUCKET + 1); X if (spare_ndx > hashp->OVFL_POINT) { X hashp->SPARES[spare_ndx] = hashp->SPARES[hashp->OVFL_POINT]; X hashp->OVFL_POINT = spare_ndx; X } X X if (new_bucket > hashp->HIGH_MASK) { X /* Starting a new doubling */ X hashp->LOW_MASK = hashp->HIGH_MASK; X hashp->HIGH_MASK = new_bucket | hashp->LOW_MASK; X } X /* Relocate records to the new bucket */ X return (__split_page(hashp, old_bucket, new_bucket)); X} X X/* X * If realloc guarantees that the pointer is not destroyed if the realloc X * fails, then this routine can go away. X */ Xstatic void * Xhash_realloc(p_ptr, oldsize, newsize) X SEGMENT **p_ptr; X int oldsize, newsize; X{ X register void *p; X X if (p = malloc(newsize)) { X memmove(p, *p_ptr, oldsize); X memset(p + oldsize, 0, newsize - oldsize); X free(*p_ptr); X *p_ptr = p; X } X return (p); X} X Xextern u_int X__call_hash(hashp, k, len) X HTAB *hashp; X char *k; X int len; X{ X int n, bucket; X X n = hashp->hash(k, len); X bucket = n & hashp->HIGH_MASK; X if (bucket > hashp->MAX_BUCKET) X bucket = bucket & hashp->LOW_MASK; X return (bucket); X} X X/* X * Allocate segment table. On error, destroy the table and set errno. X * X * Returns 0 on success X */ Xstatic int Xalloc_segs(hashp, nsegs) X HTAB *hashp; X int nsegs; X{ X register int i; X register SEGMENT store; X X int save_errno; X X if (!(hashp->dir = calloc(hashp->DSIZE, sizeof(SEGMENT *)))) { X save_errno = errno; X (void)hdestroy(hashp); X errno = save_errno; X return (-1); X } X /* Allocate segments */ X store = calloc(nsegs << hashp->SSHIFT, sizeof(SEGMENT)); X if (!store) { X save_errno = errno; X (void)hdestroy(hashp); X errno = save_errno; X return (-1); X } X for (i = 0; i < nsegs; i++, hashp->nsegs++) X hashp->dir[i] = &store[i << hashp->SSHIFT]; X return (0); X} X X#if BYTE_ORDER == LITTLE_ENDIAN X/* X * Hashp->hdr needs to be byteswapped. X */ Xstatic void Xswap_header_copy(srcp, destp) X HASHHDR *srcp, *destp; X{ X int i; X X BLSWAP_COPY(srcp->magic, destp->magic); X BLSWAP_COPY(srcp->version, destp->version); X BLSWAP_COPY(srcp->lorder, destp->lorder); X BLSWAP_COPY(srcp->bsize, destp->bsize); X BLSWAP_COPY(srcp->bshift, destp->bshift); X BLSWAP_COPY(srcp->dsize, destp->dsize); X BLSWAP_COPY(srcp->ssize, destp->ssize); X BLSWAP_COPY(srcp->sshift, destp->sshift); X BLSWAP_COPY(srcp->ovfl_point, destp->ovfl_point); X BLSWAP_COPY(srcp->last_freed, destp->last_freed); X BLSWAP_COPY(srcp->max_bucket, destp->max_bucket); X BLSWAP_COPY(srcp->high_mask, destp->high_mask); X BLSWAP_COPY(srcp->low_mask, destp->low_mask); X BLSWAP_COPY(srcp->ffactor, destp->ffactor); X BLSWAP_COPY(srcp->nkeys, destp->nkeys); X BLSWAP_COPY(srcp->hdrpages, destp->hdrpages); X BLSWAP_COPY(srcp->h_charkey, destp->h_charkey); X for (i = 0; i < NCACHED; i++) { X BLSWAP_COPY(srcp->spares[i], destp->spares[i]); X BSSWAP_COPY(srcp->bitmaps[i], destp->bitmaps[i]); X } X} X Xstatic void Xswap_header(hashp) X HTAB *hashp; X{ X HASHHDR *hdrp; X int i; X X hdrp = &hashp->hdr; X X BLSWAP(hdrp->magic); X BLSWAP(hdrp->version); X BLSWAP(hdrp->lorder); X BLSWAP(hdrp->bsize); X BLSWAP(hdrp->bshift); X BLSWAP(hdrp->dsize); X BLSWAP(hdrp->ssize); X BLSWAP(hdrp->sshift); X BLSWAP(hdrp->ovfl_point); X BLSWAP(hdrp->last_freed); X BLSWAP(hdrp->max_bucket); X BLSWAP(hdrp->high_mask); X BLSWAP(hdrp->low_mask); X BLSWAP(hdrp->ffactor); X BLSWAP(hdrp->nkeys); X BLSWAP(hdrp->hdrpages); X BLSWAP(hdrp->h_charkey); X for (i = 0; i < NCACHED; i++) { X BLSWAP(hdrp->spares[i]); X BSSWAP(hdrp->bitmaps[i]); X } X} X#endif END_OF_FILE if test 23885 -ne `wc -c <'hash/hash.c'`; then echo shar: \"'hash/hash.c'\" unpacked with wrong size! fi # end of 'hash/hash.c' fi if test -f 'hash/hash_page.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'hash/hash_page.c'\" else echo shar: Extracting \"'hash/hash_page.c'\" $23155 characters$ sed "s/^X//" >'hash/hash_page.c' <<'END_OF_FILE' X/*- X * Copyright (c) 1990, 1993 X * The Regents of the University of California. All rights reserved. X * X * This code is derived from software contributed to Berkeley by X * Margo Seltzer. X * X * Redistribution and use in source and binary forms, with or without X * modification, are permitted provided that the following conditions X * are met: X * 1. Redistributions of source code must retain the above copyright X * notice, this list of conditions and the following disclaimer. X * 2. Redistributions in binary form must reproduce the above copyright X * notice, this list of conditions and the following disclaimer in the X * documentation and/or other materials provided with the distribution. X * 3. All advertising materials mentioning features or use of this software X * must display the following acknowledgement: X * This product includes software developed by the University of X * California, Berkeley and its contributors. X * 4. Neither the name of the University nor the names of its contributors X * may be used to endorse or promote products derived from this software X * without specific prior written permission. X * X * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND X * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE X * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE X * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE X * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL X * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS X * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) X * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT X * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY X * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF X * SUCH DAMAGE. X */ X X#if defined(LIBC_SCCS) && !defined(lint) Xstatic char sccsid[] = "@(#)hash_page.c 8.1 (Berkeley) 6/6/93"; X#endif /* LIBC_SCCS and not lint */ X X/* X * PACKAGE: hashing X * X * DESCRIPTION: X * Page manipulation for hashing package. X * X * ROUTINES: X * X * External X * __get_page X * __add_ovflpage X * Internal X * overflow_page X * open_temp X */ X X#include <sys/types.h> X X#include <errno.h> X#include <fcntl.h> X#include <signal.h> X#include <stdio.h> X#include <stdlib.h> X#include <string.h> X#include <unistd.h> X#ifdef DEBUG X#include <assert.h> X#endif X X#include <db.h> X#include "hash.h" X#include "page.h" X#include "extern.h" X Xstatic u_long *fetch_bitmap __P((HTAB *, int)); Xstatic u_long first_free __P((u_long)); Xstatic int open_temp __P((HTAB *)); Xstatic u_short overflow_page __P((HTAB *)); Xstatic void putpair __P((char *, const DBT *, const DBT *)); Xstatic void squeeze_key __P((u_short *, const DBT *, const DBT *)); Xstatic int ugly_split X __P((HTAB *, u_int, BUFHEAD *, BUFHEAD *, int, int)); X X#define PAGE_INIT(P) { \ X ((u_short *)(P))[0] = 0; \ X ((u_short *)(P))[1] = hashp->BSIZE - 3 * sizeof(u_short); \ X ((u_short *)(P))[2] = hashp->BSIZE; \ X} X X/* X * This is called AFTER we have verified that there is room on the page for X * the pair (PAIRFITS has returned true) so we go right ahead and start moving X * stuff on. X */ Xstatic void Xputpair(p, key, val) X char *p; X const DBT *key, *val; X{ X register u_short *bp, n, off; X X bp = (u_short *)p; X X /* Enter the key first. */ X n = bp[0]; X X off = OFFSET(bp) - key->size; X memmove(p + off, key->data, key->size); X bp[++n] = off; X X /* Now the data. */ X off -= val->size; X memmove(p + off, val->data, val->size); X bp[++n] = off; X X /* Adjust page info. */ X bp[0] = n; X bp[n + 1] = off - ((n + 3) * sizeof(u_short)); X bp[n + 2] = off; X} X X/* X * Returns: X * 0 OK X * -1 error X */ Xextern int X__delpair(hashp, bufp, ndx) X HTAB *hashp; X BUFHEAD *bufp; X register int ndx; X{ X register u_short *bp, newoff; X register int n; X u_short pairlen; X X bp = (u_short *)bufp->page; X n = bp[0]; X X if (bp[ndx + 1] < REAL_KEY) X return (__big_delete(hashp, bufp)); X if (ndx != 1) X newoff = bp[ndx - 1]; X else X newoff = hashp->BSIZE; X pairlen = newoff - bp[ndx + 1]; X X if (ndx != (n - 1)) { X /* Hard Case -- need to shuffle keys */ X register int i; X register char *src = bufp->page + (int)OFFSET(bp); X register char *dst = src + (int)pairlen; X memmove(dst, src, bp[ndx + 1] - OFFSET(bp)); X X /* Now adjust the pointers */ X for (i = ndx + 2; i <= n; i += 2) { X if (bp[i + 1] == OVFLPAGE) { X bp[i - 2] = bp[i]; X bp[i - 1] = bp[i + 1]; X } else { X bp[i - 2] = bp[i] + pairlen; X bp[i - 1] = bp[i + 1] + pairlen; X } X } X } X /* Finally adjust the page data */ X bp[n] = OFFSET(bp) + pairlen; X bp[n - 1] = bp[n + 1] + pairlen + 2 * sizeof(u_short); X bp[0] = n - 2; X hashp->NKEYS--; X X bufp->flags |= BUF_MOD; X return (0); X} X/* X * Returns: X * 0 ==> OK X * -1 ==> Error X */ Xextern int X__split_page(hashp, obucket, nbucket) X HTAB *hashp; X u_int obucket, nbucket; X{ X register BUFHEAD *new_bufp, *old_bufp; X register u_short *ino; X register char *np; X DBT key, val; X int n, ndx, retval; X u_short copyto, diff, off, moved; X char *op; X X copyto = (u_short)hashp->BSIZE; X off = (u_short)hashp->BSIZE; X old_bufp = __get_buf(hashp, obucket, NULL, 0); X if (old_bufp == NULL) X return (-1); X new_bufp = __get_buf(hashp, nbucket, NULL, 0); X if (new_bufp == NULL) X return (-1); X X old_bufp->flags |= (BUF_MOD | BUF_PIN); X new_bufp->flags |= (BUF_MOD | BUF_PIN); X X ino = (u_short *)(op = old_bufp->page); X np = new_bufp->page; X X moved = 0; X X for (n = 1, ndx = 1; n < ino[0]; n += 2) { X if (ino[n + 1] < REAL_KEY) { X retval = ugly_split(hashp, obucket, old_bufp, new_bufp, X (int)copyto, (int)moved); X old_bufp->flags &= ~BUF_PIN; X new_bufp->flags &= ~BUF_PIN; X return (retval); X X } X key.data = (u_char *)op + ino[n]; X key.size = off - ino[n]; X X if (__call_hash(hashp, key.data, key.size) == obucket) { X /* Don't switch page */ X diff = copyto - off; X if (diff) { X copyto = ino[n + 1] + diff; X memmove(op + copyto, op + ino[n + 1], X off - ino[n + 1]); X ino[ndx] = copyto + ino[n] - ino[n + 1]; X ino[ndx + 1] = copyto; X } else X copyto = ino[n + 1]; X ndx += 2; X } else { X /* Switch page */ X val.data = (u_char *)op + ino[n + 1]; X val.size = ino[n] - ino[n + 1]; X putpair(np, &key, &val); X moved += 2; X } X X off = ino[n + 1]; X } X X /* Now clean up the page */ X ino[0] -= moved; X FREESPACE(ino) = copyto - sizeof(u_short) * (ino[0] + 3); X OFFSET(ino) = copyto; X X#ifdef DEBUG3 X (void)fprintf(stderr, "split %d/%d\n", X ((u_short *)np)[0] / 2, X ((u_short *)op)[0] / 2); X#endif X /* unpin both pages */ X old_bufp->flags &= ~BUF_PIN; X new_bufp->flags &= ~BUF_PIN; X return (0); X} X X/* X * Called when we encounter an overflow or big key/data page during split X * handling. This is special cased since we have to begin checking whether X * the key/data pairs fit on their respective pages and because we may need X * overflow pages for both the old and new pages. X * X * The first page might be a page with regular key/data pairs in which case X * we have a regular overflow condition and just need to go on to the next X * page or it might be a big key/data pair in which case we need to fix the X * big key/data pair. X * X * Returns: X * 0 ==> success X * -1 ==> failure X */ Xstatic int Xugly_split(hashp, obucket, old_bufp, new_bufp, copyto, moved) X HTAB *hashp; X u_int obucket; /* Same as __split_page. */ X BUFHEAD *old_bufp, *new_bufp; X int copyto; /* First byte on page which contains key/data values. */ X int moved; /* Number of pairs moved to new page. */ X{ X register BUFHEAD *bufp; /* Buffer header for ino */ X register u_short *ino; /* Page keys come off of */ X register u_short *np; /* New page */ X register u_short *op; /* Page keys go on to if they aren't moving */ X X BUFHEAD *last_bfp; /* Last buf header OVFL needing to be freed */ X DBT key, val; X SPLIT_RETURN ret; X u_short n, off, ov_addr, scopyto; X char *cino; /* Character value of ino */ X X bufp = old_bufp; X ino = (u_short *)old_bufp->page; X np = (u_short *)new_bufp->page; X op = (u_short *)old_bufp->page; X last_bfp = NULL; X scopyto = (u_short)copyto; /* ANSI */ X X n = ino[0] - 1; X while (n < ino[0]) { X if (ino[2] < REAL_KEY && ino[2] != OVFLPAGE) { X /* X * Ov_addr gets set before reaching this point; there's X * always an overflow page before a big key/data page. X */ X if (__big_split(hashp, old_bufp, X new_bufp, bufp, ov_addr, obucket, &ret)) X return (-1); X old_bufp = ret.oldp; X if (!old_bufp) X return (-1); X op = (u_short *)old_bufp->page; X new_bufp = ret.newp; X if (!new_bufp) X return (-1); X np = (u_short *)new_bufp->page; X bufp = ret.nextp; X if (!bufp) X return (0); X cino = (char *)bufp->page; X ino = (u_short *)cino; X last_bfp = ret.nextp; X } else if (ino[n + 1] == OVFLPAGE) { X ov_addr = ino[n]; X /* X * Fix up the old page -- the extra 2 are the fields X * which contained the overflow information. X */ X ino[0] -= (moved + 2); X FREESPACE(ino) = X scopyto - sizeof(u_short) * (ino[0] + 3); X OFFSET(ino) = scopyto; X X bufp = __get_buf(hashp, ov_addr, bufp, 0); X if (!bufp) X return (-1); X X ino = (u_short *)bufp->page; X n = 1; X scopyto = hashp->BSIZE; X moved = 0; X X if (last_bfp) X __free_ovflpage(hashp, last_bfp); X last_bfp = bufp; X } X /* Move regular sized pairs of there are any */ X off = hashp->BSIZE; X for (n = 1; (n < ino[0]) && (ino[n + 1] >= REAL_KEY); n += 2) { X cino = (char *)ino; X key.data = (u_char *)cino + ino[n]; X key.size = off - ino[n]; X val.data = (u_char *)cino + ino[n + 1]; X val.size = ino[n] - ino[n + 1]; X off = ino[n + 1]; X X if (__call_hash(hashp, key.data, key.size) == obucket) { X /* Keep on old page */ X if (PAIRFITS(op, (&key), (&val))) X putpair((char *)op, &key, &val); X else { X old_bufp = X __add_ovflpage(hashp, old_bufp); X if (!old_bufp) X return (-1); X op = (u_short *)old_bufp->page; X putpair((char *)op, &key, &val); X } X old_bufp->flags |= BUF_MOD; X } else { X /* Move to new page */ X if (PAIRFITS(np, (&key), (&val))) X putpair((char *)np, &key, &val); X else { X new_bufp = X __add_ovflpage(hashp, new_bufp); X if (!new_bufp) X return (-1); X np = (u_short *)new_bufp->page; X putpair((char *)np, &key, &val); X } X new_bufp->flags |= BUF_MOD; X } X } X } X if (last_bfp) X __free_ovflpage(hashp, last_bfp); X return (0); X} X X/* X * Add the given pair to the page X * X * Returns: X * 0 ==> OK X * 1 ==> failure X */ Xextern int X__addel(hashp, bufp, key, val) X HTAB *hashp; X BUFHEAD *bufp; X const DBT *key, *val; X{ X register u_short *bp, *sop; X int do_expand; X X bp = (u_short *)bufp->page; X do_expand = 0; X while (bp[0] && (bp[bp[0]] < REAL_KEY)) X /* Exception case */ X if (bp[2] < REAL_KEY && bp[bp[0]] != OVFLPAGE) { X /* This is a big-keydata pair */ X bufp = __add_ovflpage(hashp, bufp); X if (!bufp) X return (-1); X bp = (u_short *)bufp->page; X } else X /* Try to squeeze key on this page */ X if (FREESPACE(bp) > PAIRSIZE(key, val)) { X squeeze_key(bp, key, val); X return (0); X } else { X bufp = __get_buf(hashp, bp[bp[0] - 1], bufp, 0); X if (!bufp) X return (-1); X bp = (u_short *)bufp->page; X } X X if (PAIRFITS(bp, key, val)) X putpair(bufp->page, key, val); X else { X do_expand = 1; X bufp = __add_ovflpage(hashp, bufp); X if (!bufp) X return (-1); X sop = (u_short *)bufp->page; X X if (PAIRFITS(sop, key, val)) X putpair((char *)sop, key, val); X else X if (__big_insert(hashp, bufp, key, val)) X return (-1); X } X bufp->flags |= BUF_MOD; X /* X * If the average number of keys per bucket exceeds the fill factor, X * expand the table. X */ X hashp->NKEYS++; X if (do_expand || X (hashp->NKEYS / (hashp->MAX_BUCKET + 1) > hashp->FFACTOR)) X return (__expand_table(hashp)); X return (0); X} X X/* X * X * Returns: X * pointer on success X * NULL on error X */ Xextern BUFHEAD * X__add_ovflpage(hashp, bufp) X HTAB *hashp; X BUFHEAD *bufp; X{ X register u_short *sp; X u_short ndx, ovfl_num; X#ifdef DEBUG1 X int tmp1, tmp2; X#endif X sp = (u_short *)bufp->page; X X /* Check if we are dynamically determining the fill factor */ X if (hashp->FFACTOR == DEF_FFACTOR) { X hashp->FFACTOR = sp[0] >> 1; X if (hashp->FFACTOR < MIN_FFACTOR) X hashp->FFACTOR = MIN_FFACTOR; X } X bufp->flags |= BUF_MOD; X ovfl_num = overflow_page(hashp); X#ifdef DEBUG1 X tmp1 = bufp->addr; X tmp2 = bufp->ovfl ? bufp->ovfl->addr : 0; X#endif X if (!ovfl_num || !(bufp->ovfl = __get_buf(hashp, ovfl_num, bufp, 1))) X return (NULL); X bufp->ovfl->flags |= BUF_MOD; X#ifdef DEBUG1 X (void)fprintf(stderr, "ADDOVFLPAGE: %d->ovfl was %d is now %d\n", X tmp1, tmp2, bufp->ovfl->addr); X#endif X ndx = sp[0]; X /* X * Since a pair is allocated on a page only if there's room to add X * an overflow page, we know that the OVFL information will fit on X * the page. X */ X sp[ndx + 4] = OFFSET(sp); X sp[ndx + 3] = FREESPACE(sp) - OVFLSIZE; X sp[ndx + 1] = ovfl_num; X sp[ndx + 2] = OVFLPAGE; X sp[0] = ndx + 2; X#ifdef HASH_STATISTICS X hash_overflows++; X#endif X return (bufp->ovfl); X} X X/* X * Returns: X * 0 indicates SUCCESS X * -1 indicates FAILURE X */ Xextern int X__get_page(hashp, p, bucket, is_bucket, is_disk, is_bitmap) X HTAB *hashp; X char *p; X u_int bucket; X int is_bucket, is_disk, is_bitmap; X{ X register int fd, page, size; X int rsize; X u_short *bp; X X fd = hashp->fp; X size = hashp->BSIZE; X X if ((fd == -1) || !is_disk) { X PAGE_INIT(p); X return (0); X } X if (is_bucket) X page = BUCKET_TO_PAGE(bucket); X else X page = OADDR_TO_PAGE(bucket); X if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || X ((rsize = read(fd, p, size)) == -1)) X return (-1); X bp = (u_short *)p; X if (!rsize) X bp[0] = 0; /* We hit the EOF, so initialize a new page */ X else X if (rsize != size) { X errno = EFTYPE; X return (-1); X } X if (!is_bitmap && !bp[0]) { X PAGE_INIT(p); X } else X if (hashp->LORDER != BYTE_ORDER) { X register int i, max; X X if (is_bitmap) { X max = hashp->BSIZE >> 2; /* divide by 4 */ X for (i = 0; i < max; i++) X BLSWAP(((long *)p)[i]); X } else { X BSSWAP(bp[0]); X max = bp[0] + 2; X for (i = 1; i <= max; i++) X BSSWAP(bp[i]); X } X } X return (0); X} X X/* X * Write page p to disk X * X * Returns: X * 0 ==> OK X * -1 ==>failure X */ Xextern int X__put_page(hashp, p, bucket, is_bucket, is_bitmap) X HTAB *hashp; X char *p; X u_int bucket; X int is_bucket, is_bitmap; X{ X register int fd, page, size; X int wsize; X X size = hashp->BSIZE; X if ((hashp->fp == -1) && open_temp(hashp)) X return (-1); X fd = hashp->fp; X X if (hashp->LORDER != BYTE_ORDER) { X register int i; X register int max; X X if (is_bitmap) { X max = hashp->BSIZE >> 2; /* divide by 4 */ X for (i = 0; i < max; i++) X BLSWAP(((long *)p)[i]); X } else { X max = ((u_short *)p)[0] + 2; X for (i = 0; i <= max; i++) X BSSWAP(((u_short *)p)[i]); X } X } X if (is_bucket) X page = BUCKET_TO_PAGE(bucket); X else X page = OADDR_TO_PAGE(bucket); X if ((lseek(fd, (off_t)page << hashp->BSHIFT, SEEK_SET) == -1) || X ((wsize = write(fd, p, size)) == -1)) X /* Errno is set */ X return (-1); X if (wsize != size) { X errno = EFTYPE; X return (-1); X } X return (0); X} X X#define BYTE_MASK ((1 << INT_BYTE_SHIFT) -1) X/* X * Initialize a new bitmap page. Bitmap pages are left in memory X * once they are read in. X */ Xextern int X__init_bitmap(hashp, pnum, nbits, ndx) X HTAB *hashp; X int pnum, nbits, ndx; X{ X u_long *ip; X int clearbytes, clearints; X X if (!(ip = malloc(hashp->BSIZE))) X return (1); X hashp->nmaps++; X clearints = ((nbits - 1) >> INT_BYTE_SHIFT) + 1; X clearbytes = clearints << INT_TO_BYTE; X (void)memset((char *)ip, 0, clearbytes); X (void)memset(((char *)ip) + clearbytes, 0xFF, X hashp->BSIZE - clearbytes); X ip[clearints - 1] = ALL_SET << (nbits & BYTE_MASK); X SETBIT(ip, 0); X hashp->BITMAPS[ndx] = (u_short)pnum; X hashp->mapp[ndx] = ip; X return (0); X} X Xstatic u_long Xfirst_free(map) X u_long map; X{ X register u_long i, mask; X X mask = 0x1; X for (i = 0; i < BITS_PER_MAP; i++) { X if (!(mask & map)) X return (i); X mask = mask << 1; X } X return (i); X} X Xstatic u_short Xoverflow_page(hashp) X HTAB *hashp; X{ X register u_long *freep; X register int max_free, offset, splitnum; X u_short addr; X int bit, first_page, free_bit, free_page, i, in_use_bits, j; X#ifdef DEBUG2 X int tmp1, tmp2; X#endif X splitnum = hashp->OVFL_POINT; X max_free = hashp->SPARES[splitnum]; X X free_page = (max_free - 1) >> (hashp->BSHIFT + BYTE_SHIFT); X free_bit = (max_free - 1) & ((hashp->BSIZE << BYTE_SHIFT) - 1); X X /* Look through all the free maps to find the first free block */ X first_page = hashp->LAST_FREED >>(hashp->BSHIFT + BYTE_SHIFT); X for ( i = first_page; i <= free_page; i++ ) { X if (!(freep = (u_long *)hashp->mapp[i]) && X !(freep = fetch_bitmap(hashp, i))) X return (NULL); X if (i == free_page) X in_use_bits = free_bit; X else X in_use_bits = (hashp->BSIZE << BYTE_SHIFT) - 1; X X if (i == first_page) { X bit = hashp->LAST_FREED & X ((hashp->BSIZE << BYTE_SHIFT) - 1); X j = bit / BITS_PER_MAP; X bit = bit & ~(BITS_PER_MAP - 1); X } else { X bit = 0; X j = 0; X } X for (; bit <= in_use_bits; j++, bit += BITS_PER_MAP) X if (freep[j] != ALL_SET) X goto found; X } X X /* No Free Page Found */ X hashp->LAST_FREED = hashp->SPARES[splitnum]; X hashp->SPARES[splitnum]++; X offset = hashp->SPARES[splitnum] - X (splitnum ? hashp->SPARES[splitnum - 1] : 0); X X#define OVMSG "HASH: Out of overflow pages. Increase page size\n" X if (offset > SPLITMASK) { X if (++splitnum >= NCACHED) { X (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); X return (NULL); X } X hashp->OVFL_POINT = splitnum; X hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; X hashp->SPARES[splitnum-1]--; X offset = 1; X } X X /* Check if we need to allocate a new bitmap page */ X if (free_bit == (hashp->BSIZE << BYTE_SHIFT) - 1) { X free_page++; X if (free_page >= NCACHED) { X (void)write(STDERR_FILENO, OVMSG, sizeof(OVMSG) - 1); X return (NULL); X } X /* X * This is tricky. The 1 indicates that you want the new page X * allocated with 1 clear bit. Actually, you are going to X * allocate 2 pages from this map. The first is going to be X * the map page, the second is the overflow page we were X * looking for. The init_bitmap routine automatically, sets X * the first bit of itself to indicate that the bitmap itself X * is in use. We would explicitly set the second bit, but X * don't have to if we tell init_bitmap not to leave it clear X * in the first place. X */ X if (__init_bitmap(hashp, (int)OADDR_OF(splitnum, offset), X 1, free_page)) X return (NULL); X hashp->SPARES[splitnum]++; X#ifdef DEBUG2 X free_bit = 2; X#endif X offset++; X if (offset > SPLITMASK) { X if (++splitnum >= NCACHED) { X (void)write(STDERR_FILENO, OVMSG, X sizeof(OVMSG) - 1); X return (NULL); X } X hashp->OVFL_POINT = splitnum; X hashp->SPARES[splitnum] = hashp->SPARES[splitnum-1]; X hashp->SPARES[splitnum-1]--; X offset = 0; X } X } else { X /* X * Free_bit addresses the last used bit. Bump it to address X * the first available bit. X */ X free_bit++; X SETBIT(freep, free_bit); X } X X /* Calculate address of the new overflow page */ X addr = OADDR_OF(splitnum, offset); X#ifdef DEBUG2 X (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", X addr, free_bit, free_page); X#endif X return (addr); X Xfound: X bit = bit + first_free(freep[j]); X SETBIT(freep, bit); X#ifdef DEBUG2 X tmp1 = bit; X tmp2 = i; X#endif X /* X * Bits are addressed starting with 0, but overflow pages are addressed X * beginning at 1. Bit is a bit addressnumber, so we need to increment X * it to convert it to a page number. X */ X bit = 1 + bit + (i * (hashp->BSIZE << BYTE_SHIFT)); X if (bit >= hashp->LAST_FREED) X hashp->LAST_FREED = bit - 1; X X /* Calculate the split number for this page */ X for (i = 0; (i < splitnum) && (bit > hashp->SPARES[i]); i++); X offset = (i ? bit - hashp->SPARES[i - 1] : bit); X if (offset >= SPLITMASK) X return (NULL); /* Out of overflow pages */ X addr = OADDR_OF(i, offset); X#ifdef DEBUG2 X (void)fprintf(stderr, "OVERFLOW_PAGE: ADDR: %d BIT: %d PAGE %d\n", X addr, tmp1, tmp2); X#endif X X /* Allocate and return the overflow page */ X return (addr); X} X X/* X * Mark this overflow page as free. X */ Xextern void X__free_ovflpage(hashp, obufp) X HTAB *hashp; X BUFHEAD *obufp; X{ X register u_short addr; X u_long *freep; X int bit_address, free_page, free_bit; X u_short ndx; X X addr = obufp->addr; X#ifdef DEBUG1 X (void)fprintf(stderr, "Freeing %d\n", addr); X#endif X ndx = (((u_short)addr) >> SPLITSHIFT); X bit_address = X (ndx ? hashp->SPARES[ndx - 1] : 0) + (addr & SPLITMASK) - 1; X if (bit_address < hashp->LAST_FREED) X hashp->LAST_FREED = bit_address; X free_page = (bit_address >> (hashp->BSHIFT + BYTE_SHIFT)); X free_bit = bit_address & ((hashp->BSIZE << BYTE_SHIFT) - 1); X X if (!(freep = hashp->mapp[free_page])) X freep = fetch_bitmap(hashp, free_page); X#ifdef DEBUG X /* X * This had better never happen. It means we tried to read a bitmap X * that has already had overflow pages allocated off it, and we X * failed to read it from the file. X */ X if (!freep) X assert(0); X#endif X CLRBIT(freep, free_bit); X#ifdef DEBUG2 X (void)fprintf(stderr, "FREE_OVFLPAGE: ADDR: %d BIT: %d PAGE %d\n", X obufp->addr, free_bit, free_page); X#endif X __reclaim_buf(hashp, obufp); X} X X/* X * Returns: X * 0 success X * -1 failure X */ Xstatic int Xopen_temp(hashp) X HTAB *hashp; X{ X sigset_t set, oset; X static char namestr[] = "_hashXXXXXX"; X X /* Block signals; make sure file goes away at process exit. */ X (void)sigfillset(&set); X (void)sigprocmask(SIG_BLOCK, &set, &oset); X if ((hashp->fp = mkstemp(namestr)) != -1) { X (void)unlink(namestr); X (void)fcntl(hashp->fp, F_SETFD, 1); X } X (void)sigprocmask(SIG_SETMASK, &oset, (sigset_t *)NULL); X return (hashp->fp != -1 ? 0 : -1); X} X X/* X * We have to know that the key will fit, but the last entry on the page is X * an overflow pair, so we need to shift things. X */ Xstatic void Xsqueeze_key(sp, key, val) X u_short *sp; X const DBT *key, *val; X{ X register char *p; X u_short free_space, n, off, pageno; X X p = (char *)sp; X n = sp[0]; X free_space = FREESPACE(sp); X off = OFFSET(sp); X X pageno = sp[n - 1]; X off -= key->size; X sp[n - 1] = off; X memmove(p + off, key->data, key->size); X off -= val->size; X sp[n] = off; X memmove(p + off, val->data, val->size); X sp[0] = n + 2; X sp[n + 1] = pageno; X sp[n + 2] = OVFLPAGE; X FREESPACE(sp) = free_space - PAIRSIZE(key, val); X OFFSET(sp) = off; X} X Xstatic u_long * Xfetch_bitmap(hashp, ndx) X HTAB *hashp; X int ndx; X{ X if (ndx >= hashp->nmaps || X !(hashp->mapp[ndx] = malloc(hashp->BSIZE)) || X __get_page(hashp, (char *)hashp->mapp[ndx], X hashp->BITMAPS[ndx], 0, 1, 1)) X return (NULL); X return (hashp->mapp[ndx]); X} X X#ifdef DEBUG4 Xint Xprint_chain(addr) X int addr; X{ X BUFHEAD *bufp; X short *bp, oaddr; X X (void)fprintf(stderr, "%d ", addr); X bufp = __get_buf(hashp, addr, NULL, 0); X bp = (short *)bufp->page; X while (bp[0] && ((bp[bp[0]] == OVFLPAGE) || X ((bp[0] > 2) && bp[2] < REAL_KEY))) { X oaddr = bp[bp[0] - 1]; X (void)fprintf(stderr, "%d ", (int)oaddr); X bufp = __get_buf(hashp, (int)oaddr, bufp, 0); X bp = (short *)bufp->page; X } X (void)fprintf(stderr, "\n"); X} X#endif END_OF_FILE if test 23155 -ne `wc -c <'hash/hash_page.c'`; then echo shar: \"'hash/hash_page.c'\" unpacked with wrong size! fi # end of 'hash/hash_page.c' fi echo shar: End of archive 7 $of 9$. cp /dev/null ark7isdone MISSING="" for I in 1 2 3 4 5 6 7 8 9 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 9 archives. rm -f ark[1-9]isdone ark[1-9][0-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0