folder_select.c partial rewrite -- remove static, add full notification

| with some code refactoring we can eliminate the static
  char buffer in get_full_path()

  I'm guessing making the functions recursive prompted the static buffer
  I don't see any reason we can't just pass the same buffer
|
  During tested I noted failure after buffer was full
   -- splash added for buffer full notification

  added some logic to not add partial entries and try to find a
| selected item that will fit in the remaing buffer
------------------------------------------------------------------------

While looking through the source I noticed a few potential
pitfalls with the current code.

Namely the stack allocated temporary buffer
sized to setting_len.

I also noted the rigid vect[32] with the timeless --
/* 32 separate folders should be Enough For Everybody(TM) */
and decided to make it a bit more robust

The saved items are hashed with crc32 on all the paths
and a hashed_len is kept to aid in the buffer full message before the
user actually goes to save the changes
(assuming they even get the message)

In the old code, buffer might be the same since it ran out of
space and didn't get their later selections

the hashed_len could easily be turned into a way to get a needed buffer
size as well for someone in the future just pass a really large maxlen

I made get_full_path non recursive since it liked to blow the stack
while embedded in all the other recursive calls making it a pain to debug
(the real reason the buffer was static?)
traverse first from the current folder to root mutating the
parent pointers to point at the previous child
next traverse back to the folder unmutating & taking names on the way

Folder depth is now uint16 65535 levels is probably excessive
children_count is also uint16 as well
I made the first folders below root '/' stay below root
instead of shifting since the horizontal real estate is limited

slightly smaller than it began but hopefully faster & more reliable

Change-Id: I348f61baf865cccdeacddfd9d50641a882e890fc

1 files changed, 270 insertions, 159 deletions

diff --git a/apps/gui/folder_select.c b/apps/gui/folder_select.c
index 706b166941..e324e8649a 100644
--- a/apps/gui/folder_select.c
+++ b/apps/gui/folder_select.c
@@ -8,6 +8,7 @@
  *
  * Copyright (C) 2012 Jonathan Gordon
  * Copyright (C) 2012 Thomas Martitz
+* * Copyright (C) 2021 William Wilgus
  *
  * This program is free software; you can redistribute it and/or
  * modify it under the terms of the GNU General Public License
@@ -30,7 +31,11 @@
 #include "language.h"
 #include "list.h"
 #include "plugin.h"
+#include "splash.h"
 
+/* Define LOGF_ENABLE to enable logf output in this file */
+//#define LOGF_ENABLE
+#include "logf.h"
 
 /*
  * Order for changing child states:
@@ -56,18 +61,31 @@ struct child {
 struct folder {
     char *name;
     struct child *children;
-    int children_count;
-    int depth;
-
     struct folder* previous;
+    uint16_t children_count;
+    uint16_t depth;
 };
 
 static char *buffer_front, *buffer_end;
+
+static struct
+{
+    int32_t len; /* keeps count versus maxlen to give buffer full notification */
+    uint32_t val; /* hash of all selected items */
+    char buf[3];/* address used as identifier -- only \0 written to it */
+    char maxlen_exceeded; /*0,1*/
+} hashed;
+
+static inline void get_hash(const char *key, uint32_t *hash, int len)
+{
+    *hash = crc_32(key, len, *hash);
+}
+
 static char* folder_alloc(size_t size)
 {
     char* retval;
     /* 32-bit aligned */
-    size = (size + 3) & ~3;
+    size = ALIGN_UP(size, 4);
     if (buffer_front + size > buffer_end)
     {
         return NULL;
@@ -86,32 +104,57 @@ static char* folder_alloc_from_end(size_t size)
     buffer_end -= size;
     return buffer_end;
 }
-
-static void get_full_path_r(struct folder *start, char* dst)
+#if 0
+/* returns the buffer size required to store the path + \0 */
+static int get_full_pathsz(struct folder *start)
 {
-    if (start->previous)
-        get_full_path_r(start->previous, dst);
-
-    if (start->name && start->name[0] && strcmp(start->name, "/"))
+    int reql = 0;
+    struct folder *next = start;
+    do
     {
-        strlcat(dst, "/", MAX_PATH);
-        strlcat(dst, start->name, MAX_PATH);
-    }
+        reql += strlen(next->name) + 1;
+    } while ((next = next->previous));
+
+    if (start->name[0] != '/') reql--;
+    if (--reql < 0) reql = 0;
+    return reql;
 }
