From 89888270cfd98da4a3dff5fb3ec349adc705f175 Mon Sep 17 00:00:00 2001 From: norly Date: Sun, 14 Jul 2019 14:22:25 +0200 Subject: [PATCH] Generalise bitfield type No speed improvement to speak of, but this allows further experiments --- lookup-incoming.c | 33 +++++++++++++++++++-------------- 1 file 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]; } -- 2.30.2