main.c

// Ref: https://old.reddit.com/r/C_Programming/comments/1dlc4kw
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define new(n, t)  (t *)calloc(n, sizeof(t))

typedef struct node node;
struct node {
    node *next;
    node *ref;   // points to an arbitrary node in the list
};

// Intrusive hash map
typedef struct map map;
struct map {
    node  new;
    map  *child[2];
    node *old;
};

static node *upsert(map **m, node *old)
{
    if (!old) {
        return 0;  // map null to null
    }

    uint64_t hash = (uintptr_t)old * 1111111111111111111ull;
    for (; *m; hash <<= 1) {
        if (old == (*m)->old) {
            return &(*m)->new;
        }
        m = &(*m)->child[hash>>63];
    }

    *m = new(1, map);
    (*m)->old = old;
    return &(*m)->new;
}

// NOTE: Assumes returned nodes must be individually allocated, which is
// silly but fits the spirit of the exercise.
static node *duplicate(node *head)
{
    map *m = 0;
    for (node *old = head; old; old = old->next) {
        node *new = upsert(&m, old);
        new->next = upsert(&m, old->next);
        new->ref  = upsert(&m, old->ref);
    }
    return upsert(&m, head);
}


// Test

typedef struct idmap idmap;
struct idmap {
    idmap *child[4];
    node  *key;
    int    id;
};

static int intern(idmap **m, node *key, int *count)
{
    if (!key) {
        return -1;
    }

    uint64_t hash = (uintptr_t)key * 1111111111111111111ull;
    for (; *m; hash <<= 2) {
        if (key == (*m)->key) {
            return (*m)->id;
        }
        m = &(*m)->child[hash>>62];
    }

    *m = new(1, idmap);
    (*m)->key = key;
    (*m)->id = (*count)++;
    return (*m)->id;
}

static int randint(uint64_t *rng, int n)
{
    *rng = *rng*0x243f6a8885a308d + 1;
    return (int)(((*rng>>32) * n)>>32);
}

int main(void)
{
    uint64_t rng = 123;
    int len = 20;
    node *nodes = new(len, node);
    for (int i = 0; i < len-1; i++) {
        nodes[i].next = nodes + i + 1;
        if (!randint(&rng, 2)) {
            nodes[i].ref = nodes + randint(&rng, len);
        }
    }

    puts("input:");
    for (int i = 0; i < len; i++) {
        int next = nodes[i].next ? (int)(nodes[i].next - nodes) : -1;
        int ref  = nodes[i].ref  ? (int)(nodes[i].ref  - nodes) : -1;
        printf("nodes[%2d] = node{%2d, %2d}\n", i, next, ref);
    }

    node *copy = duplicate(nodes);
    memset(nodes, 0x5a, sizeof(*nodes)*len);

    // Create IDs for the duplicated linked list
    int    count = 0;
    idmap *ids   = 0;
    for (node *n = copy; n; n = n->next) {
        intern(&ids, n, &count);
    }

    puts("output:");
    for (node *n = copy; n; n = n->next) {
        int id   = intern(&ids, n,       0);
        int next = intern(&ids, n->next, 0);
        int ref  = intern(&ids, n->ref,  0);
        printf("nodes[%2d] = node{%2d, %2d}\n", id, next, ref);
    }
}