RBAC Role Inheritance (C)
Topics: graphs, DFS, transitive closure, cycle detection
Problem
A role grants permissions directly and inherits all permissions of its parent
roles (which inherit from theirs). Compute a role's effective permissions — the
union over the whole inheritance chain — and reject cyclic inheritance.
typedef struct {
const char *name;
const char *const *inherits; int ninherits; // parent roles
const char *const *grants; int ngrants; // direct permissions
} Role;
typedef enum { RBAC_OK, RBAC_CYCLE } RbacStatus;
RbacStatus rbac_permissions(const Role *roles, int n, const char *start,
const char **out_perms, int *out_nperms,
const char **out_cycle, int *out_ncycle);
RBAC_OK — out_perms[0..*out_nperms) is the sorted, de-duplicated union of
permissions reachable from start.RBAC_CYCLE — out_cycle[0..*out_ncycle) is the sorted set of roles on the
offending cycle.
A parent referenced but never defined is an empty leaf; an unknown start role has
no permissions; self-inheritance (a extends a) is a cycle.
Key concepts
- DFS + union: walk parents depth-first, adding each visited role's grants to a
set. A diamond (two parents sharing a grandparent) must grant the shared
permission once — a visited (black) role is skipped.
- Three-color cycle detection: mark a role gray while it's on the current
path and black once fully explored. Reaching a gray role again is a back
edge — a cycle. The cycle's members are the roles on the path from that gray node
to the top of the recursion stack.
- Deterministic output: sort parents before recursing and sort the final
permission / cycle lists.
Intern role names for color tracking — no allocation.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/rbac && /tmp/rbac
Sign in to submit your solution.