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 gboolean cancel_using_tree(void)
  50 {
  51     cancel = TRUE;
  52     return FALSE;
  53 }
  54
  55 gboolean canceled_using_tree(void)
  56 {
  57     return cancel;
  58 }
  59
  60 /* Constructor. */
  61 static tree_item *new_item(gchar * name, gchar * path)
  62 {
  63     tree_item *item;
  64
  65     item = g_new(tree_item, 1);
  66     item->name = name;
  67     item->path = path;
  68     item->thumb_key = NULL;
  69     item->thumb = NULL;
  70
  71     return item;
  72 }
  73
  74 typedef enum {
  75     DIR_PARENT,
  76     DIR_EQUAL,
  77     DIR_DIFFERENT
  78 } dir_type;
  79
  80 /* Whether dir1 is parent, equal or different from the dir where file2 is. */
  81 static dir_type dir_wrt_file(const gchar * dir1, const gchar * file2)
  82 {
  83     const gchar *ptr1;
  84     gchar *ptr2, *last_slash;
  85     dir_type res;
  86
  87     if (dir1[0] == '\0')
  88         /* dir1 == "". */
  89         return DIR_PARENT;
  90
  91     if (dir1[0] == '/' && dir1[1] == '\0' && file2[0] == '/')
  92         /* dir1 == "/" and file2 == "/...". */
  93         return strchr(file2 + 1, '/') == NULL ? DIR_EQUAL : DIR_PARENT;
  94
  95     /* We temporarily cut the filename to have the dirname. */
  96     ptr2 = (gchar *) file2;
  97     last_slash = strrchr(file2, '/');
  98     if (last_slash)
  99         *last_slash = '\0';
 100
 101     ptr1 = dir1;
 102
 103     /* Skip identical characters in the paths. */
 104     while (*ptr1 != '\0' && *ptr1 == *ptr2) {
 105         ptr1++;
 106         ptr2++;
 107     }
 108
 109     if (*ptr1 == *ptr2)
 110         res = DIR_EQUAL;
 111
 112     else if (*ptr1 == '\0' && *ptr2 == '/')
 113         res = DIR_PARENT;
 114
 115     else
 116         res = DIR_DIFFERENT;
 117
 118     if (last_slash)
 119         *last_slash = '/';
 120
 121     return res;
 122 }
 123
 124 /* When file == parent"/a/b/c...", it returns "a". */
 125 static gchar *first_dir(const gchar * file, const gchar * parent)
 126 {
 127     const gchar *res;
 128     gint prefix_length;
 129     gchar *end;
 130
 131     if (parent[0] == '\0' && file[0] == '/')
 132         return g_strdup("/");
 133
 134     prefix_length = common_prefix_length(file, parent);
 135     file += prefix_length;
 136     parent += prefix_length;
 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
 184             /* I like stars :) */
 185             do {
 186                 (*array_ptr)++;
 187             } while (**array_ptr != NULL &&
 188                      g_str_equal(**array_ptr, *(*array_ptr - 1)));
 189             break;
 190
 191             /* case DIR_DIFFERENT: */
 192         default:
 193             /* Return from the recursive calls to find a common directory. */
 194             return;
 195         }
 196     }
 197 }
 198
 199 static gboolean destroy_node(GNode * node)
 200 {
 201     tree_item *item = node->data;
 202
 203     if (G_NODE_IS_LEAF(node))
 204         g_free(item->thumb_key);
 205     else
 206         g_free(item->path);
 207
 208     g_free(item->name);
 209     g_free(item);
 210     return FALSE;
 211 }
 212
 213 static void set_parent(GNode * node, gpointer parent)
 214 {
 215     node->parent = parent;
 216 }
 217
 218 static void compress_node(GNode * node)
 219 {
 220     GNode *child;
 221     tree_item *item, *child_item;
 222     gchar *new_name;
 223
 224     if (g_node_nth_child(node, 1) != NULL)
 225         /* More than one child */
 226         return;
 227
 228     item = node->data;
 229
 230     child = g_node_first_child(node);
 231     child_item = child->data;
 232
 233     /* Skip one level. */
 234     g_node_children_foreach(child, G_TRAVERSE_ALL, set_parent, node);
 235     node->children = child->children;
 236
 237     /* Concatenate the names. */
 238     new_name = g_build_filename(item->name, child_item->name, NULL);
 239     g_free(item->name);
 240     item->name = new_name;
 241
 242     /* Use the child path. */
 243     g_free(item->path);
 244     item->path = child_item->path;
 245     child_item->path = NULL;
 246
 247     /* Get rid of the compressed child. */
 248     destroy_node(child);
 249     child->parent = NULL;
 250     child->children = NULL;
 251     g_node_destroy(child);
 252 }
 253
 254 static gboolean to_utf8(GNode * node)
 255 {
 256     tree_item *item;
 257     gchar *converted;
 258
 259     item = node->data;
 260     converted = (gchar *) filename_to_utf8(item->name);
 261     if (item->name != converted) {
 262         g_free(item->name);
 263         item->name = g_strdup(converted);
 264     }
 265
 266     return FALSE;
 267 }
 268
 269 /*
 270  * We change the tree structure so it is
 271  * safer to use our own traverse function.
 272  */
 273 static void compress_tree(GNode * node)
 274 {
 275     if (G_NODE_IS_LEAF(node) == FALSE) {
 276         g_node_children_foreach(node, G_TRAVERSE_ALL,
 277                                 (GNodeForeachFunc) compress_tree, NULL);
 278         compress_node(node);
 279     }
 280 }
 281
 282 static void print_tree(GNode * tree, gint level);
 283
 284 /* Can we avoid rebuilding a tree? */
 285 static gboolean last_tree_ok(void)
 286 {
 287     timestamp_t list_timestamp = get_list_timestamp();
 288
 289     if (last_tree == NULL)
 290         /* No tree to reuse. */
 291         return FALSE;
 292
 293     /* Check if the list has changed. */
 294     return up_to_date(timestamp, list_timestamp);
 295 }
 296
 297 gboolean more_recent_than_tree(timestamp_t ts)
 298 {
 299     if (last_tree_ok() == FALSE)
 300         return FALSE;
 301
 302     return up_to_date(ts, timestamp);
 303 }
 304
 305 GNode *make_tree(void)
 306 {
 307     GNode *tree;
 308     tree_item *item;
 309     gchar **array;
 310     gchar **array_ptr;
 311
 312     if (G_TRYLOCK(tree) == FALSE)
 313         return NULL;
 314
 315     cancel = FALSE;
 316     if (last_tree_ok())
 317         return last_tree;
 318
 319     invalidate_last_tree();
 320
 321     array_ptr = array = get_sorted_files_array();
 322     if (array == NULL) {
 323         G_UNLOCK(tree);
 324         return NULL;
 325     }
 326
 327     item = new_item(g_strdup(""), g_strdup(""));
 328     tree = g_node_new(item);
 329
 330     /* Build the tree. */
 331     while (*array_ptr != NULL)
 332         make_tree_rec(tree, &array_ptr);
 333
 334     g_free(array);
 335
 336     compress_tree(tree);
 337
 338     g_node_traverse(tree, G_POST_ORDER, G_TRAVERSE_ALL, -1,
 339                     (GNodeTraverseFunc) to_utf8, NULL);
 340
 341     print_tree(tree, 0);
 342
 343     last_tree = tree;
 344     touch(&timestamp);
 345     return tree;
 346 }
 347
 348 void destroy_tree(GNode * tree)
 349 {
 350     g_node_traverse(tree, G_POST_ORDER, G_TRAVERSE_ALL, -1,
 351                     (GNodeTraverseFunc) destroy_node, NULL);
 352
 353     g_node_destroy(tree);
 354 }
 355
 356 void invalidate_last_tree(void)
 357 {
 358     if (last_tree) {
 359         destroy_tree(last_tree);
 360         last_tree = NULL;
 361         reset_timestamp(&timestamp);
 362     }
 363 }
 364
 365 static gboolean increment(GNode * unused, gint * count)
 366 {
 367     (*count)++;
 368     return FALSE;
 369 }
 370
 371 gint tree_count_files(void)
 372 {
 373     gint count = 0;
 374
 375     g_node_traverse(last_tree, G_IN_ORDER, G_TRAVERSE_LEAFS, -1,
 376                     (GNodeTraverseFunc) increment, &count);
 377
 378     return count;
 379 }
 380
 381 static void print_tree(GNode * tree, gint level)
 382 {
 383 #if 0
 384     gint i;
 385     tree_item *item = tree->data;
 386
 387     for (i = 0; i < level; i++)
 388         printf("    ");
 389
 390     printf("name: \"%s\", path: \"%s\"\n", item->name, item->path);
 391
 392     level++;
 393     g_node_children_foreach(tree, G_TRAVERSE_ALL,
 394                             print_tree, GINT_TO_POINTER(level));
 395 #endif
 396 }