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