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
79struct _tre_last_matched_pre; /* forward reference */
80
81typedef 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
90typedef 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
98struct _tre_last_matched; /* forward reference */
99
100typedef struct _tre_last_matched_branch {
101  int *tags;
102  __TRE_LAST_MATCHED_BRANCH_SHARED(last_matched)
103} tre_last_matched_branch_t;
104
105typedef struct _tre_last_matched {
106  __TRE_LAST_MATCHED_SHARED(last_matched_branch)
107} tre_last_matched_t;
108
109#endif /* __TRE_LAST_MATCHED_H__ */
110