home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / unix / volume15 / lwf / range.c < prev    next >
C/C++ Source or Header  |  1988-05-24  |  8KB  |  351 lines
  1. /* vi: set tabstop=4 : */
  2.  
  3. /*
  4.  * Return 1 if the given number is in the specified range,
  5.  * -1 if there is an error in the range specification,
  6.  * 0 otherwise
  7.  *
  8.  * Ranges have a similar (we use a colon instead of a dash) form to that
  9.  * used by [nt]roff; i.e., a comma separated list of specifiers of the
  10.  * form:
  11.  *    1) n    means     x such that x = n
  12.  *    2) :n    means all x such that x <= n
  13.  *    3) n:    means all x such that x >= n
  14.  *    4) n:m    means all x such that n <= x <= m
  15.  *    5) :    means all x
  16.  * n is an int
  17.  *
  18.  * Problems:
  19.  * The routine prints an error message if the range is strange - this
  20.  * might not always be desirable.
  21.  *
  22.  * Jul/86 BJB
  23.  */
  24.  
  25. /*
  26.  * ===================================================================
  27.  *
  28.  * Permission is given to freely copy and distribute this software
  29.  * providing:
  30.  *
  31.  *    1) You do not sell it,
  32.  *    2) You do not use it for commercial advantage, and
  33.  *    3) This notice accompanies the distribution
  34.  *
  35.  * Copyright (c) 1988
  36.  * Barry Brachman
  37.  * Dept. of Computer Science
  38.  * Univ. of British Columbia
  39.  * Vancouver, B.C. V6T 1W5
  40.  *
  41.  * .. {ihnp4!alberta, uw-beaver, uunet}!ubc-vision!ubc-csgrads!brachman
  42.  * brachman@grads.cs.ubc.cdn
  43.  * brachman%ubc.csnet@csnet-relay.arpa
  44.  * brachman@ubc.csnet
  45.  * ====================================================================
  46.  */
  47.  
  48. #include <ctype.h>
  49. #include <stdio.h>
  50.  
  51. #define streq(a, b)            (!strcmp((a), (b)))
  52. #define smalloc(a, t, s)    ((a = (t) malloc((unsigned) (s))) == NULL)
  53. #define srealloc(a, t, b, s) ((a = (t) realloc(b, (unsigned) (s))) == NULL)
  54. #define max(a, b)            ((a) >= (b) ? (a) : (b))
  55.  
  56. #define SEP_CHAR    ':'
  57. #define SEP_T        0        /* separator token */
  58. #define NUM_T        1        /* number token */
  59. #define BAD_T        2        /* token for bad character */
  60.  
  61. #define STR_ALLOC    80
  62.  
  63. struct range_header {
  64.     char *range_str;        /* range character string */
  65.     int range_str_alloc;    /* length in bytes */
  66.     int nranges;            /* number of range entries */
  67.     struct range *range;
  68. } range_header = {
  69.     NULL, 0, NULL
  70. };
  71.  
  72. /*
  73.  * If hflag (lflag) is non-zero then the high (low) value is present
  74.  */
  75. struct range {
  76.     char hflag;            /* high value present */
  77.     char lflag;            /* low value present */
  78.     int high;            /* high part of range */
  79.     int low;            /* low part of range */
  80. };
  81.  
  82. #ifdef RANGE_DEBUG
  83.  
  84. /*
  85.  * This is a program for demonstrating and debugging the range checking
  86.  * code
  87.  * Enter a range when prompted
  88.  * (If there is a previous range shown you may enter <return> to
  89.  * reselect it)
  90.  * Enter a value
  91.  * The program will indicate whether the value is in the given range
  92.  */
  93.  
  94. char buf[BUFSIZ], range[BUFSIZ];
  95.  
  96. main(argc, argv)
  97. int argc;
  98. char **argv;
  99. {
  100.     register int i;
  101.     char *p;
  102.     struct range_header *rh;
  103.     struct range *r;
  104.     FILE *fp;
  105.     char *gets(), *index(), *strcpy();
  106.  
  107.     buf[0] = range[0] = '\0';
  108.     if (argc == 2) {
  109.         if ((fp = fopen(argv[1], "r")) == NULL) {
  110.             (void) fprintf(stderr, "Can't open %s\n", argv[1]);
  111.             exit(1);
  112.             /*NOTREACHED*/
  113.         }
  114.     }
  115.     else
  116.         fp = stdin;
  117.  
  118.     if (fp == stdin)
  119.         (void) printf("Range? ");
  120.     while (fgets(buf, sizeof(buf), fp) != NULL) {
  121.         if ((p = index(buf, '\n')) != NULL)
  122.             *p = '\0';
  123.         if (buf[0] != '\0') {
  124.             (void) strcpy(range, buf);
  125.             if (checkrange(range)) {
  126.                 if (fp == stdin)
  127.                     (void) printf("Range? ");
  128.                 continue;
  129.             }
  130.             rh = &range_header;
  131.             (void) printf("%s (%d alloc) (%d ranges):\n",
  132.                   rh->range_str, rh->range_str_alloc, rh->nranges);
  133.             for (r = rh->range, i = 0; i < rh->nranges; i++, r++)
  134.                 (void) printf("hflag=%d lflag=%d high=%d low=%d\n",
  135.                     r->hflag, r->lflag, r->high, r->low);
  136.         }
  137.         if (fp != stdin)
  138.             continue;
  139.         (void) printf("Value? ");
  140.         if (gets(buf) == NULL)
  141.             break;
  142.         i = inrange(atoi(buf), range);
  143.         if (i == 0)
  144.             (void) printf("\tno\n");
  145.         else if (i == 1)
  146.             (void) printf("\tyes\n");
  147.         else if (i == -1)
  148.             (void) printf("\terror\n");
  149.         else
  150.             (void) printf("\tbad result\n");
  151.         (void) printf("Range ['%s']? ", range);
  152.     }
  153.     (void) printf("\n");
  154. }
  155. #endif RANGE_DEBUG
  156.  
  157. /*
  158.  * Check and compile the given range specification and then determine if
  159.  * the number is in the range
  160.  * Return -1 if there is a compilation error, 1 if the number is in the
  161.  * range, or 0 if the number isn't in the range
  162.  */
  163. inrange(num, range_spec)
  164. int num;
  165. char *range_spec;
  166. {
  167.     register int i, rc;
  168.     register struct range_header *rh;
  169.     register struct range *r;
  170.  
  171.     if (checkrange(range_spec))
  172.         return(-1);
  173.     rh = &range_header;
  174.     rc = 0;
  175.     for (r = rh->range, i = 0; rc == 0 && i < rh->nranges; i++, r++) {
  176.         if (r->hflag) {
  177.             if (num > r->high)
  178.                 continue;
  179.             if (r->lflag && num < r->low)
  180.                 continue;
  181.             rc = 1;
  182.         }
  183.         else if (r->lflag) {
  184.             if (num >= r->low)
  185.                 rc = 1;
  186.         }
  187.         else                /* both unset -> ":" */
  188.             rc = 1;
  189.     }
  190.     return(rc);
  191. }
  192.  
  193. /*
  194.  * Check and compile a range specification
  195.  * Print a message and return -1 on error; return 0 oth.
  196.  *
  197.  * Could be more efficient by allocating more structures at a time... SMOP
  198.  */
  199. checkrange(range_spec)
  200. char *range_spec;
  201. {
  202.     register struct range_header *rh;
  203.     register struct range *r;
  204.     int len;
  205.     int ltype, lval, rtype, rval;
  206.     char *p;
  207.     char *malloc(), *realloc(), *strcpy();
  208.  
  209.     rh = &range_header;
  210.     /*
  211.      * Check if the previous range is being used
  212.      */
  213.     if (rh->range_str != NULL && streq(range_spec, rh->range_str))
  214.         return(0);
  215.  
  216.     /*
  217.      * New range spec
  218.      * If there is enough space, reuse it; oth. allocate enough
  219.      * (amount allocated never shrinks)
  220.      */
  221.     len = max(strlen(range_spec) + 1, STR_ALLOC);
  222.     if (rh->range_str != NULL  && len > rh->range_str_alloc) {
  223.         free(rh->range_str);
  224.         rh->range_str = (char *) malloc((unsigned) len);
  225.         rh->range_str_alloc = len;
  226.     }
  227.     else if (rh->range_str == NULL) {
  228.         rh->range_str = (char *) malloc((unsigned) len);
  229.         rh->range_str_alloc = len;
  230.     }
  231.     (void) strcpy(rh->range_str, range_spec);
  232.     if (rh->range != NULL)
  233.         free((char *) rh->range);
  234.     rh->range = NULL;
  235.  
  236.     p = range_spec;
  237.     while (1) {
  238.         lval = getnum(&p, <ype);
  239.         if (ltype == BAD_T) {
  240.             (void) fprintf(stderr, "range: bad first number\n");
  241.             *rh->range_str = '\0';        /* invalidate */
  242.             return(-1);
  243.         }
  244.  
  245.         if (rh->range == NULL) {
  246.             smalloc(r, struct range *, sizeof(struct range));
  247.             rh->nranges = 1;
  248.         }
  249.         else {
  250.             len = sizeof(struct range) * ++(rh->nranges);
  251.             srealloc(r, struct range *, (char *) rh->range, len);
  252.         }
  253.         rh->range = r;
  254.         r += rh->nranges - 1;        /* point to new one */
  255.         r->hflag = r->lflag = 0;
  256.         r->high = r->low = 0;
  257.  
  258.         /*
  259.          * If ltype != NUM_T there is no lval
  260.          */
  261.         if (ltype == NUM_T) {
  262.             r->lflag = 1;
  263.             r->low = lval;
  264.         }
  265.  
  266.         switch (*p) {
  267.         case ',':            /* single number */
  268.             r->hflag = 1;
  269.             r->high = lval;
  270.             p++;
  271.             continue;
  272.  
  273.         case '\0':            /* single number at end */
  274.             r->hflag = 1;
  275.             r->high = lval;
  276.             return(0);
  277.  
  278.         case ':':
  279.             p++;
  280.             if (*p == '\0')        /* no rval */
  281.                 return(0);
  282.             if (*p == ',') {    /* no rval */
  283.                 p++;
  284.                 break;
  285.             }
  286.  
  287.             rval = getnum(&p, &rtype);
  288.             if (rtype == BAD_T) {
  289.                 (void) fprintf(stderr, "range: bad second number\n");
  290.                 *rh->range_str = '\0';
  291.                 return(-1);
  292.             }
  293.  
  294.             if (lval > rval) {
  295.                 (void) fprintf(stderr, "range: values reversed\n");
  296.                 *rh->range_str = '\0';    /* invalidate */
  297.                 return(-1);
  298.             }
  299.             r->hflag = 1;
  300.             r->high = rval;
  301.             if (*p == '\0')
  302.                 return(0);
  303.             if (*p == ',')
  304.                 p++;
  305.             break;
  306.  
  307.         default:
  308.             (void) fprintf(stderr, "range: bad character\n");
  309.             *rh->range_str = '\0';        /* invalidate */
  310.             return(-1);
  311.         }
  312.     }
  313. }
  314.  
  315. static
  316. getnum(pp, type)
  317. char **pp;
  318. int *type;
  319. {
  320.     register int sign, val;
  321.     register char *p;
  322.  
  323.     p = *pp;
  324.     if (!isdigit(*p) && *p != '-') {
  325.         if (*p == SEP_CHAR)
  326.             *type = SEP_T;
  327.         else
  328.             *type = BAD_T;
  329.         return(0);
  330.     }
  331.     sign = 1;
  332.     if (*p == '-') {
  333.         sign = -1;
  334.         p++;
  335.     }
  336.     if (!isdigit(*p)) {
  337.         *type = BAD_T;
  338.         return(0);
  339.     }
  340.     for (val = 0; isdigit(*p) && *p != '\0'; p++)
  341.         val = val * 10 + *p - '0';
  342.     if (*p != '\0' && *p != ',' && *p != SEP_CHAR) {
  343.         *type = BAD_T;
  344.         return(0);
  345.     }
  346.     *pp = p;
  347.     *type = NUM_T;
  348.     return(sign * val);
  349. }
  350.  
  351.