diff options
Diffstat (limited to 'test')
-rw-r--r-- | test/monniaux/binary_search/Makefile | 26 | ||||
-rw-r--r-- | test/monniaux/binary_search/binary_search.c | 52 |
2 files changed, 78 insertions, 0 deletions
diff --git a/test/monniaux/binary_search/Makefile b/test/monniaux/binary_search/Makefile new file mode 100644 index 00000000..7739e4ca --- /dev/null +++ b/test/monniaux/binary_search/Makefile @@ -0,0 +1,26 @@ +include ../rules.mk + +PRODUCTS=binary_search.gcc.host.out binary_search.ccomp.host.out \ + binary_search.gcc.k1c.out binary_search.ccomp.k1c.out \ + binary_search.gcc.k1c.s binary_search.ccomp.k1c.s + +all: $(PRODUCTS) + +binary_search.gcc.host.s binary_search.ccomp.host.s binary_search.gcc.k1c.s binary_search.ccomp.k1c.s : ../clock.h + +binary_search.ccomp.host: binary_search.ccomp.host.o ../clock.gcc.host.o + $(CCOMP) $(CCOMPFLAGS) $+ -o $@ + +binary_search.gcc.host: binary_search.gcc.host.o ../clock.gcc.host.o + $(CC) $(CFLAGS) $+ -o $@ + +binary_search.gcc.k1c: binary_search.gcc.k1c.o ../clock.gcc.k1c.o + $(K1C_CC) $(K1C_CFLAGS) $+ -o $@ + +binary_search.ccomp.k1c: binary_search.ccomp.k1c.o ../clock.gcc.k1c.o + $(K1C_CCOMP) $(K1C_CCOMPFLAGS) $+ -o $@ + +clean: + -rm -f *.o *.s *.k1c + +.PHONY: clean diff --git a/test/monniaux/binary_search/binary_search.c b/test/monniaux/binary_search/binary_search.c new file mode 100644 index 00000000..9b54f28d --- /dev/null +++ b/test/monniaux/binary_search/binary_search.c @@ -0,0 +1,52 @@ +#include <stdio.h> +#include <stdlib.h> +#include <inttypes.h> +#include "../clock.h" + +typedef int data; +typedef int index; + +int my_bsearch (data *a, index n, data x) { + index i = 0, j = n - 1; + while (i <= j) { + index k = (i + j) / 2; + if (a[k] == x) { + return k; + } + else if (a[k] < x) { + i = k + 1; + } + else { + j = k - 1; + } + } + return -1; +} + +void random_ascending_fill(data *a, index n) { + unsigned r = 41; + data v = 0; + for(index i=0; i<n; i++) { + a[i] = v; + v++; + if (r & 0x40000000) v++; + r = r * 97 + 5; + } +} + +int main () { + index n=5000; + data *buf=malloc(n*sizeof(data)); + + cycle_t timestamp1 = get_current_cycle(); + random_ascending_fill(buf, n); + timestamp1 = get_current_cycle()-timestamp1; + + cycle_t timestamp2 = get_current_cycle(); + index pos = my_bsearch(buf, n, 1501); + timestamp2 = get_current_cycle()-timestamp2; + + printf("position: %d\nrandom fill cycles: %" PRIu64 "\nsearch cycles: %" PRIu64 "\n", pos, timestamp1, timestamp2); + + free(buf); +} |