1 /* ncdu - NCurses Disk Usage
2
3 Copyright (c) 2007-2021 Yoran Heling
4
5 Permission is hereby granted, free of charge, to any person obtaining
6 a copy of this software and associated documentation files (the
7 "Software"), to deal in the Software without restriction, including
8 without limitation the rights to use, copy, modify, merge, publish,
9 distribute, sublicense, and/or sell copies of the Software, and to
10 permit persons to whom the Software is furnished to do so, subject to
11 the following conditions:
12
13 The above copyright notice and this permission notice shall be included
14 in all copies or substantial portions of the Software.
15
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
17 EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
18 MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
19 IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
20 CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
21 TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
22 SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
23
24 */
25
26 #include "global.h"
27
28 #include <string.h>
29 #include <stdlib.h>
30
31
32 /* public variables */
33 struct dir *dirlist_parent = NULL,
34 *dirlist_par = NULL;
35 int64_t dirlist_maxs = 0,
36 dirlist_maxa = 0;
37
38 int dirlist_sort_desc = 1,
39 dirlist_sort_col = DL_COL_SIZE,
40 dirlist_sort_df = 0,
41 dirlist_hidden = 0;
42
43 /* private state vars */
44 static struct dir *parent_alloc, *head, *head_real, *selected, *top = NULL;
45
46
47
48 #define ISHIDDEN(d) (dirlist_hidden && (d) != dirlist_parent && (\
49 (d)->flags & FF_EXL || (d)->name[0] == '.' || (d)->name[strlen((d)->name)-1] == '~'\
50 ))
51
52
cmp_mtime(struct dir * x,struct dir * y)53 static inline int cmp_mtime(struct dir *x, struct dir*y) {
54 int64_t x_mtime = 0, y_mtime = 0;
55 if (x->flags & FF_EXT)
56 x_mtime = dir_ext_ptr(x)->mtime;
57 if (y->flags & FF_EXT)
58 y_mtime = dir_ext_ptr(y)->mtime;
59 return (x_mtime > y_mtime ? 1 : (x_mtime == y_mtime ? 0 : -1));
60 }
61
dirlist_cmp(struct dir * x,struct dir * y)62 static int dirlist_cmp(struct dir *x, struct dir *y) {
63 int r;
64
65 /* dirs are always before files when that option is set */
66 if(dirlist_sort_df) {
67 if(y->flags & FF_DIR && !(x->flags & FF_DIR))
68 return 1;
69 else if(!(y->flags & FF_DIR) && x->flags & FF_DIR)
70 return -1;
71 }
72
73 /* sort columns:
74 * 1 -> 2 -> 3 -> 4
75 * NAME: name -> size -> asize -> items
76 * SIZE: size -> asize -> name -> items
77 * ASIZE: asize -> size -> name -> items
78 * ITEMS: items -> size -> asize -> name
79 *
80 * Note that the method used below is supposed to be fast, not readable :-)
81 */
82 #define CMP_NAME strcmp(x->name, y->name)
83 #define CMP_SIZE (x->size > y->size ? 1 : (x->size == y->size ? 0 : -1))
84 #define CMP_ASIZE (x->asize > y->asize ? 1 : (x->asize == y->asize ? 0 : -1))
85 #define CMP_ITEMS (x->items > y->items ? 1 : (x->items == y->items ? 0 : -1))
86
87 /* try 1 */
88 r = dirlist_sort_col == DL_COL_NAME ? CMP_NAME :
89 dirlist_sort_col == DL_COL_SIZE ? CMP_SIZE :
90 dirlist_sort_col == DL_COL_ASIZE ? CMP_ASIZE :
91 dirlist_sort_col == DL_COL_ITEMS ? CMP_ITEMS :
92 cmp_mtime(x, y);
93 /* try 2 */
94 if(!r)
95 r = dirlist_sort_col == DL_COL_SIZE ? CMP_ASIZE : CMP_SIZE;
96 /* try 3 */
97 if(!r)
98 r = (dirlist_sort_col == DL_COL_NAME || dirlist_sort_col == DL_COL_ITEMS) ?
99 CMP_ASIZE : CMP_NAME;
100 /* try 4 */
101 if(!r)
102 r = dirlist_sort_col == DL_COL_ITEMS ? CMP_NAME : CMP_ITEMS;
103
104 /* reverse when sorting in descending order */
105 if(dirlist_sort_desc && r != 0)
106 r = r < 0 ? 1 : -1;
107
108 return r;
109 }
110
111
dirlist_sort(struct dir * list)112 static struct dir *dirlist_sort(struct dir *list) {
113 struct dir *p, *q, *e, *tail;
114 int insize, nmerges, psize, qsize, i;
115
116 insize = 1;
117 while(1) {
118 p = list;
119 list = NULL;
120 tail = NULL;
121 nmerges = 0;
122 while(p) {
123 nmerges++;
124 q = p;
125 psize = 0;
126 for(i=0; i<insize; i++) {
127 psize++;
128 q = q->next;
129 if(!q) break;
130 }
131 qsize = insize;
132 while(psize > 0 || (qsize > 0 && q)) {
133 if(psize == 0) {
134 e = q; q = q->next; qsize--;
135 } else if(qsize == 0 || !q) {
136 e = p; p = p->next; psize--;
137 } else if(dirlist_cmp(p,q) <= 0) {
138 e = p; p = p->next; psize--;
139 } else {
140 e = q; q = q->next; qsize--;
141 }
142 if(tail) tail->next = e;
143 else list = e;
144 e->prev = tail;
145 tail = e;
146 }
147 p = q;
148 }
149 tail->next = NULL;
150 if(nmerges <= 1) {
151 if(list->parent)
152 list->parent->sub = list;
153 return list;
154 }
155 insize *= 2;
156 }
157 }
158
159
160 /* passes through the dir listing once and:
161 * - makes sure one, and only one, visible item is selected
162 * - updates the dirlist_(maxs|maxa) values
163 * - makes sure that the FF_BSEL bits are correct */
dirlist_fixup(void)164 static void dirlist_fixup(void) {
165 struct dir *t;
166
167 /* we're going to determine the selected items from the list itself, so reset this one */
168 selected = NULL;
169
170 for(t=head; t; t=t->next) {
171 /* not visible? not selected! */
172 if(ISHIDDEN(t))
173 t->flags &= ~FF_BSEL;
174 else {
175 /* visible and selected? make sure only one item is selected */
176 if(t->flags & FF_BSEL) {
177 if(!selected)
178 selected = t;
179 else
180 t->flags &= ~FF_BSEL;
181 }
182 }
183
184 /* update dirlist_(maxs|maxa) */
185 if(t->size > dirlist_maxs)
186 dirlist_maxs = t->size;
187 if(t->asize > dirlist_maxa)
188 dirlist_maxa = t->asize;
189 }
190
191 /* no selected items found after one pass? select the first visible item */
192 if(!selected)
193 if((selected = dirlist_next(NULL)))
194 selected->flags |= FF_BSEL;
195 }
196
197
dirlist_open(struct dir * d)198 void dirlist_open(struct dir *d) {
199 dirlist_par = d;
200
201 /* set the head of the list */
202 head_real = head = d == NULL ? NULL : d->sub;
203
204 /* reset internal status */
205 dirlist_maxs = dirlist_maxa = 0;
206
207 /* stop if this is not a directory list we can work with */
208 if(d == NULL) {
209 dirlist_parent = NULL;
210 return;
211 }
212
213 /* sort the dir listing */
214 if(head)
215 head_real = head = dirlist_sort(head);
216
217 /* set the reference to the parent dir */
218 if(d->parent) {
219 if(!parent_alloc)
220 parent_alloc = xcalloc(1, dir_memsize(".."));
221 dirlist_parent = parent_alloc;
222 strcpy(dirlist_parent->name, "..");
223 dirlist_parent->next = head;
224 dirlist_parent->parent = d;
225 dirlist_parent->sub = d;
226 dirlist_parent->flags = FF_DIR;
227 head = dirlist_parent;
228 } else
229 dirlist_parent = NULL;
230
231 dirlist_fixup();
232 }
233
234
dirlist_next(struct dir * d)235 struct dir *dirlist_next(struct dir *d) {
236 if(!head)
237 return NULL;
238 if(!d) {
239 if(!ISHIDDEN(head))
240 return head;
241 else
242 d = head;
243 }
244 while((d = d->next)) {
245 if(!ISHIDDEN(d))
246 return d;
247 }
248 return NULL;
249 }
250
251
dirlist_prev(struct dir * d)252 static struct dir *dirlist_prev(struct dir *d) {
253 if(!head || !d)
254 return NULL;
255 while((d = d->prev)) {
256 if(!ISHIDDEN(d))
257 return d;
258 }
259 if(dirlist_parent)
260 return dirlist_parent;
261 return NULL;
262 }
263
264
dirlist_get(int i)265 struct dir *dirlist_get(int i) {
266 struct dir *t = selected, *d;
267
268 if(!head)
269 return NULL;
270
271 if(ISHIDDEN(selected)) {
272 selected = dirlist_next(NULL);
273 return selected;
274 }
275
276 /* i == 0? return the selected item */
277 if(!i)
278 return selected;
279
280 /* positive number? simply move forward */
281 while(i > 0) {
282 d = dirlist_next(t);
283 if(!d)
284 return t;
285 t = d;
286 if(!--i)
287 return t;
288 }
289
290 /* otherwise, backward */
291 while(1) {
292 d = dirlist_prev(t);
293 if(!d)
294 return t;
295 t = d;
296 if(!++i)
297 return t;
298 }
299 }
300
301
dirlist_select(struct dir * d)302 void dirlist_select(struct dir *d) {
303 if(!d || !head || ISHIDDEN(d) || d->parent != head->parent)
304 return;
305
306 selected->flags &= ~FF_BSEL;
307 selected = d;
308 selected->flags |= FF_BSEL;
309 }
310
311
312
313 /* We need a hint in order to figure out which item should be on top:
314 * 0 = only get the current top, don't set anything
315 * 1 = selected has moved down
316 * -1 = selected has moved up
317 * -2 = selected = first item in the list (faster version of '1')
318 * -3 = top should be considered as invalid (after sorting or opening another dir)
319 * -4 = an item has been deleted
320 * -5 = hidden flag has been changed
321 *
322 * Actions:
323 * hint = -1 or -4 -> top = selected_is_visible ? top : selected
324 * hint = -2 or -3 -> top = selected-(winrows-3)/2
325 * hint = 1 -> top = selected_is_visible ? top : selected-(winrows-4)
326 * hint = 0 or -5 -> top = selected_is_visible ? top : selected-(winrows-3)/2
327 *
328 * Regardless of the hint, the returned top will always be chosen such that the
329 * selected item is visible.
330 */
dirlist_top(int hint)331 struct dir *dirlist_top(int hint) {
332 struct dir *t;
333 int i, visible = 0;
334
335 if(hint == -2 || hint == -3)
336 top = NULL;
337
338 /* check whether the current selected item is within the visible window */
339 if(top) {
340 i = winrows-3;
341 t = dirlist_get(0);
342 while(t && i--) {
343 if(t == top) {
344 visible++;
345 break;
346 }
347 t = dirlist_prev(t);
348 }
349 }
350
351 /* otherwise, get a new top */
352 if(!visible)
353 top = hint == -1 || hint == -4 ? dirlist_get(0) :
354 hint == 1 ? dirlist_get(-1*(winrows-4)) :
355 dirlist_get(-1*(winrows-3)/2);
356
357 /* also make sure that if the list is longer than the window and the last
358 * item is visible, that this last item is also the last on the window */
359 t = top;
360 i = winrows-3;
361 while(t && i--)
362 t = dirlist_next(t);
363 t = top;
364 do {
365 top = t;
366 t = dirlist_prev(t);
367 } while(t && i-- > 0);
368
369 return top;
370 }
371
372
dirlist_set_sort(int col,int desc,int df)373 void dirlist_set_sort(int col, int desc, int df) {
374 /* update config */
375 if(col != DL_NOCHANGE)
376 dirlist_sort_col = col;
377 if(desc != DL_NOCHANGE)
378 dirlist_sort_desc = desc;
379 if(df != DL_NOCHANGE)
380 dirlist_sort_df = df;
381
382 /* sort the list (excluding the parent, which is always on top) */
383 if(head_real)
384 head_real = dirlist_sort(head_real);
385 if(dirlist_parent)
386 dirlist_parent->next = head_real;
387 else
388 head = head_real;
389 dirlist_top(-3);
390 }
391
392
dirlist_set_hidden(int hidden)393 void dirlist_set_hidden(int hidden) {
394 dirlist_hidden = hidden;
395 dirlist_fixup();
396 dirlist_top(-5);
397 }
398
399