Refactor fstree (#39)

* Refactor fstree, fstree_free, FSTree type

* Add FSRec structure

* Refactor fstree usage

* Decrease starting size of FSTree structure

* Check if ManifestPackage is NULL, not if the requirements array if NULL

* Use num_requirements instead of '!= NULL'

* Add fstree test

9 files changed, 222 insertions, 103 deletions

diff --git a/include/fs.h b/include/fs.h
index 81acd92..0698871 100644
--- a/include/fs.h
+++ b/include/fs.h
@@ -11,11 +11,15 @@
 #define SPM_FSTREE_FLT_RELATIVE 1 << 4
 
 typedef struct {
+    char *name;
+    struct stat *st;
+} FSRec;
+
+typedef struct {
     char *root;
-    char **dirs;
-    size_t dirs_length;
-    char **files;
-    size_t files_length;
+    FSRec **record;
+    size_t num_records;
+    size_t _num_alloc;
 } FSTree;
 
 typedef struct {
@@ -28,6 +32,7 @@ typedef struct {
 int _fstree_compare(const FTSENT **a, const FTSENT **b);
 FSTree *fstree(const char *_path, char **filter_by, unsigned int filter_mode);
 void fstree_free(FSTree *fsdata);
+char *fstree_search(FSTree *fsdata, char *path);
 FSList *fslist(const char *path);
 void fslist_free(FSList *fsdata);
 int exists(const char *filename);
diff --git a/lib/fs.c b/lib/fs.c
index e75c6a0..0cdda41 100644
--- a/lib/fs.c
+++ b/lib/fs.c
@@ -23,8 +23,8 @@ FSTree *fstree(const char *_path, char **filter_by, unsigned int filter_mode) {
     }
 
     if (path == NULL) {
-        perror(_path);
-        fprintf(SYSERROR);
+        spmerrno = errno;
+        spmerrno_cause(_path);
         return NULL;
     }
     char *root[2] = { path, NULL };
@@ -37,15 +37,12 @@ FSTree *fstree(const char *_path, char **filter_by, unsigned int filter_mode) {
         strcpy(filter_by[0], "");
     }
 
-    size_t dirs_size = 2;
-    size_t dirs_records = 0;
-    size_t files_size = 2;
-    size_t files_records = 0;
+    size_t size = 1;
+    size_t records = 0;
 
     fsdata = (FSTree *)calloc(1, sizeof(FSTree));
-    fsdata->root = (char *)calloc(PATH_MAX, sizeof(char));
-    fsdata->dirs = (char **)calloc(dirs_size, sizeof(char *));
-    fsdata->files = (char **)calloc(files_size, sizeof(char *));
+    fsdata->root = calloc(PATH_MAX, sizeof(char));
+    fsdata->record = calloc(size, sizeof(FSRec *));
 
     if (filter_mode & SPM_FSTREE_FLT_RELATIVE) {
         // Return an absolute path regardless
@@ -56,49 +53,48 @@ FSTree *fstree(const char *_path, char **filter_by, unsigned int filter_mode) {
 
     parent = fts_open(root, FTS_PHYSICAL | FTS_NOCHDIR, &_fstree_compare);
 
+    size_t last_size = size;
     if (parent != NULL) {
         while ((node = fts_read(parent)) != NULL) {
             for (size_t i = 0; filter_by[i] != NULL; i++) {
                 // Drop paths containing filter string(s) according to the requested mode
-                if (filter_mode & SPM_FSTREE_FLT_CONTAINS && strstr(node->fts_path, filter_by[i]) == NULL) {
+                if ((filter_mode & SPM_FSTREE_FLT_CONTAINS) && strstr(node->fts_path, filter_by[i]) == NULL) {
+                    continue;
+                }
+                else if ((filter_mode & SPM_FSTREE_FLT_ENDSWITH) && !endswith(node->fts_path, filter_by[i])) {
                     continue;
                 }
-                else if (filter_mode & SPM_FSTREE_FLT_ENDSWITH && !endswith(node->fts_path, filter_by[i])) {
+                else if ((filter_mode & SPM_FSTREE_FLT_STARTSWITH) && !startswith(node->fts_path, filter_by[i])) {
                     continue;
                 }
-                else if (filter_mode & SPM_FSTREE_FLT_STARTSWITH && !startswith(node->fts_path, filter_by[i])) {
+                if (strcmp(node->fts_path, "..") == 0 || strcmp(node->fts_path, ".") == 0) {
                     continue;
                 }
-                switch (node->fts_info) {
-                    case FTS_D:
-                        if (strcmp(node->fts_path, "..") == 0 || strcmp(node->fts_path, ".") == 0) {
-                            continue;
-                        }
-                        fsdata->dirs = (char **) realloc(fsdata->dirs, sizeof(char *) * dirs_size);
-                        fsdata->dirs[dirs_size - 1] = NULL;
-                        fsdata->dirs[dirs_records] = (char *) calloc(strlen(node->fts_path) + 1, sizeof(char));
-                        strncpy(fsdata->dirs[dirs_records], node->fts_path, strlen(node->fts_path));
-                        dirs_size++;
-                        dirs_records++;
-                        break;
-                    case FTS_F:
-                    case FTS_SL:
-                        fsdata->files = (char **) realloc(fsdata->files, sizeof(char *) * files_size);
-                        fsdata->files[files_size - 1] = NULL;
-                        fsdata->files[files_records] = (char *) calloc(strlen(node->fts_path) + 1, sizeof(char));
-                        strncpy(fsdata->files[files_records], node->fts_path, strlen(node->fts_path));
-                        files_size++;
-                        files_records++;
-                        break;
-                    default:
-                        break;
+
+                FSRec **tmp = realloc(fsdata->record, sizeof(FSRec *) * (size + 1) );
+                if (tmp == NULL) {
+                    spmerrno = errno;
+                    spmerrno_cause("Realloc of fsdata failed");
+                    return NULL;
+                }
+                fsdata->record = tmp;
+                fsdata->record[last_size] = NULL;
+                last_size = size;
+
+                fsdata->record[records] = calloc(1, sizeof(FSRec));
+                fsdata->record[records]->name = strdup(node->fts_path);
+                if (node->fts_statp) {
+                    fsdata->record[records]->st = calloc(1, sizeof(struct stat));
+                    memcpy(fsdata->record[records]->st, node->fts_statp, sizeof(struct stat));
                 }
+                size++;
+                records++;
             }
         }
         fts_close(parent);
     }
-    fsdata->dirs_length = dirs_records;
-    fsdata->files_length = files_records;
+    fsdata->num_records = records;
+    fsdata->_num_alloc = size;
     free(path);
     if (no_filter) {
         free(filter_by[0]);
@@ -108,6 +104,35 @@ FSTree *fstree(const char *_path, char **filter_by, unsigned int filter_mode) {
 }
 
 /**
+ * Free a `FSTree` structure
+ * @param fsdata
+ */
+void fstree_free(FSTree *fsdata) {
+    if (fsdata != NULL) {
+        if (fsdata->root != NULL) {
+            free(fsdata->root);
+        }
+        if (fsdata->record != NULL) {
+            for (int i = 0; i < fsdata->num_records; i++) {
+                free(fsdata->record[i]->name);
+                free(fsdata->record[i]->st);
+            }
+            free(fsdata->record);
+        }
+        free(fsdata);
+    }
+}
+
+char *fstree_search(FSTree *fsdata, char *path) {
+    for (size_t i = 0; i < fsdata->num_records; i++) {
+        if (strstr(fsdata->record[i]->name, path) != NULL) {
+            return fsdata->record[i]->name;
+        }
+    }
+    return NULL;
+}
+
+/**
  *
  * @param one
  * @param two
@@ -191,58 +216,26 @@ failed: // label
     return tree;
 }
 
+
 /**
  *
- * @param _path
+ * @param fsdata
+ * @param path
  * @return
  */
-int rmdirs(const char *_path) {
-    if (access(_path, F_OK) != 0) {
-        return -1;
-    }
-
-    FSTree *data = fstree(_path, NULL, SPM_FSTREE_FLT_NONE);
-    if (data->files) {
-        for (size_t i = 0; data->files[i] != NULL; i++) {
-            remove(data->files[i]);
-        }
-    }
-    if (data->dirs) {
-        for (size_t i = data->dirs_length - 1; i != 0; i--) {
-            remove(data->dirs[i]);
+char *fslist_search(FSList *fsdata, char *path) {
+    for (size_t i = 0; i < fsdata->records; i++) {
+        if (strstr(fsdata->record[i]->d_name, path) != NULL) {
+            return fsdata->record[i]->d_name;
         }
     }
-    remove(data->root);
-
-    fstree_free(data);
-    return 0;
+    return NULL;
 }
 
 /**
- * Free a `FSTree` structure
+ *
  * @param fsdata
  */
-void fstree_free(FSTree *fsdata) {
-    if (fsdata != NULL) {
-        if (fsdata->root != NULL) {
-            free(fsdata->root);
-        }
-        if (fsdata->files != NULL) {
-            for (int i = 0; fsdata->files[i] != NULL; i++) {
-                free(fsdata->files[i]);
-            }
-            free(fsdata->files);
-        }
-        if (fsdata->dirs != NULL) {
-            for (int i = 0; fsdata->dirs[i] != NULL; i++) {
-                free(fsdata->dirs[i]);
-            }
-            free(fsdata->dirs);
-        }
-        free(fsdata);
-    }
-}
-
 void fslist_free(FSList *fsdata) {
     if (fsdata == NULL) {
         return;
@@ -261,6 +254,39 @@ void fslist_free(FSList *fsdata) {
 }
 
 /**
+ *
+ * @param _path
+ * @return
+ */
+int rmdirs(const char *_path) {
+    if (access(_path, F_OK) != 0) {
+        return -1;
+    }
+
+    FSTree *data = fstree(_path, NULL, SPM_FSTREE_FLT_NONE);
+    if (data->record == NULL) {
+        return -1;
+    }
+
+    for (size_t i = 0; i < data->num_records; i++) {
+        if (!S_ISDIR(data->record[i]->st->st_mode)) {
+            remove(data->record[i]->name);
+        }
+    }
+
+    for (size_t i = 0; i < data->num_records; i++) {
+        if (S_ISDIR(data->record[i]->st->st_mode)) {
+            remove(data->record[i]->name);
+        }
+    }
+
+    remove(data->root);
+    fstree_free(data);
+
+    return 0;
+}
+
+/**
  * Expand "~" to the user's home directory
  *
  * Example:
diff --git a/lib/install.c b/lib/install.c
index 282c662..a2fdf9f 100644
--- a/lib/install.c
+++ b/lib/install.c
@@ -344,8 +344,11 @@ int spm_do_install(SPM_Hierarchy *fs, ManifestList *mf, StrList *packages) {
     }
 
     // free requirements array
-    for (size_t i = 0; requirements != NULL && requirements[i] != NULL; i++) {
-        manifest_package_free(requirements[i]);
+    for (size_t i = 0; i < num_requirements; i++) {
+        if (requirements[i] != NULL) {
+            manifest_package_free(requirements[i]);
+            requirements[i] = NULL;
+        }
     }
     free(package_dir);
 
diff --git a/lib/manifest.c b/lib/manifest.c
index 965665e..5a9fae3 100644
--- a/lib/manifest.c
+++ b/lib/manifest.c
@@ -59,7 +59,7 @@ Manifest *manifest_from(const char *package_dir) {
     fsdata = fstree(package_dir, package_filter, SPM_FSTREE_FLT_ENDSWITH);
 
     Manifest *info = (Manifest *)calloc(1, sizeof(Manifest));
-    info->records = fsdata->files_length;
+    info->records = fsdata->num_records;
     info->packages = (ManifestPackage **) calloc(info->records + 1, sizeof(ManifestPackage *));
     if (info->packages == NULL) {
         perror("Failed to allocate package array");
@@ -84,11 +84,15 @@ Manifest *manifest_from(const char *package_dir) {
         return NULL;
     }
 
-    for (size_t i = 0; i < fsdata->files_length; i++) {
-        float percent = (((float)i + 1) / fsdata->files_length) * 100;
+    for (size_t i = 0; i < fsdata->num_records; i++) {
+        if (S_ISDIR(fsdata->record[i]->st->st_mode)) {
+            continue;
+        }
+
+        float percent = (((float)i + 1) / fsdata->num_records) * 100;
 
         if (SPM_GLOBAL.verbose) {
-            printf("[%3.0f%%] %s\n", percent, basename(fsdata->files[i]));
+            printf("[%3.0f%%] %s\n", percent, basename(fsdata->record[i]->name));
         }
 
         // Initialize package record
@@ -103,21 +107,21 @@ Manifest *manifest_from(const char *package_dir) {
         }
 
         // Swap extra package separators with a bogus character
-        manifest_package_separator_swap(&fsdata->files[i]);
+        manifest_package_separator_swap(&fsdata->record[i]->name);
 
         // Split the package name into parts
         char psep[2];
         snprintf(psep, sizeof(psep), "%c", SPM_PACKAGE_MEMBER_SEPARATOR);
-        char **parts = split(fsdata->files[i], psep);
+        char **parts = split(fsdata->record[i]->name, psep);
 
         // Restore package separator
         manifest_package_separator_restore(&parts[0]);
-        manifest_package_separator_restore(&fsdata->files[i]);
+        manifest_package_separator_restore(&fsdata->record[i]->name);
 
         // Populate `ManifestPackage` record
-        info->packages[i]->size = (size_t) get_file_size(fsdata->files[i]);
+        info->packages[i]->size = (size_t) get_file_size(fsdata->record[i]->name);
         strncpy(info->packages[i]->origin, info->origin, SPM_PACKAGE_MEMBER_ORIGIN_SIZE);
-        strncpy(info->packages[i]->archive, basename(fsdata->files[i]), SPM_PACKAGE_MEMBER_SIZE);
+        strncpy(info->packages[i]->archive, basename(fsdata->record[i]->name), SPM_PACKAGE_MEMBER_SIZE);
         strncpy(info->packages[i]->name, basename(parts[0]), SPM_PACKAGE_MEMBER_SIZE);
         strncpy(info->packages[i]->version, parts[1], SPM_PACKAGE_MEMBER_SIZE);
         strncpy(info->packages[i]->revision, parts[2], SPM_PACKAGE_MEMBER_SIZE);
@@ -171,7 +175,7 @@ void manifest_free(Manifest *info) {
  * @param info `ManifestPackage`
  */
 void manifest_package_free(ManifestPackage *info) {
-    if (info->requirements == NULL) {
+    if (info == NULL) {
         return;
     }
 
diff --git a/lib/relocation.c b/lib/relocation.c
index fa03aee..a14c8e4 100644
--- a/lib/relocation.c
+++ b/lib/relocation.c
@@ -314,17 +314,20 @@ int prefixes_write(const char *output_file, int mode, char **prefix, const char
             fprintf(SYSERROR);
             return -1;
         }
-        for (size_t i = 0; i < fsdata->files_length; i++) {
-            if (file_is_metadata(fsdata->files[i])) {
+        for (size_t i = 0; i < fsdata->record; i++) {
+            if (S_ISDIR(fsdata->record[i]->st->st_mode)) {
+                continue;
+            }
+            if (file_is_metadata(fsdata->record[i]->name)) {
                 continue;
             }
             for (int p = 0; prefix[p] != NULL; p++) {
-                if (find_in_file(fsdata->files[i], prefix[p]) == 0) {
+                if (find_in_file(fsdata->record[i]->name, prefix[p]) == 0) {
                     int proceed = 0;
                     if (mode == PREFIX_WRITE_BIN) {
-                        proceed = file_is_binary(fsdata->files[i]);
+                        proceed = file_is_binary(fsdata->record[i]->name);
                     } else if (mode == PREFIX_WRITE_TEXT) {
-                        proceed = file_is_text(fsdata->files[i]);
+                        proceed = file_is_text(fsdata->record[i]->name);
                     }
 
                     // file_is_* functions return NULL when they encounter anything but a regular file
@@ -332,7 +335,7 @@ int prefixes_write(const char *output_file, int mode, char **prefix, const char
                         continue;
                     }
                     // Record in file
-                    fprintf(fp, "#%s\n%s\n", prefix[p], fsdata->files[i]);
+                    fprintf(fp, "#%s\n%s\n", prefix[p], fsdata->record[i]->name);
                 }
             }
         }
diff --git a/lib/rpath.c b/lib/rpath.c
index ae73574..0044db8 100644
--- a/lib/rpath.c
+++ b/lib/rpath.c
@@ -256,7 +256,7 @@ char *rpath_autodetect(const char *filename, FSTree *tree) {
 
         // Is the shared library in the tree?
         char *match = NULL;
-        if ((match = dirname(strstr_array(tree->files, shared_library))) != NULL) {
+        if ((match = dirname(fstree_search(tree, shared_library))) != NULL) {
             // Begin generating the relative path string
             strcat(relative, origin);
             strcat(relative, DIRSEPS);
diff --git a/src/spm.c b/src/spm.c
index bdaab23..265986e 100644
--- a/src/spm.c
+++ b/src/spm.c
@@ -356,7 +356,6 @@ int main(int argc, char *argv[], char *arge[]) {
         }
     }
 
-    //resolve_free();   // TODO: fix invalid free()
     runtime_free(rt);
     free_global_config();
     strlist_free(packages);
diff --git a/tests/framework.h b/tests/framework.h
index c9170b6..ea899ce 100644
--- a/tests/framework.h
+++ b/tests/framework.h
@@ -104,7 +104,7 @@ char *mock_size(size_t size, const char *fill_byte) {
     }
 
     if ((mkstemp(filename)) < 0) {
-        perror("mktemp failed to create temporary file");
+        perror("mkstemp failed to create temporary file");
         exit(errno);
     }
 
diff --git a/tests/test_fs_fstree.c b/tests/test_fs_fstree.c
new file mode 100644
index 0000000..aa6ef4e
--- /dev/null
+++ b/tests/test_fs_fstree.c
@@ -0,0 +1,79 @@
+#include "spm.h"
+#include "framework.h"
+
+const char *testFmt = "returned '%s', expected '%s'\n";
+struct TestCase testCase[] = {
+        {.arg[0].sptr = ".", .arg[1].slptr = NULL, .arg[2].unsigned_int = SPM_FSTREE_FLT_NONE},
+        {.arg[0].sptr = ".", .arg[1].slptr = (char *[]){"world", NULL}, .arg[2].unsigned_int = SPM_FSTREE_FLT_CONTAINS},
+        {.arg[0].sptr = ".", .arg[1].slptr = (char *[]){"/", NULL}, .arg[2].unsigned_int = SPM_FSTREE_FLT_STARTSWITH},
+        {.arg[0].sptr = ".", .arg[1].slptr = (char *[]){".txt", NULL}, .arg[2].unsigned_int = SPM_FSTREE_FLT_ENDSWITH},
+        {.arg[0].sptr = ".", .arg[1].slptr = (char *[]){"./hello", NULL}, .arg[2].unsigned_int = SPM_FSTREE_FLT_STARTSWITH | SPM_FSTREE_FLT_RELATIVE},
+};
+size_t numCases = sizeof(testCase) / sizeof(struct TestCase);
+
+int main(int argc, char *argv[]) {
+    const char *hello_world = "hello_world.txt";
+    char _tmpdir[PATH_MAX];
+    char _startdir[PATH_MAX];
+
+    char *tmpdir = _tmpdir;
+    char *startdir = _startdir;
+
+    // Create strings for local path information populated by the loop below
+    char _tc_abspath[PATH_MAX] = {0};  // absolute path of working directory post-chdir
+    char _cwd[PATH_MAX] = {0};  // working directory post-chdir
+
+    // Create pointers to local path buffers
+    char *tc_abspath = _tc_abspath;
+    char *cwd = _cwd;
+
+    // record the starting directory we executed this test from
+    getcwd(startdir, PATH_MAX);
+
+    for (size_t i = 0; i < numCases; i++) {
+        // pointers to testCase data
+        const char *tc_path = testCase[i].arg[0].sptr;
+        char **tc_filter = testCase[i].arg[1].slptr;
+        unsigned int tc_mode = testCase[i].arg[2].unsigned_int;
+
+        // Set up temporary test directory name
+        sprintf(tmpdir, "fstree_test%zu_XXXXXX", i);
+        // Create directory
+        mkdtemp(tmpdir);
+
+        // Enter the new temporary directory
+        chdir(tmpdir); {
+            // Populate the relative (or untouched) current working directory buffer
+            getcwd(cwd, PATH_MAX);
+            // Obtain the absolute path to the current working directory
+            realpath(tc_path, tc_abspath);
+
+            // Generate a mock file and rename it to hello_world.txt
+            char *tmpfile = mock_size(1 * sizeof(char), "?");
+            rename(tmpfile, hello_world);
+            free(tmpfile);
+
+            // --- Test begins here
+
+            // Read-in directory structure
+            FSTree *fsdata = fstree(tc_path, tc_filter, tc_mode);
+
+            myassert(fsdata != NULL, "FSTree was NULL");
+            myassert(fsdata->root, "FSTree root path was NULL");
+            myassert(strcmp(tc_abspath, cwd) == 0, "current directory is '%s', but should have been '%s'\n", tc_abspath, cwd);
+            myassert(fsdata->num_records > 0, "num_records should be non-zero\n");
+            myassert(fsdata->_num_alloc > 0, "_num_alloc should be non-zero\n");
+            for (size_t f = 0; f < fsdata->num_records; f++) {
+                myassert(fsdata->record[f]->name != NULL, "FSRec name record was NULL");
+                myassert(fsdata->record[f]->st != NULL, "FSRec stat struct was NULL");
+            }
+
+            fstree_free(fsdata);
+        }
+        // Return from temporary directory
+        chdir(startdir);
+
+        // Delete temporary directory
+        rmdirs(tmpdir);
+    }
+}
\ No newline at end of file