/****
This is a "reference implementation" for an efficient implementation
of IPv4 (or similar) set of non-overlapping ranges of values.
The stored procedures and the table design embody the efficiency.

There are two tables:
    * Ips -- two fields: ip and owner.  (ip represents the start of a block)
    * Another table, indexed by owner.  This contains other info.  It is not touched here.

For this 'reference implementation',
    * "ip" values are INT UNSIGNED.
    * "owner" values are MEDIUMINT UNSIGNED (0 = no owner)
    * ip+1 and ip-1 are simple arithmetic.

Rules for "ip" values:
    * A NULL value for ip means "greater than 0xFFFFFFFF.
    * A "block" of ip addresses is represented by the start and end values,
    * By convention, owner=0 means "not owned by anyone" or "free".
    * There is no way for the table to represent overlaping blocks, hence such is disallowed.
    * ALL ip addresses are ALWAYS in the Ips table.
    * INET_ATON() and INET_NTOA() may be used by the caller, if desired.

Rules for "owner" values:
    * "owner" is the PRIMARY KEY in another table.
    * The main table (Ips) contains one row per block of owned (or free) IP addresses.

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
****/

-- -----------------------------------------
-- Table needed for IP handling:
CREATE TABLE Ips (
    ip INT UNSIGNED NOT NULL  COMMENT 'IPv4 starting address',
    owner MEDIUMINT 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;
-- The table MUST be initialized with the starting IP and owner=0:
-- INSERT INTO Ips (ip, owner) VALUES (0, 0);
-- InnoDB was deliberately chosen -- for the 'clustering'.

DELIMITER //

-- -----------------------------------------
-- Add 1 to an IP
DROP FUNCTION IF EXISTS IpIncr //
CREATE DEFINER = `ip`@`localhost` FUNCTION IpIncr(
        _ip INT UNSIGNED
    ) RETURNS INT UNSIGNED
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    IF (_ip = 4294967295) THEN
        RETURN NULL;
    ELSE
        RETURN _ip + 1;
    END IF;
END //

-- -----------------------------------------
-- Subtract 1 from an IP
-- (Please do not feed 0 in)
DROP FUNCTION IF EXISTS IpDecr //
CREATE DEFINER = `ip`@`localhost` FUNCTION IpDecr(
        _ip INT UNSIGNED
    ) RETURNS INT UNSIGNED
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    IF (_ip IS NULL) THEN
        RETURN 4294967295;
    ELSE
        RETURN _ip - 1;
    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 INT UNSIGNED,
        IN _ipz INT UNSIGNED,
        IN _new_owner MEDIUMINT UNSIGNED)
BEGIN
    DECLARE _ip INT UNSIGNED;
    DECLARE _owner MEDIUMINT UNSIGNED;
    DECLARE _next INT UNSIGNED DEFAULT IpIncr(_ipz);

    IF (_next IS NULL) THEN
        -- _ipz must be ff...ff; prep for later
        SELECT ip, owner INTO _ip, _owner FROM Ips WHERE ip <= _ipz ORDER BY ip DESC LIMIT 1;
    ELSE
        -- Deal with point just off the end (_next):
        SELECT ip, owner INTO _ip, _owner FROM Ips WHERE ip <= _next ORDER BY ip DESC LIMIT 1;
        IF (_ip = _next) 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 = _next;
            END IF;
            SELECT ip, owner INTO _ip, _owner FROM Ips WHERE ip <= _ipz ORDER BY ip DESC LIMIT 1;
        ELSE
            -- Assign gap:
            IF (_owner != _new_owner) THEN
                INSERT INTO Ips (ip, owner) VALUES (_next, _owner);
            END IF;
        END IF;
    END IF;

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

    -- Deal with start of this block
    IF (_owner != _new_owner) THEN
        IF (_ip = _ipa) THEN
            SELECT owner INTO _owner FROM Ips WHERE ip < _ipa ORDER BY ip DESC LIMIT 1;
            IF (_owner = _new_owner) THEN
                DELETE FROM Ips WHERE ip = _ipa;  -- merge
            ELSE
                UPDATE Ips SET owner = _new_owner WHERE ip = _ipa;  -- change
            END IF;
        ELSE
            INSERT INTO Ips (ip, owner) VALUES (_ipa, _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 INT UNSIGNED)
    RETURNS MEDIUMINT UNSIGNED
BEGIN
    DECLARE _owner MEDIUMINT UNSIGNED;
    SELECT owner INTO _owner
        FROM Ips
        WHERE ip <= _ip
        ORDER BY ip DESC
        LIMIT 1;
    RETURN _owner;
END //

-- -----------------------------------------
-- Given a range of IP addresses, find all the owners of such
-- This can be used before assigning a block - to see if someone
--   else owns any of the block.
--   Check the output for containing any 'owner' other than
--   the desired owner and '0'.
DROP PROCEDURE IF EXISTS IpRangeOwners //
CREATE DEFINER = `ip`@`localhost` PROCEDURE IpRangeOwners(
        IN _ip_start INT UNSIGNED,
        IN _ip_end   INT UNSIGNED)
-- _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 has one owner per row, dedupped.
BEGIN
    ( SELECT owner
        FROM Ips
        WHERE ip <= _ip_start
        ORDER BY ip DESC
        LIMIT 1 )
    UNION DISTINCT
    ( SELECT owner
        FROM Ips
        WHERE ip > _ip_start
          AND ip <= _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 INT UNSIGNED,
        IN _ip_end   INT UNSIGNED)
-- _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 ip, owner
        FROM Ips
        WHERE ip <= _ip_start
        ORDER BY ip DESC
        LIMIT 1 )
    UNION ALL
    ( SELECT ip, owner
        FROM Ips
        WHERE ip > _ip_start
          AND ip <= _ip_end
        ORDER BY ip )
    ORDER BY ip;
END //

-- -----------------------------------------
-- Given an IP, find the start of the next block
-- Returns NULL if runs off end of the address space.
DROP FUNCTION IF EXISTS IpNext //
CREATE DEFINER = `ip`@`localhost` FUNCTION IpNext(
        _ipa INT UNSIGNED
    ) RETURNS INT UNSIGNED
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    DECLARE _ip_next INT UNSIGNED;
    SELECT ip INTO _ip_next
        FROM Ips
        WHERE ip > _ipa
        ORDER BY ip
        LIMIT 1;
    RETURN _ip_next;
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 INT UNSIGNED
    ) RETURNS INT UNSIGNED
    DETERMINISTIC
CONTAINS SQL  -- SQL but does not read or write
BEGIN
    DECLARE _ip_next INT UNSIGNED;
    SELECT ip INTO _ip_next
        FROM Ips
        WHERE ip > _ipa
        ORDER BY ip
        LIMIT 1;
    RETURN IpDecr(_ip_next);
END //

-- -----------------------------------------
-- Given an owner, find the starting IP for each block it owns.
-- Resultset is array of [ip_start]
DROP PROCEDURE IF EXISTS Owner2IpStarts //
CREATE DEFINER = `ip`@`localhost` PROCEDURE Owner2IpStarts(
        IN _owner MEDIUMINT UNSIGNED)
BEGIN
    SELECT 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 MEDIUMINT UNSIGNED)
BEGIN
    SELECT  ip        AS ip_start,
            IpEnd(ip) AS ip_end
        FROM IpS
        WHERE owner = _owner
        ORDER BY ip;
END //

DELIMITER ;