gio/kqueue/dep-list.c

   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 }