+#endif
 
-static char* get_full_path(struct folder *start)
+static size_t get_full_path(struct folder *start, char *dst, size_t dst_sz)
 {
-    static char buffer[MAX_PATH];
-
-    if (strcmp(start->name, "/"))
+    size_t pos = 0;
+    struct folder *prev, *cur = NULL, *next = start;
+    dst[0] = '\0'; /* for strlcat to do its thing */
+    /* First traversal R->L mutate nodes->previous to point at child */
+    while (next->previous != NULL) /* stop at the root */
     {
-        buffer[0] = 0;
-        get_full_path_r(start, buffer);
+#define PATHMUTATE()              \
+        ({                        \
+            prev = cur;           \
+            cur = next;           \
+            next = cur->previous;\
+            cur->previous = prev; \
+        })
+        PATHMUTATE();
     }
-    else /* get_full_path_r() does the wrong thing for / */
-        return "/";
-
-    return buffer;
+    /*swap the next and cur nodes to reverse direction */
+    prev = next;
+    next = cur;
+    cur = prev;
+    /* Second traversal L->R mutate nodes->previous to point back at parent
+     * copy strings to buf as they go by */
+    while (next != NULL)
+    {
+        PATHMUTATE();
+        pos = strlcat(dst, cur->name, dst_sz);
+        /* do not append slash to paths starting with slash */
+        if (cur->name[0] != '/')
+            pos = strlcat(dst, "/", dst_sz);
+    }
+    logf("get_full_path: (%d)[%s]", (int)pos, dst);
+    return pos;
+#undef PATHMUTATE
 }
 
 /* support function for qsort() */
