Documentation
¶
Overview ¶
Package graph implements handling of the groups graph.
Such graphs are built from list of AuthGroup proto messages that reference each other by name.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Graph ¶
type Graph struct {
Nodes []Node // all graph nodes
NodesByName map[string]NodeIndex // name => index in Nodes
}
Graph is a static group graph optimized for traversals.
Not safe for concurrent use.
func (*Graph) Descendants ¶
Descendants returns a set with 'n' and all groups it includes.
func (*Graph) NodeByName ¶
NodeByName returns a node given its name or nil if not found.
func (*Graph) ToQueryable ¶
func (g *Graph) ToQueryable() (*QueryableGraph, error)
ToQueryable converts the graph to a form optimized for IsMember queries.
type IsMemberResult ¶
type IsMemberResult byte
IsMemberResult is the possible results for a 'ident in group' check implemented by QueryableGraph.IsMember.
const ( IdentIsNotMember IsMemberResult = iota IdentIsMember GroupIsUnknown )
type MembershipsQueryCache ¶
type MembershipsQueryCache struct {
// Identity whose memberships are being queried.
Identity identity.Identity
// contains filtered or unexported fields
}
MembershipsQueryCache can be used to answer a bunch of IsMemberOfAny questions, caching some internal state in-between them.
func (*MembershipsQueryCache) IsMemberOfAny ¶
func (q *MembershipsQueryCache) IsMemberOfAny(groups SortedNodeSet) bool
IsMemberOfAny returns true if the identity belongs to any of the given groups.
Groups are given as a sorted slice of group indexes obtained via GroupIndex.
type Node ¶
type Node struct {
*protocol.AuthGroup // the original group proto
Nested []NodeIndex // directly nested groups
Parents []NodeIndex // direct parent (nesting) groups
Index NodeIndex // index of this node within the graph's list of nodes
// contains filtered or unexported fields
}
Node is a node in a group graph.
type NodeIndex ¶
type NodeIndex uint16
NodeIndex is an index of a node within graph's list of nodes.
Used essentially as a pointer that occupies x4 less memory than the real one.
Note: when changing the type, make sure to also change SortedNodeSet.MapKey and replace math.MaxUint16 in Build(...) with another bound.
type NodeSet ¶
type NodeSet map[NodeIndex]struct{}
NodeSet is a set of nodes referred by their indexes.
func (NodeSet) Sort ¶
func (ns NodeSet) Sort() SortedNodeSet
Sort converts the NodeSet to SortedNodeSet.
type NodeSetDedupper ¶
type NodeSetDedupper map[string]SortedNodeSet
NodeSetDedupper helps to find duplicate NodeSet's.
func (NodeSetDedupper) Dedup ¶
func (nsd NodeSetDedupper) Dedup(ns NodeSet) SortedNodeSet
Dedup returns a sorted version of 'ns' (perhaps reusing an existing one).
type QueryableGraph ¶
type QueryableGraph struct {
// contains filtered or unexported fields
}
QueryableGraph is a processed Graph optimized for IsMember queries and low memory footprint.
It is built from Graph via ToQueryable method. It is static once constructed and can be queried concurrently.
TODO(vadimsh): Optimize 'memberships' to take less memory. It turns out string keys are quite expensive in terms of memory: a totally empty preallocated map[identity.Identity]SortedNodeSet (with empty keys!) is already *half* the size of the fully populated one.
func BuildQueryable ¶
func BuildQueryable(groups []*protocol.AuthGroup) (*QueryableGraph, error)
BuildQueryable constructs the queryable graph from a list of AuthGroups.
func (*QueryableGraph) GroupIndex ¶
func (g *QueryableGraph) GroupIndex(group string) (idx NodeIndex, ok bool)
GroupIndex returns a NodeIndex of the group given its name.
func (*QueryableGraph) IsMember ¶
func (g *QueryableGraph) IsMember(ident identity.Identity, group string) IsMemberResult
IsMember returns true if the given identity belongs to the given group.
func (*QueryableGraph) MembershipsQueryCache ¶
func (g *QueryableGraph) MembershipsQueryCache(ident identity.Identity) MembershipsQueryCache
MembershipsQueryCache prepares a query for memberships of the given identity.
This query can be used to answer a bunch of IsMemberOfAny questions, caching some internal state in-between them.
type SortedNodeSet ¶
type SortedNodeSet []NodeIndex
SortedNodeSet is a compact representation of NodeSet as a sorted slice.
func (SortedNodeSet) Has ¶
func (ns SortedNodeSet) Has(idx NodeIndex) bool
Has is true if 'idx' is in 'ns'.
func (SortedNodeSet) Intersects ¶
func (a SortedNodeSet) Intersects(b SortedNodeSet) bool
Intersects is true if 'a' and 'b' have common elements.
func (SortedNodeSet) MapKey ¶
func (ns SortedNodeSet) MapKey() string
MapKey converts 'ns' to a string that can be used as a map key.
Source Files