%PDF-1.3
%âãÏÓ
2 0 obj
<<
/Length 11558
>>
stream
BT
/TT2 1 Tf
22 0 0 22 156.125 713.75 Tm
0 g
/GS1 gs
-0.0002 Tc
0 Tw
[(A)-249.6(N)0.4(ew)-249(Hashing)-255(Package)-249.5(for)-251.8(UNIX)]TJ
/TT4 1 Tf
20 0 0 20 481.875 721.75 Tm
0 Tc
(1)Tj
/TT6 1 Tf
12 0 0 12 200.875 694.625 Tm
[(Margo)-250.7(Seltzer)]TJ
/TT7 1 Tf
5.9583 0 TD
<003c>Tj
/TT6 1 Tf
0.8021 0 TD
[(University)-257.5(of)-250.3(California,)-268.7(Berkeley)]TJ
-2.5104 -1 TD
[(Ozan)-254.7(Yigit)]TJ
/TT7 1 Tf
4.6771 0 TD
<003c>Tj
/TT6 1 Tf
0.8021 0 TD
[(York)-246.9(University)]TJ
/TT2 1 Tf
-2.1875 -2.1979 TD
(ABSTRACT)Tj
/TT6 1 Tf
10 0 0 10 144 639.25 Tm
[(UNIX)-413(support)-400(of)-404.5(disk)-395.5(oriented)-411.1(hashing)-401.7(was)-407.3(originally)-399.3(provided)-407.8(by)]TJ
/TT4 1 Tf
28.425 0 TD
(dbm)Tj
/TT6 1 Tf
2.1125 0 TD
[([ATT79])-402.6(and)]TJ
-30.5375 -1.1 TD
[(subsequently)-315.8(improved)-317.5(upon)-312.5(in)]TJ
/TT4 1 Tf
13.0875 0 TD
(ndbm)Tj
/TT6 1 Tf
2.5375 0 TD
[([BSD86].)-301.2(In)-304.5(AT&T)-303.3(System)-292.7(V,)-302.8(in-memory)-306.6(hashed)]TJ
-15.625 -1.1 TD
[(storage)-462.3(and)-456.2(access)-471.3(support)-450(was)-457.3(added)-462.3(in)-447.2(the)]TJ
/TT4 1 Tf
19.4875 0 TD
(hsearch)Tj
/TT6 1 Tf
3.6125 0 TD
[(library)-447(routines)-440.8([ATT85].)-702.6(The)]TJ
-23.1 -1.1 TD
[(result)-465.8(is)-458(a)-468.7(system)-459.7(with)-459.7(two)-462.5(incompatible)-466.8(hashing)-451.7(schemes,)-462.3(each)-468.5(with)-447.2(its)-442.7(own)-452.8(set)-451.7(of)]TJ
T*
(shortcomings.)Tj
0 -1.425 TD
[(This)-272.2(paper)-291.8(presents)-285.6(the)-278.3(design)-264.2(and)-268.7(performance)-297.8(characteristics)-293.7(of)-267(a)-268.7(new)-271.5(hashing)-264.2(package)]TJ
0 -1.1 TD
[(providing)-248.8(a)-256.1(superset)-260.6(of)-254.5(the)-253.3(functionality)-252.6(provided)-257.8(by)]TJ
/TT4 1 Tf
21.3625 0 TD
(dbm)Tj
/TT6 1 Tf
1.975 0 TD
(and)Tj
/TT4 1 Tf
1.7 0 TD
(hsearch)Tj
/TT6 1 Tf
3.175 0 TD
[(.)-500(The)-257.8(new)-259(package)]TJ
-28.2125 -1.1 TD
[(uses)-402.8(linear)-411.1(hashing)-401.7(to)-397.2(provide)-407.8(ef)]TJ
/TT8 1 Tf
13.7394 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(cient)-411.1(support)-387.5(of)-392(both)-384.7(memory)-392.5(based)-398.1(and)-393.7(disk)-383(based)]TJ
-14.2955 -1.1 TD
[(hash)-254.5(tables)-255(with)-247.2(performance)-285.3(superior)-260.6(to)-247.2(both)]TJ
/TT4 1 Tf
18.625 0 TD
(dbm)Tj
/TT6 1 Tf
1.975 0 TD
(and)Tj
/TT4 1 Tf
1.7 0 TD
(hsearch)Tj
/TT6 1 Tf
3.425 0 TD
[(under)-260.6(most)-242.7(conditions.)]TJ
/TT2 1 Tf
-22.875 -2.2 TD
(Introduction)Tj
/TT6 1 Tf
-6.1 -1.65 TD
[(Current)-745.3(UNIX)-750.5(systems)-733(offer)-757.1(two)-737.5(forms)-742(of)]TJ
-2.15 -1.1 TD
[(hashed)-385.6(data)-384.5(access.)]TJ
/TT4 1 Tf
8.6625 0 TD
(Dbm)Tj
/TT6 1 Tf
2.325 0 TD
[(and)-381.2(its)-367.7(derivatives)-375.3(provide)]TJ
-10.9875 -1.1 TD
[(keyed)-349.8(access)-346.3(to)-322.2(disk)-320.5(resident)-334.5(data)-334.5(while)]TJ
/TT4 1 Tf
16.775 0 TD
(hsearch)Tj
/TT6 1 Tf
3.5 0 TD
(pro-)Tj
-20.275 -1.1 TD
[(vides)-501.7(access)-521.3(for)-509(memory)-505(resident)-509.5(data.)-759.5(These)-512.3(two)]TJ
T*
[(access)-683.8(methods)-648.8(are)-666.8(incompatible)-654.3(in)-647.2(that)-650.5(memory)]TJ
T*
[(resident)-472(hash)-467(tables)-467.5(may)-453.3(not)-447.2(be)-456.2(stored)-456.2(on)-450(disk)-445.5(and)]TJ
T*
[(disk)-383(resident)-397(tables)-392.5(cannot)-397(be)-393.7(read)-404.3(into)-369.3(memory)-380(and)]TJ
T*
[(accessed)-277.4(using)-245.5(the)-253.3(in-memory)-256.6(routines.)]TJ
/TT4 1 Tf
2.15 -1.425 TD
(Dbm)Tj
/TT6 1 Tf
2.4875 0 TD
[(has)-542(several)-556(shortcomings.)-786.3(Since)-540.8(data)-534.5(is)]TJ
-4.6375 -1.1 TD
[(assumed)-456.2(to)-447.2(be)-456.2(disk)-445.5(resident,)-459.5(each)-468.5(access)-458.8(requires)-454.3(a)]TJ
T*
[(system)-259.7(call,)-269.1(and)-268.7(almost)-258.5(certainly,)-277(a)-256.2(disk)-245.5(operation.)-261.1(For)]TJ
T*
[(extremely)-402(large)-401.5(databases,)-406(where)-407.1(caching)-390.6(is)-370.5(unlikely)]TJ
T*
[(to)-347.2(be)-356.2(effective,)-377.9(this)-330.2(is)-333(acceptable,)-368.7(however,)-357.1(when)-346.5(the)]TJ
T*
[(database)-332.6(is)-308(small)-308.5(\(i.e.)-307.8(the)-303.3(password)]TJ
/TT8 1 Tf
14.7 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(le\),)-301.7(performance)]TJ
-15.2562 -1.1 TD
[(improvements)-328.8(can)-337.3(be)-318.7(obtained)-319.1(through)-314.2(caching)-328.1(pages)]TJ
T*
[(of)-392(the)-390.8(database)-407.6(in)-384.7(memory.)-630(In)-379.5(addition,)]TJ
/TT4 1 Tf
17.175 0 TD
(dbm)Tj
/TT6 1 Tf
2.1 0 TD
(cannot)Tj
-19.275 -1.1 TD
[(store)-331.2(data)-334.5(items)-321(whose)-332.3(total)-322.7(key)-331.2(and)-318.7(data)-322(size)-320.3(exceed)]TJ
T*
[(the)-403.3(page)-412.3(size)-407.8(of)-404.5(the)-403.3(hash)-404.5(table.)-656.6(Similarly,)-390.3(if)-401.7(two)-400(or)]TJ
T*
[(more)-282.8(keys)-279.5(produce)-291.8(the)-278.3(same)-282.8(hash)-279.5(value)-284.5(and)-268.7(their)-267.5(total)]TJ
T*
[(size)-395.3(exceeds)-410.4(the)-390.8(page)-399.8(size,)-395.3(the)-390.8(table)-394.1(cannot)-384.5(store)-381.2(all)]TJ
T*
[(the)-253.3(colliding)-244.8(keys.)]TJ
2.15 -1.425 TD
[(The)-420.3(in-memory)]TJ
/TT4 1 Tf
6.8375 0 TD
(hsearch)Tj
/TT6 1 Tf
3.575 0 TD
[(routines)-403.3(have)-412.3(different)]TJ
-12.5625 -1.1 TD
[(shortcomings.)-598.8(First,)-341(the)-353.3(notion)-344.3(of)-342(a)-343.7(single)-336.3(hash)-342(table)]TJ
T*
[(is)-420.5(embedded)-440.6(in)-409.7(the)-415.8(interface,)-440.4(preventing)-423.6(an)-418.7(applica-)]TJ
T*
[(tion)-719.3(from)-731.2(accessing)-743.5(multiple)-717(tables)-717.5(concurrently.)]TJ
T*
[(Secondly,)-315.8(the)-315.8(routine)-317.5(to)-309.7(create)-338.8(a)-318.7(hash)-317(table)-319.1(requires)-316.8(a)]TJ
T*
[(parameter)-327.9(which)-306.2(declares)-312.1(the)-290.8(size)-295.3(of)-292(the)-290.8(hash)-292(table.)-294.1(If)]TJ
T*
[(this)-255.2(size)-257.8(is)-245.5(set)-251.7(too)-247.2(low,)-250(performance)-285.3(degradation)-267.3(or)-254.5(the)]TJ
T*
[(inability)-267(to)-272.2(add)-281.2(items)-271(to)-272.2(the)-265.8(table)-269.1(may)-265.8(result.)-765.8(In)-267(addi-)]TJ
T*
(tion,)Tj
/TT4 1 Tf
2.375 0 TD
(hsearch)Tj
/TT6 1 Tf
3.75 0 TD
[(requires)-591.8(that)-575.5(the)-578.3(application)-569.6(allocate)]TJ
-6.125 -1.1 TD
[(memory)-630(for)-634(the)-628.3(key)-631.2(and)-631.2(data)-634.5(items.)-871(Lastly,)-625.5(the)]TJ
/TT4 1 Tf
T*
(hsearch)Tj
/TT6 1 Tf
3.6625 0 TD
[(routines)-490.8(provide)-495.3(no)-487.5(interface)-515.4(to)-484.7(store)-481.1(hash)]TJ
-3.6625 -1.1 TD
[(tables)-255(on)-250(disk.)]TJ
ET
0 G
1 J 0 j 0.25 w 10 M []0 d
1 i
90 92.875 m
198 92.875 l
S
BT
/TT4 1 Tf
8 0 0 8 95 86 Tm
(1)Tj
/TT6 1 Tf
9 0 0 9 99 82.875 Tm
[(UNIX)-250.5(is)-249.7(a)-250.6(registered)-252.1(trademark)-252.3(of)-250.3(AT&T.)]TJ
10 0 0 10 359.75 526 Tm
[(The)-370.3(goal)-365.8(of)-367(our)-367(work)-369.8(was)-369.8(to)-359.7(design)-364.2(and)-368.7(imple-)]TJ
-2.15 -1.1 TD
[(ment)-425.5(a)-431.2(new)-434(package)-449.6(that)-425.5(provides)-418.7(a)-418.7(superset)-423.1(of)-417(the)]TJ
T*
[(functionality)-365.1(of)-367(both)]TJ
/TT4 1 Tf
8.8125 0 TD
(dbm)Tj
/TT6 1 Tf
2.0875 0 TD
(and)Tj
/TT4 1 Tf
1.8125 0 TD
(hsearch)Tj
/TT6 1 Tf
3.175 0 TD
[(.)-600(The)-357.8(package)]TJ
-15.8875 -1.1 TD
[(had)-618.7(to)-609.7(overcome)-632.6(the)-615.8(interface)-640.4(shortcomings)-611.3(cited)]TJ
T*
[(above)-412.3(and)-406.2(its)-392.7(implementation)-398.6(had)-406.2(to)-397.2(provide)-407.8(perfor-)]TJ
T*
[(mance)-340.6(equal)-334.5(or)-329.5(superior)-335.6(to)-322.2(that)-325.5(of)-329.5(the)-328.3(existing)-308.5(imple-)]TJ
T*
[(mentations.)-936.8(In)-692(order)-690.1(to)-672.2(provide)-682.8(a)-681.2(compact)-687.8(disk)]TJ
T*
[(representation,)-560.9(graceful)-562.1(table)-531.6(growth,)-529.5(and)-531.2(expected)]TJ
T*
[(constant)-755(time)-735.2(performance,)-772.8(we)-746.5(selected)-754.8(Litwin’s)]TJ
T*
[(linear)-436.1(hashing)-426.7(algorithm)-424.3([LAR88,)-429.5(LIT80].)-687.3(We)-437.3(then)]TJ
T*
[(enhanced)-362.1(the)-328.3(algorithm)-324.3(to)-322.2(handle)-334.5(page)-337.3(over)]TJ
/TT8 1 Tf
18.0019 0 TD
(ß)Tj
/TT6 1 Tf
0.5562 0 TD
[(ows)-330.7(and)]TJ
-18.558 -1.1 TD
[(large)-426.5(key)-418.7(handling)-413(with)-409.7(a)-418.7(single)-411.3(mechanism,)-420.8(named)]TJ
T*
(buddy-in-waiting.)Tj
/TT2 1 Tf
3.3625 -1.925 TD
[(Existing)-236.5(UNIX)-256.8(Hashing)-230.4(Techniques)]TJ
/TT6 1 Tf
-1.2125 -1.65 TD
[(Over)-476(the)-453.3(last)-448.8(decade,)-474.6(several)-468.5(dynamic)-456.6(hashing)]TJ
-2.15 -1.1 TD
[(schemes)-287.3(have)-287.3(been)-287.3(developed)-290.6(for)-284(the)-278.3(UNIX)-288(timeshar-)]TJ
T*
[(ing)-597.2(system,)-597.2(starting)-588(with)-584.7(the)-590.8(inclusion)-583.5(of)]TJ
/TT4 1 Tf
18.9375 0 TD
(dbm)Tj
/TT6 1 Tf
1.725 0 TD
0.5875 Tc
(,a)Tj
-20.6625 -1.1 TD
0 Tc
[(minimal)-442(database)-470.1(library)-459.5(written)-455(by)-450(Ken)-459(Thompson)]TJ
T*
[([THOM90],)-577.1(in)-559.7(the)-565.8(Seventh)-565.8(Edition)-555.7(UNIX)-575.5(system.)]TJ
T*
[(Since)-403.3(then,)-403.3(an)-406.2(extended)-415.6(version)-406.2(of)-404.5(the)-390.8(same)-395.3(library,)]TJ
/TT4 1 Tf
T*
(ndbm)Tj
/TT6 1 Tf
2.225 0 TD
[(,)-362.5(and)-368.6(a)-356.2(public-domain)-355.5(clone)-359.5(of)-354.5(the)-353.3(latter,)]TJ
/TT4 1 Tf
17.3625 0 TD
(sdbm)Tj
/TT6 1 Tf
2.1125 0 TD
(,)Tj
-21.7 -1.1 TD
[(have)-562.3(been)-562.3(developed.)]TJ
9.8125 0 TD
0.0016 Tc
[(Another)-546.5(interface-compatible)]TJ
-9.8125 -1.1 TD
0 Tc
(library)Tj
/TT4 1 Tf
3.05 0 TD
(gdbm)Tj
/TT6 1 Tf
2.225 0 TD
[(,)-375(was)-382.3(recently)-392.3(made)-384.5(available)-378.6(as)-367(part)-370.3(of)]TJ
-5.275 -1.1 TD
[(the)-315.8(Free)-323.1(Software)-327.6(Foundation’s)-309.7(\(FSF\))-303(software)-319.6(distri-)]TJ
T*
(bution.)Tj
2.15 -1.425 TD
[(All)-459.7(of)-467(these)-470.3(implementations)-459.5(are)-479.3(based)-460.6(on)-450(the)]TJ
-2.15 -1.1 TD
[(idea)-397(of)-392(revealing)-404.8(just)-380.2(enough)-381.1(bits)-367.7(of)-379.5(a)-381.2(hash)-379.5(value)-384.5(to)]TJ
T*
[(locate)-287.8(a)-281.2(page)-274.8(in)-259.7(a)-268.7(single)-261.3(access.)-533.8(While)]TJ
/TT4 1 Tf
16.0125 0 TD
(dbm/ndbm)Tj
/TT6 1 Tf
4.4875 0 TD
(and)Tj
/TT4 1 Tf
-20.5 -1.1 TD
(sdbm)Tj
/TT6 1 Tf
2.525 0 TD
[(map)-415.8(the)-415.8(hash)-417(value)-422(directly)-408.3(to)-397.2(a)-406.2(disk)-395.5(address,)]TJ
/TT4 1 Tf
-2.525 -1.1 TD
(gdbm)Tj
/TT6 1 Tf
2.6875 0 TD
[(uses)-465.3(the)-465.8(hash)-454.5(value)-459.5(to)-447.2(index)-453.3(into)-444.3(a)]TJ
/TT4 1 Tf
15.5875 0 TD
(directory)Tj
/TT6 1 Tf
-18.275 -1.1 TD
[([ENB88])-259(containing)-253.8(disk)-245.5(addresses.)]TJ
2.15 -1.425 TD
(The)Tj
/TT4 1 Tf
1.9375 0 TD
(hsearch)Tj
/TT6 1 Tf
3.55 0 TD
[(routines)-378.3(in)-372.2(System)-367.7(V)-365.3(are)-379.3(designed)]TJ
-7.6375 -1.1 TD
[(to)-447.2(provide)-457.8(memory-resident)-468.9(hash)-454.5(tables.)-705(Since)-440.8(data)]TJ
T*
[(access)-471.3(does)-454.5(not)-447.2(require)-468.5(disk)-445.5(access,)-471.3(simple)-446(hashing)]TJ
T*
[(schemes)-412.3(which)-406.2(may)-403.3(require)-406(multiple)-379.5(probes)-396.5(into)-381.8(the)]TJ
T*
[(table)-344.1(are)-354.3(used.)-342(A)-340.3(more)-345.3(interesting)-341.3(version)-343.7(of)]TJ
/TT4 1 Tf
18.775 0 TD
(hsearch)Tj
/TT6 1 Tf
-18.775 -1.1 TD
[(is)-308(a)-318.6(public)-313(domain)-313(library,)]TJ
/TT4 1 Tf
11.1 0 TD
(dynahash)Tj
/TT6 1 Tf
3.8375 0 TD
[(,)-300(that)-300.5(implements)]TJ
-14.9375 -1.1 TD
[(Larson’s)-626(in-memory)-606.6(adaptation)-610([LAR88])-609(of)-604.5(linear)]TJ
T*
[(hashing)-251.7([LIT80].)]TJ
/TT2 1 Tf
-24.825 -4.075 TD
(USENIX)Tj
/TT7 1 Tf
4.025 0 TD
<003c>Tj
/TT2 1 Tf
0.8 0 TD
[(Winter)-257.8(’91)]TJ
/TT7 1 Tf
4.9 0 TD
<003c>Tj
/TT2 1 Tf
0.8 0 TD
[(Dallas,)-245.5(TX)]TJ
/TT6 1 Tf
35.775 0 TD
(1)Tj
ET
endstream
endobj
3 0 obj
<<
/ProcSet [/PDF /Text ]
/Font <<
/TT2 4 0 R
/TT4 5 0 R
/TT6 6 0 R
/TT7 7 0 R
/TT8 8 0 R
>>
/ExtGState <<
/GS1 9 0 R
>>
>>
endobj
12 0 obj
<<
/Length 15752
>>
stream
BT
/TT2 1 Tf
10 0 0 10 54 759.75 Tm
0 g
/GS1 gs
0 Tc
0 Tw
[(A)-252.8(New)-261.8(Hashing)-230.4(Package)-257.8(for)-260.6(UNIX)-25569.3(Seltzer)-270.1(&)-254.5(Yigit)]TJ
/TT4 1 Tf
8.025 -3.5 TD
(dbm)Tj
/TT6 1 Tf
1.975 0 TD
(and)Tj
/TT4 1 Tf
1.7 0 TD
(ndbm)Tj
/TT6 1 Tf
-9.55 -1.65 TD
(The)Tj
/TT4 1 Tf
1.95 0 TD
(dbm)Tj
/TT6 1 Tf
2.1 0 TD
(and)Tj
/TT4 1 Tf
1.825 0 TD
(ndbm)Tj
/TT6 1 Tf
2.6 0 TD
[(library)-384.5(implementations)-372(are)]TJ
-10.625 -1.1 TD
[(based)-660.6(on)-650(the)-653.3(same)-657.8(algorithm)-649.3(by)-650(Ken)-646.5(Thompson)]TJ
T*
[([THOM90,)-372.7(TOR88,)-362.5(WAL84],)-377.6(but)-347.2(differ)-366.8(in)-347.2(their)-355(pro-)]TJ
T*
[(grammatic)-336.6(interfaces.)-351.3(The)-332.8(latter)-333.3(is)-320.5(a)-331.2(modi)]TJ
/TT8 1 Tf
17.1932 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(ed)-306.8(version)]TJ
-17.7493 -1.1 TD
[(of)-429.5(the)-428.3(former)-441.8(which)-431.2(adds)-417(support)-412.5(for)-421.5(multiple)-404.5(data-)]TJ
T*
[(bases)-359(to)-347.2(be)-356.2(open)-343.7(concurrently.)-609.3(The)-345.3(discussion)-333(of)-342(the)]TJ
T*
[(algorithm)-386.8(that)-388(follows)-387.5(is)-383(applicable)-391.1(to)-372.2(both)]TJ
/TT4 1 Tf
18.4 0 TD
(dbm)Tj
/TT6 1 Tf
2.1 0 TD
(and)Tj
/TT4 1 Tf
-20.5 -1.1 TD
(ndbm)Tj
/TT6 1 Tf
2.225 0 TD
(.)Tj
-0.075 -1.425 TD
[(The)-395.3(basic)-395.3(structure)-401.5(of)]TJ
/TT4 1 Tf
9.525 0 TD
(dbm)Tj
/TT6 1 Tf
2.1125 0 TD
[(calls)-380(for)]TJ
/TT8 1 Tf
3.7625 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
(xed-sized)Tj
-18.1061 -1.1 TD
[(disk)-583(blocks)-589.2(\(buckets\))-604.3(and)-593.7(an)]TJ
/TT4 1 Tf
13.3375 0 TD
(access)Tj
/TT6 1 Tf
3.2 0 TD
[(function)-580(that)]TJ
-16.5375 -1.1 TD
[(maps)-276.7(a)-281.2(key)-281.2(to)-259.7(a)-268.7(bucket.)-522(The)-270.3(interface)-290.4(routines)-265.8(use)-267(the)]TJ
/TT4 1 Tf
T*
(access)Tj
/TT6 1 Tf
3.0125 0 TD
[(function)-380(to)-372.2(obtain)-375.5(the)-378.3(appropriate)-396.8(bucket)-384.5(in)-372.2(a)]TJ
-3.0125 -1.1 TD
[(single)-248.8(disk)-245.5(access.)]TJ
2.15 -1.425 TD
[(Within)-535.2(the)]TJ
/TT4 1 Tf
5.075 0 TD
(access)Tj
/TT6 1 Tf
3.1625 0 TD
[(function,)-542.5(a)-543.7(bit-randomizing)]TJ
-10.3875 -1.1 TD
[(hash)-392(function)]TJ
/TT4 1 Tf
8 0 0 8 109.625 550.875 Tm
(2)Tj
/TT6 1 Tf
10 0 0 10 117.5 547.75 Tm
[(is)-383(used)-392(to)-372.2(convert)-389(a)-381.2(key)-381.2(into)-369.3(a)-381.2(32-bit)]TJ
-6.35 -1.1 TD
[(hash)-329.5(value.)-334.5(Out)-325(of)-329.5(these)-320.3(32)-312.5(bits,)-305.2(only)-309.7(as)-317(many)-315.8(bits)-305.2(as)]TJ
T*
[(necessary)-375.8(are)-366.8(used)-354.5(to)-347.2(determine)-364.5(the)-340.8(particular)-356.4(bucket)]TJ
T*
[(on)-262.5(which)-268.7(a)-268.7(key)-268.7(resides.)-523.1(An)-265.3(in-memory)-269.1(bitmap)-260.2(is)-258(used)]TJ
T*
[(to)-484.7(determine)-502(how)-490.3(many)-490.8(bits)-480.2(are)-504.3(required.)-493.5(Each)-489(bit)]TJ
T*
[(indicates)-370.8(whether)-366.8(its)-342.7(associated)-365.6(bucket)-359.5(has)-354.5(been)-362.3(split)]TJ
T*
[(yet)-403.3(\(a)-410.6(0)-387.5(indicating)-388.5(that)-388(the)-390.8(bucket)-397(has)-392(not)-384.7(yet)-390.8(split\).)]TJ
T*
[(The)-420.3(use)-417(of)-417(the)-415.8(hash)-417(function)-417.5(and)-418.7(the)-403.3(bitmap)-397.7(is)-395.5(best)]TJ
T*
[(described)-381(by)-362.5(stepping)-348.8(through)-351.7(database)-370.1(creation)-367.3(with)]TJ
T*
[(multiple)-242(invocations)-252.1(of)-254.5(a)]TJ
/TT4 1 Tf
10.225 0 TD
(store)Tj
/TT6 1 Tf
2.25 0 TD
(operation.)Tj
-10.325 -1.425 TD
[(Initially,)-359(the)-365.8(hash)-367(table)-369.1(contains)-367.5(a)-368.7(single)-348.8(bucket)]TJ
-2.15 -1.1 TD
[(\(bucket)-489(0\),)-479.5(the)-478.3(bit)-469.3(map)-478.3(contains)-480(a)-481.2(single)-473.8(bit)-469.3(\(bit)-461.3(0)]TJ
T*
[(corresponding)-291.8(to)-272.2(bucket)-284.5(0\),)-279.5(and)-281.2(0)-275(bits)-517.7(of)-279.5(a)-281.2(hash)-267(value)]TJ
T*
[(are)-379.3(examined)-375.3(to)-359.7(determine)-377(where)-382.1(a)-368.7(key)-368.7(is)-358(placed)-378.1(\(in)]TJ
T*
[(bucket)-309.5(0\).)-554.5(When)-312.3(bucket)-309.5(0)-300(i)0(s)-295.5(full,)-298.8(its)-292.7(bit)-294.3(in)-297.2(the)-303.3(bitmap)]TJ
T*
[(\(bit)-261.3(0\))-267(is)-258(set,)-264.2(and)-268.7(its)-255.2(contents)-267.5(are)-279.3(split)-252.3(between)-268.5(buckets)]TJ
T*
[(0)-337.5(and)-331.2(1,)-325(by)-325(considering)-334.5(the)-328.3(0)]TJ
/TT4 1 Tf
7 0 0 7 174.625 372.5 Tm
(th)Tj
/TT6 1 Tf
10 0 0 10 185 368.5 Tm
[(bit)-319.3(\(the)-332.8(lowest)-326.7(bit)-319.3(not)]TJ
-13.1 -1.1 TD
[(previously)-378.3(examined\))-392.3(of)-379.5(the)-365.8(hash)-367(value)-372(for)-371.5(each)-381(key)]TJ
T*
[(within)-394.3(the)-403.3(bucket.)-409.5(Given)-406.2(a)-393.7(well-designed)-403.1(hash)-392(func-)]TJ
T*
[(tion,)-456.8(approximately)-461.6(half)-457.8(of)-454.5(the)-453.3(keys)-454.5(will)-444.3(have)-462.3(hash)]TJ
T*
[(values)-370.3(with)-359.7(the)-365.8(0)]TJ
/TT4 1 Tf
7 0 0 7 125.5 328.5 Tm
(th)Tj
/TT6 1 Tf
10 0 0 10 136.25 324.5 Tm
[(bit)-356.8(set.)-364.2(All)-347.2(such)-354.5(keys)-354.5(and)-356.2(associ-)]TJ
-8.225 -1.1 TD
[(ated)-259.5(data)-259.5(are)-266.8(moved)-253.3(to)-247.2(bucket)-259.5(1,)-250(and)-256.2(the)-253.3(rest)-256.2(remain)-261.1(in)]TJ
T*
[(bucket)-259.5(0.)]TJ
2.15 -1.425 TD
[(After)-390.1(this)-367.7(split,)-352.3(the)]TJ
/TT8 1 Tf
8.225 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(le)-359.7(now)-365.3(contains)-367.5(two)-362.5(buck-)]TJ
-10.9312 -1.1 TD
[(ets,)-264.2(and)-268.7(the)-265.8(bitmap)-260.2(contains)-267.5(three)-264(bits:)-239.8(the)-253.3(0)]TJ
/TT4 1 Tf
7 0 0 7 230.625 281.25 Tm
(th)Tj
/TT6 1 Tf
10 0 0 10 240.25 277.25 Tm
[(bit)-244.3(is)-245.5(set)]TJ
-18.625 -1.1 TD
[(to)-384.7(indicate)-397.5(a)-381.2(bucket)-384.5(0)-375(split)-364.8(when)-384(no)-375(bits)-367.7(of)-379.5(the)-378.3(hash)]TJ
T*
[(value)-534.5(are)-541.8(considered,)-543.5(and)-531.2(two)-525(more)-532.8(unset)-526.7(bits)-517.7(for)]TJ
T*
[(buckets)-370.3(0)-362.5(and)-368.7(1.)-612.5(The)-370.3(placement)-378.6(of)-367(an)-356.2(incoming)-347.7(key)]TJ
T*
[(now)-427.8(requires)-441.8(examination)-432.1(of)-429.5(the)-428.3(0)]TJ
/TT4 1 Tf
7 0 0 7 200 237.25 Tm
(th)Tj
/TT6 1 Tf
10 0 0 10 211.375 233.25 Tm
[(bit)-419.3(of)-429.5(the)-415.8(hash)]TJ
-15.7375 -1.1 TD
[(value,)-522(and)-518.7(the)-515.8(key)-506.2(is)-495.5(placed)-515.6(either)-511.1(in)-497.2(bucket)-509.5(0)-500(o)0(r)]TJ
T*
[(bucket)-359.5(1.)-600(If)-359(either)-361.1(bucket)-359.5(0)-350(o)0(r)-354.5(bucket)-359.5(1)]TJ
/TT8 1 Tf
16.975 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(lls)-336.5(up,)-337.5(it)-331.8(is)]TJ
-17.5312 -1.1 TD
[(split)-352.3(as)-354.5(before,)-371.3(its)-342.7(bit)-344.3(is)-345.5(set)-351.7(in)-347.2(the)-353.3(bitmap,)-347.7(and)-356.1(a)-356.2(new)]TJ
T*
[(set)-251.7(of)-254.5(unset)-251.7(bits)-242.7(are)-266.8(added)-262.3(to)-247.2(the)-253.3(bitmap.)]TJ
2.15 -1.425 TD
[(Each)-339(time)-322.7(we)-334(consider)-324.8(a)-318.7(new)-321.5(bit)-306.8(\(bit)-311.3(n\),)-317(we)-321.5(add)]TJ
-2.15 -1.1 TD
(2)Tj
/TT4 1 Tf
7 0 0 7 59 168 Tm
(n)Tj
/TT9 1 Tf
0.6607 0 TD
(+)Tj
/TT6 1 Tf
0.5536 0 TD
(1)Tj
10 0 0 10 74.375 164 Tm
[(bits)-330.2(to)-334.7(the)-340.8(bitmap)-322.7(and)-331.2(obtain)-325.5(2)]TJ
/TT4 1 Tf
7 0 0 7 200.875 168 Tm
(n)Tj
/TT9 1 Tf
0.6607 0 TD
(+)Tj
/TT6 1 Tf
0.5536 0 TD
(1)Tj
10 0 0 10 216.125 164 Tm
[(more)-332.8(address-)]TJ
-16.2125 -1.1 TD
[(able)-372(buckets)-370.3(in)-359.7(the)]TJ
/TT8 1 Tf
8.1875 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(le.)-609.7(As)-363.7(a)-368.7(result,)-365.8(the)-365.8(bitmap)-347.7(con-)]TJ
-8.7437 -1.1 TD
[(tains)-436.3(the)-440.8(previous)-443.7(2)]TJ
/TT4 1 Tf
7 0 0 7 137.75 146 Tm
(n)Tj
/TT9 1 Tf
0.6607 0 TD
(+)Tj
/TT6 1 Tf
0.5536 0 TD
(1)Tj
/TT7 1 Tf
10 0 0 10 149.75 142 Tm
<003c>Tj
/TT6 1 Tf
0.55 0 TD
[(1)-437.5(bits)-430.2(\(1)]TJ
/TT9 1 Tf
3.65 0 TD
(+)Tj
/TT6 1 Tf
0.55 0 TD
(2)Tj
/TT9 1 Tf
0.5 0 TD
(+)Tj
/TT6 1 Tf
0.55 0 TD
(4)Tj
/TT9 1 Tf
0.5 0 TD
(+)Tj
/TT6 1 Tf
0.55 0 TD
(...)Tj
/TT9 1 Tf
0.75 0 TD
(+)Tj
/TT6 1 Tf
0.55 0 TD
(2)Tj
/TT4 1 Tf
7 0 0 7 236.25 146 Tm
(n)Tj
/TT6 1 Tf
10 0 0 10 241.375 142 Tm
[(\))-429.5(which)]TJ
-18.7375 -1.1 TD
[(trace)-770.1(the)-753.3(entire)]TJ
/TT4 1 Tf
7.725 0 TD
[(split)-739.8(history)]TJ
/TT6 1 Tf
5.9875 0 TD
[(of)-754.5(the)-740.8(addressable)]TJ
ET
0 G
1 J 0 j 0.25 w 10 M []0 d
1 i
54 112.875 m
162 112.875 l
S
BT
/TT4 1 Tf
8 0 0 8 59 106 Tm
(2)Tj
/TT6 1 Tf
9 0 0 9 65.375 102.875 Tm
[(This)-263.8(bit-randomizing)-265.5(property)-265.1(is)-249.7(important)-250.7(to)-249.9(obtain)-250.5(radi-)]TJ
-1.2639 -1.1111 TD
[(cally)-376.1(different)-377.1(hash)-375.3(values)-375.9(for)-375.7(nearly)-376.5(identical)-362.7(keys,)-361.4(which)]TJ
T*
[(in)-249.9(turn)-250.3(avoids)-250.3(clustering)-251.1(of)-250.3(such)-250.3(keys)-250.3(in)-249.9(a)-250.6(single)-250.2(bucket.)]TJ
10 0 0 10 302.25 724.75 Tm
(buckets.)Tj
2.15 -1.425 TD
[(Given)-293.7(a)-293.7(key)-293.7(and)-293.7(the)-290.8(bitmap)-285.2(created)-313.8(by)-287.5(this)-280.2(algo-)]TJ
-2.15 -1.1 TD
[(rithm,)-333.5(we)]TJ
/TT8 1 Tf
4.2625 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(rst)-331.3(examine)-350.3(bit)-331.8(0)-325(o)0(f)-329.5(the)-328.3(bitmap)-322.7(\(the)-332.8(bit)-319.3(to)]TJ
-4.8187 -1.1 TD
[(consult)-298.8(when)-309(0)-287.5(bits)-280.2(of)-292(the)-290.8(hash)-292(value)-297(are)-304.3(being)-290.8(exam-)]TJ
T*
[(ined\).)-357.8(If)-359(it)-344.3(is)-345.5(set)-339.2(\(indicating)-343(that)-338(the)-340.8(bucket)-347(split\),)-331.8(we)]TJ
T*
[(begin)-265.8(considering)-272(the)-265.8(bits)-255.2(of)-267(the)-253.3(32-bit)-248.8(hash)-254.5(value.)-509.5(As)]TJ
T*
[(bit)-281.8(n)-275(i)0(s)-270.5(revealed,)-301.3(a)-281.2(mask)-276.7(equal)-284.5(to)-272.2(2)]TJ
/TT4 1 Tf
7 0 0 7 443.25 659.5 Tm
(n)Tj
/TT9 1 Tf
0.6607 0 TD
(+)Tj
/TT6 1 Tf
0.5536 0 TD
(1)Tj
/TT7 1 Tf
10 0 0 10 455.25 655.5 Tm
<003c>Tj
/TT6 1 Tf
0.55 0 TD
[(1)-275(will)-269.3(yield)-275.5(the)]TJ
-15.85 -1.1 TD
[(current)-381(bucket)-372(address.)-626(Adding)-350(2)]TJ
/TT4 1 Tf
7 0 0 7 442 648.5 Tm
(n)Tj
/TT9 1 Tf
0.6607 0 TD
(+)Tj
/TT6 1 Tf
0.5536 0 TD
(1)Tj
/TT7 1 Tf
10 0 0 10 454 644.5 Tm
<003c>Tj
/TT6 1 Tf
0.55 0 TD
[(1)-350(t)0(o)-347.2(the)-353.3(bucket)]TJ
-15.725 -1.1 TD
[(address)-538.5(identi)]TJ
/TT8 1 Tf
5.8148 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(es)-508.5(which)-518.7(bit)-506.8(in)-509.7(the)-515.8(bitmap)-510.2(must)-505.2(be)]TJ
-6.371 -1.1 TD
[(checked.)-537.1(We)-274.8(continue)-269.1(revealing)-279.8(bits)-242.7(of)-254.5(the)-253.3(hash)-254.5(value)]TJ
T*
[(until)-329(all)-338(set)-339.2(bits)-317.7(in)-322.2(the)-328.3(bitmap)-322.7(are)-341.8(exhausted.)-339(The)-332.8(fol-)]TJ
T*
[(lowing)-522.2(algorithm,)-524.3(a)-531.2(simpli)]TJ
/TT8 1 Tf
11.438 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(cation)-512.5(of)-529.5(the)-528.3(algorithm)]TJ
-11.9941 -1.1 TD
[(due)-393.7(to)-384.7(Ken)-396.5(Thompson)-384.7([THOM90,)-397.7(TOR88],)-392(uses)-377.8(the)]TJ
T*
[(hash)-754.5(value)-509.5(and)-506.1(the)-503.3(bitmap)-497.7(to)-497.2(calculate)-522.3(the)-490.8(bucket)]TJ
T*
[(address)-263.5(as)-254.5(discussed)-254.5(above.)]TJ
/TT11 1 Tf
8 0 0 8 302.25 530.125 Tm
-0.0049 Tc
[(hash)-573.3(=)-592.3(calchash\(key\);)]TJ
0 -1.375 TD
0 Tc
[(mask)-568.4(=)-587.4(0)0(;)]TJ
T*
(while)Tj
3.5625 0 TD
-0.0063 Tc
[(\(isbitset\(\(hash)-592.7(&)]TJ
10.6875 0 TD
0 Tc
[(mask\))-562(+)-587.4(mask\)\))]TJ
-9.75 -1.375 TD
[(mask)-568.4(=)-587.4(\(mask)-562(<<)-581.1(1\))-581.1(+)-587.4(1)0(;)]TJ
-4.5 -1.375 TD
[(bucket)-555.7(=)-587.4(hash)-568.4(&)-587.4(mask;)]TJ
/TT4 1 Tf
10 0 0 10 401.375 440.5 Tm
(sdbm)Tj
/TT6 1 Tf
-7.7625 -1.65 TD
(The)Tj
/TT4 1 Tf
1.85 0 TD
(sdbm)Tj
/TT6 1 Tf
2.4 0 TD
[(library)-297(is)-283(a)-293.7(public-domain)-280.5(clone)-284.5(of)-279.5(the)]TJ
/TT4 1 Tf
-6.4 -1.1 TD
(ndbm)Tj
/TT6 1 Tf
2.75 0 TD
[(library,)-534.5(developed)-540.6(by)-525(Ozan)-540.1(Yigit)-519.3(to)-509.7(provide)]TJ
/TT4 1 Tf
-2.75 -1.1 TD
(ndbm)Tj
/TT6 1 Tf
2.225 0 TD
[(’s)-477.8(functionality)-477.6(under)-473.1(some)-464.2(versions)-467(of)-467(UNIX)]TJ
-2.225 -1.1 TD
[(that)-263(exclude)-278.1(it)-244.3(for)-259(licensing)-252.1(reasons)-263.5([YIG89].)-269.1(The)-257.8(pro-)]TJ
T*
[(grammer)-353.1(interface,)-365.4(and)-343.6(the)-340.8(basic)-345.3(structure)-351.5(of)]TJ
/TT4 1 Tf
18.85 0 TD
(sdbm)Tj
/TT6 1 Tf
2.4375 0 TD
(is)Tj
-21.2875 -1.1 TD
[(identical)-494.6(to)]TJ
/TT4 1 Tf
5.2 0 TD
(ndbm)Tj
/TT6 1 Tf
2.7125 0 TD
[(but)-484.7(internal)-495.8(details)-477.1(of)-479.5(the)]TJ
/TT4 1 Tf
11.4125 0 TD
(access)Tj
/TT6 1 Tf
-19.325 -1.1 TD
[(function,)-267.5(such)-267(as)-267(the)-265.8(calculation)-275.8(of)-254.5(the)-253.3(bucket)-259.5(address,)]TJ
T*
[(and)-368.6(the)-365.8(use)-354.5(of)-354.5(different)-370.1(hash)-354.5(functions)-353.3(make)-359.5(the)-353.3(two)]TJ
T*
[(incompatible)-254.3(at)-253.3(the)-253.3(database)-270.1(level.)]TJ
2.15 -1.425 TD
(The)Tj
/TT4 1 Tf
1.875 0 TD
(sdbm)Tj
/TT6 1 Tf
2.425 0 TD
[(library)-322(is)-308(based)-310.6(on)-300(a)-306.2(simpli)]TJ
/TT8 1 Tf
11.1005 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(ed)-287(imple-)]TJ
-18.1066 -1.1 TD
[(mentation)-501(of)-504.5(Larson’s)-513.5(1978)]TJ
/TT4 1 Tf
12.35 0 TD
[(dynamic)-499.8(hashing)]TJ
/TT6 1 Tf
7.5375 0 TD
(algo-)Tj
-19.8875 -1.1 TD
[(rithm)-308.5(including)-310.2(the)]TJ
/TT4 1 Tf
8.1 0 TD
(re)Tj
/TT12 1 Tf
0.833 0 TD
(Þ)Tj
/TT4 1 Tf
0.5 0 TD
[(nements)-327.6(and)-300(variations)]TJ
/TT6 1 Tf
9.7545 0 TD
[(of)-304.5(sec-)]TJ
-19.1875 -1.1 TD
[(tion)-244.3(5)-250([LAR78].)-259(Larson’s)-263.5(original)-252.1(algorithm)-249.3(calls)-255(for)-259(a)]TJ
T*
[(forest)-435.6(of)-429.5(binary)-432.8(hash)-429.5(trees)-424.8(that)-413(are)-429.3(accessed)-439.9(by)-412.5(two)]TJ
T*
[(hash)-267(functions.)-265.8(The)]TJ
/TT8 1 Tf
8.1625 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(rst)-256.3(hash)-267(function)-267.5(selects)-272(a)-268.7(partic-)]TJ
-8.7187 -1.1 TD
[(ular)-357.8(tree)-364(within)-344.3(the)-353.3(forest.)-360.6(The)-357.8(second)-360.6(hash)-342(function,)]TJ
T*
[(which)-568.6(is)-558(required)-581(to)-559.7(be)-556.2(a)-556.2(boolean)-559.5(pseudo-random)]TJ
T*
[(number)-307.8(generator)-324.6(that)-300.5(is)-295.5(seeded)-316.8(by)-300(the)-303.3(key,)-306.2(is)-295.5(used)-292(to)]TJ
T*
[(traverse)-772.9(the)-740.8(tree)-751.5(until)-729(internal)-745.8(\(split\))-736.3(nodes)-742(are)]TJ
T*
[(exhausted)-314(and)-306.2(an)-306.2(external)-317.3(\(non-split\))-303.3(node)-293.7(is)-283(reached.)]TJ
T*
[(The)-357.8(bucket)-359.5(addresses)-368(are)-366.8(stored)-356.2(directly)-345.8(in)-334.7(the)-340.8(exter-)]TJ
T*
[(nal)-253.3(nodes.)]TJ
2.15 -1.425 TD
[(Larson’s)-413.5(re)]TJ
/TT8 1 Tf
4.6894 0 TD
(Þ)Tj
/TT6 1 Tf
0.5562 0 TD
[(nements)-409.5(are)-416.8(based)-410.6(on)-400(the)-403.3(observa-)]TJ
-7.3955 -1.1 TD
[(tion)-344.3(that)-350.5(the)-353.3(nodes)-354.5(can)-362.3(be)-356.1(represented)-379.1(by)-337.5(a)-343.7(single)-336.3(bit)]TJ
T*
[(that)-388(is)-383(set)-389.2(for)-396.5(internal)-395.8(nodes)-392(and)-393.7(not)-384.7(set)-376.7(for)-384(external)]TJ
T*
[(nodes,)-342(resulting)-338(in)-334.7(a)-343.6(radix)-345.3(search)-358.8(trie.)-580(Figure)-326.7(1)-325(illus-)]TJ
T*
[(trates)-372(this.)-592.7(Nodes)-357.3(A)-352.8(and)-356.2(B)-345.5(are)-366.8(internal)-358.3(\(split\))-348.8(nodes,)]TJ
T*
[(thus)-270.5(having)-278.3(no)-275(bucket)-284.5(addresses)-280.5(associated)-278.1(with)-259.7(them.)]TJ
T*
[(Instead,)-299.8(the)-290.8(external)-304.8(nodes)-292(\(C,)-287.5(D,)-290.3(and)-293.7(E\))-293.7(each)-293.5(need)-287.3(to)]TJ
T*
[(refer)-313.3(to)-284.7(a)-293.7(bucket)-297(address.)-551(These)-299.8(bucket)-297(addresses)-305.5(can)]TJ
T*
[(be)-443.7(stored)-443.6(in)-434.7(the)-440.8(trie)-442.5(itself)-438(where)-457.1(the)-428.3(subtries)-426.7(would)]TJ
/TT2 1 Tf
-24.825 -4.05 TD
[(2)-31225(USENIX)]TJ
/TT7 1 Tf
35.75 0 TD
<003c>Tj
/TT2 1 Tf
0.8 0 TD
[(Winter)-257.8(’91)]TJ
/TT7 1 Tf
4.9 0 TD
<003c>Tj
/TT2 1 Tf
0.8 0 TD
[(Dallas,)-245.5(TX)]TJ
ET
endstream
endobj
13 0 obj
<<
/ProcSet [/PDF /Text ]
/Font <<
/TT2 4 0 R
/TT4 5 0 R
/TT6 6 0 R
/TT7 7 0 R
/TT8 8 0 R
/TT9 14 0 R
/TT11 15 0 R
/TT12 16 0 R
>>
/ExtGState <<
/GS1 9 0 R
>>
>>
endobj
18 0 obj
<<
/Length 16475
>>
stream
BT
/TT2 1 Tf
10 0 0 10 90 759.75 Tm
0 g
/GS1 gs
0 Tc
0 Tw
[(Seltzer)-270.1(&)-254.5(Yigit)-25564.2(A)-252.8(New)-261.8(Hashing)-230.4(Package)-257.8(for)-260.6(UNIX)]TJ
/TT6 1 Tf
0 -3.5 TD
[(live)-275.5(if)-276.7(they)-265.8(existed)-267.5([KNU68].)-530(For)-260.8(example,)-275.3(if)-264.2(nodes)-267(F)]TJ
0 -1.1 TD
[(and)-281.2(G)-277.8(were)-294.6(the)-278.3(children)-286.1(of)-267(node)-268.7(C,)-258(the)-265.8(bucket)-272(address)]TJ
T*
[(L00)-464.2(could)-465.8(reside)-474.8(in)-459.7(the)-453.3(bits)-442.7(that)-450.5(will)-444.3(eventually)-460(be)]TJ
T*
[(used)-254.5(to)-247.2(store)-256.2(nodes)-254.5(F)-243.8(and)-256.2(G)-252.8(and)-256.2(all)-250.5(their)-255(children.)]TJ
/T1 1 Tf
T*
-0.0012 Tc
(
| 