@@ -125,49 +168,52 @@ static int compare(const void* p1, const void* p2)
 static struct folder* load_folder(struct folder* parent, char *folder)
 {
     DIR *dir;
-    char* path = get_full_path(parent);
     char fullpath[MAX_PATH];
+
     struct dirent *entry;
-    struct folder* this = (struct folder*)folder_alloc(sizeof(struct folder));
     int child_count = 0;
     char *first_child = NULL;
+    size_t len = 0;
 
-    if (!strcmp(folder,"/"))
-        strlcpy(fullpath, folder, 2);
-    else
-        snprintf(fullpath, MAX_PATH, "%s/%s", parent ? path : "", folder);
+    struct folder* this = (struct folder*)folder_alloc(sizeof(struct folder));
+    if (this == NULL)
+        goto fail;
+
+    if (parent)
+    {
+        len = get_full_path(parent, fullpath, sizeof(fullpath));
+        if (len >= sizeof(fullpath))
+            goto fail;
+    }
+    strlcpy(&fullpath[len], folder, sizeof(fullpath) - len);
+    logf("load_folder: [%s]", fullpath);
 
-    if (!this)
-        return NULL;
     dir = opendir(fullpath);
-    if (!dir)
-        return NULL;
+    if (dir == NULL)
+        goto fail;
     this->previous = parent;
     this->name = folder;
     this->children = NULL;
     this->children_count = 0;
-    this->depth = parent ? parent->depth + 1 : 0;
+    if (parent)
+        this->depth = parent->depth + 1;
 
     while ((entry = readdir(dir))) {
-        int len = strlen((char *)entry->d_name);
-        struct dirinfo info;
-
-        info = dir_get_info(dir, entry);
-
         /* skip anything not a directory */
-        if ((info.attribute & ATTR_DIRECTORY) == 0) {
+        if ((dir_get_info(dir, entry).attribute & ATTR_DIRECTORY) == 0) {
             continue;
         }
-        /* skip directories . and .. */
-        if ((!strcmp((char *)entry->d_name, ".")) ||
-            (!strcmp((char *)entry->d_name, ".."))) {
+        /* skip . and .. */
+        char *dn = entry->d_name;
+        if ((dn[0] == '.') && (dn[1] == '\0' || (dn[1] == '.' && dn[2] == '\0')))
             continue;
-        }
-        char *name = folder_alloc_from_end(len+1);
-        if (!name)
+        /* copy entry name to end of buffer, save pointer */
+        int len = strlen((char *)entry->d_name);
+        char *name = folder_alloc_from_end(len+1); /*for NULL*/
+        if (name == NULL)
         {
             closedir(dir);
-            return NULL;
+            goto fail;
         }
         memcpy(name, (char *)entry->d_name, len+1);
         child_count++;
@@ -177,26 +223,29 @@ static struct folder* load_folder(struct folder* parent, char *folder)
     /* now put the names in the array */
     this->children = (struct child*)folder_alloc(sizeof(struct child) * child_count);
 
-    if (!this->children)
-        return NULL;
+    if (this->children == NULL)
+        goto fail;
+
     while (child_count)
     {
-        this->children[this->children_count].name = first_child;
-        this->children[this->children_count].folder = NULL;
-        this->children[this->children_count].state = COLLAPSED;
-        this->children_count++;
-        first_child += strlen(first_child) + 1;
+        struct child *child = &this->children[this->children_count++];
+        child->name = first_child;
+        child->folder = NULL;
+        child->state = COLLAPSED;
+        while(*first_child++ != '\0'){};/* move to next name entry */
         child_count--;
     }
     qsort(this->children, this->children_count, sizeof(struct child), compare);
 
     return this;
+fail:
+    return NULL;
 }
 
 struct folder* load_root(void)
 {
     static struct child root_child;
-
+    /* reset the root for each call */
     root_child.name = "/";
     root_child.folder = NULL;
     root_child.state = COLLAPSED;
@@ -205,7 +254,7 @@ struct folder* load_root(void)
         .name = "",
         .children = &root_child,
         .children_count = 1,
-        .depth = -1,
+        .depth = 0,
         .previous = NULL,
     };
 
@@ -230,7 +279,6 @@ static int count_items(struct folder *start)
 static struct child* find_index(struct folder *start, int index, struct folder **parent)
 {
     int i = 0;
-
     *parent = NULL;
 
     while (i < start->children_count)
@@ -262,22 +310,22 @@ static const char * folder_get_name(int selected_item, void * data,
     struct folder *parent;
     struct child *this = find_index(root, selected_item , &parent);
 
-    buffer[0] = '\0';
-
-    if (parent->depth >= 0)
-        for(int i = 0; i <= parent->depth; i++)
-            strcat(buffer, "\t");
-
+    char *buf = buffer;
+    if ((int)buffer_len > parent->depth)
+    {
+        int i = parent->depth;
+        while(--i > 0) /* don't indent the parent /folders */
+            *buf++ = '\t';
+    }
+    *buf = '\0';
     strlcat(buffer, this->name, buffer_len);
 
     if (this->state == EACCESS)
     {   /* append error message to the entry if unaccessible */
-        size_t len = strlcat(buffer, " (", buffer_len);
+        size_t len = strlcat(buffer, " ( ", buffer_len);
         if (buffer_len > len)
         {
-            snprintf(&buffer[len], buffer_len - len, str(LANG_READ_FAILED),
-                        this->name);
-            strlcat(buffer, ")", buffer_len);
+            snprintf(&buffer[len], buffer_len - len, str(LANG_READ_FAILED), ")");
         }
     }
 
@@ -304,6 +352,23 @@ static enum themable_icons folder_get_icon(int selected_item, void * data)
     return Icon_NOICON;
 }
 
+static int child_set_state_expand(struct child *this, struct folder *parent)
+{
+    int newstate = EACCESS;
+    if (this->folder == NULL)
+        this->folder = load_folder(parent, this->name);
+
+    if (this->folder != NULL)
+    {
+        if(this->folder->children_count == 0)
+            newstate = SELECTED;
+        else
+            newstate = EXPANDED;
+    }
+    this->state = newstate;
+    return newstate;
+}
+
 static int folder_action_callback(int action, struct gui_synclist *list)
 {
     struct folder *root = (struct folder*)list->data;
@@ -322,17 +387,13 @@ static int folder_action_callback(int action, struct gui_synclist *list)
                 this->state = COLLAPSED;
                 break;
             case COLLAPSED:
-                if (this->folder == NULL)
-                    this->folder = load_folder(parent, this->name);
-                this->state = this->folder ? (this->folder->children_count == 0 ?
-                        SELECTED : EXPANDED) : EACCESS;
+                child_set_state_expand(this, parent);
                 break;
             case EACCESS:
                 /* cannot open, do nothing */
                 return action;
         }
-        list->nb_items = count_items(root);
-        return ACTION_REDRAW;
+        action = ACTION_REDRAW;
     }
     else if (action == ACTION_STD_CONTEXT)
     {
@@ -342,140 +403,198 @@ static int folder_action_callback(int action, struct gui_synclist *list)
                 for (i = 0; i < this->folder->children_count; i++)
                 {
                     child = &this->folder->children[i];
-                    if (child->state == SELECTED ||
-                        child->state == EXPANDED)
-                        child->state = COLLAPSED;
-                    else if (child->state == COLLAPSED)
-                        child->state = SELECTED;
+                    switch (child->state)
+                    {
+                        case SELECTED:
+                        case EXPANDED:
+                            child->state = COLLAPSED;
+                            break;
+                        case COLLAPSED:
+                            child->state = SELECTED;
+                            break;
+                        case EACCESS:
+                            break;
+                    }
                 }
                 break;
             case SELECTED:
             case COLLAPSED:
-                if (this->folder == NULL)
-                    this->folder = load_folder(parent, this->name);
-                this->state = this->folder ? (this->folder->children_count == 0 ?
-                        SELECTED : EXPANDED) : EACCESS;
-                if (this->state == EACCESS)
-                    break;
-                for (i = 0; i < this->folder->children_count; i++)
+                if (child_set_state_expand(this, parent) != EACCESS)
                 {
-                    child = &this->folder->children[i];
-                    child->state = SELECTED;
+                    for (i = 0; i < (this->folder->children_count); i++)
+                    {
+                        child = &this->folder->children[i];
+                        child->state = SELECTED;
+                    }
                 }
                 break;
             case EACCESS:
                 /* cannot open, do nothing */
                 return action;
         }
-        list->nb_items = count_items(root);
-        return ACTION_REDRAW;
+        action = ACTION_REDRAW;
     }
-            
-        
+    if (action == ACTION_REDRAW)
+        list->nb_items = count_items(root);
     return action;
 }
 
