regex/TRE/tre-last-matched.h

   1 /*
   2  * Copyright (c) 2011 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28
  29 #include <bitstring.h>
  30
  31 #ifndef __TRE_LAST_MATCHED_H__
  32 #define __TRE_LAST_MATCHED_H__
  33
  34 #define __TRE_LAST_MATCHED_BRANCH_SHARED(_i)    \
  35   struct _tre_ ## _i *last_matched;             \
  36   int n_last_matched;                           \
  37   int cmp_tag;                                  \
  38   int n_tags;
  39 #define __TRE_LAST_MATCHED_SHARED(_i)           \
  40   tre_ ## _i ## _t *branches;                   \
  41   int n_branches;                               \
  42   int start_tag;
  43
  44 /* These structures record the relationship between each union branch and
  45  * its tags.  The end_tag is a special tag, created at the end of each branch
  46  * that can be used to detect which branch was last matched.  Then the tags
  47  * of the other branches can be set to unmatched.  For example:
  48  *
  49  *     ((a)|(b))*
  50  *
  51  * when matched against "ab", the tags associated with the first branch, need
  52  * to be unset, because the last match was in the second branch.
  53  *
  54  * There are two sets of two structures.  The first structure records the
  55  * branch info, while the second records union info; what branches form that
  56  * union.  Because a branch may have nested unions, we need to record that
  57  * as well.  The "n" field of the branch info structure records the number
  58  * of unions at the top level of the branch (a union may itself have branches
  59  * with nested unions, but those union are only counted with the immediate
  60  * branch that contains them).  The "n" field of the union info structure is
  61  * the count of branches in that union.
  62  *
  63  * The "end_tag" field of a branch info structure is the number of the special
  64  * tag that is created at the end of each branch.  It can be used to determine
  65  * which branch was last matched.
  66  *
  67  * The first set (the info_pre structures) are used during tre_add_tags() to
  68  * record the tag info while tags are being added to the AST.  They use link
  69  * lists, and the total number of branch and union structures used are
  70  * recorded in n_branches and n_unions.  The second set (the info structures)
  71  * are created from the first, leaving out the link pointers (these structures
  72  * use arrays of structures, rather than link lists), and the n_branches and
  73  * n_unions fields are no longer needed.  The info_pre structures are allocated
  74  * using the tre_mem mechanism, while the info structure are allocated in
  75  * one chuck with xmalloc (so it can be easily deallocated).
  76  *
  77  * The above macro are used for the shared fields of the structures. */
  78
  79 struct _tre_last_matched_pre; /* forward reference */
  80
  81 typedef struct _tre_last_matched_branch_pre {
  82   struct _tre_last_matched_branch_pre *next;
  83   __TRE_LAST_MATCHED_BRANCH_SHARED(last_matched_pre)
  84   int tot_branches;
  85   int tot_last_matched;
  86   int tot_tags;
  87   bitstr_t tags[0];
  88 } tre_last_matched_branch_pre_t;
  89
  90 typedef struct _tre_last_matched_pre {
  91   struct _tre_last_matched_pre *next;
  92   __TRE_LAST_MATCHED_SHARED(last_matched_branch_pre)
  93   int tot_branches;
  94   int tot_last_matched;
  95   int tot_tags;
  96 } tre_last_matched_pre_t;
  97
  98 struct _tre_last_matched; /* forward reference */
  99
 100 typedef struct _tre_last_matched_branch {
 101   int *tags;
 102   __TRE_LAST_MATCHED_BRANCH_SHARED(last_matched)
 103 } tre_last_matched_branch_t;
 104
 105 typedef struct _tre_last_matched {
 106   __TRE_LAST_MATCHED_SHARED(last_matched_branch)
 107 } tre_last_matched_t;
 108
 109 #endif /* __TRE_LAST_MATCHED_H__ */