table.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
#include <sys/time.h>

static inline uint32_t
read_ip(FILE *in)
{
    unsigned ip[4];
    if (fscanf(in, " %u.%u.%u.%u", ip, ip + 1, ip + 2, ip + 3) == 4)
        return (ip[0] << 24) | (ip[1] << 16) | (ip[2] << 8) | ip[3];
    return 0;
}

static struct {
    uint32_t count;
    uint32_t max;
    char **s;
} intern_table;

static uint32_t
intern(const char *s)
{
    for (uint32_t i = 0; i < intern_table.count; i++)
        if (strcmp(intern_table.s[i], s) == 0)
            return i;
    if (intern_table.count == intern_table.max) {
        intern_table.max = intern_table.max == 0 ? 4096 : intern_table.max * 2;
        intern_table.s = realloc(intern_table.s,
                                 intern_table.max * sizeof(*intern_table.s));
    }
    char *copy = malloc(strlen(s) + 1);
    strcpy(copy, s);
    intern_table.s[intern_table.count] = copy;
    return intern_table.count++;
}

static const char *
lookup(uint32_t n)
{
    return intern_table.s[n];
}

struct source {
    uint32_t min;
    uint32_t max;
    uint32_t name;
};

static inline bool
scanline(struct source *e, FILE *in)
{
    e->min = read_ip(in);
    e->max = read_ip(in);
    char name[256];
    if (e->min && e->max && fscanf(in, " %[^\n]", name) == 1) {
        e->name = intern(name);
        return true;
    }
    return false;
}

struct slot {
    uint32_t start;
    uint32_t stop;
    uint32_t source;
};

struct table {
    uint32_t count;
    struct slot slot[];
};

struct event {
    uint32_t when;
    struct source *who;
    enum { E_ADD, E_DEL } type;
};

static int
uint32_cmp(const void *va, const void *vb)
{
    uint32_t a = *(uint32_t *)va;
    uint32_t b = *(uint32_t *)vb;
    if (a < b)
        return -1;
    else if (b < a)
        return 1;
    else
        return 0;
}

static struct table *
table_create(struct source *source, uint32_t count)
{
    struct event *event = malloc(sizeof(*event) * count * 2);
    for (uint32_t i = 0; i < count; i++) {
        event[i * 2 + 0] = (struct event){
            source[i].min + 0, &source[i], E_ADD
        };
        event[i * 2 + 1] = (struct event){
            source[i].max + 1, &source[i], E_DEL
        };
    }
    qsort(event, count * 2, sizeof(*event), uint32_cmp);

    struct table *table;
    size_t size = sizeof(*table) + sizeof(*table->slot) * count * 2;
    table = malloc(size);
    table->count = 0;

    struct source **member = malloc(sizeof(*member) * count);
    uint32_t member_count = 0;
    uint32_t start;
    for (uint32_t i = 0; i < count * 2; i++) {
        if (member_count > 0) {
            struct slot *s = &table->slot[table->count++];
            s->start = start;
            s->stop = event[i].when;
            s->source = member[0]->name;
            uint32_t smallest = member[0]->max - member[0]->min;
            for (uint32_t m = 1; m < member_count; m++) {
                uint32_t range = member[m]->max - member[m]->min;
                if (range < smallest) {
                    s->source = member[m]->name;
                    smallest = range;
                }
            }
        }
        start = event[i].when;
        switch (event[i].type) {
            case E_DEL:
                for (uint32_t m = member_count - 1; m < member_count; m--)
                    if (member[m] == event[i].who) {
                        member[m] = member[--member_count];
                        break;
                    }
                break;
            case E_ADD:
                member[member_count++] = event[i].who;
                break;
        }
    }
    free(member);
    free(event);
    return table;
}

static int
search(const void *k, const void *m)
{
    uint32_t ip = *(uint32_t *)k;
    struct slot *slot = (struct slot *)m;
    if (ip < slot->start)
        return -1;
    else if (ip >= slot->stop)
        return 1;
    else
        return 0;
}

static struct slot *
table_search(struct table *t, uint32_t ip)
{
    return bsearch(&ip, t->slot, t->count, sizeof(*t->slot), search);
}

static uint64_t
uepoch(void)
{
    struct timeval tv;
    gettimeofday(&tv, NULL);
    return 1000000LL * tv.tv_sec + tv.tv_usec;
}

int
main(int argc, char **argv)
{
    fprintf(stderr, "Reading entries ...\n");
    (void)argc;
    FILE *range = fopen(argv[1], "r");
    uint32_t source_max = 64 * 1024;
    uint32_t source_count = 0;
    struct source *source = malloc(sizeof(*source) * source_max);
    while (scanline(&source[source_count], range)) {
        if (++source_count == source_max) {
            source_max *= 2;
            source = realloc(source, sizeof(*source) * source_max);
        }
    }
    fclose(range);
    source[source_count++] = (struct source){
        0, UINT32_MAX - 1, intern("<unknown>")
    };

    fprintf(stderr, "Constructing table ...\n");
    struct table *table = table_create(source, source_count);
    free(source);
    struct {
        uint32_t count;
        uint32_t name;
    } *counts = malloc(sizeof(*counts) * intern_table.count);
    for (uint32_t i = 0; i < intern_table.count; i++) {
        counts[i].count = 0;
        counts[i].name = i;
    }

    fprintf(stderr, "Sorting IPs ...\n");
    uint64_t start = uepoch();
    uint32_t ip;
    uint64_t total = 0;
    while ((ip = read_ip(stdin))) {
        struct slot *s = table_search(table, ip);
        counts[s->source].count++;
        total++;
    }

    /* Print results */
    qsort(counts, intern_table.count, sizeof(*counts), uint32_cmp);
    for (uint32_t i = intern_table.count - 1; i < intern_table.count; i--)
        if (counts[i].count)
            printf("%u - %s\n",
                   (unsigned)counts[i].count, lookup(counts[i].name));

    double delta = (uepoch() - start) / 1000000.0;
    fprintf(stderr, "Elapsed: %f sec (%f ip/sec)\n", delta, total / delta);
    return 0;
}