-static struct child* find_from_filename(char* filename, struct folder *root)
+static struct child* find_from_filename(const char* filename, struct folder *root)
 {
-    char *slash = strchr(filename, '/');
-    int i = 0;
-    if (slash)
-        *slash = '\0';
     if (!root)
         return NULL;
-
+    const char *slash = strchr(filename, '/');
     struct child *this;
 
     /* filenames beginning with a / are specially treated as the
      * loop below can't handle them. they can only occur on the first,
      * and not recursive, calls to this function.*/
-    if (slash == filename)
+    if (filename[0] == '/') /* in the loop nothing starts with '/' */
     {
+        logf("find_from_filename [%s]", filename);
         /* filename begins with /. in this case root must be the
          * top level folder */
         this = &root->children[0];
-        if (!slash[1])
+        if (filename[1] == '\0')
         {   /* filename == "/" */
             return this;
         }
-        else
-        {
-            /* filename == "/XXX/YYY". cascade down */
-            if (!this->folder)
-                this->folder = load_folder(root, this->name);
-            this->state = EXPANDED;
-            /* recurse with XXX/YYY */
-            return find_from_filename(slash+1, this->folder);
-        }
+        else /* filename == "/XXX/YYY". cascade down */
+            goto cascade;
     }
 
-    while (i < root->children_count)
+    for (int i = 0; i < root->children_count; i++)
     {
         this = &root->children[i];
-        if (!strcasecmp(this->name, filename))
+        /* when slash == NULL n will be really large but \0 stops the compare */
+        if (strncasecmp(this->name, filename, slash - filename) == 0)
         {
-            if (!slash)
+            if (slash == NULL)
             {   /* filename == XXX */
                 return this;
             }
             else
-            {
-                /* filename == XXX/YYY. cascade down */
-                if (!this->folder)
-                    this->folder = load_folder(root, this->name);
-                this->state = EXPANDED;
-                return find_from_filename(slash+1, this->folder);
-            }
+                goto cascade;
         }
-        i++;
     }
     return NULL;
+
+cascade:
+    /* filename == XXX/YYY. cascade down */
+    child_set_state_expand(this, root);
+    while (slash[0] == '/') slash++; /* eat slashes */
+    return find_from_filename(slash, this->folder);
 }
 
