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@gmail.com>
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
end_using_tree(void)43 void end_using_tree(void)
44 {
45 cancel = FALSE;
46 G_UNLOCK(tree);
47 }
48
cancel_using_tree(void)49 gboolean cancel_using_tree(void)
50 {
51 cancel = TRUE;
52 return FALSE;
53 }
54
canceled_using_tree(void)55 gboolean canceled_using_tree(void)
56 {
57 return cancel;
58 }
59
60 /* Constructor. */
new_item(gchar * name,gchar * path)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. */
dir_wrt_file(const gchar * dir1,const gchar * file2)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". */
first_dir(const gchar * file,const gchar * parent)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
make_tree_rec(GNode * parent,gchar *** array_ptr)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
destroy_node(GNode * node)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
set_parent(GNode * node,gpointer parent)213 static void set_parent(GNode * node, gpointer parent)
214 {
215 node->parent = parent;
216 }
217
compress_node(GNode * node)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
to_utf8(GNode * node)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 */
compress_tree(GNode * node)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? */
last_tree_ok(void)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
more_recent_than_tree(timestamp_t ts)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
make_tree(void)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(×tamp);
345 return tree;
346 }
347
destroy_tree(GNode * tree)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
invalidate_last_tree(void)356 void invalidate_last_tree(void)
357 {
358 if (last_tree) {
359 destroy_tree(last_tree);
360 last_tree = NULL;
361 reset_timestamp(×tamp);
362 }
363 }
364
increment(GNode * unused,gint * count)365 static gboolean increment(GNode * unused, gint * count)
366 {
367 (*count)++;
368 return FALSE;
369 }
370
tree_count_files(void)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
print_tree(GNode * tree,gint level)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 }
397