#include "policytree.h"
#include <libDER/oids.h>
#include <utilities/debugging.h>
#include <stdlib.h>
#define DUMP_POLICY_TREE 0
#if !defined(DUMP_POLICY_TREE)
#include <stdio.h>
#endif
static policy_set_t policy_set_create(const oid_t *p_oid) {
policy_set_t policy_set =
(policy_set_t)malloc(sizeof(*policy_set));
policy_set->oid_next = NULL;
policy_set->oid = *p_oid;
secdebug("policy-set", "%p", policy_set);
return policy_set;
}
void policy_set_add(policy_set_t *policy_set, const oid_t *p_oid) {
policy_set_t node = (policy_set_t)malloc(sizeof(*node));
node->oid_next = *policy_set;
node->oid = *p_oid;
*policy_set = node;
secdebug("policy-set", "%p -> %p", node, node->oid_next);
}
void policy_set_free(policy_set_t node) {
while (node) {
policy_set_t next = node->oid_next;
secdebug("policy-set", "%p -> %p", node, next);
free(node);
node = next;
}
}
bool policy_set_contains(policy_set_t node, const oid_t *oid) {
for (; node; node = node->oid_next) {
if (oid_equal(node->oid, *oid))
return true;
}
return false;
}
void policy_set_intersect(policy_set_t *policy_set, policy_set_t other_set) {
bool other_has_any = policy_set_contains(other_set, &oidAnyPolicy);
if (policy_set_contains(*policy_set, &oidAnyPolicy)) {
policy_set_t node = other_set;
if (other_has_any) {
while (node) {
if (!policy_set_contains(*policy_set, &node->oid)) {
policy_set_add(policy_set, &node->oid);
}
}
} else {
policy_set_free(*policy_set);
*policy_set = NULL;
while (node) {
policy_set_add(policy_set, &node->oid);
}
}
} else if (!other_has_any) {
policy_set_t *pnode = policy_set;
while (*pnode) {
policy_set_t node = *pnode;
if (policy_set_contains(other_set, &node->oid)) {
pnode = &node->oid_next;
} else {
*pnode = node->oid_next;
node->oid_next = NULL;
policy_set_free(node);
}
}
}
}
policy_tree_t policy_tree_create(const oid_t *p_oid, policy_qualifier_t p_q) {
policy_tree_t node = malloc(sizeof(*node));
node->valid_policy = *p_oid;
node->qualifier_set = p_q;
node->expected_policy_set = policy_set_create(p_oid);
node->children = NULL;
node->siblings = NULL;
secdebug("policy-node", "%p", node);
return node;
}
bool policy_tree_walk_depth(policy_tree_t root, int depth,
bool(*callback)(policy_tree_t, void *), void *ctx) {
policy_tree_t stack[depth + 1];
int stack_ix = 0;
stack[stack_ix] = root;
policy_tree_t node;
bool match = false;
bool child_visited = false;
while (stack_ix >= 0) {
node = stack[stack_ix];
policy_tree_t child = node->children;
if (!child_visited && stack_ix < depth && child ) {
stack[++stack_ix] = child;
} else {
if (stack_ix == depth) {
match |= callback(node, ctx);
}
policy_tree_t sibling = node->siblings;
if (sibling) {
stack[stack_ix] = sibling;
child_visited = false;
} else {
stack_ix--;
child_visited = true;
}
}
}
return match;
}
static void policy_tree_free_node(policy_tree_t node) {
secdebug("policy-node", "%p children: %p siblngs: %p", node,
node->children, node->siblings);
if (node->expected_policy_set) {
policy_set_free(node->expected_policy_set);
node->expected_policy_set = NULL;
}
free(node);
}
void policy_tree_prune(policy_tree_t *node) {
policy_tree_t *child = &(*node)->children;
if (*child)
policy_tree_prune(child);
policy_tree_t *sibling = &(*node)->siblings;
if (*sibling)
policy_tree_prune(sibling);
policy_tree_free_node(*node);
*node = NULL;
}
void policy_tree_prune_childless(policy_tree_t *root, int depth) {
policy_tree_t *stack[depth + 1];
int stack_ix = 0;
stack[stack_ix] = root;
bool child_visited = false;
while (stack_ix >= 0) {
policy_tree_t *node;
node = stack[stack_ix];
policy_tree_t *child = &(*node)->children;
if (!child_visited && stack_ix < depth && *child) {
stack[++stack_ix] = child;
} else if (!*child) {
#if !defined(DUMP_POLICY_TREE)
printf("# prune /<%.08lx<\\ |%.08lx| >%.08lx> :%s: depth %d\n",
(intptr_t)node, (intptr_t)*node, (intptr_t)(*node)->siblings,
(child_visited ? "v" : " "), stack_ix);
#endif
policy_tree_t next = (*node)->siblings;
(*node)->siblings = NULL;
policy_tree_free_node(*node);
*node = next;
if (next) {
child_visited = false;
} else {
stack_ix--;
child_visited = true;
}
} else {
policy_tree_t *sibling = &(*node)->siblings;
if (*sibling) {
stack[stack_ix] = sibling;
child_visited = false;
} else {
stack_ix--;
child_visited = true;
}
}
}
}
static void policy_tree_add_child_explicit(policy_tree_t parent,
const oid_t *p_oid, policy_qualifier_t p_q, policy_set_t p_expected) {
policy_tree_t child = malloc(sizeof(*child));
child->valid_policy = *p_oid;
child->qualifier_set = p_q;
child->expected_policy_set = p_expected;
child->children = NULL;
#if 0
printf("# /%.08lx\\ |%.08lx| \\%.08lx/ >%.08lx> \\>%.08lx>/\n",
(intptr_t)parent, (intptr_t)child, (intptr_t)parent->children,
(intptr_t)parent->siblings,
(intptr_t)(parent->children ? parent->children->siblings : NULL));
#endif
child->siblings = parent->children;
parent->children = child;
secdebug("policy-node", "%p siblngs: %p", child, child->siblings);
}
void policy_tree_add_child(policy_tree_t parent,
const oid_t *p_oid, policy_qualifier_t p_q) {
policy_set_t policy_set = policy_set_create(p_oid);
policy_tree_add_child_explicit(parent, p_oid, p_q, policy_set);
}
void policy_tree_set_expected_policy(policy_tree_t node,
policy_set_t p_expected) {
if (node->expected_policy_set)
policy_set_free(node->expected_policy_set);
node->expected_policy_set = p_expected;
}
#if !defined(DUMP_POLICY_TREE)
static void policy_tree_dump4(policy_tree_t node, policy_tree_t parent,
policy_tree_t prev_sibling, int depth) {
policy_tree_t child = node->children;
policy_tree_t sibling = node->siblings;
static const char *spaces = " ";
printf("# %.*s/%.08lx\\ |%.08lx| <%.08lx< >%.08lx> depth %d\n",
depth * 11, spaces,
(intptr_t)parent, (intptr_t)node, (intptr_t)prev_sibling,
(intptr_t)sibling, depth);
if (child)
policy_tree_dump4(child, node, NULL, depth + 1);
if (sibling)
policy_tree_dump4(sibling, parent, node, depth);
}
#endif
void policy_tree_dump(policy_tree_t node) {
#if !defined(DUMP_POLICY_TREE)
policy_tree_dump4(node, NULL, NULL, 0);
#endif
}