Ben-Nes,
One problem with the nested set approach is that you have to make sure that the
root set of
each hierarchy has upper and lower bounds that do not overlap with those of any
other
root set. So, how to do that? Attached is sql that creates a table that tracks
what value
ranges have been used. It also allows one to return a range.
What I have yet to do is write the code that "reallocates" a root set's range,
which
would require getting all child nodes and adjusting their bounds .... but this
is not really
that hard since it is just adding/subtracting values to all their bounds.
Also included is a JUnit test class for testing the PL/pgsql procedures. One
test randomly
gets ranges of size <= int (the table type is bigint) and then randomly returns
the ranges
making sure all of the rows coalesce back to a single row.
Richard
package groups;
import java.sql.*;
import junit.textui.*;
import junit.framework.*;
import junit.extensions.*;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
/*
Copyright Richard Emberson
Use but remember me (copyright must appear in all copies).
*/
public class GroupLimits extends TestSetup {
static final String FILE = "group_limits.sql";
private static String[] args;
private static Connection conn;
private static final StringBuffer buf = new StringBuffer();
private static final String dropSQL = "DROP TABLE group_limits;";
private static final String deleteSQL = "DELETE FROM group_limits;";
private static final String countSQL = "SELECT count(*) FROM group_limits;";
private static final String loadSQL =
"INSERT INTO group_limits (lower_bound,size,upper_bound) VALUES (0,9223372036854775807,9223372036854775807);";
private static final long SUCCESS_INSERT = 1;
private static final long SUCCESS_UPDATE = 2;
private static final long STATUS_NEW_ROW = 1;
private static final long STATUS_LOWER = 2;
private static final long STATUS_HIGHER = 3;
private static final long STATUS_LOWER_AND_HIGHER = 4;
private static final long ERROR_NO_MORE_SEGMENTS = -1100011;
// lower_bound < lb_p AND upper_bound > lb_p
private static final long ERROR_LOWER_BOUND_BAD = -1100012;
// lower_bound < (lb_p+size_p) AND upper_bound > (lb_p+size_p);
private static final long ERROR_UPPER_BOUND_BAD = -1100013;
public static class Segment {
long lower;
long size;
Segment(long lower, long size) {
this.lower = lower;
this.size = size;
}
}
public static class Tests extends TestCase {
public Tests(String name) {
super(name);
}
public void testConnection() {
clearAndLoadTable(conn);
assert(conn != null);
checkNosOfRows(1);
}
/*
select group_limits_get(10);
select group_limits_return(0,10);
0-end
*/
public void testSimple1() {
clearAndLoadTable(conn);
Segment s = getSegment(10);
checkNosOfRows(1);
int status = returnSegement(s);
assert(status == STATUS_HIGHER);
}
/*
select group_limits_get(10);
select group_limits_get(10);
select group_limits_return(0,10);
0-10, 10,end
select group_limits_return(10,10);
0-end
*/
public void testSimple2() {
clearAndLoadTable(conn);
Segment s1 = getSegment(10);
Segment s2 = getSegment(10);
checkNosOfRows(1);
int status = returnSegement(s1);
assert(status == STATUS_NEW_ROW);
checkNosOfRows(2);
status = returnSegement(s2);
assert(status == STATUS_LOWER_AND_HIGHER);
checkNosOfRows(1);
}
/*
select group_limits_get(10);
select group_limits_get(10);
select group_limits_return(10,10);
10-end
select group_limits_return(0,10);
0-end
*/
public void testSimple3() {
clearAndLoadTable(conn);
Segment s1 = getSegment(10);
Segment s2 = getSegment(10);
checkNosOfRows(1);
int status = returnSegement(s2);
assert(status == STATUS_HIGHER);
checkNosOfRows(1);
status = returnSegement(s1);
assert(status == STATUS_HIGHER);
checkNosOfRows(1);
}
public void testBad1() {
clearAndLoadTable(conn);
Segment s1 = getSegment(10);
Segment s2 = getSegment(10);
int status = returnSegement(s1);
assert(status == STATUS_NEW_ROW);
// 0-10, 20-end
Segment sLowerBad = new Segment(5, 10);
status = returnSegement(sLowerBad);
assert(status == ERROR_LOWER_BOUND_BAD);
Segment sUpperBad = new Segment(15, 10);
status = returnSegement(sUpperBad);
assert(status == ERROR_UPPER_BOUND_BAD);
}
public void testHard1() {
clearAndLoadTable(conn);
int n = 100;
List l = new ArrayList();
Random r = new Random();
for (int i = 0; i < n; i++) {
int ri = r.nextInt();
if (ri == 0) {
continue;
}
if (ri < 0) {
ri = -ri;
}
//System.out.println("ri = "+ri);
Segment s = getSegment(ri);
l.add(s);
}
while (l.size() > 0) {
int index = r.nextInt();
if (index < 0) {
index = -index;
}
index = index % l.size();
Segment s = (Segment)l.remove(index);
returnSegement(s);
}
// and we get back to one row!!!
checkNosOfRows(1);
}
////////////////////////////////////////////////////////////////////////
private void checkNosOfRows(int n) {
int nosOfRows = countTable(conn);
assert(nosOfRows == n);
}
private Segment getSegment(long size) {
long lower = doGetQuery(size);
Segment s = new Segment(lower, size);
return s;
}
private long doGetQuery(long size) {
String query = makeGetQuery(size);
return execute(conn, query);
}
private String makeGetQuery(long size) {
buf.setLength(0);
buf.append("SELECT group_limits_get(");
buf.append(size);
buf.append(");");
return buf.toString();
}
private int returnSegement(Segment s) {
return (int)doReturnQuery(s.lower, s.size);
}
private long doReturnQuery(long lower, long size) {
String query = makeReturnQuery(lower, size);
return execute(conn, query);
}
private String makeReturnQuery(long lower, long size) {
buf.setLength(0);
buf.append("SELECT group_limits_return(");
buf.append(lower);
buf.append(",");
buf.append(size);
buf.append(");");
return buf.toString();
}
/*
////////////////////////////////////////////////////////////////////////
*/
private int countTable(Connection conn) {
return (int)execute(conn, countSQL);
}
private void clearAndLoadTable(Connection conn) {
clearTable(conn);
loadTable(conn);
}
private void clearTable(Connection conn) {
execute(conn, deleteSQL);
}
private void loadTable(Connection conn) {
execute(conn, loadSQL);
}
private long execute(Connection conn, String query) {
Statement st = null;
long result = -1;
try {
st = conn.createStatement();
if (st.execute(query)) {
// for pl/pgsql
ResultSet rs = st.getResultSet();
if (rs.next()) {
result = rs.getLong(1);
}
} else {
// for sql delete
result = st.getUpdateCount();
}
} catch (SQLException ex) {
ex.printStackTrace();
fail("Exception: " +ex);
} finally {
try {
st.close();
} catch (Exception ex) {}
}
return result;
}
}
public GroupLimits() {
super(new TestSuite(groups.GroupLimits.Tests.class));
}
protected void setUp() throws Exception {
String[] args = GroupLimits.args;
if (args == null) {
args = AllTests.args;
}
conn = AllTests.makeConnection(args);
System.out.println("Got connection");
AllTests.loadFile(GroupLimits.FILE);
}
protected void tearDown() throws Exception {
if (conn != null) {
AllTests.execute(conn, dropSQL);
System.out.println("Closing connection");
conn.close();
}
}
public static void main(String args[]) {
GroupLimits.args = args;
junit.textui.TestRunner.run(GroupLimits.class);
}
}
--------------------------------------------------------------------------------
-- Copyright Richard Emberson
-- Use but remember me (copyright must appear in all copies).
--------------------------------------------------------------------------------
--------------------------------------------------------------------------------
-- group limits table
-- keeps the available ranges of group bounds
-- starts from 0 to 9223372036854775807
-- hold negative in reserve
--------------------------------------------------------------------------------
DROP INDEX group_limits_lower_bound_index;
DROP INDEX group_limits_upper_bound_index;
DROP TABLE group_limits;
CREATE TABLE group_limits (
lower_bound BIGINT NOT NULL,
size BIGINT NOT NULL,
upper_bound BIGINT NOT NULL
);
CREATE INDEX group_limits_lower_bound_index ON group_limits (lower_bound);
CREATE INDEX group_limits_upper_bound_index ON group_limits (upper_bound);
--------------------------------------------------------------------------------
-- load initial values
INSERT INTO group_limits (
lower_bound,
size,
upper_bound
) VALUES (
0,
9223372036854775807,
9223372036854775807
);
--------------------------------------------------------------------------------
/*
Get a group range of the size specified by the input parameter.
This gets from the group_limits table the range from the row that
has the smallest range greater than size.
If it is equals to the size, the row is deleted.
If it is greater than the size, the row's range is adjusted.
input:
size
return:
if > 0 then it is the lower_bound of the segment
-1100011 - no more segments;
select group_limits_get(10);
select * from group_limits;
*/
CREATE OR REPLACE FUNCTION group_limits_get(BIGINT)
RETURNS BIGINT AS '
DECLARE
-- parameters
size_p ALIAS FOR $1;
-- variables
lb_v BIGINT;
ub_v BIGINT;
size_v BIGINT;
row_count_v INTEGER;
BEGIN
SELECT gl1.lower_bound, gl1.size, gl1.upper_bound INTO lb_v, size_v, ub_v
FROM group_limits gl1
WHERE gl1.size IN (SELECT MIN(gl2.size)
FROM group_limits gl2
WHERE gl2.size >= size_p);
IF size_v IS NULL THEN
-- some sort of fatal error
return -1100011;
ELSIF size_v = size_p THEN
-- exact match so remove the whole row
DELETE FROM group_limits WHERE lower_bound = lb_v;
ELSE
-- its bigger than needed so modify row
UPDATE group_limits
SET lower_bound = (lb_v+size_p), size = (size_v-size_p)
WHERE lower_bound = lb_v;
END IF;
GET DIAGNOSTICS row_count_v = ROW_COUNT;
IF row_count_v <> 1 THEN
RETURN -row_count_v;
END IF;
RETURN lb_v;
END; ' LANGUAGE 'plpgsql';
/*
Return a group range.
If a row exists such that the lb_p+size_p == lower_bound, then
modify the row. Also then check if there is another row
where its lower_bound+size == lb_p+size_p. If so, then coalesce
the two rows.
If no row exists such that lb_p+size_p == lower_bound, then add
a new row.
input:
lower_bound
size
return:
1 - no higher, no lower, insert new row
2 - coalesce with lower
3 - coalesce with higher
4 - coalesce with both lower and higher
-1100012 - lower_bound < lb_p AND upper_bound > lb_p;
-1100013 -- lower_bound < (lb_p+size_p) AND upper_bound > (lb_p+size_p);
\i group_limits.sql
select * from group_limits;
tests
select group_limits_get(10);
select group_limits_return(0,10);
0-100
select group_limits_get(10);
select group_limits_get(10);
select group_limits_return(0,10);
0-10, 10,100
select group_limits_return(10,10);
0-100
select group_limits_get(10);
select group_limits_get(10);
select group_limits_return(10,10);
10-100
select group_limits_return(0,10);
0-100
select group_limits_return(0,10);
select group_limits_return(10,10);
select group_limits_return(20,10);
*/
CREATE OR REPLACE FUNCTION group_limits_return(BIGINT, BIGINT)
RETURNS BIGINT AS '
DECLARE
-- parameters
lb_p ALIAS FOR $1;
size_p ALIAS FOR $2;
-- variables
lb_h_v BIGINT;
size_h_v BIGINT;
lb_l_v BIGINT;
size_l_v BIGINT;
row_count_v INTEGER;
BEGIN
-- These two check are just in case someone at a high application level
-- tries to do something bad. It would be a real screw up if bad
-- data was passed in.
-- check: is lb_p between an existing rows lower and upper values
SELECT count(*) INTO row_count_v
FROM group_limits
WHERE lower_bound < lb_p AND upper_bound > lb_p;
IF row_count_v <> 0 THEN
RETURN -1100012;
END IF;
-- check: is lb_p+size_p between an existing rows lower and upper values
SELECT count(*) INTO row_count_v
FROM group_limits
WHERE lower_bound < (lb_p+size_p) AND upper_bound > (lb_p+size_p);
IF row_count_v <> 0 THEN
RETURN -1100013;
END IF;
-- look for the higher row
SELECT lower_bound, size INTO lb_h_v, size_h_v
FROM group_limits
WHERE lower_bound = (lb_p+size_p);
-- look for the lower row
SELECT lower_bound, size INTO lb_l_v, size_l_v
FROM group_limits
WHERE upper_bound = lb_p;
IF lb_h_v IS NULL THEN
-- no higher row, so see if there is a lower row
IF lb_l_v IS NULL THEN
-- no lower row, so just add a new row
INSERT INTO group_limits (
lower_bound,
size,
upper_bound
) VALUES (
lb_p,
size_p,
size_p+lb_p
);
RETURN 1;
ELSE
-- lower row, so coalesce
-- lower_bound remains the same
-- size += size_p
-- upper_bound += size_p
UPDATE group_limits
SET size = (size_l_v+size_p),
upper_bound = (lb_p+size_p)
WHERE upper_bound = lb_p;
RETURN 2;
END IF;
ELSE
-- higher row
IF lb_l_v IS NULL THEN
-- no lower row, so coalesce with higher
-- lower_bound = lb_p
-- size += size_p
UPDATE group_limits
SET lower_bound = lb_p,
size = (size_h_v+size_p)
WHERE lower_bound = (lb_p+size_p);
RETURN 3;
ELSE
-- lower row, coalesce with both lower and higher
-- delete higher row (must delete one of them)
DELETE FROM group_limits
WHERE lower_bound = (lb_p+size_p);
-- lower_bound = lb_l_v
-- size += size_p+size_h_v
-- upper_bound = rb_h_v = lb_h_v+size_h_v
UPDATE group_limits
SET size = (size_h_v+size_l_v+size_p),
upper_bound = (lb_h_v+size_h_v)
WHERE lower_bound = lb_l_v;
RETURN 4;
END IF;
END IF;
/*
GET DIAGNOSTICS row_count_v = ROW_COUNT;
IF row_count_v <> 1 THEN
RETURN -row_count_v;
END IF;
RETURN lb_v;
*/
END; ' LANGUAGE 'plpgsql';