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.
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.
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.
16 * See the COPYING file for license information.
18 * Guillaume Chazarain <guichaz@gmail.com>
21 /************************************************************
22 * The filenames tree, shown in images menus and serialized *
23 ************************************************************/
25 #include <string.h> /* strchr(), strrchr(), strlen() */
29 #include "str_utils.h"
30 #include "files_list.h"
31 #include "timestamp.h"
34 static GNode
*last_tree
= NULL
;
36 /* Its creation date. */
37 static DECLARE_TIMESTAMP(timestamp
);
39 /* We make sure there is only one user. */
40 static volatile gboolean cancel
= FALSE
;
41 G_LOCK_DEFINE_STATIC(tree
);
43 void end_using_tree(void)
49 gboolean
cancel_using_tree(void)
55 gboolean
canceled_using_tree(void)
61 static tree_item
*new_item(gchar
* name
, gchar
* path
)
65 item
= g_new(tree_item
, 1);
68 item
->thumb_key
= NULL
;
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
)
84 gchar
*ptr2
, *last_slash
;
91 if (dir1
[0] == '/' && dir1
[1] == '\0' && file2
[0] == '/')
92 /* dir1 == "/" and file2 == "/...". */
93 return strchr(file2
+ 1, '/') == NULL
? DIR_EQUAL
: DIR_PARENT
;
95 /* We temporarily cut the filename to have the dirname. */
96 ptr2
= (gchar
*) file2
;
97 last_slash
= strrchr(file2
, '/');
103 /* Skip identical characters in the paths. */
104 while (*ptr1
!= '\0' && *ptr1
== *ptr2
) {
112 else if (*ptr1
== '\0' && *ptr2
== '/')
124 /* When file == parent"/a/b/c...", it returns "a". */
125 static gchar
*first_dir(const gchar
* file
, const gchar
* parent
)
131 if (parent
[0] == '\0' && file
[0] == '/')
132 return g_strdup("/");
134 prefix_length
= common_prefix_length(file
, parent
);
135 file
+= prefix_length
;
136 parent
+= prefix_length
;
138 /* Suppress the leading separator. */
144 /* Keep only the first dir by looking for the second one, or the file */
145 end
= strchr(file
, '/');
147 /* and throwing it away. */
148 return g_strndup(res
, end
- res
);
151 static void make_tree_rec(GNode
* parent
, gchar
*** array_ptr
)
159 this_dir
= item
->path
;
161 while (**array_ptr
!= NULL
) {
162 switch (dir_wrt_file(this_dir
, **array_ptr
)) {
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
);
169 node
= g_node_new(item
);
170 g_node_append(parent
, node
);
172 make_tree_rec(node
, array_ptr
);
176 /* Same directory => add the filename, stay in the loop. */
177 name
= **array_ptr
+ strlen(this_dir
);
178 while (name
[0] == '/')
181 item
= new_item(g_strdup(name
), **array_ptr
);
182 g_node_append_data(parent
, item
);
184 /* I like stars :) */
187 } while (**array_ptr
!= NULL
&&
188 g_str_equal(**array_ptr
, *(*array_ptr
- 1)));
191 /* case DIR_DIFFERENT: */
193 /* Return from the recursive calls to find a common directory. */
199 static gboolean
destroy_node(GNode
* node
)
201 tree_item
*item
= node
->data
;
203 if (G_NODE_IS_LEAF(node
))
204 g_free(item
->thumb_key
);
213 static void set_parent(GNode
* node
, gpointer parent
)
215 node
->parent
= parent
;
218 static void compress_node(GNode
* node
)
221 tree_item
*item
, *child_item
;
224 if (g_node_nth_child(node
, 1) != NULL
)
225 /* More than one child */
230 child
= g_node_first_child(node
);
231 child_item
= child
->data
;
233 /* Skip one level. */
234 g_node_children_foreach(child
, G_TRAVERSE_ALL
, set_parent
, node
);
235 node
->children
= child
->children
;
237 /* Concatenate the names. */
238 new_name
= g_build_filename(item
->name
, child_item
->name
, NULL
);
240 item
->name
= new_name
;
242 /* Use the child path. */
244 item
->path
= child_item
->path
;
245 child_item
->path
= NULL
;
247 /* Get rid of the compressed child. */
249 child
->parent
= NULL
;
250 child
->children
= NULL
;
251 g_node_destroy(child
);
254 static gboolean
to_utf8(GNode
* node
)
260 converted
= (gchar
*) filename_to_utf8(item
->name
);
261 if (item
->name
!= converted
) {
263 item
->name
= g_strdup(converted
);
270 * We change the tree structure so it is
271 * safer to use our own traverse function.
273 static void compress_tree(GNode
* node
)
275 if (G_NODE_IS_LEAF(node
) == FALSE
) {
276 g_node_children_foreach(node
, G_TRAVERSE_ALL
,
277 (GNodeForeachFunc
) compress_tree
, NULL
);
282 static void print_tree(GNode
* tree
, gint level
);
284 /* Can we avoid rebuilding a tree? */
285 static gboolean
last_tree_ok(void)
287 timestamp_t list_timestamp
= get_list_timestamp();
289 if (last_tree
== NULL
)
290 /* No tree to reuse. */
293 /* Check if the list has changed. */
294 return up_to_date(timestamp
, list_timestamp
);
297 gboolean
more_recent_than_tree(timestamp_t ts
)
299 if (last_tree_ok() == FALSE
)
302 return up_to_date(ts
, timestamp
);
305 GNode
*make_tree(void)
312 if (G_TRYLOCK(tree
) == FALSE
)
319 invalidate_last_tree();
321 array_ptr
= array
= get_sorted_files_array();
327 item
= new_item(g_strdup(""), g_strdup(""));
328 tree
= g_node_new(item
);
330 /* Build the tree. */
331 while (*array_ptr
!= NULL
)
332 make_tree_rec(tree
, &array_ptr
);
338 g_node_traverse(tree
, G_POST_ORDER
, G_TRAVERSE_ALL
, -1,
339 (GNodeTraverseFunc
) to_utf8
, NULL
);
348 void destroy_tree(GNode
* tree
)
350 g_node_traverse(tree
, G_POST_ORDER
, G_TRAVERSE_ALL
, -1,
351 (GNodeTraverseFunc
) destroy_node
, NULL
);
353 g_node_destroy(tree
);
356 void invalidate_last_tree(void)
359 destroy_tree(last_tree
);
361 reset_timestamp(×tamp
);
365 static gboolean
increment(GNode
* unused
, gint
* count
)
371 gint
tree_count_files(void)
375 g_node_traverse(last_tree
, G_IN_ORDER
, G_TRAVERSE_LEAFS
, -1,
376 (GNodeTraverseFunc
) increment
, &count
);
381 static void print_tree(GNode
* tree
, gint level
)
385 tree_item
*item
= tree
->data
;
387 for (i
= 0; i
< level
; i
++)
390 printf("name: \"%s\", path: \"%s\"\n", item
->name
, item
->path
);
393 g_node_children_foreach(tree
, G_TRAVERSE_ALL
,
394 print_tree
, GINT_TO_POINTER(level
));