-/* _modifies_ buf */
-int select_paths(struct folder* root, char* buf)
+static int select_paths(struct folder* root, const char* filenames)
 {
-    struct child *item = find_from_filename(buf, root);
-    if (item)
-        item->state = SELECTED;
+    /* Takes a list of filenames in a ':' delimited string
+       splits filenames at the ':' character loads each into buffer
+       selects each file in the folder list
+
+       if last item or only item the rest of the string is copied to the buffer
+       *End the last item WITHOUT the ':' character /.rockbox/eqs:/.rockbox/wps\0*
+   */
+    char buf[MAX_PATH];
+    const int buflen = sizeof(buf);
+
+    const char *fnp = filenames;
+    const char *lastfnp = fnp;
+    const char *sstr;
+    off_t len;
+
+    while (fnp)
+    {
+        fnp = strchr(fnp, ':');
+        if (fnp)
+        {
+            len = fnp - lastfnp;
+            fnp++;
+        }
+        else /* no ':' get the rest of the string */
+            len = strlen(lastfnp);
+
+        sstr = lastfnp;
+        lastfnp = fnp;
+        if (len <= 0 || len > buflen)
+            continue;
+        strlcpy(buf, sstr, len + 1);
+        struct child *item = find_from_filename(buf, root);
+        if (item)
+            item->state = SELECTED;
+    }
+
     return 0;
 }
 
-static void save_folders_r(struct folder *root, char* dst, size_t maxlen)
+static void save_folders_r(struct folder *root, char* dst, size_t maxlen, size_t buflen)
 {
-    int i = 0;
+    size_t len;
+    struct folder *curfolder;
+    char* name;
 
-    while (i < root->children_count)
+    for (int i = 0; i < root->children_count; i++)
     {
         struct child *this = &root->children[i];
         if (this->state == SELECTED)
         {
-            if (this->folder)
-                snprintf(buffer_front, buffer_end - buffer_front,
-                        "%s:", get_full_path(this->folder));
+            if (this->folder == NULL)
+            {
+                curfolder = root;
+                name = this->name;
+                logf("save_folders_r: this->name[%s]", name);
+            }
+            else
+            {
+                curfolder = this->folder->previous;
+                name = this->folder->name;
+                logf("save_folders_r: this->folder->name[%s]", name);
+            }
+
+            len = get_full_path(curfolder, buffer_front, buflen);
+
+            if (len + 2 >= buflen)
+                continue;
+
+            len += snprintf(&buffer_front[len], buflen - len, "%s:", name);
+            logf("save_folders_r: [%s]", buffer_front);
+            if (dst != hashed.buf)
+            {
+                int dlen = strlen(dst);
+                if (dlen + len >= maxlen)
+                    continue;
+                strlcpy(&dst[dlen], buffer_front, maxlen - dlen);
+            }
             else
             {
-                char *p = get_full_path(root);
-                snprintf(buffer_front, buffer_end - buffer_front,
-                        "%s/%s:", strcmp(p, "/") ? p : "",
-                                  strcmp(this->name, "/") ? this->name : "");
+                if (hashed.len + len >= maxlen)
+                {
+                    hashed.maxlen_exceeded = 1;
+                    continue;
+                }
+                get_hash(buffer_front, &hashed.val, len);
+                hashed.len += len;
             }
-            strlcat(dst, buffer_front, maxlen);
         }
         else if (this->state == EXPANDED)
-            save_folders_r(this->folder, dst, maxlen);
-        i++;
+            save_folders_r(this->folder, dst, maxlen, buflen);
     }
 }
 
