#include #include #include #define MAX 0x191A // Magic number, my secret /* Convert computer name to single number that is used as index to * nodes array and basically for everything. Working with strings is * not optimal. * * "ta" Computer name. * 0x74 0x61 Each character number in ASCII. * 0x13 0x00 Only a-z are used, subtract 'a' to have range from 0 to 25. * 0x1300 Combine bytes together into single integer. */ #define INDEXOF(a) (((a)[0] - 'a') << 8) | ((a)[1] - 'a') // Find ID that originally started with character 't' #define IS_CHIEF(a) (((a) >> 8) == 0x13) struct node { int child; struct node *next; // Good old linked list }; static struct node *nodes[MAX]={0}; // [parent_index] static int connections[4096][3]; // [ci][computer1,computer2,computer3] static int ci=0; // Connections index static void nodes_add(int parent, int child) { struct node *node = nodes[parent]; if (!node) { nodes[parent] = malloc(sizeof *node); // Let it leak... nodes[parent]->child = child; nodes[parent]->next = 0; return; } if (node->child == child) { return; // Avoid duplicates } while (node->next) { node = node->next; if (node && node->child == child) { return; // Avoid duplicates } } node->next = malloc(sizeof *node); // Memory never bothered me anyway node->next->child = child; node->next->next = 0; } static int nodes_size(int parent) { struct node *node = nodes[parent]; int n; for (n=0; node; n++) node = node->next; return n; } static int nodes_get_child_by_index(int parent, int n) { struct node *node = nodes[parent]; for (; n && node->next; n--) node = node->next; return n == 0 && node ? node->child : -1; } static int nodes_child_indexof(int parent, int child) { struct node *node = nodes[parent]; int i; for (i=0; node; i++, node=node->next) { if (node->child == child) { return i; } } return -1; } static int compar(const void *a, const void *b) { return *(int*)a - *(int*)b; } static void connections_add(int one, int two, int three) { int i, connection[3]; // Ignore connections without Chief computer ID if (!(IS_CHIEF(one) || IS_CHIEF(two) || IS_CHIEF(three))) { return; } // Sort IDs in order to easily detect duplicates connection[0] = one; connection[1] = two; connection[2] = three; qsort(connection, 3, sizeof(int), &compar); // Skip duplicates for (i=0; i 0) { i = INDEXOF(a); j = INDEXOF(b); nodes_add(i, j); nodes_add(j, i); } for (i=0; i