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