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