[BACK]Return to regex2.h CVS log [TXT][DIR] Up to [cvs.NetBSD.org] / src / lib / libc / regex

Annotation of src/lib/libc/regex/regex2.h, Revision 1.10

1.10    ! agc         1: /*     $NetBSD: regex2.h,v 1.9 1998/12/13 12:21:47 drochner Exp $      */
1.5       cgd         2:
1.4       cgd         3: /*-
                      4:  * Copyright (c) 1992, 1993, 1994
                      5:  *     The Regents of the University of California.  All rights reserved.
1.10    ! agc         6:  *
        !             7:  * This code is derived from software contributed to Berkeley by
        !             8:  * Henry Spencer.
        !             9:  *
        !            10:  * Redistribution and use in source and binary forms, with or without
        !            11:  * modification, are permitted provided that the following conditions
        !            12:  * are met:
        !            13:  * 1. Redistributions of source code must retain the above copyright
        !            14:  *    notice, this list of conditions and the following disclaimer.
        !            15:  * 2. Redistributions in binary form must reproduce the above copyright
        !            16:  *    notice, this list of conditions and the following disclaimer in the
        !            17:  *    documentation and/or other materials provided with the distribution.
        !            18:  * 3. Neither the name of the University nor the names of its contributors
        !            19:  *    may be used to endorse or promote products derived from this software
        !            20:  *    without specific prior written permission.
        !            21:  *
        !            22:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
        !            23:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
        !            24:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
        !            25:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
        !            26:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
        !            27:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
        !            28:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
        !            29:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
        !            30:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
        !            31:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
        !            32:  * SUCH DAMAGE.
        !            33:  *
        !            34:  *     @(#)regex2.h    8.4 (Berkeley) 3/20/94
        !            35:  */
        !            36:
        !            37: /*-
        !            38:  * Copyright (c) 1992, 1993, 1994 Henry Spencer.
1.4       cgd        39:  *
                     40:  * This code is derived from software contributed to Berkeley by
                     41:  * Henry Spencer.
                     42:  *
                     43:  * Redistribution and use in source and binary forms, with or without
                     44:  * modification, are permitted provided that the following conditions
                     45:  * are met:
                     46:  * 1. Redistributions of source code must retain the above copyright
                     47:  *    notice, this list of conditions and the following disclaimer.
                     48:  * 2. Redistributions in binary form must reproduce the above copyright
                     49:  *    notice, this list of conditions and the following disclaimer in the
                     50:  *    documentation and/or other materials provided with the distribution.
                     51:  * 3. All advertising materials mentioning features or use of this software
                     52:  *    must display the following acknowledgement:
                     53:  *     This product includes software developed by the University of
                     54:  *     California, Berkeley and its contributors.
                     55:  * 4. Neither the name of the University nor the names of its contributors
                     56:  *    may be used to endorse or promote products derived from this software
                     57:  *    without specific prior written permission.
                     58:  *
                     59:  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
                     60:  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
                     61:  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
                     62:  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
                     63:  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
                     64:  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
                     65:  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
                     66:  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
                     67:  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
                     68:  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
                     69:  * SUCH DAMAGE.
                     70:  *
                     71:  *     @(#)regex2.h    8.4 (Berkeley) 3/20/94
                     72:  */
                     73:
