9 #define ROUNDUP(x,y) ((((x)+(y)-1)/(y))*(y))
12 typedef __uint32_t bitfield_type;
13 #define BITS_PER_BITFIELD 32
14 #define BITS_PER_BITFIELD_LOG 5
16 #define BIT_SET(set, d) \
17 ( (void) ( set[d >> BITS_PER_BITFIELD_LOG] |= (1 << (d & (BITS_PER_BITFIELD-1))) ) )
18 #define BIT_ISSET(set, d) \
19 (!(! ( set[d >> BITS_PER_BITFIELD_LOG] & (1 << (d & (BITS_PER_BITFIELD-1))) ) ))
21 int ANY_BITS_SET(bitfield_type *set, size_t elems)
25 for (i = 0; i < elems; i++)
33 typedef __uint32_t art_id;
38 cmpstring_p_pp(const void *p1, const void *p2)
40 return strcasecmp((char * const) p1, * (char * const *) p2);
46 int main(int argc, char **argv)
52 size_t title_blob_len;
55 art_id titles_read = 0;
69 bitfield_type *titles_seen;
70 bitfield_type *titles_prev_round;
71 bitfield_type *titles_this_round;
72 size_t titles_bitfield_elems;
73 size_t titles_bitfield_bytes;
77 printf("Supply article name to look up articles linking to it.\n");
83 * Read all incoming links into memory
86 in_file = fopen("links-incoming.bin", "rb");
87 fseek(in_file, 0, SEEK_END);
88 link_blob_len = ftell(in_file);
90 printf("Link blob size: %zd bytes.\n", link_blob_len);
92 link_blob = malloc(link_blob_len);
94 printf("Failed to allocate memory.\n");
98 if (link_blob_len != fread(link_blob, 1, link_blob_len, in_file)) {
99 printf("Failed to read entire file in one go.\n");
102 printf("Link blob read (%zd bytes).\n", ftell(in_file));
108 linki = malloc(titles * sizeof(art_id*));
109 linkis = malloc(titles * sizeof(art_id));
111 for (i = 0; i < titles; i++) {
114 linkis[i] = *link_blob;
117 linki[i] = link_blob;
118 link_blob += linkis[i];
120 printf("Incoming links prepared.\n");
127 * Read all titles into memory
132 in_file = fopen("titles-sorted.txt", "r");
133 fseek(in_file, 0, SEEK_END);
134 title_blob_len = ftell(in_file);
136 printf("Title blob size: %zd bytes.\n", title_blob_len);
138 title_blob = malloc(title_blob_len + 1);
140 printf("Failed to allocate memory.\n");
144 if (title_blob_len != fread(title_blob, 1, title_blob_len, in_file)) {
145 printf("Failed to read entire file in one go.\n");
148 printf("Title blob read (%zd bytes).\n", ftell(in_file));
151 title_blob[title_blob_len] = '\0';
153 title = malloc((titles + 1) * sizeof(title[0]));
155 title[0] = title_blob;
157 while (title_blob = strchr(title_blob, '\n')) {
158 title_blob[0] = '\0';
160 title[titles_read] = title_blob;
164 /* Last title will be an empty string, as the file ends with a newline. */
165 printf("Titles prepared: %d of %d.\n", titles_read - 1, titles);
170 /* Look up article ID */
171 cur_title = bsearch(argv[1], title,
172 titles, sizeof(title[0]),
176 printf("TITLE NOT FOUND: %s\n", argv[1]);
180 title_id = cur_title - title;
184 /* Print first degree incoming edges */
185 printf("Article %zd (%s) is linked from %zd articles:\n", title_id, title[title_id], linkis[title_id]);
186 for (i = 0; i < linkis[title_id]; i++) {
187 art_id x = linki[title_id][i];
188 printf(" %s\n", title[x]);
194 printf("\n\n\n\nBuilding table of distances...\n\n");
196 titles_bitfield_elems = ROUNDUP(titles / BITS_PER_BITFIELD, BITS_PER_BITFIELD);
197 titles_bitfield_bytes = titles_bitfield_elems * sizeof(bitfield_type);
201 titles_seen = calloc(titles_bitfield_bytes, 1);
202 titles_prev_round = NULL;
203 titles_this_round = calloc(titles_bitfield_bytes, 1);
207 BIT_SET(titles_seen, title_id);
208 BIT_SET(titles_this_round, title_id);
210 while (ANY_BITS_SET(titles_this_round, titles_bitfield_elems)) {
214 printf("Checking distance %d\n", cur_dist);
216 free(titles_prev_round); /* free is safe to call on NULL */
217 titles_prev_round = titles_this_round;
218 titles_this_round = calloc(titles_bitfield_bytes, 1);
220 for (i = 0; i < titles; i++) {
223 if (!BIT_ISSET(titles_prev_round, i))
226 for (j = 0; j < linkis[i]; j++) {
227 art_id x = linki[i][j];
228 BIT_SET(titles_this_round, x);
232 for (i = 0; i < titles_bitfield_elems; i++) {
233 titles_this_round[i] &= ~titles_seen[i];
234 titles_seen[i] |= titles_this_round[i];
238 /* Result is in titles_prev_round */
242 printf("\n\n\nThe articles with the distance of %zd are:\n\n", cur_dist);
243 for (i = 0; i < titles; i++) {
244 if (BIT_ISSET(titles_prev_round, i)) {
245 printf(" %s\n", title[i]);
251 free(titles_prev_round);
252 free(titles_this_round);