#include <stdbool.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include "random.h"
#include "xtimer.h"

#define ARRAY_SIZE (8192)

static uint8_t* alloc_random_array(size_t len) {

	uint8_t* a = malloc(len);

	for (size_t i = 0; i < len; ++i)
		a[i] = (random_uint32() & 0x7F);

	return a;
}

static bool search_naive(uint8_t key, uint8_t* array, size_t len) {

	for (uint8_t* end = array + len; array != end; ++array) {
		if (*array == key)
			return true;
	}

	return false;
}

static bool search_knuth(uint8_t key, uint8_t* array, size_t len) {

	array[len] = key;

	uint8_t* end;
	for (end = array + len; *array != key; ++array);

	return array != end;
}

static void do_benchmark(bool (*search)(uint8_t, uint8_t*, size_t),
			 uint8_t key, uint8_t* array, size_t len, int iterations) {

	unsigned long total_time = 0;

	for (int i = 0; i < iterations; ++i) {
		bool found;
		xtimer_ticks32_t t[2];
		t[0] = xtimer_now();
		found = search(key, array, len);
		t[1] = xtimer_now();

		total_time += t[1].ticks32 - t[0].ticks32;
		printf("found: %d, took %ld ticks\n", found, t[1].ticks32 - t[0].ticks32);
	}

	printf("average: %ld ticks\n", total_time / iterations);
}

int main(void) {

	uint8_t* array_a = alloc_random_array(ARRAY_SIZE);
	uint8_t* array_b = alloc_random_array(ARRAY_SIZE + 1);

	puts("naive search");
	do_benchmark(search_naive, 0xFF, array_a, ARRAY_SIZE, 10);
	puts("knuth search");
	do_benchmark(search_knuth, 0xFF, array_b, ARRAY_SIZE, 10);

	return 0;
}

Line 19: error: random.h: No such file or directory
Line 19: error: xtimer.h: No such file or directory
In function 'alloc_random_array':
Line 14: error: 'for' loop initial declaration used outside C99 mode
In function 'search_naive':
Line 22: error: 'for' loop initial declaration used outside C99 mode
In function 'do_benchmark':
Line 45: error: 'for' loop initial declaration used outside C99 mode
Line 47: error: 'xtimer_ticks32_t' undeclared (first use in this function)
Line 47: error: (Each undeclared identifier is reported only once
Line 47: error: for each function it appears in.)
Line 47: error: expected ';' before 't'
Line 48: error: 't' undeclared (first use in this function)