1.1       jtc        74: /*
                     75:  * First, the stuff that ends up in the outside-world include file
                     76:  = typedef off_t regoff_t;
                     77:  = typedef struct {
                     78:  =     int re_magic;
                     79:  =     size_t re_nsub;         // number of parenthesized subexpressions
1.3       jtc        80:  =     const char *re_endp;    // end pointer for REG_PEND
1.1       jtc        81:  =     struct re_guts *re_g;   // none of your business :-)
                     82:  = } regex_t;
                     83:  = typedef struct {
                     84:  =     regoff_t rm_so;         // start of match
                     85:  =     regoff_t rm_eo;         // end of match
                     86:  = } regmatch_t;
                     87:  */
                     88: /*
                     89:  * internals of regex_t
                     90:  */
                     91: #define        MAGIC1  ((('r'^0200)<<8) | 'e')
                     92:
                     93: /*
                     94:  * The internal representation is a *strip*, a sequence of
                     95:  * operators ending with an endmarker.  (Some terminology etc. is a
                     96:  * historical relic of earlier versions which used multiple strips.)
                     97:  * Certain oddities in the representation are there to permit running
                     98:  * the machinery backwards; in particular, any deviation from sequential
                     99:  * flow must be marked at both its source and its destination.  Some
                    100:  * fine points:
                    101:  *
                    102:  * - OPLUS_ and O_PLUS are *inside* the loop they create.
                    103:  * - OQUEST_ and O_QUEST are *outside* the bypass they create.
                    104:  * - OCH_ and O_CH are *outside* the multi-way branch they create, while
                    105:  *   OOR1 and OOR2 are respectively the end and the beginning of one of
                    106:  *   the branches.  Note that there is an implicit OOR2 following OCH_
                    107:  *   and an implicit OOR1 preceding O_CH.
                    108:  *
                    109:  * In state representations, an operator's bit is on to signify a state
                    110:  * immediately *preceding* "execution" of that operator.
                    111:  */
1.7       christos  112: typedef u_int32_t sop; /* strip operator */
1.8       drochner  113: typedef int sopno;
1.7       christos  114: #define        OPRMASK ((u_int32_t)0xf8000000UL)
                    115: #define        OPDMASK ((u_int32_t)0x07ffffffUL)
1.8       drochner  116: #define        OPSHIFT ((unsigned)27)
1.1       jtc       117: #define        OP(n)   ((n)&OPRMASK)
1.8       drochner  118: #define        OPND(n) ((int)((n)&OPDMASK))
1.1       jtc       119: #define        SOP(op, opnd)   ((op)|(opnd))
1.8       drochner  120:
                    121: #define OPC(n) (((u_int32_t)(n))<<OPSHIFT)
1.7       christos  122: /* operators              meaning      operand                 */
                    123: /*                                     (back, fwd are offsets) */
                    124: #define        OEND    OPC(1)  /* endmarker    -                       */
                    125: #define        OCHAR   OPC(2)  /* character    unsigned char           */
                    126: #define        OBOL    OPC(3)  /* left anchor  -                       */
                    127: #define        OEOL    OPC(4)  /* right anchor -                       */
                    128: #define        OANY    OPC(5)  /* .            -                       */
                    129: #define        OANYOF  OPC(6)  /* [...]        set number              */
                    130: #define        OBACK_  OPC(7)  /* begin \d     paren number            */
                    131: #define        O_BACK  OPC(8)  /* end \d       paren number            */
                    132: #define        OPLUS_  OPC(9)  /* + prefix     fwd to suffix           */
                    133: #define        O_PLUS  OPC(10) /* + suffix     back to prefix          */
                    134: #define        OQUEST_ OPC(11) /* ? prefix     fwd to suffix           */
                    135: #define        O_QUEST OPC(12) /* ? suffix     back to prefix          */
                    136: #define        OLPAREN OPC(13) /* (            fwd to )                */
                    137: #define        ORPAREN OPC(14) /* )            back to (               */
                    138: #define        OCH_    OPC(15) /* begin choice fwd to OOR2             */
                    139: #define        OOR1    OPC(16) /* | pt. 1      back to OOR1 or OCH_    */
                    140: #define        OOR2    OPC(17) /* | pt. 2      fwd to OOR2 or O_CH     */
                    141: #define        O_CH    OPC(18) /* end choice   back to OOR1            */
                    142: #define        OBOW    OPC(19) /* begin word   -                       */
                    143: #define        OEOW    OPC(20) /* end word     -                       */
