os/persistentdata/persistentstorage/sqlite3api/TEST/TCL/tcldistribution/generic/regguts.h
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/sqlite3api/TEST/TCL/tcldistribution/generic/regguts.h Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,420 @@
1.4 +/*
1.5 + * Internal interface definitions, etc., for the reg package
1.6 + *
1.7 + * Copyright (c) 1998, 1999 Henry Spencer. All rights reserved.
1.8 + *
1.9 + * Development of this software was funded, in part, by Cray Research Inc.,
1.10 + * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
1.11 + * Corporation, none of whom are responsible for the results. The author
1.12 + * thanks all of them.
1.13 + *
1.14 + * Redistribution and use in source and binary forms -- with or without
1.15 + * modification -- are permitted for any purpose, provided that
1.16 + * redistributions in source form retain this entire copyright notice and
1.17 + * indicate the origin and nature of any modifications.
1.18 + *
1.19 + * I'd appreciate being given credit for this package in the documentation
1.20 + * of software which uses it, but that is not a requirement.
1.21 + *
1.22 + * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
1.23 + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
1.24 + * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
1.25 + * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
1.26 + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
1.27 + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
1.28 + * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
1.29 + * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
1.30 + * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
1.31 + * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.32 + */
1.33 +
1.34 +
1.35 +
1.36 +/*
1.37 + * Environmental customization. It should not (I hope) be necessary to
1.38 + * alter the file you are now reading -- regcustom.h should handle it all,
1.39 + * given care here and elsewhere.
1.40 + */
1.41 +#include "regcustom.h"
1.42 +
1.43 +
1.44 +
1.45 +/*
1.46 + * Things that regcustom.h might override.
1.47 + */
1.48 +
1.49 +/* standard header files (NULL is a reasonable indicator for them) */
1.50 +#ifndef NULL
1.51 +#include <stdio.h>
1.52 +#include <stdlib.h>
1.53 +#include <ctype.h>
1.54 +#include <limits.h>
1.55 +#include <string.h>
1.56 +#endif
1.57 +
1.58 +/* assertions */
1.59 +#ifndef assert
1.60 +# ifndef REG_DEBUG
1.61 +# ifndef NDEBUG
1.62 +# define NDEBUG /* no assertions */
1.63 +# endif
1.64 +# endif
1.65 +#include <assert.h>
1.66 +#endif
1.67 +
1.68 +/* voids */
1.69 +#ifndef VOID
1.70 +#define VOID void /* for function return values */
1.71 +#endif
1.72 +#ifndef DISCARD
1.73 +#define DISCARD VOID /* for throwing values away */
1.74 +#endif
1.75 +#ifndef PVOID
1.76 +#define PVOID VOID * /* generic pointer */
1.77 +#endif
1.78 +#ifndef VS
1.79 +#define VS(x) ((PVOID)(x)) /* cast something to generic ptr */
1.80 +#endif
1.81 +#ifndef NOPARMS
1.82 +#define NOPARMS VOID /* for empty parm lists */
1.83 +#endif
1.84 +
1.85 +/* const */
1.86 +#ifndef CONST
1.87 +#define CONST const /* for old compilers, might be empty */
1.88 +#endif
1.89 +
1.90 +/* function-pointer declarator */
1.91 +#ifndef FUNCPTR
1.92 +#if __STDC__ >= 1
1.93 +#define FUNCPTR(name, args) (*name)args
1.94 +#else
1.95 +#define FUNCPTR(name, args) (*name)()
1.96 +#endif
1.97 +#endif
1.98 +
1.99 +/* memory allocation */
1.100 +#ifndef MALLOC
1.101 +#define MALLOC(n) malloc(n)
1.102 +#endif
1.103 +#ifndef REALLOC
1.104 +#define REALLOC(p, n) realloc(VS(p), n)
1.105 +#endif
1.106 +#ifndef FREE
1.107 +#define FREE(p) free(VS(p))
1.108 +#endif
1.109 +
1.110 +/* want size of a char in bits, and max value in bounded quantifiers */
1.111 +#ifndef CHAR_BIT
1.112 +#include <limits.h>
1.113 +#endif
1.114 +#ifndef _POSIX2_RE_DUP_MAX
1.115 +#define _POSIX2_RE_DUP_MAX 255 /* normally from <limits.h> */
1.116 +#endif
1.117 +
1.118 +
1.119 +
1.120 +/*
1.121 + * misc
1.122 + */
1.123 +
1.124 +#define NOTREACHED 0
1.125 +#define xxx 1
1.126 +
1.127 +#define DUPMAX _POSIX2_RE_DUP_MAX
1.128 +#define INFINITY (DUPMAX+1)
1.129 +
1.130 +#define REMAGIC 0xfed7 /* magic number for main struct */
1.131 +
1.132 +
1.133 +
1.134 +/*
1.135 + * debugging facilities
1.136 + */
1.137 +#ifdef REG_DEBUG
1.138 +/* FDEBUG does finite-state tracing */
1.139 +#define FDEBUG(arglist) { if (v->eflags®_FTRACE) printf arglist; }
1.140 +/* MDEBUG does higher-level tracing */
1.141 +#define MDEBUG(arglist) { if (v->eflags®_MTRACE) printf arglist; }
1.142 +#else
1.143 +#define FDEBUG(arglist) {}
1.144 +#define MDEBUG(arglist) {}
1.145 +#endif
1.146 +
1.147 +
1.148 +
1.149 +/*
1.150 + * bitmap manipulation
1.151 + */
1.152 +#define UBITS (CHAR_BIT * sizeof(unsigned))
1.153 +#define BSET(uv, sn) ((uv)[(sn)/UBITS] |= (unsigned)1 << ((sn)%UBITS))
1.154 +#define ISBSET(uv, sn) ((uv)[(sn)/UBITS] & ((unsigned)1 << ((sn)%UBITS)))
1.155 +
1.156 +
1.157 +
1.158 +/*
1.159 + * We dissect a chr into byts for colormap table indexing. Here we define
1.160 + * a byt, which will be the same as a byte on most machines... The exact
1.161 + * size of a byt is not critical, but about 8 bits is good, and extraction
1.162 + * of 8-bit chunks is sometimes especially fast.
1.163 + */
1.164 +#ifndef BYTBITS
1.165 +#define BYTBITS 8 /* bits in a byt */
1.166 +#endif
1.167 +#define BYTTAB (1<<BYTBITS) /* size of table with one entry per byt value */
1.168 +#define BYTMASK (BYTTAB-1) /* bit mask for byt */
1.169 +#define NBYTS ((CHRBITS+BYTBITS-1)/BYTBITS)
1.170 +/* the definition of GETCOLOR(), below, assumes NBYTS <= 4 */
1.171 +
1.172 +
1.173 +
1.174 +/*
1.175 + * As soon as possible, we map chrs into equivalence classes -- "colors" --
1.176 + * which are of much more manageable number.
1.177 + */
1.178 +typedef short color; /* colors of characters */
1.179 +typedef int pcolor; /* what color promotes to */
1.180 +#define COLORLESS (-1) /* impossible color */
1.181 +#define WHITE 0 /* default color, parent of all others */
1.182 +
1.183 +
1.184 +
1.185 +/*
1.186 + * A colormap is a tree -- more precisely, a DAG -- indexed at each level
1.187 + * by a byt of the chr, to map the chr to a color efficiently. Because
1.188 + * lower sections of the tree can be shared, it can exploit the usual
1.189 + * sparseness of such a mapping table. The tree is always NBYTS levels
1.190 + * deep (in the past it was shallower during construction but was "filled"
1.191 + * to full depth at the end of that); areas that are unaltered as yet point
1.192 + * to "fill blocks" which are entirely WHITE in color.
1.193 + */
1.194 +
1.195 +/* the tree itself */
1.196 +struct colors {
1.197 + color ccolor[BYTTAB];
1.198 +};
1.199 +struct ptrs {
1.200 + union tree *pptr[BYTTAB];
1.201 +};
1.202 +union tree {
1.203 + struct colors colors;
1.204 + struct ptrs ptrs;
1.205 +};
1.206 +#define tcolor colors.ccolor
1.207 +#define tptr ptrs.pptr
1.208 +
1.209 +/* internal per-color structure for the color machinery */
1.210 +struct colordesc {
1.211 + uchr nchrs; /* number of chars of this color */
1.212 + color sub; /* open subcolor (if any); free chain ptr */
1.213 +# define NOSUB COLORLESS
1.214 + struct arc *arcs; /* color chain */
1.215 + int flags;
1.216 +# define FREECOL 01 /* currently free */
1.217 +# define PSEUDO 02 /* pseudocolor, no real chars */
1.218 +# define UNUSEDCOLOR(cd) ((cd)->flags&FREECOL)
1.219 + union tree *block; /* block of solid color, if any */
1.220 +};
1.221 +
1.222 +/* the color map itself */
1.223 +struct colormap {
1.224 + int magic;
1.225 +# define CMMAGIC 0x876
1.226 + struct vars *v; /* for compile error reporting */
1.227 + size_t ncds; /* number of colordescs */
1.228 + size_t max; /* highest in use */
1.229 + color free; /* beginning of free chain (if non-0) */
1.230 + struct colordesc *cd;
1.231 +# define CDEND(cm) (&(cm)->cd[(cm)->max + 1])
1.232 +# define NINLINECDS ((size_t)10)
1.233 + struct colordesc cdspace[NINLINECDS];
1.234 + union tree tree[NBYTS]; /* tree top, plus fill blocks */
1.235 +};
1.236 +
1.237 +/* optimization magic to do fast chr->color mapping */
1.238 +#define B0(c) ((c) & BYTMASK)
1.239 +#define B1(c) (((c)>>BYTBITS) & BYTMASK)
1.240 +#define B2(c) (((c)>>(2*BYTBITS)) & BYTMASK)
1.241 +#define B3(c) (((c)>>(3*BYTBITS)) & BYTMASK)
1.242 +#if NBYTS == 1
1.243 +#define GETCOLOR(cm, c) ((cm)->tree->tcolor[B0(c)])
1.244 +#endif
1.245 +/* beware, for NBYTS>1, GETCOLOR() is unsafe -- 2nd arg used repeatedly */
1.246 +#if NBYTS == 2
1.247 +#define GETCOLOR(cm, c) ((cm)->tree->tptr[B1(c)]->tcolor[B0(c)])
1.248 +#endif
1.249 +#if NBYTS == 4
1.250 +#define GETCOLOR(cm, c) ((cm)->tree->tptr[B3(c)]->tptr[B2(c)]->tptr[B1(c)]->tcolor[B0(c)])
1.251 +#endif
1.252 +
1.253 +
1.254 +
1.255 +/*
1.256 + * Interface definitions for locale-interface functions in locale.c.
1.257 + * Multi-character collating elements (MCCEs) cause most of the trouble.
1.258 + */
1.259 +struct cvec {
1.260 + int nchrs; /* number of chrs */
1.261 + int chrspace; /* number of chrs possible */
1.262 + chr *chrs; /* pointer to vector of chrs */
1.263 + int nranges; /* number of ranges (chr pairs) */
1.264 + int rangespace; /* number of chrs possible */
1.265 + chr *ranges; /* pointer to vector of chr pairs */
1.266 + int nmcces; /* number of MCCEs */
1.267 + int mccespace; /* number of MCCEs possible */
1.268 + int nmccechrs; /* number of chrs used for MCCEs */
1.269 + chr *mcces[1]; /* pointers to 0-terminated MCCEs */
1.270 + /* and both batches of chrs are on the end */
1.271 +};
1.272 +
1.273 +/* caution: this value cannot be changed easily */
1.274 +#define MAXMCCE 2 /* length of longest MCCE */
1.275 +
1.276 +
1.277 +
1.278 +/*
1.279 + * definitions for NFA internal representation
1.280 + *
1.281 + * Having a "from" pointer within each arc may seem redundant, but it
1.282 + * saves a lot of hassle.
1.283 + */
1.284 +struct state;
1.285 +
1.286 +struct arc {
1.287 + int type;
1.288 +# define ARCFREE '\0'
1.289 + color co;
1.290 + struct state *from; /* where it's from (and contained within) */
1.291 + struct state *to; /* where it's to */
1.292 + struct arc *outchain; /* *from's outs chain or free chain */
1.293 +# define freechain outchain
1.294 + struct arc *inchain; /* *to's ins chain */
1.295 + struct arc *colorchain; /* color's arc chain */
1.296 +};
1.297 +
1.298 +struct arcbatch { /* for bulk allocation of arcs */
1.299 + struct arcbatch *next;
1.300 +# define ABSIZE 10
1.301 + struct arc a[ABSIZE];
1.302 +};
1.303 +
1.304 +struct state {
1.305 + int no;
1.306 +# define FREESTATE (-1)
1.307 + char flag; /* marks special states */
1.308 + int nins; /* number of inarcs */
1.309 + struct arc *ins; /* chain of inarcs */
1.310 + int nouts; /* number of outarcs */
1.311 + struct arc *outs; /* chain of outarcs */
1.312 + struct arc *free; /* chain of free arcs */
1.313 + struct state *tmp; /* temporary for traversal algorithms */
1.314 + struct state *next; /* chain for traversing all */
1.315 + struct state *prev; /* back chain */
1.316 + struct arcbatch oas; /* first arcbatch, avoid malloc in easy case */
1.317 + int noas; /* number of arcs used in first arcbatch */
1.318 +};
1.319 +
1.320 +struct nfa {
1.321 + struct state *pre; /* pre-initial state */
1.322 + struct state *init; /* initial state */
1.323 + struct state *final; /* final state */
1.324 + struct state *post; /* post-final state */
1.325 + int nstates; /* for numbering states */
1.326 + struct state *states; /* state-chain header */
1.327 + struct state *slast; /* tail of the chain */
1.328 + struct state *free; /* free list */
1.329 + struct colormap *cm; /* the color map */
1.330 + color bos[2]; /* colors, if any, assigned to BOS and BOL */
1.331 + color eos[2]; /* colors, if any, assigned to EOS and EOL */
1.332 + struct vars *v; /* simplifies compile error reporting */
1.333 + struct nfa *parent; /* parent NFA, if any */
1.334 +};
1.335 +
1.336 +
1.337 +
1.338 +/*
1.339 + * definitions for compacted NFA
1.340 + */
1.341 +struct carc {
1.342 + color co; /* COLORLESS is list terminator */
1.343 + int to; /* state number */
1.344 +};
1.345 +
1.346 +struct cnfa {
1.347 + int nstates; /* number of states */
1.348 + int ncolors; /* number of colors */
1.349 + int flags;
1.350 +# define HASLACONS 01 /* uses lookahead constraints */
1.351 + int pre; /* setup state number */
1.352 + int post; /* teardown state number */
1.353 + color bos[2]; /* colors, if any, assigned to BOS and BOL */
1.354 + color eos[2]; /* colors, if any, assigned to EOS and EOL */
1.355 + struct carc **states; /* vector of pointers to outarc lists */
1.356 + struct carc *arcs; /* the area for the lists */
1.357 +};
1.358 +#define ZAPCNFA(cnfa) ((cnfa).nstates = 0)
1.359 +#define NULLCNFA(cnfa) ((cnfa).nstates == 0)
1.360 +
1.361 +
1.362 +
1.363 +/*
1.364 + * subexpression tree
1.365 + */
1.366 +struct subre {
1.367 + char op; /* '|', '.' (concat), 'b' (backref), '(', '=' */
1.368 + char flags;
1.369 +# define LONGER 01 /* prefers longer match */
1.370 +# define SHORTER 02 /* prefers shorter match */
1.371 +# define MIXED 04 /* mixed preference below */
1.372 +# define CAP 010 /* capturing parens below */
1.373 +# define BACKR 020 /* back reference below */
1.374 +# define INUSE 0100 /* in use in final tree */
1.375 +# define LOCAL 03 /* bits which may not propagate up */
1.376 +# define LMIX(f) ((f)<<2) /* LONGER -> MIXED */
1.377 +# define SMIX(f) ((f)<<1) /* SHORTER -> MIXED */
1.378 +# define UP(f) (((f)&~LOCAL) | (LMIX(f) & SMIX(f) & MIXED))
1.379 +# define MESSY(f) ((f)&(MIXED|CAP|BACKR))
1.380 +# define PREF(f) ((f)&LOCAL)
1.381 +# define PREF2(f1, f2) ((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
1.382 +# define COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2))
1.383 + short retry; /* index into retry memory */
1.384 + int subno; /* subexpression number (for 'b' and '(') */
1.385 + short min; /* min repetitions, for backref only */
1.386 + short max; /* max repetitions, for backref only */
1.387 + struct subre *left; /* left child, if any (also freelist chain) */
1.388 + struct subre *right; /* right child, if any */
1.389 + struct state *begin; /* outarcs from here... */
1.390 + struct state *end; /* ...ending in inarcs here */
1.391 + struct cnfa cnfa; /* compacted NFA, if any */
1.392 + struct subre *chain; /* for bookkeeping and error cleanup */
1.393 +};
1.394 +
1.395 +
1.396 +
1.397 +/*
1.398 + * table of function pointers for generic manipulation functions
1.399 + * A regex_t's re_fns points to one of these.
1.400 + */
1.401 +struct fns {
1.402 + VOID FUNCPTR(free, (regex_t *));
1.403 +};
1.404 +
1.405 +
1.406 +
1.407 +/*
1.408 + * the insides of a regex_t, hidden behind a void *
1.409 + */
1.410 +struct guts {
1.411 + int magic;
1.412 +# define GUTSMAGIC 0xfed9
1.413 + int cflags; /* copy of compile flags */
1.414 + long info; /* copy of re_info */
1.415 + size_t nsub; /* copy of re_nsub */
1.416 + struct subre *tree;
1.417 + struct cnfa search; /* for fast preliminary search */
1.418 + int ntree;
1.419 + struct colormap cmap;
1.420 + int FUNCPTR(compare, (CONST chr *, CONST chr *, size_t));
1.421 + struct subre *lacons; /* lookahead-constraint vector */
1.422 + int nlacons; /* size of lacons */
1.423 +};