Lines Matching defs:node
44 static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
45 static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
47 bin_tree_t *node);
48 static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
49 static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
50 static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
56 Idx node, bool root);
122 static void free_token (re_token_t *node);
123 static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
124 static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
320 Idx node = init_state->nodes.elems[node_cnt];
321 re_token_type_t type = dfa->nodes[node].type;
325 re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
335 *p++ = dfa->nodes[node].opr.c;
336 while (++node < dfa->nodes_len
337 && dfa->nodes[node].type == CHARACTER
338 && dfa->nodes[node].mb_partial)
339 *p++ = dfa->nodes[node].opr.c;
355 bitset_word_t w = dfa->nodes[node].opr.sbcset[i];
364 re_charset_t *cset = dfa->nodes[node].opr.mbcset;
989 /* Initial states have the epsilon closure of the node which is
990 the first node of the regular expression. */
1068 Idx node;
1073 for (node = 0; node < dfa->nodes_len; ++node)
1074 switch (dfa->nodes[node].type)
1077 if (dfa->nodes[node].opr.c >= ASCII_CHARS)
1081 switch (dfa->nodes[node].opr.ctx_type)
1115 if (dfa->nodes[node].opr.sbcset[i] >> rshift != 0)
1126 for (node = 0; node < dfa->nodes_len; ++node)
1128 if (dfa->nodes[node].type == CHARACTER
1129 && dfa->nodes[node].opr.c >= ASCII_CHARS)
1130 dfa->nodes[node].mb_partial = 0;
1131 else if (dfa->nodes[node].type == OP_PERIOD)
1132 dfa->nodes[node].type = OP_UTF8_PERIOD;
1213 bin_tree_t *node, *prev;
1215 for (node = root; ; )
1219 while (node->left || node->right)
1220 if (node->left)
1221 node = node->left;
1223 node = node->right;
1227 reg_errcode_t err = fn (extra, node);
1230 if (node->parent == NULL)
1232 prev = node;
1233 node = node->parent;
1235 /* Go up while we have a node that is reached from the right. */
1236 while (node->right == prev || node->right == NULL);
1237 node = node->right;
1245 bin_tree_t *node;
1247 for (node = root; ; )
1249 reg_errcode_t err = fn (extra, node);
1253 /* Go to the left node, or up and to the right. */
1254 if (node->left)
1255 node = node->left;
1259 while (node->right == prev || node->right == NULL)
1261 prev = node;
1262 node = node->parent;
1263 if (!node)
1266 node = node->right;
1275 optimize_subexps (void *extra, bin_tree_t *node)
1279 if (node->token.type == OP_BACK_REF && dfa->subexp_map)
1281 int idx = node->token.opr.idx;
1282 node->token.opr.idx = dfa->subexp_map[idx];
1283 dfa->used_bkref_map |= 1 << node->token.opr.idx;
1286 else if (node->token.type == SUBEXP
1287 && node->left && node->left->token.type == SUBEXP)
1289 Idx other_idx = node->left->token.opr.idx;
1291 node->left = node->left->left;
1292 if (node->left)
1293 node->left->parent = node;
1295 dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
1303 /* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
1306 lower_subexps (void *extra, bin_tree_t *node)
1311 if (node->left && node->left->token.type == SUBEXP)
1313 node->left = lower_subexp (&err, preg, node->left);
1314 if (node->left)
1315 node->left->parent = node;
1317 if (node->right && node->right->token.type == SUBEXP)
1319 node->right = lower_subexp (&err, preg, node->right);
1320 if (node->right)
1321 node->right->parent = node;
1328 lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
1331 bin_tree_t *body = node->left;
1339 && node->left != NULL
1340 && (node->token.opr.idx >= BITSET_WORD_BITS
1342 & ((bitset_word_t) 1 << node->token.opr.idx))))
1343 return node->left;
1345 /* Convert the SUBEXP node to the concatenation of an
1357 op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
1358 op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
1365 calc_first (void *extra, bin_tree_t *node)
1368 if (node->token.type == CONCAT)
1370 node->first = node->left->first;
1371 node->node_idx = node->left->node_idx;
1375 node->first = node;
1376 node->node_idx = re_dfa_add_node (dfa, node->token);
1377 if (BE (node->node_idx == REG_MISSING, 0))
1379 if (node->token.type == ANCHOR)
1380 dfa->nodes[node->node_idx].constraint = node->token.opr.ctx_type;
1387 calc_next (void *extra, bin_tree_t *node)
1389 switch (node->token.type)
1392 node->left->next = node;
1395 node->left->next = node->right->first;
1396 node->right->next = node->next;
1399 if (node->left)
1400 node->left->next = node->next;
1401 if (node->right)
1402 node->right->next = node->next;
1408 /* Pass 3: link all DFA nodes to their NEXT node (any order will do). */
1410 link_nfa_nodes (void *extra, bin_tree_t *node)
1413 Idx idx = node->node_idx;
1416 switch (node->token.type)
1422 assert (node->next == NULL);
1430 if (node->left != NULL)
1431 left = node->left->first->node_idx;
1433 left = node->next->node_idx;
1434 if (node->right != NULL)
1435 right = node->right->first->node_idx;
1437 right = node->next->node_idx;
1447 err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
1451 dfa->nexts[idx] = node->next->node_idx;
1452 if (node->token.type == OP_BACK_REF)
1457 assert (!IS_EPSILON_NODE (node->token.type));
1458 dfa->nexts[idx] = node->next->node_idx;
1465 /* Duplicate the epsilon closure of the node ROOT_NODE.
1498 /* In case of the node can't epsilon-transit, don't duplicate the
1500 destination of the node. */
1506 /* In case of the node can epsilon-transit, and it has only one
1511 /* If the node is root_node itself, it means the epsilon closure
1520 /* In case the node has another constraint, append it. */
1531 /* In case of the node can epsilon-transit, and it has two
1535 /* Search for a duplicated node which satisfies the constraint. */
1539 /* There is no such duplicated node, create a new one. */
1554 /* There is a duplicated node which satisfy the constraint,
1575 /* Search for a node which is duplicated from the node ORG_NODE, and
1592 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1593 Return the index of the new node, or REG_MISSING if insufficient storage is
1606 /* Store the index of the original node. */
1634 /* Calculate "eclosure" for all the node in DFA. */
1679 /* Calculate epsilon closure of NODE. */
1682 calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, Idx node, bool root)
1690 err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1694 /* This indicates that we are calculating this node now.
1696 dfa->eclosures[node].nelem = REG_MISSING;
1698 /* If the current node has constraints, duplicate all nodes
1700 if (dfa->nodes[node].constraint
1701 && dfa->edests[node].nelem
1702 && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1704 err = duplicate_node_closure (dfa, node, node, node,
1705 dfa->nodes[node].constraint);
1711 if (IS_EPSILON_NODE(dfa->nodes[node].type))
1712 for (i = 0; i < dfa->edests[node].nelem; ++i)
1715 Idx edest = dfa->edests[node].elems[i];
1736 the epsilon closure of this node is also incomplete. */
1745 ok = re_node_set_insert (&eclosure, node);
1749 dfa->eclosures[node].nelem = 0;
1751 dfa->eclosures[node] = eclosure;
3283 /* Then join them by ALT node. */
3668 /* Then join them by ALT node. */
3738 /* Create a tree node. */
3787 mark_opt_subexp (void *extra, bin_tree_t *node)
3791 if (node->token.type == SUBEXP && node->token.opr.idx == idx)
3792 node->token.opt_subexp = 1;
3797 /* Free the allocated memory inside NODE. */
3800 free_token (re_token_t *node)
3803 if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
3804 free_charset (node->opr.mbcset);
3807 if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
3808 re_free (node->opr.sbcset);
3811 /* Worker function for tree walking. Free the allocated memory inside NODE
3815 free_tree (void *extra, bin_tree_t *node)
3817 free_token (&node->token);
3822 /* Duplicate the node SRC, and return new node. This is a preorder
3830 const bin_tree_t *node;
3834 for (node = root; ; )
3837 *p_new = create_token_tree (dfa, NULL, NULL, &node->token);
3844 /* Go to the left node, or up and to the right. */
3845 if (node->left)
3847 node = node->left;
3853 while (node->right == prev || node->right == NULL)
3855 prev = node;
3856 node = node->parent;
3858 if (!node)
3861 node = node->right;
