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())
9 * $FreeBSD: src/gnu/lib/libdialog/tree.c,v 1.5.2.1 2001/07/31 20:34:00 eric Exp $
10 * $DragonFly: src/gnu/lib/libdialog/tree.c,v 1.2 2003/06/17 04:25:43 dillon Exp $
17 #include "dialog.priv.h"
20 /* static utils for make tree */
22 unsigned char *name; /* name of leaf */
23 unsigned char *branches; /* branches that going by leaf */
24 unsigned char slip; /* slip of leaf*/
25 int shift; /* shift relative root of tree */
28 static int mk_slip(struct leaf array[], int arr_size,
29 int number, int shift);
31 /* make tree from file
33 * filename - name of file with like find(1) output
34 * p_names - pointer to array of strings
35 * p_size - pointer to size of array
36 * FS - fields separator
37 * p_array - pointer to array of leafs
40 * 0 - ok and names by p_names, size by p_size, array by p_array set
41 * -1 - memory allocation error (errno set)
44 static int mk_ftree(char *filename,
45 unsigned char ***p_names, int *p_size, unsigned char FS,
46 struct leaf **p_array);
48 /* make tree from array
50 * names - array of strings
51 * size - size of array
52 * FS - fields separator
53 * p_array - pointer to array of leafs
56 * 0 - ok and array by p_array set
57 * -1 - memory allocation error (errno set)
60 static int mk_tree(unsigned char **names, int size, unsigned char FS,
61 struct leaf **p_array);
63 /* free memory from tree (leafs)
69 static void free_leafs(struct leaf *array, int size);
71 /* free memory from source data for tree (names)
74 * if 0 <= choice <= size - pointer to name from names,
75 * and memory for name not released (must be freed later)
76 * else - NULL (recomended choice -1 for it)
79 static unsigned char *free_names(unsigned char **names,
80 int size, int choice);
82 /* end of static utils for make tree */
84 /* static utils for ftree */
86 /* control struct for queue */
88 int size; /* size of queue */
89 struct m_queue *first; /* begin of queue */
90 struct m_queue *last; /* end of queue */
95 void *pointer; /* queue member */
96 struct m_queue *next; /* next queue member */
99 /* init struct queue by zeros */
100 static void init_queue(struct queue *queue);
102 /* add pointer to queue */
103 /* return - pointer or NULL if error */
104 static void *p2_queue(struct queue *queue, void *pointer);
106 /* get first from queue */
107 /* return - pointer or NULL if queue is empty */
108 static void *first_queue(struct queue *queue);
110 /* make zero terminated array from queue */
111 /* return - pointer to array or NULL if error */
112 static void **q2arr(struct queue *queue, int depth);
114 /* smart_tree (for like find(1) with -d flag output compliance) */
115 /* return - not NULL or NULL if malloc error */
116 static unsigned char *smart_tree(struct queue *queue, unsigned char FS,
117 unsigned char *current,
118 unsigned char *prev);
120 /* end of static utils for ftree */
122 /* static utils for saved_tree */
124 /* saved values for unique tree */
126 unsigned char **names; /* names + */
127 int size; /* size + */
128 unsigned char FS; /* FS + */
129 int height; /* height + */
130 int width; /* width + */
131 int menu_height; /* menu_height - unique for treebox ? */
132 int ch; /* saved ch - choice */
133 int sc; /* saved sc - scroll */
136 /* search saved tree within queue */
137 /* return - struct saved_tree * or NULL if not found */
138 static struct saved_tree *search_saved_tree(struct queue *queue,
139 unsigned char **names,
146 /* end of static utils for saved_tree */
148 static void print_item(WINDOW *win, struct leaf item, int choice, int selected);
150 static void print_position(WINDOW *win, int x, int y,
151 int cur_pos, int size);
153 static int menu_width, item_x;
155 static int dialog_treemenu(unsigned char *title, unsigned char *prompt,
156 int height, int width, int menu_height,
157 int item_no, struct leaf items[],
162 * Display a menu for choosing among a number of options
165 int dialog_treemenu(unsigned char *title, unsigned char *prompt,
166 int height, int width, int menu_height,
167 int item_no, struct leaf items[],
171 int i, j, x, y, cur_x, cur_y, box_x, box_y, key = 0, button = 0, choice = 0,
172 l, scroll = 0, max_choice, redraw_menu = FALSE;
173 WINDOW *dialog, *menu;
175 if (ch) /* restore menu item info */
180 max_choice = MIN(menu_height, item_no);
183 /* Find length of longest item in order to center menu */
184 for (i = 0; i < item_no; i++) {
185 l = strlen(items[i].name) + strlen(items[i].branches) * 4 + 4;
186 item_x = MAX(item_x, l);
190 height = strheight(prompt)+menu_height+4+2;
192 i = strwidth(prompt);
193 j = ((title != NULL) ? strwidth(title) : 0);
195 width = MAX(width,item_x+4)+4;
197 width = MAX(width,24);
203 /* center dialog box on screen */
204 x = (COLS - width)/2;
205 y = (LINES - height)/2;
209 draw_shadow(stdscr, y, x, height, width);
211 dialog = newwin(height, width, y, x);
212 if (dialog == NULL) {
214 fprintf(stderr, "\nnewwin(%d,%d,%d,%d) failed, maybe wrong dims\n", height,width,y,x);
217 keypad(dialog, TRUE);
219 draw_box(dialog, 0, 0, height, width, dialog_attr, border_attr);
220 wattrset(dialog, border_attr);
221 wmove(dialog, height-3, 0);
222 waddch(dialog, ACS_LTEE);
223 for (i = 0; i < width-2; i++)
224 waddch(dialog, ACS_HLINE);
225 wattrset(dialog, dialog_attr);
226 waddch(dialog, ACS_RTEE);
227 wmove(dialog, height-2, 1);
228 for (i = 0; i < width-2; i++)
232 wattrset(dialog, title_attr);
233 wmove(dialog, 0, (width - strlen(title))/2 - 1);
235 waddstr(dialog, title);
238 wattrset(dialog, dialog_attr);
240 print_autowrap(dialog, prompt, height-1, width-2, width, 1, 2, TRUE, FALSE);
242 menu_width = width-6;
243 getyx(dialog, cur_y, cur_x);
245 box_x = (width - menu_width)/2 - 1;
247 /* create new window for the menu */
248 menu = subwin(dialog, menu_height, menu_width, y + box_y + 1, x + box_x + 1);
251 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);
256 /* draw a box around the menu items */
257 draw_box(dialog, box_y, box_x, menu_height+2, menu_width+2, menubox_border_attr, menubox_attr);
262 for (i = 0; i < max_choice; i++)
263 print_item(menu, items[(scroll+i)], i, i == choice);
265 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
266 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
268 display_helpline(dialog, height-1, width);
272 print_button(dialog, "Cancel", y, x+14, FALSE);
273 print_button(dialog, " OK ", y, x, TRUE);
278 key = wgetch(dialog);
279 /* Check if key pressed matches first character of any item tag in menu */
281 if (key == KEY_UP || key == KEY_DOWN || key == '-' || key == '+') {
282 if (key == KEY_UP || key == '-') {
286 /* wscrl() in ncurses 1.8.1 seems to be broken, causing a segmentation
287 violation when scrolling windows of height = 4, so scrolling is not
290 getyx(dialog, cur_y, cur_x); /* Save cursor position */
291 /* Reprint menu to scroll down */
292 for (i = 0; i < max_choice; i++)
293 print_item(menu, items[(scroll+i)], i, i == choice);
297 /* Scroll menu down */
298 getyx(dialog, cur_y, cur_x); /* Save cursor position */
299 if (menu_height > 1) {
300 /* De-highlight current first item before scrolling down */
301 print_item(menu, items[scroll], 0, FALSE);
302 scrollok(menu, TRUE);
304 scrollok(menu, FALSE);
307 print_item(menu, items[scroll], 0, TRUE);
310 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
311 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
312 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
315 continue; /* wait for another key press */
320 else if (key == KEY_DOWN || key == '+') {
321 if (choice == max_choice - 1) {
322 if (scroll+choice < item_no-1) {
324 /* wscrl() in ncurses 1.8.1 seems to be broken, causing a segmentation
325 violation when scrolling windows of height = 4, so scrolling is not
328 getyx(dialog, cur_y, cur_x); /* Save cursor position */
329 /* Reprint menu to scroll up */
330 for (i = 0; i < max_choice; i++)
331 print_item(menu, items[(scroll+i)], i, i == choice);
336 getyx(dialog, cur_y, cur_x); /* Save cursor position */
337 if (menu_height > 1) {
338 /* De-highlight current last item before scrolling up */
339 print_item(menu, items[(scroll+max_choice-1)], max_choice-1, FALSE);
340 scrollok(menu, TRUE);
342 scrollok(menu, FALSE);
345 print_item(menu, items[(scroll+max_choice-1)], max_choice-1, TRUE);
348 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
349 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
350 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
353 continue; /* wait for another key press */
360 /* De-highlight current item */
361 getyx(dialog, cur_y, cur_x); /* Save cursor position */
362 print_item(menu, items[(scroll+choice)], choice, FALSE);
364 /* Highlight new item */
366 print_item(menu, items[(scroll+choice)], choice, TRUE);
368 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
369 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
372 continue; /* wait for another key press */
375 /* save info about menu item position */
385 if (scroll > menu_height) { /* can we go up? */
386 scroll -= (menu_height);
395 if (scroll + menu_height >= item_no-1 - menu_height) { /* can we go down a full page? */
396 scroll = item_no - menu_height;
397 if (scroll < 0) scroll = 0;
399 scroll += menu_height;
411 scroll = item_no - menu_height;
412 if (scroll < 0) scroll = 0;
413 choice = max_choice - 1;
419 *result = scroll+choice;
430 button = 1; /* Indicates "Cancel" button is selected */
431 print_button(dialog, " OK ", y, x, FALSE);
432 print_button(dialog, "Cancel", y, x+14, TRUE);
435 button = 0; /* Indicates "OK" button is selected */
436 print_button(dialog, "Cancel", y, x+14, FALSE);
437 print_button(dialog, " OK ", y, x, TRUE);
446 *result = scroll+choice;
456 for (i = 0; i < max_choice; i++) {
457 print_item(menu, items[(scroll+i)],
461 getyx(dialog, cur_y, cur_x); /* Save cursor position */
462 print_arrows(dialog, scroll, menu_height, item_no, box_x, box_y, item_x, cur_x, cur_y);
463 print_position(dialog, box_x+menu_width, box_y+menu_height, scroll+choice, item_no);
464 wmove(dialog, cur_y, cur_x); /* Restore cursor to previous position */
471 return -1; /* ESC pressed */
473 /* End of dialog_treemenu() */
479 static void print_item(WINDOW *win, struct leaf item, int choice, int selected)
481 int i, j = menu_width - 2;
482 char *branches = item.branches;
484 /* Clear 'residue' of last item */
485 wattrset(win, menubox_attr);
486 wmove(win, choice, 0);
487 for (i = 0; i < menu_width; i++)
489 wmove(win, choice, item_x);
491 while(*branches && j)
493 switch (*branches++) {
494 case ' ' : waddch(win, ' ');
496 case '|' : waddch(win, ACS_VLINE);
511 case '+' : waddch(win, ACS_LTEE);
513 case '`' : waddch(win, ACS_LLCORNER);
521 waddch(win, ACS_HLINE);
525 wattrset(win, selected ? item_selected_attr : item_attr);
527 waddnstr(win, item.name, j);
529 /* End of print_item() */
532 * Print current position
534 static void print_position(WINDOW *win, int x, int y,
535 int cur_pos, int size)
539 wattrset(win, position_indicator_attr);
540 percent = cur_pos == size - 1 ? 100 : (cur_pos * 100)/(size - 1);
541 wmove(win, y + 1, x - 6);
542 wprintw(win, "(%3d%%)", percent);
544 /* End of print_position() */
547 * Display a tree menu from file
549 * filename - file with like find(1) output
550 * FS - fields separator
551 * title - title of dialog box
552 * prompt - prompt text into dialog box
553 * height - height of dialog box
554 * width - width of dialog box
555 * menu_height - height of menu box
556 * result - pointer to char array
560 * 0 - Ok, result set (must be freed later)
564 int dialog_ftree(unsigned char *filename, unsigned char FS,
565 unsigned char *title, unsigned char *prompt,
566 int height, int width, int menu_height,
567 unsigned char **result)
569 int retcode, choice, size;
571 unsigned char **names;
573 if (mk_ftree(filename, &names, &size, FS, &items))
575 perror("dialog_ftree");
582 fprintf(stderr, "\ndialog_ftree: file %s is empty\n", filename);
587 retcode = dialog_treemenu(title, prompt, height, width, menu_height,
588 size, items, &choice, NULL, NULL);
590 free_leafs(items, size);
593 *result = free_names(names, size, choice);
595 (void)free_names(names, size, -1);
599 /* End of dialog_ftree() */
602 * Display a tree menu from array
604 * names - array with like find(1) output
605 * size - size of array
606 * FS - fields separator
607 * title - title of dialog box
608 * prompt - prompt text into dialog box
609 * height - height of dialog box
610 * width - width of dialog box
611 * menu_height - height of menu box
612 * result - pointer to char array
620 int dialog_tree(unsigned char **names, int size, unsigned char FS,
621 unsigned char *title, unsigned char *prompt,
622 int height, int width, int menu_height,
623 unsigned char **result)
627 struct saved_tree *st;
628 static struct queue *q_saved_tree = NULL;
632 fprintf(stderr, "\ndialog_tree: source array is empty\n");
637 if (mk_tree(names, size, FS, &items))
639 perror("dialog_tree");
644 /* is tree saved ? */
645 if (!(st = search_saved_tree(q_saved_tree, names,
647 height, width, menu_height))) {
650 calloc(sizeof (struct queue), 1))) {
651 perror("dialog_tree");
657 if (!(st = calloc(sizeof (struct saved_tree), 1))) {
658 perror("dialog_tree");
668 st->menu_height = menu_height;
670 if (!p2_queue(q_saved_tree, st)) {
671 perror("dialog_tree");
677 retcode = dialog_treemenu(title, prompt, height, width, menu_height,
678 size, items, &choice,
679 &(st->ch), &(st->sc));
681 free_leafs(items, size);
684 *result = names[choice];
688 /* End of dialog_tree() */
690 /* utils for ftree */
692 /* init struct queue by zeros */
694 init_queue(struct queue *queue)
696 bzero((void *)queue, sizeof(struct queue));
699 /* add pointer to queue */
700 /* return - pointer or NULL if error */
702 p2_queue(struct queue *queue, void *pointer)
709 if (!(queue->first = queue->last =
710 calloc(1, sizeof(struct m_queue))))
716 if (!(queue->last->next =
717 calloc(1, sizeof(struct m_queue))))
720 queue->last = queue->last->next;
724 return queue->last->pointer = pointer;
727 /* get first from queue */
728 /* return - pointer or NULL if queue is empty */
730 first_queue(struct queue *queue)
733 struct m_queue *new_first;
740 retval = queue->first->pointer;
741 new_first = queue->first->next;
743 queue->first = new_first;
750 /* make zero terminated array from queue */
751 /* return - pointer to array or NULL if error */
753 q2arr(struct queue *queue, int depth)
762 /* memory allocation for array */
763 if (!(mono = end = malloc(depth * sizeof(void *) + 1)))
768 if (!(*end++ = first_queue(queue)))
779 * smart_tree (for like find(1) with -d flag output compliance)
782 * NULL - malloc error
788 smart_tree(struct queue *queue,
790 unsigned char *current,
791 unsigned char *prev) {
792 unsigned char *pcurrent = current, *pprev = prev, *toqueue;
793 register char break_flag = 0;
795 while(*pcurrent && *pprev) {
796 if (*pcurrent == *pprev) {
806 if (!*pprev || break_flag) {
807 if (*pcurrent == FS) {
810 if ((!*prev) && (*pcurrent)) {
811 unsigned char tchar = *pcurrent;
814 if (!(toqueue = strdup(current))) {
818 if (!p2_queue(queue, toqueue)) {
827 if (*pcurrent == FS) {
829 if (!(toqueue = strdup(current))) {
833 if (!p2_queue(queue, toqueue)) {
841 if (!p2_queue(queue, current))
847 /* end of utils for ftree */
849 /* utils for make tree */
851 /* if error - return -1 */
854 mk_slip(struct leaf array[], int arr_size, int number, int shift)
859 if (number > arr_size - 1)
864 if (!(array[number].branches = calloc(1, t_shift + 1)))
867 (void)memset(array[number].branches, ' ', t_shift);
871 while (array[number].shift < array[t_number + 1].shift)
873 t_number = mk_slip(array, arr_size, t_number + 1, t_shift + 1);
876 if (t_number == arr_size - 1)
880 if (array[number].shift == array[t_number + 1].shift)
881 array[number].slip = '+';
883 if ((array[number].shift > array[t_number + 1].shift) ||
884 t_number == arr_size - 1)
885 array[number].slip = '`';
891 /* make tree from file
893 * filename - name of file with like find(1) output
894 * p_names - pointer to array of strings
895 * p_size - pointer to size of array
896 * FS - fields separator
897 * p_array - pointer to array of leafs
900 * 0 - ok and names by p_names, size by p_size, array by p_array set
901 * -1 - memory allocation error (errno set)
906 mk_ftree(char *filename,
907 unsigned char ***p_names, int *p_size, unsigned char FS,
908 struct leaf **p_array)
910 int NR; /* number of input records */
912 unsigned char *string, *sstring = "";
913 unsigned char **names;
917 if (!(input_file = fopen(filename, "r")))
922 if (!(string = malloc(BUFSIZ)))
925 /* read input file into queue */
926 while(fgets(string, BUFSIZ, input_file))
928 if (strchr(string, '\n'))
929 *strchr(string, '\n') = '\0';
931 if (!(string = realloc(string, strlen(string) + 1)))
934 if (!smart_tree(&queue, FS, string, sstring))
938 if (!(string = malloc(BUFSIZ)))
940 } /* read input file into queue */
942 if (fclose(input_file) == EOF)
945 if (!(NR = queue.size))
951 /* make array from queue */
952 if (!(names = (unsigned char **)q2arr(&queue, NR)))
958 /* make tree from array */
959 return mk_tree(names, NR, FS, p_array);
963 /* make tree from array
965 * names - array of strings
966 * size - size of array
967 * FS - fields separator
968 * p_array - pointer to array of leafs
971 * 0 - ok and array by p_array set
972 * -1 - memory allocation error (errno set)
977 mk_tree(unsigned char **names, int size, unsigned char FS,
978 struct leaf **p_array)
983 /* make array of leafs */
984 if (!(array = calloc(size, sizeof(struct leaf))))
988 for (i = 0; i < size; i++)
990 unsigned char *in_string, *name;
993 in_string = name = names[i];
996 if (*in_string == FS) {
997 if (!i && !*(in_string + 1))
1002 name = in_string + 1;
1007 array[i].name = name;
1008 array[i].shift = shift;
1009 array[i].slip = '\0';
1010 array[i].branches = NULL;
1014 for (i = 0;i < size; i++)
1016 i = mk_slip(array, size, i, 0);
1022 for (i = 1;i < size; i++)
1024 unsigned char *src = array[i - 1].branches;
1025 unsigned char *dst = array[i].branches;
1031 switch (array[i - 1].slip) {
1032 case '+' : *dst = '|';
1034 case '`' : *dst = ' ';
1036 } /* make branches */
1043 /* free memory from tree (leafs)
1051 free_leafs(struct leaf *array, int size)
1053 struct leaf *p_array = array;
1056 free(array++->branches);
1059 } /* free_leafs() */
1061 /* free memory from source data for tree (names)
1064 * if 0 <= choice <= size - pointer to name from names,
1065 * and memory for name not released (must be freed later)
1066 * else - NULL (recomended choice -1 for it)
1071 free_names(unsigned char **names, int size, int choice)
1073 unsigned char *retval = NULL;
1074 unsigned char **p_names = names;
1085 } /* free_names() */
1087 /* end of utils for make tree */
1089 /* static utils for saved_tree */
1091 /* search saved tree within queue */
1092 /* return - struct *saved_tree or NULL if not found */
1095 search_saved_tree(struct queue *queue, unsigned char **names, int size,
1097 int height, int width,
1100 struct m_queue *member;
1101 struct saved_tree *retval;
1103 if (!queue || !names || !FS ||
1104 !height || !width || !menu_height)
1107 if (!(member = queue->first))
1110 while (member->next) {
1111 retval = member->pointer;
1112 if ((names == retval->names) &&
1113 (size == retval->size) &&
1114 (FS == retval->FS) &&
1115 (height == retval->height) &&
1116 (width == retval->width) &&
1117 (menu_height == retval->menu_height))
1119 member = member->next;
1121 retval = member->pointer;
1122 if ((names == retval->names) &&
1123 (size == retval->size) &&
1124 (FS == retval->FS) &&
1125 (height == retval->height) &&
1126 (width == retval->width) &&
1127 (menu_height == retval->menu_height))
1132 /* end of static utils for saved_tree */