ocker@lan.informatik.tu-muenchen.dbp.de (Wolfgang Ocker) (10/20/88)
#! /bin/sh # This is a shell archive. Remove anything before this line, then unpack # it by saving it into a file and typing "sh file". To overwrite existing # files, type "sh file -c". You can also feed this as standard input via # unshar, or by typing "sh <file", e.g.. If this archive is complete, you # will see the following message at the end: # "End of archive 5 (of 5)." # Contents: info.c rnd.c regexp.c # Wrapped by weo@recsys on Tue Oct 11 14:24:50 1988 PATH=/bin:/usr/bin:/usr/ucb ; export PATH if test -f 'info.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'info.c'\" else echo shar: Extracting \"'info.c'\" \(10915 characters\) sed "s/^X//" >'info.c' <<'END_OF_FILE' X/* X * SYSINFO Library X * X * Copyrights (c) 1988 by reccoware systems, Wolfgang Ocker, Puchheim X * X * X * X * IMPORTANT NOTICE X * ===================================================================== X * X * I would like to establish the SYSINFO concept as a STANDARD for X * OS-9/68000. So please DON'T CHANGE ANYTHING. Please send any bug X * reports or suggestions to X * X * X * Wolfgang Ocker X * Lochhauserstrasse 35a X * D-8039 Puchheim X * Tel. +49 89 / 80 77 02 X * X * e-mail: weo@recco (...!pyramid!tmpmbx!recco!weo) X * weo@altger (...!altnet!altger!weo) X * ocker@lan.informatik.tu-muenchen.dbp.de X * X * X * I will maintain the SYSINFO package and keep it (upward) compatible! X * You may not distribute any modified versions, or programs which rely X * on a modified version. X * X * If you don't like SYSINFO, don't use it! X */ X X/* X * Revision history X * X * # Date Comments By X * -------------------------------------------------------------------- --- X * 00 09/16/88 Prepared for net release weo X * 01 10/06/88 Corrected modlink parameters weo X * X */ X X#define PATCHLEVEL 1 X X#include <stdio.h> X#include <module.h> X#include <strings.h> X#include <procid.h> X#include <errno.h> X#include "infomod.h" X Xextern int errno; Xstatic char *Copyright = "Copyrights (c) 1988 by reccoware systems puchheim"; X X/* X * l i n k _ i n f o _ m o d X * X * Link to SYSINFO data module X */ Xstatic INFO * Xlink_info_mod() X{ X register mod_exec *info_module; X X if ((info_module = (mod_exec *) modlink(INFO_MODULE_NAME, X mktypelang(MT_DATA, ML_ANY))) == X (mod_exec *) -1) X return(NULL); /* can't link */ X X return((INFO *) (((char *) info_module) + info_module->_mexec)); X} X X/* X * u n l i n k _ i n f o _ m o d X * X * unlink from SYSINFO data module X */ Xstatic void Xunlink_info_mod() X{ X (void) munload(INFO_MODULE_NAME, 0x0400); X} X X/* X * i n f o _ e n t r y X * X * Get pointer to an entry within the SYSINFO data module. Needs X * name of the entry (case sensitiv) and its type. X */ Xstatic ENTRY * Xinfo_entry(name, type) X register char *name; X register int type; X{ X register INFO *info; X register int i; X X if ((info = link_info_mod()) == NULL) /* Link to data module */ X return(NULL); X X /* X * Check revision (for compatiblity reasons) X */ X if (info->rev != REVISION) { X unlink_info_mod(); X return(NULL); X } X X for (i = 0; i < info->num; i++) /* search entry by name */ X if (!strcmp(info->entry[i].name, name) && X (info->entry[i].type == type)) /* desired type? */ X return(&(info->entry[i])); /* all ok, return pointer */ X X unlink_info_mod(); X errno = E_PNNF; X return(NULL); X} X X/* X * i n f o _ t y p e X * X * Determine type of SYSINFO entry. Needs only the name of the entry. X */ Xint Xinfo_type(name) X char *name; X{ X register INFO *info; X register int i; X register int type; X X if ((info = link_info_mod()) == NULL) /* Link to data module */ X return(NULL); X X for (i = 0; i < info->num; i++) /* Search entry */ X if (!strcmp(info->entry[i].name, name)) { X type = info->entry[i].type; X unlink_info_mod(); X return(type); /* found, return type */ X } X X unlink_info_mod(); X errno = E_PNNF; X return(FAILED); X} X X/* X * i n f o _ s t r X * X * Get a string from SYSINFO. Needs name, buffer, and max. length. X */ Xchar * Xinfo_str(name, str, len) X register char *name; X register char *str; X register int len; X{ X register ENTRY *entry; X X /* X * Get a pointer to the desired entry X */ X if ((entry = info_entry(name, T_STRING)) == NULL) X return(NULL); /* Not found */ X X (void) strncpy(str, entry->data, len-1); /* Copy */ X str[len-1] = '\0'; X unlink_info_mod(); X return(str); X} X X/* X * i n f o _ n u m X * X * Get number from SYSINFO X */ Xint Xinfo_num(name) X register char *name; X{ X register ENTRY *entry; X X /* X * Get a pointer to the entry X */ X if ((entry = info_entry(name, T_NUM)) == NULL) X return(FAILED); X X unlink_info_mod(); X return(*((int *) entry->data)); X} X X/* X * i n f o _ i s _ l o c k e d X * X * Check, if a lock entry is locked. Needs name. X */ Xint Xinfo_is_locked(name) X register char *name; X{ X int EvID; X int status; X procid procdesc; X register LOCK *lock; X register ENTRY *entry; X X /* X * Remove a leading slash ("/t7" is equal to "t7") X */ X if (name[0] == '/') X name++; X X /* X * Get pointer to entry X */ X if ((entry = info_entry(name, T_LOCK)) == NULL) X return(FAILED); X X /* X * Link to the SYSINFO event X */ X if ((EvID = _ev_link(INFO_EVENT_NAME)) == -1) { X unlink_info_mod(); X return(FAILED); X } X X /* X * Wait, until we can access the entry. X * We should check for a timeout here ... (perhaps alarms?) X */ X while (_ev_wait(EvID, 0, 0) != 0) ; X X /* X * Now we can access the entry X */ X lock = (LOCK *) entry->data; X status = lock->status; /* Get status */ X X if (status == ST_LOCKED) /* Locked? */ X if (lock->pid == 0) /* Process ID? */ X status = ST_FREE; /* NOT LOCKED! */ X else X /* X * Now we have to check, whether the existing process X * still exists. We do this by checking the PID and the X * start time of the locking process X */ X if (_get_process_desc(lock->pid, sizeof(procdesc), X &procdesc) == -1 || X lock->timbeg != procdesc._timbeg || X lock->datbeg != procdesc._datbeg) X status = ST_FREE; /* Meanwhile, the process has died! */ X X (void) _ev_signal(EvID, 0); X _ev_unlink(EvID); X unlink_info_mod(); X X return(status == ST_FREE ? OK : FAILED); X} X X/* X * i n f o _ l o c k X * X * Lock a SYSINFO entry X */ Xint Xinfo_lock(name, signal) X register char *name; X int signal; X{ X int EvID; X register LOCK *lock; X procid procdesc; X register int timeout; X register ENTRY *entry; X X if (name[0] == '/') X name++; X X if ((entry = info_entry(name, T_LOCK)) == NULL) X return(FAILED); X X if ((EvID = _ev_link(INFO_EVENT_NAME)) == -1) { X unlink_info_mod(); X return(FAILED); X } X X while (_ev_wait(EvID, 0, 0) != 0) ; X X /* X * Now we can access the entry X */ X lock = (LOCK *) entry->data; X X if (lock->status == ST_LOCKED) { /* locked? */ X if (lock->pid != 0) { /* Process ID given? */ X timeout = 0; X while (lock->status == ST_LOCKED && X _get_process_desc(lock->pid, sizeof(procdesc), X &procdesc) != -1 && X lock->timbeg == procdesc._timbeg && X lock->datbeg == procdesc._datbeg) { X X if (timeout++ > 20) { /* Timeout? */ X (void) _ev_signal(EvID, 0); X _ev_unlink(EvID); X unlink_info_mod(); X return(FAILED); X } X X if (lock->signal != -1) /* May we send a signal to the */ X /* locking process? */ X (void) kill(lock->pid, lock->signal); X X (void) _ev_signal(EvID, 0); /* Now others may access */ X (void) sleep(5); /* Wait a bit ... */ X while (_ev_wait(EvID, 0, 0) != 0) ; X } X } X } X X lock->status = ST_LOCKED; X lock->timestamp = time(NULL); X lock->pid = getpid(); X lock->signal = signal; /* A process which want lock may send us */ X /* this signal */ X X if (_get_process_desc(lock->pid, sizeof(procdesc), &procdesc) != -1) { X lock->timbeg = procdesc._timbeg; /* Our start time */ X lock->datbeg = procdesc._datbeg; X } X else { X lock->timbeg = 0; X lock->datbeg = 0; X } X X (void) _ev_signal(EvID, 0); X _ev_unlink(EvID); X unlink_info_mod(); X return(OK); X} X X/* X * i n f o _ u n l o c k X * X * Unlock X */ Xint Xinfo_unlock(name) X register char *name; X{ X int EvID; X procid procdesc; X register LOCK *lock; X register ENTRY *entry; X X if (name[0] == '/') X name++; X X if ((entry = info_entry(name, T_LOCK)) == NULL) X return(FAILED); X X if ((EvID = _ev_link(INFO_EVENT_NAME)) == -1) { X unlink_info_mod(); X return(FAILED); X } X X while (_ev_wait(EvID, 0, 0) != 0); X X lock = (LOCK *) entry->data; X X if (lock->status == ST_LOCKED && lock->pid == getpid() && X _get_process_desc(lock->pid, sizeof(procdesc), &procdesc) != -1 && X lock->timbeg == procdesc._timbeg && X lock->datbeg == procdesc._datbeg) /* IS it "our" lock? */ X lock->status = ST_FREE; /* Unlock */ X X (void) _ev_signal(EvID, 0); X _ev_unlink(EvID); X unlink_info_mod(); X return(OK); X} X X/* X * i n f o _ c h a n g e X * X * Change signal number of a lock X */ Xint Xinfo_change(name, signal) X register char *name; X int signal; X{ X int err; X int EvID; X register LOCK *lock; X procid procdesc; X register ENTRY *entry; X X if (name[0] == '/') X name++; X X if ((entry = info_entry(name, T_LOCK)) == NULL) X return(FAILED); X X if ((EvID = _ev_link(INFO_EVENT_NAME)) == -1) { X unlink_info_mod(); X return(FAILED); X } X X while (_ev_wait(EvID, 0, 0) != 0) ; X X lock = (LOCK *) entry->data; X X err = FAILED; X X if (lock->status == ST_LOCKED && lock->pid == getpid() && X _get_process_desc(lock->pid, sizeof(procdesc), &procdesc) != -1 && X lock->timbeg == procdesc._timbeg && X lock->datbeg == procdesc._datbeg) { /* Locking proc. still existing? */ X err = OK; X lock->signal = signal; /* new signal code */ X } X X (void) _ev_signal(EvID, 0); X _ev_unlink(EvID); X unlink_info_mod(); X return(err); X} X X/* X * i n f o _ s i g n a l X * X * Send a signal to a locking process X */ Xint Xinfo_signal(name) X register char *name; X{ X int err; X int EvID; X register LOCK *lock; X procid procdesc; X register ENTRY *entry; X X if (name[0] == '/') X name++; X X if ((entry = info_entry(name, T_LOCK)) == NULL) X return(FAILED); X X if ((EvID = _ev_link(INFO_EVENT_NAME)) == -1) { X unlink_info_mod(); X return(FAILED); X } X X while (_ev_wait(EvID, 0, 0) != 0) ; X X lock = (LOCK *) entry->data; X X err = FAILED; X X if (lock->status == ST_LOCKED && X _get_process_desc(lock->pid, sizeof(procdesc), &procdesc) != -1 && X lock->timbeg == procdesc._timbeg && X lock->datbeg == procdesc._datbeg) { /* Locking proc. still existing? */ X X if (lock->signal != -1) { /* May we send a signal? */ X err = OK; X (void) kill(lock->pid, lock->signal); /* Yes, "kill" him! */ X } X } X X (void) _ev_signal(EvID, 0); X _ev_unlink(EvID); X unlink_info_mod(); X return(err); X} X END_OF_FILE if test 10915 -ne `wc -c <'info.c'`; then echo shar: \"'info.c'\" unpacked with wrong size! fi # end of 'info.c' fi if test -f 'rnd.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'rnd.c'\" else echo shar: Extracting \"'rnd.c'\" \(11902 characters\) sed "s/^X//" >'rnd.c' <<'END_OF_FILE' X#ifndef lint X/* static char sccsid[] = "@(#)random.c 4.2 (Berkeley) 83/01/02"; */ X#endif X X#include <stdio.h> X X/* X * random.c: X * An improved random number generation package. In addition to the standard X * rand()/srand() like interface, this package also has a special state info X * interface. The initstate() routine is called with a seed, an array of X * bytes, and a count of how many bytes are being passed in; this array is then X * initialized to contain information for random number generation with that X * much state information. Good sizes for the amount of state information are X * 32, 64, 128, and 256 bytes. The state can be switched by calling the X * setstate() routine with the same array as was initiallized with initstate(). X * By default, the package runs with 128 bytes of state information and X * generates far better random numbers than a linear congruential generator. X * If the amount of state information is less than 32 bytes, a simple linear X * congruential R.N.G. is used. X * Internally, the state information is treated as an array of longs; the X * zeroeth element of the array is the type of R.N.G. being used (small X * integer); the remainder of the array is the state information for the X * R.N.G. Thus, 32 bytes of state information will give 7 longs worth of X * state information, which will allow a degree seven polynomial. (Note: the X * zeroeth word of state information also has some other information stored X * in it -- see setstate() for details). X * The random number generation technique is a linear feedback shift register X * approach, employing trinomials (since there are fewer terms to sum up that X * way). In this approach, the least significant bit of all the numbers in X * the state table will act as a linear feedback shift register, and will have X * period 2^deg - 1 (where deg is the degree of the polynomial being used, X * assuming that the polynomial is irreducible and primitive). The higher X * order bits will have longer periods, since their values are also influenced X * by pseudo-random carries out of the lower bits. The total period of the X * generator is approximately deg*(2**deg - 1); thus doubling the amount of X * state information has a vast influence on the period of the generator. X * Note: the deg*(2**deg - 1) is an approximation only good for large deg, X * when the period of the shift register is the dominant factor. With deg X * equal to seven, the period is actually much longer than the 7*(2**7 - 1) X * predicted by this formula. X */ X X X X/* X * For each of the currently supported random number generators, we have a X * break value on the amount of state information (you need at least this X * many bytes of state info to support this random number generator), a degree X * for the polynomial (actually a trinomial) that the R.N.G. is based on, and X * the separation between the two lower order coefficients of the trinomial. X */ X X#define TYPE_0 0 /* linear congruential */ X#define BREAK_0 8 X#define DEG_0 0 X#define SEP_0 0 X X#define TYPE_1 1 /* x**7 + x**3 + 1 */ X#define BREAK_1 32 X#define DEG_1 7 X#define SEP_1 3 X X#define TYPE_2 2 /* x**15 + x + 1 */ X#define BREAK_2 64 X#define DEG_2 15 X#define SEP_2 1 X X#define TYPE_3 3 /* x**31 + x**3 + 1 */ X#define BREAK_3 128 X#define DEG_3 31 X#define SEP_3 3 X X#define TYPE_4 4 /* x**63 + x + 1 */ X#define BREAK_4 256 X#define DEG_4 63 X#define SEP_4 1 X X X/* X * Array versions of the above information to make code run faster -- relies X * on fact that TYPE_i == i. X */ X X#define MAX_TYPES 5 /* max number of types above */ X Xstatic int degrees[ MAX_TYPES ] = { DEG_0, DEG_1, DEG_2, X DEG_3, DEG_4 }; X Xstatic int seps[ MAX_TYPES ] = { SEP_0, SEP_1, SEP_2, X SEP_3, SEP_4 }; X X X X/* X * Initially, everything is set up as if from : X * initstate( 1, &randtbl, 128 ); X * Note that this initialization takes advantage of the fact that srandom() X * advances the front and rear pointers 10*rand_deg times, and hence the X * rear pointer which starts at 0 will also end up at zero; thus the zeroeth X * element of the state information, which contains info about the current X * position of the rear pointer is just X * MAX_TYPES*(rptr - state) + TYPE_3 == TYPE_3. X */ X Xstatic long randtbl[ DEG_3 + 1 ] = { TYPE_3, X 0x9a319039, 0x32d9c024, 0x9b663182, 0x5da1f342, X 0xde3b81e0, 0xdf0a6fb5, 0xf103bc02, 0x48f340fb, X 0x7449e56b, 0xbeb1dbb0, 0xab5c5918, 0x946554fd, X 0x8c2e680f, 0xeb3d799f, 0xb11ee0b7, 0x2d436b86, X 0xda672e2a, 0x1588ca88, 0xe369735d, 0x904f35f7, X 0xd7158fd6, 0x6fa6f051, 0x616e6b96, 0xac94efdc, X 0x36413f93, 0xc622c298, 0xf5a42ab8, 0x8a88d77b, X 0xf5ad9d0e, 0x8999220b, 0x27fb47b9 }; X X/* X * fptr and rptr are two pointers into the state info, a front and a rear X * pointer. These two pointers are always rand_sep places aparts, as they cycle X * cyclically through the state information. (Yes, this does mean we could get X * away with just one pointer, but the code for random() is more efficient this X * way). The pointers are left positioned as they would be from the call X * initstate( 1, randtbl, 128 ) X * (The position of the rear pointer, rptr, is really 0 (as explained above X * in the initialization of randtbl) because the state table pointer is set X * to point to randtbl[1] (as explained below). X */ X Xstatic long *fptr = &randtbl[ SEP_3 + 1 ]; Xstatic long *rptr = &randtbl[ 1 ]; X X X X/* X * The following things are the pointer to the state information table, X * the type of the current generator, the degree of the current polynomial X * being used, and the separation between the two pointers. X * Note that for efficiency of random(), we remember the first location of X * the state information, not the zeroeth. Hence it is valid to access X * state[-1], which is used to store the type of the R.N.G. X * Also, we remember the last location, since this is more efficient than X * indexing every time to find the address of the last element to see if X * the front and rear pointers have wrapped. X */ X Xstatic long *state = &randtbl[ 1 ]; X Xstatic int rand_type = TYPE_3; Xstatic int rand_deg = DEG_3; Xstatic int rand_sep = SEP_3; X Xstatic long *end_ptr = &randtbl[ DEG_3 + 1 ]; X X X X/* X * srandom: X * Initialize the random number generator based on the given seed. If the X * type is the trivial no-state-information type, just remember the seed. X * Otherwise, initializes state[] based on the given "seed" via a linear X * congruential generator. Then, the pointers are set to known locations X * that are exactly rand_sep places apart. Lastly, it cycles the state X * information a given number of times to get rid of any initial dependencies X * introduced by the L.C.R.N.G. X * Note that the initialization of randtbl[] for default usage relies on X * values produced by this routine. X */ X Xsrandom( x ) X X unsigned x; X{ X register int i, j; X X if( rand_type == TYPE_0 ) { X state[ 0 ] = x; X } X else { X j = 1; X state[ 0 ] = x; X for( i = 1; i < rand_deg; i++ ) { X state[i] = 1103515245*state[i - 1] + 12345; X } X fptr = &state[ rand_sep ]; X rptr = &state[ 0 ]; X for( i = 0; i < 10*rand_deg; i++ ) random(); X } X} X X X X/* X * initstate: X * Initialize the state information in the given array of n bytes for X * future random number generation. Based on the number of bytes we X * are given, and the break values for the different R.N.G.'s, we choose X * the best (largest) one we can and set things up for it. srandom() is X * then called to initialize the state information. X * Note that on return from srandom(), we set state[-1] to be the type X * multiplexed with the current value of the rear pointer; this is so X * successive calls to initstate() won't lose this information and will X * be able to restart with setstate(). X * Note: the first thing we do is save the current state, if any, just like X * setstate() so that it doesn't matter when initstate is called. X * Returns a pointer to the old state. X */ X Xchar * Xinitstate( seed, arg_state, n ) X X unsigned seed; /* seed for R. N. G. */ X char *arg_state; /* pointer to state array */ X int n; /* # bytes of state info */ X{ X register char *ostate = (char *)( &state[ -1 ] ); X X if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; X else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; X if( n < BREAK_1 ) { X if( n < BREAK_0 ) { X fprintf( stderr, "initstate: not enough state (%d bytes) with which to do jack; ignored.\n" ); X return; X } X rand_type = TYPE_0; X rand_deg = DEG_0; X rand_sep = SEP_0; X } X else { X if( n < BREAK_2 ) { X rand_type = TYPE_1; X rand_deg = DEG_1; X rand_sep = SEP_1; X } X else { X if( n < BREAK_3 ) { X rand_type = TYPE_2; X rand_deg = DEG_2; X rand_sep = SEP_2; X } X else { X if( n < BREAK_4 ) { X rand_type = TYPE_3; X rand_deg = DEG_3; X rand_sep = SEP_3; X } X else { X rand_type = TYPE_4; X rand_deg = DEG_4; X rand_sep = SEP_4; X } X } X } X } X state = &( ( (long *)arg_state )[1] ); /* first location */ X end_ptr = &state[ rand_deg ]; /* must set end_ptr before srandom */ X srandom( seed ); X if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; X else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; X return( ostate ); X} X X X X/* X * setstate: X * Restore the state from the given state array. X * Note: it is important that we also remember the locations of the pointers X * in the current state information, and restore the locations of the pointers X * from the old state information. This is done by multiplexing the pointer X * location into the zeroeth word of the state information. X * Note that due to the order in which things are done, it is OK to call X * setstate() with the same state as the current state. X * Returns a pointer to the old state information. X */ X Xchar * Xsetstate( arg_state ) X X char *arg_state; X{ X register long *new_state = (long *)arg_state; X register int type = new_state[0]%MAX_TYPES; X register int rear = new_state[0]/MAX_TYPES; X char *ostate = (char *)( &state[ -1 ] ); X X if( rand_type == TYPE_0 ) state[ -1 ] = rand_type; X else state[ -1 ] = MAX_TYPES*(rptr - state) + rand_type; X switch( type ) { X case TYPE_0: X case TYPE_1: X case TYPE_2: X case TYPE_3: X case TYPE_4: X rand_type = type; X rand_deg = degrees[ type ]; X rand_sep = seps[ type ]; X break; X X default: X fprintf( stderr, "setstate: state info has been munged; not changed.\n" ); X } X state = &new_state[ 1 ]; X if( rand_type != TYPE_0 ) { X rptr = &state[ rear ]; X fptr = &state[ (rear + rand_sep)%rand_deg ]; X } X end_ptr = &state[ rand_deg ]; /* set end_ptr too */ X return( ostate ); X} X X X X/* X * random: X * If we are using the trivial TYPE_0 R.N.G., just do the old linear X * congruential bit. Otherwise, we do our fancy trinomial stuff, which is the X * same in all ther other cases due to all the global variables that have been X * set up. The basic operation is to add the number at the rear pointer into X * the one at the front pointer. Then both pointers are advanced to the next X * location cyclically in the table. The value returned is the sum generated, X * reduced to 31 bits by throwing away the "least random" low bit. X * Note: the code takes advantage of the fact that both the front and X * rear pointers can't wrap on the same call by not testing the rear X * pointer if the front one has wrapped. X * Returns a 31-bit random number. X */ X Xlong Xrandom() X{ X long i; X X if( rand_type == TYPE_0 ) { X i = state[0] = ( state[0]*1103515245 + 12345 )&0x7fffffff; X } X else { X *fptr += *rptr; X i = (*fptr >> 1)&0x7fffffff; /* chucking least random bit */ X if( ++fptr >= end_ptr ) { X fptr = state; X ++rptr; X } X else { X if( ++rptr >= end_ptr ) rptr = state; X } X } X return( i ); X} END_OF_FILE if test 11902 -ne `wc -c <'rnd.c'`; then echo shar: \"'rnd.c'\" unpacked with wrong size! fi # end of 'rnd.c' fi if test -f 'regexp.c' -a "${1}" != "-c" ; then echo shar: Will not clobber existing file \"'regexp.c'\" else echo shar: Extracting \"'regexp.c'\" \(27786 characters\) sed "s/^X//" >'regexp.c' <<'END_OF_FILE' X/* X * regcomp and regexec -- regsub and regerror are elsewhere X * X * Copyright (c) 1986 by University of Toronto. X * Written by Henry Spencer. Not derived from licensed software. X * X * Permission is granted to anyone to use this software for any X * purpose on any computer system, and to redistribute it freely, X * subject to the following restrictions: X * X * 1. The author is not responsible for the consequences of use of X * this software, no matter how awful, even if they arise X * from defects in it. X * X * 2. The origin of this software must not be misrepresented, either X * by explicit claim or by omission. X * X * 3. Altered versions must be plainly marked as such, and must not X * be misrepresented as being the original software. X * X * Beware that some of this code is subtly aware of the way operator X * precedence is structured in regular expressions. Serious changes in X * regular-expression syntax might require a total rethink. X */ X#ifdef OSK X#define sp sp_ /* only for some compilers */ X#define STRCSPN X#define strchr index X#define STATIC extern X#endif X X#include <stdio.h> X#include "regexp.h" X#include "regmagic.h" X X/* X * The "internal use only" fields in regexp.h are present to pass info from X * compile to execute that permits the execute phase to run lots faster on X * simple cases. They are: X * X * regstart char that must begin a match; '\0' if none obvious X * reganch is the match anchored (at beginning-of-line only)? X * regmust string (pointer into program) that match must include, or NULL X * regmlen length of regmust string X * X * Regstart and reganch permit very fast decisions on suitable starting points X * for a match, cutting down the work a lot. Regmust permits fast rejection X * of lines that cannot possibly match. The regmust tests are costly enough X * that regcomp() supplies a regmust only if the r.e. contains something X * potentially expensive (at present, the only such thing detected is * or + X * at the start of the r.e., which can involve a lot of backup). Regmlen is X * supplied because the test in regexec() needs it and regcomp() is computing X * it anyway. X */ X X/* X * Structure for regexp "program". This is essentially a linear encoding X * of a nondeterministic finite-state machine (aka syntax charts or X * "railroad normal form" in parsing technology). Each node is an opcode X * plus a "next" pointer, possibly plus an operand. "Next" pointers of X * all nodes except BRANCH implement concatenation; a "next" pointer with X * a BRANCH on both ends of it is connecting two alternatives. (Here we X * have one of the subtle syntax dependencies: an individual BRANCH (as X * opposed to a collection of them) is never concatenated with anything X * because of operator precedence.) The operand of some types of node is X * a literal string; for others, it is a node leading into a sub-FSM. In X * particular, the operand of a BRANCH node is the first node of the branch. X * (NB this is *not* a tree structure: the tail of the branch connects X * to the thing following the set of BRANCHes.) The opcodes are: X */ X X#ifdef OSK X#ifdef EOL X#undef EOL X#endif X#endif X X/* definition number opnd? meaning */ X#define END 0 /* no End of program. */ X#define BOL 1 /* no Match "" at beginning of line. */ X#define EOL 2 /* no Match "" at end of line. */ X#define ANY 3 /* no Match any one character. */ X#define ANYOF 4 /* str Match any character in this string. */ X#define ANYBUT 5 /* str Match any character not in this string. */ X#define BRANCH 6 /* node Match this alternative, or the next... */ X#define BACK 7 /* no Match "", "next" ptr points backward. */ X#define EXACTLY 8 /* str Match this string. */ X#define NOTHING 9 /* no Match empty string. */ X#define STAR 10 /* node Match this (simple) thing 0 or more times. */ X#define PLUS 11 /* node Match this (simple) thing 1 or more times. */ X#define OPEN 20 /* no Mark this point in input as start of #n. */ X /* OPEN+1 is number 1, etc. */ X#define CLOSE 30 /* no Analogous to OPEN. */ X X/* X * Opcode notes: X * X * BRANCH The set of branches constituting a single choice are hooked X * together with their "next" pointers, since precedence prevents X * anything being concatenated to any individual branch. The X * "next" pointer of the last BRANCH in a choice points to the X * thing following the whole choice. This is also where the X * final "next" pointer of each individual branch points; each X * branch starts with the operand node of a BRANCH node. X * X * BACK Normal "next" pointers all implicitly point forward; BACK X * exists to make loop structures possible. X * X * STAR,PLUS '?', and complex '*' and '+', are implemented as circular X * BRANCH structures using BACK. Simple cases (one character X * per match) are implemented with STAR and PLUS for speed X * and to minimize recursive plunges. X * X * OPEN,CLOSE ...are numbered at compile time. X */ X X/* X * A node is one char of opcode followed by two chars of "next" pointer. X * "Next" pointers are stored as two 8-bit pieces, high order first. The X * value is a positive offset from the opcode of the node containing it. X * An operand, if any, simply follows the node. (Note that much of the X * code generation knows about this implicit relationship.) X * X * Using two bytes for the "next" pointer is vast overkill for most things, X * but allows patterns to get big without disasters. X */ X#define OP(p) (*(p)) X#define NEXT(p) (((*((p)+1)&0377)<<8) + *((p)+2)&0377) X#define OPERAND(p) ((p) + 3) X X/* X * See regmagic.h for one further detail of program structure. X */ X X X/* X * Utility definitions. X */ X#ifndef CHARBITS X#define UCHARAT(p) ((int)*(unsigned char *)(p)) X#else X#define UCHARAT(p) ((int)*(p)&CHARBITS) X#endif X X#define FAIL(m) { regerror(m); return(NULL); } X#define ISMULT(c) ((c) == '*' || (c) == '+' || (c) == '?') X#define META "^$.[()|?+*\\" X X/* X * Flags to be passed up and down. X */ X#define HASWIDTH 01 /* Known never to match null string. */ X#define SIMPLE 02 /* Simple enough to be STAR/PLUS operand. */ X#define SPSTART 04 /* Starts with * or +. */ X#define WORST 0 /* Worst case. */ X X/* X * Global work variables for regcomp(). X */ Xstatic char *regparse; /* Input-scan pointer. */ Xstatic int regnpar; /* () count. */ Xstatic char regdummy; Xstatic char *regcode; /* Code-emit pointer; ®dummy = don't. */ Xstatic long regsize; /* Code size. */ X X/* X * Forward declarations for regcomp()'s friends. X */ X#ifndef STATIC X#define STATIC static X#endif XSTATIC char *reg(); XSTATIC char *regbranch(); XSTATIC char *regpiece(); XSTATIC char *regatom(); XSTATIC char *regnode(); XSTATIC char *regnext(); XSTATIC void regc(); XSTATIC void reginsert(); XSTATIC void regtail(); XSTATIC void regoptail(); X#ifdef STRCSPN XSTATIC int strcspn(); X#endif X X/* X - regcomp - compile a regular expression into internal code X * X * We can't allocate space until we know how big the compiled form will be, X * but we can't compile it (and thus know how big it is) until we've got a X * place to put the code. So we cheat: we compile it twice, once with code X * generation turned off and size counting turned on, and once "for real". X * This also means that we don't allocate space until we are sure that the X * thing really will compile successfully, and we never have to move the X * code and thus invalidate pointers into it. (Note that it has to be in X * one piece because free() must be able to free it all.) X * X * Beware that the optimization-preparation code in here knows about some X * of the structure of the compiled regexp. X */ Xregexp * Xregcomp(exp) Xchar *exp; X{ X register regexp *r; X register char *scan; X register char *longest; X register int len; X int flags; X extern char *malloc(); X X if (exp == NULL) X FAIL("NULL argument"); X X /* First pass: determine size, legality. */ X regparse = exp; X regnpar = 1; X regsize = 0L; X regcode = ®dummy; X regc(MAGIC); X if (reg(0, &flags) == NULL) X return(NULL); X X /* Small enough for pointer-storage convention? */ X if (regsize >= 32767L) /* Probably could be 65535L. */ X FAIL("regexp too big"); X X /* Allocate space. */ X r = (regexp *)malloc(sizeof(regexp) + (unsigned)regsize); X if (r == NULL) X FAIL("out of space"); X X /* Second pass: emit code. */ X regparse = exp; X regnpar = 1; X regcode = r->program; X regc(MAGIC); X if (reg(0, &flags) == NULL) X return(NULL); X X /* Dig out information for optimizations. */ X r->regstart = '\0'; /* Worst-case defaults. */ X r->reganch = 0; X r->regmust = NULL; X r->regmlen = 0; X scan = r->program+1; /* First BRANCH. */ X if (OP(regnext(scan)) == END) { /* Only one top-level choice. */ X scan = OPERAND(scan); X X /* Starting-point info. */ X if (OP(scan) == EXACTLY) X r->regstart = *OPERAND(scan); X else if (OP(scan) == BOL) X r->reganch++; X X /* X * If there's something expensive in the r.e., find the X * longest literal string that must appear and make it the X * regmust. Resolve ties in favor of later strings, since X * the regstart check works with the beginning of the r.e. X * and avoiding duplication strengthens checking. Not a X * strong reason, but sufficient in the absence of others. X */ X if (flags&SPSTART) { X longest = NULL; X len = 0; X for (; scan != NULL; scan = regnext(scan)) X if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) { X longest = OPERAND(scan); X len = strlen(OPERAND(scan)); X } X r->regmust = longest; X r->regmlen = len; X } X } X X return(r); X} X X/* X - reg - regular expression, i.e. main body or parenthesized thing X * X * Caller must absorb opening parenthesis. X * X * Combining parenthesis handling with the base level of regular expression X * is a trifle forced, but the need to tie the tails of the branches to what X * follows makes it hard to avoid. X */ Xstatic char * Xreg(paren, flagp) Xint paren; /* Parenthesized? */ Xint *flagp; X{ X register char *ret; X register char *br; X register char *ender; X register int parno; X int flags; X X *flagp = HASWIDTH; /* Tentatively. */ X X /* Make an OPEN node, if parenthesized. */ X if (paren) { X if (regnpar >= NSUBEXP) X FAIL("too many ()"); X parno = regnpar; X regnpar++; X ret = regnode(OPEN+parno); X } else X ret = NULL; X X /* Pick up the branches, linking them together. */ X br = regbranch(&flags); X if (br == NULL) X return(NULL); X if (ret != NULL) X regtail(ret, br); /* OPEN -> first. */ X else X ret = br; X if (!(flags&HASWIDTH)) X *flagp &= ~HASWIDTH; X *flagp |= flags&SPSTART; X while (*regparse == '|') { X regparse++; X br = regbranch(&flags); X if (br == NULL) X return(NULL); X regtail(ret, br); /* BRANCH -> BRANCH. */ X if (!(flags&HASWIDTH)) X *flagp &= ~HASWIDTH; X *flagp |= flags&SPSTART; X } X X /* Make a closing node, and hook it on the end. */ X ender = regnode((paren) ? CLOSE+parno : END); X regtail(ret, ender); X X /* Hook the tails of the branches to the closing node. */ X for (br = ret; br != NULL; br = regnext(br)) X regoptail(br, ender); X X /* Check for proper termination. */ X if (paren && *regparse++ != ')') { X FAIL("unmatched ()"); X } else if (!paren && *regparse != '\0') { X if (*regparse == ')') { X FAIL("unmatched ()"); X } else X FAIL("junk on end"); /* "Can't happen". */ X /* NOTREACHED */ X } X X return(ret); X} X X/* X - regbranch - one alternative of an | operator X * X * Implements the concatenation operator. X */ Xstatic char * Xregbranch(flagp) Xint *flagp; X{ X register char *ret; X register char *chain; X register char *latest; X int flags; X X *flagp = WORST; /* Tentatively. */ X X ret = regnode(BRANCH); X chain = NULL; X while (*regparse != '\0' && *regparse != '|' && *regparse != ')') { X latest = regpiece(&flags); X if (latest == NULL) X return(NULL); X *flagp |= flags&HASWIDTH; X if (chain == NULL) /* First piece. */ X *flagp |= flags&SPSTART; X else X regtail(chain, latest); X chain = latest; X } X if (chain == NULL) /* Loop ran zero times. */ X (void) regnode(NOTHING); X X return(ret); X} X X/* X - regpiece - something followed by possible [*+?] X * X * Note that the branching code sequences used for ? and the general cases X * of * and + are somewhat optimized: they use the same NOTHING node as X * both the endmarker for their branch list and the body of the last branch. X * It might seem that this node could be dispensed with entirely, but the X * endmarker role is not redundant. X */ Xstatic char * Xregpiece(flagp) Xint *flagp; X{ X register char *ret; X register char op; X register char *next; X int flags; X X ret = regatom(&flags); X if (ret == NULL) X return(NULL); X X op = *regparse; X if (!ISMULT(op)) { X *flagp = flags; X return(ret); X } X X if (!(flags&HASWIDTH) && op != '?') X FAIL("*+ operand could be empty"); X *flagp = (op != '+') ? (WORST|SPSTART) : (WORST|HASWIDTH); X X if (op == '*' && (flags&SIMPLE)) X reginsert(STAR, ret); X else if (op == '*') { X /* Emit x* as (x&|), where & means "self". */ X reginsert(BRANCH, ret); /* Either x */ X regoptail(ret, regnode(BACK)); /* and loop */ X regoptail(ret, ret); /* back */ X regtail(ret, regnode(BRANCH)); /* or */ X regtail(ret, regnode(NOTHING)); /* null. */ X } else if (op == '+' && (flags&SIMPLE)) X reginsert(PLUS, ret); X else if (op == '+') { X /* Emit x+ as x(&|), where & means "self". */ X next = regnode(BRANCH); /* Either */ X regtail(ret, next); X regtail(regnode(BACK), ret); /* loop back */ X regtail(next, regnode(BRANCH)); /* or */ X regtail(ret, regnode(NOTHING)); /* null. */ X } else if (op == '?') { X /* Emit x? as (x|) */ X reginsert(BRANCH, ret); /* Either x */ X regtail(ret, regnode(BRANCH)); /* or */ X next = regnode(NOTHING); /* null. */ X regtail(ret, next); X regoptail(ret, next); X } X regparse++; X if (ISMULT(*regparse)) X FAIL("nested *?+"); X X return(ret); X} X X/* X - regatom - the lowest level X * X * Optimization: gobbles an entire sequence of ordinary characters so that X * it can turn them into a single node, which is smaller to store and X * faster to run. Backslashed characters are exceptions, each becoming a X * separate node; the code is simpler that way and it's not worth fixing. X */ Xstatic char * Xregatom(flagp) Xint *flagp; X{ X register char *ret; X int flags; X X *flagp = WORST; /* Tentatively. */ X X switch (*regparse++) { X case '^': X ret = regnode(BOL); X break; X case '$': X ret = regnode(EOL); X break; X case '.': X ret = regnode(ANY); X *flagp |= HASWIDTH|SIMPLE; X break; X case '[': { X register int class; X register int classend; X X if (*regparse == '^') { /* Complement of range. */ X ret = regnode(ANYBUT); X regparse++; X } else X ret = regnode(ANYOF); X if (*regparse == ']' || *regparse == '-') X regc(*regparse++); X while (*regparse != '\0' && *regparse != ']') { X if (*regparse == '-') { X regparse++; X if (*regparse == ']' || *regparse == '\0') X regc('-'); X else { X class = UCHARAT(regparse-2)+1; X classend = UCHARAT(regparse); X if (class > classend+1) X FAIL("invalid [] range"); X for (; class <= classend; class++) X regc(class); X regparse++; X } X } else X regc(*regparse++); X } X regc('\0'); X if (*regparse != ']') X FAIL("unmatched []"); X regparse++; X *flagp |= HASWIDTH|SIMPLE; X } X break; X case '(': X ret = reg(1, &flags); X if (ret == NULL) X return(NULL); X *flagp |= flags&(HASWIDTH|SPSTART); X break; X case '\0': X case '|': X case ')': X FAIL("internal urp"); /* Supposed to be caught earlier. */ X break; X case '?': X case '+': X case '*': X FAIL("?+* follows nothing"); X break; X case '\\': X if (*regparse == '\0') X FAIL("trailing \\"); X ret = regnode(EXACTLY); X regc(*regparse++); X regc('\0'); X *flagp |= HASWIDTH|SIMPLE; X break; X default: { X register int len; X register char ender; X X regparse--; X len = strcspn(regparse, META); X if (len <= 0) X FAIL("internal disaster"); X ender = *(regparse+len); X if (len > 1 && ISMULT(ender)) X len--; /* Back off clear of ?+* operand. */ X *flagp |= HASWIDTH; X if (len == 1) X *flagp |= SIMPLE; X ret = regnode(EXACTLY); X while (len > 0) { X regc(*regparse++); X len--; X } X regc('\0'); X } X break; X } X X return(ret); X} X X/* X - regnode - emit a node X */ Xstatic char * /* Location. */ Xregnode(op) Xchar op; X{ X register char *ret; X register char *ptr; X X ret = regcode; X if (ret == ®dummy) { X regsize += 3; X return(ret); X } X X ptr = ret; X *ptr++ = op; X *ptr++ = '\0'; /* Null "next" pointer. */ X *ptr++ = '\0'; X regcode = ptr; X X return(ret); X} X X/* X - regc - emit (if appropriate) a byte of code X */ Xstatic void Xregc(b) Xchar b; X{ X if (regcode != ®dummy) X *regcode++ = b; X else X regsize++; X} X X/* X - reginsert - insert an operator in front of already-emitted operand X * X * Means relocating the operand. X */ Xstatic void Xreginsert(op, opnd) Xchar op; Xchar *opnd; X{ X register char *src; X register char *dst; X register char *place; X X if (regcode == ®dummy) { X regsize += 3; X return; X } X X src = regcode; X regcode += 3; X dst = regcode; X while (src > opnd) X *--dst = *--src; X X place = opnd; /* Op node, where operand used to be. */ X *place++ = op; X *place++ = '\0'; X *place++ = '\0'; X} X X/* X - regtail - set the next-pointer at the end of a node chain X */ Xstatic void Xregtail(p, val) Xchar *p; Xchar *val; X{ X register char *scan; X register char *temp; X register int offset; X X if (p == ®dummy) X return; X X /* Find last node. */ X scan = p; X for (;;) { X temp = regnext(scan); X if (temp == NULL) X break; X scan = temp; X } X X if (OP(scan) == BACK) X offset = scan - val; X else X offset = val - scan; X *(scan+1) = (offset>>8)&0377; X *(scan+2) = offset&0377; X} X X/* X - regoptail - regtail on operand of first argument; nop if operandless X */ Xstatic void Xregoptail(p, val) Xchar *p; Xchar *val; X{ X /* "Operandless" and "op != BRANCH" are synonymous in practice. */ X if (p == NULL || p == ®dummy || OP(p) != BRANCH) X return; X regtail(OPERAND(p), val); X} X X/* X * regexec and friends X */ X X/* X * Global work variables for regexec(). X */ Xstatic char *reginput; /* String-input pointer. */ Xstatic char *regbol; /* Beginning of input, for ^ check. */ Xstatic char **regstartp; /* Pointer to startp array. */ Xstatic char **regendp; /* Ditto for endp. */ X X/* X * Forwards. X */ XSTATIC int regtry(); XSTATIC int regmatch(); XSTATIC int regrepeat(); X X#ifdef DEBUG Xint regnarrate = 0; Xvoid regdump(); XSTATIC char *regprop(); X#endif X X/* X - regexec - match a regexp against a string X */ Xint Xregexec(prog, string) Xregister regexp *prog; Xregister char *string; X{ X register char *s; X extern char *strchr(); X X /* Be paranoid... */ X if (prog == NULL || string == NULL) { X regerror("NULL parameter"); X return(0); X } X X /* Check validity of program. */ X if (UCHARAT(prog->program) != MAGIC) { X regerror("corrupted program"); X return(0); X } X X /* If there is a "must appear" string, look for it. */ X if (prog->regmust != NULL) { X s = string; X while ((s = strchr(s, prog->regmust[0])) != NULL) { X if (strncmp(s, prog->regmust, prog->regmlen) == 0) X break; /* Found it. */ X s++; X } X if (s == NULL) /* Not present. */ X return(0); X } X X /* Mark beginning of line for ^ . */ X regbol = string; X X /* Simplest case: anchored match need be tried only once. */ X if (prog->reganch) X return(regtry(prog, string)); X X /* Messy cases: unanchored match. */ X s = string; X if (prog->regstart != '\0') X /* We know what char it must start with. */ X while ((s = strchr(s, prog->regstart)) != NULL) { X if (regtry(prog, s)) X return(1); X s++; X } X else X /* We don't -- general case. */ X do { X if (regtry(prog, s)) X return(1); X } while (*s++ != '\0'); X X /* Failure. */ X return(0); X} X X/* X - regtry - try match at specific point X */ Xstatic int /* 0 failure, 1 success */ Xregtry(prog, string) Xregexp *prog; Xchar *string; X{ X register int i; X register char **sp; X register char **ep; X X reginput = string; X regstartp = prog->startp; X regendp = prog->endp; X X sp = prog->startp; X ep = prog->endp; X for (i = NSUBEXP; i > 0; i--) { X *sp++ = NULL; X *ep++ = NULL; X } X if (regmatch(prog->program + 1)) { X prog->startp[0] = string; X prog->endp[0] = reginput; X return(1); X } else X return(0); X} X X/* X - regmatch - main matching routine X * X * Conceptually the strategy is simple: check to see whether the current X * node matches, call self recursively to see whether the rest matches, X * and then act accordingly. In practice we make some effort to avoid X * recursion, in particular by going through "ordinary" nodes (that don't X * need to know whether the rest of the match failed) by a loop instead of X * by recursion. X */ Xstatic int /* 0 failure, 1 success */ Xregmatch(prog) Xchar *prog; X{ X register char *scan; /* Current node. */ X char *next; /* Next node. */ X extern char *strchr(); X X scan = prog; X#ifdef DEBUG X if (scan != NULL && regnarrate) X fprintf(stderr, "%s(\n", regprop(scan)); X#endif X while (scan != NULL) { X#ifdef DEBUG X if (regnarrate) X fprintf(stderr, "%s...\n", regprop(scan)); X#endif X next = regnext(scan); X X switch (OP(scan)) { X case BOL: X if (reginput != regbol) X return(0); X break; X case EOL: X if (*reginput != '\0') X return(0); X break; X case ANY: X if (*reginput == '\0') X return(0); X reginput++; X break; X case EXACTLY: { X register int len; X register char *opnd; X X opnd = OPERAND(scan); X /* Inline the first character, for speed. */ X if (*opnd != *reginput) X return(0); X len = strlen(opnd); X if (len > 1 && strncmp(opnd, reginput, len) != 0) X return(0); X reginput += len; X } X break; X case ANYOF: X if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) == NULL) X return(0); X reginput++; X break; X case ANYBUT: X if (*reginput == '\0' || strchr(OPERAND(scan), *reginput) != NULL) X return(0); X reginput++; X break; X case NOTHING: X break; X case BACK: X break; X case OPEN+1: X case OPEN+2: X case OPEN+3: X case OPEN+4: X case OPEN+5: X case OPEN+6: X case OPEN+7: X case OPEN+8: X case OPEN+9: { X register int no; X register char *save; X X no = OP(scan) - OPEN; X save = reginput; X X if (regmatch(next)) { X /* X * Don't set startp if some later X * invocation of the same parentheses X * already has. X */ X if (regstartp[no] == NULL) X regstartp[no] = save; X return(1); X } else X return(0); X } X break; X case CLOSE+1: X case CLOSE+2: X case CLOSE+3: X case CLOSE+4: X case CLOSE+5: X case CLOSE+6: X case CLOSE+7: X case CLOSE+8: X case CLOSE+9: { X register int no; X register char *save; X X no = OP(scan) - CLOSE; X save = reginput; X X if (regmatch(next)) { X /* X * Don't set endp if some later X * invocation of the same parentheses X * already has. X */ X if (regendp[no] == NULL) X regendp[no] = save; X return(1); X } else X return(0); X } X break; X case BRANCH: { X register char *save; X X if (OP(next) != BRANCH) /* No choice. */ X next = OPERAND(scan); /* Avoid recursion. */ X else { X do { X save = reginput; X if (regmatch(OPERAND(scan))) X return(1); X reginput = save; X scan = regnext(scan); X } while (scan != NULL && OP(scan) == BRANCH); X return(0); X /* NOTREACHED */ X } X } X break; X case STAR: X case PLUS: { X register char nextch; X register int no; X register char *save; X register int min; X X /* X * Lookahead to avoid useless match attempts X * when we know what character comes next. X */ X nextch = '\0'; X if (OP(next) == EXACTLY) X nextch = *OPERAND(next); X min = (OP(scan) == STAR) ? 0 : 1; X save = reginput; X no = regrepeat(OPERAND(scan)); X while (no >= min) { X /* If it could work, try it. */ X if (nextch == '\0' || *reginput == nextch) X if (regmatch(next)) X return(1); X /* Couldn't or didn't -- back up. */ X no--; X reginput = save + no; X } X return(0); X } X break; X case END: X return(1); /* Success! */ X break; X default: X regerror("memory corruption"); X return(0); X break; X } X X scan = next; X } X X /* X * We get here only if there's trouble -- normally "case END" is X * the terminating point. X */ X regerror("corrupted pointers"); X return(0); X} X X/* X - regrepeat - repeatedly match something simple, report how many X */ Xstatic int Xregrepeat(p) Xchar *p; X{ X register int count = 0; X register char *scan; X register char *opnd; X X scan = reginput; X opnd = OPERAND(p); X switch (OP(p)) { X case ANY: X count = strlen(scan); X scan += count; X break; X case EXACTLY: X while (*opnd == *scan) { X count++; X scan++; X } X break; X case ANYOF: X while (*scan != '\0' && strchr(opnd, *scan) != NULL) { X count++; X scan++; X } X break; X case ANYBUT: X while (*scan != '\0' && strchr(opnd, *scan) == NULL) { X count++; X scan++; X } X break; X default: /* Oh dear. Called inappropriately. */ X regerror("internal foulup"); X count = 0; /* Best compromise. */ X break; X } X reginput = scan; X X return(count); X} X X/* X - regnext - dig the "next" pointer out of a node X */ Xstatic char * Xregnext(p) Xregister char *p; X{ X register int offset; X X if (p == ®dummy) X return(NULL); X X offset = NEXT(p); X if (offset == 0) X return(NULL); X X if (OP(p) == BACK) X return(p-offset); X else X return(p+offset); X} X X#ifdef DEBUG X XSTATIC char *regprop(); X X/* X - regdump - dump a regexp onto stdout in vaguely comprehensible form X */ Xvoid Xregdump(r) Xregexp *r; X{ X register char *s; X register char op = EXACTLY; /* Arbitrary non-END op. */ X register char *next; X extern char *strchr(); X X X s = r->program + 1; X while (op != END) { /* While that wasn't END last time... */ X op = OP(s); X printf("%2d%s", s-r->program, regprop(s)); /* Where, what. */ X next = regnext(s); X if (next == NULL) /* Next ptr. */ X printf("(0)"); X else X printf("(%d)", (s-r->program)+(next-s)); X s += 3; X if (op == ANYOF || op == ANYBUT || op == EXACTLY) { X /* Literal string, where present. */ X while (*s != '\0') { X putchar(*s); X s++; X } X s++; X } X putchar('\n'); X } X X /* Header fields of interest. */ X if (r->regstart != '\0') X printf("start `%c' ", r->regstart); X if (r->reganch) X printf("anchored "); X if (r->regmust != NULL) X printf("must have \"%s\"", r->regmust); X printf("\n"); X} X X/* X - regprop - printable representation of opcode X */ Xstatic char * Xregprop(op) Xchar *op; X{ X register char *p; X static char buf[50]; X X (void) strcpy(buf, ":"); X X switch (OP(op)) { X case BOL: X p = "BOL"; X break; X case EOL: X p = "EOL"; X break; X case ANY: X p = "ANY"; X break; X case ANYOF: X p = "ANYOF"; X break; X case ANYBUT: X p = "ANYBUT"; X break; X case BRANCH: X p = "BRANCH"; X break; X case EXACTLY: X p = "EXACTLY"; X break; X case NOTHING: X p = "NOTHING"; X break; X case BACK: X p = "BACK"; X break; X case END: X p = "END"; X break; X case OPEN+1: X case OPEN+2: X case OPEN+3: X case OPEN+4: X case OPEN+5: X case OPEN+6: X case OPEN+7: X case OPEN+8: X case OPEN+9: X sprintf(buf+strlen(buf), "OPEN%d", OP(op)-OPEN); X p = NULL; X break; X case CLOSE+1: X case CLOSE+2: X case CLOSE+3: X case CLOSE+4: X case CLOSE+5: X case CLOSE+6: X case CLOSE+7: X case CLOSE+8: X case CLOSE+9: X sprintf(buf+strlen(buf), "CLOSE%d", OP(op)-CLOSE); X p = NULL; X break; X case STAR: X p = "STAR"; X break; X case PLUS: X p = "PLUS"; X break; X default: X regerror("corrupted opcode"); X break; X } X if (p != NULL) X (void) strcat(buf, p); X return(buf); X} X#endif X X/* X * The following is provided for those people who do not have strcspn() in X * their C libraries. They should get off their butts and do something X * about it; at least one public-domain implementation of those (highly X * useful) string routines has been published on Usenet. X */ X#ifdef STRCSPN X/* X * strcspn - find length of initial segment of s1 consisting entirely X * of characters not from s2 X */ X Xstatic int Xstrcspn(s1, s2) Xchar *s1; Xchar *s2; X{ X register char *scan1; X register char *scan2; X register int count; X X count = 0; X for (scan1 = s1; *scan1 != '\0'; scan1++) { X for (scan2 = s2; *scan2 != '\0';) /* ++ moved down. */ X if (*scan1 == *scan2++) X return(count); X count++; X } X return(count); X} X#endif END_OF_FILE if test 27786 -ne `wc -c <'regexp.c'`; then echo shar: \"'regexp.c'\" unpacked with wrong size! fi # end of 'regexp.c' fi echo shar: End of archive 5 \(of 5\). cp /dev/null ark5isdone MISSING="" for I in 1 2 3 4 5 ; do if test ! -f ark${I}isdone ; then MISSING="${MISSING} ${I}" fi done if test "${MISSING}" = "" ; then echo You have unpacked all 5 archives. rm -f ark[1-9]isdone else echo You still need to unpack the following archives: echo " " ${MISSING} fi ## End of shell archive. exit 0 -- | Wolfgang Ocker | ocker@lan.informatik.tu-muenchen.dbp.de | | Lochhauserstr. 35a | pyramid!tmpmbx!recco!weo (home) | | D-8039 Puchheim | Technische Universitaet Muenchen | | Voice: +49 89 80 77 02 | Huh, What? Where am I? |