Dfa-module header files.

diff --git a/include/bset.h b/include/bset.h
new file mode 100644 (file)
index 0000000..8c9966c
--- /dev/null
+++ b/include/bset.h
@@ -0,0 +1,44 @@
+/*
+ * Copyright (C) 1994, Index Data I/S 
+ * All rights reserved.
+ * Sebastian Hammer, Adam Dickmeiss
+ *
+ * $Log: bset.h,v $
+ * Revision 1.1  1994-09-26 10:17:42  adam
+ * Dfa-module header files.
+ *
+ */
+#ifndef BSET_H
+#define BSET_H
+
+typedef unsigned short BSetWord;
+typedef BSetWord *BSet;
+
+typedef struct BSetHandle_ {
+    unsigned size;        /* size of set in members */
+    unsigned wsize;       /* size of individual set (in BSetWord)*/
+    unsigned offset;      /* offset in current set block */
+    unsigned chunk;       /* chunk, i.e. size of each block */
+    struct BSetHandle_ *setchain;
+    BSetWord setarray[1];
+} BSetHandle;
+
+BSetHandle *mk_BSetHandle (int size, int chunk);
+void       rm_BSetHandle  (BSetHandle **shp);
+int        inf_BSetHandle (BSetHandle *sh, long *used, long *alloc);
+BSet       cp_BSet        (BSetHandle *sh, BSet dst, BSet src);
+void       add_BSet       (BSetHandle *sh, BSet dst, unsigned member);
+void       union_BSet     (BSetHandle *sh, BSet dst, BSet src);
+BSet       mk_BSet        (BSetHandle **shp);
+void       rm_BSet        (BSetHandle **shp);
+void       res_BSet       (BSetHandle *sh, BSet dst);
+void       com_BSet       (BSetHandle *sh, BSet dst);
+void       pr_BSet        (BSetHandle *sh, BSet src);
+unsigned   test_BSet      (BSetHandle *sh, BSet src, unsigned member);
+int        trav_BSet      (BSetHandle *sh, BSet src, unsigned member);
+int        travi_BSet     (BSetHandle *sh, BSet src, unsigned member);
+unsigned   hash_BSet      (BSetHandle *sh, BSet src);
+int        eq_BSet        (BSetHandle *sh, BSet dst, BSet src);
+void       pr_charBSet    (BSetHandle *sh, BSet src, void (*f)(int));
+
+#endif

