da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/***********************************************************************
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* This software is part of the ast package *
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner* Copyright (c) 1985-2010 AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* and is licensed under the *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Common Public License, Version 1.0 *
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin* by AT&T Intellectual Property *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* A copy of the License is available at *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* http://www.opensource.org/licenses/cpl1.0.txt *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* (with md5 checksum 059e8cd6165cb4c31e351f2b69388fd9) *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Information and Software Systems Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* AT&T Research *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Florham Park NJ *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Glenn Fowler <gsf@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* David Korn <dgk@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* Phong Vo <kpv@research.att.com> *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin* *
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin***********************************************************************/
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#pragma prototyped
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * regcomp() regex_t cache
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner * at&t research
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <ast.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin#include <regex.h>
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin#define CACHE 8 /* default # cached re's */
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner#define ROUND 64 /* pattern buffer size round */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulknertypedef unsigned long Key_t;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chintypedef struct Cache_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner char* pattern;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin regex_t re;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unsigned long serial;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin regflags_t reflags;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner int keep;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner int size;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin} Cache_t;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chintypedef struct State_s
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin unsigned int size;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unsigned long serial;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin char* locale;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin Cache_t** cache;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin} State_t;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chinstatic State_t matchstate;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * flush the cache
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinstatic void
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinflushcache(void)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register int i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin for (i = matchstate.size; i--;)
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner if (matchstate.cache[i] && matchstate.cache[i]->keep)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner matchstate.cache[i]->keep = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin regfree(&matchstate.cache[i]->re);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin/*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * return regcomp() compiled re for pattern and reflags
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinregex_t*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chinregcache(const char* pattern, regflags_t reflags, int* status)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin{
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register Cache_t* cp;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin register int i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin char* s;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int empty;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int unused;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin int old;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner Key_t key;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /*
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin * 0 pattern flushes the cache and reflags>0 extends cache
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!pattern)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin flushcache();
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin i = 0;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin if (reflags > matchstate.size)
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin {
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin if (matchstate.cache = newof(matchstate.cache, Cache_t*, reflags, 0))
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin matchstate.size = reflags;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin else
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin {
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin matchstate.size = 0;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin i = 1;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin }
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (status)
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin *status = i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin if (!matchstate.cache)
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin {
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin if (!(matchstate.cache = newof(0, Cache_t*, CACHE, 0)))
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin return 0;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin matchstate.size = CACHE;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * flush the cache if the locale changed
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * the ast setlocale() intercept maintains
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * persistent setlocale() return values
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if ((s = setlocale(LC_CTYPE, NiL)) != matchstate.locale)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin matchstate.locale = s;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin flushcache();
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin /*
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin * check if the pattern is in the cache
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin */
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner for (i = 0; i < sizeof(key) && pattern[i]; i++)
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner ((char*)&key)[i] = pattern[i];
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner for (; i < sizeof(key); i++)
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner ((char*)&key)[i] = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin empty = unused = -1;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin old = 0;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin for (i = matchstate.size; i--;)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!matchstate.cache[i])
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin empty = i;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner else if (!matchstate.cache[i]->keep)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unused = i;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner else if (*(Key_t*)matchstate.cache[i]->pattern == key && !strcmp(matchstate.cache[i]->pattern, pattern) && matchstate.cache[i]->reflags == reflags)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin break;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else if (!matchstate.cache[old] || matchstate.cache[old]->serial > matchstate.cache[i]->serial)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin old = i;
7c2fbfb345896881c631598ee3852ce9ce33fb07April Chin if (i < 0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (unused < 0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (empty < 0)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unused = old;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin unused = empty;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (!(cp = matchstate.cache[unused]) && !(cp = matchstate.cache[unused] = newof(0, Cache_t, 1, 0)))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (status)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *status = REG_ESPACE;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner if (cp->keep)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner cp->keep = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin regfree(&cp->re);
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner if ((i = strlen(pattern) + 1) >= cp->size)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner cp->size = roundof(i, ROUND);
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner if (!(cp->pattern = newof(cp->pattern, char, cp->size, 0)))
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner {
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner if (status)
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner *status = REG_ESPACE;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner return 0;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner strcpy(cp->pattern, pattern);
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner while (++i < sizeof(Key_t))
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner cp->pattern[i] = 0;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner pattern = (const char*)cp->pattern;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner if (i = regcomp(&cp->re, pattern, reflags))
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin {
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (status)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *status = i;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner cp->keep = 1;
3e14f97f673e8a630f076077de35afdd43dc1587Roger A. Faulkner cp->reflags = reflags;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin }
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin else
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin cp = matchstate.cache[i];
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin cp->serial = ++matchstate.serial;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin if (status)
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin *status = 0;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin return &cp->re;
da2e3ebdc1edfbc5028edf1354e7dd2fa69a7968chin}