view regexParser/regexParser.h @ 248:2b1fbfb92d54

implement tSearch
author Masataka Kohagura <>
date Fri, 22 Jan 2016 20:09:42 +0900
parents f5931151d70c
children 9493800265a8
line wrap: on
line source

#define NEW(type) (type*)malloc(sizeof(type))


#define BITBLOCK 64
typedef struct bitVector {
    unsigned long bitContainer;
} BitVector,*BitVectorPtr;

typedef struct word {
    unsigned char *word;
    int length;
    // look up table for BM search.
    // BitVector nextState;
    // struct word *next;
} Word, *WordPtr;

typedef struct utf8Range {
    unsigned long begin;
    unsigned long end;
    struct utf8Range *next; // only used in the parser.
} RangeList , *RangeListPtr;

typedef struct condition {
    RangeList range;
    Word w;
} Condition, *ConditionList;

typedef struct charClass {
    unsigned char type;
    struct charClass *left;
    struct charClass *right;
    Condition cond;
    int stateNum;
    BitVector nextState;
} CharClass, *CharClassPtr;

struct node;

typedef struct state {
    int stateNum;
    BitVector bitState;
    CharClassPtr cc;
    bool accept;
    struct tState *tState;
    struct node *node;
    struct state *next;
} State, *StatePtr;

struct tsValue;

typedef struct ccv {
    unsigned long begin;
    unsigned long end;
    Word w;
    BitVector state;
    struct tState *tState;
} CCV,*CCVPtr;

typedef struct tState {
    State *state;
    void stateSkip(tsValue);
    int ccvSize;
    CCV ccv;
} TState, *TStatePtr;

typedef struct result {
    unsigned char begin;
    unsigned char end;
    struct result *next;
} Result, *ResultPtr;

typedef struct node {
    unsigned char tokenType;
    CharClassPtr cc;
    int stateNum;
    int nextStateNum;
    StatePtr state;
    StatePtr nextState;
    struct node *left;
    struct node *right;
} Node, *NodePtr;

typedef struct stateStack {
    BitVector state;
    struct stateStack *next;
} StateStack, *StateStackPtr;

typedef struct transitionGenerator {
    long totalStateCount;
    StateStackPtr stack;
    StatePtr stateTop;
    StatePtr stateEnd;
    StatePtr *stateArray;
    StatePtr stateList;
} TransitionGenerator, *TransitionGeneratorPtr;

typedef struct tsValue {
    Buffer buff;
    ResultPtr result;
    TransitionGeneratorPtr tg;
    TState *current;
    TState *blockBegin;
    TState *blockEnd;
} TSValue, *TSValuePtr;

typedef struct tgValue {
    StatePtr asterisk;   // last * state of the expression
    StatePtr startState;
    StatePtr endState;
    TransitionGeneratorPtr tg;
} TGValue, *TGValuePtr;

enum charClassStackState {

typedef struct charClassStack {
    charClassStackState turn;
    CharClassPtr cc;
    struct charClassStack *next;
} CharClassStack, *CharClassStackPtr;

typedef struct charClassWalker {
    CharClassStackPtr stack;
    charClassStackState turn;
    CharClassPtr next;
} CharClassWalker, *CharClassWalkerPtr;

typedef struct regexInfo {
    unsigned char *ptr;
    unsigned char tokenType;
    unsigned char *tokenValue;
    int stateNumber;
} RegexInfo, *RegexInfoPtr;

typedef struct buffer {
    unsigned char *buff;
    unsigned char *buffptr;
    unsigned char *buffend;
    unsigned char *matchBegin;
} Buffer, *BufferPtr;

typedef struct {
    unsigned char* file_mmap;
    off_t size;
} st_mmap_t;

extern NodePtr createNode(RegexInfoPtr ri,unsigned char type,CharClassPtr cc, NodePtr left, NodePtr right);
extern CharClassPtr createCharClassRange(unsigned long begin, unsigned long end,unsigned long state, CharClassPtr left, CharClassPtr right);
extern NodePtr regex(RegexInfoPtr);