2 * tree.c -- implements the 'tree' interface element for libdialog
4 * Author: Anatoly A. Orehovsky (tolik@mpeks.tomsk.su)
6 * Copyright (c) 1997, Anatoly A. Orehovsky
7 * 09/28/98 - patched by Anatoly A. Orehovsky (smart_tree())
11 #include <sys/cdefs.h>
12 __FBSDID("$FreeBSD$");
18 #include "dialog.priv.h"
21 /* static utils for make tree */
23 unsigned char *name; /* name of leaf */
24 unsigned char *branches; /* branches that going by leaf */
25 unsigned char slip; /* slip of leaf*/
26 int shift; /* shift relative root of tree */
29 static int mk_slip(struct leaf array[], int arr_size,
30 int number, int shift);
32 /* make tree from file
34 * filename - name of file with like find(1) output
35 * p_names - pointer to array of strings
36 * p_size - pointer to size of array
37 * FS - fields separator
38 * p_array - pointer to array of leafs
41 * 0 - ok and names by p_names, size by p_size, array by p_array set
42 * -1 - memory allocation error (errno set)
45 static int mk_ftree(char *filename,
46 unsigned char ***p_names, int *p_size, unsigned char FS,
47 struct leaf **p_array);
49 /* make tree from array
51 * names - array of strings
52 * size - size of array
53 * FS - fields separator
54 * p_array - pointer to array of leafs
57 * 0 - ok and array by p_array set
58 * -1 - memory allocation error (errno set)
61 static int mk_tree(unsigned char **names, int size, unsigned char FS,
62 struct leaf **p_array);
64 /* free memory from tree (leafs)
70 static void free_leafs(struct leaf *array, int size);
72 /* free memory from source data for tree (names)
75 * if 0 <= choice <= size - pointer to name from names,
76 * and memory for name not released (must be freed later)
77 * else - NULL (recomended choice -1 for it)
80 static unsigned char *free_names(unsigned char **names,
81 int size, int choice);
83 /* end of static utils for make tree */
85 /* static utils for ftree */
87 /* control struct for queue */
89 int size; /* size of queue */
90 struct m_queue *first; /* begin of queue */
91 struct m_queue *last; /* end of queue */
96 void *pointer; /* queue member */
97 struct m_queue *next; /* next queue member */
100 /* init struct queue by zeros */
101 static void init_queue(struct queue *queue);
103 /* add pointer to queue */
104 /* return - pointer or NULL if error */
105 static void *p2_queue(struct queue *queue, void *pointer);
107 /* get first from queue */
108 /* return - pointer or NULL if queue is empty */
109 static void *first_queue(struct queue *queue);
111 /* make zero terminated array from queue */
112 /* return - pointer to array or NULL if error */
113 static void **q2arr(struct queue *queue, int depth);
115 /* smart_tree (for like find(1) with -d flag output compliance) */
116 /* return - not NULL or NULL if malloc error */
117 static unsigned char *smart_tree(struct queue *queue, unsigned char FS,
118 unsigned char *current,
119 unsigned char *prev);
121 /* end of static utils for ftree */
123 /* static utils for saved_tree */
125 /* saved values for unique tree */
127 unsigned char **names; /* names + */
128 int size; /* size + */
129 unsigned char FS; /* FS + */
130 int height; /* height + */
131 int width; /* width + */
132 int menu_height; /* menu_height - unique for treebox ? */
133 int ch; /* saved ch - choice */
134 int sc; /* saved sc - scroll */
137 /* search saved tree within queue */
138 /* return - struct saved_tree * or NULL if not found */
139 static struct saved_tree *search_saved_tree(struct queue *queue,
140 unsigned char **names,
147 /* end of static utils for saved_tree */
149 static void print_item(WINDOW *win, struct leaf item, int choice, int selected);
151 static void print_position(WINDOW *win, int x, int y,
152 int cur_pos, int size);
154 static int menu_width, item_x;
156 static int dialog_treemenu(unsigned char *title, unsigned char *prompt,
157 int height, int width, int menu_height,
158 int item_no, struct leaf items[],
163 * Display a menu for choosing among a number of options
166 int dialog_treemenu(unsigned char *title, unsigned char *prompt,
167 int height, int width, int menu_height,
168 int item_no, struct leaf items[],
172 int i, j, x, y, cur_x, cur_y, box_x, box_y, key = 0, button = 0, choice = 0,
173 l, scroll = 0, max_choice, redraw_menu = FALSE;
174 WINDOW *dialog, *menu;
176 if (ch) /* restore menu item info */
181 max_choice = MIN(menu_height, item_no);
184 /* Find length of longest item in order to center menu */
185 for (i = 0; i < item_no; i++) {
186 l = strlen(items[i].name) + strlen(items[i].branches) * 4 + 4;
187 item_x = MAX(item_x, l);
191 height = strheight(prompt)+menu_height+4+2;
193 i = strwidth(prompt);
194 j = ((title != NULL) ? strwidth(title) : 0);
196 width = MAX(width,item_x+4)+4;
198 width = MAX(width,24);
204 /* center dialog box on screen */
205 x = (COLS - width)/2;
206 y = (LINES - height)/2;
210 draw_shadow(stdscr, y, x, height, width);
212 dialog = newwin(height, width, y, x);
213 if (dialog == NULL) {
215 fprintf(stderr, "\nnewwin(%d,%d,%d,%d) failed, maybe wrong dims\n", height,width,y,x);
218 keypad(dialog, TRUE);
220 draw_box(dialog, 0, 0, height, width, dialog_attr, border_attr);
221 wattrset(dialog, border_attr);
222 wmove(dialog, height-3, 0);
223 waddch(dialog, ACS_LTEE);
224 for (i = 0; i < width-2; i++)
225 waddch(dialog, ACS_HLINE);
226 wattrset(dialog, dialog_attr);
227 waddch(dialog, ACS_RTEE);
228 wmove(dialog, height-2, 1);
229 for (i = 0; i < width-2; i++)
233 wattrset(dialog, title_attr);
234 wmove(dialog, 0, (width - strlen(title))/2 - 1);
236 waddstr(dialog, title);
239 wattrset(dialog, dialog_attr);
241 print_autowrap(dialog, prompt, height-1, width-2, width, 1, 2, TRUE, FALSE);
243 menu_width = width-6;
244 getyx(dialog, cur_y, cur_x);
246 box_x = (width - menu_width)/2 - 1;
248 /* create new window for the menu */
249 menu = subwin(dialog, menu_height, menu_width, y + box_y + 1, x + box_x + 1);
252 fprintf(stderr, "\nsubwin(dialog,%d,%d,%d,%d) failed, maybe wrong dims\n", menu_height,menu_width,y+box_y+1,x+box_x+1);
257 /* draw a box around the menu items */
258 draw_box(dialog, box_y, box_x, menu_height+2, menu_width+2, menubox_border_attr, menubox_attr);
263 for (i = 0; i < max_choice; i++)
264 print_item(menu, items[(scroll+i)], i, i == choice);
266 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
267 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
269 display_helpline(dialog, height-1, width);
273 print_button(dialog, "Cancel", y, x+14, FALSE);
274 print_button(dialog, " OK ", y, x, TRUE);
279 key = wgetch(dialog);
280 /* Check if key pressed matches first character of any item tag in menu */
282 if (key == KEY_UP || key == KEY_DOWN || key == '-' || key == '+') {
283 if (key == KEY_UP || key == '-') {
287 /* wscrl() in ncurses 1.8.1 seems to be broken, causing a segmentation
288 violation when scrolling windows of height = 4, so scrolling is not
291 getyx(dialog, cur_y, cur_x); /* Save cursor position */
292 /* Reprint menu to scroll down */
293 for (i = 0; i < max_choice; i++)
294 print_item(menu, items[(scroll+i)], i, i == choice);
298 /* Scroll menu down */
299 getyx(dialog, cur_y, cur_x); /* Save cursor position */
300 if (menu_height > 1) {
301 /* De-highlight current first item before scrolling down */
302 print_item(menu, items[scroll], 0, FALSE);
303 scrollok(menu, TRUE);
305 scrollok(menu, FALSE);
308 print_item(menu, items[scroll], 0, TRUE);
311 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
312 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
313 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
316 continue; /* wait for another key press */
321 else if (key == KEY_DOWN || key == '+') {
322 if (choice == max_choice - 1) {
323 if (scroll+choice < item_no-1) {
325 /* wscrl() in ncurses 1.8.1 seems to be broken, causing a segmentation
326 violation when scrolling windows of height = 4, so scrolling is not
329 getyx(dialog, cur_y, cur_x); /* Save cursor position */
330 /* Reprint menu to scroll up */
331 for (i = 0; i < max_choice; i++)
332 print_item(menu, items[(scroll+i)], i, i == choice);
337 getyx(dialog, cur_y, cur_x); /* Save cursor position */
338 if (menu_height > 1) {
339 /* De-highlight current last item before scrolling up */
340 print_item(menu, items[(scroll+max_choice-1)], max_choice-1, FALSE);
341 scrollok(menu, TRUE);
343 scrollok(menu, FALSE);
346 print_item(menu, items[(scroll+max_choice-1)], max_choice-1, TRUE);
349 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
350 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
351 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
354 continue; /* wait for another key press */
361 /* De-highlight current item */
362 getyx(dialog, cur_y, cur_x); /* Save cursor position */
363 print_item(menu, items[(scroll+choice)], choice, FALSE);
365 /* Highlight new item */
367 print_item(menu, items[(scroll+choice)], choice, TRUE);
369 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
370 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
373 continue; /* wait for another key press */
376 /* save info about menu item position */
386 if (scroll > menu_height) { /* can we go up? */
387 scroll -= (menu_height);
396 if (scroll + menu_height >= item_no-1 - menu_height) { /* can we go down a full page? */
397 scroll = item_no - menu_height;
398 if (scroll < 0) scroll = 0;
400 scroll += menu_height;
412 scroll = item_no - menu_height;
413 if (scroll < 0) scroll = 0;
414 choice = max_choice - 1;
420 *result = scroll+choice;
431 button = 1; /* Indicates "Cancel" button is selected */
432 print_button(dialog, " OK ", y, x, FALSE);
433 print_button(dialog, "Cancel", y, x+14, TRUE);
436 button = 0; /* Indicates "OK" button is selected */
437 print_button(dialog, "Cancel", y, x+14, FALSE);
438 print_button(dialog, " OK ", y, x, TRUE);
447 *result = scroll+choice;
457 for (i = 0; i < max_choice; i++) {
458 print_item(menu, items[(scroll+i)],
462 getyx(dialog, cur_y, cur_x); /* Save cursor position */
463 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
464 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
465 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
472 return -1; /* ESC pressed */
474 /* End of dialog_treemenu() */
480 static void print_item(WINDOW *win, struct leaf item, int choice, int selected)
482 int i, j = menu_width - 2;
483 char *branches = item.branches;
485 /* Clear 'residue' of last item */
486 wattrset(win, menubox_attr);
487 wmove(win, choice, 0);
488 for (i = 0; i < menu_width; i++)
490 wmove(win, choice, item_x);
492 while(*branches && j)
494 switch (*branches++) {
495 case ' ' : waddch(win, ' ');
497 case '|' : waddch(win, ACS_VLINE);
512 case '+' : waddch(win, ACS_LTEE);
514 case '`' : waddch(win, ACS_LLCORNER);
522 waddch(win, ACS_HLINE);
526 wattrset(win, selected ? item_selected_attr : item_attr);
528 waddnstr(win, item.name, j);
530 /* End of print_item() */
533 * Print current position
535 static void print_position(WINDOW *win, int x, int y,
536 int cur_pos, int size)
540 wattrset(win, position_indicator_attr);
541 percent = cur_pos == size - 1 ? 100 : (cur_pos * 100)/(size - 1);
542 wmove(win, y + 1, x - 6);
543 wprintw(win, "(%3d%%)", percent);
545 /* End of print_position() */
548 * Display a tree menu from file
550 * filename - file with like find(1) output
551 * FS - fields separator
552 * title - title of dialog box
553 * prompt - prompt text into dialog box
554 * height - height of dialog box
555 * width - width of dialog box
556 * menu_height - height of menu box
557 * result - pointer to char array
561 * 0 - Ok, result set (must be freed later)
565 int dialog_ftree(unsigned char *filename, unsigned char FS,
566 unsigned char *title, unsigned char *prompt,
567 int height, int width, int menu_height,
568 unsigned char **result)
570 int retcode, choice, size;
572 unsigned char **names;
574 if (mk_ftree(filename, &names, &size, FS, &items))
576 perror("dialog_ftree");
583 fprintf(stderr, "\ndialog_ftree: file %s is empty\n", filename);
588 retcode = dialog_treemenu(title, prompt, height, width, menu_height,
589 size, items, &choice, NULL, NULL);
591 free_leafs(items, size);
594 *result = free_names(names, size, choice);
596 (void)free_names(names, size, -1);
600 /* End of dialog_ftree() */
603 * Display a tree menu from array
605 * names - array with like find(1) output
606 * size - size of array
607 * FS - fields separator
608 * title - title of dialog box
609 * prompt - prompt text into dialog box
610 * height - height of dialog box
611 * width - width of dialog box
612 * menu_height - height of menu box
613 * result - pointer to char array
621 int dialog_tree(unsigned char **names, int size, unsigned char FS,
622 unsigned char *title, unsigned char *prompt,
623 int height, int width, int menu_height,
624 unsigned char **result)
628 struct saved_tree *st;
629 static struct queue *q_saved_tree = NULL;
633 fprintf(stderr, "\ndialog_tree: source array is empty\n");
638 if (mk_tree(names, size, FS, &items))
640 perror("dialog_tree");
645 /* is tree saved ? */
646 if (!(st = search_saved_tree(q_saved_tree, names,
648 height, width, menu_height))) {
651 calloc(sizeof (struct queue), 1))) {
652 perror("dialog_tree");
658 if (!(st = calloc(sizeof (struct saved_tree), 1))) {
659 perror("dialog_tree");
669 st->menu_height = menu_height;
671 if (!p2_queue(q_saved_tree, st)) {
672 perror("dialog_tree");
678 retcode = dialog_treemenu(title, prompt, height, width, menu_height,
679 size, items, &choice,
680 &(st->ch), &(st->sc));
682 free_leafs(items, size);
685 *result = names[choice];
689 /* End of dialog_tree() */
691 /* utils for ftree */
693 /* init struct queue by zeros */
695 init_queue(struct queue *queue)
697 bzero((void *)queue, sizeof(struct queue));
700 /* add pointer to queue */
701 /* return - pointer or NULL if error */
703 p2_queue(struct queue *queue, void *pointer)
710 if (!(queue->first = queue->last =
711 calloc(1, sizeof(struct m_queue))))
717 if (!(queue->last->next =
718 calloc(1, sizeof(struct m_queue))))
721 queue->last = queue->last->next;
725 return queue->last->pointer = pointer;
728 /* get first from queue */
729 /* return - pointer or NULL if queue is empty */
731 first_queue(struct queue *queue)
734 struct m_queue *new_first;
741 retval = queue->first->pointer;
742 new_first = queue->first->next;
744 queue->first = new_first;
751 /* make zero terminated array from queue */
752 /* return - pointer to array or NULL if error */
754 q2arr(struct queue *queue, int depth)
763 /* memory allocation for array */
764 if (!(mono = end = malloc(depth * sizeof(void *) + 1)))
769 if (!(*end++ = first_queue(queue)))
780 * smart_tree (for like find(1) with -d flag output compliance)
783 * NULL - malloc error
789 smart_tree(struct queue *queue,
791 unsigned char *current,
792 unsigned char *prev) {
793 unsigned char *pcurrent = current, *pprev = prev, *toqueue;
794 register char break_flag = 0;
796 while(*pcurrent && *pprev) {
797 if (*pcurrent == *pprev) {
807 if (!*pprev || break_flag) {
808 if (*pcurrent == FS) {
811 if ((!*prev) && (*pcurrent)) {
812 unsigned char tchar = *pcurrent;
815 if (!(toqueue = strdup(current))) {
819 if (!p2_queue(queue, toqueue)) {
828 if (*pcurrent == FS) {
830 if (!(toqueue = strdup(current))) {
834 if (!p2_queue(queue, toqueue)) {
842 if (!p2_queue(queue, current))
848 /* end of utils for ftree */
850 /* utils for make tree */
852 /* if error - return -1 */
855 mk_slip(struct leaf array[], int arr_size, int number, int shift)
860 if (number > arr_size - 1)
865 if (!(array[number].branches = calloc(1, t_shift + 1)))
868 (void)memset(array[number].branches, ' ', t_shift);
872 while (array[number].shift < array[t_number + 1].shift)
874 t_number = mk_slip(array, arr_size, t_number + 1, t_shift + 1);
877 if (t_number == arr_size - 1)
881 if (array[number].shift == array[t_number + 1].shift)
882 array[number].slip = '+';
884 if ((array[number].shift > array[t_number + 1].shift) ||
885 t_number == arr_size - 1)
886 array[number].slip = '`';
892 /* make tree from file
894 * filename - name of file with like find(1) output
895 * p_names - pointer to array of strings
896 * p_size - pointer to size of array
897 * FS - fields separator
898 * p_array - pointer to array of leafs
901 * 0 - ok and names by p_names, size by p_size, array by p_array set
902 * -1 - memory allocation error (errno set)
907 mk_ftree(char *filename,
908 unsigned char ***p_names, int *p_size, unsigned char FS,
909 struct leaf **p_array)
911 int NR; /* number of input records */
913 unsigned char *string, *sstring = "";
914 unsigned char **names;
918 if (!(input_file = fopen(filename, "r")))
923 if (!(string = malloc(BUFSIZ)))
926 /* read input file into queue */
927 while(fgets(string, BUFSIZ, input_file))
929 if (strchr(string, '\n'))
930 *strchr(string, '\n') = '\0';
932 if (!(string = realloc(string, strlen(string) + 1)))
935 if (!smart_tree(&queue, FS, string, sstring))
939 if (!(string = malloc(BUFSIZ)))
941 } /* read input file into queue */
943 if (fclose(input_file) == EOF)
946 if (!(NR = queue.size))
952 /* make array from queue */
953 if (!(names = (unsigned char **)q2arr(&queue, NR)))
959 /* make tree from array */
960 return mk_tree(names, NR, FS, p_array);
964 /* make tree from array
966 * names - array of strings
967 * size - size of array
968 * FS - fields separator
969 * p_array - pointer to array of leafs
972 * 0 - ok and array by p_array set
973 * -1 - memory allocation error (errno set)
978 mk_tree(unsigned char **names, int size, unsigned char FS,
979 struct leaf **p_array)
984 /* make array of leafs */
985 if (!(array = calloc(size, sizeof(struct leaf))))
989 for (i = 0; i < size; i++)
991 unsigned char *in_string, *name;
994 in_string = name = names[i];
997 if (*in_string == FS) {
998 if (!i && !*(in_string + 1))
1003 name = in_string + 1;
1008 array[i].name = name;
1009 array[i].shift = shift;
1010 array[i].slip = '\0';
1011 array[i].branches = NULL;
1015 for (i = 0;i < size; i++)
1017 i = mk_slip(array, size, i, 0);
1023 for (i = 1;i < size; i++)
1025 unsigned char *src = array[i - 1].branches;
1026 unsigned char *dst = array[i].branches;
1032 switch (array[i - 1].slip) {
1033 case '+' : *dst = '|';
1035 case '`' : *dst = ' ';
1037 } /* make branches */
1044 /* free memory from tree (leafs)
1052 free_leafs(struct leaf *array, int size)
1054 struct leaf *p_array = array;
1057 free(array++->branches);
1060 } /* free_leafs() */
1062 /* free memory from source data for tree (names)
1065 * if 0 <= choice <= size - pointer to name from names,
1066 * and memory for name not released (must be freed later)
1067 * else - NULL (recomended choice -1 for it)
1072 free_names(unsigned char **names, int size, int choice)
1074 unsigned char *retval = NULL;
1075 unsigned char **p_names = names;
1086 } /* free_names() */
1088 /* end of utils for make tree */
1090 /* static utils for saved_tree */
1092 /* search saved tree within queue */
1093 /* return - struct *saved_tree or NULL if not found */
1096 search_saved_tree(struct queue *queue, unsigned char **names, int size,
1098 int height, int width,
1101 struct m_queue *member;
1102 struct saved_tree *retval;
1104 if (!queue || !names || !FS ||
1105 !height || !width || !menu_height)
1108 if (!(member = queue->first))
1111 while (member->next) {
1112 retval = member->pointer;
1113 if ((names == retval->names) &&
1114 (size == retval->size) &&
1115 (FS == retval->FS) &&
1116 (height == retval->height) &&
1117 (width == retval->width) &&
1118 (menu_height == retval->menu_height))
1120 member = member->next;
1122 retval = member->pointer;
1123 if ((names == retval->names) &&
1124 (size == retval->size) &&
1125 (FS == retval->FS) &&
1126 (height == retval->height) &&
1127 (width == retval->width) &&
1128 (menu_height == retval->menu_height))
1133 /* end of static utils for saved_tree */