gnu/lib/libodialog/tree.c

   1 /*
   2  * tree.c -- implements the 'tree' interface element for libdialog
   3  *
   4  * Author: Anatoly A. Orehovsky (tolik@mpeks.tomsk.su)
   5  *
   6  * Copyright (c) 1997, Anatoly A. Orehovsky
   7  * 09/28/98 - patched by Anatoly A. Orehovsky (smart_tree())
   8  *
   9  */
  10
  11 #include <sys/cdefs.h>
  12 __FBSDID("$FreeBSD$");
  13
  14 #include <stdlib.h>
  15 #include <strings.h>
  16 #include <stdio.h>
  17 #include <dialog.h>
  18 #include "dialog.priv.h"
  19 #include <ncurses.h>
  20
  21 /* static utils for make tree */
  22 struct leaf {
  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 */
  27 };
  28
  29 static int      mk_slip(struct leaf array[], int arr_size,
  30                         int number, int shift);
  31
  32 /* make tree from file
  33  *
  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
  39  *
  40  * return values:
  41  * 0            - ok and names by p_names, size by p_size, array by p_array set
  42  * -1           - memory allocation error (errno set)
  43  */
  44
  45 static int      mk_ftree(char *filename,
  46                 unsigned char ***p_names, int *p_size, unsigned char FS,
  47                         struct leaf **p_array);
  48
  49 /* make tree from array
  50  *
  51  * names        - array of strings
  52  * size         - size of array
  53  * FS           - fields separator
  54  * p_array      - pointer to array of leafs
  55  *
  56  * return values:
  57  * 0            - ok and array by p_array set
  58  * -1           - memory allocation error (errno set)
  59  */
  60
  61 static int      mk_tree(unsigned char **names, int size, unsigned char FS,
  62                         struct leaf **p_array);
  63
  64 /* free memory from tree (leafs)
  65  *
  66  * return values:
  67  * nothing
  68  */
  69
  70 static void     free_leafs(struct leaf *array, int size);
  71
  72 /* free memory from source data for tree (names)
  73  *
  74  * return values:
  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)
  78  */
  79
  80 static unsigned char    *free_names(unsigned char **names,
  81                                         int size, int choice);
  82
  83 /* end of static utils for make tree */
  84
  85 /* static utils for ftree */
  86
  87 /* control struct for queue */
  88 struct queue {
  89         int size;                       /* size of queue */
  90         struct m_queue *first;          /* begin of queue */
  91         struct m_queue *last;           /* end of queue */
  92 };
  93
  94 /* queue member */
  95 struct m_queue {
  96         void *pointer;                  /* queue member */
  97         struct m_queue *next;           /* next queue member */
  98 };
  99
 100 /* init struct queue by zeros */
 101 static void     init_queue(struct queue *queue);
 102
 103 /* add pointer to queue */
 104 /* return - pointer or NULL if error */
 105 static void     *p2_queue(struct queue *queue, void *pointer);
 106
 107 /* get first from queue */
 108 /* return - pointer or NULL if queue is empty */
 109 static void     *first_queue(struct queue *queue);
 110
 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);
 114
 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);
 120
 121 /* end of static utils for ftree */
 122
 123 /* static utils for saved_tree */
 124
 125 /* saved values for unique tree */
 126 struct saved_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 */
 135 };
 136
 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,
 141                                         int size,
 142                                         unsigned char FS,
 143                                         int height,
 144                                         int width,
 145                                         int menu_height);
 146
 147 /* end of static utils for saved_tree */
 148
 149 static void print_item(WINDOW *win, struct leaf item, int choice, int selected);
 150
 151 static void print_position(WINDOW *win, int x, int y,
 152                                 int cur_pos, int size);
 153
 154 static int menu_width, item_x;
 155
 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[],
 159                                         int *result,
 160                                                 int *ch, int *sc);
 161
 162 /*
 163  * Display a menu for choosing among a number of options
 164  */
 165 static
 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[],
 169                                         int *result,
 170                                                 int *ch, int *sc)
 171 {
 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;
 175
 176   if (ch)  /* restore menu item info */
 177       choice = *ch;
 178   if (sc)
 179       scroll = *sc;
 180
 181   max_choice = MIN(menu_height, item_no);
 182
 183   item_x = 0;
 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);
 188   }
 189
 190   if (height < 0)
 191         height = strheight(prompt)+menu_height+4+2;
 192   if (width < 0) {
 193         i = strwidth(prompt);
 194         j = ((title != NULL) ? strwidth(title) : 0);
 195         width = MAX(i,j);
 196         width = MAX(width,item_x+4)+4;
 197   }
 198   width = MAX(width,24);
 199
 200   if (width > COLS)
 201         width = COLS;
 202   if (height > LINES)
 203         height = LINES;
 204   /* center dialog box on screen */
 205   x = (COLS - width)/2;
 206   y = (LINES - height)/2;
 207
 208 #ifdef HAVE_NCURSES
 209   if (use_shadow)
 210     draw_shadow(stdscr, y, x, height, width);
 211 #endif
 212   dialog = newwin(height, width, y, x);
 213   if (dialog == NULL) {
 214     endwin();
 215     fprintf(stderr, "\nnewwin(%d,%d,%d,%d) failed, maybe wrong dims\n", height,width,y,x);
 216     exit(1);
 217   }
 218   keypad(dialog, TRUE);
 219
 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++)
 230     waddch(dialog, ' ');
 231
 232   if (title != NULL) {
 233     wattrset(dialog, title_attr);
 234     wmove(dialog, 0, (width - strlen(title))/2 - 1);
 235     waddch(dialog, ' ');
 236     waddstr(dialog, title);
 237     waddch(dialog, ' ');
 238   }
 239   wattrset(dialog, dialog_attr);
 240   wmove(dialog, 1, 2);
 241   print_autowrap(dialog, prompt, height-1, width-2, width, 1, 2, TRUE, FALSE);
 242
 243   menu_width = width-6;
 244   getyx(dialog, cur_y, cur_x);
 245   box_y = cur_y + 1;
 246   box_x = (width - menu_width)/2 - 1;
 247
 248   /* create new window for the menu */
 249   menu = subwin(dialog, menu_height, menu_width, y + box_y + 1, x + box_x + 1);
 250   if (menu == NULL) {
 251     endwin();
 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);
 253     exit(1);
 254   }
 255   keypad(menu, TRUE);
 256
 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);
 259
 260   item_x = 1;
 261
 262   /* Print the menu */
 263   for (i = 0; i < max_choice; i++)
 264     print_item(menu, items[(scroll+i)], i, i == choice);
 265   wnoutrefresh(menu);
 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);
 268
 269   display_helpline(dialog, height-1, width);
 270
 271   x = width/2-11;
 272   y = height-2;
 273   print_button(dialog, "Cancel", y, x+14, FALSE);
 274   print_button(dialog, "  OK  ", y, x, TRUE);
 275
 276   wrefresh(dialog);
 277
 278   while (key != ESC) {
 279     key = wgetch(dialog);
 280     /* Check if key pressed matches first character of any item tag in menu */
 281
 282     if (key == KEY_UP || key == KEY_DOWN || key == '-' || key == '+') {
 283      if (key == KEY_UP || key == '-') {
 284         if (!choice) {
 285           if (scroll) {
 286 #ifdef BROKEN_WSCRL
 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
 289        used for now */
 290             scroll--;
 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);
 295
 296 #else
 297
 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);
 304               wscrl(menu, -1);
 305               scrollok(menu, FALSE);
 306             }
 307             scroll--;
 308             print_item(menu, items[scroll], 0, TRUE);
 309 #endif
 310             wnoutrefresh(menu);
 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 */
 314             wrefresh(dialog);
 315           }
 316           continue;    /* wait for another key press */
 317         }
 318         else
 319           i = choice - 1;
 320       }
 321       else if (key == KEY_DOWN || key == '+') {
 322         if (choice == max_choice - 1) {
 323           if (scroll+choice < item_no-1) {
 324 #ifdef BROKEN_WSCRL
 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
 327        used for now */
 328             scroll++;
 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);
 333
 334 #else
 335
 336             /* Scroll menu up */
 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);
 342               scroll(menu);
 343               scrollok(menu, FALSE);
 344             }
 345             scroll++;
 346               print_item(menu, items[(scroll+max_choice-1)], max_choice-1, TRUE);
 347 #endif
 348             wnoutrefresh(menu);
 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 */
 352             wrefresh(dialog);
 353           }
 354           continue;    /* wait for another key press */
 355         }
 356         else
 357           i = choice + 1;
 358       }
 359
 360       if (i != choice) {
 361         /* De-highlight current item */
 362         getyx(dialog, cur_y, cur_x);    /* Save cursor position */
 363         print_item(menu, items[(scroll+choice)], choice, FALSE);
 364
 365         /* Highlight new item */
 366         choice = i;
 367         print_item(menu, items[(scroll+choice)], choice, TRUE);
 368         wnoutrefresh(menu);
 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 */
 371         wrefresh(dialog);
 372       }
 373       continue;    /* wait for another key press */
 374     }
 375
 376     /* save info about menu item position */
 377     if (ch)
 378         *ch = choice;
 379     if (sc)
 380         *sc = scroll;
 381
 382     switch (key) {
 383     case KEY_PPAGE:
 384     case 'B' :
 385     case 'b' :
 386         if (scroll > menu_height) {     /* can we go up? */
 387             scroll -= (menu_height);
 388         } else {
 389             scroll = 0;
 390         }
 391         redraw_menu = TRUE;
 392         break;
 393     case KEY_NPAGE:
 394     case 'F' :
 395     case 'f' :
 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;
 399         } else {
 400             scroll += menu_height;
 401         }
 402         redraw_menu = TRUE;
 403         break;
 404     case KEY_HOME:
 405     case 'g' :
 406         scroll = 0;
 407         choice = 0;
 408         redraw_menu = TRUE;
 409         break;
 410     case KEY_END:
 411     case 'G' :
 412         scroll = item_no - menu_height;
 413         if (scroll < 0) scroll = 0;
 414         choice = max_choice - 1;
 415         redraw_menu = TRUE;
 416         break;
 417     case 'O':
 418     case 'o':
 419         delwin(dialog);
 420         *result = scroll+choice;
 421         return 0;
 422     case 'C':
 423     case 'c':
 424         delwin(dialog);
 425         return 1;
 426     case KEY_BTAB:
 427     case TAB:
 428     case KEY_LEFT:
 429     case KEY_RIGHT:
 430         if (!button) {
 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);
 434         }
 435         else {
 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);
 439         }
 440         wrefresh(dialog);
 441         break;
 442     case ' ':
 443     case '\r':
 444     case '\n':
 445         delwin(dialog);
 446         if (!button)
 447           *result = scroll+choice;
 448         return button;
 449     case ESC:
 450         break;
 451     case KEY_F(1):
 452     case '?':
 453         display_helpfile();
 454         break;
 455     }
 456     if (redraw_menu) {
 457         for (i = 0; i < max_choice; i++) {
 458             print_item(menu, items[(scroll+i)],
 459                        i, i == choice);
 460         }
 461         wnoutrefresh(menu);
 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 */
 466         wrefresh(dialog);
 467         redraw_menu = FALSE;
 468     }
 469   }
 470
 471   delwin(dialog);
 472   return -1;    /* ESC pressed */
 473 }
 474 /* End of dialog_treemenu() */
 475
 476
 477 /*
 478  * Print menu item
 479  */
 480 static void print_item(WINDOW *win, struct leaf item, int choice, int selected)
 481 {
 482   int i, j = menu_width - 2;
 483   char *branches = item.branches;
 484
 485   /* Clear 'residue' of last item */
 486   wattrset(win, menubox_attr);
 487   wmove(win, choice, 0);
 488   for (i = 0; i < menu_width; i++)
 489     waddch(win, ' ');
 490   wmove(win, choice, item_x);
 491
 492   while(*branches && j)
 493   {
 494         switch (*branches++) {
 495         case ' ' : waddch(win, ' ');
 496                 break;
 497         case '|' : waddch(win, ACS_VLINE);
 498         }
 499
 500         j--;
 501         i = 3;
 502         while(i-- && j)
 503         {
 504                 waddch(win, ' ');
 505                 j--;
 506         }
 507   }
 508
 509   if (j)
 510   {
 511           switch (item.slip) {
 512           case '+' : waddch(win, ACS_LTEE);
 513                 break;
 514           case '`' : waddch(win, ACS_LLCORNER);
 515           }
 516           j--;
 517   }
 518
 519   i = 3;
 520   while(i-- && j)
 521   {
 522         waddch(win, ACS_HLINE);
 523         j--;
 524   }
 525
 526   wattrset(win, selected ? item_selected_attr : item_attr);
 527   if (j)
 528           waddnstr(win, item.name, j);
 529 }
 530 /* End of print_item() */
 531
 532 /*
 533  * Print current position
 534  */
 535 static void print_position(WINDOW *win, int x, int y,
 536                                         int cur_pos, int size)
 537 {
 538   int percent;
 539
 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);
 544 }
 545 /* End of print_position() */
 546
 547 /*
 548  * Display a tree menu from file
 549  *
 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
 558  *
 559  * return values:
 560  * -1           - ESC pressed
 561  * 0            - Ok, result set (must be freed later)
 562  * 1            - Cancel
 563  */
 564
 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)
 569 {
 570         int retcode, choice, size;
 571         struct leaf *items;
 572         unsigned char **names;
 573
 574         if (mk_ftree(filename, &names, &size, FS, &items))
 575         {
 576                 perror("dialog_ftree");
 577                 end_dialog();
 578                 exit(-1);
 579         }
 580
 581         if (!size)
 582         {
 583                 fprintf(stderr, "\ndialog_ftree: file %s is empty\n", filename);
 584                 end_dialog();
 585                 exit(-1);
 586         }
 587
 588         retcode = dialog_treemenu(title, prompt, height, width, menu_height,
 589                                         size, items, &choice, NULL, NULL);
 590
 591         free_leafs(items, size);
 592
 593         if (!retcode)
 594                 *result = free_names(names, size, choice);
 595         else
 596                 (void)free_names(names, size, -1);
 597
 598         return retcode;
 599 }
 600 /* End of dialog_ftree() */
 601
 602 /*
 603  * Display a tree menu from array
 604  *
 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
 614  *
 615  * return values:
 616  * -1           - ESC pressed
 617  * 0            - Ok, result set
 618  * 1            - Cancel
 619  */
 620
 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)
 625 {
 626         int retcode, choice;
 627         struct leaf *items;
 628         struct saved_tree *st;
 629         static struct queue *q_saved_tree = NULL;
 630
 631         if (!size)
 632         {
 633                 fprintf(stderr, "\ndialog_tree: source array is empty\n");
 634                 end_dialog();
 635                 exit(-1);
 636         }
 637
 638         if (mk_tree(names, size, FS, &items))
 639         {
 640                 perror("dialog_tree");
 641                 end_dialog();
 642                 exit(-1);
 643         }
 644
 645 /* is tree saved ? */
 646         if (!(st = search_saved_tree(q_saved_tree, names,
 647                                         size, FS,
 648                                         height, width, menu_height))) {
 649                 if (!q_saved_tree) {
 650                         if (!(q_saved_tree =
 651                                 calloc(sizeof (struct queue), 1))) {
 652                                 perror("dialog_tree");
 653                                 end_dialog();
 654                                 exit(-1);
 655                         }
 656                 }
 657
 658                 if (!(st = calloc(sizeof (struct saved_tree), 1))) {
 659                         perror("dialog_tree");
 660                         end_dialog();
 661                         exit(-1);
 662                 }
 663
 664                 st->names = names;
 665                 st->size = size;
 666                 st->FS = FS;
 667                 st->height = height;
 668                 st->width = width;
 669                 st->menu_height = menu_height;
 670
 671                 if (!p2_queue(q_saved_tree, st)) {
 672                         perror("dialog_tree");
 673                         end_dialog();
 674                         exit(-1);
 675                 }
 676         }
 677
 678         retcode = dialog_treemenu(title, prompt, height, width, menu_height,
 679                                         size, items, &choice,
 680                                         &(st->ch), &(st->sc));
 681
 682         free_leafs(items, size);
 683
 684         if (!retcode)
 685                 *result = names[choice];
 686
 687         return retcode;
 688 }
 689 /* End of dialog_tree() */
 690
 691 /* utils for ftree */
 692
 693 /* init struct queue by zeros */
 694 static void
 695 init_queue(struct queue *queue)
 696 {
 697         bzero((void *)queue, sizeof(struct queue));
 698 }
 699
 700 /* add pointer to queue */
 701 /* return - pointer or NULL if error */
 702 static void     *
 703 p2_queue(struct queue *queue, void *pointer)
 704 {
 705         if (!queue)
 706                 return NULL;
 707
 708         if (!queue->first)
 709         {
 710                 if (!(queue->first = queue->last =
 711                         calloc(1, sizeof(struct m_queue))))
 712                                 return NULL;
 713
 714         }
 715         else
 716         {
 717         if (!(queue->last->next =
 718                         calloc(1, sizeof(struct m_queue))))
 719                                 return NULL;
 720
 721         queue->last = queue->last->next;
 722         }
 723
 724         queue->size++;
 725         return queue->last->pointer = pointer;
 726 }
 727
 728 /* get first from queue */
 729 /* return - pointer or NULL if queue is empty */
 730 static void     *
 731 first_queue(struct queue *queue)
 732 {
 733         void *retval;
 734         struct m_queue *new_first;
 735
 736         if (!queue ||
 737                 !queue->first ||
 738                         !queue->size)
 739                                 return NULL;
 740
 741         retval = queue->first->pointer;
 742         new_first = queue->first->next;
 743         free(queue->first);
 744         queue->first = new_first;
 745         queue->size--;
 746
 747         return retval;
 748
 749 }
 750
 751 /* make zero terminated array from queue */
 752 /* return - pointer to array or NULL if error */
 753 static void     **
 754 q2arr(struct queue *queue, int depth)
 755 {
 756         void **mono, **end;
 757
 758         if (!queue ||
 759                 !queue->first ||
 760                         !queue->size)
 761                         return NULL;
 762
 763         /* memory allocation for array */
 764         if (!(mono = end = malloc(depth * sizeof(void *) + 1)))
 765                 return NULL;
 766
 767         while(depth--)
 768         {
 769                 if (!(*end++ = first_queue(queue)))
 770                         break;
 771         }
 772
 773         *end = NULL;
 774
 775         return mono;
 776
 777 }
 778
 779 /*
 780  * smart_tree (for like find(1) with -d flag output compliance)
 781  *
 782  * return values:
 783  * NULL - malloc error
 784  * not NULL - ok
 785  *
 786  */
 787 static
 788 unsigned char *
 789 smart_tree(struct queue *queue,
 790                 unsigned char FS,
 791                 unsigned char *current,
 792                 unsigned char *prev) {
 793         unsigned char *pcurrent = current, *pprev = prev, *toqueue;
 794         register char break_flag = 0;
 795
 796         while(*pcurrent && *pprev) {
 797                 if (*pcurrent == *pprev) {
 798                         pcurrent++;
 799                         pprev++;
 800                 }
 801                 else {
 802                         break_flag = 1;
 803                         break;
 804                 }
 805         }
 806
 807         if (!*pprev || break_flag) {
 808                 if (*pcurrent == FS) {
 809                         pcurrent++;
 810
 811                         if ((!*prev) && (*pcurrent)) {
 812                                 unsigned char tchar = *pcurrent;
 813
 814                                 *pcurrent = '\0';
 815                                 if (!(toqueue = strdup(current))) {
 816                                         *pcurrent = tchar;
 817                                         return NULL;
 818                                 }
 819                                 if (!p2_queue(queue, toqueue)) {
 820                                         *pcurrent = tchar;
 821                                         return NULL;
 822                                 }
 823                                 *pcurrent = tchar;
 824                         }
 825                 }
 826
 827                 while(*pcurrent) {
 828                         if (*pcurrent == FS) {
 829                                 *pcurrent = '\0';
 830                                 if (!(toqueue = strdup(current))) {
 831                                         *pcurrent = FS;
 832                                         return NULL;
 833                                 }
 834                                 if (!p2_queue(queue, toqueue)) {
 835                                         *pcurrent = FS;
 836                                         return NULL;
 837                                 }
 838                                 *pcurrent = FS;
 839                         }
 840                         pcurrent++;
 841                 }
 842                 if (!p2_queue(queue, current))
 843                         return NULL;
 844         }
 845         return current;
 846 }
 847
 848 /* end of utils for ftree */
 849
 850 /* utils for make tree */
 851
 852 /* if error - return -1 */
 853 static
 854 int
 855 mk_slip(struct leaf array[], int arr_size, int number, int shift)
 856 {
 857         int t_number;
 858         int t_shift;
 859
 860         if (number > arr_size - 1)
 861                 return number - 1;
 862
 863         t_shift = shift;
 864
 865         if (!(array[number].branches = calloc(1, t_shift + 1)))
 866                         return -1;
 867
 868         (void)memset(array[number].branches, ' ', t_shift);
 869
 870         t_number = number;
 871
 872         while (array[number].shift < array[t_number + 1].shift)
 873         {
 874                 t_number = mk_slip(array, arr_size, t_number + 1, t_shift + 1);
 875                 if (t_number < 0)
 876                                 return -1;
 877                 if (t_number == arr_size - 1)
 878                                 break;
 879         }
 880
 881         if (array[number].shift == array[t_number + 1].shift)
 882                 array[number].slip = '+';
 883
 884         if ((array[number].shift > array[t_number + 1].shift) ||
 885                                 t_number == arr_size - 1)
 886                 array[number].slip = '`';
 887
 888         return t_number;
 889
 890 } /* mk_slip() */
 891
 892 /* make tree from file
 893  *
 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
 899  *
 900  * return values:
 901  * 0            - ok and names by p_names, size by p_size, array by p_array set
 902  * -1           - memory allocation error (errno set)
 903  */
 904
 905 static
 906 int
 907 mk_ftree(char *filename,
 908         unsigned char ***p_names, int *p_size, unsigned char FS,
 909                 struct leaf **p_array)
 910 {
 911         int NR; /* number of input records */
 912         struct queue queue;
 913         unsigned char *string, *sstring = "";
 914         unsigned char **names;
 915
 916         FILE *input_file;
 917
 918         if (!(input_file = fopen(filename, "r")))
 919                                 return -1;
 920
 921         init_queue(&queue);
 922
 923         if (!(string = malloc(BUFSIZ)))
 924                         return -1;
 925
 926         /* read input file into queue */
 927         while(fgets(string, BUFSIZ, input_file))
 928         {
 929                 if (strchr(string, '\n'))
 930                         *strchr(string, '\n') = '\0';
 931
 932                 if (!(string = realloc(string, strlen(string) + 1)))
 933                                 return -1;
 934
 935                 if (!smart_tree(&queue, FS, string, sstring))
 936                                 return -1;
 937                 sstring = string;
 938
 939                 if (!(string = malloc(BUFSIZ)))
 940                                 return -1;
 941         } /* read input file into queue */
 942
 943         if (fclose(input_file) == EOF)
 944                         return -1;
 945
 946         if (!(NR = queue.size))
 947         {
 948                 *p_size = 0;
 949                 return 0;
 950         }
 951
 952         /* make array from queue */
 953         if (!(names = (unsigned char **)q2arr(&queue, NR)))
 954                         return -1;
 955
 956         *p_names = names;
 957         *p_size = NR;
 958
 959         /* make tree from array */
 960         return mk_tree(names, NR, FS, p_array);
 961
 962 } /* mk_ftree */
 963
 964 /* make tree from array
 965  *
 966  * names        - array of strings
 967  * size         - size of array
 968  * FS           - fields separator
 969  * p_array      - pointer to array of leafs
 970  *
 971  * return values:
 972  * 0            - ok and array by p_array set
 973  * -1           - memory allocation error (errno set)
 974  */
 975
 976 static
 977 int
 978 mk_tree(unsigned char **names, int size, unsigned char FS,
 979                 struct leaf **p_array)
 980 {
 981         int i;
 982         struct leaf *array;
 983
 984         /* make array of leafs */
 985         if (!(array = calloc(size, sizeof(struct leaf))))
 986                         return -1;
 987
 988         /* init leafs */
 989         for (i = 0; i < size; i++)
 990         {
 991                 unsigned char *in_string, *name;
 992                 int shift = 0;
 993
 994                 in_string = name = names[i];
 995                 while(*in_string)
 996                 {
 997                         if (*in_string == FS) {
 998                                 if (!i && !*(in_string + 1))
 999                                         name = in_string;
1000                                 else
1001                                 {
1002                                         shift++;
1003                                         name = in_string + 1;
1004                                 }
1005                         }
1006                         in_string++;
1007                 }
1008                 array[i].name = name;
1009                 array[i].shift = shift;
1010                 array[i].slip = '\0';
1011                 array[i].branches = NULL;
1012         } /* init leafs */
1013
1014         /* make slips */
1015         for (i = 0;i < size; i++)
1016         {
1017                 i = mk_slip(array, size, i, 0);
1018                 if (i < 0)
1019                         return -1;
1020         } /* make slips */
1021
1022         /* make branches */
1023         for (i = 1;i < size; i++)
1024         {
1025                 unsigned char *src = array[i - 1].branches;
1026                 unsigned char *dst = array[i].branches;
1027
1028                 while(*src && *dst)
1029                         *dst++ = *src++;
1030
1031                 if (*dst)
1032                         switch (array[i - 1].slip) {
1033                         case '+' : *dst = '|';
1034                                 break;
1035                         case '`' : *dst = ' ';
1036                         }
1037         } /* make branches */
1038
1039         *p_array = array;
1040         return 0;
1041
1042 } /* mk_tree() */
1043
1044 /* free memory from tree (leafs)
1045  *
1046  * return values:
1047  * nothing
1048  */
1049
1050 static
1051 void
1052 free_leafs(struct leaf *array, int size)
1053 {
1054         struct leaf *p_array = array;
1055
1056         while (size--)
1057                 free(array++->branches);
1058
1059         free(p_array);
1060 } /* free_leafs() */
1061
1062 /* free memory from source data for tree (names)
1063  *
1064  * return values:
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)
1068  */
1069
1070 static
1071 unsigned char *
1072 free_names(unsigned char **names, int size, int choice)
1073 {
1074         unsigned char *retval = NULL;
1075         unsigned char **p_names = names;
1076
1077         while (size--)
1078         {
1079                 if (!choice--)
1080                         retval = *names++;
1081                 else
1082                         free(*names++);
1083         }
1084         free(p_names);
1085         return retval;
1086 } /* free_names() */
1087
1088 /* end of utils for make tree */
1089
1090 /* static utils for saved_tree */
1091
1092 /* search saved tree within queue */
1093 /* return - struct *saved_tree or NULL if not found */
1094 static
1095 struct saved_tree *
1096 search_saved_tree(struct queue *queue, unsigned char **names, int size,
1097                                         unsigned char FS,
1098                                         int height, int width,
1099                                         int menu_height)
1100 {
1101         struct m_queue *member;
1102         struct saved_tree *retval;
1103
1104         if (!queue || !names || !FS ||
1105                 !height || !width || !menu_height)
1106                 return NULL;
1107
1108         if (!(member = queue->first))
1109                 return NULL;
1110
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))
1119                         return retval;
1120                 member = member->next;
1121         }
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))
1129                 return retval;
1130         return NULL;
1131 }
1132
1133 /* end of static utils for saved_tree */