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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 71 - (show annotations) (download)
Sat Nov 5 11:07:06 2016 UTC (7 years, 4 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 /* $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