/****
Stored procedures for implementing an efficient storage of INT
values that are assigned in blocks, such as IPv6.

Rules for "ip" values:
    * A NULL value for ip means "greater than 'FF...FF'.
    * A "block" of ip addresses is represented as the start and end values.
    * owner=0 means "not owned by anyone" or "free".
    * There is no way for the table to represent overlaping blocks, hence such is disallowed.
Rules for "owner" values:
    * "owner" is the PRIMARY KEY in another table.
    * The main table (Ips) contains one row per block.

For this 'reference implementation', I use
    * "ip" values are BINARY(16) in the table Ips.
    * "ip" values used exposed to the user are BINARY(32), the HEX of the BINARY(16).
    * "owner" values are INT UNSIGNED (but it could be something else)
    * ip+1 and ip-1 are rather complex.

This file is designed to be installed using "source"
from the 'mysql' command line tool.

(started 7/2011; continued 4/2012, 8/2012)
-- Rick James

CAVEAT:  These stored routines have not been thoroughly tested.
****/

-- IP addresses are passed around as HEX strings.
-- Use HEX() and UNHEX() when touching Ips.ip, which is BINARY(16)

-- -----------------------------------------
-- Table needed for IP handling:
CREATE TABLE Ips (
    ip BINARY(16) NOT NULL  COMMENT "IPv6 starting address - UNHEX('...')",
    owner INT UNSIGNED NOT NULL  COMMENT '0=not owned; Join to another table to get info on owner',
    PRIMARY KEY(ip),
    INDEX(owner)   -- for finding range(s) owned
) ENGINE=InnoDB;
-- InnoDB was deliberately chosen for its 'clustering' on the PK.

-- The table MUST be initialized with the starting IP and owner=0
INSERT INTO Ips (ip, owner) VALUES (UNHEX('00000000000000000000000000000000'), 0);

DELIMITER //

-- -----------------------------------------
-- Add 1 to an IP
-- Hex in, Hex out.
DROP FUNCTION IF EXISTS IpIncr //
CREATE DEFINER = 'ip'@'localhost' FUNCTION IpIncr(
        _ip BINARY(32)  -- hex
    ) RETURNS BINARY(32)
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    DECLARE _non_f VARCHAR(32) DEFAULT RTRIM(REPLACE(UPPER(_ip), 'F', ' '));
    DECLARE _len INT DEFAULT LENGTH(_non_f);
    IF (_len = 0) THEN
        RETURN NULL;       -- all f... +1 => null
    ELSE
        RETURN
            CONCAT( LEFT(_ip, _len - 1),
                    CONV(CONV(RIGHT(_non_f, 1), 16, 10) + 1, 10, 16),
                    REPEAT('0', 32 - _len));
    END IF;
END //
-- not as fast:                      LEFT('00000000000000000000000000000000', 32 - _len));

-- -----------------------------------------
-- Subtract 1 from an IP
-- (Please do not feed 0 in)
DROP FUNCTION IF EXISTS IpDecr //
CREATE DEFINER = 'ip'@'localhost' FUNCTION IpDecr(
        _ip BINARY(32)  -- hex
    ) RETURNS BINARY(32)
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    DECLARE _non_0 VARCHAR(32) DEFAULT RTRIM(REPLACE(_ip, '0', ' '));
    DECLARE _len INT DEFAULT LENGTH(_non_0);
    IF (_ip IS NULL) THEN
        RETURN 'FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF';
    ELSE
        RETURN
            CONCAT( LEFT(_ip, _len - 1),
                    CONV(CONV(RIGHT(_non_0, 1), 16, 10) - 1, 10, 16),
                    REPEAT('F', 32 - _len));
    END IF;
END //

-- -----------------------------------------
-- Assign a range of IP addresses to an owner
-- This version does not return any information about current owner(s)
--    of the range.  Any checks need to be done separately.
-- 1-7 SQL statements executed; most hit only one row.
-- To 'free' up a block, assign it owner=0.
DROP PROCEDURE IF EXISTS IpStore //
CREATE DEFINER = 'ip'@'localhost' PROCEDURE IpStore(
        IN _ipa BINARY(32),
        IN _ipz BINARY(32),
        IN _new_owner INT UNSIGNED)
BEGIN
    DECLARE _bipa BINARY(16) DEFAULT UNHEX(_ipa);
    DECLARE _bipz BINARY(16) DEFAULT UNHEX(_ipz);
    DECLARE _bip BINARY(16);
    DECLARE _owner INT UNSIGNED;
    DECLARE _bnext BINARY(16) DEFAULT UNHEX(IpIncr(_ipz));
    -- All work is done in BINARY(16), thereby avoiding case
    --    folding issues with HEX values compared in binary.

    IF (_bnext IS NULL) THEN
        -- _ipz is ff...ff
        SELECT ip, owner INTO _bip, _owner FROM Ips WHERE ip <= _bipz ORDER BY ip DESC LIMIT 1;
    ELSE
        -- Deal with point just off the end (_bnext):
        SELECT ip, owner INTO _bip, _owner FROM Ips WHERE ip <= _bnext ORDER BY ip DESC LIMIT 1;
        IF (_bip = _bnext) THEN
            -- No gap before next block, so may need to coalesce:
            IF (_owner = _new_owner) THEN   -- Merge with new entry
                DELETE FROM Ips WHERE ip = _bnext;
            END IF;
            SELECT ip, owner INTO _bip, _owner FROM Ips WHERE ip <= _bipz ORDER BY ip DESC LIMIT 1;
        ELSE
            -- Assign gap:
            IF (_owner != _new_owner) THEN
                INSERT INTO Ips (ip, owner) VALUES (_bnext, _owner);
            END IF;
        END IF;
    END IF;

    -- Gut the middle (if needed):
    IF (_bip > _bipa) THEN
        DELETE FROM Ips WHERE ip > _bipa AND ip <= _bipz;
        SELECT ip, owner INTO _bip, _owner FROM Ips WHERE ip <= _bipa ORDER BY ip DESC LIMIT 1;
    END IF;

    -- Deal with start of this block
    IF (_owner != _new_owner) THEN
        IF (_bip = _bipa) THEN
            SELECT owner INTO _owner FROM Ips WHERE ip < _bipa ORDER BY ip DESC LIMIT 1;
            IF (_owner = _new_owner) THEN
                DELETE FROM Ips WHERE ip = _bipa;  -- merge
            ELSE
                UPDATE Ips SET owner = _new_owner WHERE ip = _bipa;  -- change
            END IF;
        ELSE
            INSERT INTO Ips (ip, owner) VALUES (_bipa, _new_owner);  -- split
        END IF;
    END IF;
