// based on the code we looked at last lecture, here are some ideas and // variations related to testing #include #include // our basic, slow, primality tester int is_prime(int x) { int y=2; for(; y < x; ++y) if((x % y) == 0) return 0; return 1; } // correct? says every number <= 1 (including negatives) is prime // coverage? // statement coverage: need 2 tests, 1 prime 1 not // branch coverage: need 3 tests x==2, 1 other prime 1 not // total coverage on attu: 2^32 tests (and it takes 1 int) // and what if is_prime did an illegal-free but didn't crash: int is_prime2(int x) { if(x==8675308) free((int*)8675308); int y=2; for(; y < x; ++y) if((x % y) == 0) return 0; return 1; } // testing ideas: // * hard to know if large values are prime, could write code that tests // (in this example, as much work as is_prime) // another (buggy) version with some special cases int is_prime3(int x) { if(x > 13) { int y=2; for(; y < x; ++y) if((x % y) == 0) return 0; return 1; } return x==2 || x==3 || x==5 || x==7 || x==11; } // black-box: more likely to test negatives? // white-box: more liketly to test 12, 13, 14 // return -1 if there are no primes int find_largest(int arrlen, int * nums, int * is_primes) { if(arrlen==0) return -1; if(!is_primes[arrlen-1]) return find_largest(arrlen-1,nums,is_primes); if(find_largest(arrlen-1,nums,is_primes) > nums[arrlen-1]) return find_largest(arrlen-1,nums,is_primes); return nums[arrlen-1]; } // testing ideas: // * do not choose nums randomly, may never be sorted // or reverse-sorted or have-no-primes // * try very short arrays and very long arrays // * try arrays with repeats // * white-box: notice is_primes need not be correct (just a filter)! // * full coverage impossible; possible for very short arrays int * find_primes(int arrlen, int * arr) { int * ans = (int*)calloc(arrlen,sizeof(int)); int i=0; for(; i < arrlen; ++i) if(is_prime(arr[i])) // how to stub the call to is_prime? ans[i] = 1; return ans; } // approach: pre-computed answers int is_prime_stub1(int x) { int answers[10][2] = {{2,1},{3,1},{4,0},{5,1},{13,1},{35,0},{51,0},{9,0},{17,1},{20,0}}; int i=0; for(; i < 10; ++i) if(answers[i][0]==x) return answers[i][1]; fprintf(stderr,"is_prime_stub1: unsupported argument"); exit(1); } // approach: lie in a way that does not affect caller int is_prime_stub2(int x) { return x > 20; } // approach: do less void print_output_stub(int arrlen, int * nums, int * is_primes, int largest) { fprintf(stdout,"\nlargest: %d\n (rest unimplemented)\n",largest); } // approach: slower algorithm // (right way to do primes is with a Sieve) // spec example from hw4: typedef struct PlayerList * player_list_t; player_list_t remove_player(player_list_t lst); // input: lst is NULL or a cyclic list, no aliases to any elements, // player field of first element heap-allocated, not NULL // name field of player heap-allocated, not NULL // ... // output: lst is NULL or cyclic list, containing all elements of input // except the first // first element and its player and name no longer available // Note: Java equivalent would be the same spec except heap-allocated // redundant (no stack pointers) and first element is still // available (no actual free)