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