Obsessbook

/* A module for computing the DERPCON metric between two users. */

typedef struct user_struct user;

struct user_struct {
        int     user_ID;
        char    *name;
        char    *account_handle;
        int     number_of_BFFs;
        user    **BFF_list;
        int     scratch;
};

int DERPCON(user x, user y);
void visit_user(hashtable_t *table, const user *u, int distance_to_u);
int derpcon_hashfunc(const char *key);

#include "hashtable.h"
#include "derpcon.h"

#define INFINITY -1

/* A module for computing the DERPCON metric between two users.
 *
 * A robust implementation must be reentrant, so we will treat the graph of
 * users as immutable.
 *
 * To keep track of which parts of the graph we've already visited, and how far
 * away in the graph each user is, we'll use a hash table. Starting at user x,
 * we traverse the graph recursively, noting in the hash table the shortest
 * distance to every reachable user.
 *
 * Then we simply read out the distance to user y and compute the corresponding
 * DERPCON value.
 */

int DERPCON(user x, user y) {
        hashtable_t hashtable;
        int distance = INFINITY;

        hashtable_init(&hashtable, derpcon_hashfunc);
        visit_user(&hashtable, &x, 0);
        hashtable_get(&hashtable, y.account_handle, &distance);
        hashtable_free(&hashtable);

        if(distance == INFINITY) {
                return 0;       /* No path exists. */
        } else if(distance == 0) {
                return 1;       /* DERPCON to self is 1. */
        } else {
                return distance;
        }
}

/*
 * Traverse the user graph recursively, marking distances in a hash table. When
 * a shorter path is discovered, the corresponding hash table entry is updated.
 */

void visit_user(hashtable_t *hashtable, const user *u, int distance_to_u) {
        int i;
        int known_distance = INFINITY;

        hashtable_get(hashtable, u->account_handle, &known_distance);
        if(known_distance == INFINITY || known_distance > distance_to_u) {
                hashtable_update(hashtable, u->account_handle, &distance_to_u);
                for(i = 0; i < u->number_of_BFFs; i++) {
                        visit_user(hashtable, u->BFF_list[i], distance_to_u + 1);
                }
        }
}

/* A simple hash function; fast but with adequate distribution properties. */

int derpcon_hashfunc(const char *key) {
        int hash = 0, factor = 1, i;

        for(i = 0; key[i]; i++) {
                hash += factor * (unsigned char) key[i];
                factor *= 2;
        }
        return hash;
}

/* Generic string-to-anything hash table implementation.
 *
 * For performance reasons, the first entry of each chain is kept inside the
 * table itself. This removes one pointer-lookup per access, and helps keep as
 * much as possible of the table within the cache. 
 */

/* Configure the hash table here. */

#define BUCKETS 1024
typedef int value_t;

/* End of configuration section. */

typedef struct entry {
        value_t         value;
        char            *key;
        struct entry    *next;
} entry_t;

typedef int (*hashfunc_t)(const char *key);

typedef struct {
        /* Useful for profiling. */
        int             collisions;

        /* User-supplied hash function. */
        hashfunc_t      hash;

        /* The first entry of each chain. */
        entry_t         table[BUCKETS];
} hashtable_t;

void hashtable_init(hashtable_t *ht, hashfunc_t hash);
void hashtable_free(hashtable_t *ht);
void hashtable_get(const hashtable_t *ht, const char *key, value_t *value);
void hashtable_update(hashtable_t *ht, const char *key, const value_t *value);

/* Generic string-to-anything hash table implementation. */

#include <stdlib.h>
#include <string.h>

#include "hashtable.h"

/* Prepare an empty table and install a callback function for computing hashes. */

void hashtable_init(hashtable_t *ht, hashfunc_t hash) {
        memset(ht, 0, sizeof(hashtable_t));
        ht->hash = hash;
}

/* Free dynamic memory used by a hash table. */

void hashtable_free(hashtable_t *ht) {
        int i;
        struct entry *e, *next;

        for(i = 0; i < BUCKETS; i++) {
                free(ht->table[i].key);
                for(e = ht->table[i].next; e; e = next) {
                        next = e->next;
                        free(e->key);
                        free(e);
                }
        }
        memset(ht, 0, sizeof(hashtable_t));
}

/* Retrieve an entry from a hash table. If no entry exists, the output variable
 * is left unmodified, so it should be prepared with a default value.
 */

void hashtable_get(const hashtable_t *ht, const char *key, value_t *value) {
        const struct entry *e;

        for(e = &ht->table[ht->hash(key) % BUCKETS]; e->key; e = e->next) {
                if(!strcmp(e->key, key)) {
                        *value = e->value;
                        return;
                }
        }
}

/* Store an entry into a hash table. If an entry already exists, it is replaced. */

void hashtable_update(hashtable_t *ht, const char *key, const value_t *value) {
        struct entry *e, **lastptr;

        e = &ht->table[ht->hash(key) % BUCKETS];
        if(!e->key) {
                /* This chain is empty. Use the first slot. */
                e->key = strdup(key);
                e->value = *value;
        } else {
                do {
                        if(!strcmp(e->key, key)) {
                                e->value = *value;
                                return;
                        }
                        lastptr = &e->next;
                        e = e->next;
                } while(e);
                /* End of chain reached. Add a new entry. */
                e = calloc(1, sizeof(struct entry));
                e->key = strdup(key);
                e->value = *value;
                *lastptr = e;
                ht->collisions++;
        }
}