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