--- /dev/null
+#include <assert.h>
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/types.h>
+
+
+#define ROUNDUP(x,y) ((((x)+(y)-1)/(y))*(y))
+
+
+typedef __uint32_t bitfield_type;
+#define BITS_PER_BITFIELD 32
+#define BITS_PER_BITFIELD_LOG 5
+
+#define BIT_SET(set, d) \
+ ( (void) ( set[d >> BITS_PER_BITFIELD_LOG] |= (1 << (d & (BITS_PER_BITFIELD-1))) ) )
+#define BIT_ISSET(set, d) \
+ (!(! ( set[d >> BITS_PER_BITFIELD_LOG] & (1 << (d & (BITS_PER_BITFIELD-1))) ) ))
+
+int ANY_BITS_SET(bitfield_type *set, size_t elems)
+{
+ size_t i;
+
+ for (i = 0; i < elems; i++)
+ if (set[i] != 0)
+ return 1;
+
+ return 0;
+}
+
+
+typedef __uint32_t art_id;
+
+
+
+static int
+cmpstring_p_pp(const void *p1, const void *p2)
+{
+ return strcasecmp((char * const) p1, * (char * const *) p2);
+}
+
+
+
+
+int main(int argc, char **argv)
+{
+ FILE *in_file;
+ FILE *out_file;
+
+ char *title_blob;
+ size_t title_blob_len;
+ char **title = NULL;
+ art_id titles;
+ art_id titles_read = 0;
+
+ art_id *link_blob;
+ size_t link_blob_len;
+ art_id **linki;
+ art_id *linkis;
+
+ char **cur_title;
+ art_id title_id;
+
+ art_id cur_dist;
+
+ art_id i;
+
+ bitfield_type *titles_seen;
+ bitfield_type *titles_prev_round;
+ bitfield_type *titles_this_round;
+ size_t titles_bitfield_elems;
+ size_t titles_bitfield_bytes;
+
+
+ if (argc < 2) {
+ printf("Supply article name to look up articles linking to it.\n");
+ return 1;
+ }
+
+
+ /*
+ * Read all incoming links into memory
+ */
+
+ in_file = fopen("links-incoming.bin", "rb");
+ fseek(in_file, 0, SEEK_END);
+ link_blob_len = ftell(in_file);
+ rewind(in_file);
+ printf("Link blob size: %zd bytes.\n", link_blob_len);
+
+ link_blob = malloc(link_blob_len);
+ if (!link_blob) {
+ printf("Failed to allocate memory.\n");
+ return 1;
+ }
+
+ if (link_blob_len != fread(link_blob, 1, link_blob_len, in_file)) {
+ printf("Failed to read entire file in one go.\n");
+ return 1;
+ }
+ printf("Link blob read (%zd bytes).\n", ftell(in_file));
+ fclose(in_file);
+
+ titles = *link_blob;
+ link_blob++;
+
+ linki = malloc(titles * sizeof(art_id*));
+ linkis = malloc(titles * sizeof(art_id));
+
+ for (i = 0; i < titles; i++) {
+ art_id j;
+
+ linkis[i] = *link_blob;
+ link_blob++;
+
+ linki[i] = link_blob;
+ link_blob += linkis[i];
+ }
+ printf("Incoming links prepared.\n");
+
+
+
+
+
+ /*
+ * Read all titles into memory
+ */
+
+
+
+ in_file = fopen("titles-sorted.txt", "r");
+ fseek(in_file, 0, SEEK_END);
+ title_blob_len = ftell(in_file);
+ rewind(in_file);
+ printf("Title blob size: %zd bytes.\n", title_blob_len);
+
+ title_blob = malloc(title_blob_len + 1);
+ if (!title_blob) {
+ printf("Failed to allocate memory.\n");
+ return 1;
+ }
+
+ if (title_blob_len != fread(title_blob, 1, title_blob_len, in_file)) {
+ printf("Failed to read entire file in one go.\n");
+ return 1;
+ }
+ printf("Title blob read (%zd bytes).\n", ftell(in_file));
+ fclose(in_file);
+
+ title_blob[title_blob_len] = '\0';
+
+ title = malloc((titles + 1) * sizeof(title[0]));
+
+ title[0] = title_blob;
+ titles_read = 1;
+ while (title_blob = strchr(title_blob, '\n')) {
+ title_blob[0] = '\0';
+ title_blob++;
+ title[titles_read] = title_blob;
+ titles_read++;
+ }
+
+ /* Last title will be an empty string, as the file ends with a newline. */
+ printf("Titles prepared: %d of %d.\n", titles_read - 1, titles);
+
+
+
+
+ /* Look up article ID */
+ cur_title = bsearch(argv[1], title,
+ titles, sizeof(title[0]),
+ cmpstring_p_pp);
+
+ if (!cur_title) {
+ printf("TITLE NOT FOUND: %s\n", argv[1]);
+ return 1;
+ }
+
+ title_id = cur_title - title;
+
+
+ #if 0
+ /* Print first degree incoming edges */
+ printf("Article %zd (%s) is linked from %zd articles:\n", title_id, title[title_id], linkis[title_id]);
+ for (i = 0; i < linkis[title_id]; i++) {
+ art_id x = linki[title_id][i];
+ printf(" %s\n", title[x]);
+ }
+ #endif
+
+
+
+ printf("\n\n\n\nBuilding table of distances...\n\n");
+
+ titles_bitfield_elems = ROUNDUP(titles / BITS_PER_BITFIELD, BITS_PER_BITFIELD);
+ titles_bitfield_bytes = titles_bitfield_elems * sizeof(bitfield_type);
+
+BENCHMARK:
+
+ titles_seen = calloc(titles_bitfield_bytes, 1);
+ titles_prev_round = NULL;
+ titles_this_round = calloc(titles_bitfield_bytes, 1);
+
+ cur_dist = 0;
+
+ BIT_SET(titles_seen, title_id);
+ BIT_SET(titles_this_round, title_id);
+
+ while (ANY_BITS_SET(titles_this_round, titles_bitfield_elems)) {
+ art_id i;
+
+ cur_dist++;
+ printf("Checking distance %d\n", cur_dist);
+
+ free(titles_prev_round); /* free is safe to call on NULL */
+ titles_prev_round = titles_this_round;
+ titles_this_round = calloc(titles_bitfield_bytes, 1);
+
+ for (i = 0; i < titles; i++) {
+ int j;
+
+ if (!BIT_ISSET(titles_prev_round, i))
+ continue;
+
+ for (j = 0; j < linkis[i]; j++) {
+ art_id x = linki[i][j];
+ BIT_SET(titles_this_round, x);
+ }
+ }
+
+ for (i = 0; i < titles_bitfield_elems; i++) {
+ titles_this_round[i] &= ~titles_seen[i];
+ titles_seen[i] |= titles_this_round[i];
+ }
+ }
+
+ /* Result is in titles_prev_round */
+
+ cur_dist -= 1;
+
+ printf("\n\n\nThe articles with the distance of %zd are:\n\n", cur_dist);
+ for (i = 0; i < titles; i++) {
+ if (BIT_ISSET(titles_prev_round, i)) {
+ printf(" %s\n", title[i]);
+ }
+ }
+
+
+ free(titles_seen);
+ free(titles_prev_round);
+ free(titles_this_round);
+
+ //goto BENCHMARK;
+
+ return 0;
+}
projects / enwiki-links-graph.git / blobdiff