/[dtapublic]/projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regguts.h
ViewVC logotype

Annotation of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/regguts.h

Parent Directory Parent Directory | Revision Log Revision Log


Revision 71 - (hide annotations) (download)
Sat Nov 5 11:07:06 2016 UTC (7 years, 8 months ago) by dashley
File MIME type: text/plain
File size: 12421 byte(s)
Set EOL properties appropriately to facilitate simultaneous Linux and Windows development.
1 dashley 71 /* $Header$ */
2     /*
3     * Internal interface definitions, etc., for the reg package
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    
32    
33    
34     /*
35     * Environmental customization. It should not (I hope) be necessary to
36     * alter the file you are now reading -- regcustom.h should handle it all,
37     * given care here and elsewhere.
38     */
39     #include "regcustom.h"
40    
41    
42    
43     /*
44     * Things that regcustom.h might override.
45     */
46    
47     /* standard header files (NULL is a reasonable indicator for them) */
48     #ifndef NULL
49     #include <stdio.h>
50     #include <stdlib.h>
51     #include <ctype.h>
52     #include <limits.h>
53     #include <string.h>
54     #endif
55    
56     /* assertions */
57     #ifndef assert
58     # ifndef REG_DEBUG
59     /* # define NDEBUG */ /* no assertions */
60     # endif
61     #include <assert.h>
62     #endif
63    
64     /* voids */
65     #ifndef VOID
66     #define VOID void /* for function return values */
67     #endif
68     #ifndef DISCARD
69     #define DISCARD VOID /* for throwing values away */
70     #endif
71     #ifndef PVOID
72     #define PVOID VOID * /* generic pointer */
73     #endif
74     #ifndef VS
75     #define VS(x) ((PVOID)(x)) /* cast something to generic ptr */
76     #endif
77     #ifndef NOPARMS
78     #define NOPARMS VOID /* for empty parm lists */
79     #endif
80    
81     /* const */
82     #ifndef CONST
83     #define CONST const /* for old compilers, might be empty */
84     #endif
85    
86     /* function-pointer declarator */
87     #ifndef FUNCPTR
88     #if __STDC__ >= 1
89     #define FUNCPTR(name, args) (*name)args
90     #else
91     #define FUNCPTR(name, args) (*name)()
92     #endif
93     #endif
94    
95     /* memory allocation */
96     #ifndef MALLOC
97     #define MALLOC(n) malloc(n)
98     #endif
99     #ifndef REALLOC
100     #define REALLOC(p, n) realloc(VS(p), n)
101     #endif
102     #ifndef FREE
103     #define FREE(p) free(VS(p))
104     #endif
105    
106     /* want size of a char in bits, and max value in bounded quantifiers */
107     #ifndef CHAR_BIT
108     #include <limits.h>
109     #endif
110     #ifndef _POSIX2_RE_DUP_MAX
111     #define _POSIX2_RE_DUP_MAX 255 /* normally from <limits.h> */
112     #endif
113    
114    
115    
116     /*
117     * misc
118     */
119    
120     #define NOTREACHED 0
121     #define xxx 1
122    
123     #define DUPMAX _POSIX2_RE_DUP_MAX
124     #define INFINITY (DUPMAX+1)
125    
126     #define REMAGIC 0xfed7 /* magic number for main struct */
127    
128    
129    
130     /*
131     * debugging facilities
132     */
133     #ifdef REG_DEBUG
134     /* FDEBUG does finite-state tracing */
135     #define FDEBUG(arglist) { if (v->eflags&REG_FTRACE) printf arglist; }
136     /* MDEBUG does higher-level tracing */
137     #define MDEBUG(arglist) { if (v->eflags&REG_MTRACE) printf arglist; }
138     #else
139     #define FDEBUG(arglist) {}
140     #define MDEBUG(arglist) {}
141     #endif
142    
143    
144    
145     /*
146     * bitmap manipulation
147     */
148     #define UBITS (CHAR_BIT * sizeof(unsigned))
149     #define BSET(uv, sn) ((uv)[(sn)/UBITS] |= (unsigned)1 << ((sn)%UBITS))
150     #define ISBSET(uv, sn) ((uv)[(sn)/UBITS] & ((unsigned)1 << ((sn)%UBITS)))
151    
152    
153    
154     /*
155     * We dissect a chr into byts for colormap table indexing. Here we define
156     * a byt, which will be the same as a byte on most machines... The exact
157     * size of a byt is not critical, but about 8 bits is good, and extraction
158     * of 8-bit chunks is sometimes especially fast.
159     */
160     #ifndef BYTBITS
161     #define BYTBITS 8 /* bits in a byt */
162     #endif
163     #define BYTTAB (1<<BYTBITS) /* size of table with one entry per byt value */
164     #define BYTMASK (BYTTAB-1) /* bit mask for byt */
165     #define NBYTS ((CHRBITS+BYTBITS-1)/BYTBITS)
166     /* the definition of GETCOLOR(), below, assumes NBYTS <= 4 */
167    
168    
169    
170     /*
171     * As soon as possible, we map chrs into equivalence classes -- "colors" --
172     * which are of much more manageable number.
173     */
174     typedef short color; /* colors of characters */
175     typedef int pcolor; /* what color promotes to */
176     #define COLORLESS (-1) /* impossible color */
177     #define WHITE 0 /* default color, parent of all others */
178    
179    
180    
181     /*
182     * A colormap is a tree -- more precisely, a DAG -- indexed at each level
183     * by a byt of the chr, to map the chr to a color efficiently. Because
184     * lower sections of the tree can be shared, it can exploit the usual
185     * sparseness of such a mapping table. The tree is always NBYTS levels
186     * deep (in the past it was shallower during construction but was "filled"
187     * to full depth at the end of that); areas that are unaltered as yet point
188     * to "fill blocks" which are entirely WHITE in color.
189     */
190    
191     /* the tree itself */
192     struct colors {
193     color ccolor[BYTTAB];
194     };
195     struct ptrs {
196     union tree *pptr[BYTTAB];
197     };
198     union tree {
199     struct colors colors;
200     struct ptrs ptrs;
201     };
202     #define tcolor colors.ccolor
203     #define tptr ptrs.pptr
204    
205     /* internal per-color structure for the color machinery */
206     struct colordesc {
207     uchr nchrs; /* number of chars of this color */
208     color sub; /* open subcolor (if any); free chain ptr */
209     # define NOSUB COLORLESS
210     struct arc *arcs; /* color chain */
211     int flags;
212     # define FREECOL 01 /* currently free */
213     # define PSEUDO 02 /* pseudocolor, no real chars */
214     # define UNUSEDCOLOR(cd) ((cd)->flags&FREECOL)
215     union tree *block; /* block of solid color, if any */
216     };
217    
218     /* the color map itself */
219     struct colormap {
220     int magic;
221     # define CMMAGIC 0x876
222     struct vars *v; /* for compile error reporting */
223     size_t ncds; /* number of colordescs */
224     size_t max; /* highest in use */
225     color free; /* beginning of free chain (if non-0) */
226     struct colordesc *cd;
227     # define CDEND(cm) (&(cm)->cd[(cm)->max + 1])
228     # define NINLINECDS ((size_t)10)
229     struct colordesc cdspace[NINLINECDS];
230     union tree tree[NBYTS]; /* tree top, plus fill blocks */
231     };
232    
233     /* optimization magic to do fast chr->color mapping */
234     #define B0(c) ((c) & BYTMASK)
235     #define B1(c) (((c)>>BYTBITS) & BYTMASK)
236     #define B2(c) (((c)>>(2*BYTBITS)) & BYTMASK)
237     #define B3(c) (((c)>>(3*BYTBITS)) & BYTMASK)
238     #if NBYTS == 1
239     #define GETCOLOR(cm, c) ((cm)->tree->tcolor[B0(c)])
240     #endif
241     /* beware, for NBYTS>1, GETCOLOR() is unsafe -- 2nd arg used repeatedly */
242     #if NBYTS == 2
243     #define GETCOLOR(cm, c) ((cm)->tree->tptr[B1(c)]->tcolor[B0(c)])
244     #endif
245     #if NBYTS == 4
246     #define GETCOLOR(cm, c) ((cm)->tree->tptr[B3(c)]->tptr[B2(c)]->tptr[B1(c)]->tcolor[B0(c)])
247     #endif
248    
249    
250    
251     /*
252     * Interface definitions for locale-interface functions in locale.c.
253     * Multi-character collating elements (MCCEs) cause most of the trouble.
254     */
255     struct cvec {
256     int nchrs; /* number of chrs */
257     int chrspace; /* number of chrs possible */
258     chr *chrs; /* pointer to vector of chrs */
259     int nranges; /* number of ranges (chr pairs) */
260     int rangespace; /* number of chrs possible */
261     chr *ranges; /* pointer to vector of chr pairs */
262     int nmcces; /* number of MCCEs */
263     int mccespace; /* number of MCCEs possible */
264     int nmccechrs; /* number of chrs used for MCCEs */
265     chr *mcces[1]; /* pointers to 0-terminated MCCEs */
266     /* and both batches of chrs are on the end */
267     };
268    
269     /* caution: this value cannot be changed easily */
270     #define MAXMCCE 2 /* length of longest MCCE */
271    
272    
273    
274     /*
275     * definitions for NFA internal representation
276     *
277     * Having a "from" pointer within each arc may seem redundant, but it
278     * saves a lot of hassle.
279     */
280     struct state;
281    
282     struct arc {
283     int type;
284     # define ARCFREE '\0'
285     color co;
286     struct state *from; /* where it's from (and contained within) */
287     struct state *to; /* where it's to */
288     struct arc *outchain; /* *from's outs chain or free chain */
289     # define freechain outchain
290     struct arc *inchain; /* *to's ins chain */
291     struct arc *colorchain; /* color's arc chain */
292     };
293    
294     struct arcbatch { /* for bulk allocation of arcs */
295     struct arcbatch *next;
296     # define ABSIZE 10
297     struct arc a[ABSIZE];
298     };
299    
300     struct state {
301     int no;
302     # define FREESTATE (-1)
303     char flag; /* marks special states */
304     int nins; /* number of inarcs */
305     struct arc *ins; /* chain of inarcs */
306     int nouts; /* number of outarcs */
307     struct arc *outs; /* chain of outarcs */
308     struct arc *free; /* chain of free arcs */
309     struct state *tmp; /* temporary for traversal algorithms */
310     struct state *next; /* chain for traversing all */
311     struct state *prev; /* back chain */
312     struct arcbatch oas; /* first arcbatch, avoid malloc in easy case */
313     int noas; /* number of arcs used in first arcbatch */
314     };
315    
316     struct nfa {
317     struct state *pre; /* pre-initial state */
318     struct state *init; /* initial state */
319     struct state *final; /* final state */
320     struct state *post; /* post-final state */
321     int nstates; /* for numbering states */
322     struct state *states; /* state-chain header */
323     struct state *slast; /* tail of the chain */
324     struct state *free; /* free list */
325     struct colormap *cm; /* the color map */
326     color bos[2]; /* colors, if any, assigned to BOS and BOL */
327     color eos[2]; /* colors, if any, assigned to EOS and EOL */
328     struct vars *v; /* simplifies compile error reporting */
329     struct nfa *parent; /* parent NFA, if any */
330     };
331    
332    
333    
334     /*
335     * definitions for compacted NFA
336     */
337     struct carc {
338     color co; /* COLORLESS is list terminator */
339     int to; /* state number */
340     };
341    
342     struct cnfa {
343     int nstates; /* number of states */
344     int ncolors; /* number of colors */
345     int flags;
346     # define HASLACONS 01 /* uses lookahead constraints */
347     int pre; /* setup state number */
348     int post; /* teardown state number */
349     color bos[2]; /* colors, if any, assigned to BOS and BOL */
350     color eos[2]; /* colors, if any, assigned to EOS and EOL */
351     struct carc **states; /* vector of pointers to outarc lists */
352     struct carc *arcs; /* the area for the lists */
353     };
354     #define ZAPCNFA(cnfa) ((cnfa).nstates = 0)
355     #define NULLCNFA(cnfa) ((cnfa).nstates == 0)
356    
357    
358    
359     /*
360     * subexpression tree
361     */
362     struct subre {
363     char op; /* '|', '.' (concat), 'b' (backref), '(', '=' */
364     char flags;
365     # define LONGER 01 /* prefers longer match */
366     # define SHORTER 02 /* prefers shorter match */
367     # define MIXED 04 /* mixed preference below */
368     # define CAP 010 /* capturing parens below */
369     # define BACKR 020 /* back reference below */
370     # define INUSE 0100 /* in use in final tree */
371     # define LOCAL 03 /* bits which may not propagate up */
372     # define LMIX(f) ((f)<<2) /* LONGER -> MIXED */
373     # define SMIX(f) ((f)<<1) /* SHORTER -> MIXED */
374     # define UP(f) (((f)&~LOCAL) | (LMIX(f) & SMIX(f) & MIXED))
375     # define MESSY(f) ((f)&(MIXED|CAP|BACKR))
376     # define PREF(f) ((f)&LOCAL)
377     # define PREF2(f1, f2) ((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
378     # define COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2))
379     short retry; /* index into retry memory */
380     int subno; /* subexpression number (for 'b' and '(') */
381     short min; /* min repetitions, for backref only */
382     short max; /* max repetitions, for backref only */
383     struct subre *left; /* left child, if any (also freelist chain) */
384     struct subre *right; /* right child, if any */
385     struct state *begin; /* outarcs from here... */
386     struct state *end; /* ...ending in inarcs here */
387     struct cnfa cnfa; /* compacted NFA, if any */
388     struct subre *chain; /* for bookkeeping and error cleanup */
389     };
390    
391    
392    
393     /*
394     * table of function pointers for generic manipulation functions
395     * A regex_t's re_fns points to one of these.
396     */
397     struct fns {
398     VOID FUNCPTR(free, (regex_t *));
399     };
400    
401    
402    
403     /*
404     * the insides of a regex_t, hidden behind a void *
405     */
406     struct guts {
407     int magic;
408     # define GUTSMAGIC 0xfed9
409     int cflags; /* copy of compile flags */
410     long info; /* copy of re_info */
411     size_t nsub; /* copy of re_nsub */
412     struct subre *tree;
413     struct cnfa search; /* for fast preliminary search */
414     int ntree;
415     struct colormap cmap;
416     int FUNCPTR(compare, (CONST chr *, CONST chr *, size_t));
417     struct subre *lacons; /* lookahead-constraint vector */
418     int nlacons; /* size of lacons */
419     };
420    
421     /* End of regguts.h */

Properties

Name Value
svn:eol-style native
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25