1 #include "internal.h"
2
3 // these are never allocated themselves, but always as arrays of object
4 typedef struct nctree_int_item {
5 void* curry;
6 ncplane* ncp;
7 unsigned subcount;
8 struct nctree_int_item* subs;
9 } nctree_int_item;
10
11 typedef struct nctree {
12 int (*cbfxn)(ncplane*, void*, int);
13 nctree_int_item items; // topmost set of items, holds widget plane
14 nctree_int_item* curitem; // item addressed by the path
15 unsigned maxdepth; // maximum hierarchy level
16 unsigned* currentpath; // array of |maxdepth|+1 elements, ended by UINT_MAX
17 int activerow; // active row -1 <= activerow < dimy
18 int indentcols; // cols to indent per level
19 uint64_t bchannels; // border glyph channels
20 } nctree;
21
22 // recursively free an array of nctree_int_item; nctree_int_item structs are
23 // never individually free()d, just their innards
24 static void
free_tree_items(nctree_int_item * iarray)25 free_tree_items(nctree_int_item* iarray){
26 for(unsigned c = 0 ; c < iarray->subcount ; ++c){
27 free_tree_items(&iarray->subs[c]);
28 }
29 ncplane_destroy(iarray->ncp);
30 free(iarray->subs);
31 }
32
33 // allocates a |count|-sized array of nctree_int_items, and fills |fill| in,
34 // using |items|. updates |*maxdepth| when appropriate.
35 static int
dup_tree_items(nctree_int_item * fill,const struct nctree_item * items,unsigned count,unsigned depth,unsigned * maxdepth)36 dup_tree_items(nctree_int_item* fill, const struct nctree_item* items,
37 unsigned count, unsigned depth, unsigned* maxdepth){
38 fill->subcount = count;
39 // FIXME perhaps better to alloc a page at a time and take all items from
40 // there, for better TLB performance?
41 fill->subs = malloc(sizeof(*fill->subs) * count);
42 if(fill->subs == NULL){
43 return -1;
44 }
45 for(unsigned c = 0 ; c < fill->subcount ; ++c){
46 nctree_int_item* nii = &fill->subs[c];
47 nii->curry = items[c].curry;
48 if(nii->curry == NULL){
49 while(c--){
50 free_tree_items(&fill->subs[c]);
51 }
52 free(fill->subs);
53 return -1;
54 }
55 nii->ncp = NULL;
56 if(dup_tree_items(nii, items[c].subs, items[c].subcount, depth + 1, maxdepth)){
57 while(c--){
58 free_tree_items(&fill->subs[c]);
59 }
60 free(fill->subs);
61 return -1;
62 }
63 }
64 if(depth > *maxdepth){
65 *maxdepth = depth;
66 }
67 return 0;
68 }
69
70 static void
goto_last_item(nctree * n)71 goto_last_item(nctree* n){
72 void* prev = NULL;
73 void* r;
74 while((r = nctree_next(n))){
75 if(r == prev){
76 return;
77 }
78 prev = r;
79 }
80 }
81
82 static void
goto_first_item(nctree * n)83 goto_first_item(nctree* n){
84 if(n->maxdepth == 0){
85 n->currentpath[0] = UINT_MAX;
86 n->curitem = NULL;
87 n->activerow = -1;
88 }else{
89 n->currentpath[0] = 0;
90 n->currentpath[1] = UINT_MAX;
91 n->curitem = &n->items.subs[0];
92 n->activerow = 0;
93 }
94 }
95
96 // the initial path ought point to the first item.
97 static int
prep_initial_path(nctree * n,unsigned maxdepth)98 prep_initial_path(nctree* n, unsigned maxdepth){
99 n->currentpath = malloc(sizeof(*n->currentpath) * (maxdepth + 1));
100 if(n->currentpath == NULL){
101 return -1;
102 }
103 goto_first_item(n);
104 return 0;
105 }
106
107 static nctree*
nctree_inner_create(ncplane * n,const nctree_options * opts)108 nctree_inner_create(ncplane* n, const nctree_options* opts){
109 nctree* ret = malloc(sizeof(*ret));
110 if(ret){
111 ret->cbfxn = opts->nctreecb;
112 ret->indentcols = opts->indentcols;
113 ret->maxdepth = 0;
114 if(dup_tree_items(&ret->items, opts->items, opts->count, 0, &ret->maxdepth)){
115 free(ret);
116 return NULL;
117 }
118 //fprintf(stderr, "MAXDEPTH: %u\n", ret->maxdepth);
119 if(prep_initial_path(ret, ret->maxdepth)){
120 free_tree_items(&ret->items);
121 free(ret);
122 return NULL;
123 }
124 ret->items.ncp = n;
125 ret->items.curry = NULL;
126 nctree_redraw(ret);
127 }
128 return ret;
129 }
130
nctree_add(nctree * n,const unsigned * spec,const struct nctree_item * add)131 int nctree_add(nctree* n, const unsigned* spec, const struct nctree_item* add){
132 // it's illegal to pass an empty path for addition; one must pass { 0, UINT_MAX }
133 if(spec[0] == UINT_MAX){
134 logerror("invalid empty path\n");
135 return -1;
136 }
137 struct nctree_int_item* nii = &n->items;
138 const unsigned* p = spec;
139 unsigned depth = 0;
140 while(p[1] != UINT_MAX){ // we know p[1] isn't UINT_MAX
141 if(*p >= nii->subcount){
142 logerror("invalid path element (%u >= %u)\n", *p, nii->subcount);
143 return -1;
144 }
145 nii = &nii->subs[*p];
146 ++p;
147 ++depth;
148 }
149 // this last one can be equal to subcount; we're placing it at the end
150 if(*p > nii->subcount){
151 logerror("invalid path element (%u >= %u)\n", *p, nii->subcount);
152 return -1;
153 }
154 struct nctree_int_item* tmparr = realloc(nii->subs, sizeof(*nii->subs) * (nii->subcount + 1));
155 if(tmparr == NULL){
156 return -1;
157 }
158 nii->subs = tmparr;
159 if(*p != nii->subcount++){
160 memmove(&nii->subs[*p], &nii->subs[*p + 1], sizeof(*nii->subs) * (nii->subcount - *p));
161 }
162 if(p - spec >= n->maxdepth){
163 unsigned max = p - spec + 1;
164 unsigned* tmp = realloc(n->currentpath, sizeof(*n->currentpath) * (max + 1));
165 if(tmp == NULL){
166 return -1;
167 }
168 n->currentpath = tmp;
169 n->currentpath[max] = UINT_MAX;
170 n->maxdepth = max;
171 }
172 nii->subs[*p].subs = NULL;
173 nii->subs[*p].subcount = 0;
174 nii->subs[*p].curry = NULL;
175 nii->subs[*p].ncp = NULL;
176 if(dup_tree_items(&nii->subs[*p], add->subs, add->subcount, depth, &n->maxdepth)){
177 return -1;
178 }
179 if(n->activerow == -1){
180 n->activerow = 0;
181 n->curitem = &n->items;
182 n->currentpath[0] = 0;
183 }
184 return 0;
185 }
186
nctree_del(nctree * n,const unsigned * spec)187 int nctree_del(nctree* n, const unsigned* spec){
188 nctree_int_item* parent = NULL;
189 nctree_int_item* nii = &n->items;
190 const unsigned* p = spec;
191 while(*p != UINT_MAX){
192 if(*p >= nii->subcount){
193 logerror("invalid path element (%u >= %u)\n", *p, nii->subcount);
194 return -1;
195 }
196 parent = nii;
197 nii = &nii->subs[*p];
198 ++p;
199 }
200 free_tree_items(nii);
201 if(parent){
202 // parent can only be defined if we had at least one path element
203 unsigned lastelem = spec[-1];
204 if(lastelem != --parent->subcount){
205 memmove(&parent->subs[lastelem], &parent->subs[lastelem + 1],
206 sizeof(*parent->subs) * (parent->subcount - lastelem));
207 }
208 }
209 if(n->items.subcount == 0){
210 n->activerow = -1;
211 n->curitem = NULL;
212 }
213 return 0;
214 }
215
nctree_create(ncplane * n,const nctree_options * opts)216 nctree* nctree_create(ncplane* n, const nctree_options* opts){
217 if(opts->flags){
218 logwarn("Passed invalid flags 0x%016" PRIx64 "\n", opts->flags);
219 }
220 if(n == notcurses_stdplane(ncplane_notcurses(n))){
221 logerror("can't use the standard plane\n");
222 goto error;
223 }
224 if(opts->nctreecb == NULL){
225 logerror("Can't use NULL callback\n");
226 goto error;
227 }
228 if(opts->indentcols < 0){
229 logerror("Can't indent negative columns\n");
230 goto error;
231 }
232 nctree* ret = nctree_inner_create(n, opts);
233 if(ret == NULL){
234 logerror("Couldn't prepare nctree\n");
235 goto error;
236 }
237 return ret;
238
239 error:
240 ncplane_destroy(n);
241 return NULL;
242 }
243
nctree_destroy(nctree * n)244 void nctree_destroy(nctree* n){
245 if(n){
246 free_tree_items(&n->items);
247 free(n->currentpath);
248 free(n);
249 }
250 }
251
252 // Returns the ncplane on which this nctree lives.
nctree_plane(nctree * n)253 ncplane* nctree_plane(nctree* n){
254 return n->items.ncp;
255 }
256
257 // the prev is either:
258 // the item to the left, if the last path component is 0, or
259 // a drop from the rightmost non-zero path component, extended out to the right, or
260 // the current item
261 // so we can always just go to the last path component, act there, and possibly
262 // extend it out to the maximal topright.
263 static nctree_int_item*
nctree_prev_internal(nctree * n,unsigned * newpath)264 nctree_prev_internal(nctree* n, unsigned* newpath){
265 nctree_int_item* nii = &n->items;
266 nctree_int_item* wedge = NULL; // tracks the rightmost non-zero path
267 int idx = 0;
268 while(newpath[idx] != UINT_MAX){
269 nii = &nii->subs[newpath[idx]];
270 if(idx == 0){
271 wedge = &n->items;
272 }else{// if(idx > 1){
273 wedge = &wedge->subs[newpath[idx - 1]];
274 }
275 ++idx;
276 }
277 --idx;
278 if(newpath[idx]){
279 --newpath[idx];
280 nii = &wedge->subs[newpath[idx]];
281 ++idx;
282 //fprintf(stderr, "nii->subcount: %u idx: %d\n", nii->subcount, idx);
283 while(nii->subcount){
284 newpath[idx] = nii->subcount - 1;
285 nii = &nii->subs[newpath[idx]];
286 ++idx;
287 //fprintf(stderr, "nii->subcount: %u idx: %d\n", nii->subcount, idx);
288 }
289 newpath[idx] = UINT_MAX;
290 return nii;
291 }
292 if(wedge == &n->items){
293 return nii; // no change
294 }
295 newpath[idx] = UINT_MAX;
296 return wedge;
297 }
298
nctree_prev(nctree * n)299 void* nctree_prev(nctree* n){
300 int rows = 0;
301 if(n->curitem->ncp){
302 rows = ncplane_dim_y(n->curitem->ncp);
303 }
304 nctree_int_item* tmp = nctree_prev_internal(n, n->currentpath);
305 if(tmp != n->curitem){
306 n->curitem = tmp;
307 n->activerow -= rows;
308 if(n->activerow < 0){
309 n->activerow = 0;
310 }
311 }
312 return n->curitem->curry;
313 }
314
315 // the next is either:
316 // - an extension to the right, if subs are available, or
317 // - a bump to the rightmost path component with subcount available, or
318 // - the current item
319 static nctree_int_item*
nctree_next_internal(nctree * n,unsigned * newpath)320 nctree_next_internal(nctree* n, unsigned* newpath){
321 nctree_int_item* nii = &n->items;
322 nctree_int_item* wedge = NULL; // tracks the rightmost with room in subs
323 int idx = 0;
324 int wedidx = 0;
325 while(newpath[idx] != UINT_MAX){
326 if(newpath[idx] < nii->subcount - 1){
327 wedge = nii;
328 wedidx = idx;
329 }
330 nii = &nii->subs[newpath[idx]];
331 ++idx;
332 }
333 if(nii->subcount){
334 newpath[idx] = 0;
335 newpath[idx + 1] = UINT_MAX;
336 return &nii->subs[newpath[idx]];
337 }
338 if(wedge){
339 ++newpath[wedidx];
340 newpath[wedidx + 1] = UINT_MAX;
341 return &wedge->subs[newpath[wedidx]];
342 }
343 return nii;
344 }
345
nctree_next(nctree * n)346 void* nctree_next(nctree* n){
347 int rows = 0;
348 if(n->curitem->ncp){
349 rows = ncplane_dim_y(n->curitem->ncp);
350 }
351 nctree_int_item* tmp = nctree_next_internal(n, n->currentpath);
352 if(tmp != n->curitem){
353 n->curitem = tmp;
354 n->activerow += rows;
355 if(n->activerow >= (int)ncplane_dim_y(n->items.ncp)){
356 n->activerow = ncplane_dim_y(n->items.ncp) - 1;
357 }
358 }
359 return n->curitem->curry;
360 }
361
362 static int
tree_path_length(const unsigned * path)363 tree_path_length(const unsigned* path){
364 int len = 0;
365 while(path[len] != UINT_MAX){
366 ++len;
367 }
368 return len;
369 }
370
371 // draw the item. if *|frontiert| == *|frontierb|, we're the current item, and
372 // can use all the available space. if *|frontiert| < 0, draw down from
373 // *|frontierb|. otherwise, draw up from *|frontiert|.
374 static int
draw_tree_item(nctree * n,nctree_int_item * nii,const unsigned * path,int * frontiert,int * frontierb,int distance)375 draw_tree_item(nctree* n, nctree_int_item* nii, const unsigned* path,
376 int* frontiert, int* frontierb, int distance){
377 if(!nii->ncp){
378 const int startx = (tree_path_length(path) - 1) * n->indentcols;
379 int ymin, ymax;
380 if(*frontiert == *frontierb){
381 ymin = 0;
382 ymax = ncplane_dim_y(n->items.ncp) - 1;
383 }else if(*frontiert < 0){
384 ymin = *frontierb;
385 ymax = ncplane_dim_y(n->items.ncp) - 1;
386 }else{
387 ymin = 0;
388 ymax = *frontiert;
389 }
390 //fprintf(stderr, "x: %d y: %d\n", startx, ymin);
391 struct ncplane_options nopts = {
392 .x = startx,
393 .y = ymin,
394 .cols = ncplane_dim_x(n->items.ncp) - startx,
395 .rows = ymax - ymin + 1,
396 .userptr = NULL,
397 .name = NULL,
398 .resizecb = NULL,
399 .flags = 0,
400 };
401 nii->ncp = ncplane_create(n->items.ncp, &nopts);
402 if(nii->ncp == NULL){
403 return -1;
404 }
405 }else{
406 // FIXME possibly enlarge nii->ncp?
407 }
408 if(ncplane_y(nii->ncp) <= *frontiert || *frontierb >= (int)ncplane_dim_y(n->items.ncp)){
409 ncplane_move_yx(nii->ncp, *frontiert, ncplane_x(nii->ncp));
410 }else{
411 ncplane_move_yx(nii->ncp, *frontierb, ncplane_x(nii->ncp));
412 }
413 int ret = n->cbfxn(nii->ncp, nii->curry, distance);
414 if(ret < 0){
415 return -1;
416 }
417 // FIXME shrink plane if it was enlarged
418 //fprintf(stderr, "ft: %d fb: %d %p ncplane_y: %d\n", *frontiert, *frontierb, nii->ncp, ncplane_y(nii->ncp));
419 if(ncplane_y(nii->ncp) <= *frontiert){
420 *frontiert = ncplane_y(nii->ncp) - 1;
421 }
422 if(ncplane_y(nii->ncp) + (int)ncplane_dim_y(nii->ncp) > *frontierb){
423 *frontierb = ncplane_y(nii->ncp) + ncplane_dim_y(nii->ncp);
424 }
425 return 0;
426 }
427
428 // iterate backwards from tmppath, destroying any ncplanes we find. they've
429 // been pushed off-screen. tmppath is changed as we iterate. nii will not be
430 // destroyed, only items above nii.
431 static int
destroy_above(nctree * n,nctree_int_item * nii,unsigned * path,int distance)432 destroy_above(nctree* n, nctree_int_item* nii, unsigned* path, int distance){
433 nctree_int_item* tmpnii;
434 while((tmpnii = nctree_prev_internal(n, path)) != nii){
435 nii = tmpnii;
436 --distance;
437 if(nii->ncp){
438 ncplane_destroy(nii->ncp);
439 nii->ncp = NULL;
440 n->cbfxn(nii->ncp, nii->curry, distance);
441 }
442 }
443 return 0;
444 }
445
446 // iterate forwards from tmppath, destroying any ncplanes we find. they've
447 // been pushed off-screen. tmppath is changed as we iterate. nii will not be
448 // destroyed, only items below nii.
449 static int
destroy_below(nctree * n,nctree_int_item * nii,unsigned * path,int distance)450 destroy_below(nctree* n, nctree_int_item* nii, unsigned* path, int distance){
451 nctree_int_item* tmpnii;
452 while((tmpnii = nctree_next_internal(n, path)) != nii){
453 nii = tmpnii;
454 ++distance;
455 if(nii->ncp){
456 ncplane_destroy(nii->ncp);
457 nii->ncp = NULL;
458 n->cbfxn(nii->ncp, nii->curry, distance);
459 }
460 }
461 return 0;
462 }
463
464 // tmppath ought be initialized with currentpath, but having size sufficient
465 // to hold n->maxdepth + 1 unsigneds.
466 static int
nctree_inner_redraw(nctree * n,unsigned * tmppath)467 nctree_inner_redraw(nctree* n, unsigned* tmppath){
468 if(n->activerow < 0){
469 return 0;
470 }
471 ncplane* ncp = n->items.ncp;
472 if(ncplane_cursor_move_yx(ncp, n->activerow, 0)){
473 return -1;
474 }
475 int frontiert = n->activerow;
476 int frontierb = n->activerow;
477 nctree_int_item* nii = n->curitem;
478 int distance = 0;
479 // draw the focused item
480 if(draw_tree_item(n, nii, tmppath, &frontiert, &frontierb, distance)){
481 return -1;
482 }
483 nctree_int_item* tmpnii;
484 // draw items above the current one
485 while(frontiert >= 0){
486 if((tmpnii = nctree_prev_internal(n, tmppath)) == nii){
487 break;
488 }
489 nii = tmpnii;
490 --distance;
491 if(draw_tree_item(n, nii, tmppath, &frontiert, &frontierb, distance)){
492 return -1;
493 }
494 }
495 destroy_above(n, nii, tmppath, distance);
496 // move items up if there is a gap at the top FIXME
497 if(frontiert >= 0){
498 }
499 distance = 0;
500 n->activerow = ncplane_y(n->curitem->ncp);
501 nii = n->curitem;
502 // draw items below the current one FIXME
503 memcpy(tmppath, n->currentpath, sizeof(*tmppath) * (n->maxdepth + 1));
504 while(frontierb < (int)ncplane_dim_y(n->items.ncp)){
505 if((tmpnii = nctree_next_internal(n, tmppath)) == nii){
506 break;
507 }
508 nii = tmpnii;
509 ++distance;
510 if(draw_tree_item(n, nii, tmppath, &frontiert, &frontierb, distance)){
511 return -1;
512 }
513 }
514 destroy_below(n, nii, tmppath, distance);
515 return 0;
516 }
517
nctree_redraw(nctree * n)518 int nctree_redraw(nctree* n){
519 unsigned* tmppath = malloc(sizeof(*tmppath) * (n->maxdepth + 1));
520 if(tmppath == NULL){
521 return -1;
522 }
523 memcpy(tmppath, n->currentpath, sizeof(*tmppath) * (n->maxdepth + 1));
524 int ret = nctree_inner_redraw(n, tmppath);
525 free(tmppath);
526 return ret;
527 }
528
nctree_offer_input(nctree * n,const ncinput * ni)529 bool nctree_offer_input(nctree* n, const ncinput* ni){
530 if(ni->evtype == NCTYPE_RELEASE){
531 return false;
532 }
533 if(ni->id == NCKEY_UP){
534 nctree_prev(n);
535 return true;
536 }else if(ni->id == NCKEY_DOWN){
537 nctree_next(n);
538 return true;
539 }else if(ni->id == NCKEY_PGUP){
540 nctree_prev(n); // more FIXME
541 return true;
542 }else if(ni->id == NCKEY_PGDOWN){
543 nctree_next(n); // more FIXME
544 return true;
545 }else if(ni->id == NCKEY_HOME){
546 goto_first_item(n);
547 return true;
548 }else if(ni->id == NCKEY_END){
549 goto_last_item(n);
550 return true;
551 }
552 // FIXME implement left, right, +, - (expand/collapse)
553 return false;
554 }
555
nctree_focused(nctree * n)556 void* nctree_focused(nctree* n){
557 return n->curitem->curry;
558 }
559
nctree_goto(nctree * n,const unsigned * spec,int * failspec)560 void* nctree_goto(nctree* n, const unsigned* spec, int* failspec){
561 n->activerow = 0;
562 (void)spec;
563 (void)failspec;
564 // FIXME
565 return NULL;
566 }
567