diff options
author | norly <ny-git@enpas.org> | 2019-07-14 14:22:25 +0200 |
---|---|---|
committer | norly <ny-git@enpas.org> | 2019-07-14 14:22:25 +0200 |
commit | 89888270cfd98da4a3dff5fb3ec349adc705f175 (patch) | |
tree | 280bce5b318f97b710147a32194f190a9eafca2a /lookup-incoming.c | |
parent | 6416cb45c442bf3a714c02094387c40eae88faba (diff) |
Generalise bitfield type
No speed improvement to speak of, but this allows further experiments
Diffstat (limited to 'lookup-incoming.c')
-rw-r--r-- | lookup-incoming.c | 33 |
1 files changed, 19 insertions, 14 deletions
diff --git a/lookup-incoming.c b/lookup-incoming.c index c312518..8223feb 100644 --- a/lookup-incoming.c +++ b/lookup-incoming.c @@ -8,16 +8,19 @@ #define ROUNDUP(x,y) ((((x)+(y)-1)/(y))*(y)) + +typedef __uint32_t bitfield_type; + #define BIT_SET(set, d) \ - ( (void) ( set[d >> 3] |= (1 << (d & 7)) ) ) + ( (void) ( set[d >> 5] |= (1 << (d & 31)) ) ) #define BIT_ISSET(set, d) \ - (!(! ( set[d >> 3] & (1 << (d & 7)) ) )) + (!(! ( set[d >> 5] & (1 << (d & 31)) ) )) -int ANY_BITS_SET(unsigned char *set, size_t bytes) +int ANY_BITS_SET(bitfield_type *set, size_t elems) { size_t i; - for (i = 0; i < bytes; i++) + for (i = 0; i < elems; i++) if (set[i] != 0) return 1; @@ -61,10 +64,11 @@ int main(int argc, char **argv) art_id i; - unsigned char *titles_seen; - unsigned char *titles_prev_round; - unsigned char *titles_this_round; - size_t titles_bitfield_len; + bitfield_type *titles_seen; + bitfield_type *titles_prev_round; + bitfield_type *titles_this_round; + size_t titles_bitfield_elems; + size_t titles_bitfield_bytes; if (argc < 2) { @@ -187,18 +191,19 @@ int main(int argc, char **argv) printf("\n\n\n\nBuilding table of distances...\n\n"); - titles_bitfield_len = ROUNDUP(titles / 8, sizeof(size_t)); + titles_bitfield_elems = ROUNDUP(titles / 8 / sizeof(bitfield_type), sizeof(bitfield_type)); + titles_bitfield_bytes = titles_bitfield_elems * sizeof(bitfield_type); - titles_seen = calloc(titles_bitfield_len, 1); + titles_seen = calloc(titles_bitfield_bytes, 1); titles_prev_round = NULL; - titles_this_round = calloc(titles_bitfield_len, 1); + titles_this_round = calloc(titles_bitfield_bytes, 1); cur_dist = 0; BIT_SET(titles_seen, title_id); BIT_SET(titles_this_round, title_id); - while (ANY_BITS_SET(titles_this_round, titles_bitfield_len)) { + while (ANY_BITS_SET(titles_this_round, titles_bitfield_elems)) { art_id i; cur_dist++; @@ -206,7 +211,7 @@ int main(int argc, char **argv) free(titles_prev_round); /* free is safe to call on NULL */ titles_prev_round = titles_this_round; - titles_this_round = calloc(titles_bitfield_len, 1); + titles_this_round = calloc(titles_bitfield_bytes, 1); for (i = 0; i < titles; i++) { int j; @@ -220,7 +225,7 @@ int main(int argc, char **argv) } } - for (i = 0; i < titles_bitfield_len; i++) { + for (i = 0; i < titles_bitfield_elems; i++) { titles_this_round[i] &= ~titles_seen[i]; titles_seen[i] |= titles_this_round[i]; } |