From 3afee57ff6dbdb1e07830f3e81c6d806952dece0 Mon Sep 17 00:00:00 2001 From: teodor Date: Mon, 14 Feb 2005 16:22:34 +0000 Subject: [PATCH] add TBTGetFirst/TBTGetLast methods --- expected/btree | 12 ++++++++++ tbtree.c | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++ tbtree.h | 3 +++ tbtreetest.c | 31 ++++++++++++++++++++++-- tests/btree | 1 + 5 files changed, 110 insertions(+), 2 deletions(-) diff --git a/expected/btree b/expected/btree index c359f66..3b04600 100644 --- a/expected/btree +++ b/expected/btree @@ -999,6 +999,8 @@ I 996 dyxa3q596u5mj3wfk8qebotg0oats5wbhcgiwoud5je2ortyjxbt429oqo4sl5hf7pxf8u12e3 I 997 5sphrrpkp6zogpqtuphdo2e7udw8b83l I 998 k83wbmalo9dk07nndjfrlmms1e9tajd25tok40hk820dnrwj050lzn4mu24jnub91d6qsakow7wyhech7x86nuxafgukqah1va18xocexviqtphjp3sg97n216p1cnjihbx0sck6oy63g1pblqk7dutekfoekmmd3mdrap99ga23qj707f6p0h273qg1yre835jztgkltn2ctrxk7617s8oz8bpeu3hhe69u1hyat76nh6ys2sblp7wvz2yy0xxw7lovg47lyovxro650z3oh5sgwj0qjxkdey9j9sgrzkbvmz8nlmff0nijxu7q1gf4z2mll I 999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl +0 9piyiad8wg6gibvnlj30oh81116zzyll5yrwj698pps7fgxs54azoopggtf8p7hxk9cf4q2lpehe7hginn17dhs1znnoqz39l5s2aea0cye8qjxmx1w8y3bt82f8scsp6rjycuyvsbx3rxkrslqjstcnsgwehfssjo7wgwt1tn9boh20f2jtsk3bs5m1ikwrmgxrhnpx3iikegjjvdq8p4qxrus1b343u4se9ceuomr2txb1dbrv7tv0a8mfu9ydoj5uk73ue78u7qdobhax080pamejri4str8wq1ieexn9xqun68n65bxt3rc715b58wdfi06pxzix04ns1dvqjvyomuxjqo1fpeijeeye +999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl Value: 'nynle4vpeonknahl5g74by29h61z9pgr6lw8sbv5s12hqv85w4rtgae4u3dxlir4mt1ki3s99lf9y1ouq3agl3otwqm0b33ff9ax1w0nzdenz1azlq8w' Not found sort -k2 -k3 data/btree.data | ./tbtreetest -c 10 -f temp/BTREE -b -S 1 @@ -2002,6 +2004,8 @@ I 996 dyxa3q596u5mj3wfk8qebotg0oats5wbhcgiwoud5je2ortyjxbt429oqo4sl5hf7pxf8u12e3 I 997 5sphrrpkp6zogpqtuphdo2e7udw8b83l I 998 k83wbmalo9dk07nndjfrlmms1e9tajd25tok40hk820dnrwj050lzn4mu24jnub91d6qsakow7wyhech7x86nuxafgukqah1va18xocexviqtphjp3sg97n216p1cnjihbx0sck6oy63g1pblqk7dutekfoekmmd3mdrap99ga23qj707f6p0h273qg1yre835jztgkltn2ctrxk7617s8oz8bpeu3hhe69u1hyat76nh6ys2sblp7wvz2yy0xxw7lovg47lyovxro650z3oh5sgwj0qjxkdey9j9sgrzkbvmz8nlmff0nijxu7q1gf4z2mll I 999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl +0 9piyiad8wg6gibvnlj30oh81116zzyll5yrwj698pps7fgxs54azoopggtf8p7hxk9cf4q2lpehe7hginn17dhs1znnoqz39l5s2aea0cye8qjxmx1w8y3bt82f8scsp6rjycuyvsbx3rxkrslqjstcnsgwehfssjo7wgwt1tn9boh20f2jtsk3bs5m1ikwrmgxrhnpx3iikegjjvdq8p4qxrus1b343u4se9ceuomr2txb1dbrv7tv0a8mfu9ydoj5uk73ue78u7qdobhax080pamejri4str8wq1ieexn9xqun68n65bxt3rc715b58wdfi06pxzix04ns1dvqjvyomuxjqo1fpeijeeye +999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl Value: 'nynle4vpeonknahl5g74by29h61z9pgr6lw8sbv5s12hqv85w4rtgae4u3dxlir4mt1ki3s99lf9y1ouq3agl3otwqm0b33ff9ax1w0nzdenz1azlq8w' Not found sort -k2 -k3 data/btree.data | ./tbtreetest -c 10 -f temp/BTREE -b -S 2 @@ -3005,6 +3009,8 @@ I 996 dyxa3q596u5mj3wfk8qebotg0oats5wbhcgiwoud5je2ortyjxbt429oqo4sl5hf7pxf8u12e3 I 997 5sphrrpkp6zogpqtuphdo2e7udw8b83l I 998 k83wbmalo9dk07nndjfrlmms1e9tajd25tok40hk820dnrwj050lzn4mu24jnub91d6qsakow7wyhech7x86nuxafgukqah1va18xocexviqtphjp3sg97n216p1cnjihbx0sck6oy63g1pblqk7dutekfoekmmd3mdrap99ga23qj707f6p0h273qg1yre835jztgkltn2ctrxk7617s8oz8bpeu3hhe69u1hyat76nh6ys2sblp7wvz2yy0xxw7lovg47lyovxro650z3oh5sgwj0qjxkdey9j9sgrzkbvmz8nlmff0nijxu7q1gf4z2mll I 999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl +0 9piyiad8wg6gibvnlj30oh81116zzyll5yrwj698pps7fgxs54azoopggtf8p7hxk9cf4q2lpehe7hginn17dhs1znnoqz39l5s2aea0cye8qjxmx1w8y3bt82f8scsp6rjycuyvsbx3rxkrslqjstcnsgwehfssjo7wgwt1tn9boh20f2jtsk3bs5m1ikwrmgxrhnpx3iikegjjvdq8p4qxrus1b343u4se9ceuomr2txb1dbrv7tv0a8mfu9ydoj5uk73ue78u7qdobhax080pamejri4str8wq1ieexn9xqun68n65bxt3rc715b58wdfi06pxzix04ns1dvqjvyomuxjqo1fpeijeeye +999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl Value: 'nynle4vpeonknahl5g74by29h61z9pgr6lw8sbv5s12hqv85w4rtgae4u3dxlir4mt1ki3s99lf9y1ouq3agl3otwqm0b33ff9ax1w0nzdenz1azlq8w' Not found cat data/btree.data | ./tbtreetest -c 10 -f temp/BTREE -b -S 0 -k @@ -4008,6 +4014,8 @@ I 996 dyxa3q596u5mj3wfk8qebotg0oats5wbhcgiwoud5je2ortyjxbt429oqo4sl5hf7pxf8u12e3 I 997 5sphrrpkp6zogpqtuphdo2e7udw8b83l I 998 k83wbmalo9dk07nndjfrlmms1e9tajd25tok40hk820dnrwj050lzn4mu24jnub91d6qsakow7wyhech7x86nuxafgukqah1va18xocexviqtphjp3sg97n216p1cnjihbx0sck6oy63g1pblqk7dutekfoekmmd3mdrap99ga23qj707f6p0h273qg1yre835jztgkltn2ctrxk7617s8oz8bpeu3hhe69u1hyat76nh6ys2sblp7wvz2yy0xxw7lovg47lyovxro650z3oh5sgwj0qjxkdey9j9sgrzkbvmz8nlmff0nijxu7q1gf4z2mll I 999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl +0 9piyiad8wg6gibvnlj30oh81116zzyll5yrwj698pps7fgxs54azoopggtf8p7hxk9cf4q2lpehe7hginn17dhs1znnoqz39l5s2aea0cye8qjxmx1w8y3bt82f8scsp6rjycuyvsbx3rxkrslqjstcnsgwehfssjo7wgwt1tn9boh20f2jtsk3bs5m1ikwrmgxrhnpx3iikegjjvdq8p4qxrus1b343u4se9ceuomr2txb1dbrv7tv0a8mfu9ydoj5uk73ue78u7qdobhax080pamejri4str8wq1ieexn9xqun68n65bxt3rc715b58wdfi06pxzix04ns1dvqjvyomuxjqo1fpeijeeye +999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl Value: 'nynle4vpeonknahl5g74by29h61z9pgr6lw8sbv5s12hqv85w4rtgae4u3dxlir4mt1ki3s99lf9y1ouq3agl3otwqm0b33ff9ax1w0nzdenz1azlq8w' Not found sort -k2n -k3 data/btree.data | ./tbtreetest -c 10 -f temp/BTREE -b -S 1 -k @@ -5011,6 +5019,8 @@ I 996 dyxa3q596u5mj3wfk8qebotg0oats5wbhcgiwoud5je2ortyjxbt429oqo4sl5hf7pxf8u12e3 I 997 5sphrrpkp6zogpqtuphdo2e7udw8b83l I 998 k83wbmalo9dk07nndjfrlmms1e9tajd25tok40hk820dnrwj050lzn4mu24jnub91d6qsakow7wyhech7x86nuxafgukqah1va18xocexviqtphjp3sg97n216p1cnjihbx0sck6oy63g1pblqk7dutekfoekmmd3mdrap99ga23qj707f6p0h273qg1yre835jztgkltn2ctrxk7617s8oz8bpeu3hhe69u1hyat76nh6ys2sblp7wvz2yy0xxw7lovg47lyovxro650z3oh5sgwj0qjxkdey9j9sgrzkbvmz8nlmff0nijxu7q1gf4z2mll I 999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl +0 9piyiad8wg6gibvnlj30oh81116zzyll5yrwj698pps7fgxs54azoopggtf8p7hxk9cf4q2lpehe7hginn17dhs1znnoqz39l5s2aea0cye8qjxmx1w8y3bt82f8scsp6rjycuyvsbx3rxkrslqjstcnsgwehfssjo7wgwt1tn9boh20f2jtsk3bs5m1ikwrmgxrhnpx3iikegjjvdq8p4qxrus1b343u4se9ceuomr2txb1dbrv7tv0a8mfu9ydoj5uk73ue78u7qdobhax080pamejri4str8wq1ieexn9xqun68n65bxt3rc715b58wdfi06pxzix04ns1dvqjvyomuxjqo1fpeijeeye +999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl Value: 'nynle4vpeonknahl5g74by29h61z9pgr6lw8sbv5s12hqv85w4rtgae4u3dxlir4mt1ki3s99lf9y1ouq3agl3otwqm0b33ff9ax1w0nzdenz1azlq8w' Not found sort -k2n -k3 data/btree.data | ./tbtreetest -c 10 -f temp/BTREE -b -S 2 -k @@ -6014,5 +6024,7 @@ I 996 dyxa3q596u5mj3wfk8qebotg0oats5wbhcgiwoud5je2ortyjxbt429oqo4sl5hf7pxf8u12e3 I 997 5sphrrpkp6zogpqtuphdo2e7udw8b83l I 998 k83wbmalo9dk07nndjfrlmms1e9tajd25tok40hk820dnrwj050lzn4mu24jnub91d6qsakow7wyhech7x86nuxafgukqah1va18xocexviqtphjp3sg97n216p1cnjihbx0sck6oy63g1pblqk7dutekfoekmmd3mdrap99ga23qj707f6p0h273qg1yre835jztgkltn2ctrxk7617s8oz8bpeu3hhe69u1hyat76nh6ys2sblp7wvz2yy0xxw7lovg47lyovxro650z3oh5sgwj0qjxkdey9j9sgrzkbvmz8nlmff0nijxu7q1gf4z2mll I 999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl +0 9piyiad8wg6gibvnlj30oh81116zzyll5yrwj698pps7fgxs54azoopggtf8p7hxk9cf4q2lpehe7hginn17dhs1znnoqz39l5s2aea0cye8qjxmx1w8y3bt82f8scsp6rjycuyvsbx3rxkrslqjstcnsgwehfssjo7wgwt1tn9boh20f2jtsk3bs5m1ikwrmgxrhnpx3iikegjjvdq8p4qxrus1b343u4se9ceuomr2txb1dbrv7tv0a8mfu9ydoj5uk73ue78u7qdobhax080pamejri4str8wq1ieexn9xqun68n65bxt3rc715b58wdfi06pxzix04ns1dvqjvyomuxjqo1fpeijeeye +999 wwwmt1nk5uubzv21es703r4ydddwa6cddek7oyfr2qu1e97tp3zw63vichms11bl4xhwyox7o2eam96g257eb91nf60rcrv5bk7pm7ygbnt3vhi4ar7fwew68jg9zj4b8y7rwkkmywk3ktc2b8xyhwq3k52wsqtnyq2v8nsr1psi47gka9vmhv977mfiy8718rd6otg94mcvwhrs4mko2hxnx9sm6b6p2ixhs94xbgin4ajej8ab3523or8x134804d22ys509lopgay2qoz6qszzormqdrjyhidw9uj8yyvz6is7hai6e1gaat2eiine5qzobjyoci27gl35phmsvxw7t3gshe4mzf9vpz55iw1cq06pgwxjcc3m5ijmmphoe4as3tc0v3cvi76w86l97abu8z7b42ssqvr3uto37p5zyycrqrkf4yz2n6g8eyme23697zup3w38ufjb79juzhfbsicfd17tlil51trl Value: 'nynle4vpeonknahl5g74by29h61z9pgr6lw8sbv5s12hqv85w4rtgae4u3dxlir4mt1ki3s99lf9y1ouq3agl3otwqm0b33ff9ax1w0nzdenz1azlq8w' Not found diff --git a/tbtree.c b/tbtree.c index 1096a94..b7bb757 100644 --- a/tbtree.c +++ b/tbtree.c @@ -1043,4 +1043,69 @@ TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value ) { return TBT_OK; } +int +TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value) { + TBTIterator iterator; + int rc; + + if ( (rc=TBTInitIterator(db, &iterator))!=TBT_OK ) + return rc; + + rc=TBTIterate(db, &iterator, key, value); + + TBTFreeIterator(db, &iterator); + + return rc; +} + +static int +findLast(TBTree *db, TBTValue *key, TBTValue *value, u_int32_t pagenumber) { + TBTMemPage *page; + TBTPointer *ptr; + int rc=TBT_OK,i; + + if ( (rc=TBTReadPage(db, pagenumber, &page)) != TBT_OK ) + return rc; + + if ( page->page.npointer==0 ) { + if ( !page->iscached ) + tfree(page); + return TBT_OK; + } + + page->islocked=1; + if ( page->page.isleaf ) { + ptr = (TBTPointer*)(page->page.data + db->pointersize * (page->page.npointer-1)); + if ( db->keylen ) { + key->length = db->keylen; + key->value = ptr->key.fixed.key; + } else { + key->length = ptr->key.varlen.length; + key->value = page->page.data + ptr->key.varlen.offset; + } + + value->length = ptr->pointer.leaf.length; + value->value = page->page.data + ptr->pointer.leaf.offset; + } else { + for(i=page->page.npointer-1; i>=0; i--) { + ptr = (TBTPointer*)( page->page.data + db->pointersize * i ); + rc = findLast(db, key, value, ptr->pointer.internal.link); + if ( rc!=TBT_OK || key->value ) + break; + } + } + + page->islocked=0; + if ( !page->iscached ) + tfree(page); + + return rc; +} + +int +TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value) { + memset(key, 0, sizeof(TBTValue)); + memset(value, 0, sizeof(TBTValue)); + return findLast(db, key, value, TBTPAGEROOT); +} diff --git a/tbtree.h b/tbtree.h index 083d34c..0df6381 100644 --- a/tbtree.h +++ b/tbtree.h @@ -156,4 +156,7 @@ int TBTIterate(TBTree *db, TBTIterator *iterator, TBTValue *key, TBTValue *value void TBTFreeIterator(TBTree *db, TBTIterator *iterator); +int TBTGetFirst(TBTree *db, TBTValue *key, TBTValue *value); +int TBTGetLast(TBTree *db, TBTValue *key, TBTValue *value); + #endif diff --git a/tbtreetest.c b/tbtreetest.c index cb5456e..124d733 100644 --- a/tbtreetest.c +++ b/tbtreetest.c @@ -41,7 +41,7 @@ static void usage() { puts( "Usage:\n" - "tbtreetest [ -c CACHESIZE ] [-r] [-k] [-f FILE] [-D | -L | -b | -i KEY -v VALUE [ -S strategynumber ] | -d KEY | -s KEY ] [-V] [-q]\n" + "tbtreetest [ -c CACHESIZE ] [-r] [-k] [-f FILE] [-D | -L | -z | -b | -i KEY -v VALUE [ -S strategynumber ] | -d KEY | -s KEY ] [-V] [-q]\n" "\t-c CACHESIZE - cache size in pages (default 0)\n" "\t-r - readonly mode\n" "\t-k - fixed size key (integer)\n" @@ -49,6 +49,7 @@ usage() { puts( "\t-D - dump data base\n" "\t-L - list all pairs (in bulk format)\n" + "\t-z - list first and last pairs\n" "\t-b - bulk operations from stdin in format (insert/delete/search):\n" "\t I KEY VALUE\n" "\t D KEY\n" @@ -72,6 +73,7 @@ extern int opterr; #define MODE_DUMP 4 #define MODE_LIST 5 #define MODE_BULK 6 +#define MODE_FL 7 static TBTValue K,V; @@ -127,7 +129,7 @@ main(int argn, char *argv[]) { memset(&db, 0, sizeof(TBTree)); - while((i=getopt(argn,argv,"qVbS:Dc:hrkf:i:v:d:s:L")) != EOF) { + while((i=getopt(argn,argv,"qVbS:Dc:hrkf:i:v:d:s:Lz")) != EOF) { switch(i) { case 'q': quietout=1; @@ -177,6 +179,9 @@ main(int argn, char *argv[]) { case 'b': mode=MODE_BULK; break; + case 'z': + mode=MODE_FL; + break; case 'h': default: usage(); @@ -237,6 +242,28 @@ main(int argn, char *argv[]) { } TBTFreeIterator(&db, &iterator); + } else if ( mode==MODE_FL ) { + TBTValue key, value; + rc = TBTGetFirst(&db, &key, &value); + if ( key.value ) { + if ( db.keylen ) + printf("%d", *(int*)(key.value)); + else + printLSTR(key.length, key.value); + fputc('\t', stdout); + printLSTR(value.length, value.value); + fputc('\n', stdout); + } + rc |= TBTGetLast(&db, &key, &value); + if ( key.value ) { + if ( db.keylen ) + printf("%d", *(int*)(key.value)); + else + printLSTR(key.length, key.value); + fputc('\t', stdout); + printLSTR(value.length, value.value); + fputc('\n', stdout); + } } else if ( mode==MODE_BULK ) { char buf[TBTREEPAGESIZE]; int tmp; diff --git a/tests/btree b/tests/btree index df18b14..e364e0b 100644 --- a/tests/btree +++ b/tests/btree @@ -9,6 +9,7 @@ do echo "$DATACAT | ./tbtreetest -c 10 -f temp/BTREE -b -S $STRATEGY $BTREEOPT" $DATACAT | ./tbtreetest -c 10 -f temp/BTREE -b -S $STRATEGY $BTREEOPT || exit 1 ./tbtreetest -c 10 -f temp/BTREE -S $STRATEGY $BTREEOPT -L || exit 1 + ./tbtreetest -c 10 -f temp/BTREE -S $STRATEGY $BTREEOPT -z || exit 1 ./tbtreetest -c 10 -f temp/BTREE -S $STRATEGY $BTREEOPT -s 542 || exit 1 ./tbtreetest -c 10 -f temp/BTREE -S $STRATEGY $BTREEOPT -d 542 || exit 1 ./tbtreetest -c 10 -f temp/BTREE -S $STRATEGY $BTREEOPT -s 542 || exit 1 -- 2.37.3