pdl_rule.c File Reference

Implementation of the pdl rules. More...

#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "lcmaps_log.h"
#include "pdl_rule.h"
#include "pdl_policy.h"
#include "pdl_variable.h"

Go to the source code of this file.

Functions
rule_t *	_add_rule (const record_t *state, const record_t *true_branch, const record_t *false_branch)
const rule_t *	find_state (const rule_t *rule, const char *state)
int	find_insert_position (const int *list, const int rule_number, unsigned int high)
unsigned int	rule_number (const rule_t *rule)
BOOL	make_list (int *new_list, const int *list, const int rule_number, const unsigned int depth)
unsigned int	count_rules (const rule_t *rule)
void	update_list (unsigned int *rules, unsigned int rule)
const rule_t *	get_rule_number (unsigned int rule_num)
void	start_new_rules (void)
void	allow_new_rules (BOOL allow)
rule_t *	add_rule (record_t *state, record_t *true_branch, record_t *false_branch)
BOOL	check_rule_for_recursion (const rule_t *rule)
recursion_t	has_recursion (const rule_t *rule, int *list, unsigned int depth, unsigned int *seen_rules)
void	reduce_rule (rule_t *rule)
void	show_rules (const rule_t *rule)
void	free_rules (rule_t *rule)
const rule_t *	get_top_rule (void)
void	set_top_rule (const rule_t *rule)

---

Detailed Description

Implementation of the pdl rules.

Author:

G.M. Venekamp (venekamp@nikhef.nl)

Version:

Revision

1.22

Date:

Date

2005/03/01 17:05:10

Definition in file pdl_rule.c.

---

Function Documentation

rule_t * _add_rule (  const record_t *  state, const record_t *  true_branch, const record_t *  false_branch )

Rules come in three different forms: a -> b a -> b | c ~a ->b They share a common structure. First the left hand side gives the starting state and right hand side the states to transit to. This means that each rule has a starting state and depending on the form one or two transit states: The first form has only the true transit state; The second form had both true and false transit states; The thrird for has only the false transit state. When either the true or false transit state for a rule does not exists, 0 should be supplied. Parameters: state  Starting state true_branch  True transit state false_branch  False transit state Returns: TRUE if the rule has been added successfully, FALSE otherwise. Definition at line 151 of file pdl_rule.c. References rule_s::false_branch, find_policy(), find_state(), record_s::lineno, rule_s::lineno, policy_s::lineno, rule_s::next, PDL_ERROR, policy_t, record_t, rule_t, rule_s::state, record_s::string, rule_s::true_branch, and warning(). Referenced by add_rule().

rule_t* add_rule (  record_t *  state, record_t *  true_branch, record_t *  false_branch )

Add a new rule to the list of rules. This function acts as a wrapper function for _add_rule(). Parameters: state  Starting state true_branch  True transit state false_branch  False transit state Definition at line 93 of file pdl_rule.c. References _add_rule(), record_t, rule_t, and record_s::string.

void allow_new_rules (  BOOL  allow  )

Is it allowed to add new rules? Parameters: allow  TRUE if adding new rules is allowed, FALSE otherwise. Definition at line 78 of file pdl_rule.c. Referenced by allow_rules().

BOOL check_rule_for_recursion (  const rule_t *  rule  )

Check the rule for occurances of recursion. Returns: TRUE if a recursion have been found, FALSE otherwise. Definition at line 228 of file pdl_rule.c. References count_rules(), get_rule_number(), has_recursion(), lineno, rule_s::lineno, PDL_WARNING, RECURSION, recursion_t, rule_t, TRUE, and warning(). Referenced by check_policies_for_recursion().

unsigned int count_rules (  const rule_t *  rule  )

Count the number of rules that follow 'rule' inclusive. Parameters: rule  The rule to start count from. Returns: Number of counted rules. Definition at line 265 of file pdl_rule.c. References rule_s::next, and rule_t. Referenced by check_rule_for_recursion().

int find_insert_position (  const int *  list, const int  rule_number, unsigned int  high )

Based on a sorted list, find the position where to insert an new element without disturbing the ordering in the list. The search is a binary search. Parameters: list  List of sorted numbers. rule_number  Number to be inserted. high  Element number of last element in the list. Returns: Position of insertion. Definition at line 496 of file pdl_rule.c. References rule_number(). Referenced by make_list(), and update_list().

const rule_t * find_state (  const rule_t *  rule, const char *  state )

Find a state with name state. Parameters: state  Name of the state to be found. rule  list of rules to be searched Returns: Rule which contains the state or 0 when no such rule could be found. Definition at line 210 of file pdl_rule.c. References find_state(), rule_s::next, rule_t, and rule_s::state. Referenced by _add_rule(), find_state(), has_recursion(), and pdl_next_plugin().