diff --git a/include/dfa.h b/include/dfa.h
new file mode 100644 (file)
index 0000000..0d58314
--- /dev/null
+++ b/include/dfa.h
@@ -0,0 +1,122 @@
+/*
+ * Copyright (C) 1994, Index Data I/S 
+ * All rights reserved.
+ * Sebastian Hammer, Adam Dickmeiss
+ *
+ * $Log: dfa.h,v $
+ * Revision 1.1  1994-09-26 10:17:43  adam
+ * Dfa-module header files.
+ *
+ */
+
+#ifndef DFA_H
+#define DFA_H
+
+#include <bset.h>
+#include <set.h>
+#define CAT     16000
+#define OR      16001
+#define STAR    16002
+#define PLUS    16003
+#define EPSILON 16004
+
+typedef struct Tnode_ {
+    union  {
+        struct Tnode_ *p[2];  /* CAT,OR,STAR,PLUS (left,right) */
+        short ch[2];          /* if ch[0] >= 0 then this Tnode represents */
+                              /*   a character in range [ch[0]..ch[1]]    */
+                              /* otherwise ch[0] represents */
+                              /*   accepting no (-acceptno) */
+    } u;
+    unsigned pos : 15;        /* CAT/OR/STAR/EPSILON or non-neg. position */
+    unsigned nullable : 1;
+    Set firstpos;             /* first positions */
+    Set lastpos;              /* last positions */
+} Tnode;
+
+typedef struct Tblock_ {      /* Tnode bucket (block) */
+    struct Tblock_ *next;     /* pointer to next bucket */
+    Tnode *tarray;            /* array of nodes in bucket */
+} Tblock;
+
+typedef struct  {
+    Tnode *root;              /* root of regular syntax tree */
+    Tnode *top;               /* regular tree top (returned by parse_dfa) */
+    int position;             /* no of positions so far */
+    int rule;                 /* no of rules so far */
+    BSetHandle *charset;      /* character set type */
+    BSet anyset;              /* character recognized by `.' */
+    int use_Tnode;            /* used Tnodes */
+    int max_Tnode;            /* allocated Tnodes */
+    Tblock *start;            /* start block of Tnodes */
+    Tblock *end;              /* end block of Tnodes */
+} DFA;
+
+typedef struct {
+    unsigned char ch[2];      /* transition on ch[0] <= c <= ch[1] to */
+    unsigned short to;        /* this state */
+} DFA_tran;
+
+typedef struct DFA_trans_ {
+    struct DFA_trans_ *next;  /* next DFA transition block */
+    DFA_tran *tran_block;     /* pointer to transitions */
+    int  ptr;                 /* index of next transition in tran_block */
+    int  size;                /* allocated size of tran_block */
+} DFA_trans;
+
+typedef struct DFA_state_ {
+    struct DFA_state_ *next;  /* next entry in free/unmarked/marked list */
+    struct DFA_state_ *link;  /* link to next entry in hash chain */
+    DFA_tran *trans;          /* transition list */
+    Set set;                  /* set of positions (important nfa states) */
+    short no;                 /* no of this state */
+    short tran_no;            /* no of transitions to other states */
+    short rule_no;            /* if non-zero, this holds accept rule no */
+} DFA_state;
+
+typedef struct DFA_stateb_ {
+    struct DFA_stateb_ *next;
+    DFA_state *state_block;
+} DFA_stateb;
+
+typedef struct  {
+    DFA_state *freelist;      /* chain of unused (but allocated) DFA states */
+    DFA_state *unmarked;      /* chain of unmarked DFA states */
+    DFA_state *marked;        /* chain of marked DFA states */
+    DFA_stateb *statemem;     /* state memory */
+    int no;                   /* no of states (unmarked+marked) */
+    SetType st;               /* Position set type */
+    int hash;                 /* no hash entries in hasharray */
+    DFA_state **hasharray;    /* hash pointers */
+    DFA_state **sortarray;    /* sorted DFA states */
+    DFA_trans *transmem;      /* transition memory */
+} DFA_states;
+           
+DFA *       init_dfa        (void);
+void        rm_dfa          (DFA **dfap);
+int         parse_dfa       (DFA *, char **, const unsigned short *);
+DFA_states* mk_dfas         (DFA *, int poset_chunk);
+void        rm_dfas         (DFA_states **dfas);
+
+Tnode *     mk_Tnode        (void);
+Tnode *     mk_Tnode_cset   (BSet charset);
+void        term_Tnode      (void);
+
+int         init_DFA_states (DFA_states **dfasp, SetType st, int hash);
+int         rm_DFA_states   (DFA_states **dfasp);
+int         add_DFA_state   (DFA_states *dfas, Set *s, DFA_state **sp);
+DFA_state   *get_DFA_state  (DFA_states *dfas);
+void        sort_DFA_states (DFA_states *dfas);
+void        add_DFA_tran    (DFA_states *, DFA_state *, int, int, int);
+
+extern int  debug_dfa_trav;
+extern int  debug_dfa_tran;
+extern int  debug_dfa_followpos;
+extern int  dfa_verbose;
+
+extern unsigned short
+        thompson_chars[],
+        brief_chars[],
+        grep_chars[],
+        ccl_chars[];
+#endif

diff --git a/include/set.h b/include/set.h
new file mode 100644 (file)
index 0000000..ed31c8f
--- /dev/null
+++ b/include/set.h
@@ -0,0 +1,40 @@
+/*
+ * Copyright (C) 1994, Index Data I/S 
+ * All rights reserved.
+ * Sebastian Hammer, Adam Dickmeiss
+ *
+ * $Log: set.h,v $
+ * Revision 1.1  1994-09-26 10:17:44  adam
+ * Dfa-module header files.
+ *
+ */
+#ifndef SET_H
+#define SET_H
+
+typedef struct SetElement_  {
+    struct SetElement_ *next;
+    int value;
+} SetElement, *Set;
+
+typedef struct {
+    Set  alloclist;
+    Set  freelist;
+    long used;
+    int  chunk;
+} *SetType;
+
+SetType  mk_SetType   (int chunk);
+int      inf_SetType  (SetType st, long *used, long *allocated);
+SetType  rm_SetType   (SetType st);
+Set      mk_Set       (SetType st);
+Set      add_Set      (SetType st, Set s, int value);
+Set      merge_Set    (SetType st, Set s1, Set s2);
+Set      union_Set    (SetType st, Set s1, Set s2);
+Set      rm_Set       (SetType st, Set s);
+Set      cp_Set       (SetType st, Set s);
+void     pr_Set       (SetType st, Set s);
+unsigned hash_Set     (SetType st, Set s);
+int      eq_Set       (SetType s, Set s1, Set s2);
+
+#endif
+