src/regex/regc_cvec.c

   1 /*
   2  * Utility functions for handling cvecs
   3  * This file is #included by regcomp.c.
   4  *
   5  * Copyright (c) 1998, 1999 Henry Spencer.      All rights reserved.
   6  *
   7  * Development of this software was funded, in part, by Cray Research Inc.,
   8  * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
   9  * Corporation, none of whom are responsible for the results.  The author
  10  * thanks all of them.
  11  *
  12  * Redistribution and use in source and binary forms -- with or without
  13  * modification -- are permitted for any purpose, provided that
  14  * redistributions in source form retain this entire copyright notice and
  15  * indicate the origin and nature of any modifications.
  16  *
  17  * I'd appreciate being given credit for this package in the documentation
  18  * of software which uses it, but that is not a requirement.
  19  *
  20  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
  21  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
  22  * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
  23  * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  24  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  25  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
  26  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
  27  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
  28  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  29  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  30  *
  31  * $Header$
  32  *
  33  */
  34
  35 /*
  36  * newcvec - allocate a new cvec
  37  */
  38 static struct cvec *
  39 newcvec(int nchrs,                              /* to hold this many chrs... */
  40                 int nranges,                    /* ... and this many ranges... */
  41                 int nmcces)                             /* ... and this many MCCEs */
  42 {
  43         size_t          n;
  44         size_t          nc;
  45         struct cvec *cv;
  46
  47         nc = (size_t) nchrs + (size_t) nmcces *(MAXMCCE + 1) + (size_t) nranges *2;
  48
  49         n = sizeof(struct cvec) + (size_t) (nmcces - 1) * sizeof(chr *)
  50                 + nc * sizeof(chr);
  51         cv = (struct cvec *) MALLOC(n);
  52         if (cv == NULL)
  53                 return NULL;
  54         cv->chrspace = nchrs;
  55         cv->chrs = (chr *) &cv->mcces[nmcces];          /* chrs just after MCCE
  56                                                                                                  * ptrs */
  57         cv->mccespace = nmcces;
  58         cv->ranges = cv->chrs + nchrs + nmcces * (MAXMCCE + 1);
  59         cv->rangespace = nranges;
  60         return clearcvec(cv);
  61 }
  62
  63 /*
  64  * clearcvec - clear a possibly-new cvec
  65  * Returns pointer as convenience.
  66  */
  67 static struct cvec *
  68 clearcvec(struct cvec * cv)
  69 {
  70         int                     i;
  71
  72         assert(cv != NULL);
  73         cv->nchrs = 0;
  74         assert(cv->chrs == (chr *) &cv->mcces[cv->mccespace]);
  75         cv->nmcces = 0;
  76         cv->nmccechrs = 0;
  77         cv->nranges = 0;
  78         for (i = 0; i < cv->mccespace; i++)
  79                 cv->mcces[i] = NULL;
  80
  81         return cv;
  82 }
  83
  84 /*
  85  * addchr - add a chr to a cvec
  86  */
  87 static void
  88 addchr(struct cvec * cv,                /* character vector */
  89            chr c)                                       /* character to add */
  90 {
  91         assert(cv->nchrs < cv->chrspace - cv->nmccechrs);
  92         cv->chrs[cv->nchrs++] = (chr) c;
  93 }
  94
  95 /*
  96  * addrange - add a range to a cvec
  97  */
  98 static void
  99 addrange(struct cvec * cv,              /* character vector */
 100                  chr from,                              /* first character of range */
 101                  chr to)                                /* last character of range */
 102 {
 103         assert(cv->nranges < cv->rangespace);
 104         cv->ranges[cv->nranges * 2] = (chr) from;
 105         cv->ranges[cv->nranges * 2 + 1] = (chr) to;
 106         cv->nranges++;
 107 }
 108
 109 /*
 110  * addmcce - add an MCCE to a cvec
 111  */
 112 static void
 113 addmcce(struct cvec * cv,               /* character vector */
 114                 chr *startp,                    /* beginning of text */
 115                 chr *endp)                              /* just past end of text */
 116 {
 117         int                     len;
 118         int                     i;
 119         chr                *s;
 120         chr                *d;
 121
 122         if (startp == NULL && endp == NULL)
 123                 return;
 124         len = endp - startp;
 125         assert(len > 0);
 126         assert(cv->nchrs + len < cv->chrspace - cv->nmccechrs);
 127         assert(cv->nmcces < cv->mccespace);
 128         d = &cv->chrs[cv->chrspace - cv->nmccechrs - len - 1];
 129         cv->mcces[cv->nmcces++] = d;
 130         for (s = startp, i = len; i > 0; s++, i--)
 131                 *d++ = *s;
 132         *d++ = 0;                                       /* endmarker */
 133         assert(d == &cv->chrs[cv->chrspace - cv->nmccechrs]);
 134         cv->nmccechrs += len + 1;
 135 }
 136
 137 /*
 138  * haschr - does a cvec contain this chr?
 139  */
 140 static int                                              /* predicate */
 141 haschr(struct cvec * cv,                /* character vector */
 142            chr c)                                       /* character to test for */
 143 {
 144         int                     i;
 145         chr                *p;
 146
 147         for (p = cv->chrs, i = cv->nchrs; i > 0; p++, i--)
 148         {
 149                 if (*p == c)
 150                         return 1;
 151         }
 152         for (p = cv->ranges, i = cv->nranges; i > 0; p += 2, i--)
 153         {
 154                 if ((*p <= c) && (c <= *(p + 1)))
 155                         return 1;
 156         }
 157         return 0;
 158 }
 159
 160 /*
 161  * getcvec - get a cvec, remembering it as v->cv
 162  */
 163 static struct cvec *
 164 getcvec(struct vars * v,                /* context */
 165                 int nchrs,                              /* to hold this many chrs... */
 166                 int nranges,                    /* ... and this many ranges... */
 167                 int nmcces)                             /* ... and this many MCCEs */
 168 {
 169         if (v->cv != NULL && nchrs <= v->cv->chrspace &&
 170                 nranges <= v->cv->rangespace && nmcces <= v->cv->mccespace)
 171                 return clearcvec(v->cv);
 172
 173         if (v->cv != NULL)
 174                 freecvec(v->cv);
 175         v->cv = newcvec(nchrs, nranges, nmcces);
 176         if (v->cv == NULL)
 177                 ERR(REG_ESPACE);
 178
 179         return v->cv;
 180 }
 181
 182 /*
 183  * freecvec - free a cvec
 184  */
 185 static void
 186 freecvec(struct cvec * cv)
 187 {
 188         FREE(cv);
 189 }