END //

-- -----------------------------------------
-- Given a single IP address, find the owner
-- Result may be 0 (un-owned), but will not be NULL.
DROP FUNCTION IF EXISTS IpOwner //
CREATE DEFINER = 'ip'@'localhost' FUNCTION IpOwner(
        _ip BINARY(32))
    RETURNS INT UNSIGNED
BEGIN
    DECLARE _owner INT UNSIGNED;
    SELECT owner INTO _owner
        FROM Ips
        WHERE ip <= UNHEX(_ip)
        ORDER BY ip DESC
        LIMIT 1;
    RETURN _owner;
END //

-- -----------------------------------------
-- Given a range of IP addresses, find all the owners of such
DROP PROCEDURE IF EXISTS IpRangeOwners //
CREATE DEFINER = 'ip'@'localhost' PROCEDURE IpRangeOwners(
        IN _ip_start BINARY(32),
        IN _ip_end  BINARY(32))
-- _ip_start..ip_end is the range
-- Resultset has one owner per row.
BEGIN
    ( SELECT owner
        FROM Ips
        WHERE ip <= UNHEX(_ip_start)
        ORDER BY ip DESC
        LIMIT 1 )
    UNION DISTINCT
    ( SELECT owner
        FROM Ips
        WHERE ip > UNHEX(_ip_start)
          AND ip <= UNHEX(_ip_end) );
END //

-- -----------------------------------------
-- Given a range of IP addresses, find blocks and owners of such
DROP PROCEDURE IF EXISTS IpFindRanges //
CREATE DEFINER = 'ip'@'localhost' PROCEDURE IpFindRanges(
        IN _ip_start BINARY(32),
        IN _ip_end   BINARY(32))
-- _ip_start is start of the range
-- _ip_next is the addr after the end of the range (or NULL when wanting to end at fff...)
-- Resultset contains array of [starting IP, owner]
-- First IP will be <= _ip_start, and may be strictly <.
-- Owners with disjoint blocks will show up multiple times.
BEGIN
    ( SELECT HEX(ip), owner
        FROM Ips
        WHERE ip <= UNHEX(_ip_start)
        ORDER BY ip DESC
        LIMIT 1 )
    UNION ALL
    ( SELECT HEX(ip), owner
        FROM Ips
        WHERE ip > UNHEX(_ip_start)
          AND ip <= UNHEX(_ip_end)
        ORDER BY ip );
END //

-- -----------------------------------------
-- Given an IP, find the start of the next block
-- Returns NULL if runs off end of list.
DROP FUNCTION IF EXISTS IpNext //
CREATE DEFINER = 'ip'@'localhost' FUNCTION IpNext(
        _ipa BINARY(32)  -- hex
    ) RETURNS BINARY(32)
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    DECLARE _ipz BINARY(32);
    SELECT HEX(ip) INTO _ipz
        FROM Ips
        WHERE ip > UNHEX(_ipa)
        ORDER BY ip
        LIMIT 1;
    RETURN _ipz;
END //

-- -----------------------------------------
-- Given an IP, find the end of the block containing the IP.
DROP FUNCTION IF EXISTS IpEnd //
CREATE DEFINER = 'ip'@'localhost' FUNCTION IpEnd(
        _ipa BINARY(32)  -- hex
    ) RETURNS BINARY(32)
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    DECLARE _ipz BINARY(32);
    SELECT HEX(ip) INTO _ipz
        FROM Ips
        WHERE ip > UNHEX(_ipa)
        ORDER BY ip
        LIMIT 1;
    -- If off the end, SELECT returns NULL, then IpDecr turns it into ff...ff
    RETURN IpDecr(_ipz);
END //

-- -----------------------------------------
-- Given an owner, find the starting IP for each block it owns.
-- Resultset is array if [ip_start]
DROP PROCEDURE IF EXISTS Owner2IpStarts //
CREATE DEFINER = 'ip'@'localhost' PROCEDURE Owner2IpStarts(
        IN _owner INT UNSIGNED)
BEGIN
    SELECT HEX(ip)
        FROM Ips
        WHERE owner = _owner
        ORDER BY ip;
END //

-- -----------------------------------------
-- Given an owner, find the ranges it owns.
-- Resultset is array if [ip_start, ip_end]
DROP PROCEDURE IF EXISTS Owner2IpRanges //
CREATE DEFINER = 'ip'@'localhost' PROCEDURE Owner2IpRanges(
        IN _owner INT UNSIGNED)
BEGIN
    SELECT  HEX(ip)        AS ip_start,
            IpEnd(HEX(ip)) AS ip_end
        FROM Ips
        WHERE owner = _owner;
END //

DELIMITER ;