1 /*******************************************************************************
2 Copyright (c) 2011, 2012 Dmitry Matveev <me@dmitrymatveev.co.uk>
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 THE SOFTWARE.
21 *******************************************************************************/
22
23 #include <glib.h>
24
25 #include <stdlib.h> /* calloc */
26 #include <stdio.h> /* printf */
27 #include <dirent.h> /* opendir, readdir, closedir */
28 #include <string.h> /* strcmp */
29 #include <assert.h>
30
31 #include "dep-list.h"
32
33 static gboolean kdl_debug_enabled = FALSE;
34 #define perror_msg if (kdl_debug_enabled) g_warning
35
36
37 /**
38 * Print a list to stdout.
39 *
40 * @param[in] dl A pointer to a list.
41 **/
42 void
43 dl_print (const dep_list *dl)
44 {
45 while (dl != NULL) {
46 printf ("%lld:%s ", (long long int) dl->inode, dl->path);
47 dl = dl->next;
48 }
49 printf ("\n");
50 }
51
52 /**
53 * Create a new list item.
54 *
55 * Create a new list item and initialize its fields.
56 *
57 * @param[in] path A name of a file (the string is not copied!).
58 * @param[in] inode A file's inode number.
59 * @return A pointer to a new item or NULL in the case of error.
60 **/
61 dep_list* dl_create (char *path, ino_t inode)
62 {
63 dep_list *dl = calloc (1, sizeof (dep_list));
64 if (dl == NULL) {
65 perror_msg ("Failed to create a new dep-list item");
66 return NULL;
67 }
68
69 dl->path = path;
70 dl->inode = inode;
71 return dl;
72 }
73
74 /**
75 * Create a shallow copy of a list.
76 *
77 * A shallow copy is a copy of a structure, but not the copy of the
78 * contents. All data pointers ('path' in our case) of a list and its
79 * shallow copy will point to the same memory.
80 *
81 * @param[in] dl A pointer to list to make a copy. May be NULL.
82 * @return A shallow copy of the list.
83 **/
84 dep_list*
85 dl_shallow_copy (const dep_list *dl)
86 {
87 dep_list *head;
88 dep_list *cp;
89 const dep_list *it;
90
91 if (dl == NULL) {
92 return NULL;
93 }
94
95 head = calloc (1, sizeof (dep_list));
96 if (head == NULL) {
97 perror_msg ("Failed to allocate head during shallow copy");
98 return NULL;
99 }
100
101 cp = head;
102 it = dl;
103
104 while (it != NULL) {
105 cp->path = it->path;
106 cp->inode = it->inode;
107 if (it->next) {
108 cp->next = calloc (1, sizeof (dep_list));
109 if (cp->next == NULL) {
110 perror_msg ("Failed to allocate a new element during shallow copy");
111 dl_shallow_free (head);
112 return NULL;
113 }
114 cp = cp->next;
115 }
116 it = it->next;
117 }
118
119 return head;
120 }
121
122 /**
123 * Free the memory allocated for shallow copy.
124 *
125 * This function will free the memory used by a list structure, but
126 * the list data will remain in the heap.
127 *
128 * @param[in] dl A pointer to a list. May be NULL.
129 **/
130 void
131 dl_shallow_free (dep_list *dl)
132 {
133 while (dl != NULL) {
134 dep_list *ptr = dl;
135 dl = dl->next;
136 free (ptr);
137 }
138 }
139
140 /**
141 * Free the memory allocated for a list.
142 *
143 * This function will free all the memory used by a list: both
144 * list structure and the list data.
145 *
146 * @param[in] dl A pointer to a list. May be NULL.
147 **/
148 void
149 dl_free (dep_list *dl)
150 {
151 while (dl != NULL) {
152 dep_list *ptr = dl;
153 dl = dl->next;
154
155 free (ptr->path);
156 free (ptr);
157 }
158 }
159
160 /**
161 * Create a directory listing and return it as a list.
162 *
163 * @param[in] path A path to a directory.
164 * @return A pointer to a list. May return NULL, check errno in this case.
165 **/
166 dep_list*
167 dl_listing (const char *path)
168 {
169 dep_list *head = NULL;
170 dep_list *prev = NULL;
171 DIR *dir;
172
173 assert (path != NULL);
174
175 dir = opendir (path);
176 if (dir != NULL) {
177 struct dirent *ent;
178
179 while ((ent = readdir (dir)) != NULL) {
180 dep_list *iter;
181
182 if (!strcmp (ent->d_name, ".") || !strcmp (ent->d_name, "..")) {
183 continue;
184 }
185
186 if (head == NULL) {
187 head = calloc (1, sizeof (dep_list));
188 if (head == NULL) {
189 perror_msg ("Failed to allocate head during listing");
190 goto error;
191 }
192 }
193
194 iter = (prev == NULL) ? head : calloc (1, sizeof (dep_list));
195 if (iter == NULL) {
196 perror_msg ("Failed to allocate a new element during listing");
197 goto error;
198 }
199
200 iter->path = strdup (ent->d_name);
201 if (iter->path == NULL) {
202 perror_msg ("Failed to copy a string during listing");
203 goto error;
204 }
205
206 iter->inode = ent->d_ino;
207 iter->next = NULL;
208 if (prev) {
209 prev->next = iter;
210 }
211 prev = iter;
212 }
213
214 closedir (dir);
215 }
216 return head;
217
218 error:
219 if (dir != NULL) {
220 closedir (dir);
221 }
222 dl_free (head);
223 return NULL;
224 }
225
226 /**
227 * Perform a diff on lists.
228 *
229 * This function performs something like a set intersection. The same items
230 * will be removed from the both lists. Items are comapred by a filename.
231 *
232 * @param[in,out] before A pointer to a pointer to a list. Will contain items
233 * which were not found in the 'after' list.
234 * @param[in,out] after A pointer to a pointer to a list. Will contain items
235 * which were not found in the 'before' list.
236 **/
237 void
238 dl_diff (dep_list **before, dep_list **after)
239 {
240 dep_list *before_iter;
241 dep_list *before_prev;
242
243 assert (before != NULL);
244 assert (after != NULL);
245
246 if (*before == NULL || *after == NULL) {
247 return;
248 }
249
250 before_iter = *before;
251 before_prev = NULL;
252
253 while (before_iter != NULL) {
254 dep_list *after_iter = *after;
255 dep_list *after_prev = NULL;
256 dep_list *oldptr;
257
258 int matched = 0;
259 while (after_iter != NULL) {
260 if (strcmp (before_iter->path, after_iter->path) == 0) {
261 matched = 1;
262 /* removing the entry from the both lists */
263 if (before_prev) {
264 before_prev->next = before_iter->next;
265 } else {
266 *before = before_iter->next;
267 }
268
269 if (after_prev) {
270 after_prev->next = after_iter->next;
271 } else {
272 *after = after_iter->next;
273 }
274 free (after_iter);
275 break;
276 }
277 after_prev = after_iter;
278 after_iter = after_iter->next;
279 }
280
281 oldptr = before_iter;
282 before_iter = before_iter->next;
283 if (matched == 0) {
284 before_prev = oldptr;
285 } else {
286 free (oldptr);
287 }
288 }
289 }
290
291
292 /**
293 * Traverses two lists. Compares items with a supplied expression
294 * and performs the passed code on a match. Removes the matched entries
295 * from the both lists.
296 **/
297 #define EXCLUDE_SIMILAR(removed_list, added_list, match_expr, matched_code) \
298 G_STMT_START { \
299 dep_list *removed_list##_iter; \
300 dep_list *removed_list##_prev; \
301 int productive = 0; \
302 \
303 assert (removed_list != NULL); \
304 assert (added_list != NULL); \
305 \
306 removed_list##_iter = *removed_list; \
307 removed_list##_prev = NULL; \
308 \
309 while (removed_list##_iter != NULL) { \
310 dep_list *added_list##_iter = *added_list; \
311 dep_list *added_list##_prev = NULL; \
312 dep_list *oldptr; \
313 \
314 int matched = 0; \
315 while (added_list##_iter != NULL) { \
316 if (match_expr) { \
317 matched = 1; \
318 ++productive; \
319 matched_code; \
320 \
321 if (removed_list##_prev) { \
322 removed_list##_prev->next = removed_list##_iter->next; \
323 } else { \
324 *removed_list = removed_list##_iter->next; \
325 } \
326 if (added_list##_prev) { \
327 added_list##_prev->next = added_list##_iter->next; \
328 } else { \
329 *added_list = added_list##_iter->next; \
330 } \
331 free (added_list##_iter); \
332 break; \
333 } \
334 added_list##_iter = added_list##_iter->next; \
335 } \
336 oldptr = removed_list##_iter; \
337 removed_list##_iter = removed_list##_iter->next; \
338 if (matched == 0) { \
339 removed_list##_prev = oldptr; \
340 } else { \
341 free (oldptr); \
342 } \
343 } \
344 return (productive > 0); \
345 } G_STMT_END
346
347
348 #define cb_invoke(cbs, name, udata, ...) \
349 do { \
350 if (cbs->name) { \
351 (cbs->name) (udata, ## __VA_ARGS__); \
352 } \
353 } while (0)
354
355 /**
356 * Detect and notify about moves in the watched directory.
357 *
358 * A move is what happens when you rename a file in a directory, and
359 * a new name is unique, i.e. you didn't overwrite any existing files
360 * with this one.
361 *
362 * @param[in,out] removed A list of the removed files in the directory.
363 * @param[in,out] added A list of the added files of the directory.
364 * @param[in] cbs A pointer to #traverse_cbs, a user-defined set of
365 * traverse callbacks.
366 * @param[in] udata A pointer to the user-defined data.
367 * @return 0 if no files were renamed, >0 otherwise.
368 **/
369 static int
370 dl_detect_moves (dep_list **removed,
371 dep_list **added,
372 const traverse_cbs *cbs,
373 void *udata)
374 {
375 assert (cbs != NULL);
376
377 EXCLUDE_SIMILAR
378 (removed, added,
379 (removed_iter->inode == added_iter->inode),
380 {
381 cb_invoke (cbs, moved, udata,
382 removed_iter->path, removed_iter->inode,
383 added_iter->path, added_iter->inode);
384 });
385 }
386
387 /**
388 * Detect and notify about replacements in the watched directory.
389 *
390 * Consider you are watching a directory foo with the following files
391 * insinde:
392 *
393 * foo/bar
394 * foo/baz
395 *
396 * A replacement in a watched directory is what happens when you invoke
397 *
398 * mv /foo/bar /foo/bar
399 *
400 * i.e. when you replace a file in a watched directory with another file
401 * from the same directory.
402 *
403 * @param[in,out] removed A list of the removed files in the directory.
404 * @param[in,out] current A list with the current contents of the directory.
405 * @param[in] cbs A pointer to #traverse_cbs, a user-defined set of
406 * traverse callbacks.
407 * @param[in] udata A pointer to the user-defined data.
408 * @return 0 if no files were renamed, >0 otherwise.
409 **/
410 static int
411 dl_detect_replacements (dep_list **removed,
412 dep_list **current,
413 const traverse_cbs *cbs,
414 void *udata)
415 {
416 assert (cbs != NULL);
417
418 EXCLUDE_SIMILAR
419 (removed, current,
420 (removed_iter->inode == current_iter->inode),
421 {
422 cb_invoke (cbs, replaced, udata,
423 removed_iter->path, removed_iter->inode,
424 current_iter->path, current_iter->inode);
425 });
426 }
427
428 /**
429 * Detect and notify about overwrites in the watched directory.
430 *
431 * Consider you are watching a directory foo with a file inside:
432 *
433 * foo/bar
434 *
435 * And you also have a directory tmp with a file 1:
436 *
437 * tmp/1
438 *
439 * You do not watching directory tmp.
440 *
441 * An overwrite in a watched directory is what happens when you invoke
442 *
443 * mv /tmp/1 /foo/bar
444 *
445 * i.e. when you overwrite a file in a watched directory with another file
446 * from the another directory.
447 *
448 * @param[in,out] previous A list with the previous contents of the directory.
449 * @param[in,out] current A list with the current contents of the directory.
450 * @param[in] cbs A pointer to #traverse_cbs, a user-defined set of
451 * traverse callbacks.
452 * @param[in] udata A pointer to the user-defined data.
453 * @return 0 if no files were renamed, >0 otherwise.
454 **/
455 static int
456 dl_detect_overwrites (dep_list **previous,
457 dep_list **current,
458 const traverse_cbs *cbs,
459 void *udata)
460 {
461 assert (cbs != NULL);
462
463 EXCLUDE_SIMILAR
464 (previous, current,
465 (strcmp (previous_iter->path, current_iter->path) == 0
466 && previous_iter->inode != current_iter->inode),
467 {
468 cb_invoke (cbs, overwritten, udata, current_iter->path, current_iter->inode);
469 });
470 }
471
472
473 /**
474 * Traverse a list and invoke a callback for each item.
475 *
476 * @param[in] list A #dep_list.
477 * @param[in] cb A #single_entry_cb callback function.
478 * @param[in] udata A pointer to the user-defined data.
479 **/
480 static void
481 dl_emit_single_cb_on (dep_list *list,
482 single_entry_cb cb,
483 void *udata)
484 {
485 while (cb && list != NULL) {
486 (cb) (udata, list->path, list->inode);
487 list = list->next;
488 }
489 }
490
491
492 /**
493 * Recognize all the changes in the directory, invoke the appropriate callbacks.
494 *
495 * This is the core function of directory diffing submodule.
496 *
497 * @param[in] before The previous contents of the directory.
498 * @param[in] after The current contents of the directory.
499 * @param[in] cbs A pointer to user callbacks (#traverse_callbacks).
500 * @param[in] udata A pointer to user data.
501 **/
502 void
503 dl_calculate (dep_list *before,
504 dep_list *after,
505 const traverse_cbs *cbs,
506 void *udata)
507 {
508 int need_update = 0;
509 dep_list *was = dl_shallow_copy (before);
510 dep_list *pre = dl_shallow_copy (before);
511 dep_list *now = dl_shallow_copy (after);
512 dep_list *lst = dl_shallow_copy (after);
513
514 assert (cbs != NULL);
515
516 dl_diff (&was, &now);
517
518 need_update += dl_detect_moves (&was, &now, cbs, udata);
519 need_update += dl_detect_replacements (&was, &lst, cbs, udata);
520 dl_detect_overwrites (&pre, &lst, cbs, udata);
521
522 if (need_update) {
523 cb_invoke (cbs, names_updated, udata);
524 }
525
526 dl_emit_single_cb_on (was, cbs->removed, udata);
527 dl_emit_single_cb_on (now, cbs->added, udata);
528
529 cb_invoke (cbs, many_added, udata, now);
530 cb_invoke (cbs, many_removed, udata, was);
531
532 dl_shallow_free (lst);
533 dl_shallow_free (now);
534 dl_shallow_free (pre);
535 dl_shallow_free (was);
536 }