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 = NULL;
  47         art_id titles;
  48         art_id titles_read = 0;
  49
  50         art_id **linki;
  51         art_id *linkis;
  52
  53         char **cur_title;
  54         art_id title_id;
  55
  56         art_id cur_dist;
  57
  58         art_id i;
  59
  60         unsigned char *titles_seen;
  61         unsigned char *titles_prev_round;
  62         unsigned char *titles_this_round;
  63         size_t titles_bitfield_len;
  64
  65
  66         if (argc < 2) {
  67                 printf("Supply article name to look up articles linking to it.\n");
  68                 return 1;
  69         }
  70
  71
  72         /*
  73          * Read all incoming links into memory
  74          */
  75
  76         in_file = fopen("links-incoming.bin", "rb");
  77
  78         fread(&titles, sizeof(titles), 1, in_file);
  79
  80         linki = malloc(titles * sizeof(art_id*));
  81         linkis = malloc(titles * sizeof(art_id));
  82
  83         for (i = 0; i < titles; i++) {
  84                 art_id j;
  85
  86                 fread(&linkis[i], sizeof(linkis[i]), 1, in_file);
  87                 //printf("linkis[%zd] = %zd\n", i, linkis[i]);
  88
  89                 linki[i] = malloc(linkis[i] * sizeof(linki[i][0]));
  90
  91                 j = fread(linki[i], sizeof(linki[i][0]), linkis[i], in_file);
  92                 assert(j == linkis[i]);
  93                 //for (j = 0; j < linkis[i]; j++) {
  94                 //      fread(&linki[i][j], sizeof(linki[i][j]), 1, in_file);
  95                 //}
  96         }
  97         printf("Incoming links read (%zd bytes).\n", ftell(in_file));
  98         fclose(in_file);
  99
 100
 101
 102
 103         /*
 104          * Read all titles into memory
 105          */
 106
 107         title = malloc(titles * sizeof(title[0]));
 108
 109         in_file = fopen("titles-sorted.txt", "r");
 110         while (!feof(in_file)) {
 111                 char *in_line = NULL;
 112                 ssize_t in_line_len = 0;
 113                 size_t zero = 0;
 114
 115                 in_line_len = getline(&in_line, &zero, in_file);
 116
 117                 /* Ignore empty lines and errors */
 118                 if (in_line_len < 2) {
 119                         continue;
 120                 }
 121
 122                 /* Delete trailing newline */
 123                 in_line[in_line_len - 1] = '\0';
 124
 125                 title[titles_read] = in_line;
 126                 titles_read++;
 127         }
 128         fclose(in_file);
 129
 130         printf("Titles read.\n");
 131
 132
 133
 134
 135         /* Look up article ID */
 136         cur_title = bsearch(argv[1], title,
 137                                 titles, sizeof(title[0]),
 138                                 cmpstring_p_pp);
 139
 140         if (!cur_title) {
 141                 printf("TITLE NOT FOUND: %s\n", argv[1]);
 142                 return 1;
 143         }
 144
 145         title_id = cur_title - title;
 146
 147
 148         #if 0
 149         /* Print first degree incoming edges */
 150         printf("Article %zd (%s) is linked from %zd articles:\n", title_id, title[title_id], linkis[title_id]);
 151         for (i = 0; i < linkis[title_id]; i++) {
 152                 art_id x = linki[title_id][i];
 153                 printf("  %s\n", title[x]);
 154         }
 155         #endif
 156
 157
 158
 159         printf("\n\n\n\nBuilding table of distances...\n\n");
 160
 161         titles_bitfield_len = ROUNDUP(titles / 8, sizeof(size_t));
 162
 163         titles_seen = calloc(titles_bitfield_len, 1);
 164         titles_prev_round = NULL;
 165         titles_this_round = calloc(titles_bitfield_len, 1);
 166
 167         cur_dist = 0;
 168
 169         BIT_SET(titles_seen, title_id);
 170         BIT_SET(titles_this_round, title_id);
 171
 172         while (ANY_BITS_SET(titles_this_round, titles_bitfield_len)) {
 173                 art_id i;
 174
 175                 cur_dist++;
 176                 printf("Checking distance %d\n", cur_dist);
 177
 178                 free(titles_prev_round); /* free is safe to call on NULL */
 179                 titles_prev_round = titles_this_round;
 180                 titles_this_round = calloc(titles_bitfield_len, 1);
 181
 182                 for (i = 0; i < titles; i++) {
 183                         int j;
 184
 185                         if (!BIT_ISSET(titles_prev_round, i))
 186                                 continue;
 187
 188                         for (j = 0; j < linkis[i]; j++) {
 189                                 art_id x = linki[i][j];
 190                                 BIT_SET(titles_this_round, x);
 191                         }
 192                 }
 193
 194                 for (i = 0; i < titles_bitfield_len; i++) {
 195                         titles_this_round[i] &= ~titles_seen[i];
 196                         titles_seen[i] |= titles_this_round[i];
 197                 }
 198         }
 199
 200         /* Result is in titles_prev_round */
 201
 202         cur_dist -= 1;
 203
 204         printf("\n\n\nThe articles with the distance of %zd are:\n\n", cur_dist);
 205         for (i = 0; i < titles; i++) {
 206                 if (BIT_ISSET(titles_prev_round, i)) {
 207                         printf("  %s\n", title[i]);
 208                 }
 209         }
 210
 211
 212         return 0;
 213 }