summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorYorhel <git@yorhel.nl>2012-08-26 14:41:25 +0200
committerYorhel <git@yorhel.nl>2012-08-26 15:29:55 +0200
commit0fd7dec7b0fbe50c8662e0496997b01842abf0db (patch)
tree0cfe11c67658abc6a4a1b857d95377eabf63fd8b /src
parent0b49021a6c676975d93c83e1e4228f96136c334c (diff)
Split calc.c into separate components (dir_(mem|scan|common).c)
The architecture is explained in dir.h. The reasons for these changes is two-fold: - calc.c was too complex, it simply did too many things. 399ccdeb is a nice example of that: Should have been an easy fix, but it introduced a segfault (fixed in 0b49021a), and added a small memory leak. - This architecture features a pluggable input/output system, which should make a file export/import feature relatively simple. The current commit does not feature any user interface, so there's no feedback yet when scanning a directory. I'll get to that in a bit. I've also not tested the new scanning code very well yet, so I might have introduced some bugs.
Diffstat (limited to 'src')
-rw-r--r--src/browser.c6
-rw-r--r--src/calc.c530
-rw-r--r--src/calc.h39
-rw-r--r--src/dir.h116
-rw-r--r--src/dir_common.c100
-rw-r--r--src/dir_mem.c209
-rw-r--r--src/dir_scan.c263
-rw-r--r--src/global.h12
-rw-r--r--src/main.c11
-rw-r--r--src/util.c29
-rw-r--r--src/util.h6
11 files changed, 730 insertions, 591 deletions
diff --git a/src/browser.c b/src/browser.c
index 4d9aba0..d13dac8 100644
--- a/src/browser.c
+++ b/src/browser.c
@@ -345,8 +345,10 @@ int browse_key(int ch) {
/* and other stuff */
case 'r':
- if(sel != NULL)
- calc_init(getpath(sel->parent), sel->parent);
+ if(sel != NULL) {
+ dir_mem_init(sel->parent);
+ dir_scan_init(getpath(sel->parent));
+ }
info_show = 0;
break;
case 'q':
diff --git a/src/calc.c b/src/calc.c
deleted file mode 100644
index 01b6971..0000000
--- a/src/calc.c
+++ /dev/null
@@ -1,530 +0,0 @@
-/* ncdu - NCurses Disk Usage
-
- Copyright (c) 2007-2012 Yoran Heling
-
- Permission is hereby granted, free of charge, to any person obtaining
- a copy of this software and associated documentation files (the
- "Software"), to deal in the Software without restriction, including
- without limitation the rights to use, copy, modify, merge, publish,
- distribute, sublicense, and/or sell copies of the Software, and to
- permit persons to whom the Software is furnished to do so, subject to
- the following conditions:
-
- The above copyright notice and this permission notice shall be included
- in all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
- IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
- CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
- TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
- SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-*/
-
-#include "global.h"
-
-#include <string.h>
-#include <stdlib.h>
-#include <errno.h>
-
-#include <unistd.h>
-#include <sys/types.h>
-#include <sys/stat.h>
-#include <dirent.h>
-
-#include "khash.h"
-
-/* set S_BLKSIZE if not defined already in sys/stat.h */
-#ifndef S_BLKSIZE
-# define S_BLKSIZE 512
-#endif
-
-
-/* external vars */
-char calc_smfs = 0;
-
-/* global vars for internal use */
-static char failed; /* 1 on fatal error */
-static char *curpath; /* last lstat()'ed item, used for excludes matching and display */
-static char *lasterr; /* last unreadable dir/item */
-static char errmsg[128]; /* error message, when failed=1 */
-static struct dir *root; /* root directory struct we're calculating */
-static struct dir *orig; /* original directory, when recalculating */
-static dev_t curdev; /* current device we're calculating on */
-static int anpos; /* position of the animation string */
-static int curpathl = 0, lasterrl = 0;
-
-
-// Table of struct dir items with more than one link (in order to detect hard links)
-#define links_dir_hash(d) (kh_int64_hash_func((khint64_t)d->dev) ^ kh_int64_hash_func((khint64_t)d->ino))
-#define links_dir_equal(a, b) ((a)->dev == (b)->dev && (a)->ino == (b)->ino)
-KHASH_INIT(hl, struct dir *, char, 0, links_dir_hash, links_dir_equal);
-static khash_t(hl) *links = NULL;
-
-
-
-/* adds name to curpath */
-static void calc_enterpath(char *name) {
- int n;
-
- n = strlen(curpath)+strlen(name)+2;
- if(n > curpathl) {
- curpathl = n;
- curpath = realloc(curpath, curpathl);
- }
- if(curpath[1])
- strcat(curpath, "/");
- strcat(curpath, name);
-}
-
-
-/* removes last component from curpath */
-static void calc_leavepath() {
- char *tmp;
- if((tmp = strrchr(curpath, '/')) == NULL)
- strcpy(curpath, "/");
- else if(tmp != curpath)
- tmp[0] = 0;
- else
- tmp[1] = 0;
-}
-
-
-/* recursively checks a dir structure for hard links and fills the lookup array */
-static void calc_hlink_init(struct dir *d) {
- struct dir *t;
-
- for(t=d->sub; t!=NULL; t=t->next)
- calc_hlink_init(t);
-
- if(!(d->flags & FF_HLNKC))
- return;
- int r;
- kh_put(hl, links, d, &r);
-}
-
-
-/* checks an individual file and updates the flags and cicrular linked list,
- * also updates the sizes of the parent dirs */
-static void calc_hlink_check(struct dir *d) {
- struct dir *t, *pt, *par;
- int i;
-
- d->flags |= FF_HLNKC;
-
- // add to links table
- khiter_t k = kh_put(hl, links, d, &i);
-
- /* found in the table? update hlnk */
- if(!i) {
- t = d->hlnk = kh_key(links, k);
- if(t->hlnk != NULL)
- for(t=t->hlnk; t->hlnk!=d->hlnk; t=t->hlnk)
- ;
- t->hlnk = d;
- }
-
- /* now update the sizes of the parent directories,
- * This works by only counting this file in the parent directories where this
- * file hasn't been counted yet, which can be determined from the hlnk list.
- * XXX: This may not be the most efficient algorithm to do this */
- for(i=1,par=d->parent; i&&par; par=par->parent) {
- if(d->hlnk)
- for(t=d->hlnk; i&&t!=d; t=t->hlnk)
- for(pt=t->parent; i&&pt; pt=pt->parent)
- if(pt==par)
- i=0;
- if(i) {
- par->size += d->size;
- par->asize += d->asize;
- }
- }
-}
-
-
-static int calc_item(struct dir *par, char *name) {
- struct dir *t, *d;
- struct stat fs;
-
- if(name[0] == '.' && (name[1] == '\0' || (name[1] == '.' && name[2] == '\0')))
- return 0;
-
- /* allocate dir and fix references */
- d = calloc(SDIRSIZE+strlen(name), 1);
- d->parent = par;
- d->next = par->sub;
- par->sub = d;
- if(d->next)
- d->next->prev = d;
- strcpy(d->name, name);
-
-#ifdef __CYGWIN__
- /* /proc/registry names may contain slashes */
- if(strchr(d->name, '/') || strchr(d->name, '\\')) {
- d->flags |= FF_ERR;
- return 0;
- }
-#endif
-
- /* lstat */
- if(lstat(name, &fs)) {
- d->flags |= FF_ERR;
- return 0;
- }
-
- /* check for excludes and same filesystem */
- if(exclude_match(curpath))
- d->flags |= FF_EXL;
-
- if(calc_smfs && curdev != fs.st_dev)
- d->flags |= FF_OTHFS;
-
- /* determine type of this item */
- if(S_ISREG(fs.st_mode))
- d->flags |= FF_FILE;
- else if(S_ISDIR(fs.st_mode))
- d->flags |= FF_DIR;
-
- /* update the items count of the parent dirs */
- if(!(d->flags & FF_EXL))
- for(t=d->parent; t!=NULL; t=t->parent)
- t->items++;
-
- /* count the size */
- if(!(d->flags & FF_EXL || d->flags & FF_OTHFS)) {
- d->size = fs.st_blocks * S_BLKSIZE;
- d->asize = fs.st_size;
- /* only update the sizes of the parents if it's not a hard link */
- if(S_ISDIR(fs.st_mode) || fs.st_nlink <= 1)
- for(t=d->parent; t!=NULL; t=t->parent) {
- t->size += d->size;
- t->asize += d->asize;
- }
- }
-
- /* Hard link checking (also takes care of updating the sizes of the parents) */
- d->ino = fs.st_ino;
- d->dev = fs.st_dev;
- if(!S_ISDIR(fs.st_mode) && fs.st_nlink > 1)
- calc_hlink_check(d);
-
- return 0;
-}
-
-
-/* recursively walk through the directory tree,
- assumes path resides in the cwd */
-static int calc_dir(struct dir *dest, char *name) {
- struct dir *t;
- DIR *dir;
- struct dirent *dr;
-
- if(input_handle(1))
- return 1;
-
- /* curpath */
- calc_enterpath(name);
-
- /* open & chdir into directory */
- if((dir = opendir(name)) == NULL || chdir(name) < 0) {
- if(lasterrl <= (int)strlen(curpath)) {
- lasterrl = strlen(curpath)+1;
- lasterr = realloc(lasterr, lasterrl);
- }
- strcpy(lasterr, curpath);
- dest->flags |= FF_ERR;
- t = dest;
- while((t = t->parent) != NULL)
- t->flags |= FF_SERR;
- calc_leavepath();
- if(dir != NULL)
- closedir(dir);
- return 0;
- }
-
- /* read directory */
- while((dr = readdir(dir)) != NULL) {
- calc_enterpath(dr->d_name);
- if(calc_item(dest, dr->d_name))
- dest->flags |= FF_ERR;
- if(input_handle(1)) {
- calc_leavepath();
- closedir(dir);
- return 1;
- }
- calc_leavepath();
- errno = 0;
- }
-
- if(errno) {
- if(dest->flags & FF_SERR)
- dest->flags -= FF_SERR;
- dest->flags |= FF_ERR;
- }
- closedir(dir);
-
- /* error occured while reading this dir, update parent dirs */
- for(t=dest->sub; t!=NULL; t=t->next)
- if(t->flags & FF_ERR || t->flags & FF_SERR)
- dest->flags |= FF_SERR;
- if(dest->flags & FF_ERR || dest->flags & FF_SERR) {
- for(t = dest; (t = t->parent) != NULL; )
- t->flags |= FF_SERR;
- }
-
- /* calculate subdirectories */
- for(t=dest->sub; t!=NULL; t=t->next)
- if(t->flags & FF_DIR && !(t->flags & FF_EXL || t->flags & FF_OTHFS))
- if(calc_dir(t, t->name)) {
- calc_leavepath();
- return 1;
- }
-
- /* chdir back */
- if(chdir("..") < 0) {
- failed = 1;
- strcpy(errmsg, "Couldn't chdir to previous directory");
- calc_leavepath();
- return 1;
- }
- calc_leavepath();
-
- return 0;
-}
-
-
-static void calc_draw_progress() {
- static char antext[15] = "Calculating...";
- char ani[15];
- int i;
- int width = wincols-5;
-
- nccreate(10, width, !orig ? "Calculating..." : "Recalculating...");
-
- ncprint(2, 2, "Total items: %-8d size: %s",
- root->items, formatsize(root->size));
- ncprint(3, 2, "Current dir: %s", cropstr(curpath, width-17));
- ncaddstr(8, width-17, "Press q to quit");
-
- /* show warning if we couldn't open a dir */
- if(lasterr[0] != '\0') {
- attron(A_BOLD);
- ncaddstr(5, 2, "Warning:");
- attroff(A_BOLD);
- ncprint(5, 11, "could not open %-32s", cropstr(lasterr, width-28));
- ncaddstr(6, 3, "some directory sizes may not be correct");
- }
-
- /* animation - but only if the screen refreshes more than or once every second */
- if(update_delay <= 1000) {
- if(++anpos == 28)
- anpos = 0;
- strcpy(ani, " ");
- if(anpos < 14)
- for(i=0; i<=anpos; i++)
- ani[i] = antext[i];
- else
- for(i=13; i>anpos-14; i--)
- ani[i] = antext[i];
- } else
- strcpy(ani, antext);
- ncaddstr(8, 3, ani);
-}
-
-
-static void calc_draw_error(char *cur, char *msg) {
- int width = wincols-5;
- nccreate(7, width, "Error!");
-
- attron(A_BOLD);
- ncaddstr(2, 2, "Error:");
- attroff(A_BOLD);
-
- ncprint(2, 9, "could not open %s", cropstr(cur, width-26));
- ncprint(3, 4, "%s", cropstr(msg, width-8));
- ncaddstr(5, width-30, "press any key to continue...");
-}
-
-
-void calc_draw() {
- browse_draw();
- if(failed)
- calc_draw_error(curpath, errmsg);
- else
- calc_draw_progress();
-}
-
-
-int calc_key(int ch) {
- if(failed)
- return 1;
- if(ch == 'q')
- return 1;
- return 0;
-}
-
-
-int calc_process() {
- char *path = NULL, *name = NULL;
- struct stat fs;
- struct dir *t;
- int n;
-
- /* create initial links set */
- links = kh_init(hl);
- if(orig) {
- for(t=orig; t->parent!=NULL; t=t->parent)
- ;
- calc_hlink_init(t);
- }
-
- /* check root directory */
- if((path = path_real(curpath)) == NULL) {
- failed = 1;
- strcpy(errmsg, "Directory not found");
- goto calc_fail;
- }
-
- /* split into path and last component */
- name = strrchr(path, '/');
- if(name == path) {
- if(!path[1])
- name = ".";
- else {
- name = malloc(strlen(path));
- strcpy(name, path+1);
- path[1] = 0;
- }
- } else
- *(name++) = 0;
-
- /* we need to chdir so we can provide relative paths for lstat() and opendir(),
- * this to prevent creating path names longer than PATH_MAX */
- if(path_chdir(path) < 0) {
- failed = 1;
- strcpy(errmsg, "Couldn't chdir into directory");
- free(path);
- goto calc_fail;
- }
- /* would be strange for this to fail, but oh well... */
- if(lstat(name, &fs) != 0 || !S_ISDIR(fs.st_mode)) {
- failed = 1;
- strcpy(errmsg, "Couldn't stat directory");
- free(path);
- goto calc_fail;
- }
-
- /* initialize parent dir */
- n = orig ? strlen(orig->name) : strlen(path)+strlen(name)+1;
- t = (struct dir *) calloc(1, SDIRSIZE+n);
- t->size = fs.st_blocks * S_BLKSIZE;
- t->asize = fs.st_size;
- t->flags |= FF_DIR;
- if(orig) {
- strcpy(t->name, orig->name);
- t->parent = orig->parent;
- } else {
- t->name[0] = 0;
- if(strcmp(path, "/"))
- strcpy(t->name, path);
- if(strcmp(name, ".")) {
- strcat(t->name, "/");
- strcat(t->name, name);
- }
- }
- root = t;
- curdev = fs.st_dev;
-
- /* make sure to count this directory entry in its parents at this point */
- if(orig)
- for(t=root->parent; t!=NULL; t=t->parent) {
- t->size += root->size;
- t->asize += root->asize;
- t->items += 1;
- }
-
- /* update curpath */
- if(strcmp(name, ".")) {
- if(curpathl <= (int)strlen(path)) {
- curpathl = strlen(path)+1;
- curpath = realloc(curpath, curpathl);
- }
- strcpy(curpath, path);
- } else
- curpath[0] = 0;
-
- /* calculate */
- n = calc_dir(root, name);
-
- if(links) {
- kh_destroy(hl, links);
- links = NULL;
- }
-
- /* success */
- if(!n && !failed) {
- if(root->sub == NULL) {
- freedir(root);
- failed = 1;
- calc_enterpath(name);
- strcpy(errmsg, "Directory empty.");
- goto calc_fail;
- }
-
- /* update references and free original item */
- if(orig) {
- root->next = orig->next;
- root->prev = orig->prev;
- if(root->parent && root->parent->sub == orig)
- root->parent->sub = root;
- if(root->prev)
- root->prev->next = root;
- if(root->next)
- root->next->prev = root;
- orig->next = orig->prev = NULL;
- freedir(orig);
- }
- browse_init(root->sub);
- dirlist_top(-3);
- return 0;
- }
-
- /* something went wrong... */
- freedir(root);
-calc_fail:
- if(name && path && !path[1] && strcmp(name, "."))
- free(name);
- free(path);
-
- while(failed && !input_handle(0))
- ;
- if(orig == NULL)
- return 1;
- else {
- browse_init(orig);
- return 0;
- }
-}
-
-
-void calc_init(char *dir, struct dir *org) {
- failed = anpos = 0;
- orig = org;
- if(curpathl == 0) {
- curpathl = strlen(dir)+1;
- curpath = malloc(curpathl);
- } else if(curpathl <= (int)strlen(dir)) {
- curpathl = strlen(dir)+1;
- curpath = realloc(curpath, curpathl);
- }
- strcpy(curpath, dir);
- if(lasterrl == 0) {
- lasterrl = 1;
- lasterr = malloc(lasterrl);
- }
- lasterr[0] = 0;
- pstate = ST_CALC;
-}
-
diff --git a/src/calc.h b/src/calc.h
deleted file mode 100644
index 16bbe57..0000000
--- a/src/calc.h
+++ /dev/null
@@ -1,39 +0,0 @@
-/* ncdu - NCurses Disk Usage
-
- Copyright (c) 2007-2012 Yoran Heling
-
- Permission is hereby granted, free of charge, to any person obtaining
- a copy of this software and associated documentation files (the
- "Software"), to deal in the Software without restriction, including
- without limitation the rights to use, copy, modify, merge, publish,
- distribute, sublicense, and/or sell copies of the Software, and to
- permit persons to whom the Software is furnished to do so, subject to
- the following conditions:
-
- The above copyright notice and this permission notice shall be included
- in all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
- IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
- CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
- TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
- SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-*/
-
-#ifndef _calc_h
-#define _calc_h
-
-#include "global.h"
-
-extern char calc_smfs; /* stay on the same filesystem */
-
-int calc_process(void);
-int calc_key(int);
-void calc_draw(void);
-void calc_init(char *, struct dir *);
-
-
-#endif
diff --git a/src/dir.h b/src/dir.h
new file mode 100644
index 0000000..bd50579
--- /dev/null
+++ b/src/dir.h
@@ -0,0 +1,116 @@
+/* ncdu - NCurses Disk Usage
+
+ Copyright (c) 2007-2012 Yoran Heling
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be included
+ in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+*/
+
+#ifndef _dir_h
+#define _dir_h
+
+/* The dir_* functions and files implement the SCAN state and are organized as
+ * follows:
+ *
+ * Input:
+ * Responsible for getting a directory structure into ncdu. Will call the
+ * Output functions for data and the UI functions for feedback. Currently
+ * there is only one input implementation: dir_scan.c
+ * Output:
+ * Called by the Input handling code when there's some new file/directory
+ * information. The Output code is responsible for doing something with it
+ * and determines what action should follow after the Input is done.
+ * Currently there is only one output implementation: dir_mem.c.
+ * Common:
+ * Utility functions and UI code for use by the Input handling code to draw
+ * progress/error information on the screen, handle any user input and misc.
+ * stuff.
+ */
+
+
+/* "Interface" that Input code should call and Output code should implement. */
+struct dir_output {
+ /* Called when there is new file/dir info. Call stack for an example
+ * directory structure:
+ * / item('/')
+ * /subdir item('subdir')
+ * /subdir/f item('f')
+ * .. item(NULL)
+ * /abc item('abc')
+ * .. item(NULL)
+ * Every opened dir is followed by a call to NULL. There is only one top-level
+ * dir item. The name of the top-level dir item is the absolute path to the
+ * scanned directory.
+ *
+ * The *item struct has the following fields set when item() is called:
+ * size, asize, ino, dev, flags (only DIR,FILE,ERR,OTHFS,EXL,HLNKC) and name.
+ * All other fields/flags should be initialzed to NULL or 0.
+ * *item may be overwritten or freed in subsequent calls, so this function
+ * should make a copy if necessary.
+ */
+ void (*item)(struct dir *);
+
+ /* Finalizes the output to go to the next program state or exit ncdu. Called
+ * after item(NULL) has been called for the root item or before any item()
+ * has been called at all.
+ * Argument indicates success (0) or failure (1).
+ * Failure happens when the root directory couldn't be opened, chdir, lstat,
+ * read, when it is empty, or when the user aborted the operation.
+ * Return value should be 0 to continue running ncdu, 1 to exit.
+ */
+ int (*final)(int);
+};
+
+
+/* Initializes the SCAN state and dir_output for immediate browsing.
+ * On success:
+ * If a dir item is given, overwrites it with the new dir struct.
+ * Then calls browse_init(new_dir_struct->sub).
+ * On failure:
+ * If a dir item is given, will just call browse_init(orig).
+ * Otherwise, will exit ncdu.
+ */
+void dir_mem_init(struct dir *);
+
+
+/* Scanning a live directory */
+extern int dir_scan_smfs;
+void dir_scan_init(const char *path);
+int dir_scan_process();
+
+
+/* The currently configured output functions. */
+extern struct dir_output dir_output;
+
+/* Current path that we're working with. These are defined in dir_common.c. */
+extern char *dir_curpath;
+void dir_curpath_set(const char *);
+void dir_curpath_enter(const char *);
+void dir_curpath_leave();
+
+/* Sets the path where the last error occured, or reset on NULL. */
+void dir_setlasterr(const char *);
+
+/* Return an empty struct dir with the given name, for use with
+ * dir_output.item(). Returned memory may be freed/overwritten on a subsequent
+ * call. */
+struct dir *dir_createstruct(const char *);
+
+#endif
diff --git a/src/dir_common.c b/src/dir_common.c
new file mode 100644
index 0000000..dec814b
--- /dev/null
+++ b/src/dir_common.c
@@ -0,0 +1,100 @@
+/* ncdu - NCurses Disk Usage
+
+ Copyright (c) 2007-2012 Yoran Heling
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be included
+ in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+*/
+
+#include "global.h"
+
+#include <string.h>
+#include <stdlib.h>
+
+
+char *dir_curpath; /* Full path of the last seen item. */
+struct dir_output dir_output;
+static char *lasterr; /* Path where the last error occured. */
+static int curpathl; /* Allocated length of dir_curpath */
+static int lasterrl; /* ^ of lasterr */
+
+
+static void curpath_resize(int s) {
+ if(curpathl < s) {
+ curpathl = s < 128 ? 128 : s < curpathl*2 ? curpathl*2 : s;
+ dir_curpath = realloc(dir_curpath, curpathl);
+ }
+}
+
+
+void dir_curpath_set(const char *path) {
+ curpath_resize(strlen(path)+1);
+ strcpy(dir_curpath, path);
+}
+
+
+void dir_curpath_enter(const char *name) {
+ curpath_resize(strlen(dir_curpath)+strlen(name)+2);
+ if(dir_curpath[1])
+ strcat(dir_curpath, "/");
+ strcat(dir_curpath, name);
+}
+
+
+/* removes last component from dir_curpath */
+void dir_curpath_leave() {
+ char *tmp;
+ if((tmp = strrchr(dir_curpath, '/')) == NULL)
+ strcpy(dir_curpath, "/");
+ else if(tmp != dir_curpath)
+ tmp[0] = 0;
+ else
+ tmp[1] = 0;
+}
+
+
+void dir_setlasterr(const char *path) {
+ if(!path) {
+ free(lasterr);
+ lasterr = NULL;
+ lasterrl = 0;
+ return;
+ }
+ int req = strlen(path)+1;
+ if(lasterrl < req) {
+ lasterrl = req;
+ lasterr = realloc(lasterr, lasterrl);
+ }
+ strcpy(lasterr, dir_curpath);
+}
+
+
+struct dir *dir_createstruct(const char *name) {
+ static struct dir *d = NULL;
+ static size_t len = 0;
+ size_t req = SDIRSIZE+strlen(name);
+ if(len < req) {
+ len = req < SDIRSIZE+256 ? SDIRSIZE+256 : req < len*2 ? len*2 : req;
+ d = realloc(d, len);
+ }
+ memset(d, 0, SDIRSIZE);
+ strcpy(d->name, name);
+ return d;
+}
diff --git a/src/dir_mem.c b/src/dir_mem.c
new file mode 100644
index 0000000..4549b61
--- /dev/null
+++ b/src/dir_mem.c
@@ -0,0 +1,209 @@
+/* ncdu - NCurses Disk Usage
+
+ Copyright (c) 2007-2012 Yoran Heling
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be included
+ in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+*/
+
+#include "global.h"
+#include "khash.h"
+
+#include <string.h>
+#include <stdlib.h>
+
+
+static struct dir *root; /* root directory struct we're scanning */
+static struct dir *curdir; /* directory item that we're currently adding items to */
+static struct dir *orig; /* original directory, when refreshing an already scanned dir */
+
+/* Table of struct dir items with more than one link (in order to detect hard links) */
+#define hlink_hash(d) (kh_int64_hash_func((khint64_t)d->dev) ^ kh_int64_hash_func((khint64_t)d->ino))
+#define hlink_equal(a, b) ((a)->dev == (b)->dev && (a)->ino == (b)->ino)
+KHASH_INIT(hl, struct dir *, char, 0, hlink_hash, hlink_equal);
+static khash_t(hl) *links = NULL;
+
+
+/* recursively checks a dir structure for hard links and fills the lookup array */
+static void hlink_init(struct dir *d) {
+ struct dir *t;
+
+ for(t=d->sub; t!=NULL; t=t->next)
+ hlink_init(t);
+
+ if(!(d->flags & FF_HLNKC))
+ return;
+ int r;
+ kh_put(hl, links, d, &r);
+}
+
+
+/* checks an individual file for hard links and updates its cicrular linked
+ * list, also updates the sizes of the parent dirs */
+static void hlink_check(struct dir *d) {
+ struct dir *t, *pt, *par;
+ int i;
+
+ /* add to links table */
+ khiter_t k = kh_put(hl, links, d, &i);
+
+ /* found in the table? update hlnk */
+ if(!i) {
+ t = d->hlnk = kh_key(links, k);
+ if(t->hlnk != NULL)
+ for(t=t->hlnk; t->hlnk!=d->hlnk; t=t->hlnk)
+ ;
+ t->hlnk = d;
+ }
+
+ /* now update the sizes of the parent directories,
+ * This works by only counting this file in the parent directories where this
+ * file hasn't been counted yet, which can be determined from the hlnk list.
+ * XXX: This may not be the most efficient algorithm to do this */
+ for(i=1,par=d->parent; i&&par; par=par->parent) {
+ if(d->hlnk)
+ for(t=d->hlnk; i&&t!=d; t=t->hlnk)
+ for(pt=t->parent; i&&pt; pt=pt->parent)
+ if(pt==par)
+ i=0;
+ if(i) {
+ par->size += d->size;
+ par->asize += d->asize;
+ }
+ }
+}
+
+
+/* Make a copy of *item so that we'll keep it in memory. In the special case
+ * of !root && orig, we need to copy over the name of *orig instead of *item.
+ */
+static struct dir *item_copy(struct dir *item) {
+ struct dir *t;
+
+ if(!root && orig) {
+ t = malloc(SDIRSIZE+strlen(orig->name));
+ memcpy(t, item, SDIRSIZE);
+ strcpy(t->name, orig->name);
+ } else {
+ t = malloc(SDIRSIZE+strlen(item->name));
+ memcpy(t, item, SDIRSIZE+strlen(item->name));
+ }
+ return t;
+}
+
+
+/* Add item to the correct place in the memory structure */
+static void item_add(struct dir *item) {
+ if(!root) {
+ root = item;
+ /* Make sure that the *root appears to be part of the same dir structure as
+ * *orig, otherwise the directory size calculation will be incorrect in the
+ * case of hard links. */
+ if(orig)
+ root->parent = orig->parent;
+ } else {
+ item->parent = curdir;
+ item->next = curdir->sub;
+ if(item->next)
+ item->next->prev = item;
+ curdir->sub = item;
+ }
+}
+
+
+static void item(struct dir *item) {
+ struct dir *t;
+
+ /* Go back to parent dir */
+ if(!item) {
+ curdir = curdir->parent;
+ return;
+ }
+
+ item = item_copy(item);
+ item_add(item);
+
+ /* Ensure that any next items will go to this directory */
+ if(item->flags & FF_DIR)
+ curdir = item;
+
+ /* Update stats of parents. Don't update the size/asize fields if this is a
+ * possible hard link, because hlnk_check() will take care of it in that
+ * case. */
+ if(item->flags & FF_HLNKC) {
+ addparentstats(item->parent, 0, 0, 1);
+ hlink_check(item);
+ } else
+ addparentstats(item->parent, item->size, item->asize, 1);
+
+ /* propagate ERR and SERR back up to the root */
+ if(item->flags & FF_SERR || item->flags & FF_ERR)
+ for(t=item->parent; t; t=t->parent)
+ t->flags |= FF_SERR;
+}
+
+
+static int final(int fail) {
+ kh_destroy(hl, links);
+ links = NULL;
+
+ if(fail) {
+ freedir(root);
+ if(orig) {
+ browse_init(orig);
+ return 0;
+ } else
+ return 1;
+ }
+
+ /* success, update references and free original item */
+ if(orig) {
+ root->next = orig->next;
+ root->prev = orig->prev;
+ if(root->parent && root->parent->sub == orig)
+ root->parent->sub = root;
+ if(root->prev)
+ root->prev->next = root;
+ if(root->next)
+ root->next->prev = root;
+ orig->next = orig->prev = NULL;
+ freedir(orig);
+ }
+
+ browse_init(root->sub);
+ dirlist_top(-3);
+ return 0;
+}
+
+
+void dir_mem_init(struct dir *_orig) {
+ orig = _orig;
+ root = curdir = NULL;
+ pstate = ST_CALC;
+
+ dir_output.item = item;
+ dir_output.final = final;
+
+ /* Init hash table for hard link detection */
+ links = kh_init(hl);
+ if(orig)
+ hlink_init(getroot(orig));
+}
+
diff --git a/src/dir_scan.c b/src/dir_scan.c
new file mode 100644
index 0000000..3ab172f
--- /dev/null
+++ b/src/dir_scan.c
@@ -0,0 +1,263 @@
+/* ncdu - NCurses Disk Usage
+
+ Copyright (c) 2007-2012 Yoran Heling
+
+ Permission is hereby granted, free of charge, to any person obtaining
+ a copy of this software and associated documentation files (the
+ "Software"), to deal in the Software without restriction, including
+ without limitation the rights to use, copy, modify, merge, publish,
+ distribute, sublicense, and/or sell copies of the Software, and to
+ permit persons to whom the Software is furnished to do so, subject to
+ the following conditions:
+
+ The above copyright notice and this permission notice shall be included
+ in all copies or substantial portions of the Software.
+
+ THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+ IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+ CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+ TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+ SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+
+*/
+
+#include "global.h"
+
+#include <string.h>
+#include <stdlib.h>
+#include <errno.h>
+
+#include <unistd.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <dirent.h>
+
+
+/* set S_BLKSIZE if not defined already in sys/stat.h */
+#ifndef S_BLKSIZE
+# define S_BLKSIZE 512
+#endif
+
+
+int dir_scan_smfs; /* Stay on the same filesystem */
+
+static dev_t curdev; /* current device we're scanning on */
+
+
+/* Populates the struct dir item with information from the stat struct. Sets
+ * everything necessary for output_dir.item() except FF_ERR and FF_EXL. */
+static void stat_to_dir(struct dir *d, struct stat *fs) {
+ d->ino = fs->st_ino;
+ d->dev = fs->st_dev;
+
+ if(S_ISREG(fs->st_mode))
+ d->flags |= FF_FILE;
+ else if(S_ISDIR(fs->st_mode))
+ d->flags |= FF_DIR;
+
+ if(!S_ISDIR(fs->st_mode) && fs->st_nlink > 1)
+ d->flags |= FF_HLNKC;
+
+ if(dir_scan_smfs && curdev != fs->st_dev)
+ d->flags |= FF_OTHFS;
+
+ if(!(d->flags & (FF_OTHFS|FF_EXL))) {
+ d->size = fs->st_blocks * S_BLKSIZE;
+ d->asize = fs->st_size;
+ }
+}
+
+
+/* Reads all filenames in the currently chdir'ed directory and stores it as a
+ * nul-separated list of filenames. The list ends with an empty filename (i.e.
+ * two nuls). . and .. are not included. Returned memory should be freed. *err
+ * is set to 1 if some error occured. Returns NULL if that error was fatal.
+ * The reason for reading everything in memory first and then walking through
+ * the list is to avoid eating too many file descriptors in a deeply recursive
+ * directory. */
+static char *dir_read(int *err) {
+ DIR *dir;
+ struct dirent *item;
+ char *buf = NULL;
+ int buflen = 512;
+ int off = 0;
+
+ if((dir = opendir(".")) == NULL) {
+ *err = 1;
+ return NULL;
+ }
+
+ buf = malloc(buflen);
+ errno = 0;
+
+ while((item = readdir(dir)) != NULL) {
+ if(item->d_name[0] == '.' && (item->d_name[1] == 0 || (item->d_name[1] == '.' && item->d_name[2] == 0)))
+ continue;
+ int req = off+3+strlen(item->d_name);
+ if(req > buflen) {
+ buflen = req < buflen*2 ? buflen*2 : req;
+ buf = realloc(buf, buflen);
+ }
+ strcpy(buf+off, item->d_name);
+ off += strlen(item->d_name)+1;
+ }
+ if(errno)
+ *err = 1;
+ if(closedir(dir) < 0)
+ *err = 1;
+
+ buf[off] = 0;
+ buf[off+1] = 0;
+ return buf;
+}
+
+
+static int dir_walk(char *);
+
+
+/* Tries to recurse into the given directory item */
+static int dir_scan_recurse(struct dir *d) {
+ int fail = 0;
+ char *dir;
+
+ if(chdir(d->name)) {
+ dir_setlasterr(dir_curpath);
+ d->flags |= FF_ERR;
+ dir_output.item(d);
+ dir_output.item(NULL);
+ return 0;
+ }
+
+ if((dir = dir_read(&fail)) == NULL) {
+ dir_setlasterr(dir_curpath);
+ d->flags |= FF_ERR;
+ dir_output.item(d);
+ dir_output.item(NULL);
+ return chdir("..") ? 1 : 0; /* TODO: Error reporting */
+ }
+
+ /* readdir() failed halfway, not fatal. */
+ if(fail)
+ d->flags |= FF_ERR;
+
+ dir_output.item(d);
+ fail = dir_walk(dir);
+ dir_output.item(NULL);
+
+ /* Not being able to chdir back is fatal */
+ if(!fail && chdir(".."))
+ return 1; /* TODO: Error reporting */
+
+ return fail;
+}
+
+
+/* Scans and adds a single item. Recurses into dir_walk() again if this is a
+ * directory. Assumes we're chdir'ed in the directory in which this item
+ * resides, i.e. d->name is a valid relative path to the item. */
+static int dir_scan_item(struct dir *d) {
+ struct stat st;
+ int fail = 0;
+
+#ifdef __CYGWIN__
+ /* /proc/registry names may contain slashes */
+ if(strchr(d->name, '/') || strchr(d->name, '\\')) {
+ d->flags |= FF_ERR;
+ dir_setlasterr(dir_curpath);
+ }
+#endif
+
+ if(exclude_match(dir_curpath))
+ d->flags |= FF_EXL;
+
+ if(!(d->flags & (FF_ERR|FF_EXL)) && lstat(d->name, &st)) {
+ d->flags |= FF_ERR;
+ dir_setlasterr(dir_curpath);
+ }
+
+ if(!(d->flags & (FF_ERR|FF_EXL)))
+ stat_to_dir(d, &st);
+
+ /* Recurse into the dir or output the item */
+ if(d->flags & FF_DIR && !(d->flags & (FF_ERR|FF_EXL|FF_OTHFS)))
+ dir_scan_recurse(d);
+ else if(d->flags & FF_DIR) {
+ dir_output.item(d);
+ dir_output.item(NULL);
+ } else
+ dir_output.item(d);
+
+ return fail; /* TODO: UI */
+}
+
+
+/* Walks through the directory that we're currently chdir'ed to. *dir contains
+ * the filenames as returned by dir_read(), and will be freed automatically by
+ * this function. */
+static int dir_walk(char *dir) {
+ struct dir *d;
+ int fail = 0;
+ char *cur;
+
+ fail = 0;
+ for(cur=dir; !fail&&cur&&*cur; cur+=strlen(cur)+1) {
+ dir_curpath_enter(cur);
+ d = dir_createstruct(cur);
+ fail = dir_scan_item(d);
+ dir_curpath_leave();
+ }
+
+ free(dir);
+ return fail;
+}
+
+
+/* Returns 0 to continue running ncdu, 1 to quit. */
+int dir_scan_process() {
+ char *path;
+ char *dir;
+ int fail = 0;
+ struct stat fs;
+ struct dir *d;
+
+ if((path = path_real(dir_curpath)) == NULL) {
+ /* TODO */
+ }
+ dir_curpath_set(path);
+ free(path);
+
+ if(path_chdir(dir_curpath) < 0) {
+ /* TODO */
+ }
+
+ /* Can these even fail after a chdir? */
+ if(lstat(".", &fs) != 0 || !S_ISDIR(fs.st_mode)) {
+ /* TODO */
+ }
+
+ dir = dir_read(&fail);
+ if(!dir) {
+ /* TODO */
+ }
+
+ curdev = fs.st_dev;
+ d = dir_createstruct(dir_curpath);
+ if(fail)
+ d->flags |= FF_ERR;
+ stat_to_dir(d, &fs);
+
+ dir_output.item(d);
+ fail = dir_walk(dir);
+ dir_output.item(NULL);
+
+ return dir_output.final(fail);
+}
+
+
+void dir_scan_init(const char *path) {
+ dir_curpath_set(path);
+ dir_setlasterr(NULL);
+ pstate = ST_CALC;
+}
diff --git a/src/global.h b/src/global.h
index d6903e7..c34f44c 100644
--- a/src/global.h
+++ b/src/global.h
@@ -55,7 +55,7 @@ struct dir {
struct dir *parent, *next, *prev, *sub, *hlnk;
off_t size, asize;
ino_t ino;
- unsigned long items;
+ long items;
dev_t dev;
unsigned char flags;
char name[3]; /* must be large enough to hold ".." */
@@ -81,13 +81,13 @@ int input_handle(int);
/* import all other global functions and variables */
-#include "exclude.h"
-#include "util.h"
-#include "calc.h"
-#include "delete.h"
#include "browser.h"
+#include "delete.h"
+#include "dir.h"
+#include "dirlist.h"
+#include "exclude.h"
#include "help.h"
#include "path.h"
-#include "dirlist.h"
+#include "util.h"
#endif
diff --git a/src/main.c b/src/main.c
index 2b103ae..81283f3 100644
--- a/src/main.c
+++ b/src/main.c
@@ -44,7 +44,7 @@ static long lastupdate = 999;
static void screen_draw() {
switch(pstate) {
- case ST_CALC: calc_draw(); break;
+ case ST_CALC: /* TODO */ break;
case ST_BROWSE: browse_draw(); break;
case ST_HELP: help_draw(); break;
case ST_DEL: delete_draw(); break;
@@ -82,7 +82,7 @@ int input_handle(int wait) {
continue;
}
switch(pstate) {
- case ST_CALC: return calc_key(ch);
+ case ST_CALC: return 0; /* TODO */
case ST_BROWSE: return browse_key(ch);
case ST_HELP: return help_key(ch);
case ST_DEL: return delete_key(ch);
@@ -120,7 +120,7 @@ static char *argv_parse(int argc, char **argv) {
len = strlen(argv[i]);
for(j=1; j<len; j++)
switch(argv[i][j]) {
- case 'x': calc_smfs = 1; break;
+ case 'x': dir_scan_smfs = 1; break;
case 'r': read_only = 1; break;
case 'q': update_delay = 2000; break;
case '?':
@@ -157,7 +157,8 @@ int main(int argc, char **argv) {
if((dir = argv_parse(argc, argv)) == NULL)
dir = ".";
- calc_init(dir, NULL);
+ dir_mem_init(NULL);
+ dir_scan_init(dir);
initscr();
cbreak();
@@ -168,7 +169,7 @@ int main(int argc, char **argv) {
min_rows = min_cols = 0;
while(1) {
- if(pstate == ST_CALC && calc_process())
+ if(pstate == ST_CALC && dir_scan_process())
break;
else if(pstate == ST_DEL)
delete_process();
diff --git a/src/util.c b/src/util.c
index 8aca86a..e4f1e22 100644
--- a/src/util.c
+++ b/src/util.c
@@ -175,7 +175,7 @@ static void freedir_hlnk(struct dir *d) {
* This works the same as with adding: only the parents in which THIS is the
* only occurence of the hard link will be modified, if the same file still
* exists within the parent it shouldn't get removed from the count.
- * XXX: Same note as for calc.c / calc_hlnk_check():
+ * XXX: Same note as for dir_mem.c / hlink_check():
* this is probably not the most efficient algorithm */
for(i=1,par=d->parent; i&&par; par=par->parent) {
if(d->hlnk)
@@ -212,7 +212,8 @@ static void freedir_rec(struct dir *dr) {
void freedir(struct dir *dr) {
- struct dir *tmp;
+ if(!dr)
+ return;
/* free dr->sub recursively */
if(dr->sub)
@@ -230,13 +231,7 @@ void freedir(struct dir *dr) {
/* update sizes of parent directories if this isn't a hard link.
* If this is a hard link, freedir_hlnk() would have done so already */
- for(tmp=dr->parent; tmp; tmp=tmp->parent) {
- if(!(dr->flags & FF_HLNKC)) {
- tmp->size -= dr->size;
- tmp->asize -= dr->asize;
- }
- tmp->items -= dr->items+1;
- }
+ addparentstats(dr->parent, dr->flags & FF_HLNKC ? 0 : -dr->size, dr->flags & FF_HLNKC ? 0 : -dr->asize, -(dr->items+1));
free(dr);
}
@@ -280,3 +275,19 @@ char *getpath(struct dir *cur) {
return dat;
}
+
+struct dir *getroot(struct dir *d) {
+ while(d && d->parent)
+ d = d->parent;
+ return d;
+}
+
+
+void addparentstats(struct dir *d, off_t size, off_t asize, long items) {
+ while(d) {
+ d->size += size;
+ d->asize += asize;
+ d->items += items;
+ d = d->parent;
+ }
+}
diff --git a/src/util.h b/src/util.h
index 26eb406..a0d7641 100644
--- a/src/util.h
+++ b/src/util.h
@@ -78,5 +78,11 @@ void freedir(struct dir *);
returned pointer will be overwritten with a subsequent call */
char *getpath(struct dir *);
+/* returns the root element of the given dir struct */
+struct dir *getroot(struct dir *);
+
+/* Adds a value to the size, asize and items fields of *d and its parents */
+void addparentstats(struct dir *, off_t, off_t, long);
+
#endif