home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Guide / c-cplusplus-interactive-guide.iso / c_ref / csource3 / 165_01 / source.d < prev    next >
C/C++ Source or Header  |  1988-02-19  |  111KB  |  4,392 lines
  1. ###acd_menu.c
  2. /* acd_menu - PART MENU */
  3. #include "local.h"
  4. #include "menu.h"
  5. #include "part.h"
  6. extern bool addpart();
  7. extern bool chgpart();
  8. extern bool delpart();
  9. static FIELD Facd_menu[] =
  10.     {
  11.     {2, 0, "Add a part record", 'f', NULL, NULL, NULL, addpart},
  12.     {4, 0, "Change a part record", 'f', NULL, NULL, NULL, chgpart},
  13.     {6, 0, "Delete a part record", 'f', NULL, NULL, NULL, delpart},
  14.     };
  15. MENU acd_menu = {"PART MENU", Facd_menu, DIM(Facd_menu), 0};
  16. ###acd_menu.mu
  17. Menu name:  acd_menu    Menu title: PART MENU
  18.     Header: part.h        C-struct: part1
  19.  
  20. Field name: 0     Desc: Add a part record
  21.     Line: 2 Col: 0     Type: f              Post-fn: addpart
  22.  
  23. Field name: 0     Desc: Change a part record
  24.     Line: 4 Col: 0     Type: f              Post-fn: chgpart
  25.  
  26. Field name: 0     Desc: Delete a part record
  27.     Line: 6 Col: 0     Type: f              Post-fn: delpart
  28. ###add_menu.c
  29. /* add_menu - ADD A PART RECORD */
  30. #include "local.h"
  31. #include "menu.h"
  32. #include "part.h"
  33. extern bool isn_part();
  34. static STRING_VAL Spart_no =
  35.     {'a', (part1).part_no, sizeof((part1).part_no), NULL};
  36. static STRING_VAL Slead_time =
  37.     {'n', (part1).lead_time, sizeof((part1).lead_time), NULL};
  38. static char *Tunit_meas[]=
  39.     
  40.     {
  41.     "each", "lb", "box",
  42.     };
  43. static CHOICE_VAL Cunit_meas =
  44.     {DIM(Tunit_meas), Tunit_meas, (part1).unit_meas};
  45. static STRING_VAL Sunit_cost =
  46.     {'a', (part1).unit_cost, sizeof((part1).unit_cost), NULL};
  47. static STRING_VAL Scost_qty =
  48.     {'n', (part1).cost_qty, sizeof((part1).cost_qty), NULL};
  49. static FIELD Fadd_menu[] =
  50.     {
  51.     {2, 0, "Part number", 'S', &Spart_no, NULL, NULL, isn_part},
  52.     {4, 0, "Lead time (in weeks)", 's', &Slead_time, NULL, NULL, 0},
  53.     {6, 0, "Unit of measure", 'c', NULL, &Cunit_meas, NULL, 0},
  54.     {8, 0, "Cost per unit", 's', &Sunit_cost, NULL, NULL, 0},
  55.     {10, 0, "Qty required for price", 's', &Scost_qty, NULL, NULL, 0},
  56.     };
  57. MENU add_menu = {"ADD A PART RECORD", Fadd_menu, DIM(Fadd_menu), 0};
  58. ###add_menu.mu
  59. Menu name: add_menu    Menu title: ADD A PART RECORD
  60.     Header: part.h        C-struct: part1
  61.  
  62. Field name: part_no    Desc: Part number
  63.     Line: 2 Col: 0     Type: S     Edit: a     Post-fn: isn_part    
  64.  
  65. Field name: lead_time    Desc: Lead time (in weeks)
  66.     Line: 4 Col: 0     Type: s     Edit: n     Post-fn: 0    
  67.  
  68. Field name: unit_meas    Desc: Unit of measure
  69.     Line: 6 Col: 0     Type: c     Post-fn: 0    
  70.     {
  71.     "each", "lb", "box",
  72.     };
  73.  
  74. Field name: unit_cost    Desc: Cost per unit
  75.     Line: 8 Col: 0     Type: s     Edit: a     Post-fn: 0    
  76.  
  77. Field name: cost_qty    Desc: Qty required for price
  78.     Line: 10 Col: 0     Type: s     Edit: n     Post-fn: 0    
  79. ###args.c
  80. /* args - show command-line arguments, one line each
  81.  */
  82. #include "local.h"
  83. main(ac, av)
  84.     int ac;
  85.     char *av[];
  86.     {
  87.     int i;
  88.  
  89.     for (i = 0; i < ac; ++i)
  90.         printf("av[%d]=<%s>\n", i, av[i]);
  91.     }
  92. ###atopi(#1).c
  93. /* atopi - convert string to positive integer */
  94. int atopi(s)
  95.     char s[];
  96.     {
  97.     int n = 0;
  98.     int i;
  99.  
  100.     for (i = 0; isdigit(s[i]); ++i)
  101.         n = 10 * n + s[i] - '0';
  102.     return (n);
  103.     }
  104. ###atopi(#2).c
  105. /* atopi - convert string to positive integer {0:INT_MAX} */
  106. #include <limits.h>
  107. int atopi(s)
  108.     char s[];
  109.     {
  110.     unsigned n = 0;    /* the converted number: {0:INT_MAX} */
  111.     int i;
  112.  
  113.     for (i = 0; isdigit(s[i]) && n <= INT_MAX/10; ++i)
  114.         {
  115.         if (n > INT_MAX / 10)
  116.             return (-1);
  117.         n = 10 * n + (s[i] - '0');
  118.         }
  119.     if (n > INT_MAX || isdigit(s[i]))
  120.         return (-1);
  121.     else
  122.         return (n);
  123.     }
  124. ###chg_menu.c
  125. /* chg_menu - CHANGE A PART RECORD */
  126. #include "local.h"
  127. #include "menu.h"
  128. #include "part.h"
  129. extern bool is_part();
  130. static STRING_VAL Spart_no =
  131.     {'a', (part1).part_no, sizeof((part1).part_no), NULL};
  132. static STRING_VAL Slead_time =
  133.     {'n', (part1).lead_time, sizeof((part1).lead_time), NULL};
  134. static char *Tunit_meas[]=
  135.     {
  136.     "each", "lb", "box",
  137.     };
  138. static CHOICE_VAL Cunit_meas =
  139.     {DIM(Tunit_meas), Tunit_meas, (part1).unit_meas};
  140. static STRING_VAL Sunit_cost =
  141.     {'a', (part1).unit_cost, sizeof((part1).unit_cost), NULL};
  142. static STRING_VAL Scost_qty =
  143.     {'n', (part1).cost_qty, sizeof((part1).cost_qty), NULL};
  144. static FIELD Fchg_menu[] =
  145.     {
  146.     {2, 0, "Part number", 'S', &Spart_no, NULL, NULL, is_part},
  147.     {4, 0, "Lead time (in weeks)", 's', &Slead_time, NULL, NULL, 0},
  148.     {6, 0, "Unit of measure", 'c', NULL, &Cunit_meas, NULL, 0},
  149.     {8, 0, "Cost per unit", 's', &Sunit_cost, NULL, NULL, 0},
  150.     {10, 0, "Qty required for price", 's', &Scost_qty, NULL, NULL, 0},
  151.     };
  152. MENU chg_menu = {"CHANGE A PART RECORD", Fchg_menu, DIM(Fchg_menu), 0};
  153. ###chg_menu.mu
  154. Menu name: chg_menu    Menu title: CHANGE A PART RECORD
  155.     Header: part.h        C-struct: part1    
  156.  
  157. Field name: part_no    Desc: Part number
  158.     Line: 2 Col: 0     Type: S     Edit: a     Post-fn: is_part
  159.  
  160. Field name: lead_time    Desc: Lead time (in weeks)
  161.     Line: 4 Col: 0     Type: s     Edit: n     Post-fn: 0
  162.  
  163. Field name: unit_meas    Desc: Unit of measure
  164.     Line: 6 Col: 0     Type: c              Post-fn: 0
  165.     {
  166.     "each", "lb", "box",
  167.     };
  168.  
  169. Field name: unit_cost    Desc: Cost per unit
  170.     Line: 8 Col: 0     Type: s     Edit: a     Post-fn: 0
  171.  
  172. Field name: cost_qty    Desc: Qty required for price
  173.     Line: 10 Col: 0     Type: s     Edit: n     Post-fn: 0
  174. ###cpystr.c
  175. /* cpystr - copy several source strings into one destination string
  176.  * NOT UNIVERSALLY PORTABLE: assumes argument stack layout
  177.  */
  178. #include "local.h"
  179. char *cpystr(olddest, s)
  180.     char *olddest;
  181.     char *s;
  182.     {
  183.     char **ps;
  184.     register char *dest = olddest;
  185.     register char *src;
  186.  
  187.     ps = &s + 1;    /* no range limits! */
  188.     for (src = s; src != NULL; src = *ps++)
  189.         while (*src != '\0')
  190.             *dest++ = *src++;
  191.     *dest = '\0';
  192.     return (olddest);
  193.     }
  194. ###cpystrm.c
  195. #include "cpystr.c"
  196. main()
  197.     {
  198.     char buf[BUFSIZ];
  199.  
  200.     cpystr(buf, "ab", "c", "de", NULL);
  201.     printf("<%s>\n", buf);
  202.     }
  203. ###crhash.c
  204. /* crhash -- create and initialize an empty hash file
  205.  *        used to hold part database records
  206.  */
  207. #include "local.h"
  208. #include "part.h"
  209. #include "rec_io.h"
  210.  
  211. main(ac, av)
  212.     int ac;
  213.     char *av[];
  214.     {
  215.     rec_fd fd;            /* record file descriptor */
  216.     short size;            /* size of one record in created file */
  217.     long nrecs;            /* maximum numbers of records in created file */
  218.     char *buf;            /* data to init. each record */
  219.     long i;                /* counter to write records in created file */
  220.  
  221.     if (ac != 4)
  222.         error("usage: crhash filename nrecs recsize", "");
  223.  
  224.     nrecs = atol(av[2]);
  225.     size = atoi(av[3]);
  226.     fd = rec_open(av[1], O_RDONLY, size);
  227.     if (fd > 0)
  228.         {
  229.         rec_close(fd);
  230.         error("file already exists:", av[1]);
  231.         }
  232.  
  233.     fd = rec_open(av[1], O_RDWR|O_CREAT, size);
  234.     if (fd < 0)
  235.         error("can't create file", av[1]);
  236.  
  237.     buf = (char *)calloc(size, 1);
  238.     if (buf == NULL)
  239.         error("Need more heap space to allow size =", av[3]);
  240.     *buf = REC_AVAIL;
  241.     /* file was created ok, initialize file */
  242.     for (i = 0; i < nrecs; ++i)
  243.         {
  244.         if (!rec_put(fd, buf, REC_W_END))
  245.             error("I/O error writing new file", "");
  246.         }
  247.     rec_close(fd);
  248.     exit(SUCCEED);
  249.     }
  250. ###dangling.c
  251. /* dangling - example of dangling pointer
  252.  */
  253. #include "local.h"
  254. static short *pi = NULL;
  255. main()
  256.     {
  257.     void f1();
  258.  
  259.                 /* pi => NULL initially */
  260.     f1();        /* pi => undefined suddenly! */
  261.     }
  262. void f1()
  263.     {
  264.     short i;
  265.  
  266.     pi = &i;    /* pi => complete,  momentarily */
  267.     }
  268. ###del_menu.c
  269. /* del_menu - DELETE A PART RECORD */
  270. #include "local.h"
  271. #include "menu.h"
  272. #include "part.h"
  273. extern bool is_part();
  274. static STRING_VAL Spart_no =
  275.     {'a', (part1).part_no, sizeof((part1).part_no), NULL};
  276. static FIELD Fdel_menu[] =
  277.     {
  278.     {2, 0, "Part number", 'S', &Spart_no, NULL, NULL, is_part},
  279.     };
  280. MENU del_menu = {"DELETE A PART RECORD", Fdel_menu, DIM(Fdel_menu), 0};
  281. ###del_menu.mu
  282. Menu name: del_menu    Menu title: DELETE A PART RECORD
  283.     Header: part.h        C-struct: part1
  284.  
  285. Field name: part_no    Desc: Part number
  286.     Line: 2 Col: 0     Type: S     Edit: a     Post-fn: is_part
  287.  
  288. ###dq_close.c
  289. /* dq_close - close a deque  */
  290. #include "deque.h"
  291. void dq_close(pdq)
  292.     DQ_NODE **pdq;    /* ptr to ptr to master DQ_NODE */
  293.     {
  294.     DQ_NODE *p;
  295.     DQ_NODE *pnext;
  296.  
  297.     for (p = (*pdq)->right; p != (*pdq); p = pnext)
  298.         {
  299.         pnext = p->right;
  300.         free(p);
  301.         }
  302.     free(*pdq);
  303.     *pdq = NULL;
  304.     }
  305. ###dq_detach.c
  306. /* dq_detach - detach node d from deque */
  307. #include "deque.h"
  308. DQ_NODE *dq_detach(dq, d)
  309.     DQ_NODE *dq;
  310.     DQ_NODE *d;
  311.     {
  312.     DQ_NODE *p;
  313.     DQ_NODE *q;
  314.  
  315.     if (d == dq)
  316.         return (NULL);
  317.     q = d->right;
  318.     p = d->left;
  319.     p->right = q;
  320.     q->left = p;
  321.     return (d);
  322.     }
  323. ###dq_find.c
  324. /* dq_find - search deque for equal match to d, return ptr to match
  325.  * Return NULL if no match
  326.  */
  327. #include "deque.h"
  328. DQ_NODE *dq_find(dq, d, cmpfn)
  329.     DQ_NODE *dq;
  330.     DQ_NODE *d;
  331.     int (*cmpfn)();                        /*function for comparisons */
  332.     {
  333.     DQ_NODE *d2;
  334.  
  335.     EACH_DQ(dq, d2, DQ_NODE)
  336.         if ((*cmpfn)(d2, d) == 0)
  337.             return (d2);
  338.     return (NULL);
  339.     }
  340. ###dq_first.c
  341. /* dq_first - produce ptr to first deque node, otherwise NULL */
  342. #include "deque.h"
  343. DQ_NODE *dq_first(dq)
  344.     DQ_NODE *dq;
  345.     {
  346.     if (dq->right == dq)
  347.         return (NULL);
  348.     return (dq->right);
  349.     }
  350. ###dq_insert.c
  351. /* dq_insert - install DQ_NODE at proper place in deque */
  352. #include "deque.h"
  353. void dq_insert(dq, p, cmpfn)
  354.     DQ_NODE *dq;
  355.     DQ_NODE *p;
  356.     int (*cmpfn)();        /* function for comparisons: neg, zero, or pos */
  357.     {
  358.     DQ_NODE *p2;
  359.  
  360.     if (DQ_IS_EMPTY(dq)                /* if deque was empty, */
  361.         || (*cmpfn)(p, DQ_FIRST(dq)) < 0) /* or if p comes first, */
  362.         DQ_PUSH(dq, p);                /* push p onto front */
  363.     else                            /* else, p must sort after p2 */
  364.         {
  365.         EACH_DQ(dq, p2, DQ_NODE)    /* find where p belongs */
  366.             {
  367.             if (p2->right == dq)
  368.                 {                     /* if end of deque, */
  369.                 DQ_APPEND(dq, p);    /* append p at rear of deque */
  370.                 break;
  371.                 }
  372.             else if ((*cmpfn)(p, p2->right) < 0)
  373.                 {                     /* if p sorts before p2->right */
  374.                 DQ_R_INSERT(p, p2);    /* insert after p2 */
  375.                 break;
  376.                 }
  377.             }
  378.         }
  379.     }
  380. ###dq_main.c
  381. /* dq_main - test routine for deque package
  382.  */
  383. #include "local.h"
  384. #include "deque.h"
  385. DQ_NODE *dq = NULL;
  386. #define MYNODE struct mynode
  387. MYNODE
  388.     {
  389.     MYNODE *left;
  390.     MYNODE *right;
  391.     int data;
  392.     };
  393. #define LINESIZE 20
  394. main()
  395.     {
  396.     MYNODE *p;            /* current node */
  397.     char buf[LINESIZE];    /* buffer for input */
  398.  
  399.     DQ_OPEN(&dq);
  400.     printf("Type < to push (insert at left end of deque)\n");
  401.     printf("Type > to enque (insert at right end of deque)\n");
  402.     printf("Type - to pop (remove leftmost node)\n");
  403.     printf("Type = to print contents of deque\n");
  404.     printf("Type 0 to reset deque\n");
  405.     for (;;)
  406.         {
  407.         getreply("?: ", buf, 2);
  408.         switch (buf[0])
  409.             {
  410.         case '<':
  411.             p = (MYNODE *)malloc(sizeof(MYNODE));
  412.             if (p == NULL)
  413.                 error("out of space", "");
  414.             getreply("data: ", buf, 5);    /* bound to 4 digits */
  415.             p->data = atoi(buf);
  416.             DQ_PUSH(dq, p);
  417.             break;
  418.         case '>':
  419.             p = (MYNODE *)malloc(sizeof(MYNODE));
  420.             if (p == NULL)
  421.                 error("out of space", "");
  422.             getreply("data: ", buf, 5);    /* bound to 4 digits */
  423.             p->data = atoi(buf);
  424.             DQ_APPEND(dq, p);
  425.             break;
  426.         case '-':
  427.             p = (MYNODE *)DQ_POP(dq);
  428.             if (p == NULL)
  429.                 printf("EMPTY DEQUE\n");
  430.             else
  431.                 {
  432.                 printf("data=%6d\n", p->data);
  433.                 free((data_ptr)p);
  434.                 }
  435.             break;
  436.         case '=':
  437.             if (DQ_IS_EMPTY(dq))
  438.                 printf("EMPTY DEQUE\n");
  439.             else
  440.                 EACH_DQ(dq, p, MYNODE)
  441.                     printf("data=%6d\n", p->data);
  442.             break;
  443.         case '0':
  444.             DQ_CLOSE(&dq);
  445.             break;
  446.         default:
  447.             printf("unknown command: %c\n", buf[0]);
  448.             break;
  449.             }
  450.         }
  451.     }
  452. ###dq_open.c
  453. /* dq_open - open a deque */
  454. #include "deque.h"
  455. void dq_open(pdq)
  456.     DQ_NODE **pdq;
  457.     {
  458.     *pdq = (DQ_NODE *)malloc(sizeof(DQ_NODE));
  459.     if (*pdq == NULL)
  460.         return;
  461.     (*pdq)->left = (*pdq)->right = (*pdq);
  462.     }
  463. ###dq_pop.c
  464. /* dq_pop - remove leftmost node and return pointer to it
  465.  * Treats deque as a stack to the right of dq master node.
  466.  */
  467. #include "deque.h"
  468. DQ_NODE *dq_pop(dq)
  469.     DQ_NODE *dq;
  470.     {
  471.     DQ_NODE *d;
  472.  
  473.     d = dq->right;
  474.     if (d == dq)
  475.         return (NULL);
  476.     return (DQ_DETACH(dq, d));
  477.     }
  478. ###dq_r_insert.c
  479. /* dq_r_insert - insert node d to the right of node p */
  480. #include "deque.h"
  481. void dq_r_insert(d, p)
  482.     DQ_NODE *d;
  483.     DQ_NODE *p;
  484.     {
  485.     DQ_NODE *q;
  486.  
  487.     q = p->right;
  488.     d->left = p;
  489.     d->right = q;
  490.     p->right = d;
  491.     q->left = d;
  492.     }
  493. ###dump.c
  494. /* dump - print memory bytes
  495.  *        (Warning - some usages may be non-portable)
  496.  */
  497. #include "local.h"
  498. #define LINESIZE 16
  499. #define BYTEMASK 0xFF
  500. void dump(s, n)
  501.     char s[];        /* byte address to be dumped */
  502.     unsigned n;        /* number of bytes to dump */
  503.     {
  504.     unsigned i;        /* byte counter */
  505.  
  506.     for (i = 0; i < n; ++i)
  507.         {
  508.         if (i % LINESIZE == 0)
  509.             printf("\n%08x: ", &s[i]);
  510.         printf(" %02x", s[i] & BYTEMASK);
  511.         }
  512.     printf("\n");
  513.     }
  514. ###errno.c
  515. int errno = 0;
  516. ###error.c
  517. /* error - print error message and exit */
  518. #include <stdio.h>
  519. error(s1, s2)
  520.     char s1[], s2[];
  521.     {
  522.     fprintf(stderr, "%s %s\n", s1, s2);
  523.     fflush(stderr);
  524.     exit(1);
  525.     }
  526. ###fgetsnn.c
  527. /* fgetsnn - get one line, omitting the newline (if any)
  528.  * Returns the number of characters stored,
  529.  * which equals size-1 only if no newline was found to that point.
  530.  * Returns EOF at end of file.
  531.  */
  532. #include "local.h"
  533. int fgetsnn(s, size, fp)
  534.     char s[];
  535.     int size;
  536.     FILE *fp;
  537.     {
  538.     int i;
  539.     metachar c;
  540.  
  541.     for (i = 0; i < size-1 && (c = getc(fp)) != EOF && c != '\n'; ++i)
  542.         s[i] = c;
  543.     if (c == EOF)
  544.         return (EOF);
  545.     /* else */
  546.     s[i] = '\0';
  547.     return (i);
  548.     }
  549. ###gen_menu.c
  550. /* gen_menu - generate C source for menu from description file */
  551. #include "local.h"
  552. #define MAXBFLDS 8000
  553. #define C_ID_LEN 31
  554. #define FILE_NM_LEN 64        /* max length of file name */
  555. #define C_EXPR_LEN 80        /* arbitrarly limit on length of struct ref */
  556. #define TITLE_LEN 80        /* max length of displayed title */
  557. #define SCR_POS_LEN 3        /* max digits in screen position */
  558. #define FTYPE_LEN 1            /* field type is only one char */
  559. #define EDIT_LEN 2            /* edit type is 1 char plus 1 optional digit */
  560. #define MAXFLINE (TITLE_LEN+FTYPE_LEN+EDIT_LEN+SCR_POS_LEN+SCR_POS_LEN+50)
  561. #define GETPSTR(p, s)  \
  562.     {  if (!getpstr(p, s, sizeof(s)))  error("Cannot match" , p);  }
  563. #define OPTPSTR(p, s)  \
  564.     getpstr(p, s, sizeof(s))
  565. #define GETPLIN(p, s)  \
  566.     {  if (!getplin(p, s, sizeof(s)))  error("Cannot match" , p);  }                                                                                                                                                             /*
  567. .PE
  568. .PS 17
  569. /* internal variables */
  570. static char buf[BUFSIZ] = {""};
  571. static char buf_flds[MAXBFLDS] = {""};
  572. static short i_flds = 0;
  573. static char mname[C_ID_LEN+1] = {""};
  574. static char mstruct[C_EXPR_LEN+1] = {""};
  575. static char mtitle[TITLE_LEN+1] = {""};
  576. static char mheader[FILE_NM_LEN+1] = {""};
  577. static char fname[C_ID_LEN+1] = {""};
  578. static char fline[SCR_POS_LEN+1] = {""};
  579. static char fcol[SCR_POS_LEN+1] = {""};
  580. static char ffn[C_ID_LEN+1] = {""};
  581. static char ftype[FTYPE_LEN+1] = {""};
  582. static char fedit[EDIT_LEN+1] = {""};
  583. static char fdesc[TITLE_LEN+1] = {""};
  584. void do_1_menu(), do_1_fld(), pr_s_fld(), pr_c_fld(), pr_m_fld(), pr_f_fld();                                                                                                                                                             /*
  585. .PE
  586. .PS 15
  587. /* gen_menu (main) */
  588. void main()
  589.     {
  590.     do_1_menu();
  591.     while (OPTPSTR("Field name:", fname))
  592.         do_1_fld();        /* process one field */
  593.     printf("static FIELD F%s[] =\n", mname);
  594.     printf("\t{\n");
  595.     for (i_flds = 0; buf_flds[i_flds] != '\0'; ++i_flds)
  596.         putchar(buf_flds[i_flds]);
  597.     printf("\t};\n");
  598.     printf("MENU %s = {\"%s\", F%s, DIM(F%s), 0};\n",
  599.         mname, mtitle, mname, mname);
  600.     }                                                                                                                                                             /*
  601. .PE
  602. .PS 13
  603. /* do_1_menu - process the menu information */
  604. void do_1_menu()
  605.     {
  606.     GETPSTR("Menu name:", mname);
  607.     GETPLIN("Menu title:", mtitle);
  608.     GETPSTR("Header:", mheader);
  609.     GETPSTR("C-struct:", mstruct);
  610.     printf("/* %s - %s */\n", mname, mtitle);
  611.     printf("#include \"local.h\"\n");
  612.     printf("#include \"menu.h\"\n");
  613.     printf("#include \"%s\"\n", mheader);
  614.     }                                                                                                                                                             /*
  615. .PE
  616. .PS 33
  617. /* do_1_fld - process the info for one field */
  618. void do_1_fld()
  619.     {
  620.     asserts(IN_RANGE(i_flds, 0, MAXBFLDS - MAXFLINE), "buffer space ok"); 
  621.     GETPLIN("Desc:", fdesc);
  622.     GETPSTR("Line:", fline);
  623.     GETPSTR("Col:", fcol);
  624.     GETPSTR("Type:", ftype);
  625.     if (tolower(ftype[0]) == 's')
  626.         GETPSTR("Edit:", fedit);
  627.     if (ftype[0] != 'm')
  628.         GETPSTR("Post-fn:", ffn);
  629.     if (!STREQ(ffn, "0") && !STREQ(ffn, "NULL"))
  630.         printf("extern bool %s();\n", ffn);
  631.     switch (ftype[0])
  632.         {
  633.     case 's':
  634.     case 'S':
  635.         pr_s_fld();
  636.         break;
  637.     case 'c':
  638.         pr_c_fld();
  639.         break;
  640.     case 'm':
  641.         pr_m_fld();
  642.         break;
  643.     case 'f':
  644.         pr_f_fld();
  645.         break;
  646.     default:
  647.         error("Unknown field type", ftype);
  648.         }
  649.     i_flds += strlen(&buf_flds[i_flds]);
  650.     if (i_flds > MAXBFLDS - MAXFLINE)
  651.         error("out of buffer space", "");
  652.     }                                                                                                                                                             /*
  653. .PE
  654. .PS 22
  655. /* pr_s_fld - print the info for a string field */
  656. void pr_s_fld()
  657.     {
  658.     sprintf(&buf_flds[i_flds],
  659.         "\t{%s, %s, \"%s\", '%c', &S%s, NULL, NULL, %s},\n",
  660.         fline, fcol, fdesc, ftype[0], fname, ffn);
  661.     if (fedit[1] == '\0')
  662.         {
  663.         printf("static STRING_VAL S%s =\n", fname);
  664.         printf("\t{'%c', (%s).%s, sizeof((%s).%s), NULL};\n",
  665.             fedit[0], mstruct, fname, mstruct, fname);
  666.         }
  667.     else
  668.         {
  669.         printf("static char N%s[%c+1] = {0};\n",
  670.             fname, fedit[1]);
  671.         printf("static STRING_VAL S%s =\n", fname);
  672.         printf("\t{'%c', N%s, sizeof(N%s), &(%s).%s};\n",
  673.             fedit[0], fname, fname, mstruct, fname);
  674.         }
  675.     }                                                                                                                                                             /*
  676. .PE
  677. .PS 18
  678. /* pr_c_fld - print the info for a choice field */
  679. void pr_c_fld()
  680.     {
  681.     int ret;
  682.  
  683.     sprintf(&buf_flds[i_flds],
  684.         "\t{%s, %s, \"%s\", '%c', NULL, &C%s, NULL, %s},\n",
  685.         fline, fcol, fdesc, ftype[0], fname, ffn);
  686.     printf("static char *T%s[]=\n", fname);
  687.     do    {
  688.         ret = getsnn(buf, BUFSIZ);
  689.         if (ret != EOF && ret > 0)    /* skip blank lines */
  690.             printf("%s\n", buf);
  691.         } while (ret != EOF && strchr(buf, ';') == NULL);
  692.     printf("static CHOICE_VAL C%s =\n", fname);
  693.     printf("\t{DIM(T%s), T%s, (%s).%s};\n",
  694.         fname, fname, mstruct, fname);
  695.     }                                                                                                                                                             /*
  696. .PE
  697. .PS 15
  698. /* pr_m_fld - print the info for a menu field */
  699. void pr_m_fld()
  700.     {
  701.     printf("extern MENU %s;\n", fname);
  702.     sprintf(&buf_flds[i_flds],
  703.         "\t{%s, %s, \"%s\", '%c', NULL, NULL, &%s, %s},\n",
  704.         fline, fcol, fdesc, ftype[0], fname, ffn);
  705.     }
  706. /* pr_f_fld - print the info for a function field */
  707. void pr_f_fld()
  708.     {
  709.     sprintf(&buf_flds[i_flds],
  710.         "\t{%s, %s, \"%s\", '%c', NULL, NULL, NULL, %s},\n",
  711.         fline, fcol, fdesc, ftype[0], ffn);
  712.     }
  713. ###getplin.c
  714. /* getplin - get a line from input
  715.  * line must start with specified "prompt" text
  716.  * return YES if text matched, NO otherwise
  717.  */
  718. #include "local.h"
  719. #define FMTSIZE 84
  720. bool getplin(p, s, n)
  721.     char p[];
  722.     char s[];
  723.     size_t n;
  724.     {
  725.     char buf[BUFSIZ];
  726.     char fmt[FMTSIZE];
  727.     metachar c;
  728.  
  729.     if (!strfit(fmt, p, FMTSIZE - 4))
  730.         return (NO);    /* prompt text is too long */
  731.     strcat(fmt, "%c");
  732.     while (isspace(c = getchar()))
  733.         ;
  734.     ungetc(c, stdin);
  735.     if (scanf(fmt, buf) != 1)
  736.         return (NO);
  737.     if (getsnn(buf, BUFSIZ) == EOF)
  738.         return (NO);
  739.     if (!strfit(s, buf, n))
  740.         fprintf(stderr, "<%s> chopped to \n<%s>\n", buf, s);
  741.     return (YES);
  742.     }
  743. ###getpstr.c
  744. /* getpstr - get a string from input
  745.  * string must be preceded by specified "prompt" text
  746.  * return YES if text matched, NO otherwise
  747.  */
  748. #include "local.h"
  749. #define FMTSIZE 84    /* arbitrary limit on size of "prompt" */
  750.  
  751. bool getpstr(p, s, n)
  752.     char p[];                /* : !NULL */
  753.     char s[];                /* : string */
  754.     size_t n;                /* : {1:sizeof(p[*])} */
  755.     {
  756.     char buf[BUFSIZ];        /* : string */
  757.     char fmt[FMTSIZE];        /* : string */
  758.     metachar c;
  759.  
  760.     if (!strfit(fmt, p, FMTSIZE - 4))    /* copy "prompt" into fmt */
  761.         return (NO);        /* prompt text is too long */
  762.     strcat(fmt, "%s");        /* make fmt into a scanf format */
  763.     while (isspace(c = getchar()))
  764.         ;                    /* skip leading whitespace */
  765.     ungetc(c, stdin);        /* put the non-whitespace back */
  766.     if (scanf(fmt, buf) != 1)
  767.         return (NO);        /* scanf match failed */
  768.     if (!strfit(s, buf, n))
  769.         fprintf(stderr, "<%s> chopped to <%s>\n", buf, s);
  770.     return (YES);
  771.     }
  772. ###getreply.c
  773. /* getreply - print a prompt and get one-line reply
  774.  * Returns length of reply string, or EOF if end-of-file
  775.  * Consumes an entire input line, even if over-long.
  776.  */
  777. #include "local.h"
  778. int getreply(prompt, reply, size)
  779.     char prompt[];
  780.     char reply[];
  781.     int size;
  782.     {
  783.     metachar last_char;            /* the last char read */
  784.     int get_ret;                /* getsnn return: length of reply or EOF */
  785.  
  786.     printf("%s", prompt);
  787.     get_ret = getsnn(reply, size);
  788.     if (get_ret == EOF)
  789.         return (EOF);
  790.     else if (get_ret == size-1)    /* no newline was read */
  791.         while ((last_char = getchar()) != EOF && last_char != '\n')
  792.             ;
  793.     if (last_char == EOF)
  794.         return (EOF);
  795.     return (get_ret);
  796.     }
  797. ###getsnn.c
  798. /* getsnn - get one line, omitting the newline (if any)
  799.  * Returns the number of characters stored,
  800.  * which equals size-1 only if no newline was found to that point.
  801.  * Returns EOF at end of file.
  802.  */
  803. #include "local.h"
  804. int getsnn(s, size)
  805.     char s[];
  806.     int size;
  807.     {
  808.     int i;
  809.     metachar c;
  810.  
  811.     for (i = 0; i < size-1 && (c = getchar()) != EOF && c != '\n'; ++i)
  812.         s[i] = c;
  813.     s[i] = '\0';
  814.     if (c == EOF)
  815.         return (EOF);
  816.     return (i);
  817.     }
  818. ###isort.c
  819. /* isort - sort array a (dimension n) using insertion sort
  820.  */
  821. #include "local.h"
  822. void isort(a, n)
  823.     short a[];    /* array to be sorted; a[0:n-1]: multiset */
  824.     index_t n;    /* dimension of a */
  825.     {
  826.     index_t i;
  827.     index_t j;
  828.     short t;
  829.  
  830.     for (i = 1; i < n; ++i)
  831.         {
  832.         /* a[0:i-1] => sorted */
  833.         t = a[i];
  834.         for (j = i; j > 0 && a[j-1] > t; --j)
  835.             a[j] = a[j-1];        /* a[0:n-1] => !multiset */
  836.         a[j] = t;                /* a[0:n-1] => multiset */
  837.         }
  838.     /* a[0:n-1] => sorted */
  839.     }
  840. ###isort1.c
  841. /* isort - sort array a (dimension n) using insertion sort
  842.  */
  843. #include "local.h"
  844. void isort(a, n)
  845.     int a[];
  846.     int n;
  847.     {
  848.     int i;
  849.     int j;
  850.     int t;
  851.  
  852.     for (i = 1; i < n; ++i)    /* a[0:i-1]=>sorted */
  853.         {
  854.         t = a[i];
  855.         j = i;
  856.         while (j > 0 && a[j-1] > t)
  857.             {
  858.             a[j] = a[j-1];
  859.             --j;
  860.             }
  861.         a[j] = t;
  862.         }
  863.     /* a=>sorted */
  864.     }
  865. #ifdef TRYMAIN
  866. #include <math.h>
  867. main(ac, av)
  868.     int ac;
  869.     char *av[];
  870.     {
  871.     int i;
  872.     int lim;
  873.     static int a[10000];
  874.     double tim;
  875.     long cputim();
  876.  
  877.     lim = atoi(av[1]);
  878.     printf("lim=%d\n", lim);
  879.     for (i = 0; i < lim; ++i)
  880.         a[i] = rand();
  881.     cputim();
  882.     isort(a, lim);
  883.     tim = cputim() * 1e6 / 60;
  884.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  885.     printf("N**2 = %.0f\n", (double)lim * lim);
  886.     printf("cpu time = %.2f N**2 (usec)\n", tim / ((double)lim * lim));
  887.     for (i = 0; i < lim-1; ++i)
  888.         {
  889.         if (a[i] > a[i+1])
  890.             error("bad value", "");
  891.         }
  892.     exit(SUCCEED);
  893.     }
  894. #endif
  895. ###isort2.c
  896. /* isort - sort array a (dimension n) using insertion sort
  897.  */
  898. #include "local.h"
  899. void isort(a, n)
  900.     int a[];
  901.     int n;
  902.     {
  903.     int i;
  904.     int *pj;
  905.     int *pjm;
  906.     int t;
  907.  
  908.     for (i = 1; i < n; ++i)    /* a[0:i-1]=>sorted */
  909.         {
  910.         t = a[i];
  911.         pj = &a[i];
  912.         pjm = pj - 1;
  913.         while (pj > a && *pjm > t)
  914.             {
  915.             *pj = *pjm;
  916.             --pj;
  917.             --pjm;
  918.             }
  919.         *pj = t;
  920.         }
  921.     /* a=>sorted */
  922.     }
  923. #ifdef TRYMAIN
  924. #include <math.h>
  925. main(ac, av)
  926.     int ac;
  927.     char *av[];
  928.     {
  929.     int i;
  930.     int lim;
  931.     static int a[10000];
  932.     double tim;
  933.     long cputim();
  934.  
  935.     lim = atoi(av[1]);
  936.     printf("lim=%d\n", lim);
  937.     for (i = 0; i < lim; ++i)
  938.         a[i] = rand();
  939.     cputim();
  940.     isort(a, lim);
  941.     tim = cputim() * 1e6 / 60;
  942.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  943.     printf("N**2 = %.0f\n", (double)lim * lim);
  944.     printf("cpu time = %.2f N**2 (usec)\n", tim / ((double)lim * lim));
  945.     for (i = 0; i < lim-1; ++i)
  946.         {
  947.         if (a[i] > a[i+1])
  948.             error("bad value", "");
  949.         }
  950.     exit(SUCCEED);
  951.     }
  952. #endif
  953. ###isort3.c
  954. /* isort - sort array a (dimension n) using insertion sort
  955.  */
  956. #include "local.h"
  957. void isort(a, n)
  958.     int a[];
  959.     int n;
  960.     {
  961.     int i;
  962.     register int *pj;
  963.     register int *pjm;
  964.     int t;
  965.  
  966.     for (i = 1; i < n; ++i)    /* a[0:i-1]=>sorted */
  967.         {
  968.         t = a[i];
  969.         pj = &a[i];
  970.         pjm = pj - 1;
  971.         while (pj > a && *pjm > t)
  972.             {
  973.             *pj = *pjm;
  974.             --pj;
  975.             --pjm;
  976.             }
  977.         *pj = t;
  978.         }
  979.     /* a=>sorted */
  980.     }
  981. #ifdef TRYMAIN
  982. #include <math.h>
  983. main(ac, av)
  984.     int ac;
  985.     char *av[];
  986.     {
  987.     int i;
  988.     int lim;
  989.     static int a[10000];
  990.     double tim;
  991.     long cputim();
  992.  
  993.     lim = atoi(av[1]);
  994.     printf("lim=%d\n", lim);
  995.     for (i = 0; i < lim; ++i)
  996.         a[i] = rand();
  997.     cputim();
  998.     isort(a, lim);
  999.     tim = cputim() * 1e6 / 60;
  1000.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  1001.     printf("N**2 = %.0f\n", (double)lim * lim);
  1002.     printf("cpu time = %.2f N**2 (usec)\n", tim / ((double)lim * lim));
  1003.     for (i = 0; i < lim-1; ++i)
  1004.         {
  1005.         if (a[i] > a[i+1])
  1006.             error("bad value", "");
  1007.         }
  1008.     exit(SUCCEED);
  1009.     }
  1010. #endif
  1011. ###isortp.c
  1012. /* isort - sort array a (dimension n) using insertion sort
  1013.  */
  1014. #include "local.h"
  1015. void isort(a, n)
  1016.     int a[];
  1017.     int n;
  1018.     {
  1019.     int i;
  1020.     int *pj;
  1021.     int *pjm;
  1022.     int t;
  1023.  
  1024.     for (i = 1; i < n; ++i)    /* a[0:i-1]=>sorted */
  1025.         {
  1026.         t = a[i];
  1027.         pj = &a[i];
  1028.         pjm = pj - 1;
  1029.         while (pj > a && *pjm > t)
  1030.             {
  1031.             *pj = *pjm;
  1032.             --pj;
  1033.             --pjm;
  1034.             }
  1035.         *pj = t;
  1036.         }
  1037.     /* a=>sorted */
  1038.     }
  1039. ###itoa.c
  1040. /* itoa - convert integer n to string (ndigits max) */
  1041. #include "local.h"
  1042. bool itoa(n, str, ndigits)
  1043.     int n;
  1044.     char str[];
  1045.     int ndigits;
  1046.     {
  1047.     int sign;
  1048.     short i;
  1049.     bool success;
  1050.     unsigned un = n;    /* need room for most-negative n */
  1051.  
  1052.     success = YES;
  1053.     if (ndigits < 1 || n < 0 && ndigits < 2)
  1054.         return (NO);        /* can't even get started */
  1055.     else if (n == 0)
  1056.         {
  1057.         strcpy(str, "0");    /* dispose of a special case */
  1058.         return (YES);
  1059.         }
  1060.     else if (n < 0)
  1061.         {
  1062.         sign = -1;
  1063.         un = -n;
  1064.         --ndigits;            /* sign consumes one print digit */
  1065.         }
  1066.     else
  1067.         sign = 1;
  1068.     for (i = 0; i < ndigits && un != 0; ++i)
  1069.         {
  1070.         str[i] = '0' + un % 10;
  1071.         un /= 10;
  1072.         }
  1073.     if (un != 0)        /* still more digits to print, and no room */
  1074.         {
  1075.         for (i = 0; i < ndigits; ++i)
  1076.             str[i] = '9';
  1077.         success = NO;
  1078.         }
  1079.     if (sign < 0)
  1080.         str[i++] = '-';
  1081.     str[i] = '\0';
  1082.     reverse(str);
  1083.     return (success);
  1084.     }
  1085. ###itoa_demo.c
  1086. /* itoa_demo - demonstrate itoa */
  1087. #include "local.h"
  1088. #define TEST(n, str, ndigits) \
  1089.     { \
  1090.     printf("%8d %4d %8d ", n, ndigits, itoa(n, str, ndigits)); \
  1091.     printf("<%s>\n", str); \
  1092.     }
  1093. main()
  1094.     {
  1095.     char str[20];
  1096.  
  1097.     TEST(0, str, 1);
  1098.     TEST(0, str, 0);
  1099.     TEST(-1, str, 1);
  1100.     TEST(-1, str, 2);
  1101.     TEST(100, str, 2);
  1102.     TEST(10000, str, 5);
  1103.     TEST(10000, str, 6);
  1104.     TEST(-10000, str, 6);
  1105.     }
  1106. ###memcpy.c
  1107. /* memcpy - copy n bytes from b to a */
  1108. #include "local.h"
  1109. data_ptr memcpy(s1, s2, n)
  1110.     data_ptr s1;
  1111.     data_ptr s2;
  1112.     register size_t n;
  1113.     {
  1114.     register char *a = s1;
  1115.     register char *b = s2;
  1116.  
  1117.     for (; n > 0; --n, ++a, ++b)
  1118.         *a = *b;
  1119.     return (s1);
  1120.     }
  1121. ###mu_ask.c
  1122. /* mu_ask - get responses to menu items
  1123.  * Keeps looping over string and choice fields;
  1124.  * terminates when user selects an action field, or hits SCR_EXIT.
  1125.  */
  1126. #include "menu.h"
  1127. FIELD *mu_ask(pm)
  1128.     MENU *pm;        /* ptr to current MENU */
  1129.     {
  1130.     FIELD *pf;        /* ptr to current FIELD */
  1131.     FIELD *pfj;        /* ptr to j-th FIELD of this MENU */
  1132.     SCR_CMDCHAR c;    /* most recent user key input */
  1133.     char vtype;        /* value type of current FIELD */
  1134.     bool legal;        /* is  c  valid input in this state? */
  1135.     short j;        /* index over FIELDs of this MENU */
  1136.  
  1137.     pm->cur_field = 0;        /* start with first field */
  1138.     FOREVER
  1139.         {
  1140.         pf = &pm->fields[pm->cur_field];
  1141.         legal = YES;
  1142.         vtype = pf->val_type;
  1143.  
  1144.         /* accept user input, get user's SCR_CMDCHAR */
  1145.         if (vtype == 'c' || tolower(vtype) == 's')
  1146.             {
  1147.             if (vtype == 'c')
  1148.                 c = mu_chv(pf);
  1149.             else            /* vtype == 's' OR 'S' */
  1150.                 c = mu_str(pf);
  1151.             if (pf->pfn != NULL)
  1152.                 legal = (*pf->pfn)(pm);
  1153.             if (c == SCR_EXIT)
  1154.                 return (NULL);
  1155.             }
  1156.         else
  1157.             {
  1158.             scr_curs(pf->line, pf->col);
  1159.             c = scr_getkey();
  1160.             }
  1161.         /* at this point, c is the user's response, and */
  1162.         /* legal records validity of 'c' or 's' field */
  1163.         /* (more) */                                                                /*
  1164. .PE
  1165. .PS  46
  1166.         /* determine next action, based on c */
  1167.         if (c == SCR_RETURN && (vtype == 'm' || vtype == 'f'))
  1168.             return (pf);
  1169.         else if (c == SCR_EXIT)
  1170.             return (NULL);
  1171.         else if (!legal)
  1172.             ;        /* no actions allowed if validation failed */
  1173.         else if (vtype == 'S' && pf->psv->string[0] == '\0')
  1174.             legal = NO;
  1175.         else if (!SCR_CMD(c) && tolower(vtype) != 's')
  1176.             {
  1177.             legal = NO;    /* tentatively */
  1178.             for (j = 0; j < pm->nfields; ++j)
  1179.                 {
  1180.                 pfj = &pm->fields[j];
  1181.                 if (toupper(pfj->desc[0]) == toupper(c))
  1182.                     {
  1183.                     pm->cur_field = j;
  1184.                     legal = YES;
  1185.                     break;
  1186.                     }
  1187.                 }
  1188.             }
  1189.         else if (SCR_CMD(c))
  1190.             {
  1191.             switch (c)
  1192.                 {
  1193.             case SCR_UP:
  1194.                 pm->cur_field = IMOD(pm->cur_field - 1, pm->nfields);
  1195.                 break;
  1196.             case SCR_DOWN:
  1197.             case SCR_RETURN:
  1198.                 pm->cur_field = IMOD(pm->cur_field + 1, pm->nfields);
  1199.                 break;
  1200.             case SCR_HOME:
  1201.                 pm->cur_field = 0;
  1202.                 break;
  1203.             default:
  1204.                 legal = NO;
  1205.                 break;
  1206.                 }
  1207.             }
  1208.         if (!legal)
  1209.             scr_beep();
  1210.         } /* end FOREVER */
  1211.     }
  1212. ###mu_chv.c
  1213. /* mu_chv - get a value for a CHOICE_VAL field
  1214.  * Return the SCR_CMDCHAR that terminated the input of this field.
  1215.  * fld_sync = field in data rec agrees with screen
  1216.  */
  1217. #include "menu.h"
  1218. SCR_CMDCHAR mu_chv(pf)
  1219.     FIELD *pf;                /* ptr to current FIELD : fld_sync */
  1220.     {
  1221.     short nchoice;            /* current choice value: {0:9} */
  1222.     CHOICE_VAL *pcv;        /* ptr to this field's CHOICE_VAL */
  1223.     SCR_CMDCHAR c;            /* most recent user input char */
  1224.     short prevlen;            /* length of previous choice display string */
  1225.     short curlen;            /* length of current choice display string */
  1226.     short i;
  1227.     
  1228.     prevlen = 0;
  1229.     pcv = pf->pcv;
  1230.     if ('0' <= *pcv->pc && *pcv->pc <= '9')
  1231.         nchoice = *pcv->pc - '0';
  1232.     else
  1233.         nchoice = 0;
  1234.     FOREVER
  1235.         {
  1236.         /* scr_curs to start of choice display, display current choice */
  1237.         scr_curs(pf->line, pf->col + strlen(pf->desc) + 2);
  1238.         scr_print("%s", pcv->choices[nchoice]);        /* pf => fld_sync */
  1239.  
  1240.         /* erase any leftover from previous choice */
  1241.         curlen = strlen(pcv->choices[nchoice]);
  1242.         for (i = 0; i < prevlen - curlen; ++i)
  1243.             scr_putc(' ');
  1244.         for (i = 0; i < prevlen - curlen; ++i)
  1245.             scr_putc('\b');
  1246.         prevlen = curlen;
  1247.  
  1248.         /* get user input and process it */
  1249.         c = scr_getkey();
  1250.         if (c != SCR_LEFT && c != SCR_RIGHT)
  1251.             return (c);
  1252.         else if (c == SCR_RIGHT)
  1253.             nchoice = IMOD(nchoice + 1, pcv->nchoices);
  1254.         else /* c == SCR_LEFT */
  1255.             nchoice = IMOD(nchoice - 1, pcv->nchoices);
  1256.         *pcv->pc = '0' + nchoice;                    /* pf => !fld_sync */
  1257.         }
  1258.     }
  1259. ###mu_do.c
  1260. #include "menu.h"
  1261. /* mu_do - present a menu, process actions until user SCR_EXIT
  1262.  */
  1263. void mu_do(pm)
  1264.     MENU *pm;
  1265.     {
  1266.     FIELD *pf;
  1267.     static short level = 0;
  1268.  
  1269.     if (level == 0)
  1270.         scr_open();    /* initialize the terminal state */
  1271.     ++level;
  1272.     FOREVER
  1273.         {
  1274.         mu_pr(pm);                        /* print the menu */
  1275.         pf = mu_ask(pm);                /* get a new field ptr */
  1276.         if (pf == NULL)
  1277.             break;
  1278.         else if (pf->val_type == 'm')    /* new field is a menu */
  1279.             mu_do(pf->pmenu);
  1280.         else /* pf->val_type == 'f' -- new field is a C fn */
  1281.             {
  1282.             asserts(pf->val_type == 'f', "val_type is 'f'");
  1283.             (void)(*pf->pfn)(pm);
  1284.             }
  1285.         }
  1286.     --level;
  1287.     if (level == 0)
  1288.         {
  1289.         scr_curs(scr_lins-1, 0);
  1290.         scr_close();    /* restore terminal state */
  1291.         }
  1292.     }
  1293. ###mu_pr.c
  1294. /* mu_pr - display a menu on the screen */
  1295. #include "menu.h"
  1296. void mu_pr(pm)        /* at return, pm => menu-sync */
  1297.     MENU *pm;        /* ptr to the MENU to be displayed */
  1298.     {
  1299.     short i;        /* index for loop over fields */
  1300.     FIELD *pf;        /* pointer to each FIELD */
  1301.     short i_choice;    /* numeric value of choice field */
  1302.  
  1303.     scr_clear();
  1304.  
  1305.     /* print the menu title, centered on top line */
  1306.     scr_curs(0, (scr_cols - strlen(pm->title))/2 - 3);
  1307.     scr_print("%s", pm->title);
  1308.  
  1309.     for (i = 0; i < pm->nfields; ++i)        /* for each field */
  1310.         {
  1311.         pf = &pm->fields[i];
  1312.  
  1313.         /* print the field description at proper x,y location */
  1314.         scr_curs(pf->line, pf->col);
  1315.         scr_print("%s  ", pf->desc);
  1316.  
  1317.         /* for string and choice fields, print current value */
  1318.         if (tolower(pf->val_type) == 's')
  1319.             {
  1320.             if (pf->psv->pnum != NULL)        /* field has numeric form */
  1321.                 itoa(*pf->psv->pnum, pf->psv->string, pf->psv->maxsize -1);
  1322.             scr_print("%s", pf->psv->string);
  1323.             }
  1324.         else if (pf->val_type == 'c')
  1325.             {
  1326.             if ('0' <= *pf->pcv->pc && *pf->pcv->pc <= '9')
  1327.                 i_choice = *pf->pcv->pc - '0';
  1328.             else
  1329.                 i_choice = 0;
  1330.             scr_print("%s", pf->pcv->choices[i_choice]);
  1331.             }
  1332.         }
  1333.     scr_refresh();
  1334.     }
  1335. ###mu_reply.c
  1336. /*  mu_reply -- get a reply in response to a prompt
  1337.  *                on the last screen line
  1338.  */
  1339. #include "local.h"
  1340. #include "menu.h"
  1341.  
  1342. mu_reply(prompt, reply, size)
  1343.     char prompt[];        /* : string */
  1344.     char reply[];        /* : !NULL */
  1345.     int size;            /* max number of chars allowed in reply */
  1346.     {
  1347.     STRING_VAL rsv;        /* reply string value structure */
  1348.  
  1349.     if (scr_mode == SCR_TTY)
  1350.         return (getreply(prompt, reply, size));
  1351.     else
  1352.         {
  1353.         scr_curs(scr_lins - 1, 0);
  1354.         scr_print("%s", prompt);
  1355.         reply[0] = '\0';        /* reply string initially empty */
  1356.         rsv.edit_type = 'a';    /* initialize the STRING_VAL rsv */
  1357.         rsv.string = reply;
  1358.         rsv.maxsize = size;
  1359.         rsv.pnum = NULL;        /* rsv => well-defined */
  1360.         mu_sval(&rsv);            /* let mu_sval handle the dialog */
  1361.         return (strlen(reply));
  1362.         }
  1363.     }
  1364. ###mu_str.c
  1365. /* mu_str - get a string for a STRING_VAL field */
  1366. #include "menu.h"
  1367. SCR_CMDCHAR mu_str(pf)
  1368.     FIELD *pf;        /* : fld_sync */
  1369.     {                 /* fld_sync = field in data rec agrees with screen */
  1370.     SCR_CMDCHAR ret;
  1371.     STRING_VAL *psv;
  1372.  
  1373.     psv = pf->psv;    /* get the string-value pointer for this field */
  1374.  
  1375.     /* position scr_curs just to right of string value */
  1376.     scr_curs(pf->line, pf->col + strlen(pf->desc) + 2 + strlen(psv->string));
  1377.  
  1378.     ret = mu_sval(psv);                        /* get string value */
  1379.     if (psv->pnum != NULL)                    /* pf => !fld_sync */
  1380.         *psv->pnum = atoi(psv->string);        /* pf => fld_sync */
  1381.     return (ret);
  1382.     }
  1383. ###mu_sval.c
  1384. /* mu_sval - get the string contents for a STRING_VAL field
  1385.  * Assumes cursor is just to right of string
  1386.  */
  1387. #include "menu.h"
  1388. SCR_CMDCHAR mu_sval(psv)
  1389.     STRING_VAL *psv;    /* ptr to the STRING_VAL structure : str_sync  */
  1390.                         /* str_sync = screen agrees with contents of   */
  1391.                         /*            psv->string                      */
  1392.     {
  1393.     char *s;            /* ptr to start of string */
  1394.     short i;            /* index of current nul-terminator */
  1395.     SCR_CMDCHAR c;        /* latest SCR_CMDCHAR returned from scr_getkey */
  1396.  
  1397.     s = psv->string;
  1398.     i = strlen(s);
  1399.     FOREVER
  1400.         {
  1401.         c = scr_getkey();
  1402.         if (SCR_CMD(c))                /* if c is a command character, */
  1403.             return (c);                /* return it */
  1404.         else if (c == '\b')
  1405.             {
  1406.             if (i > 0)
  1407.                 {
  1408.                 scr_print("\b \b");    /* erase previous character */
  1409.                 s[--i] = '\0';        /* shorten the string */
  1410.                 }
  1411.             }
  1412.         else if (psv->edit_type == 'n' && !isdigit(c) &&
  1413.             !(i == 0 && c == '-'))
  1414.             {
  1415.             scr_beep();                /* non-digit invalid */
  1416.             }
  1417.         else if (i < psv->maxsize - 1)
  1418.             {
  1419.             scr_putc(s[i++] = c);    /* append the char, and echo it */
  1420.             s[i] = '\0';
  1421.             }
  1422.         else
  1423.             scr_beep();                /* no room left in string */
  1424.         }
  1425.     }
  1426. ###nfrom.c
  1427. /* nfrom - {{ get listing from lpc files }} */
  1428. int nfrom(lo, hi)
  1429.     int lo, hi;
  1430.     {
  1431.     return (rand() % (hi - lo + 1) + lo);
  1432.     }
  1433. ###part_db.c
  1434. /* part_db.c - simulated database access to parts */
  1435. #include "local.h"
  1436. #include "part.h"
  1437. static PART parts[3] = {0};
  1438. static short n_part = 0;
  1439.  
  1440. /* db_locate_part -- see if a part is in the database */
  1441. static int db_locate_part(partp)
  1442.     PART *partp;
  1443.     {
  1444.     short i;
  1445.  
  1446.     for (i = 0; i < n_part; ++i)
  1447.         if (STREQ(partp->part_no, parts[i].part_no))
  1448.             return (i);        /* this is the part, return its index */
  1449.     return (-1); /* no part from 0 to n_part matches this part_no */
  1450.     }                                                                                                                                                             /*
  1451. .PE
  1452. .PS 13
  1453. /* db_add_part - add a part record to database */
  1454. bool db_add_part(partp)
  1455.     PART *partp;
  1456.     {
  1457.     if (n_part >= DIM(parts))
  1458.         {
  1459.         remark("Part storage is full", "");
  1460.         return (NO);
  1461.         }
  1462.     STRUCTASST(parts[n_part], *partp);
  1463.     ++n_part;
  1464.     return (YES);
  1465.     }                                                                                                                                                             /*
  1466. .PE
  1467. .PS 12
  1468. /* db_find_part - find a part record in database */
  1469. bool db_find_part(partp)
  1470.     PART *partp;
  1471.     {
  1472.     short i;
  1473.  
  1474.     i = db_locate_part(partp);
  1475.     if (i == -1)
  1476.         return(NO);
  1477.     STRUCTASST(*partp, parts[i]);
  1478.     return(YES);
  1479.     }                                                                                                                                              /* 
  1480. .PE
  1481. .PS 17
  1482. /* db_del_part - delete a part record in database */
  1483. bool db_del_part(partp)
  1484.     PART *partp;
  1485.     {
  1486.     short i;
  1487.  
  1488.     for (i = 0; i < n_part; ++i)
  1489.         {
  1490.         if (STREQ(partp->part_no, parts[i].part_no))
  1491.             {
  1492.             --n_part;
  1493.             STRUCTASST(parts[i], parts[n_part]);
  1494.             return (YES);
  1495.             }
  1496.         }
  1497.     return (NO);
  1498.     }                                                                                                                                                             /*
  1499. .PE
  1500. .PS 16
  1501. /* db_chg_part - change a part record in database */
  1502. bool db_chg_part(partp)
  1503.     PART *partp;
  1504.     {
  1505.     short i;
  1506.  
  1507.     for (i = 0; i < n_part; ++i)
  1508.         {
  1509.         if (STREQ(partp->part_no, parts[i].part_no))
  1510.             {
  1511.             STRUCTASST(parts[i], *partp);
  1512.             return (YES);
  1513.             }
  1514.         }
  1515.     return (NO);
  1516.     }                                                                                                                                                             /*
  1517. .PE
  1518. .PS 12
  1519. /* db_open_part - open the parts database
  1520.  * Dummy - no action needed
  1521.  */
  1522. void db_open_part()
  1523.     {
  1524.     }
  1525. /* db_close_part - close the parts database
  1526.  * Dummy - no action needed
  1527.  */
  1528. void db_close_part()
  1529.     {
  1530.     }
  1531. ###part_db_tr.c
  1532. /* part_db_tr.c - simulated database access to parts 
  1533.  * uses binary tree for in-memory storage
  1534.  */
  1535. #include "tree.h"
  1536. #include "part.h"
  1537. #define TPART struct tr_part
  1538. TPART
  1539.     {
  1540.     TPART *right;
  1541.     TPART *left;
  1542.     PART part;
  1543.     };
  1544. static TPART tpart = {0};
  1545. static TPART *parts = NULL;
  1546.  
  1547. /* db_cmp_part - comparison function for database access */
  1548. static int db_cmp_part(p1, p2)
  1549.     TPART *p1, *p2;
  1550.     {
  1551.     return (strcmp(p1->part.part_no, p2->part.part_no));
  1552.     }
  1553. /* (more) */                                                                                                                            /*
  1554. .PE
  1555. .PS 16
  1556. /* db_add_part - add a part record to database */
  1557. bool db_add_part(partp)
  1558.     PART *partp;
  1559.     {
  1560.     TPART *p;
  1561.  
  1562.     p = (TPART *)malloc(sizeof(TPART));
  1563.     if (p == NULL)
  1564.         {
  1565.         remark("Part storage is full", "");
  1566.         return (NO);
  1567.         }
  1568.     STRUCTASST(p->part, *partp);
  1569.     TR_INSERT(&parts, p, db_cmp_part);
  1570.     return (YES);
  1571.     }
  1572.                                                                                                                                           /* 
  1573. .PE
  1574. .PS  50
  1575. /* db_find_part - find a part record in database */
  1576. bool db_find_part(partp)
  1577.     PART *partp;
  1578.     {
  1579.     TPART *pn;        /* ptr to part record in tree */
  1580.  
  1581.     STRUCTASST(tpart.part, *partp);
  1582.     pn = (TPART *)TR_FIND(&parts, &tpart, db_cmp_part);
  1583.     if (pn == NULL)
  1584.         return (NO);
  1585.     STRUCTASST(*partp, pn->part);
  1586.     return (YES);
  1587.     }
  1588. /* db_del_part - delete a part record in database */
  1589. bool db_del_part(partp)
  1590.     PART *partp;
  1591.     {
  1592.     TPART **pln;        /* ptr to link-in of part record in tree */
  1593.  
  1594.     STRUCTASST(tpart.part, *partp);
  1595.     pln = (TPART **)TR_LFIND(&parts, &tpart, db_cmp_part);
  1596.     if (*pln == NULL)
  1597.         {
  1598.         remark("No record for this part", "");
  1599.         return (NO);
  1600.         }
  1601.     TR_DELETE(&parts, pln, db_cmp_part);
  1602.     return (YES);
  1603.     }
  1604. /* db_chg_part - change a part record in database */
  1605. bool db_chg_part(partp)
  1606.     PART *partp;
  1607.     {
  1608.     TPART *pn;        /* ptr to part record in tree */
  1609.  
  1610.     STRUCTASST(tpart.part, *partp);
  1611.     pn = (TPART *)TR_FIND(&parts, &tpart, db_cmp_part);
  1612.     if (pn == NULL)        /* validation done in menu should prevent */
  1613.         return (NO);    /* non-existent part from reaching here */
  1614.     STRUCTASST(pn->part, *partp);
  1615.     return (YES);
  1616.     }
  1617. /* (more) */                                                                                                                            /*
  1618. .PE
  1619. .PS  50
  1620. /* db_open_part - open a part record database */
  1621. void db_open_part()
  1622.     {
  1623.     TR_OPEN(&parts);
  1624.     }
  1625.  
  1626. /* db_close_part - close the part record database */
  1627. void db_close_part()
  1628.     {
  1629.     TR_CLOSE(&parts);
  1630.     }
  1631. ###part_hash.c
  1632. /* part_hash.c -- hash file database access to parts */
  1633. #include "rec_io.h"
  1634. #include "part.h"
  1635. #define HPART struct hash_part
  1636. HPART
  1637.     {
  1638.     char hcode;
  1639.     PART part;
  1640.     };
  1641. static HPART hpart = {0};
  1642. static HPART kpart = {0};
  1643. static rec_fd part_fd = 0;
  1644.  
  1645. /* db_cmp_part - compare function for database access */
  1646. static int db_cmp_part(p1, p2)
  1647.     HPART *p1, *p2;
  1648.     {
  1649.     return (strcmp(p1->part.part_no, p2->part.part_no));
  1650.     }                                                                                                                                                             /*
  1651. .PE
  1652. .PS 11
  1653. /* db_hash_part - hash the part_no field */
  1654. static long db_hash_part(p1)
  1655.     HPART *p1;
  1656.     {
  1657.     char *p;
  1658.     long sum = 0;
  1659.  
  1660.     for (p = p1->part.part_no; *p != '\0'; ++p)
  1661.         sum += *p;
  1662.     return (IMOD(sum, rec_nrecs(part_fd)));
  1663.     }                                                                                                                                                             /*
  1664. .PE
  1665. .PS 7
  1666. /* db_open_part - open the parts database */
  1667. void db_open_part()
  1668.     {
  1669.     part_fd = rec_open("part.dat", O_RDWR, sizeof(HPART));
  1670.     if (part_fd < 0)
  1671.         error("can't open ", "part.dat");
  1672.     }                                                                                                                                                             /*
  1673. .PE
  1674. .PS 6
  1675. /* db_close_part - close the parts database */
  1676. void db_close_part()
  1677.     {
  1678.     if (rec_close(part_fd) < 0)
  1679.         error("can't close ", "part.dat");
  1680.     }                                                                                                                                                             /*
  1681. .PE
  1682. .PS 21
  1683. /* db_add_part - add a part to the database */
  1684. bool db_add_part(partp)
  1685.     PART *partp;
  1686.     {
  1687.     long i;
  1688.  
  1689.     STRUCTASST(hpart.part, *partp);
  1690.     hpart.hcode = REC_OCCUP;
  1691.     i = rec_havail(part_fd, &hpart, &kpart, db_hash_part);
  1692.     if (i == REC_FULL)
  1693.         {
  1694.         remark("Part storage is full", "");
  1695.         return (NO);
  1696.         }
  1697.     else if (i == REC_ERROR || !rec_put(part_fd, &hpart, i))
  1698.         {
  1699.         remark("I/O error", "");
  1700.         return (NO);
  1701.         }
  1702.     return (YES);
  1703.     }                                                                                                                                                             /*
  1704. .PE
  1705. .PS 11
  1706. /* db_chg_part - change a part record on database */
  1707. bool db_chg_part(partp)
  1708.     PART *partp;
  1709.     {
  1710.     long this_rec;
  1711.     
  1712.     STRUCTASST(kpart.part, *partp);
  1713.     this_rec = rec_hfind(part_fd, &kpart, &hpart, db_cmp_part, db_hash_part);
  1714.     kpart.hcode = REC_OCCUP;
  1715.     return (rec_put(part_fd, &kpart, this_rec));
  1716.     }                                                                                                                                                             /*
  1717. .PE
  1718. .PS 11
  1719. /* db_del_part - delete a part record on database */
  1720. bool db_del_part(partp)
  1721.     PART *partp;
  1722.     {
  1723.     long this_rec;
  1724.     
  1725.     STRUCTASST(kpart.part, *partp);
  1726.     this_rec = rec_hfind(part_fd, &kpart, &hpart, db_cmp_part, db_hash_part);
  1727.     kpart.hcode = REC_DELET;
  1728.     return (rec_put(part_fd, &kpart, this_rec));
  1729.     }                                                                                                                                                             /*
  1730. .PE
  1731. .PS 21
  1732. /* db_find_part - find a part on the database */
  1733. bool db_find_part(partp)
  1734.     PART *partp;
  1735.     {
  1736.     long this_rec;
  1737.  
  1738.     STRUCTASST(kpart.part, *partp);
  1739.     this_rec = rec_hfind(part_fd, &kpart, &hpart, db_cmp_part, db_hash_part);
  1740.     if (this_rec >= 0)
  1741.         {
  1742.         STRUCTASST(*partp, hpart.part);
  1743.         return (YES);
  1744.         }
  1745.     else if (this_rec == REC_ERROR)
  1746.         {
  1747.         remark("I/O error", "");
  1748.         return (NO);
  1749.         }
  1750.     else
  1751.         return (NO);
  1752.     }
  1753. ###part_menu.c
  1754. #include "menu.h"
  1755. #include "part.h"
  1756. /* main menu */
  1757. /* menu-sync = screen agrees with menu contents */
  1758. PART part1 = {0};
  1759. PART null_part = {0};
  1760. extern MENU add_menu, chg_menu, del_menu, acd_menu;
  1761. /* isn_part - verify that no record exists for this key */
  1762. bool isn_part(pm)
  1763.     MENU *pm;        /* : menu-sync */
  1764.     {
  1765.     if (db_find_part(&part1))
  1766.         {
  1767.         /* pm => !menu-sync, new part contents */
  1768.         remark("This part is entered already", "");
  1769.         STRUCTASST(part1, null_part);    /* clear the part struct */
  1770.         mu_pr(pm);                        /* pm => menu-sync */
  1771.         return (NO);
  1772.         }
  1773.     return (YES);
  1774.     }                                                                                                                                                             /*
  1775. .PE
  1776. .PS 14
  1777. /* is_part - verify that record exists and read it into part1 */
  1778. bool is_part(pm)
  1779.     MENU *pm;
  1780.     {
  1781.     if (!db_find_part(&part1))
  1782.         {
  1783.         remark("Unknown part number", "");
  1784.         STRUCTASST(part1, null_part);        /* clear the part struct */
  1785.         mu_pr(pm);        /* display the cleared record, pm => menu-sync */
  1786.         return (NO);
  1787.         }
  1788.     /* pm => !menu-sync, new part contents */
  1789.     mu_pr(pm);            /* display the found record, pm => menu-sync */
  1790.     return (YES);
  1791.     }                                                                                                                                                             /*
  1792. .PE
  1793. .PS 19
  1794. /* addpart - add a part record */
  1795. bool addpart(pm)
  1796.     MENU *pm;
  1797.     {
  1798.     char reply[2];
  1799.  
  1800.     STRUCTASST(part1, null_part);
  1801.     mu_do(&add_menu);
  1802.     /* if no valid transaction occured, exit without change to db */
  1803.     if (part1.part_no[0] == '\0')
  1804.         return (NO);
  1805.     mu_reply("Add this part [y/n]? ", reply, 2);
  1806.     if (reply[0] == 'y')
  1807.         {
  1808.         return (db_add_part(&part1));
  1809.         }
  1810.     else
  1811.         return (NO);
  1812.     }                                                                                                                                                         /*
  1813. .PE
  1814. .PS 18
  1815. /* chgpart - change a part record */
  1816. bool chgpart(pm)
  1817.     MENU *pm;
  1818.     {
  1819.     char reply[2];
  1820.  
  1821.     STRUCTASST(part1, null_part);
  1822.     mu_do(&chg_menu);
  1823.     /* if no valid transaction occured, exit without change to db */
  1824.     if (part1.part_no[0] == '\0')
  1825.         return (NO);
  1826.     mu_reply("Change this part [y/n]? ", reply, 2);
  1827.     if (reply[0] == 'y')
  1828.         return (db_chg_part(&part1));
  1829.     else
  1830.         return (NO);
  1831.     }                                                                                                                                                             /*
  1832. .PE
  1833. .PS 18
  1834. /* delpart - delete a part record */
  1835. bool delpart(pm)
  1836.     MENU *pm;
  1837.     {
  1838.     char reply[2];
  1839.  
  1840.     STRUCTASST(part1, null_part);
  1841.     mu_do(&del_menu);
  1842.     /* if no valid transaction occured, exit without change to db */
  1843.     if (part1.part_no[0] == '\0')
  1844.         return (NO);
  1845.     mu_reply("Delete this part [y/n]? ", reply, 2);
  1846.     if (reply[0] == 'y')
  1847.         return (db_del_part(&part1));
  1848.     else
  1849.         return (NO);
  1850.     }                                                                                                                                                             /*
  1851. .PE
  1852. .PS 7
  1853. /* part_menu (main) - execute the parts menu */
  1854. main()
  1855.     {
  1856.     db_open_part();
  1857.     mu_do(&acd_menu);
  1858.     db_close_part();
  1859.     }
  1860. ###plot_m.c
  1861. /* plot_m - demonstrate plot_trk function */
  1862. #include "local.h"
  1863. #include "screen.h"
  1864. main()
  1865.     {
  1866.     short i;
  1867.  
  1868.     scr_open();
  1869.     scr_clear();
  1870.     for (i = 0; i < 400; ++i)    /* four times around the track */
  1871.         plot_trk(i, 'X');
  1872.     scr_curs(scr_lins-1, 0);
  1873.     scr_close();
  1874.     }
  1875. ###plot_trk.c
  1876. /* plot_trk - plot position around a pseudo-oval track */
  1877. #include "local.h"
  1878. #include "screen.h"
  1879. #define LIN_ORIGIN 11
  1880. #define COL_ORIGIN 40
  1881. #define NPOINTS 26
  1882. #define IMAX (NPOINTS - 1)
  1883. #define POS(n, signlin, signcol) \
  1884.     scr_curs(LIN_ORIGIN + (signlin) * coords[n].lin, \
  1885.         COL_ORIGIN + (signcol) * coords[n].col)
  1886. static struct coords
  1887.     {
  1888.     short lin, col;
  1889.     } coords[NPOINTS] =
  1890.     {        /* points for one quadrant (quarter-screen) */
  1891.     {11,  0},  {11,  2},  {11,  4},  {11,  6},  {11,  8},
  1892.     {11, 10},  {11, 12},  {11, 14},  {11, 16},  {11, 18},
  1893.     {11, 20},  {11, 22},  {11, 24},  {11, 26},  {11, 28},
  1894.     {10, 29},  { 9, 30},  { 8, 31},  { 7, 32},  { 6, 33},
  1895.     { 5, 34},  { 4, 35},  { 3, 36},  { 2, 36},  { 1, 36},
  1896.     { 0, 36},
  1897.     };                                                                                                                                        /*
  1898. .PE
  1899. .PS 26
  1900. /* plot_trk - plot a point */
  1901. void plot_trk(n, c)
  1902.     int n;
  1903.     char c;
  1904.     {
  1905.     asserts(n >= 0, "plot_trk: n is non-negative");
  1906.     n %= 4 * IMAX;
  1907.     if (n < IMAX)
  1908.         POS(n, 1, 1);                /* 1st quadrant - lower right */
  1909.     else if (n < 2 * IMAX)
  1910.         POS(2 * IMAX - n, -1, 1);    /* 2nd quadrant - upper right */
  1911.     else if (n < 3 * IMAX)
  1912.         POS(n - 2 * IMAX, -1, -1);    /* 3rd quadrant - upper left */
  1913.     else
  1914.         POS(4 * IMAX - n, 1, -1);    /* 4th quadrant - lower left */
  1915.     scr_putc(c);
  1916.     }
  1917. ###pmt.c
  1918. /* pmt - compute payment on mortgage
  1919.  */
  1920. #include <local.h>
  1921. main()
  1922.     {
  1923.     double pow();    /* power function */
  1924.     double round();    /* rounding function */
  1925.     double intmo;    /* monthly interest */
  1926.     double intyr;    /* annual interest */
  1927.     double bal;        /* balance remaining */
  1928.     double pmt;        /* monthly payment */
  1929.     short npmts;    /* number of payments */
  1930.     short nyears;    /* number of years */
  1931.  
  1932.     /* get input and compute monthly payment */
  1933.     printf("Enter principal (e.g. 82500.00): ");
  1934.     scanf("%lf", &bal);
  1935.     printf("Enter annual interest rate (e.g. 16.25): ");
  1936.     scanf("%lf", &intyr);
  1937.     printf("Enter number of years: ");
  1938.     scanf("%hd", &nyears);
  1939.     printf("\nprincipal=%.2f", bal);
  1940.     printf("  interest=%.4f%%", intyr);
  1941.     printf("  years=%d\n\n", nyears);
  1942.     intyr /= 100.;
  1943.     intmo = intyr / 12.;
  1944.     npmts = nyears * 12;
  1945.     pmt = bal * (intmo / (1. - pow(1. + intmo, (double)-npmts)));
  1946.     pmt = round(pmt, .0099);
  1947.  
  1948.     printf("pmt=%.2f\n", pmt);
  1949.     }
  1950. double round(dollars, adjust)
  1951.     double dollars;
  1952.     double adjust;
  1953.     {
  1954.     long pennies;
  1955.  
  1956.     pennies = (dollars + adjust) * 100.;
  1957.     return (pennies / 100.);
  1958.     }
  1959. ###powtst.c
  1960. /* powtst - test accuracy of pow
  1961.  */
  1962. #include "local.h"
  1963. #include <math.h>
  1964. main()
  1965.     {
  1966.     double x, y, z;
  1967.  
  1968.     for (x = 1.; x <= 25.; x = x + 1.)
  1969.         {
  1970.         y = x * x;
  1971.         z = pow(x, 2.);
  1972.         if (y != z)
  1973.             printf("%5.1f %20.16f %20.16f %20.16f\n", x, y, z, y-z);
  1974.         }
  1975.     }
  1976. ###q_append.c
  1977. /* q_append - install Q_NODE at rear of queue */
  1978. #include "queue.h"
  1979. void q_append(frontp, rearp, p)
  1980.     Q_NODE **frontp, **rearp;
  1981.     Q_NODE *p;
  1982.     {
  1983.     Q_NEXT(p) = NULL;            /* new node will be rear of queue */
  1984.     if (*frontp == NULL)        /* if queue was empty, */
  1985.         *frontp = *rearp = p;    /* p becomes front and rear */
  1986.     else
  1987.         {
  1988.         Q_NEXT(*rearp) = p;        /* splice p into queue */
  1989.         *rearp = p;                /* p becomes rear of queue */
  1990.         }
  1991.     }
  1992. ###q_close.c
  1993. /* q_close - close the queue accessed via *frontp and *rearp */
  1994. #include "queue.h"
  1995. void q_close(frontp, rearp)
  1996.     Q_NODE **frontp, **rearp;
  1997.     {
  1998.     Q_NODE *p;
  1999.     Q_NODE *pnext;
  2000.  
  2001.     for (p = *frontp; p != NULL; p = pnext)
  2002.         {
  2003.         pnext = Q_NEXT(p);
  2004.         free(p);        /* p is (momentarily) undefined */
  2005.         }
  2006.     *frontp = *rearp = NULL;        /* prevent dangling ptr */
  2007.     }
  2008. ###q_insert.c
  2009. /* q_insert - install Q_NODE at proper place in queue */
  2010. #include "queue.h"
  2011. void q_insert(frontp, rearp, p, cmpfn)
  2012.     Q_NODE **frontp, **rearp;
  2013.     Q_NODE *p;
  2014.     int (*cmpfn)();                /* function for comparisons */
  2015.     {
  2016.     Q_NODE *p2;
  2017.  
  2018.     if (*frontp == NULL                    /* if queue was empty, */
  2019.         || (*cmpfn)(p, *frontp) < 0)    /* or if p comes first, */
  2020.         Q_PUSH(frontp, rearp, p);        /* push p onto front */
  2021.     else
  2022.         {
  2023.         for (p2 = *frontp; ; p2 = Q_NEXT(p2))
  2024.             {
  2025.             if (Q_NEXT(p2) == NULL)            
  2026.                 {                             /* if end of queue, */
  2027.                 Q_APPEND(frontp, rearp, p);    /* append p at rear of queue */
  2028.                 break;
  2029.                 }
  2030.             else if ((*cmpfn)(p, Q_NEXT(p2)) < 0)
  2031.                 {                        /* if p sorts before Q_NEXT(p2) */
  2032.                 Q_R_INSERT(frontp, rearp, p, p2);    /* insert after p2 */
  2033.                 break;
  2034.                 }
  2035.             }
  2036.         }
  2037.     }
  2038. ###q_lfind.c
  2039. /* q_lfind - search queue for equal match to p, return its link-in 
  2040.  * Return NULL if no match
  2041.  */
  2042. #include "queue.h"
  2043. Q_NODE **q_lfind(frontp, rearp, p, cmpfn)
  2044.     Q_NODE **frontp, **rearp;
  2045.     Q_NODE *p;
  2046.     int (*cmpfn)();
  2047.     {
  2048.     Q_NODE **pp;
  2049.  
  2050.     for (pp = frontp; *pp != NULL; pp = &Q_NEXT(*pp))
  2051.         if ((*cmpfn)(*pp, p) == 0)
  2052.             return (pp);
  2053.     return (NULL);
  2054.     }
  2055. ###q_main.c
  2056. /* q_main - test routine for queue package */
  2057. #include "local.h"
  2058. #include "queue.h"
  2059. #define NAME_NODE struct name_node
  2060. NAME_NODE
  2061.     {
  2062.     NAME_NODE *next;
  2063.     char name[4];
  2064.     };
  2065. NAME_NODE *front = NULL;        /* front node of queue */
  2066. NAME_NODE *rear = NULL;            /* rear node of queue */
  2067. NAME_NODE *p = NULL;            /* current node */
  2068. void show_cmds(), append_name(), push_name(), pop_name(), dump_names();
  2069. main()
  2070.     {
  2071.     char buf[2];                /* buffer for input */
  2072.  
  2073.     show_cmds();
  2074.     Q_OPEN(&front, &rear);        /* open the queue */
  2075.     FOREVER
  2076.         {
  2077.         if (getreply("?: ", buf, 2) == EOF)
  2078.             exit(0);
  2079.         switch (buf[0])
  2080.             {
  2081.         case '>':
  2082.             append_name();
  2083.             break;
  2084.         case '+':
  2085.             push_name();
  2086.             break;
  2087.         case '-':
  2088.             pop_name();
  2089.             break;
  2090.         case '=':
  2091.             dump_names();
  2092.             break;
  2093.         case '0':
  2094.             Q_CLOSE(&front, &rear);
  2095.             Q_OPEN(&front, &rear);        /* open the queue */
  2096.             break;
  2097.         case '?':
  2098.             show_cmds();
  2099.             break;
  2100.         default:
  2101.             printf("unknown command: %c\n", buf[0]);
  2102.             show_cmds();
  2103.             break;
  2104.             }
  2105.         }
  2106.     }                                                                    /*
  2107. .PE
  2108. .PS 44
  2109. /* show_cmds -- show legal commands */
  2110. void show_cmds()
  2111.     {
  2112.     printf("Type > to append, + to push, - to pop, = to print, 0 to reset:\n");
  2113.     }
  2114. /* append_name - append new name on queue */
  2115. void append_name()
  2116.     {
  2117.     p = (NAME_NODE *)malloc(sizeof(NAME_NODE));
  2118.     if (p == NULL)
  2119.         error("out of space", "");
  2120.     getreply("name: ", p->name, 4);
  2121.     Q_APPEND(&front, &rear, p);
  2122.     }
  2123. /* push_name - push new name on queue */
  2124. void push_name()
  2125.     {
  2126.     p = (NAME_NODE *)malloc(sizeof(NAME_NODE));
  2127.     if (p == NULL)
  2128.         error("out of space", "");
  2129.     getreply("name: ", p->name, 4);
  2130.     Q_PUSH(&front, &rear, p);
  2131.     }
  2132. /* pop_name - pop a name off queue */
  2133. void pop_name()
  2134.     {
  2135.     p = (NAME_NODE *)Q_POP(&front, &rear);
  2136.     if (p == NULL)
  2137.         printf("EMPTY QUEUE\n");
  2138.     else
  2139.         {
  2140.         printf("name= %s\n", p->name);
  2141.         free(p);
  2142.         }
  2143.     }
  2144. /* dump_names - print the current queue of names */
  2145. void dump_names()
  2146.     {
  2147.     if (front == NULL)
  2148.         printf("EMPTY QUEUE\n");
  2149.     else
  2150.         EACH_Q(front, p)
  2151.             printf("name= %s\n", p->name);
  2152.     }
  2153. ###q_pop.c
  2154. /* q_pop - detach front node of queue and return pointer to it */
  2155. #include "queue.h"
  2156. Q_NODE *q_pop(frontp, rearp)
  2157.     Q_NODE **frontp, **rearp;
  2158.     {
  2159.     Q_NODE *p;
  2160.  
  2161.     if (*frontp == NULL)
  2162.         return (NULL);
  2163.     p = *frontp;            /* p points to front of queue */
  2164.     *frontp = Q_NEXT(p);    /* front now points to next node (or NULL) */
  2165.     if (*frontp == NULL)    /* if queue is now empty, */
  2166.         *rearp = NULL;        /* then make both ptrs NULL */
  2167.     Q_NEXT(p) = NULL;        /* prevent dangling ptr */
  2168.     return (p);
  2169.     }
  2170. ###q_push.c
  2171. /* q_push - install Q_NODE at front of queue */
  2172. #include "queue.h"
  2173. void q_push(frontp, rearp, p)
  2174.     Q_NODE **frontp, **rearp;
  2175.     Q_NODE *p;
  2176.     {
  2177.     Q_NEXT(p) = *frontp;    /* p points to previous front (or NULL) */
  2178.     *frontp = p;            /* *frontp now points to p */
  2179.     if (*rearp == NULL)        /* if queue was empty, */
  2180.         *rearp = p;            /* *rearp also points to p */
  2181.     }
  2182. ###q_r_detach.c
  2183. /* q_r_detach - detach queue node that *pp links-in and return pointer to it */
  2184. #include "queue.h"
  2185. Q_NODE *q_r_detach(frontp, rearp, pp)
  2186.     Q_NODE **frontp, **rearp;
  2187.     Q_NODE **pp;
  2188.     {
  2189.     Q_NODE *p2;                /* ptr to detached node */
  2190.  
  2191.     if (*pp == NULL)
  2192.         return (NULL);
  2193.     p2 = *pp;                /* p2 points to node to detach */
  2194.     *pp = Q_NEXT(p2);        /* *pp now points to next node (or NULL) */
  2195.     if (*frontp == NULL)    /* if queue is now empty, */
  2196.         *rearp = NULL;        /* then make both ptrs NULL */
  2197.     Q_NEXT(p2) = NULL;        /* prevent dangling ptr */
  2198.     return (p2);
  2199.     }
  2200. ###q_r_insert.c
  2201. /* q_r_insert - install Q_NODE after *pp */
  2202. #include "queue.h"
  2203. void q_r_insert(frontp, rearp, p, pp)
  2204.     Q_NODE **frontp, **rearp;
  2205.     Q_NODE *p;
  2206.     Q_NODE **pp;
  2207.     {
  2208.     Q_NEXT(p) = *pp;        /* p points to node following *pp (or NULL) */
  2209.     *pp = p;                /* *pp now points to p */
  2210.     if (*rearp == NULL)        /* if queue was empty, */
  2211.         *rearp = p;            /* *rearp also points to p */
  2212.     }
  2213. ###qkmain3.c
  2214. #include "qksort3.c"
  2215. #define SORTFN(a, lim) qksort(a, lim)
  2216. static int intcmp(a, b)
  2217.     int *a, *b;
  2218.     {
  2219.     if (*a > *b)
  2220.         return (1);
  2221.     else if (*a == *b)
  2222.         return (0);
  2223.     else
  2224.         return (-1);
  2225.     }
  2226. #include "qkmain.h"
  2227. ###qksort.c
  2228. /* qksort - sort array a (dimension n) using quicksort */
  2229. #include "local.h"
  2230. /* iqksort - internal function to partition a[lo:hi] */
  2231. static void iqksort(a, lo, hi)
  2232.     short a[];    /* array to be sorted; a[lo:hi]: multiset */
  2233.     index_t lo;    /* lowest subscript */
  2234.     index_t hi;    /* highest subscript */
  2235.     {
  2236.     index_t mid = lo + (hi-lo)/2;    /* : {lo:hi} */
  2237.     index_t i;                        /* : {lo+1:hi+1} */
  2238.     index_t lastlo;                    /* : {lo:hi-1} */
  2239.     short tmp;
  2240.  
  2241.     SWAP(a[lo], a[mid], tmp);
  2242.     lastlo = lo;
  2243.     for (i = lo + 1; i <= hi; ++i)
  2244.         {
  2245.         if (a[lo] > a[i])
  2246.             {
  2247.             ++lastlo;
  2248.             SWAP(a[lastlo], a[i], tmp);
  2249.             }
  2250.         }
  2251.     SWAP(a[lo], a[lastlo], tmp);
  2252.     if (lastlo != 0 && lo < lastlo - 1)
  2253.         iqksort(a, lo, lastlo - 1);
  2254.     if (lastlo + 1 < hi)
  2255.         iqksort(a, lastlo + 1, hi);
  2256.     }
  2257. /* qksort - external entry point */
  2258. void qksort(a, n)
  2259.     short a[];    /* array to be sorted; a[0:n-1]: multiset */
  2260.     index_t n;    /* number of elements */
  2261.     {
  2262.     if (n > 1)
  2263.         iqksort(a, 0, n - 1);
  2264.     asserts(tst_sort(a, n), "a is sorted");
  2265.     }
  2266. ###qksort1a.c
  2267. /* qksort - sort array a (dimension n) using quicksort
  2268.  */
  2269. #include "local.h"
  2270. void qksort(a, n)
  2271.     int a[];
  2272.     int n;
  2273.     {
  2274.     iqksort(a, 0, n-1);
  2275.     isort(a, n);
  2276.     }
  2277. static void iqksort(a, lo, hi)
  2278.     int a[];
  2279.     int lo, hi;
  2280.     {
  2281.     int mid = (lo + hi) / 2;
  2282.     int i;
  2283.     int lastlo;
  2284.     int t;
  2285.     int tmp;
  2286.  
  2287.     if (hi - lo < 16)        /* should not use (hi < lo + 16) */
  2288.         return;
  2289.     SWAP(a[lo], a[mid], tmp);
  2290.     t = a[lo];
  2291.     lastlo = lo;
  2292.     for (i = lo+1; i <= hi; ++i)
  2293.         {
  2294.         if (a[i] < t)
  2295.             {
  2296.             ++lastlo;
  2297.             SWAP(a[lastlo], a[i], tmp);
  2298.             }
  2299.         }
  2300.     SWAP(a[lo], a[lastlo], tmp);
  2301.     iqksort(a, lo, lastlo - 1);
  2302.     iqksort(a, lastlo + 1, hi);
  2303.     }
  2304. /* isort - sort array a (dimension n) using insertion sort
  2305.  */
  2306. void isort(a, n)
  2307.     int a[];
  2308.     int n;
  2309.     {
  2310.     int i;
  2311.     int j;
  2312.     int t;
  2313.  
  2314.     for (i = 1; i < n; ++i)    /* a[0:i-1]=>sorted */
  2315.         {
  2316.         t = a[i];
  2317.         j = i;
  2318.         while (j > 0 && a[j-1] > t)
  2319.             {
  2320.             a[j] = a[j-1];
  2321.             --j;
  2322.             }
  2323.         a[j] = t;
  2324.         }
  2325.     /* a=>sorted */
  2326.     }
  2327. #ifdef TRYMAIN
  2328. #include <math.h>
  2329. main(ac, av)
  2330.     int ac;
  2331.     char *av[];
  2332.     {
  2333.     int i;
  2334.     int lim;
  2335.     static int a[10000];
  2336.     double nlogn;
  2337.     double tim;
  2338.     long cputim();
  2339.  
  2340.     lim = atoi(av[1]);
  2341.     printf("lim=%d\n", lim);
  2342.     for (i = 0; i < lim; ++i)
  2343.         a[i] = rand();
  2344.     cputim();
  2345.     qksort(a, lim);
  2346.     tim = cputim() * 1e6 / 60;
  2347.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  2348.     nlogn = lim * log((double)lim) / log(2.);
  2349.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  2350.     printf("N log N = %.3f\n", nlogn);
  2351.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  2352.     for (i = 0; i < lim-1; ++i)
  2353.         {
  2354.         if (a[i] > a[i+1])
  2355.             error("bad value", "");
  2356.         }
  2357.     exit(SUCCEED);
  2358.     }
  2359. #endif
  2360. ###qksort2.c
  2361. /* qksort - sort array a (dimension n) using quicksort
  2362.  */
  2363. #include "local.h"
  2364. void qksort(a, n)
  2365.     int a[];
  2366.     int n;
  2367.     {
  2368.     iqksort(a, &a[n-1]);
  2369.     }
  2370. static void iqksort(lo, hi)
  2371.     int *lo, *hi;
  2372.     {
  2373.     int *mid = lo + (hi - lo) / 2;
  2374.     int *i;
  2375.     int *lastlo;
  2376.     int t;
  2377.     int tmp;
  2378.  
  2379.     if (hi <= lo)
  2380.         return;
  2381.     SWAP(*lo, *mid, tmp);
  2382.     t = *lo;
  2383.     lastlo = lo;
  2384.     for (i = lo+1; i <= hi; ++i)
  2385.         {
  2386.         if (*i < t)
  2387.             {
  2388.             ++lastlo;
  2389.             SWAP(*lastlo, *i, tmp);
  2390.             }
  2391.         }
  2392.     SWAP(*lo, *lastlo, tmp);
  2393.     iqksort(lo, lastlo - 1);
  2394.     iqksort(lastlo + 1, hi);
  2395.     }
  2396. #ifdef TRYMAIN
  2397. #include <math.h>
  2398. main(ac, av)
  2399.     int ac;
  2400.     char *av[];
  2401.     {
  2402.     int i;
  2403.     int lim;
  2404.     static int a[10000];
  2405.     double nlogn;
  2406.     double tim;
  2407.     long cputim();
  2408.  
  2409.     lim = atoi(av[1]);
  2410.     printf("lim=%d\n", lim);
  2411.     for (i = 0; i < lim; ++i)
  2412.         a[i] = rand();
  2413.     cputim();
  2414.     qksort(a, lim);
  2415.     tim = cputim() * 1e6 / 60;
  2416.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  2417.     nlogn = lim * log((double)lim) / log(2.);
  2418.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  2419.     printf("N log N = %.3f\n", nlogn);
  2420.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  2421.     for (i = 0; i < lim-1; ++i)
  2422.         {
  2423.         if (a[i] > a[i+1])
  2424.             error("bad value", "");
  2425.         }
  2426.     exit(SUCCEED);
  2427.     }
  2428. #endif
  2429. ###qksort3.c
  2430. /* qksort - sort array a (dimension n) using quicksort
  2431.  */
  2432. #include "local.h"
  2433. void qksort(a, n)
  2434.     int a[];
  2435.     int n;
  2436.     {
  2437.     iqksort(a, &a[n-1]);
  2438.     }
  2439. static void iqksort(lo, hi)
  2440.     int *lo, *hi;
  2441.     {
  2442.     int *mid = lo + (hi - lo) / 2;
  2443.     register int *i;
  2444.     register int *lastlo;
  2445.     int t;
  2446.     register int tmp;
  2447.  
  2448.     if (hi <= lo)
  2449.         return;
  2450.     SWAP(*lo, *mid, tmp);
  2451.     t = *lo;
  2452.     lastlo = lo;
  2453.     for (i = lo+1; i <= hi; ++i)
  2454.         {
  2455.         if (*i < t)
  2456.             {
  2457.             ++lastlo;
  2458.             SWAP(*lastlo, *i, tmp);
  2459.             }
  2460.         }
  2461.     SWAP(*lo, *lastlo, tmp);
  2462.     iqksort(lo, lastlo - 1);
  2463.     iqksort(lastlo + 1, hi);
  2464.     }
  2465. ###qksort4.c
  2466. /* qksort - sort array a (dimension n) using quicksort
  2467.  */
  2468. #include "local.h"
  2469. void qksort(a, n)
  2470.     int a[];
  2471.     int n;
  2472.     {
  2473.     iqksort(a, &a[n-1]);
  2474.     isort(a, n);
  2475.     }
  2476. static void iqksort(lo, hi)
  2477.     int *lo, *hi;
  2478.     {
  2479.     int *mid = lo + (hi - lo) / 2;
  2480.     register int *i;
  2481.     register int *lastlo;
  2482.     int t;
  2483.     register int tmp;
  2484.  
  2485.     if (hi < lo + 16)    /* cannot use   (hi < lo + 16) */
  2486.         return;
  2487.     SWAP(*lo, *mid, tmp);
  2488.     t = *lo;
  2489.     lastlo = lo;
  2490.     for (i = lo+1; i <= hi; ++i)
  2491.         {
  2492.         if (*i < t)
  2493.             {
  2494.             ++lastlo;
  2495.             SWAP(*lastlo, *i, tmp);
  2496.             }
  2497.         }
  2498.     SWAP(*lo, *lastlo, tmp);
  2499.     iqksort(lo, lastlo - 1);
  2500.     iqksort(lastlo + 1, hi);
  2501.     }
  2502. /* isort - sort array a (dimension n) using insertion sort
  2503.  */
  2504. void isort(a, n)
  2505.     int a[];
  2506.     int n;
  2507.     {
  2508.     int i;
  2509.     register int *pj;
  2510.     register int *pjm;
  2511.     int t;
  2512.  
  2513.     for (i = 1; i < n; ++i)    /* a[0:i-1]=>sorted */
  2514.         {
  2515.         t = a[i];
  2516.         pj = &a[i];
  2517.         pjm = pj - 1;
  2518.         while (pj > a && *pjm > t)
  2519.             {
  2520.             *pj = *pjm;
  2521.             --pj;
  2522.             --pjm;
  2523.             }
  2524.         *pj = t;
  2525.         }
  2526.     /* a=>sorted */
  2527.     }
  2528. #ifdef TRYMAIN
  2529. #include <math.h>
  2530. main(ac, av)
  2531.     int ac;
  2532.     char *av[];
  2533.     {
  2534.     int i;
  2535.     int lim;
  2536.     static int a[10000];
  2537.     double nlogn;
  2538.     double tim;
  2539.     long cputim();
  2540.  
  2541.     lim = atoi(av[1]);
  2542.     printf("lim=%d\n", lim);
  2543.     for (i = 0; i < lim; ++i)
  2544.         a[i] = rand();
  2545.     cputim();
  2546.     qksort(a, lim);
  2547.     tim = cputim() * 1e6 / 60;
  2548.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  2549.     nlogn = lim * log((double)lim) / log(2.);
  2550.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  2551.     printf("N log N = %.3f\n", nlogn);
  2552.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  2553.     for (i = 0; i < lim-1; ++i)
  2554.         {
  2555.         if (a[i] > a[i+1])
  2556.             error("bad value", "");
  2557.         }
  2558.     exit(SUCCEED);
  2559.     }
  2560. #endif
  2561. ###qksortm.c
  2562. #ifdef TRYMAIN
  2563. #include <math.h>
  2564. main(ac, av)
  2565.     int ac;
  2566.     char *av[];
  2567.     {
  2568.     int i;
  2569.     int lim;
  2570.     static int a[10000];
  2571.     double nlogn;
  2572.     double tim;
  2573.     long cputim();
  2574.  
  2575.     lim = atoi(av[1]);
  2576.     printf("lim=%d\n", lim);
  2577.     for (i = 0; i < lim; ++i)
  2578.         a[i] = rand();
  2579.     cputim();
  2580.     qksort(a, lim);
  2581.     tim = cputim() * 1e6 / 60;
  2582.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  2583.     nlogn = lim * log((double)lim) / log(2.);
  2584.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  2585.     printf("N log N = %.3f\n", nlogn);
  2586.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  2587.     for (i = 0; i < lim-1; ++i)
  2588.         {
  2589.         if (a[i] > a[i+1])
  2590.             error("bad value", "");
  2591.         }
  2592.     exit(SUCCEED);
  2593.     }
  2594. #endif
  2595. ###qksortp.c
  2596. /* qksort - sort array a (dimension n) using quicksort */
  2597. #include "local.h"
  2598. /* iqksort - internal function to partition the array [*lo:*hi] */
  2599. static void iqksort(p_lo, p_hi)
  2600.     short *p_lo, *p_hi;
  2601.     {
  2602.     short *p_mid = p_lo + (p_hi - p_lo) / 2;    /* : {p_lo:p_hi} */
  2603.     short *p_i;                                    /* : {p_lo+1:p_hi+1} */
  2604.     short *p_lastlo;                            /* : {p_lo:p_hi-1} */
  2605.     short tmp;
  2606.  
  2607.     SWAP(*p_lo, *p_mid, tmp);
  2608.     p_lastlo = p_lo;
  2609.     for (p_i = p_lo+1; p_i <= p_hi; ++p_i)
  2610.         {
  2611.         if (*p_lo > *p_i)
  2612.             {
  2613.             ++p_lastlo;
  2614.             SWAP(*p_lastlo, *p_i, tmp);
  2615.             }
  2616.         }
  2617.     SWAP(*p_lo, *p_lastlo, tmp);
  2618.     if (p_lo < p_lastlo && p_lo < p_lastlo - 1)
  2619.         iqksort(p_lo, p_lastlo - 1);
  2620.     if (p_lastlo + 1 < p_hi)
  2621.         iqksort(p_lastlo + 1, p_hi);
  2622.     }
  2623. /* qksort - external entry point */
  2624. void qksort(a, n)
  2625.     short a[];    /* array to be sorted; a[0:n-1]: multiset */
  2626.     size_t n;    /* number of elements */
  2627.     {
  2628.     if (n > 1)
  2629.         iqksort(a, &a[n-1]);
  2630.     }
  2631. ###qmain.c
  2632. #include "qsort.c"
  2633. #define SORTFN(a, lim) qsort(a, lim, sizeof(a[0]), intcmp)
  2634. static int intcmp(a, b)
  2635.     int *a, *b;
  2636.     {
  2637.     if (*a > *b)
  2638.         return (1);
  2639.     else if (*a == *b)
  2640.         return (0);
  2641.     else
  2642.         return (-1);
  2643.     }
  2644. #include "qkmain.h"
  2645. ###qsort.c
  2646. /* qsort - sort array a (dimension n) using quicksort
  2647.  * based on Bentley, CACM April 84
  2648.  * Comments use notation A[i], a (fictitious) array of things
  2649.  * that are of size elt_size.
  2650.  */
  2651. #include "local.h"
  2652. /* swapfn - swap  elt_size bytes  a <--> b (internal routine) 
  2653.  */
  2654. static void swapfn(a, b, elt_size)
  2655.     register char *a;    /* pointer to one element of A */
  2656.     register char *b;    /* pointer to another element of A */
  2657.     size_t elt_size;    /* size of each element */
  2658.     {
  2659.     register size_t i;
  2660.     char tmp;
  2661.  
  2662.     for (i = 0; i < elt_size; ++i, ++a, ++b)
  2663.         SWAP(*a, *b, tmp);
  2664.     }                                                                                                                                  /*
  2665. .PE
  2666. .PS 25
  2667. /* iqsort - internal quicksort routine */
  2668. static void iqsort(p_lo, p_hi, elt_size, cmpfn)
  2669.     char *p_lo;            /* ptr to low element of (sub)array */
  2670.     char *p_hi;            /* ptr to high element of (sub)array */
  2671.     size_t elt_size;    /* size of each element */
  2672.     int (*cmpfn)();        /* comparison function ptr */
  2673.     {
  2674.     char *p_mid = p_lo + ((((p_hi - p_lo) / elt_size) / 2) * elt_size);
  2675.     register char *p_i;            /* pointer to A[i] */
  2676.     register char *p_lastlo;    /* pointer to A[lastlo] */
  2677.  
  2678.     swapfn(p_lo, p_mid, elt_size);    /* pick the middle element as pivot */
  2679.     p_lastlo = p_lo;
  2680.     for (p_i = p_lo + elt_size;  p_i <= p_hi; p_i += elt_size)
  2681.         {
  2682.         if ((*cmpfn)(p_lo, p_i) > 0)
  2683.             {
  2684.             p_lastlo += elt_size;
  2685.             swapfn(p_lastlo, p_i, elt_size);
  2686.             }
  2687.         }
  2688.     swapfn(p_lo, p_lastlo, elt_size);
  2689.     if (p_lo < p_lastlo && p_lo < p_lastlo - elt_size)
  2690.         iqsort(p_lo, p_lastlo - elt_size, elt_size, cmpfn);    /* lower */
  2691.     if (p_lastlo + elt_size < p_hi)
  2692.         iqsort(p_lastlo + elt_size, p_hi, elt_size, cmpfn);    /* upper */
  2693.     }                                                                                                                                  /*
  2694. .PE
  2695. .PS 9
  2696. /* qsort - the callable entry point */
  2697. void qsort(a, n, size, pf)
  2698.     data_ptr a;        /* address of array A to be sorted */
  2699.     size_t n;        /* number of elements in A */
  2700.     size_t size;    /* size of each element */
  2701.     int (*pf)();    /* comparison function ptr */
  2702.     {
  2703.     if (n > 1)
  2704.         iqsort((char *)a, (char *)a + (n-1) * size, size, pf);
  2705.     }
  2706. ###qsort_i.c
  2707. /* qsort - sort array a (dimension n) using quicksort
  2708.  * based on Bentley, CACM April 84
  2709.  * Iterative version; avoids recursion, uses little stack
  2710.  * Comments use notation A[i], a (fictitious) array of things
  2711.  * that are of size elt_size.
  2712.  * Uses static storage, not re-entrant.
  2713.  */
  2714. #include "local.h"
  2715.  
  2716. #define STACK_DEPTH (sizeof(size_t) * CHAR_BIT)
  2717.  
  2718. static size_t elt_size = 0;        /* size of one element */
  2719. static int (*cmpfn)() = NULL;    /* the comparison function ptr */
  2720. /* swapfn - swap  elt_size bytes  a <--> b (internal routine)  */
  2721. static void swapfn(a, b)
  2722.     register char *a;    /* pointer to one element of A */
  2723.     register char *b;    /* pointer to another element of A */
  2724.     {
  2725.     register size_t i;
  2726.     char tmp;
  2727.  
  2728.     LOOPDN(i, elt_size)
  2729.         {
  2730.         SWAP(*a, *b, tmp);
  2731.         ++a, ++b;
  2732.         }
  2733.     }                                                                                          /*
  2734. .PE
  2735. .PS 24
  2736. /* sort1 - partition one (sub)array, returning p_lastlo */
  2737. static char *sort1(p_lo, p_hi)
  2738.     char *p_lo;            /* ptr to low element of (sub)array */
  2739.     char *p_hi;            /* ptr to high element of (sub)array */
  2740.     {
  2741.     char *p_mid;
  2742.     register char *p_i;            /* pointer to A[i] */
  2743.     register char *p_lastlo;    /* pointer to A[lastlo] */
  2744.  
  2745.     p_mid = p_lo + ((((p_hi - p_lo) / elt_size) / 2) * elt_size);
  2746.     swapfn(p_lo, p_mid);        /* pick the middle element as pivot */
  2747.     p_lastlo = p_lo;
  2748.     for (p_i = p_lo + elt_size;  p_i <= p_hi; p_i += elt_size)
  2749.         {
  2750.         if ((*cmpfn)(p_lo, p_i) > 0)
  2751.             {
  2752.             p_lastlo += elt_size;
  2753.             swapfn(p_lastlo, p_i);
  2754.             }
  2755.         }
  2756.     swapfn(p_lo, p_lastlo);
  2757.     return (p_lastlo);
  2758.     }                                                                                                   /*
  2759. .PE
  2760. .PS 23
  2761. /* qsort - the callable entry point */
  2762. void qsort(a, n, size, pf)
  2763.     data_ptr a;        /* address of array A to be sorted */
  2764.     size_t n;        /* number of elements in A */
  2765.     size_t size;    /* size of each element */
  2766.     int (*pf)();    /* comparison function ptr */
  2767.     {
  2768.     static char *histack[STACK_DEPTH] = {0};
  2769.     static char *lostack[STACK_DEPTH] = {0};
  2770.     int istack;                /* index of next free stack cell */
  2771.     char *p_lo;                /* ptr to A[lo] */
  2772.     char *p_hi;                /* ptr to A[hi] */
  2773.     char *p_lastlo;            /* ptr to A[lastlo] */
  2774.     char *p_lo1, *p_hi1;    /* partition 1 */
  2775.     char *p_lo2, *p_hi2;    /* partition 2 */
  2776.     char *tpc;                /* tmp ptr for swaps */
  2777.  
  2778.     elt_size = size;
  2779.     cmpfn = pf;
  2780.     istack = 0;
  2781.     p_lo = a;
  2782.     p_hi = (char *)a + (n-1) * elt_size;                                                                            /*
  2783. .PE
  2784. .PS 45
  2785.     /* loop until no non-trivial partitions remain */
  2786.     while (istack != 0 || p_lo < p_hi)
  2787.         {
  2788.         p_lastlo = sort1(p_lo, p_hi);
  2789.         p_lo1 = p_lo;
  2790.         p_hi1 = p_lastlo - elt_size;
  2791.         p_lo2 = p_lastlo + elt_size;
  2792.         p_hi2 = p_hi;
  2793.         if (p_hi1 - p_lo1 > p_hi2 - p_lo2)
  2794.             {
  2795.             SWAP(p_lo1, p_lo2, tpc);
  2796.             SWAP(p_hi1, p_hi2, tpc);
  2797.             }
  2798.         /* now [p_lo1,p_hi1] is smaller partition */
  2799.         if (p_lo1 >= p_hi1)
  2800.             {
  2801.             if (p_lo2 < p_hi2)
  2802.                 {
  2803.                 /* do next iteration on [p_lo2, p_hi2] */
  2804.                 p_lo = p_lo2;
  2805.                 p_hi = p_hi2;
  2806.                 }
  2807.             else if (istack > 0)
  2808.                 {
  2809.                 /* take next iteration from stack */
  2810.                 --istack;
  2811.                 p_hi = histack[istack];
  2812.                 p_lo = lostack[istack];
  2813.                 }
  2814.             else
  2815.                 p_hi = p_lo;    /* done */
  2816.             }
  2817.         else
  2818.             {
  2819.             /* push [p_lo2, p_hi2] on stack */
  2820.             histack[istack] = p_hi2;
  2821.             lostack[istack] = p_lo2;
  2822.             ++istack;
  2823.             /* take next iteration from [p_lo1, p_hi1] */
  2824.             p_lo = p_lo1;
  2825.             p_hi = p_hi1;
  2826.             }
  2827.         }
  2828.     }
  2829. ###qsort_r.c
  2830. /* qsort - sort array a (dimension n) using quicksort
  2831.  * based on Bentley, CACM April 84
  2832.  * Comments use notation A[i], a (fictitious) array of things
  2833.  * that are of size elt_size.
  2834.  */
  2835. #include "local.h"
  2836. /* swapfn - swap  elt_size bytes  a <--> b (internal routine) 
  2837.  */
  2838. static void swapfn(a, b, elt_size)
  2839.     register char *a;    /* pointer to one element of A */
  2840.     register char *b;    /* pointer to another element of A */
  2841.     size_t elt_size;    /* size of each element */
  2842.     {
  2843.     register size_t i;
  2844.     char tmp;
  2845.  
  2846.     for (i = 0; i < elt_size; ++i, ++a, ++b)
  2847.         SWAP(*a, *b, tmp);
  2848.     }                                                                                                                                  /*
  2849. .PE
  2850. .PS 25
  2851. /* iqsort - internal quicksort routine */
  2852. static void iqsort(p_lo, p_hi, elt_size, cmpfn)
  2853.     char *p_lo;            /* ptr to low element of (sub)array */
  2854.     char *p_hi;            /* ptr to high element of (sub)array */
  2855.     size_t elt_size;    /* size of each element */
  2856.     int (*cmpfn)();        /* comparison function ptr */
  2857.     {
  2858.     char *p_mid = p_lo + ((((p_hi - p_lo) / elt_size) / 2) * elt_size);
  2859.     register char *p_i;            /* pointer to A[i] */
  2860.     register char *p_lastlo;    /* pointer to A[lastlo] */
  2861.  
  2862.     swapfn(p_lo, p_mid, elt_size);    /* pick the middle element as pivot */
  2863.     p_lastlo = p_lo;
  2864.     for (p_i = p_lo + elt_size;  p_i <= p_hi; p_i += elt_size)
  2865.         {
  2866.         if ((*cmpfn)(p_lo, p_i) > 0)
  2867.             {
  2868.             p_lastlo += elt_size;
  2869.             swapfn(p_lastlo, p_i, elt_size);
  2870.             }
  2871.         }
  2872.     swapfn(p_lo, p_lastlo, elt_size);
  2873.     if (p_lo < p_lastlo && p_lo < p_lastlo - elt_size)
  2874.         iqsort(p_lo, p_lastlo - elt_size, elt_size, cmpfn);    /* lower */
  2875.     if (p_lastlo + elt_size < p_hi)
  2876.         iqsort(p_lastlo + elt_size, p_hi, elt_size, cmpfn);    /* upper */
  2877.     }                                                                                                                                  /*
  2878. .PE
  2879. .PS 9
  2880. /* qsort - the callable entry point */
  2881. void qsort(a, n, size, pf)
  2882.     data_ptr a;        /* address of array A to be sorted */
  2883.     size_t n;        /* number of elements in A */
  2884.     size_t size;    /* size of each element */
  2885.     int (*pf)();    /* comparison function ptr */
  2886.     {
  2887.     if (n > 1)
  2888.         iqsort((char *)a, (char *)a + (n-1) * size, size, pf);
  2889.     }
  2890. ###qsortm.c
  2891. /* qsortm - test the qsort function
  2892.  */
  2893. #include "local.h"
  2894. #include "cputim.h"
  2895. /* cmpfn - compare two ints
  2896.  */
  2897. int cmpfn(pi, pj)
  2898.     register int *pi, *pj;
  2899.     {
  2900.     if (*pi < *pj)
  2901.         return (-1);
  2902.     else if (*pi == *pj)
  2903.         return (0);
  2904.     else
  2905.         return (1);
  2906.     }
  2907. /* qsortm (main) - run the test */
  2908. main(ac, av)
  2909.     int ac;
  2910.     char *av[];
  2911.     {
  2912.     int i;
  2913.     int lim;
  2914.     static int a[10000];
  2915.     double nlogn;
  2916.     double tim;    /* in usec */
  2917.     cputim_t cputim();
  2918.  
  2919.     lim = atoi(av[1]);
  2920.     printf("lim=%d\n", lim);
  2921.     for (i = 0; i < lim; ++i)
  2922.         a[i] = rand();
  2923. #if 0
  2924.     if (lim <= 100)
  2925.         for (i = 0; i < lim; ++i)
  2926.             printf("%5d\n", a[i]);
  2927. #endif
  2928.     printf("start:\n");
  2929.     cputim();
  2930.     qsort((data_ptr)a, lim, sizeof(int), cmpfn);
  2931.     tim = 1e6 * (double)cputim() / CLOCK_TICKS_PER_SECOND;
  2932. #if 0
  2933.     if (lim <= 100)
  2934.         for (i = 0; i < lim; ++i)
  2935.             printf("%5d\n", a[i]);
  2936. #endif
  2937.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  2938.     nlogn = lim * log((double)lim) / log(2.);
  2939.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  2940.     printf("N log N = %.3f\n", nlogn);
  2941.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  2942.     for (i = 0; i < lim-1; ++i)
  2943.         {
  2944.         if (a[i] > a[i+1])
  2945.             error("bad value", "");
  2946.         }
  2947.     exit(SUCCEED);
  2948.     }
  2949. ###qsortm.out
  2950. qsortm.x 100
  2951. lim=100
  2952. cpu time = 0.267 (sec)
  2953. log N = 6.644
  2954. N log N = 664.386
  2955. cpu time = 401.37 N log N (usec)
  2956. qsortm.x 1000
  2957. lim=1000
  2958. cpu time = 3.633 (sec)
  2959. log N = 9.966
  2960. N log N = 9965.784
  2961. cpu time = 364.58 N log N (usec)
  2962. qsortm.x 10000
  2963. lim=10000
  2964. cpu time = 44.000 (sec)
  2965. log N = 13.288
  2966. N log N = 132877.124
  2967. cpu time = 331.13 N log N (usec)
  2968. ###rec_close.c
  2969. /* rec_close - close the REC_FILE fd */
  2970. #include "rec_io.h"
  2971. int rec_close(fd)
  2972.     rec_fd fd;
  2973.     {
  2974.     REC_FILE *rfp;
  2975.     int old_errno = errno;
  2976.  
  2977.     errno = 0;
  2978.     if (fd < 0 || fd >= REC_NFILE)        /* validate fd */
  2979.         return (-1);
  2980.     rfp = &rec_files[fd];
  2981.     if ((rfp->_status & O_RWMODE) == O_RDONLY)
  2982.         return (bin_close(fd));            /* if read-only, all done */
  2983.     bin_lseek(fd, (long)0, SEEK_SET);    
  2984.     bin_write(fd, rfp, sizeof(*rfp));    /* write new REC_FILE info */
  2985.     bin_close(fd);
  2986.     if (errno == 0)
  2987.         {
  2988.         errno = old_errno;
  2989.         return (0);
  2990.         }
  2991.     else
  2992.         {
  2993.         return (-1);
  2994.         }
  2995.     }
  2996. ###rec_files.c
  2997. /* rec_files - global array of REC_FILEs */
  2998. #include "rec_io.h"
  2999. REC_FILE rec_files[REC_NFILE] = {0};
  3000. ###rec_get.c
  3001. /* rec_get - read one record from record-binary file */
  3002. #include "rec_io.h"
  3003. bool rec_get(fd, buf, recno)
  3004.     rec_fd fd;        /* which file */
  3005.     data_ptr buf;    /* where to put the data */
  3006.     long recno;        /* {REC_NEXT,0:rec_nrecs(fd)-1} */
  3007.     {
  3008.     REC_FILE *rfp;
  3009.     short n;        /* size of each record */
  3010.  
  3011.     if (fd < 0 || fd >= REC_NFILE)    /* validate fd */
  3012.         return (NO);
  3013.     rfp = &rec_files[fd];
  3014.     n = rfp->_recsize;
  3015.     if (recno != REC_NEXT && recno < 0 || recno >= rfp->_nrecs)
  3016.         return (NO);
  3017.     else if (recno == REC_NEXT)
  3018.         ;    /* no seek, ready for next record */
  3019.     else if (bin_lseek(fd, rfp->_byte0 + recno * n, SEEK_SET) < 0)
  3020.         return (NO);
  3021.     return (bin_read(fd, buf, n) == n);
  3022.     }
  3023. ###rec_havail.c
  3024. /* rec_havail.c -- find where a record belongs in a hashed file */
  3025. #include "rec_io.h"
  3026.  
  3027. long rec_havail(fd, keybuf, buf, hashfn)
  3028.     rec_fd fd;            /* hashed file */
  3029.     data_ptr keybuf;    /* record key to find */
  3030.     data_ptr buf;        /* buffer for found record */
  3031.     long (*hashfn)();    /* hash lookup function */
  3032.     {
  3033.     long nrecs;            /* number of records in file */
  3034.     long ntry;
  3035.     long i;
  3036.  
  3037.     nrecs = rec_nrecs(fd);
  3038.     i = (*hashfn)(keybuf);
  3039.     for (ntry = 0; ntry < nrecs; ++ntry)
  3040.         {
  3041.         if (!rec_get(fd, buf, i))
  3042.             return (REC_ERROR);
  3043.         if (*(char *)buf == REC_AVAIL || *(char *)buf == REC_DELET)
  3044.             return (i);
  3045.         i = IMOD(i + 1, nrecs);
  3046.         }
  3047.     return (REC_FULL);
  3048.     }
  3049. ###rec_hfind.c
  3050. /* rec_hfind.c -- find a record in a hashed file */
  3051. #include "rec_io.h"
  3052.  
  3053. long rec_hfind(fd, keybuf, buf, cmpfn, hashfn)
  3054.     rec_fd fd;            /* hashed file */
  3055.     data_ptr keybuf;    /* record key to find */
  3056.     data_ptr buf;        /* buffer for found record */
  3057.     int (*cmpfn)();        /* record key comparison function */
  3058.     long (*hashfn)();    /* hash lookup function */
  3059.     {
  3060.     long nrecs;            /* number of records in file */
  3061.     long ntry;
  3062.     long i;
  3063.  
  3064.     nrecs = rec_nrecs(fd);
  3065.     i = (*hashfn)(keybuf);
  3066.     for (ntry = 0; ntry < nrecs; ++ntry)
  3067.         {
  3068.         if (!rec_get(fd, buf, i))
  3069.             return (REC_ERROR);                /* i/o error during rec_get */
  3070.         if (*(char *)buf == REC_AVAIL)        /* examine first byte of buf */
  3071.             return (REC_NOT_FOUND);
  3072.         if (*(char *)buf == REC_OCCUP)
  3073.             {
  3074.             if ((*cmpfn)(keybuf, buf) == 0)
  3075.                     return (i);
  3076.             }
  3077.         i = IMOD(i + 1, nrecs);
  3078.         }
  3079.     return (REC_FULL);
  3080.     }
  3081. ###rec_main.c
  3082. /* rec_main - simple test harness for rec_io */
  3083. #include "local.h"
  3084. #include "rec_io.h"
  3085.  
  3086. main()
  3087.     {
  3088.     long lnum;
  3089.     long rec_no;
  3090.     rec_fd rfd;
  3091.  
  3092.     rfd = rec_open("lnum.dat", O_WRONLY|O_CREAT|O_TRUNC, sizeof(lnum));
  3093.     if (rfd < 0)
  3094.         error("can't open (output)", "lnum.dat");
  3095.     for (lnum = 0; lnum <= 9; ++lnum)
  3096.         if (!rec_put(rfd, (data_ptr)&lnum, REC_W_END))
  3097.             error("rec_put (END) error", "");
  3098.     rec_close(rfd);
  3099.  
  3100.     rfd = rec_open("lnum.dat", O_RDONLY, sizeof(lnum));
  3101.     if (rfd < 0)
  3102.         error("can't open (input)", "lnum.dat");
  3103.     while (rec_get(rfd, (data_ptr)&lnum, REC_NEXT))
  3104.         printf("%4ld\n", lnum);
  3105.     rec_close(rfd);
  3106.  
  3107.     rfd = rec_open("lnum.dat", O_RDWR, sizeof(lnum));
  3108.     if (rfd < 0)
  3109.         error("can't open (update-output)", "lnum.dat");
  3110.     for (lnum = 109; lnum >= 100; --lnum)
  3111.         if (!rec_put(rfd, (data_ptr)&lnum, lnum - 100))
  3112.             error("rec_put (direct) error", "");
  3113.     rec_close(rfd);
  3114.  
  3115.     rfd = rec_open("lnum.dat", O_RDWR, sizeof(lnum));
  3116.     if (rfd < 0)
  3117.         error("can't open (update-input)", "lnum.dat");
  3118.     for (rec_no = 0; rec_no <= 9; ++rec_no)
  3119.         {
  3120.         if (!rec_get(rfd, (data_ptr)&lnum, rec_no))
  3121.             error("rec_get (direct) error", "");
  3122.         else if (lnum != rec_no + 100)
  3123.             error("bad data on re-read", "");
  3124.         else
  3125.             printf("%4ld %4ld\n", rec_no, lnum);
  3126.         }
  3127.     rec_close(rfd);
  3128.     exit(SUCCEED);
  3129.     }
  3130. ###rec_open.c
  3131. /* rec_open - open a record-binary file */
  3132. #include "rec_io.h"
  3133. REC_FILE rec_files[REC_NFILE] = {0};
  3134. rec_fd rec_open(fname, type, recsize)
  3135.     char fname[];
  3136.     int type;
  3137.     int recsize;
  3138.     {
  3139.     rec_fd fd;
  3140.     REC_FILE *rfp;            /* pointer to a REC_FILE entry */
  3141.     int old_errno = errno;    /* save system error indicator */
  3142.     short i;                /* counter to clear first record */
  3143.  
  3144.     errno = 0;                /* clear error indicator */
  3145.     fd = bin_open(fname, type);
  3146.     if (fd < 0 || fd >= REC_NFILE)    /* validate fd */
  3147.         return (-1);
  3148.     rfp = &rec_files[fd];
  3149.     bin_lseek(fd, (long)0, SEEK_SET);    /* seek to initial byte of file */
  3150.     if ((type & O_RWMODE) == O_WRONLY ||    /* new file: opened write-only, or */
  3151.         bin_read(fd, rfp, sizeof(*rfp)) != sizeof(*rfp))    /* can't be read */
  3152.         {
  3153.         bin_lseek(fd, (long)0, SEEK_SET);
  3154.         rfp->_byte0 = REC_BYTE0;
  3155.         rfp->_recsize = recsize;
  3156.         rfp->_nrecs = 0;
  3157.         bin_write(fd, rfp, sizeof(*rfp));
  3158.         for (i = 1; i <= REC_BYTE0 - sizeof(*rfp); ++i)
  3159.             bin_write(fd, "\0", 1);
  3160.         }
  3161.     else if (recsize != rfp->_recsize)    /* file exists, but bad recsize */
  3162.         {
  3163.         bin_close(fd);
  3164.         return (-1);
  3165.         }
  3166.     if (errno == 0)
  3167.         {
  3168.         errno = old_errno;                /* restore saved value */
  3169.         bin_lseek(fd, (long)rfp->_byte0, 0);
  3170.         rfp->_status = type;            /* save the open-mode of file */
  3171.         return (fd);
  3172.         }
  3173.     else /* error was returned from some bin_io function */
  3174.         {
  3175.         bin_close(fd);
  3176.         return (-1);
  3177.         }
  3178.     }
  3179. ###rec_put.c
  3180. /* rec_put - write one record to record-binary file
  3181.  */
  3182. #include "rec_io.h"
  3183. bool rec_put(fd, buf, recno)
  3184.     rec_fd fd;
  3185.     data_ptr buf;    /* where to get the data */
  3186.     long recno;        /* {REC_W_END,REC_NEXT,0:rec_nrecs(fd)} */
  3187.     {
  3188.     REC_FILE *rfp;
  3189.     short n;        /* size of each record */
  3190.  
  3191.     if (fd < 0 || fd >= REC_NFILE)
  3192.         return (NO);
  3193.     rfp = &rec_files[fd];
  3194.     n = rfp->_recsize;
  3195.     if (recno != REC_NEXT && recno != REC_W_END && recno < 0 ||
  3196.         recno > rfp->_nrecs)
  3197.         return (NO);
  3198.     else if (recno == REC_W_END || recno == rfp->_nrecs)
  3199.         {
  3200.         recno = rfp->_nrecs;    /* block will be added at end */
  3201.         ++rfp->_nrecs;            /* extend the file size */
  3202.         }
  3203.     if (bin_lseek(fd, rfp->_byte0 + recno * n, SEEK_SET) < 0)
  3204.         return (NO);
  3205.     return (bin_write(fd, buf, n) == n);
  3206.     }
  3207. ###reverse.c
  3208. /* reverse - reverse the order of a string */
  3209. #include "local.h"
  3210. void reverse(s)
  3211.     char s[];
  3212.     {
  3213.     char t;
  3214.     size_t i, j;
  3215.  
  3216.     if ((j = strlen(s)) == 0)
  3217.         return;
  3218.     for (i = 0, j = j - 1; i < j; ++i, --j)
  3219.         SWAP(s[i], s[j], t);
  3220.     }
  3221. ###round.c
  3222. /* round - adjust floating dollars to even pennies */
  3223. #include "local.h"
  3224. double round(dollars)
  3225.     double dollars;
  3226.     {
  3227.     double pennies;
  3228.  
  3229.     pennies = floor(dollars * 100 + .5);
  3230.     return (pennies / 100.);
  3231.     }
  3232. ###roundup.c
  3233. /* roundup - adjust floating dollars to even pennies
  3234.  * round all fractional pennies upward
  3235.  */
  3236. #include "local.h"
  3237. double roundup(dollars)
  3238.     double dollars;
  3239.     {
  3240.     double pennies;
  3241.  
  3242.     pennies = ceil(dollars * 100.);
  3243.     return (pennies / 100.);
  3244.     }
  3245. ###run_cars.c
  3246. /* run_cars - simulate airport terminal train cars */
  3247. #include "deque.h"
  3248. #include "screen.h"
  3249. #define TRKSIZE 1000
  3250. #define CAR struct car
  3251. CAR
  3252.     {
  3253.     CAR *left;        /* pointer to previous deque node; !NULL */
  3254.     CAR *right;        /* pointer to next deque node; !NULL */
  3255.     short pos;        /* position on track; {0:TRKSIZE-1} */
  3256.     short vel;        /* velocity; {0:SHORT_MAX} */
  3257.     char ident[2];    /* identifier for this car; {"a":"z"} */
  3258.     };
  3259. void init();            /* initialize the simulation */
  3260. void run();                /* run one time step */
  3261. DQ_NODE *cars = NULL;    /* pointer to master deque node */
  3262. CAR *p = NULL;            /* pointer to a CAR */
  3263. short ncars = 0;        /* number of cars on track; {2:26} */
  3264. char idents[] = "abcdefghijklmnopqrstuvwxyz";
  3265. main(ac, av)
  3266.     int ac;
  3267.     char *av[];
  3268.     {
  3269.     short t;            /* loop counter */
  3270.     SCR_CMDCHAR c;        /* input from keyboard */
  3271.  
  3272.     if (ac < 2)
  3273.         error("usage: run_cars  #-of-cars", "");
  3274.     ncars = atoi(av[1]);
  3275.     if (ncars < 2 || ncars > 26)
  3276.         error("#-of-cars must be between 2 and 26", "");
  3277.     scr_open();
  3278.     scr_clear();
  3279.     scr_curs(21, 40); scr_putc('A');
  3280.     scr_curs(11, 75); scr_putc('B');
  3281.     scr_curs( 1, 40); scr_putc('C');
  3282.     scr_curs(11,  5); scr_putc('D');
  3283.     init();
  3284.     do {
  3285.         for (t = 0; t < 200; ++t)
  3286.             run();
  3287.         scr_curs(scr_lins - 1, 0);
  3288.         scr_print("More? ");
  3289.         scr_refresh();
  3290.         c = scr_getkey();
  3291.         scr_putc(c);
  3292.         } while (c == 'y');
  3293.     scr_close();
  3294.     exit(SUCCEED);
  3295.     }                                                                                                                                                                                   /*
  3296. .PE
  3297. .PS 50
  3298. /* init - initialize the simulation */
  3299. void init()
  3300.     {
  3301.     short i;            /* loop counter; {0:ncars-1} */
  3302.  
  3303.     DQ_OPEN(&cars);
  3304.     for (i = 0; i < ncars; ++i)
  3305.         {
  3306.         p = (CAR *)malloc(sizeof(CAR));
  3307.         if (p == NULL)
  3308.             error("out of space", "");
  3309.         p->pos = i * (TRKSIZE / ncars);
  3310.         p->vel = 0;
  3311.         p->ident[0] = idents[i];
  3312.         p->ident[1] = '\0';
  3313.         DQ_APPEND(cars, p);
  3314.         }
  3315.     }
  3316. /* run - run the simulation for one time step */
  3317. void run()
  3318.     {
  3319.     short to_station;    /* distance to next station */
  3320.     short to_car;        /* distance to next car */
  3321.     short to_stop;        /* safe distance required to stop this car */
  3322.     short i;            /* loop counter */
  3323.     CAR *psucc;            /* ptr to successor of car p */
  3324.  
  3325.     EACH_DQ(cars, p, CAR)
  3326.         {
  3327.         plot_trk(p->pos / (TRKSIZE/100), ' ');
  3328.         p->pos = IMOD(p->pos + p->vel, TRKSIZE);
  3329.         plot_trk(p->pos / (TRKSIZE/100), p->ident[0]);
  3330.         to_station = IMOD(p->pos, TRKSIZE / 4);
  3331.         psucc = (CAR *)DQ_SUCC(cars, p);
  3332.         to_car = IMOD(psucc->pos - p->pos, TRKSIZE);
  3333.         for (i = 1, to_stop = 0; i <= p->vel+1; ++i)
  3334.             to_stop += i;
  3335.         if (to_car < 10)
  3336.             p->vel = 0;                /* screeching halt */
  3337.         else if (to_station <= 5)
  3338.             p->vel = rand() & 0x1;    /* random jerk in station */
  3339.         else if (MIN(to_station, to_car) < to_stop && p->vel > 0)
  3340.             --p->vel;                /* slow down */
  3341.         else
  3342.             ++p->vel;                /* speed up */
  3343.         }
  3344.     scr_refresh();
  3345.     }
  3346. ###screen.c
  3347. /* screen - environment-specific terminal functions
  3348.  * Idris version for ANSI terminal
  3349.  */
  3350. #include "local.h"
  3351. #include "screen.h"
  3352. #define get_7bit_char() (getchar() & 0177)    /* "raw" getchar never EOF */
  3353. short scr_mode = SCR_TTY;    /* screen mode - TTY or RAW */
  3354. short scr_lines = 24;    /* screen lines (default) */
  3355. short scr_cols = 80;    /* screen columns (default) */
  3356. /* scr_getkey - get a (coded) keyboard char */
  3357. SCR_CMDCHAR scr_getkey()
  3358.     {
  3359.     char c1, c2, c3;
  3360.     
  3361.     if ((c1 = get_7bit_char()) != '\33')
  3362.         return (c1);
  3363.     else if ((c2 = get_7bit_char()) == 'O')
  3364.         {
  3365.         if ((c3 = get_7bit_char()) == 'S')
  3366.             return (SCR_EXIT);
  3367.         return (getkey());
  3368.         }
  3369.     else if (c2 == '[')
  3370.         {
  3371.         switch (c3 = get_7bit_char())
  3372.             {
  3373.         case 'A':    return (SCR_UP);    /* no "break" needed - all returns */
  3374.         case 'B':    return (SCR_DOWN);
  3375.         case 'C':    return (SCR_RIGHT);
  3376.         case 'D':    return (SCR_LEFT);
  3377.         case 'H':    return (SCR_HOME);
  3378.         default:    return (scr_getkey());
  3379.             }
  3380.         }
  3381.     else
  3382.         return (scr_getkey());
  3383.     }
  3384. /* remark - print error message, appropriate for scr_mode */
  3385. void remark(s1, s2)
  3386.     char s1[], s2[];    /* strings to be printed */
  3387.     {
  3388.     if (scr_mode == SCR_TTY)
  3389.         fprintf(stderr, "%s %s\n", s1, s2);
  3390.     else
  3391.         {
  3392.         scr_curs(scr_lines-1, 0);
  3393.         scr_print("%s %s; hit any key to continue", s1, s2);
  3394.         scr_getkey();
  3395.         /* clear message from screen after response */
  3396.         /* print 79 spaces, 80 would cause CR on last line
  3397.         **     screen would scroll up (on most terminals  
  3398.         */
  3399.         scr_curs(scr_lines-1, 0);
  3400.         scr_print("                                                    ");
  3401.         scr_print("                           ");
  3402.         }
  3403.     }
  3404. /* (new page)
  3405. .PE
  3406. .PS
  3407.  */
  3408. /* scr_open - initialize the terminal
  3409.  */
  3410. void scr_open()
  3411.     {
  3412.     system("stty +raw -echo");    /* slow but universal */
  3413.     printf("\33[>6h");            /* enter keypad-shifted mode */
  3414.     scr_mode = SCR_RAW;
  3415.     }
  3416. /* scr_close - re-establish normal terminal environment
  3417.  */
  3418. void scr_close()
  3419.     {
  3420.     printf("\33[>6l");            /* exit keypad-shifted mode */
  3421.     system("stty -raw +echo");    /* slow but universal */
  3422.     scr_mode = SCR_TTY;
  3423.     }
  3424. ###screen86.c
  3425. /* screen - environment-specific terminal functions
  3426.  * PC Version - uses  bdos  function
  3427.  */
  3428. #include "local.h"
  3429. #include "screen.h"
  3430. short scr_mode = SCR_TTY;    /* screen mode - TTY or RAW */
  3431. short scr_lins = 24;    /* screen lines (default) */
  3432. short scr_cols = 80;    /* screen columns (default) */
  3433. /* scr_getkey - get a (coded) keyboard char */
  3434. SCR_CMDCHAR scr_getkey()
  3435.     {
  3436.     char c1;
  3437.     
  3438.     scr_refresh();
  3439.     if ((c1 = bdos(8)) != '\0')
  3440.         return (c1 & 0x7F);
  3441.     switch (c1 = bdos(8))
  3442.         {
  3443.     /* no "break" needed - all returns */
  3444.     case 'H':    return (SCR_UP);
  3445.     case 'P':    return (SCR_DOWN);
  3446.     case 'M':    return (SCR_RIGHT);
  3447.     case 'K':    return (SCR_LEFT);
  3448.     case 'G':    return (SCR_HOME);
  3449.     case ';':    return (SCR_EXIT);    /* F1 function key */
  3450.     default:    scr_beep();
  3451.                 return (scr_getkey());
  3452.         }
  3453.     }
  3454. /* remark - print error message, appropriate for scr_mode */
  3455. void remark(s1, s2)
  3456.     char s1[], s2[];    /* strings to be printed */
  3457.     {
  3458.     if (scr_mode == SCR_TTY)
  3459.         fprintf(stderr, "%s %s\n", s1, s2);
  3460.     else
  3461.         {
  3462.         scr_curs(scr_lins-1, 0);
  3463.         scr_print("%s %s; hit any key to continue", s1, s2);
  3464.         scr_getkey();
  3465.         scr_curs(scr_lins-1, 0);
  3466.         scr_cel();
  3467.         }
  3468.     }
  3469. /* scr_open - enter "raw" screen mode */
  3470. void scr_open()
  3471.     {
  3472.     scr_mode = SCR_RAW;    /* otherwise no work; bdos(8) is unbuffered */
  3473.     }                                                                                /*
  3474. .PE
  3475. .PS
  3476. /* scr_close - restore normal tty state */
  3477. void scr_close()
  3478.     {
  3479.     scr_mode = SCR_TTY;
  3480.     }
  3481. ###screenU.c
  3482. /* screen - environment-specific terminal functions
  3483.  * UNIX version for ANSI terminal
  3484.  */
  3485. #include "local.h"
  3486. #include "screen.h"
  3487. #define get_7bit_char() (getchar() & 0177)    /* "raw" getchar never EOF */
  3488. short scr_mode = SCR_TTY;    /* screen mode - TTY or RAW */
  3489. short scr_lins = 24;    /* screen lines (default) */
  3490. short scr_cols = 80;    /* screen columns (default) */
  3491. /* scr_getkey - get a (coded) keyboard char */
  3492. SCR_CMDCHAR scr_getkey()
  3493.     {
  3494.     char c1, c2;
  3495.     
  3496.     scr_refresh();
  3497.     if ((c1 = get_7bit_char()) != '\33')
  3498.         return (c1);
  3499.     else if ((c2 = get_7bit_char()) == 'O')
  3500.         {
  3501.         if (get_7bit_char() == 'S')        /* F1 function key */
  3502.             return (SCR_EXIT);
  3503.         scr_beep();
  3504.         return (scr_getkey());
  3505.         }
  3506.     else if (c2 == '[')
  3507.         {
  3508.         switch (get_7bit_char())
  3509.             {
  3510.         case 'A':    return (SCR_UP);    /* no "break" needed - all returns */
  3511.         case 'B':    return (SCR_DOWN);
  3512.         case 'C':    return (SCR_RIGHT);
  3513.         case 'D':    return (SCR_LEFT);
  3514.         case 'H':    return (SCR_HOME);
  3515.         default:    scr_beep();
  3516.                     return (scr_getkey());
  3517.             }
  3518.         }
  3519.     else
  3520.         {
  3521.         scr_beep();
  3522.         return (scr_getkey());
  3523.         }
  3524.     }                                                                                                                                              /*
  3525. .PE
  3526. .PS 30
  3527. /* remark - print error message, appropriate for scr_mode */
  3528. void remark(s1, s2)
  3529.     char s1[], s2[];    /* strings to be printed */
  3530.     {
  3531.     if (scr_mode == SCR_TTY)
  3532.         fprintf(stderr, "%s %s\n", s1, s2);
  3533.     else
  3534.         {
  3535.         scr_curs(scr_lins-1, 0);
  3536.         scr_print("%s %s; hit any key to continue", s1, s2);
  3537.         scr_getkey();
  3538.         scr_curs(scr_lins-1, 0);
  3539.         scr_cel();
  3540.         }
  3541.     }
  3542. /* scr_open - initialize the terminal */
  3543. void scr_open()
  3544.     {
  3545.     system("stty raw -echo");    /* slow but universal */
  3546.     printf("\33[>6h");            /* keypad-shifted; not universal ANSI */
  3547.     scr_mode = SCR_RAW;
  3548.     }
  3549. /* scr_close - re-establish normal terminal environment */
  3550. void scr_close()
  3551.     {
  3552.     printf("\33[>6l");            /* exit keypad-shifted mode */
  3553.     system("stty -raw echo");    /* slow but universal */
  3554.     scr_mode = SCR_TTY;
  3555.     }
  3556. ###short_order.c
  3557. /* short_order - put two short integers into order
  3558.  */
  3559. #include "local.h"
  3560. void short_order(pi, pj)
  3561.     short *pi, *pj;
  3562.     {
  3563.     short t;
  3564.  
  3565.     if (*pj < *pi)
  3566.         t = *pi, *pi = *pj, *pj = t;
  3567.     }
  3568. ###sisort.c
  3569. /* sisort - string version of isort
  3570.  * sorts an array of pointers to char
  3571.  */
  3572. #define ISORT_NAME sisort
  3573. #define ISORT_TYPE char *
  3574. #define ISORT_GT(a, b) (strcmp(a, b) > 0)
  3575. #include "isort.h"
  3576. ###sqksort.c
  3577. /* sqksort - string version of qksort
  3578.  */
  3579. #define QKSORT_NAME sqksort
  3580. #define QKSORT_TYPE char *
  3581. #define QKSORT_GT(a, b) (strcmp(a, b) > 0)
  3582. #include "qksort.h"
  3583. ###sqksortm.c
  3584. /* sqksort - string version of qksort
  3585.  */
  3586. #define QKSORT_NAME sqksort
  3587. #define QKSORT_TYPE char *
  3588. #define QKSORT_GT(a, b) (strcmp(a, b) > 0)
  3589. #include "qksort.h"
  3590. #ifdef TRYMAIN
  3591. #include <math.h>
  3592. main(ac, av)
  3593.     int ac;
  3594.     char *av[];
  3595.     {
  3596.     int i;
  3597.     int lim;
  3598.     static char * a[10000];
  3599.     static char pie[10001] = {0};
  3600.     double nlogn;
  3601.     double tim;
  3602.     long cputim();
  3603.  
  3604.     lim = atoi(av[1]);
  3605.     printf("lim=%d\n", lim);
  3606.     for (i = 0; i < 10000; ++i)
  3607.         pie[i] = rand() & 63;
  3608.     for (i = 0; i < lim; ++i)
  3609.         a[i] = &pie[rand() % 10000];
  3610.     cputim();
  3611.     QKSORT_NAME(a, lim);
  3612.     tim = cputim() * 1e6 / 60;
  3613.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  3614.     nlogn = lim * log((double)lim) / log(2.);
  3615.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  3616.     printf("N log N = %.3f\n", nlogn);
  3617.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  3618.     for (i = 0; i < lim-1; ++i)
  3619.         {
  3620.         if (QKSORT_GT(a[i], a[i+1]))
  3621.             error("bad value", "");
  3622.         }
  3623.     exit(SUCCEED);
  3624.     }
  3625. #endif
  3626. ###sqksortm2.c
  3627. /* sqksort - string version of qksort
  3628.  */
  3629. #define QKSORT_NAME sqksort
  3630. #define QKSORT_TYPE char *
  3631. #define QKSORT_GT(a, b) \
  3632.     ((a)[0] != (b)[0] ? (a)[0] > (b)[0] : strcmp(a, b) > 0)
  3633. #include "qksort.h"
  3634. #ifdef TRYMAIN
  3635. #include <math.h>
  3636. main(ac, av)
  3637.     int ac;
  3638.     char *av[];
  3639.     {
  3640.     int i;
  3641.     int lim;
  3642.     static char * a[10000];
  3643.     static char pie[10001] = {0};
  3644.     double nlogn;
  3645.     double tim;
  3646.     long cputim();
  3647.  
  3648.     lim = atoi(av[1]);
  3649.     printf("lim=%d\n", lim);
  3650.     for (i = 0; i < 10000; ++i)
  3651.         pie[i] = rand() & 63;
  3652.     for (i = 0; i < lim; ++i)
  3653.         a[i] = &pie[rand() % 10000];
  3654.     cputim();
  3655.     QKSORT_NAME(a, lim);
  3656.     tim = cputim() * 1e6 / 60;
  3657.     printf("cpu time = %.3f (sec)\n", tim / 1e6);
  3658.     nlogn = lim * log((double)lim) / log(2.);
  3659.     printf("log N = %.3f\n", log((double)lim) / log(2.));
  3660.     printf("N log N = %.3f\n", nlogn);
  3661.     printf("cpu time = %.2f N log N (usec)\n", tim / nlogn);
  3662.     for (i = 0; i < lim-1; ++i)
  3663.         {
  3664.         if (QKSORT_GT(a[i], a[i+1]))
  3665.             error("bad value", "");
  3666.         }
  3667.     exit(SUCCEED);
  3668.     }
  3669. #endif
  3670. ###sqrtx.c
  3671. /* sqrttst - test accuracy of sqrt
  3672.  */
  3673. #include "local.h"
  3674. main()
  3675.     {
  3676.     double x, y;
  3677.  
  3678.     for (x = 1.; x <= 25.; x = x + 1.)
  3679.         {
  3680.         y = sqrt(x) * sqrt(x);
  3681.         if (y != x)
  3682.             printf("%5.1f %21.17f %10.2e\n", x, y, x-y);
  3683.         }
  3684.     }
  3685. ###sqrtx.out
  3686.   2.0   2.00000000000000010  -5.55e-17
  3687.   3.0   3.00000000000000010  -5.55e-17
  3688.   7.0   6.99999999999999990   2.22e-16
  3689.   8.0   8.00000000000000020  -2.22e-16
  3690.  10.0  10.00000000000000000  -2.22e-16
  3691.  12.0  12.00000000000000000  -2.22e-16
  3692.  15.0  15.00000000000000000  -2.22e-16
  3693.  17.0  17.00000000000000100  -4.44e-16
  3694.  18.0  18.00000000000000000   4.44e-16
  3695.  21.0  21.00000000000000000   4.44e-16
  3696.  22.0  22.00000000000000000   4.44e-16
  3697.  23.0  22.99999999999999900   8.88e-16
  3698. ###sqrtx86.out
  3699.   2.0   2.00000000000000044  -4.44E-16
  3700.   3.0   2.99999999999999955   4.44E-16
  3701.   5.0   5.00000000000000088  -8.88E-16
  3702.   6.0   5.99999999999999911   8.88E-16
  3703.   7.0   7.00000000000000088  -8.88E-16
  3704.   8.0   8.00000000000000177  -1.78E-15
  3705.  10.0  10.00000000000000176  -1.78E-15
  3706.  12.0  11.99999999999999821   1.78E-15
  3707.  13.0  12.99999999999999822   1.78E-15
  3708.  15.0  15.00000000000000176  -1.78E-15
  3709.  18.0  17.99999999999999642   3.55E-15
  3710.  19.0  19.00000000000000355  -3.55E-15
  3711.  20.0  20.00000000000000353  -3.55E-15
  3712.  23.0  22.99999999999999642   3.55E-15
  3713.  24.0  23.99999999999999642   3.55E-15
  3714. ###st_close.c
  3715. /* st_close - close the stack accessed via *headp */
  3716. #include "stack.h"
  3717. void st_close(headp)
  3718.     ST_NODE **headp;
  3719.     {
  3720.     ST_NODE *p;
  3721.     ST_NODE *pnext;
  3722.  
  3723.     for (p = *headp; p != NULL; p = pnext)
  3724.         {
  3725.         pnext = p->next;
  3726.         free(p);    /* p is (momentarily) undefined */
  3727.         }
  3728.     *headp = NULL;        /* prevent dangling ptr */
  3729.     }
  3730. ###st_main.c
  3731. /* st_main - test routine for stack package
  3732.  */
  3733. #include "local.h"
  3734. #include "stack.h"
  3735.  
  3736. #define NAME_NODE struct name_node
  3737. NAME_NODE
  3738.     {
  3739.     NAME_NODE *next;
  3740.     char data[4];
  3741.     };
  3742. NAME_NODE *head = NULL;        /* head node of stack */
  3743. NAME_NODE *p = NULL;        /* current node */
  3744. void show_cmds(), push_name(), pop_name(), dump_names();
  3745.                                                                                                                                                              /*
  3746. .PE
  3747. .PS 26
  3748. /* st_main (main) */
  3749. main()
  3750.     {
  3751.     char buf[2];            /* buffer for input */
  3752.  
  3753.     ST_OPEN(&head);            /* open the stack */
  3754.     show_cmds();
  3755.     while (getreply("?: ", buf, 2) != EOF)
  3756.         {
  3757.         switch (buf[0])
  3758.             {
  3759.         case '+':
  3760.             push_name();
  3761.             break;
  3762.         case '-':
  3763.             pop_name();
  3764.             break;
  3765.         case '=':
  3766.             dump_names();
  3767.             break;
  3768.         case '0':
  3769.             ST_CLOSE(&head);
  3770.             ST_OPEN(&head);        /* open the stack again */
  3771.             break;
  3772.         case '?':
  3773.             show_cmds();
  3774.             break;
  3775.         default:
  3776.             printf("unknown command: %c\n", buf[0]);
  3777.             show_cmds();
  3778.             break;
  3779.             }
  3780.         }
  3781.     exit(SUCCEED);
  3782.     }                                                                                                                                                                                      /*
  3783. .PE
  3784. .PS  30
  3785. /* show_cmds -- show legal commands */
  3786. void show_cmds()
  3787.     {
  3788.     printf("Type + to push, - to pop, = to print, 0 to reset:\n");
  3789.     }
  3790. /* push_name - push new name on stack */
  3791. void push_name()
  3792.     {
  3793.     p = (NAME_NODE *)malloc(sizeof(NAME_NODE));
  3794.     if (p == NULL)
  3795.         error("out of space", "");
  3796.     if (getreply("name: ", p->data, 4) == EOF)
  3797.          error("unexpected EOF", ""); 
  3798.     ST_PUSH(&head, p);
  3799.     }
  3800. /* pop_name - pop a name off stack */
  3801. void pop_name()
  3802.     {
  3803.     p = (NAME_NODE *)ST_POP(&head);
  3804.     if (p == NULL)
  3805.         printf("EMPTY STACK\n");
  3806.     else
  3807.         {
  3808.         printf("name= %s\n", p->data);
  3809.         free(p);
  3810.         }
  3811.     }
  3812. /* dump_names - print the current stack of names */
  3813. void dump_names()
  3814.     {
  3815.     if (ST_IS_EMPTY(head))
  3816.         printf("EMPTY STACK\n");
  3817.     else
  3818.         EACH_ST(head, p)
  3819.             printf("name= %s\n", p->data);
  3820.     }
  3821. ###st_pop.c
  3822. /* st_pop - detach top node of stack and return pointer to it */
  3823. #include "stack.h"
  3824. ST_NODE *st_pop(headp)
  3825.     ST_NODE **headp;
  3826.     {
  3827.     ST_NODE *p;
  3828.  
  3829.     if (*headp == NULL)
  3830.         return (NULL);
  3831.     p = *headp;            /* p points to top of stack */
  3832.     *headp = p->next;    /* headp now points to next node (or is NULL) */
  3833.     p->next = NULL;        /* prevent dangling ptr */
  3834.     return (p);
  3835.     }
  3836. ###st_push.c
  3837. /* st_push - install ST_NODE at head of stack */
  3838. #include "stack.h"
  3839. void st_push(headp, p)
  3840.     ST_NODE **headp;
  3841.     ST_NODE *p;
  3842.     {
  3843.     p->next = *headp;    /* p->next now points to previous head (or is NULL) */
  3844.     *headp = p;            /* *headp now points to p */
  3845.     }
  3846. ###strcspn.c
  3847. /* strcspn - xxx
  3848.  */
  3849. size_t strcspn(s1, s2)
  3850. char s1[];
  3851. char s2[];
  3852.     {                    /* strcspn */
  3853.     register size_t i;
  3854.     register char *p;
  3855.  
  3856.     for (i = 0;  s1[i] != '\0';  ++i)
  3857.         {
  3858.         for (p = s2;  *p != '\0';  ++p)
  3859.             {
  3860.             if (*p == s1[i])
  3861.                 return (i);
  3862.             }
  3863.         }
  3864.     return (i);
  3865.     }                    /* strcspn */
  3866. ###strfit.c
  3867. /* strfit - copy s2 to s1, chopping to n chars
  3868.  * return YES if sufficient space, no if not
  3869.  */
  3870. #include "local.h"
  3871.  
  3872. bool strfit(s1, s2, n)
  3873.     char s1[];
  3874.     char s2[];
  3875.     size_t n;
  3876.     {
  3877.     size_t i;
  3878.  
  3879.     for (i = 0; i < n-1 && s2[i] != '\0'; ++i)
  3880.         s1[i] = s2[i];
  3881.     s1[i] = '\0';
  3882.     return (s2[i] == '\0');
  3883.     }
  3884. ###strspn.c
  3885. /* strspn - xxx
  3886.  */
  3887. #include "local.h"
  3888. size_t strspn(s1, s2)
  3889. char s1[];
  3890. char s2[];
  3891.     {                    /* strspn */
  3892.     register size_t i;
  3893.     register char *p;
  3894.  
  3895.     for (i = 0;  s1[i] != '\0';  ++i)
  3896.         {
  3897.         for (p = s2;  *p != '\0';  ++p)
  3898.             {
  3899.             if (*p == s1[i])
  3900.                 break;
  3901.             }
  3902.         if (*p == '\0')
  3903.             return (i);
  3904.         }
  3905.     return (i);
  3906.     }                    /* strspn */
  3907. ###strtok.c
  3908. /* strtok - return pointer to next token in string
  3909.  */
  3910. #include "local.h"
  3911. static char *nextpos = NULL;
  3912.  
  3913. char *strtok(s1, s2)
  3914. char s1[];
  3915. char s2[];
  3916.     {                    /* strtok */
  3917.     char *returnp;
  3918.     size_t nchars;
  3919.  
  3920.     if (s1 != NULL)
  3921.         nextpos = s1;
  3922.     nchars = strspn(nextpos, s2);    /* length of sep char sequence */
  3923.     if (*nextpos == '\0')
  3924.         return (NULL);    /* no more tokens left */
  3925.     nextpos += nchars;
  3926.     nchars = strcspn(nextpos, s2);    /* length of token char sequence */
  3927.     nextpos[nchars] = '\0';
  3928.     returnp = nextpos;
  3929.     nextpos += nchars + 1;
  3930.     return (returnp);
  3931.     }                    /* strtok */
  3932. ###testmain.c
  3933. #include "qsort.c"
  3934. #define SORTFN(a, lim) qsort(a, lim, sizeof(a[0]), intcmp)
  3935. static int intcmp(a, b)
  3936.     int *a, *b;
  3937.     {
  3938.     if (*a > *b)
  3939.         return (1);
  3940.     else if (*a == *b)
  3941.         return (0);
  3942.     else
  3943.         return (-1);
  3944.     }
  3945. #include "qkmain.h"
  3946. ###tr_close.c
  3947. /* tr_close - free a tree or subtree */
  3948. #include "tree.h"
  3949. void tr_close(plt)
  3950.     TR_NODE **plt;                /* ptr to link-in of tree */
  3951.     {
  3952.     TR_NODE *pt;                /* ptr to root of tree */
  3953.  
  3954.     pt = *plt;                    /* pt now points to root of tree */
  3955.     if (pt == NULL)                /* if link-in is NULL, */
  3956.         return;                    /* nothing to do, so return */
  3957.     TR_CLOSE(&pt->left);        /* free left subtree */
  3958.     TR_CLOSE(&pt->right);        /* free right subtree */
  3959.     free(pt);                    /* free the node itself */
  3960.     }
  3961. ###tr_delete.c
  3962. /* tr_delete - delete the node **pln from tree *plt
  3963.  */
  3964. #include "tree.h"
  3965. void tr_delete(plt, pln, cmpfn)
  3966.     TR_NODE **plt;            /* ptr to link-in of tree */
  3967.     TR_NODE **pln;            /* ptr to link-in of node */
  3968.     int (*cmpfn)();            /* ptr to comparison function */
  3969.     {
  3970.     TR_NODE *pn;            /* ptr to specific node of tree */
  3971.     TR_NODE *ps;            /* ptr to node's successor */
  3972.     TR_NODE **pls;            /* ptr to link-in of successor */
  3973.  
  3974.     pn = *pln;                    /* pn pts to the node to delete */
  3975.     if (pn->right == NULL)        /* if node has no right subtree, */
  3976.         {
  3977.         if (pn->left == NULL)    /* if node has no children, */
  3978.             *pln = NULL;        /* replacement for pn is NULL */
  3979.         else                    /* if node has L subtree, but not R, */
  3980.             *pln = pn->left;    /* replacement is pn's L subtree */
  3981.         }
  3982.     else if (pn->left == NULL)    /* if node has R subtree, but not L */
  3983.         *pln = pn->right;        /* replacement is pn's R subtree */
  3984.     else                        /* if node has R and L subtrees *
  3985.         {
  3986.         pls = TR_LNEXT(plt, pn, cmpfn);    /* get ptr to link-in of succ */
  3987.         ps = *pls;                /* ps now points to successor */
  3988.         *pls = ps->right;        /* succ's R subtree takes succ's place */
  3989.         ps->right = pn->right;    /* succ acquires node's R ... */
  3990.         ps->left = pn->left;    /* ... and L subtree */
  3991.         *pln = ps;                /* replacement is successor */
  3992.         }
  3993.     free(pn);
  3994.     }
  3995. ###tr_detach.c
  3996. /* tr_detach - detach node (or subtree) from tree, given link-in
  3997.  */
  3998. #include "tree.h"
  3999. TR_NODE *tr_detach(pln)
  4000.     TR_NODE **pln;        /* ptr to link-in of node to be detached */
  4001.     {
  4002.     TR_NODE *p;
  4003.  
  4004.     p = *pln;            /* hold the address of the node */
  4005.     *pln = NULL;        /* detach the node */
  4006.     return (p);            /* return its address */
  4007.     }
  4008. ###tr_insert.c
  4009. /* tr_insert - insert a single node in tree (recursive version) */
  4010. #include "tree.h"
  4011. void tr_insert(plt, pn, cmpfn)
  4012.     TR_NODE **plt;        /* ptr to link-in of tree or subtree */
  4013.     TR_NODE *pn;        /* ptr to node to be inserted */
  4014.     int (*cmpfn)();        /* ptr to comparison function */
  4015.     {
  4016.     TR_NODE *pt;        /* ptr to tree (or subtree) */
  4017.     int cmp;            /* result of key comparison; neg, zero, or pos */
  4018.  
  4019.     pt = *plt;            /* pt now pts to current tree (if any) */
  4020.     if (pt == NULL)        /* if plt pointed to a null pointer, */
  4021.         {
  4022.         pn->left = pn->right = NULL;    /* has no sub trees yet */
  4023.         *plt = pn;        /* then this is the place to install pn; do so */
  4024.         }
  4025.     else if ((cmp = (*cmpfn)(pn, pt)) == 0)    /* if already in tree, */
  4026.         return;                                /* then don't install */
  4027.     else if (cmp < 0)                /* if node's key compares low */
  4028.         TR_INSERT(&pt->left, pn, cmpfn);    /* then insert in left tree */
  4029.     else                            /* otherwise, */
  4030.         TR_INSERT(&pt->right, pn, cmpfn);    /* insert in right tree */
  4031.     }
  4032. ###tr_lfin1.c
  4033. /* tr_lfind - find node matching a specified key
  4034.  * recursive version
  4035.  * never returns NULL
  4036.  */
  4037. #include "tree.h"
  4038. TR_NODE **tr_lfind(plt, pn, cmpfn)
  4039.     TR_NODE **plt;            /* ptr to link-in of tree or subtree */
  4040.     TR_NODE *pn;            /* ptr to structure containing key to match */
  4041.     int (*cmpfn)();            /* ptr to comparison function */
  4042.     {
  4043.     TR_NODE *pt;            /* ptr to current tree */
  4044.     int cmp;                /* comparison result: neg, zero, pos */
  4045.  
  4046.     pt = *plt;                /* pt now points to current tree */
  4047.     if (pt == NULL)            /* if plt points to a null pointer, */
  4048.         return (plt);        /* the data isn't in the tree */
  4049.     else if ((cmp = (*cmpfn)(pn, pt)) == 0)    /* if key already in tree, */
  4050.         return (plt);                    /* return its node's link-in */
  4051.     else if (cmp < 0)                    /* if key compares low, */
  4052.         return (TR_LFIND(&pt->left, pn, cmpfn));    /* search in left tree */
  4053.     else                                /* otherwise, */
  4054.         return (TR_LFIND(&pt->right, pn, cmpfn));    /* search in right tree */
  4055.     }
  4056. ###tr_lfin2.c
  4057. /* tr_lfind - find node matching a specified key
  4058.  * iterative version
  4059.  * never returns NULL
  4060.  */
  4061. #include "tree.h"
  4062. TR_NODE **tr_lfind(plt, pn, cmpfn)
  4063.     TR_NODE **plt;            /* ptr to link-in of tree or subtree */
  4064.     TR_NODE *pn;            /* ptr to structure containing key to match */
  4065.     int (*cmpfn)();            /* ptr to comparison function */
  4066.     {
  4067.     TR_NODE *pt;            /* ptr to current tree */
  4068.     int cmp;                /* comparison result: neg, zero, pos */
  4069.  
  4070.     FOREVER
  4071.         {
  4072.         pt = *plt;                    /* pt now points to current tree */
  4073.         if (pt == NULL)                /* if plt points to a null pointer, */
  4074.             return (plt);            /* the data isn't in the tree */
  4075.         else if ((cmp = (*cmpfn)(pn, pt)) == 0) /* if key already in tree, */
  4076.             return (plt);            /* return its node's link-in */
  4077.         else if (cmp < 0)            /* if key compares low, */
  4078.             plt = &pt->left;        /* then search in left tree */
  4079.         else                        /* otherwise, */
  4080.             plt = &pt->right;        /* search in right tree */
  4081.         }
  4082.     }
  4083. ###tr_lfind.c
  4084. /* tr_lfind - find node matching a specified key
  4085.  * iterative version
  4086.  * never returns NULL
  4087.  */
  4088. #include "tree.h"
  4089. TR_NODE **tr_lfind(plt, pn, cmpfn)
  4090.     TR_NODE **plt;            /* ptr to link-in of tree or subtree */
  4091.     TR_NODE *pn;            /* ptr to structure containing key to match */
  4092.     int (*cmpfn)();            /* ptr to comparison function */
  4093.     {
  4094.     TR_NODE *pt;            /* ptr to current tree */
  4095.     int cmp;                /* comparison result: neg, zero, pos */
  4096.  
  4097.     FOREVER
  4098.         {
  4099.         pt = *plt;                    /* pt now points to current tree */
  4100.         if (pt == NULL)                /* if plt points to a null pointer, */
  4101.             return (plt);            /* the data isn't in the tree */
  4102.         else if ((cmp = (*cmpfn)(pn, pt)) == 0) /* if key already in tree, */
  4103.             return (plt);            /* return its node's link-in */
  4104.         else if (cmp < 0)            /* if key compares low, */
  4105.             plt = &TR_LEFT(pt);        /* then search in left tree */
  4106.         else                        /* otherwise, */
  4107.             plt = &TR_RIGHT(pt);        /* search in right tree */
  4108.         }
  4109.     }
  4110. ###tr_lfirst.c
  4111. /* tr_lfirst - find first node in tree
  4112.  * Returned value is ptr to link-in of first node
  4113.  * never returns NULL, and never points to null ptr
  4114.  */
  4115. #include "tree.h"
  4116. TR_NODE **tr_lfirst(plt)
  4117.     TR_NODE **plt;            /* ptr to (non-null) link-in of tree */
  4118.     {
  4119.     TR_NODE **pln;            /* ptr to link-in of node */
  4120.  
  4121.     for (pln = plt; (*pln)->left != NULL; pln = &(*pln)->left)
  4122.         ;
  4123.     return (pln);
  4124.     }
  4125. ###tr_lnext.c
  4126. /* tr_lnext - find the successor of node pn
  4127.  * Returned value is ptr to link-in of successor node
  4128.  * Never returns NULL; may return addr of a null ptr
  4129.  */
  4130. #include "tree.h"
  4131. static TR_NODE *nullp = NULL;    /* used to return addr of null ptr */
  4132. TR_NODE **tr_lnext(plt, pn, cmpfn)
  4133.     TR_NODE **plt;            /* ptr to link-in of tree */
  4134.     TR_NODE *pn;            /* ptr to specific node of tree */
  4135.     int (*cmpfn)();            /* ptr to comparison function */
  4136.     {
  4137.     TR_NODE **pls;            /* ptr to link-in of successor */
  4138.     TR_NODE **pln;            /* ptr to link-in of a TR_NODE */
  4139.  
  4140.     if (pn->right != NULL)    /* if node has a right subtree, */
  4141.         { /* return ptr to link-in of "leftmost"  node in right subtree */
  4142.         return (TR_LFIRST(&pn->right));
  4143.         }
  4144.     else                        /* if node has no right subtree, */
  4145.         {        /* return ptr to link-in of parent of pn */
  4146.         pln = TR_LPFIND(plt, pn, cmpfn);
  4147.         if (*pln != NULL && (*pln)->left == pn)
  4148.             return (pln);        /* node is left subtree of parent */
  4149.         else
  4150.             return (&nullp);    /* node is rightmost in tree */
  4151.         }
  4152.     }
  4153. ###tr_lpfind.c
  4154. /* tr_lpfind - find parent of node matching a specified key
  4155.  * iterative version
  4156.  * never returns NULL; may return addr of null ptr
  4157.  */
  4158. #include "tree.h"
  4159. static TR_NODE *nullp = NULL;    /* used to return addr of null ptr */
  4160. TR_NODE **tr_lpfind(plt, pn, cmpfn)
  4161.     TR_NODE **plt;            /* ptr to link-in of tree or subtree */
  4162.     TR_NODE *pn;            /* ptr to structure containing key to match */
  4163.     int (*cmpfn)();            /* ptr to comparison function */
  4164.     {
  4165.     TR_NODE *pt;            /* ptr to current tree */
  4166.     TR_NODE **plp;            /* ptr to link-in of parent of tree */
  4167.     int cmp;                /* comparison result: neg, zero, pos */
  4168.  
  4169.     plp = &nullp;                    /* root has no parent */
  4170.     FOREVER
  4171.         {
  4172.         pt = *plt;                    /* pt now points to current tree */
  4173.         if (pt == NULL)                /* if plt points to a null pointer, */
  4174.             return (&nullp);        /* the data isn't in the tree */
  4175.         else if ((cmp = (*cmpfn)(pn, pt)) == 0) /* if key already in tree, */
  4176.             return (plp);            /* return its parent's link-in */
  4177.         plp = plt;                /* before starting subtree, save plt */
  4178.         if (cmp < 0)                /* if key compares low, */
  4179.             plt = &pt->left;        /* then search in left tree */
  4180.         else                        /* otherwise, */
  4181.             plt = &pt->right;    /* search in right tree */
  4182.         }
  4183.     }
  4184. ###tr_main.c
  4185. /* tr_main - main pgm to test tree pkg
  4186.  */
  4187. #include "tree.h"
  4188. #define DATA_NODE struct data_node
  4189. DATA_NODE
  4190.     {
  4191.     DATA_NODE *right;
  4192.     DATA_NODE *left;
  4193.     char data[4];
  4194.     };
  4195.  
  4196. /* mknode - allocate a new node with specified key
  4197.  */
  4198. DATA_NODE *mknode(key)
  4199.     char key[];
  4200.     {
  4201.     DATA_NODE *p;
  4202.  
  4203.     p = (DATA_NODE *)malloc(sizeof(DATA_NODE));
  4204.     if (p == NULL)
  4205.         return (NULL);
  4206.     strncpy(p->data, key, sizeof(p->data));
  4207.     TR_RIGHT(p) = TR_LEFT(p) = NULL;
  4208.     return (p);
  4209.     }
  4210.  
  4211. /*
  4212.     tr_pr -- print the contents of the tree
  4213. */
  4214. void tr_pr(pt)
  4215.     DATA_NODE *pt;    /* ptr to root of tree */
  4216.     {
  4217.     static short level = -1;
  4218.     short i;
  4219.  
  4220.     if (pt == NULL)
  4221.         return;
  4222.     ++level;
  4223.     tr_pr(TR_LEFT(pt));
  4224.     for (i = 0; i < level; ++i)
  4225.         putchar('.');
  4226.     printf("%s\n", pt->data);
  4227.     tr_pr(TR_RIGHT(pt));
  4228.     --level;
  4229.     }
  4230.  
  4231. /*
  4232.     comp_str -- comparison function 
  4233. */
  4234.  
  4235. int comp_str(p1, p2)
  4236.     DATA_NODE *p1;
  4237.     DATA_NODE *p2;
  4238.     {
  4239.     return(strcmp(p1->data, p2->data));
  4240.     }
  4241.  
  4242.  
  4243. main()
  4244.     {
  4245.  
  4246.     DATA_NODE *root = NULL;
  4247.     DATA_NODE *p = NULL;
  4248.     DATA_NODE **q = NULL;
  4249.     static char *keys[] = 
  4250.         {"d", "b", "c", "a", "e"};
  4251.     int i = 0;
  4252.     int comp_str();        /* comparison function */
  4253.  
  4254.     for (i = 0; i < DIM(keys); ++i)
  4255.         {
  4256.         p = (DATA_NODE *) mknode(keys[i]);
  4257.         TR_INSERT(&root, p, comp_str);
  4258.         q = (DATA_NODE **) TR_LFIND(&root, p, comp_str);
  4259.         tr_pr(root);
  4260.         printf("q=<%s>\n", (*q)->data);
  4261.         q = (DATA_NODE **) TR_LPFIND(&root, p, comp_str);
  4262.         printf("parent=<%s>\n", *q != NULL ? (*q)->data : "NULL");
  4263.         q = (DATA_NODE **) TR_LFIND(&root, p, comp_str);
  4264.         TR_DELETE(&root, q, comp_str);
  4265.         printf("after deletion\n");
  4266.         tr_pr(root);
  4267.         printf("after re-inserting\n");
  4268.         p = (DATA_NODE *) mknode(keys[i]);
  4269.         TR_INSERT(&root, p, comp_str);
  4270.         q = (DATA_NODE **) TR_LFIND(&root, p, comp_str);
  4271.         tr_pr(root);
  4272.         printf("q=<%s>\n\n", (*q)->data);
  4273.         }
  4274.     p = mknode("a");    /* dup, already in tree */
  4275.     TR_INSERT(&root, p, comp_str);
  4276.     printf("after dup:\n");
  4277.     tr_pr(root);
  4278.  
  4279.     p = mknode("x");    /* not in tree */
  4280.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4281.     printf("LFIND(missing) %s properly NULL\n", *q == NULL ? "is" : "NOT");
  4282.  
  4283.     q = (DATA_NODE **)TR_LPFIND(&root, p, comp_str);
  4284.     printf("LPFIND(missing) %s properly NULL\n", *q == NULL ? "is" : "NOT");
  4285.  
  4286.     p = mknode("d");    /* the root */
  4287.     q = (DATA_NODE **)TR_LPFIND(&root, p, comp_str);
  4288.     printf("LPFIND(root) %s properly NULL\n", *q == NULL ? "is" : "NOT");
  4289.  
  4290.     p = mknode("d");    /* root, 2 subtrees */
  4291.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4292.     q = (DATA_NODE **)TR_LNEXT(&root, *q, comp_str);
  4293.     printf("LNEXT(d) == <%s>\n", *q != NULL ? (*q)->data : "NULL");
  4294.  
  4295.     p = mknode("a");    /* no subtrees, successor is parent */
  4296.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4297.     q = (DATA_NODE **)TR_LNEXT(&root, *q, comp_str);
  4298.     printf("LNEXT(a) == <%s>\n", *q != NULL ? (*q)->data : "NULL");
  4299.  
  4300.     p = mknode("e");    /* no subtrees, has no successor */
  4301.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4302.     q = (DATA_NODE **)TR_LNEXT(&root, *q, comp_str);
  4303.     printf("LNEXT(e) == <%s>\n", *q == NULL ? "NULL" : (*q)->data);
  4304.  
  4305.     p = mknode("e");    /* no subtrees, has no successor */
  4306.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4307.     q = (DATA_NODE **)TR_LFIRST(q);
  4308.     printf("LFIRST(e) == <%s>\n", *q == NULL ? "NULL" : (*q)->data);
  4309.  
  4310.     p = mknode("d");
  4311.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4312.     TR_DELETE(&root, q, comp_str);
  4313.     printf("\nAfter deleting 'd':\n");
  4314.     tr_pr(root);
  4315.  
  4316.     p = mknode("b");
  4317.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4318.     TR_DELETE(&root, q, comp_str);
  4319.     printf("\nAfter deleting 'b':\n");
  4320.     tr_pr(root);
  4321.  
  4322.     p = mknode("c");
  4323.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4324.     TR_DELETE(&root, q, comp_str);
  4325.     printf("\nAfter deleting 'c':\n");
  4326.     tr_pr(root);
  4327.  
  4328.     p = mknode("a");
  4329.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4330.     TR_DELETE(&root, q, comp_str);
  4331.     printf("\nAfter deleting 'a':\n");
  4332.     tr_pr(root);
  4333.  
  4334.     p = mknode("e");
  4335.     q = (DATA_NODE **)TR_LFIND(&root, p, comp_str);
  4336.     TR_DELETE(&root, q, comp_str);
  4337.     printf("\nAfter deleting 'e':\n");
  4338.     tr_pr(root);
  4339.     }
  4340.  
  4341. ###tst_sort.c
  4342. /* tst_sort - returns YES if array a is sorted
  4343.  * specialized "short" version
  4344.  */
  4345. #include "local.h"
  4346. bool tst_sort(a, n)
  4347.     short a[];
  4348.     index_t n;
  4349.     {
  4350.     index_t i;
  4351.  
  4352.     if (n <= 0)
  4353.         return (NO);
  4354.     for (i = 1; i < n; ++i)
  4355.         {
  4356.         /* a[0:i-1] => sorted */
  4357.         if (a[i] < a[i-1])        /* compare adjacent elements */
  4358.             return (NO);
  4359.         }
  4360.     /* a[0:n-1] => sorted */
  4361.     return (YES);
  4362.     }
  4363. ###w_bin_open.c
  4364. /* bin_open - open a binary file 
  4365.  * WSL 2.3 version
  4366.  */
  4367. #include "bin_io.h"
  4368. bin_fd bin_open(fname, type)
  4369.     char fname[];
  4370.     int type;
  4371.     {
  4372.     int fd;
  4373.  
  4374.     if ((type & O_TRUNC) != O_TRUNC)    /* not TRUNC mode */
  4375.         {
  4376.         fd = open(fname, type & O_RWMODE, 1);        /* attempt open */
  4377.         if (fd >= 0)
  4378.             {
  4379.             if ((type & (O_EXCL|O_CREAT)) == (O_EXCL|O_CREAT))
  4380.                 return (-1);            /* not allowed to exist */
  4381.             else
  4382.                 return (fd);            /* open succeeded */
  4383.             }
  4384.         else if ((type & O_RWMODE) == O_RDONLY)
  4385.             return (fd);                /* rdonly, open failed */
  4386.         }
  4387.     if ((type & O_CREAT) != O_CREAT)
  4388.         return (-1);                    /* not allowed to create */
  4389.     fd = create(fname, type & O_RWMODE, 1);        /* attempt create */
  4390.     return (fd);
  4391.     }
  4392.