-static void save_folders(struct folder *root, char* dst, size_t maxlen)
+static uint32_t save_folders(struct folder *root, char* dst, size_t maxlen)
 {
-    int len;
+    hashed.len = 0;
+    hashed.val = 0;
+    hashed.maxlen_exceeded = 0;
+    size_t len = buffer_end - buffer_front;
     dst[0] = '\0';
-    save_folders_r(root, dst, maxlen);
+    save_folders_r(root, dst, maxlen, len);
     len = strlen(dst);
     /* fix trailing ':' */
     if (len > 1) dst[len-1] = '\0';
+    /*Notify - user will probably not see save dialog if nothing new got added*/
+    if (hashed.maxlen_exceeded > 0) splash(HZ *2, ID2P(LANG_SHOWDIR_BUFFER_FULL));
+    return hashed.val;
 }
 
 bool folder_select(char* setting, int setting_len)
@@ -483,40 +602,32 @@ bool folder_select(char* setting, int setting_len)
     struct folder *root;
     struct simplelist_info info;
     size_t buf_size;
-    /* 32 separate folders should be Enough For Everybody(TM) */
-    char *vect[32];
-    char copy[setting_len];
-    int nb_items;
-
-    /* copy onto stack as split_string() modifies it */
-    strlcpy(copy, setting, setting_len);
-    nb_items = split_string(copy, ':', vect, ARRAYLEN(vect));
 
     buffer_front = plugin_get_buffer(&buf_size);
     buffer_end = buffer_front + buf_size;
+    logf("%d bytes free", (int)(buffer_end - buffer_front));
     root = load_root();
 
-    if (nb_items > 0)
-    {
-        for(int i = 0; i < nb_items; i++)
-            select_paths(root, vect[i]);
-    }
-
+    logf("folders in: %s", setting);
+    /* Load previous selection(s) */
+    select_paths(root, setting);
+    /* get current hash to check for changes later */
+    uint32_t hash = save_folders(root, hashed.buf, setting_len);
     simplelist_info_init(&info, str(LANG_SELECT_FOLDER),
             count_items(root), root);
     info.get_name = folder_get_name;
     info.action_callback = folder_action_callback;
     info.get_icon = folder_get_icon;
     simplelist_show_list(&info);
-
+    logf("%d bytes free", (int)(buffer_end - buffer_front));
     /* done editing. check for changes */
-    save_folders(root, copy, setting_len);
-    if (strcmp(copy, setting))
-    {   /* prompt for saving changes and commit if yes */
+    if (hash != save_folders(root, hashed.buf, setting_len))
+    {  /* prompt for saving changes and commit if yes */
         if (yesno_pop(ID2P(LANG_SAVE_CHANGES)))
         {
-            strcpy(setting, copy);
+            save_folders(root, setting, setting_len);
             settings_save();
+            logf("folders out: %s", setting);
             return true;
         }
     }