1.1       jtc       144:
                    145: /*
                    146:  * Structure for [] character-set representation.  Character sets are
                    147:  * done as bit vectors, grouped 8 to a byte vector for compactness.
                    148:  * The individual set therefore has both a pointer to the byte vector
                    149:  * and a mask to pick out the relevant bit of each byte.  A hash code
                    150:  * simplifies testing whether two sets could be identical.
                    151:  *
                    152:  * This will get trickier for multicharacter collating elements.  As
                    153:  * preliminary hooks for dealing with such things, we also carry along
                    154:  * a string of multi-character elements, and decide the size of the
                    155:  * vectors at run time.
                    156:  */
                    157: typedef struct {
1.2       jtc       158:        uch *ptr;               /* -> uch [csetsize] */
                    159:        uch mask;               /* bit within array */
                    160:        uch hash;               /* hash code */
1.1       jtc       161:        size_t smultis;
                    162:        char *multis;           /* -> char[smulti]  ab\0cd\0ef\0\0 */
                    163: } cset;
                    164: /* note that CHadd and CHsub are unsafe, and CHIN doesn't yield 0/1 */
1.2       jtc       165: #define        CHadd(cs, c)    ((cs)->ptr[(uch)(c)] |= (cs)->mask, (cs)->hash += (c))
                    166: #define        CHsub(cs, c)    ((cs)->ptr[(uch)(c)] &= ~(cs)->mask, (cs)->hash -= (c))
                    167: #define        CHIN(cs, c)     ((cs)->ptr[(uch)(c)] & (cs)->mask)
                    168: #define        MCadd(p, cs, cp)        mcadd(p, cs, cp)        /* regcomp() internal fns */
                    169: #define        MCsub(p, cs, cp)        mcsub(p, cs, cp)
                    170: #define        MCin(p, cs, cp) mcin(p, cs, cp)
1.1       jtc       171:
                    172: /* stuff for character categories */
                    173: typedef unsigned char cat_t;
                    174:
                    175: /*
                    176:  * main compiled-expression structure
                    177:  */
                    178: struct re_guts {
                    179:        int magic;
                    180: #              define  MAGIC2  ((('R'^0200)<<8)|'E')
                    181:        sop *strip;             /* malloced area for strip */
                    182:        int csetsize;           /* number of bits in a cset vector */
                    183:        int ncsets;             /* number of csets in use */
                    184:        cset *sets;             /* -> cset [ncsets] */
1.2       jtc       185:        uch *setbits;           /* -> uch[csetsize][ncsets/CHAR_BIT] */
1.1       jtc       186:        int cflags;             /* copy of regcomp() cflags argument */
                    187:        sopno nstates;          /* = number of sops */
                    188:        sopno firststate;       /* the initial OEND (normally 0) */
                    189:        sopno laststate;        /* the final OEND */
                    190:        int iflags;             /* internal flags */
                    191: #              define  USEBOL  01      /* used ^ */
                    192: #              define  USEEOL  02      /* used $ */
                    193: #              define  BAD     04      /* something wrong */
                    194:        int nbol;               /* number of ^ used */
                    195:        int neol;               /* number of $ used */
                    196:        int ncategories;        /* how many character categories */
                    197:        cat_t *categories;      /* ->catspace[-CHAR_MIN] */
                    198:        char *must;             /* match must contain this string */
                    199:        int mlen;               /* length of must */
1.9       drochner  200:        sopno nsub;             /* copy of re_nsub */
1.1       jtc       201:        int backrefs;           /* does it use back references? */
                    202:        sopno nplus;            /* how deep does it nest +s? */
                    203:        /* catspace must be last */
                    204:        cat_t catspace[1];      /* actually [NC] */
                    205: };
                    206:
                    207: /* misc utilities */
                    208: #define        OUT     (CHAR_MAX+1)    /* a non-character value */
1.3       jtc       209: #define        ISWORD(c)       (isalnum(c) || (c) == '_')

CVSweb <webmaster@jp.NetBSD.org>