/* Tests that |f->search| returns |expect| when called to search for |key| within |array[]|, which has |n| elements such that |array[i] == i|. */ static void test_search_func_at (struct search_func *f, int array[], int n, int key, int expect) { int result = f->search (array, n, key); if (result != expect) printf ("%s returned %d looking for %d - expected %d\n", f->name, result, key, expect); } /* Tests searches for each element in |array[]| having |n| elements such that |array[i] == i|, and some unsuccessful searches too, all using function |f->search|. */ static void test_search_func (struct search_func *f, int array[], int n) { static const int shouldnt_find[] = {INT_MIN, -20, -1, INT_MAX}; int i; printf ("Testing integrity of %s... ", f->name); fflush (stdout); /* Verify that the function finds values that it should. */ for (i = 0; i < n; i++) test_search_func_at (f, array, n, i, i); /* Verify that the function doesn't find values it shouldn't. */ for (i = 0; i < (int) (sizeof shouldnt_find / sizeof *shouldnt_find); i++) test_search_func_at (f, array, n, shouldnt_find[i], -1); printf ("done\n"); } /* Times a search for each element in |array[]| having |n| elements such that |array[i] == i|, repeated |n_iter| times, using function |f->search|. */ static void time_successful_search (struct search_func *f, int array[], int n, int n_iter) { clock_t timer; printf ("Timing %d sets of successful searches... ", n_iter); fflush (stdout); start_timer (&timer); while (n_iter-- > 0) { int i; for (i = 0; i < n; i++) f->search (array, n, i); } stop_timer (timer); } /* Times |n| search for elements not in |array[]| having |n| elements such that |array[i] == i|, repeated |n_iter| times, using function |f->search|. */ static void time_unsuccessful_search (struct search_func *f, int array[], int n, int n_iter) { clock_t timer; printf ("Timing %d sets of unsuccessful searches... ", n_iter); fflush (stdout); start_timer (&timer); while (n_iter-- > 0) { int i; for (i = 0; i < n; i++) f->search (array, n, -i); } stop_timer (timer); }