src/tree.c

   1 /*
   2  * This program is free software; you can redistribute it and/or
   3  * modify it under the terms of the GNU General Public License
   4  * as published by the Free Software Foundation; either version 2
   5  * of the License, or (at your option) any later version.
   6  *
   7  * This program is distributed in the hope that it will be useful,
   8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  10  * GNU General Public License for more details.
  11  *
  12  * You should have received a copy of the GNU General Public License
  13  * along with this program; if not, write to the Free Software
  14  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  15  *
  16  * See the COPYING file for license information.
  17  *
  18  * Guillaume Chazarain <guichaz@yahoo.fr>
  19  */
  20
  21 /************************************************************
  22  * The filenames tree, shown in images menus and serialized *
  23  ************************************************************/
  24
  25 #include <string.h>             /* strchr(), strrchr(), strlen() */
  26
  27 #include "gliv.h"
  28 #include "tree.h"
  29 #include "str_utils.h"
  30 #include "files_list.h"
  31 #include "timestamp.h"
  32
  33 /* Last made tree. */
  34 static GNode *last_tree = NULL;
  35
  36 /* Its creation date. */
  37 static DECLARE_TIMESTAMP(timestamp);
  38
  39 /* We make sure there is only one user. */
  40 static volatile gboolean cancel = FALSE;
  41 G_LOCK_DEFINE_STATIC(tree);
  42
  43 void end_using_tree(void)
  44 {
  45     cancel = FALSE;
  46     G_UNLOCK(tree);
  47 }
  48
  49 void cancel_using_tree(void)
  50 {
  51     cancel = TRUE;
  52 }
  53
  54 gboolean canceled_using_tree(void)
  55 {
  56     return cancel;
  57 }
  58
  59 /* Constructor. */
  60 static tree_item *new_item(gchar * name, gchar * path)
  61 {
  62     tree_item *item;
  63
  64     item = g_new(tree_item, 1);
  65     item->name = name;
  66     item->path = path;
  67     item->thumb_key = NULL;
  68     item->thumb = NULL;
  69
  70     return item;
  71 }
  72
  73 typedef enum {
  74     DIR_PARENT,
  75     DIR_EQUAL,
  76     DIR_DIFFERENT
  77 } dir_type;
  78
  79 /* Whether dir1 is parent, equal or different from the dir where file2 is. */
  80 static dir_type dir_wrt_file(const gchar * dir1, const gchar * file2)
  81 {
  82     const gchar *ptr1;
  83     gchar *ptr2, *last_slash;
  84     dir_type res;
  85
  86     if (dir1[0] == '\0')
  87         /* dir1 == "". */
  88         return DIR_PARENT;
  89
  90     if (dir1[0] == '/' && dir1[1] == '\0' && file2[0] == '/')
  91         /* dir1 == "/" and file2 == "/...". */
  92         return strchr(file2 + 1, '/') == NULL ? DIR_EQUAL : DIR_PARENT;
  93
  94     /* We temporarily cut the filename to have the dirname. */
  95     ptr2 = (gchar *) file2;
  96     last_slash = strrchr(file2, '/');
  97     if (last_slash)
  98         *last_slash = '\0';
  99
 100     ptr1 = dir1;
 101
 102     /* Skip identical characters in the paths. */
 103     while (*ptr1 != '\0' && *ptr1 == *ptr2) {
 104         ptr1++;
 105         ptr2++;
 106     }
 107
 108     if (*ptr1 == *ptr2)
 109         res = DIR_EQUAL;
 110
 111     else if (*ptr1 == '\0' && *ptr2 == '/')
 112         res = DIR_PARENT;
 113
 114     else
 115         res = DIR_DIFFERENT;
 116
 117     if (last_slash)
 118         *last_slash = '/';
 119
 120     return res;
 121 }
 122
 123 /* When file == parent"/a/b/c...", it returns "a". */
 124 static gchar *first_dir(const gchar * file, const gchar * parent)
 125 {
 126     const gchar *res;
 127     gchar *end;
 128
 129     if (parent[0] == '\0' && file[0] == '/')
 130         return g_strdup("/");
 131
 132     /* Skip identical characters in the paths. */
 133     while (*file == *parent) {
 134         file++;
 135         parent++;
 136     }
 137
 138     /* Suppress the leading separator. */
 139     if (file[0] == '/')
 140         file++;
 141
 142     res = file;
 143
 144     /* Keep only the first dir by looking for the second one, or the file */
 145     end = strchr(file, '/');
 146
 147     /* and throwing it away. */
 148     return g_strndup(res, end - res);
 149 }
 150
 151 static void make_tree_rec(GNode * parent, gchar *** array_ptr)
 152 {
 153     gchar *this_dir;
 154     gchar *name, *path;
 155     GNode *node;
 156     tree_item *item;
 157
 158     item = parent->data;
 159     this_dir = item->path;
 160
 161     while (**array_ptr != NULL) {
 162         switch (dir_wrt_file(this_dir, **array_ptr)) {
 163         case DIR_PARENT:
 164             /* Subdirectory => add it, then recursive call. */
 165             name = first_dir(**array_ptr, this_dir);
 166             path = g_build_filename(this_dir, name, NULL);
 167             item = new_item(name, path);
 168
 169             node = g_node_new(item);
 170             g_node_append(parent, node);
 171
 172             make_tree_rec(node, array_ptr);
 173             break;
 174
 175         case DIR_EQUAL:
 176             /* Same directory => add the filename, stay in the loop. */
 177             name = **array_ptr + strlen(this_dir);
 178             while (name[0] == '/')
 179                 name++;
 180
 181             item = new_item(g_strdup(name), **array_ptr);
 182             g_node_append_data(parent, item);
 183             (*array_ptr)++;
 184             break;
 185
 186             /* case DIR_DIFFERENT: */
 187         default:
 188             /* Return from the recursive calls to find a common directory. */
 189             return;
 190         }
 191     }
 192 }
 193
 194 static gboolean destroy_node(GNode * node)
 195 {
 196     tree_item *item = node->data;
 197
 198     if (G_NODE_IS_LEAF(node))
 199         g_free(item->thumb_key);
 200     else
 201         g_free(item->path);
 202
 203     g_free(item->name);
 204     g_free(item);
 205     return FALSE;
 206 }
 207
 208 static void set_parent(GNode * node, gpointer parent)
 209 {
 210     node->parent = parent;
 211 }
 212
 213 static void compress_node(GNode * node)
 214 {
 215     GNode *child;
 216     tree_item *item, *child_item;
 217     gchar *new_name;
 218
 219     if (g_node_nth_child(node, 1) != NULL)
 220         /* More than one child */
 221         return;
 222
 223     item = node->data;
 224
 225     child = g_node_first_child(node);
 226     child_item = child->data;
 227
 228     /* Skip one level. */
 229     g_node_children_foreach(child, G_TRAVERSE_ALL, set_parent, node);
 230     node->children = child->children;
 231
 232     /* Concatenate the names. */
 233     new_name = g_build_filename(item->name, child_item->name, NULL);
 234     g_free(item->name);
 235     item->name = new_name;
 236
 237     /* Use the child path. */
 238     g_free(item->path);
 239     item->path = child_item->path;
 240     child_item->path = NULL;
 241
 242     /* Get rid of the compressed child. */
 243     destroy_node(child);
 244     child->parent = NULL;
 245     child->children = NULL;
 246     g_node_destroy(child);
 247 }
 248
 249 static gboolean to_utf8(GNode * node)
 250 {
 251     tree_item *item;
 252     gchar *converted;
 253
 254     item = node->data;
 255     converted = (gchar *) filename_to_utf8(item->name);
 256     if (item->name != converted) {
 257         g_free(item->name);
 258         item->name = g_strdup(converted);
 259     }
 260
 261     return FALSE;
 262 }
 263
 264 /*
 265  * We change the tree structure so it is
 266  * safer to use our own traverse function.
 267  */
 268 static void compress_tree(GNode * node)
 269 {
 270     if (G_NODE_IS_LEAF(node) == FALSE) {
 271         g_node_children_foreach(node, G_TRAVERSE_ALL,
 272                                 (GNodeForeachFunc) compress_tree, NULL);
 273         compress_node(node);
 274     }
 275 }
 276
 277 static void print_tree(GNode * tree, gint level);
 278
 279 /* Can we avoid rebuilding a tree? */
 280 gboolean last_tree_ok(timestamp_t menu_timestamp)
 281 {
 282     timestamp_t list_timestamp = get_list_timestamp();
 283
 284     if (last_tree == NULL)
 285         /* No tree to reuse. */
 286         return FALSE;
 287
 288     if (up_to_date(timestamp, list_timestamp) == FALSE)
 289         /* The list has changed. */
 290         return FALSE;
 291
 292     if (menu_timestamp)
 293         return up_to_date(menu_timestamp, timestamp);
 294
 295
 296     return TRUE;
 297 }
 298
 299 GNode *make_tree(void)
 300 {
 301     GNode *tree;
 302     tree_item *item;
 303     gchar **array;
 304     gchar **array_ptr;
 305
 306     if (G_TRYLOCK(tree) == FALSE)
 307         return NULL;
 308
 309     cancel = FALSE;
 310     if (last_tree_ok(0))
 311         return last_tree;
 312
 313     invalidate_last_tree();
 314
 315     array_ptr = array = get_sorted_files_array();
 316     if (array == NULL) {
 317         G_UNLOCK(tree);
 318         return NULL;
 319     }
 320
 321     item = new_item(g_strdup(""), g_strdup(""));
 322     tree = g_node_new(item);
 323
 324     /* Build the tree. */
 325     while (*array_ptr != NULL)
 326         make_tree_rec(tree, &array_ptr);
 327
 328     g_free(array);
 329
 330     compress_tree(tree);
 331
 332     g_node_traverse(tree, G_POST_ORDER, G_TRAVERSE_ALL, -1,
 333                     (GNodeTraverseFunc) to_utf8, NULL);
 334
 335     print_tree(tree, 0);
 336
 337     last_tree = tree;
 338     touch(&timestamp);
 339     return tree;
 340 }
 341
 342 void destroy_tree(GNode * tree)
 343 {
 344     g_node_traverse(tree, G_POST_ORDER, G_TRAVERSE_ALL, -1,
 345                     (GNodeTraverseFunc) destroy_node, NULL);
 346
 347     g_node_destroy(tree);
 348 }
 349
 350 void invalidate_last_tree(void)
 351 {
 352     if (last_tree) {
 353         destroy_tree(last_tree);
 354         last_tree = NULL;
 355         reset_timestamp(&timestamp);
 356     }
 357 }
 358
 359 static void print_tree(GNode * tree, gint level)
 360 {
 361 #if 0
 362     gint i;
 363     tree_item *item = tree->data;
 364
 365     for (i = 0; i < level; i++)
 366         printf("    ");
 367
 368     printf("name: \"%s\", path: \"%s\"\n", item->name, item->path);
 369
 370     level++;
 371     g_node_children_foreach(tree, G_TRAVERSE_ALL,
 372                             print_tree, GINT_TO_POINTER(level));
 373 #endif
 374 }