12 #define ROUNDUP(x,y) ((((x)+(y)-1)/(y))*(y))
14 typedef __uint32_t bitfield_type;
15 #define BITS_PER_BITFIELD 32
16 #define BITS_PER_BITFIELD_LOG 5
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))) ) ))
23 int ANY_BITS_SET(bitfield_type *set, size_t elems)
27 for (i = 0; i < elems; i++)
39 typedef __uint32_t art_id;
43 cmpstring_p_pp(const void *p1, const void *p2)
45 return strcasecmp((char * const) p1, * (char * const *) p2);
49 void* load_file(char *path)
55 in_file = fopen(path, "rb");
57 fseek(in_file, 0, SEEK_END);
58 blob_len = ftell(in_file);
60 printf(" blob size: %zd bytes.\n", blob_len);
62 blob = malloc(blob_len);
64 printf("Failed to allocate memory.\n");
68 if (blob_len != fread(blob, 1, blob_len, in_file)) {
69 printf("Failed to read entire file in one go.\n");
73 printf(" blob read :%zd bytes.\n", ftell(in_file));
84 int main(int argc, char **argv)
93 art_id titles_read = 0;
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;
110 printf("Supply article name to look up articles linking to it.\n");
115 /* Read all incoming links into memory */
116 link_blob = load_file("links-incoming.bin");
124 linki = malloc(titles * sizeof(art_id*));
125 linkis = malloc(titles * sizeof(art_id));
127 for (i = 0; i < titles; i++) {
128 linkis[i] = *link_blob;
131 linki[i] = link_blob;
132 link_blob += linkis[i];
134 printf("Incoming links parsed: %d\n", titles);
137 /* Read all titles into memory */
138 title_blob = load_file("titles-sorted.txt");
143 title = malloc((titles + 1) * sizeof(title[0]));
145 title[0] = title_blob;
147 while ((title_blob = strchr(title_blob, '\n'))) {
148 title_blob[0] = '\0';
151 if (title_blob[0] == '\0')
152 /* Reached empty line at end of file */
155 title[titles_read] = title_blob;
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);
163 /* Look up article ID */
164 cur_title = bsearch(argv[1], title,
165 titles, sizeof(title[0]),
169 printf("TITLE NOT FOUND: %s\n", argv[1]);
173 title_id = cur_title - title;
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]);
187 printf("\n\n\n\nFlooding graph...\n\n");
189 titles_bitfield_elems = ROUNDUP(titles / BITS_PER_BITFIELD, BITS_PER_BITFIELD);
190 titles_bitfield_bytes = titles_bitfield_elems * sizeof(bitfield_type);
194 titles_seen = calloc(titles_bitfield_bytes, 1);
195 titles_prev_round = NULL;
196 titles_this_round = calloc(titles_bitfield_bytes, 1);
200 BIT_SET(titles_seen, title_id);
201 BIT_SET(titles_this_round, title_id);
203 while (ANY_BITS_SET(titles_this_round, titles_bitfield_elems)) {
207 printf("Checking distance %d\n", cur_dist);
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);
213 for (i = 0; i < titles; i++) {
216 if (!BIT_ISSET(titles_prev_round, i))
219 for (j = 0; j < linkis[i]; j++) {
220 art_id x = linki[i][j];
221 BIT_SET(titles_this_round, x);
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];
231 /* Result is now in titles_prev_round */
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]);
244 free(titles_prev_round);
245 free(titles_this_round);