lookup-incoming.c

   1 #include <assert.h>
   2 #include <ctype.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6 #include <sys/types.h>
   7
   8
   9 #define ROUNDUP(x,y) ((((x)+(y)-1)/(y))*(y))
  10
  11
  12 typedef __uint32_t bitfield_type;
  13 #define BITS_PER_BITFIELD 32
  14 #define BITS_PER_BITFIELD_LOG 5
  15
  16 #define BIT_SET(set, d) \
  17   ( (void) ( set[d >> BITS_PER_BITFIELD_LOG] |= (1 << (d & (BITS_PER_BITFIELD-1))) ) )
  18 #define BIT_ISSET(set, d) \
  19   (!(! ( set[d >> BITS_PER_BITFIELD_LOG] & (1 << (d & (BITS_PER_BITFIELD-1))) ) ))
  20
  21 int ANY_BITS_SET(bitfield_type *set, size_t elems)
  22 {
  23         size_t i;
  24
  25         for (i = 0; i < elems; i++)
  26                 if (set[i] != 0)
  27                         return 1;
  28
  29         return 0;
  30 }
  31
  32
  33 typedef __uint32_t art_id;
  34
  35
  36
  37 static int
  38 cmpstring_p_pp(const void *p1, const void *p2)
  39 {
  40         return strcasecmp((char * const) p1, * (char * const *) p2);
  41 }
  42
  43
  44
  45
  46 int main(int argc, char **argv)
  47 {
  48         FILE *in_file;
  49         FILE *out_file;
  50
  51         char *title_blob;
  52         size_t title_blob_len;
  53         char **title = NULL;
  54         art_id titles;
  55         art_id titles_read = 0;
  56
  57         art_id *link_blob;
  58         size_t link_blob_len;
  59         art_id **linki;
  60         art_id *linkis;
  61
  62         char **cur_title;
  63         art_id title_id;
  64
  65         art_id cur_dist;
  66
  67         art_id i;
  68
  69         bitfield_type *titles_seen;
  70         bitfield_type *titles_prev_round;
  71         bitfield_type *titles_this_round;
  72         size_t titles_bitfield_elems;
  73         size_t titles_bitfield_bytes;
  74
  75
  76         if (argc < 2) {
  77                 printf("Supply article name to look up articles linking to it.\n");
  78                 return 1;
  79         }
  80
  81
  82         /*
  83          * Read all incoming links into memory
  84          */
  85
  86         in_file = fopen("links-incoming.bin", "rb");
  87         fseek(in_file, 0, SEEK_END);
  88         link_blob_len = ftell(in_file);
  89         rewind(in_file);
  90         printf("Link blob size: %zd bytes.\n", link_blob_len);
  91
  92         link_blob = malloc(link_blob_len);
  93         if (!link_blob) {
  94                 printf("Failed to allocate memory.\n");
  95                 return 1;
  96         }
  97
  98         if (link_blob_len != fread(link_blob, 1, link_blob_len, in_file)) {
  99                 printf("Failed to read entire file in one go.\n");
 100                 return 1;
 101         }
 102         printf("Link blob read (%zd bytes).\n", ftell(in_file));
 103         fclose(in_file);
 104
 105         titles = *link_blob;
 106         link_blob++;
 107
 108         linki = malloc(titles * sizeof(art_id*));
 109         linkis = malloc(titles * sizeof(art_id));
 110
 111         for (i = 0; i < titles; i++) {
 112                 art_id j;
 113
 114                 linkis[i] = *link_blob;
 115                 link_blob++;
 116
 117                 linki[i] = link_blob;
 118                 link_blob += linkis[i];
 119         }
 120         printf("Incoming links prepared.\n");
 121
 122
 123
 124
 125
 126         /*
 127          * Read all titles into memory
 128          */
 129
 130
 131
 132         in_file = fopen("titles-sorted.txt", "r");
 133         fseek(in_file, 0, SEEK_END);
 134         title_blob_len = ftell(in_file);
 135         rewind(in_file);
 136         printf("Title blob size: %zd bytes.\n", title_blob_len);
 137
 138         title_blob = malloc(title_blob_len + 1);
 139         if (!title_blob) {
 140                 printf("Failed to allocate memory.\n");
 141                 return 1;
 142         }
 143
 144         if (title_blob_len != fread(title_blob, 1, title_blob_len, in_file)) {
 145                 printf("Failed to read entire file in one go.\n");
 146                 return 1;
 147         }
 148         printf("Title blob read (%zd bytes).\n", ftell(in_file));
 149         fclose(in_file);
 150
 151         title_blob[title_blob_len] = '\0';
 152
 153         title = malloc((titles + 1) * sizeof(title[0]));
 154
 155         title[0] = title_blob;
 156         titles_read = 1;
 157         while (title_blob = strchr(title_blob, '\n')) {
 158                 title_blob[0] = '\0';
 159                 title_blob++;
 160                 title[titles_read] = title_blob;
 161                 titles_read++;
 162         }
 163
 164         /* Last title will be an empty string, as the file ends with a newline. */
 165         printf("Titles prepared: %d of %d.\n", titles_read - 1, titles);
 166
 167
 168
 169
 170         /* Look up article ID */
 171         cur_title = bsearch(argv[1], title,
 172                                 titles, sizeof(title[0]),
 173                                 cmpstring_p_pp);
 174
 175         if (!cur_title) {
 176                 printf("TITLE NOT FOUND: %s\n", argv[1]);
 177                 return 1;
 178         }
 179
 180         title_id = cur_title - title;
 181
 182
 183         #if 0
 184         /* Print first degree incoming edges */
 185         printf("Article %zd (%s) is linked from %zd articles:\n", title_id, title[title_id], linkis[title_id]);
 186         for (i = 0; i < linkis[title_id]; i++) {
 187                 art_id x = linki[title_id][i];
 188                 printf("  %s\n", title[x]);
 189         }
 190         #endif
 191
 192
 193
 194         printf("\n\n\n\nBuilding table of distances...\n\n");
 195
 196         titles_bitfield_elems = ROUNDUP(titles / BITS_PER_BITFIELD, BITS_PER_BITFIELD);
 197         titles_bitfield_bytes = titles_bitfield_elems * sizeof(bitfield_type);
 198
 199         titles_seen = calloc(titles_bitfield_bytes, 1);
 200         titles_prev_round = NULL;
 201         titles_this_round = calloc(titles_bitfield_bytes, 1);
 202
 203         cur_dist = 0;
 204
 205         BIT_SET(titles_seen, title_id);
 206         BIT_SET(titles_this_round, title_id);
 207
 208         while (ANY_BITS_SET(titles_this_round, titles_bitfield_elems)) {
 209                 art_id i;
 210
 211                 cur_dist++;
 212                 printf("Checking distance %d\n", cur_dist);
 213
 214                 free(titles_prev_round); /* free is safe to call on NULL */
 215                 titles_prev_round = titles_this_round;
 216                 titles_this_round = calloc(titles_bitfield_bytes, 1);
 217
 218                 for (i = 0; i < titles; i++) {
 219                         int j;
 220
 221                         if (!BIT_ISSET(titles_prev_round, i))
 222                                 continue;
 223
 224                         for (j = 0; j < linkis[i]; j++) {
 225                                 art_id x = linki[i][j];
 226                                 BIT_SET(titles_this_round, x);
 227                         }
 228                 }
 229
 230                 for (i = 0; i < titles_bitfield_elems; i++) {
 231                         titles_this_round[i] &= ~titles_seen[i];
 232                         titles_seen[i] |= titles_this_round[i];
 233                 }
 234         }
 235
 236         /* Result is in titles_prev_round */
 237
 238         cur_dist -= 1;
 239
 240         printf("\n\n\nThe articles with the distance of %zd are:\n\n", cur_dist);
 241         for (i = 0; i < titles; i++) {
 242                 if (BIT_ISSET(titles_prev_round, i)) {
 243                         printf("  %s\n", title[i]);
 244                 }
 245         }
 246
 247
 248         return 0;
 249 }