IPTable.ts

/**
 * Manage a table of IP addresses
 * Supports the following operations:
 * adding an IP
 * removing an IP
 * checking if an IP is in the table
 * iterating all IP addresses inside the table
 */

/**
 * Convert an IP address to a unique base 10 number
 * @param ipAddress IPv4 address to convert to base 10
 * @returns a representation of the ip address in base 10
 */
function base256ToBase10(ipAddress) {
    // Extract the address elements (a.b.c.d)
    const pts = ipAddress.split(".");
    let result = 0;
    for (let i = 0; i < 4; i++) {
        result += Number(pts[i]) * (256 ** i);
    }
    return result;
}

/**
 * Convert a base10 IP address back to it's base256 representation
 * @param ipAddress in base 10 to convert
 * @returns the ip address in a.b.c.d form
 */
function base10ToBase256(ipAddress: number): string {
    const pts = new Array<number>(4);
    for (let i = 0; i < 4; i++) {
        const element = ipAddress % (256 ** (i + 1));
        ipAddress -= element;
        pts[i] = element / (256 ** i);
    }
    return pts.join(".");
}

/**
 * The above functions allow IP addresses to be dealt with as javascript Numbers
 * Which are simpler
 * For example, the following will be true:
 * base10ToBase256(base256ToBase10("127.42.1.0")) === "127.42.1.0"
 */

// Now for the IP table, which is implemented as a "free list"
// See https://en.wikipedia.org/wiki/Free_list
// This table operates exclusively on IP addresses in base 10
// For a table that works with the format a.b.c.d see below
class IPTable {
    private ranges: IPRange[];
    constructor() {
        // Initialize ranges with sentinel nodes to simplify algorithms
        // These nodes cannot be removed because they are invalid IP addresses
        this.ranges = [
            new IPRangeMinSentinel(),
            new IPRangeMaxSentinel(),
        ];
    }
    /**
     * Helper function to iterate the ranges in the table
     * in triples (prev, current, next)
     * @yields (prev, current, next) ranges
     */
    private *iterateRanges() {
        for (let i = 1; i < (this.ranges.length - 1); i++) {
            yield [
                this.ranges[i - 1],
                this.ranges[i],
                this.ranges[i + 1],
            ];
        }
    }
    /**
     * Merge to ranges inside the IPTable
     * Do nothing if blocks don't touch
     */
    private mergeRanges(a: IPRange, b: IPRange) {
        if (!this.blocksTouch(a, b)) {
            return;
        }
        // Make b the bigger one
        if (a.start > b.end) {
            [a, b] = [b, a];
        }
        // Remove b
        this.ranges.splice(this.ranges.indexOf(b), 1);
        // Extend a
        a.end = b.end;
    }
    /**
     * Returns whether the two range blocks touch
     * @param a 
     * @param b 
     */
    private blocksTouch(a: IPRange, b: IPRange) {
        return a.end == b.start || a.start == b.end;
    }
    /**
     * Add an ip address
     * @param ip to add to table
     */
    addIP(ip: number) {
        for (const [prev, cur, next] of this.iterateRanges()) {
            const cmp = cur.compare(ip);
            // Sanity check, ip already inside table
            if (cmp === CompareResult.EQUAL) {
                return;
            }
            const cmpNext = next.compare(ip);
            if (cmpNext != CompareResult.LESS) {
                continue;
            }
            const block = IPRange.fromIP(ip);
            // Insert the new block after the current one
            this.ranges.splice(this.ranges.indexOf(cur) + 1, 0, block);
            this.mergeRanges(cur, block);
            this.mergeRanges(next, block);
            return;
        }
    }
    /**
     * Removes an IP address from the table
     * @param ip to remove
     * @todo Not implemented
     */
    removeIP(ip: number) { }
    /**
     * Returns whether an IP address is in the table
     * @param ip to check
     * @returns whether ip is in table
     */
    hasIP(ip: number): boolean {
        for (const range of this.ranges) {
            if (range.compare(ip) === CompareResult.EQUAL) {
                return true;
            }
        }
        return false;
    }
    /**
     * Iterate the ip addresses
     * @yields The ip addresses in the table
     */
    *[Symbol.iterator](): IterableIterator<number> {
        for (const range of this.ranges) {
            for (let i = range.start; i <= range.end; i++) {
                yield i;
            }
        }
    }
}

enum CompareResult {
    LESS,
    EQUAL,
    GREATER,
}

// Represents a range of IP addresses
class IPRange {
    public start: number;
    public end: number;
    constructor(start: number, end: number) {
        this.start = start;
        this.end = end;
    }
    /**
     * Compare an ip addresses with the block
     * @param check base 10 ip address to check
     */
    public compare(check: number): CompareResult {
        if (check < this.start) return CompareResult.LESS;
        if (check > this.end) return CompareResult.GREATER;
        return CompareResult.EQUAL;
    }
    /**
     * Create a block from an IP address
     * @param ip 
     */
    static fromIP(ip: number): IPRange {
        return new IPRange(ip, ip);
    }
}

class IPRangeMaxSentinel extends IPRange {
    constructor() {
        const max = base256ToBase10("256.256.256") + 2;
        super(max, max);
    }
    public compare(check: number): CompareResult {
        return CompareResult.LESS;
    }
}

class IPRangeMinSentinel extends IPRange {
    constructor() {
        const min = -2;
        super(min, min);
    }
    public compare(check: number): CompareResult {
        return CompareResult.GREATER;
    }
}

// Wrapper class that translates base 10 ip addresses to base 256
// This is the class you would actually want to use
export class IPTable256 {
    private table = new IPTable();
    addIP(ip: string) {
        const ip10 = base256ToBase10(ip);
        this.table.addIP(ip10);
    }
    removeIP(ip: string) {
        const ip10 = base256ToBase10(ip);
        this.table.removeIP(ip10);
    }
    hasIP(ip: string): boolean {
        const ip10 = base256ToBase10(ip);
        return this.table.hasIP(ip10);
    }
    *[Symbol.iterator](): IterableIterator<string> {
        for (const ip10 of this.table) {
            yield base10ToBase256(ip10);
        }
    }
}

If I wanted to store 3702258432 globally-routable IPs, how much memory would this take?