lander/test/fuzzy.h

#ifndef AD3_FUZZYTEST
#define AD3_FUZZYTEST

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdio.h>

typedef struct fuzzyconfig {
    int seed;
    int word_length;
    int word_count;
} FuzzyConfig;

void random_clean_string(char* s, int len) {
    char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789,?";
    int charset_len = strlen(charset);

    // len - 1 ensures that we can still set the null byte for the final byte
    int actual_len = rand() % (len - 1);
    int key;
    int i;

    for (i = 0; i < actual_len; i++) {
        key = rand() % charset_len;
        s[i] = charset[key];
    }

    s[i] = '\0';
}

void random_string(char* s, int len) {
    int val = rand();

    // String can't be an empty string as they aren't supported
    s[0] = (char)(val % 255 + 1);

    for (int i = 1; i < len - 1; i++) {
        val = rand();
        s[i] = (char)(val % 256);
    }

    // Just in case no null characters were created
    s[len - 1] = '\0';
}

void random_string_matrix(char** s, int count, int len) {
    for (int i = 0; i < count; i++) {
        random_string(s[i], len);
    }
}

char** init_string_matrix(int count, int len) {
    char** matrix = malloc(count * sizeof(char*));

    for (int i = 0; i < count; i++) {
        matrix[i] = calloc(len, sizeof(char));
    }

    return matrix;
}

/**
 * Test a given trie implementation using randomly generated strings generated
 * using a given seed.
 *
 * @param seed seed to use for generating random strings
 * @param count how many strings to test with
 * @param len maximum length of each string
 * @param init_func function to creat a new trie of the wanted type
 * @param free_func function to free the given trie
 * @param add_func function to add a string to the given trie
 * @param remove_func function to remove a string from the given trie
 * @param size_func function to get the size of the given trie
 * @return exit code describing failures, if any
 */
int fuzzy_test_trie_seed(FuzzyConfig conf, void* (*init_func) (), void (*free_func) (void*), bool (*add_func) (void*, char*, void*), bool (*remove_func) (void*, char*), size_t (*size_func) (void*)) {
    srand(conf.seed);

    char** matrix = init_string_matrix(conf.word_count, conf.word_length);
    random_string_matrix(matrix, conf.word_count, conf.word_length);
    bool* contains = calloc(conf.word_count, sizeof(bool));

    // It's possible that the string matrix contains duplicate strings
    bool** contains_dedupped = calloc(conf.word_count, sizeof(bool*));

    for (int i = 0; i < conf.word_count; i++) {
        if (contains_dedupped[i] == NULL) {
            contains_dedupped[i] = contains + i;

            for (int j = i + 1; j < conf.word_count; j++) {
                if (strcmp(matrix[i], matrix[j]) == 0) {
                    contains_dedupped[j] = contains + i;
                }
            }
        }
    }
    
    // We keep track of the size as well so that we can check whether this is
    // also correct
    size_t size = 0;

    void* ct = init_func();

    bool changed;

    // 0: success
    // 1: invalid add
    // 2: invalid remove
    // 3: bad size after adds
    // 4: bad size after removes
    int exit_code = 0;

    // Add all strings to trie, checking for duplicates
    for (int i = 0; i < conf.word_count; i++) {
      changed = add_func(ct, matrix[i], NULL);

      // if changed is false, *contains_dedupped[i] should be true, as changed
      // can only be false if the string is already contained in the trie. if
      // changed is true, *contains_dedupped[i] should be false, as the string
      // cannot be in the trie yet.
      if (changed == *contains_dedupped[i]) {
        exit_code = 1;
        goto END;
      }

      if (!*contains_dedupped[i]) {
        *contains_dedupped[i] = true;
        size++;
      }
    }

    // Ensure size is correct
    if (size_func(ct) != size) {
      printf("%i %i\n", size_func(ct), size);
      exit_code = 3;
      goto END;
    }

    // Remove all strings again, again taking duplicates into consideration
    /* for (int i = 0; i < conf.word_count; i++) { */
    /*   changed = remove_func(ct, matrix[i]); */

    /*   // The string shouldn't be in the trie, yet another add operation */
    /*   // says it added it as well */
    /*   if (changed != *contains_dedupped[i]) { */
    /*     exit_code = 2; */
    /*     goto END; */
    /*   } */

    /*   if (*contains_dedupped[i]) { */
    /*     *contains_dedupped[i] = false; */
    /*     size--; */
    /*   } */
    /* } */

    // Finally, check that the trie is completely empty
    /* if (size_func(ct) != 0) { */
    /*   exit_code = 4; */
    /* } */

END:
    free_func(ct);

    // Even testing functions should properly free memory
    free(contains);
    free(contains_dedupped);

    for (int i = 0; i < conf.word_count; i++) {
        free(matrix[i]);
    }

    free(matrix);

    return exit_code;
}

/**
 * Same as fuzzy_test_trie_seed, except that the seed is randomly generated.
 *
 * @param count how many strings to test with
 * @param len maximum length of each string
 * @param init_func function to creat a new trie of the wanted type
 * @param free_func function to free the given trie
 * @param add_func function to add a string to the given trie
 * @param remove_func function to remove a string from the given trie
 * @param size_func function to get the size of the given trie
 * @return the generated seed if the test wasn't successful, -1 otherwise.
 */
/* int fuzzy_test_trie(int count, int len, void* (*init_func) (), void (*free_func) (void*), bool (*add_func) (void*, char*), bool (*remove_func) (void*, char*), int (*size_func) (void*)) { */
/*     int seed = rand(); */
/*     bool succeeded = fuzzy_test_trie_seed(seed, count, len, init_func, free_func, add_func, remove_func, size_func); */

/*     if (!succeeded) { */
/*         return seed; */
/*     } */

/*     return -1; */
/* } */


#endif