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     if (dl == NULL) {
  88         return NULL;
  89     }
  90
  91     dep_list *head = calloc (1, sizeof (dep_list));
  92     if (head == NULL) {
  93         perror_msg ("Failed to allocate head during shallow copy");
  94         return NULL;
  95     }
  96
  97     dep_list *cp = head;
  98     const dep_list *it = dl;
  99
 100     while (it != NULL) {
 101         cp->path = it->path;
 102         cp->inode = it->inode;
 103         if (it->next) {
 104             cp->next = calloc (1, sizeof (dep_list));
 105             if (cp->next == NULL) {
 106                 perror_msg ("Failed to allocate a new element during shallow copy");
 107                 dl_shallow_free (head);
 108                 return NULL;
 109             }
 110             cp = cp->next;
 111         }
 112         it = it->next;
 113     }
 114
 115     return head;
 116 }
 117
 118 /**
 119  * Free the memory allocated for shallow copy.
 120  *
 121  * This function will free the memory used by a list structure, but
 122  * the list data will remain in the heap.
 123  *
 124  * @param[in] dl A pointer to a list. May be NULL.
 125  **/
 126 void
 127 dl_shallow_free (dep_list *dl)
 128 {
 129     while (dl != NULL) {
 130         dep_list *ptr = dl;
 131         dl = dl->next;
 132         free (ptr);
 133     }
 134 }
 135
 136 /**
 137  * Free the memory allocated for a list.
 138  *
 139  * This function will free all the memory used by a list: both
 140  * list structure and the list data.
 141  *
 142  * @param[in] dl A pointer to a list. May be NULL.
 143  **/
 144 void
 145 dl_free (dep_list *dl)
 146 {
 147     while (dl != NULL) {
 148         dep_list *ptr = dl;
 149         dl = dl->next;
 150
 151         free (ptr->path);
 152         free (ptr);
 153     }
 154 }
 155
 156 /**
 157  * Create a directory listing and return it as a list.
 158  *
 159  * @param[in] path A path to a directory.
 160  * @return A pointer to a list. May return NULL, check errno in this case.
 161  **/
 162 dep_list*
 163 dl_listing (const char *path)
 164 {
 165     assert (path != NULL);
 166
 167     dep_list *head = NULL;
 168     dep_list *prev = NULL;
 169     DIR *dir = opendir (path);
 170     if (dir != NULL) {
 171         struct dirent *ent;
 172
 173         while ((ent = readdir (dir)) != NULL) {
 174             if (!strcmp (ent->d_name, ".") || !strcmp (ent->d_name, "..")) {
 175                 continue;
 176             }
 177
 178             if (head == NULL) {
 179                 head = calloc (1, sizeof (dep_list));
 180                 if (head == NULL) {
 181                     perror_msg ("Failed to allocate head during listing");
 182                     goto error;
 183                 }
 184             }
 185
 186             dep_list *iter = (prev == NULL) ? head : calloc (1, sizeof (dep_list));
 187             if (iter == NULL) {
 188                 perror_msg ("Failed to allocate a new element during listing");
 189                 goto error;
 190             }
 191
 192             iter->path = strdup (ent->d_name);
 193             if (iter->path == NULL) {
 194                 perror_msg ("Failed to copy a string during listing");
 195                 goto error;
 196             }
 197
 198             iter->inode = ent->d_ino;
 199             iter->next = NULL;
 200             if (prev) {
 201                 prev->next = iter;
 202             }
 203             prev = iter;
 204         }
 205
 206         closedir (dir);
 207     }
 208     return head;
 209
 210 error:
 211     if (dir != NULL) {
 212         closedir (dir);
 213     }
 214     dl_free (head);
 215     return NULL;
 216 }
 217
 218 /**
 219  * Perform a diff on lists.
 220  *
 221  * This function performs something like a set intersection. The same items
 222  * will be removed from the both lists. Items are comapred by a filename.
 223  *
 224  * @param[in,out] before A pointer to a pointer to a list. Will contain items
 225  *     which were not found in the 'after' list.
 226  * @param[in,out] after  A pointer to a pointer to a list. Will containt items
 227  *     which were not found in the 'before' list.
 228  **/
 229 void
 230 dl_diff (dep_list **before, dep_list **after)
 231 {
 232     assert (before != NULL);
 233     assert (after != NULL);
 234
 235     if (*before == NULL || *after == NULL) {
 236         return;
 237     }
 238
 239     dep_list *before_iter = *before;
 240     dep_list *before_prev = NULL;
 241
 242     while (before_iter != NULL) {
 243         dep_list *after_iter = *after;
 244         dep_list *after_prev = NULL;
 245
 246         int matched = 0;
 247         while (after_iter != NULL) {
 248             if (strcmp (before_iter->path, after_iter->path) == 0) {
 249                 matched = 1;
 250                 /* removing the entry from the both lists */
 251                 if (before_prev) {
 252                     before_prev->next = before_iter->next;
 253                 } else {
 254                     *before = before_iter->next;
 255                 }
 256
 257                 if (after_prev) {
 258                     after_prev->next = after_iter->next;
 259                 } else {
 260                     *after = after_iter->next;
 261                 }
 262                 free (after_iter);
 263                 break;
 264             }
 265             after_prev = after_iter;
 266             after_iter = after_iter->next;
 267         }
 268
 269         dep_list *oldptr = before_iter;
 270         before_iter = before_iter->next;
 271         if (matched == 0) {
 272             before_prev = oldptr;
 273         } else {
 274             free (oldptr);
 275         }
 276     }
 277 }
 278
 279
 280 /**
 281  * Traverses two lists. Compares items with a supplied expression
 282  * and performs the passed code on a match. Removes the matched entries
 283  * from the both lists.
 284  **/
 285 #define EXCLUDE_SIMILAR(removed_list, added_list, match_expr, matched_code) \
 286     assert (removed_list != NULL);                                      \
 287     assert (added_list != NULL);                                        \
 288                                                                         \
 289     dep_list *removed_list##_iter = *removed_list;                      \
 290     dep_list *removed_list##_prev = NULL;                               \
 291                                                                         \
 292     int productive = 0;                                                 \
 293                                                                         \
 294     while (removed_list##_iter != NULL) {                               \
 295         dep_list *added_list##_iter = *added_list;                      \
 296         dep_list *added_list##_prev = NULL;                             \
 297                                                                         \
 298         int matched = 0;                                                \
 299         while (added_list##_iter != NULL) {                             \
 300             if (match_expr) {                                           \
 301                 matched = 1;                                            \
 302                 ++productive;                                           \
 303                 matched_code;                                           \
 304                                                                         \
 305                 if (removed_list##_prev) {                              \
 306                     removed_list##_prev->next = removed_list##_iter->next; \
 307                 } else {                                                \
 308                     *removed_list = removed_list##_iter->next;          \
 309                 }                                                       \
 310                 if (added_list##_prev) {                                \
 311                     added_list##_prev->next = added_list##_iter->next;  \
 312                 } else {                                                \
 313                     *added_list = added_list##_iter->next;              \
 314                 }                                                       \
 315                 free (added_list##_iter);                               \
 316                 break;                                                  \
 317             }                                                           \
 318             added_list##_iter = added_list##_iter->next;                \
 319         }                                                               \
 320         dep_list *oldptr = removed_list##_iter;                         \
 321         removed_list##_iter = removed_list##_iter->next;                \
 322         if (matched == 0) {                                             \
 323             removed_list##_prev = oldptr;                               \
 324         } else {                                                        \
 325             free (oldptr);                                              \
 326         }                                                               \
 327     }                                                                   \
 328     return (productive > 0);
 329
 330
 331 #define cb_invoke(cbs, name, udata, ...) \
 332     do { \
 333         if (cbs->name) { \
 334             (cbs->name) (udata, ## __VA_ARGS__); \
 335         } \
 336     } while (0)
 337
 338 /**
 339  * Detect and notify about moves in the watched directory.
 340  *
 341  * A move is what happens when you rename a file in a directory, and
 342  * a new name is unique, i.e. you didnt overwrite any existing files
 343  * with this one.
 344  *
 345  * @param[in,out] removed  A list of the removed files in the directory.
 346  * @param[in,out] added    A list of the added files of the directory.
 347  * @param[in]     cbs      A pointer to #traverse_cbs, an user-defined set of
 348  *     traverse callbacks.
 349  * @param[in]     udata    A pointer to the user-defined data.
 350  * @return 0 if no files were renamed, >0 otherwise.
 351 **/
 352 static int
 353 dl_detect_moves (dep_list           **removed,
 354                  dep_list           **added,
 355                  const traverse_cbs  *cbs,
 356                  void                *udata)
 357 {
 358     assert (cbs != NULL);
 359
 360      EXCLUDE_SIMILAR
 361         (removed, added,
 362          (removed_iter->inode == added_iter->inode),
 363          {
 364              cb_invoke (cbs, moved, udata,
 365                         removed_iter->path, removed_iter->inode,
 366                         added_iter->path, added_iter->inode);
 367          });
 368 }
 369
 370 /**
 371  * Detect and notify about replacements in the watched directory.
 372  *
 373  * Consider you are watching a directory foo with the folloing files
 374  * insinde:
 375  *
 376  *    foo/bar
 377  *    foo/baz
 378  *
 379  * A replacement in a watched directory is what happens when you invoke
 380  *
 381  *    mv /foo/bar /foo/bar
 382  *
 383  * i.e. when you replace a file in a watched directory with another file
 384  * from the same directory.
 385  *
 386  * @param[in,out] removed  A list of the removed files in the directory.
 387  * @param[in,out] current  A list with the current contents of the directory.
 388  * @param[in]     cbs      A pointer to #traverse_cbs, an user-defined set of
 389  *     traverse callbacks.
 390  * @param[in]     udata    A pointer to the user-defined data.
 391  * @return 0 if no files were renamed, >0 otherwise.
 392  **/
 393 static int
 394 dl_detect_replacements (dep_list           **removed,
 395                         dep_list           **current,
 396                         const traverse_cbs  *cbs,
 397                         void                *udata)
 398 {
 399     assert (cbs != NULL);
 400
 401     EXCLUDE_SIMILAR
 402         (removed, current,
 403          (removed_iter->inode == current_iter->inode),
 404          {
 405             cb_invoke (cbs, replaced, udata,
 406                         removed_iter->path, removed_iter->inode,
 407                         current_iter->path, current_iter->inode);
 408          });
 409 }
 410
 411 /**
 412  * Detect and notify about overwrites in the watched directory.
 413  *
 414  * Consider you are watching a directory foo with a file inside:
 415  *
 416  *    foo/bar
 417  *
 418  * And you also have a directory tmp with a file 1:
 419  *
 420  *    tmp/1
 421  *
 422  * You do not watching directory tmp.
 423  *
 424  * An overwrite in a watched directory is what happens when you invoke
 425  *
 426  *    mv /tmp/1 /foo/bar
 427  *
 428  * i.e. when you overwrite a file in a watched directory with another file
 429  * from the another directory.
 430  *
 431  * @param[in,out] previous A list with the previous contents of the directory.
 432  * @param[in,out] current  A list with the current contents of the directory.
 433  * @param[in]     cbs      A pointer to #traverse_cbs, an user-defined set of
 434  *     traverse callbacks.
 435  * @param[in]     udata    A pointer to the user-defined data.
 436  * @return 0 if no files were renamed, >0 otherwise.
 437  **/
 438 static int
 439 dl_detect_overwrites (dep_list           **previous,
 440                       dep_list           **current,
 441                       const traverse_cbs  *cbs,
 442                       void                *udata)
 443 {
 444     assert (cbs != NULL);
 445
 446     EXCLUDE_SIMILAR
 447         (previous, current,
 448          (strcmp (previous_iter->path, current_iter->path) == 0
 449           && previous_iter->inode != current_iter->inode),
 450          {
 451              cb_invoke (cbs, overwritten, udata, current_iter->path, current_iter->inode);
 452          });
 453 }
 454
 455
 456 /**
 457  * Traverse a list and invoke a callback for each item.
 458  *
 459  * @param[in] list  A #dep_list.
 460  * @param[in] cb    A #single_entry_cb callback function.
 461  * @param[in] udata A pointer to the user-defined data.
 462  **/
 463 static void
 464 dl_emit_single_cb_on (dep_list        *list,
 465                       single_entry_cb  cb,
 466                       void            *udata)
 467 {
 468     while (cb && list != NULL) {
 469         (cb) (udata, list->path, list->inode);
 470         list = list->next;
 471     }
 472 }
 473
 474
 475 /**
 476  * Recognize all the changes in the directory, invoke the appropriate callbacks.
 477  *
 478  * This is the core function of directory diffing submodule.
 479  *
 480  * @param[in] before The previous contents of the directory.
 481  * @param[in] after  The current contents of the directory.
 482  * @param[in] cbs    A pointer to user callbacks (#traverse_callbacks).
 483  * @param[in] udata  A pointer to user data.
 484  **/
 485 void
 486 dl_calculate (dep_list           *before,
 487               dep_list           *after,
 488               const traverse_cbs *cbs,
 489               void               *udata)
 490 {
 491     assert (cbs != NULL);
 492
 493     int need_update = 0;
 494
 495     dep_list *was = dl_shallow_copy (before);
 496     dep_list *pre = dl_shallow_copy (before);
 497     dep_list *now = dl_shallow_copy (after);
 498     dep_list *lst = dl_shallow_copy (after);
 499
 500     dl_diff (&was, &now);
 501
 502     need_update += dl_detect_moves (&was, &now, cbs, udata);
 503     need_update += dl_detect_replacements (&was, &lst, cbs, udata);
 504     dl_detect_overwrites (&pre, &lst, cbs, udata);
 505
 506     if (need_update) {
 507         cb_invoke (cbs, names_updated, udata);
 508     }
 509
 510     dl_emit_single_cb_on (was, cbs->removed, udata);
 511     dl_emit_single_cb_on (now, cbs->added, udata);
 512
 513     cb_invoke (cbs, many_added, udata, now);
 514     cb_invoke (cbs, many_removed, udata, was);
 515
 516     dl_shallow_free (lst);
 517     dl_shallow_free (now);
 518     dl_shallow_free (pre);
 519     dl_shallow_free (was);
 520 }
 521