generator.c

// Generates a random city adjacency list
// Ref: https://old.reddit.com/r/C_Programming/comments/zgdxqr
// This is free and unencumbered software released into the public domain.
#include <stdio.h>
#include <time.h>

#define NCITIES 1000
#define NEDGES  (NCITIES*10)

static int randint(unsigned long long *s, int n)
{
    return (((*s = *s*0x3243f6a8885a308d + 1) >> 32) * n) >> 32;
}

// Markov chain city name generator, with a lookup table created from
// several hundred large American city names.
static int namegen(unsigned long long *rng, char *name, int min, int max)
{
    static const char tx[52] =
        "ABCDEFGHIJKLMNOPQRSTVWYabcdefghijklmnopqrstuvwxyz";
    static const unsigned char markov[][26] = {
        {0,1,0,0,0,0,0,0,0,0,1,5,1,3,0,0,0,2,0,2,3,0,0,0,0,0},
        {2,0,0,0,5,0,0,0,2,0,0,0,0,0,3,0,0,3,0,0,3,0,0,0,0,0},
        {5,0,0,0,1,0,0,7,1,0,0,4,0,0,4,0,0,0,0,0,0,0,0,0,0,0},
        {4,0,0,0,4,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0},
        {0,0,0,2,0,0,0,0,0,0,0,2,0,0,0,0,0,0,1,0,1,2,0,0,0,0},
        {3,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,3,0,0,1,0,0,0,0,0},
        {2,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,3,0,0,0,0,0,0,0,0},
        {4,0,0,0,2,0,0,0,2,0,0,0,0,0,3,0,0,0,0,0,1,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,2,0,0,0,0,0,0,0,0},
        {2,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,1,0,0,0,2,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
        {6,0,0,0,2,0,0,0,1,0,0,0,0,0,3,0,0,0,0,0,1,0,0,0,1,0},
        {3,0,2,0,5,0,0,0,5,0,0,0,0,0,3,0,0,0,0,0,2,0,0,0,0,0},
        {3,0,0,0,1,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,1,1,0,0,0,0,0,0,0,1,1,1,0,0,0,3,0,0,0,0,0,1,0,0},
        {3,0,0,0,2,0,0,2,1,0,0,1,0,0,2,0,0,2,0,0,1,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
        {1,0,0,0,2,0,0,0,4,0,0,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0},
        {4,0,1,0,1,0,0,1,0,0,0,0,0,0,0,3,0,0,0,2,2,0,0,0,1,0},
        {3,0,0,0,2,0,0,1,0,0,0,0,0,0,2,0,0,0,0,0,3,0,0,0,1,0},
        {3,0,0,0,1,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
        {4,0,0,0,1,0,0,0,2,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {0,1,8,5,0,1,2,5,2,0,5,19,11,30,0,4,0,24,8,7,2,5,0,0,4,0},
        {2,1,0,0,2,0,0,0,3,0,0,1,0,0,5,0,0,2,0,0,5,0,0,0,0,0},
        {4,0,0,0,5,0,0,7,1,0,7,0,0,0,10,0,0,1,1,1,2,0,0,0,1,0},
        {4,1,0,0,11,1,3,0,6,0,0,2,0,0,4,0,0,1,1,0,0,0,0,0,1,0},
        {11,1,1,3,7,0,0,0,2,1,0,11,5,29,1,3,0,27,15,7,0,5,4,2,5,0},
        {2,0,0,0,1,1,0,0,3,0,0,0,0,0,5,0,0,1,0,0,0,0,0,0,0,0},
        {1,0,0,0,6,1,0,3,1,0,0,1,1,0,3,0,0,0,1,4,1,0,0,0,0,0},
        {10,0,0,0,7,0,0,0,7,0,0,0,1,0,3,0,0,1,0,0,0,1,0,0,0,0},
        {12,0,6,9,6,1,1,0,0,0,0,25,2,22,2,0,0,3,13,4,0,1,0,1,0,1},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,8,1,0,0,0,0,0,1,0,0,0,0,0,1,4,2,0,0,0,0,0,0},
        {16,2,0,4,44,0,1,0,8,0,2,30,2,1,6,1,0,0,3,3,4,0,1,0,1,0},
        {5,3,0,1,4,1,0,0,4,0,0,0,0,0,6,5,0,0,0,0,0,0,0,0,0,0},
        {10,1,11,18,8,0,12,0,3,0,2,0,0,7,6,1,0,0,9,17,0,2,0,0,1,0},
        {0,1,6,6,1,0,1,0,2,0,1,11,3,39,7,0,0,25,3,2,4,3,4,1,0,0},
        {3,0,0,0,5,0,0,2,0,0,0,0,0,0,6,0,0,2,0,1,0,0,0,0,0,0},
        {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0},
        {8,3,1,8,11,3,3,1,13,0,4,8,3,2,12,1,1,4,6,7,0,5,2,0,3,0},
        {8,5,3,1,5,1,0,4,3,0,0,0,0,1,8,1,1,0,2,12,0,7,0,0,0,0},
        {8,0,0,0,13,1,1,3,4,0,0,3,1,0,22,0,0,1,3,8,1,0,0,0,0,0},
        {0,1,2,0,4,1,2,0,3,0,1,5,3,2,0,0,1,10,6,0,0,1,0,0,0,0},
        {4,0,0,0,8,0,0,0,20,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0},
        {5,0,0,0,1,0,0,0,1,0,0,0,0,3,3,0,0,0,0,0,0,0,0,0,0,0},
        {1,0,0,0,0,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,0},
        {0,0,0,0,4,0,0,0,0,0,0,1,0,1,0,0,0,1,0,1,0,1,2,0,0,0},
        {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
    };
    int len = min + randint(rng, max-min);
    int c   = randint(rng, 23);
    *name++ = tx[c];
    for (int i = 0; i < len; i++) {
        int t = 0;
        for (int i = 0; i < 26; i++) {
            t += markov[c][i];
        }
        t = randint(rng, t);
        for (int i = 0; i < 26; i++) {
            if (markov[c][i]) {
                t -= markov[c][i];
                if (t <= 0) {
                    c = 23 + i;
                    break;
                }
            }
        }
        *name++ = tx[c];
    }
    return len;
}

int main(void)
{
    int noptions = NCITIES*NCITIES;
    static int options[NCITIES*NCITIES];
    for (int i = 0; i < noptions; i++) {
        options[i] = i;
    }

    char cities[NCITIES][12] = {{0}};
    unsigned long long rng[1] = {time(0)};
    for (int i = 0; i < NCITIES; i++) {
        namegen(rng, cities[i], 4, sizeof(cities[i])-1);
    }

    for (int n, m, i = 0; i < NEDGES; i++) {
        do {
            int choice = randint(rng, noptions--);
            int option = options[choice];
            options[choice] = options[NCITIES*NCITIES-1];
            n = option % NCITIES;
            m = option / NCITIES;
        } while (n <= m);
        printf("%s %s %d\n", cities[n], cities[m], 1+randint(rng, 999));
    }
}

parse.c

// Demonstration parser for an edge list
// Ref: https://old.reddit.com/r/C_Programming/comments/zgdxqr
// This is free and unencumbered software released into the public domain.
#include <assert.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NEW(arena, type, n) alloc(arena, sizeof(type)*n, _Alignof(type))

typedef struct {
    char *mem;
    int len, off;
} Arena;

static void *alloc(Arena *a, int len, int align)
{
    a->off += -a->off & (align - 1);
    assert(a->len-a->off >= len);
    return memset((a->mem + (a->off += len)) - len, 0, len);
}

typedef struct City {
    struct City *next;
    char *name;
    int len;
    int id;
} City;

typedef struct IdNode {
    struct IdNode *next;
    City *city;
} IdNode;

typedef struct {
    City *byname;
    IdNode *byid;
    int cap, len;
} Hashtab;

// Construct a hash table tuned for around 2**exp elements.
static Hashtab *hashtab(Arena *a, int exp)
{
    Hashtab *ht = NEW(a, Hashtab, 1);
    ht->byname  = NEW(a, *ht->byname, 1<<exp);
    ht->byid    = NEW(a, *ht->byid, 1<<exp);
    ht->cap     = 1 << exp;
    return ht;
}

// Look up a city entry by name, creating one if necessary. City IDs
// begin at zero and increment monotonically.
static City *byname(Arena *a, Hashtab *ht, char *name, int len)
{
    uint64_t h = 0;
    memcpy(&h, name, len<8?len:8);
    h *= 1111111111111111111;
    h ^= h >> 32;

    City *city = ht->byname + (h&(ht->cap - 1));
    if (city->name) {
        for (;;) {
            if (len==city->len && !memcmp(name, city->name, len)) {
                return city;
            }
            if (!city->next) {
                city = city->next = NEW(a, City, 1);
                break;
            }
            city = city->next;
        }
    }

    // None found, insert into the table
    city->name = NEW(a, char, len);
    city->next = 0;
    memcpy(city->name, name, len);
    city->len = len;
    city->id = ht->len++;

    // Enter into the inverse index, too
    uint64_t hid = city->id;
    hid *= 1111111111111111111;
    hid ^= hid >> 32;
    IdNode *node = ht->byid + (hid&(ht->cap - 1));
    if (node->city) {
        IdNode *new = NEW(a, IdNode, 1);
        new->next = node->next;
        node->next = new;
        new->city = city;
    } else {
        node->city = city;
    }

    return city;
}

// Look up a city by its ID, returning null if not found.
static City *byid(Hashtab *ht, int id)
{
    uint64_t hid = id;
    hid *= 1111111111111111111;
    hid ^= hid >> 32;
    IdNode *node = ht->byid + (hid&(ht->cap - 1));
    for (; node && node->city; node = node->next) {
        if (node->city->id == id) {
            return node->city;
        }
    }
    return 0;
}

typedef struct {
    City *city1;
    City *city2;
    int weight;
} Edge;

static Edge parseline(Arena *a, Hashtab *ht, char *line)
{
    char *city1 = line;
    int len1 = strcspn(city1, "\t ");
    char *city2 = line + len1 + strspn(line+len1, "\t ");
    int len2 = strcspn(city2, " \t");

    City *c1 = byname(a, ht, city1, len1);
    City *c2 = byname(a, ht, city2, len2);
    Edge e = {c1, c2, atoi(city2+len2)};
    return e;
}

static Hashtab *parsefile(Arena *a, FILE *f)
{
    char line[128];
    Hashtab *ht = hashtab(a, 8);
    while (fgets(line, sizeof(line), f)) {
        Edge e = parseline(a, ht, line);
        printf("%d %d %d\n", e.city1->id, e.city2->id, e.weight);
        // TODO: enter into an adjacency list
    }
    return ht;
}

int main(void)
{
    Arena arena = {malloc(1<<20), 1<<20, 0};
    Hashtab *ht = parsefile(&arena, stdin);
    for (int i = 0; i < ht->len; i++) {
        City *c = byid(ht, i);
        printf("%-4d%.*s\n", i, c->len, c->name);
    }
    fprintf(stderr, "memory used: %d bytes\n", arena.off);
    free(arena.mem);
}