void free_rules (  rule_t *  rule  )

Free all resources associated with the rules. Parameters: rule  Rule for which the resources must be freed. Definition at line 645 of file pdl_rule.c. References rule_s::false_branch, rule_s::next, rule_t, rule_s::state, and rule_s::true_branch. Referenced by add_policy(), and free_policies().

const rule_t * get_rule_number (  unsigned int  rule_num  )

Give the position of the rule in the policy, return that rule. Parameters: rule_num  Position of the rule in the current policy. Returns: Rule that is associated with the rule_num, NULL if the rule cannot be found. Definition at line 286 of file pdl_rule.c. References rule_s::next, and rule_t. Referenced by check_rule_for_recursion().

const rule_t* get_top_rule (  void   )

Get the top rule. Returns: Top rule. Definition at line 666 of file pdl_rule.c. References rule_t.

recursion_t has_recursion (  const rule_t *  rule, int *  list, unsigned int  depth, unsigned int *  seen_rules )

Check the a rule for recursion. This is done in a recursive manner. From the top rule, all possible paths are considered. Each path becomes a top of its own and from their all possible paths are traveled. Each time the tree is searched at a greater depth, a list is kept to tell which states have been seen for the current path. In this list of states no duplicates should be present. If a seen state state already appears in the list, the path taken is recursive. This information is propagated back up the traveled tree. At the same time another list is maintained. In this list all visited states are remembered. Duplicates are not added. When all possible paths have been traveled, the list tells all visited rules. When a particular rule is not part of the tree, it is also not listed in the list. This way one can check for disconnected rules. Parameters: rule  Rule to check for recursion. list  List to keep track of each traveled path. depth  Current depth of the tree. seen_rules  Rules that have been visited and hence are part of the path. Returns: Whether or not recursion has been detected and also if it has been reported. Definition at line 326 of file pdl_rule.c. References rule_s::false_branch, find_state(), rule_s::lineno, lineno, make_list(), NO_RECURSION, PDL_ERROR, RECURSION, RECURSION_HANDLED, recursion_t, rule_number(), rule_t, rule_s::state, rule_s::true_branch, update_list(), and warning(). Referenced by check_rule_for_recursion().

BOOL make_list (  int *  new_list, const int *  list, const int  rule_number, const unsigned int  depth )

Make a new sorted list based on the current list and the element to be inserted. The element will only be added to the list if it is not already present. Parameters: new_list  New list after sorted insertion of new element. list  Old list. rule_number  Number to be inserted into the list. depth  Current depth of the tree. It is used to detmine the number of elements of the list. Returns: TRUE if element has been added, FALSE otherwise Definition at line 534 of file pdl_rule.c. References find_insert_position(), rule_number(), and TRUE. Referenced by has_recursion().

void reduce_rule (  rule_t *  rule  )

Reduce a rule to its elementry form, i.e. all variables in the rule are substituted by their respective values. Parameters: rule  Rule to reduce. Definition at line 566 of file pdl_rule.c. References rule_s::false_branch, FALSE_BRANCH, reduce_to_var(), rule_t, rule_s::state, STATE, rule_s::true_branch, and TRUE_BRANCH. Referenced by reduce_policies().

unsigned int rule_number (  const rule_t *  rule  )

Given a rule, find the corresponding position in the policy. Parameters: rule  Rule of which the position must be found. Returns: Position of the rule in the current policy. Definition at line 433 of file pdl_rule.c. References rule_s::next, and rule_t. Referenced by find_insert_position(), has_recursion(), and make_list().

void set_top_rule (  const rule_t *  rule  )

Set the top rule to a new value. Parameters: rule  New value of top rule. Definition at line 678 of file pdl_rule.c. References rule_t. Referenced by free_policies(), and reduce_policies().

void show_rules (  const rule_t *  rule  )

Show a rule and its descendants. Parameters: rule  Rule to display. Definition at line 623 of file pdl_rule.c. References rule_s::false_branch, lcmaps_log_debug(), rule_s::next, rule_t, rule_s::state, and rule_s::true_branch. Referenced by show_policies().

void start_new_rules (  void   )

Start a new list of rules. Definition at line 65 of file pdl_rule.c. Referenced by add_policy().

void update_list (  unsigned int *  rules, unsigned int  rule )

Update the list that hold the visited rules. This is a sorted list for easy insertion and look-up. Duplicate rules are not inserted. The first element of the list tells the total number of elements that follow. Note: The list expects rules to be numbered starting from 1. This is because 0 denotes empty cells. The find_insert_position() returns numbers starting from 0. This is corrected for in this function. Parameters: rules  List of visited rules. rule  rule to insert. Definition at line 461 of file pdl_rule.c. References find_insert_position(). Referenced by has_recursion().

---