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