edit.c File Reference

Functions to edit pair lists, and track undo operations. More...

#include <freeradius-devel/util/value.h>
#include <freeradius-devel/util/talloc.h>
#include "edit.h"
#include "calc.h"

Include dependency graph for edit.c:

Go to the source code of this file.

Data Structures
struct	fr_edit_ignore_t
struct	fr_edit_list_s
	Track a series of edits. More...
struct	fr_edit_t
	Track one particular edit. More...
union	fr_edit_t.__unnamed115__
union	fr_edit_t.__unnamed115__.__unnamed117__
struct	fr_edit_t.__unnamed115__.__unnamed119__

Macros
#define	COPY(_x)
#define	COPY
#define	NEXT_A   do { a = an; an = fr_pair_list_next(&dst->children, a); } while (0)
#define	NEXT_B   do { b = bn; bn = fr_pair_list_next(src, b); } while (0)

Enumerations
enum	fr_edit_op_t {   FR_EDIT_INVALID = 0 ,   FR_EDIT_DELETE ,   FR_EDIT_VALUE ,   FR_EDIT_CLEAR ,   FR_EDIT_INSERT ,   FR_EDIT_CHILD }

Functions
static int	_edit_list_destructor (fr_edit_list_t *el)
	Finalize the edits when we destroy the edit list. More...
static int	edit_record (fr_edit_list_t *el, fr_edit_op_t op, fr_pair_t *vp, fr_pair_list_t *list, fr_pair_t *ref)
	Record one particular edit. More...
static int	edit_undo (fr_edit_t *e)
	Undo one particular edit. More...
void	fr_edit_list_abort (fr_edit_list_t *el)
	Abort the entries in an edit list. More...
fr_edit_list_t *	fr_edit_list_alloc (TALLOC_CTX *ctx, int hint, fr_edit_list_t *parent)
	Allocate an edit list. More...
int	fr_edit_list_apply_list_assignment (fr_edit_list_t *el, fr_pair_t *dst, fr_token_t op, fr_pair_list_t *src, bool copy)
	Apply operators to lists. More...
int	fr_edit_list_apply_pair_assignment (fr_edit_list_t *el, fr_pair_t *vp, fr_token_t op, fr_value_box_t const *in)
	Apply operators to pairs. More...
void	fr_edit_list_commit (fr_edit_list_t *el)
	Commit an edit list. More...
static int	fr_edit_list_delete_list (fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_list_t *to_remove)
	Removes elements matching a list. More...
static bool	fr_edit_list_empty (fr_edit_list_t *el)
int	fr_edit_list_free_pair_children (fr_edit_list_t *el, fr_pair_t *vp)
	Free children of a structural pair. More...
int	fr_edit_list_insert_list_after (fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *pos, fr_pair_list_t *to_insert)
	Notes. More...
int	fr_edit_list_insert_pair_after (fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *pos, fr_pair_t *vp)
	Insert a new VP after an existing one. More...
int	fr_edit_list_pair_delete (fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *vp)
	Delete a VP. More...
int	fr_edit_list_pair_delete_by_da (fr_edit_list_t *el, fr_pair_list_t *list, fr_dict_attr_t const *da)
	Delete VPs with a matching da. More...
int	fr_edit_list_replace_pair (fr_edit_list_t *el, fr_pair_list_t *list, fr_pair_t *to_replace, fr_pair_t *vp)
	Replace a pair with another one. More...
int	fr_edit_list_replace_pair_value (fr_edit_list_t *el, fr_pair_t *vp, fr_value_box_t *box)
	Write a new value to the fr_value_box_t. More...
int	fr_edit_list_save_pair_value (fr_edit_list_t *el, fr_pair_t *vp)
	Record the value of a leaf fr_value_box_t. More...
static int	list_intersection (fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src)
	A INTERSECTION B. More...
static int	list_merge_lhs (fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src, bool copy)
	A MERGE B. More...
static int	list_merge_rhs (fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src, bool copy)
	A MERGE B. More...
static int	list_union (fr_edit_list_t *el, fr_pair_t *dst, fr_pair_list_t *src, bool copy)
	A UNION B. More...

Detailed Description

Functions to edit pair lists, and track undo operations.

Id

64d211a250036ca5102ed65474d431be3773b387

This file implements an "edit list" for changing values of fr_pair_t. After some investigation, it turns out that it's much easier to have an "undo list" than to track partially applied transactions. Tracking partial transactions means that none of the fr_pair_foo() functions will work, as some pairs are in the "old" list and some in the "new" list. Also, a transaction may still fail when we finalize it by moving the pairs around.

In contrast, an "undo" list means that all of the fr_pair_foo() functions will work, as any list contains only "active" pairs. And we never need to "finalize" a transaction, as the lists are already in their final form. The only thing needed for finalization is to free the undo list. Which can never fail.

Note that the functions here require the input VPs to already have the correct talloc parent! The only thing the edit list does is to record "undo" actions.

The only exception to this is fr_edit_list_apply_list_assignment(). Which does call talloc_steal, and then also frees any pairs which weren't applied to the LHS.

Copyright

2021 Network RADIUS SAS (legal.nosp@m.@net.nosp@m.workr.nosp@m.adiu.nosp@m.s.com)

Definition in file edit.c.

---

Data Structure Documentation

fr_edit_ignore_t

struct fr_edit_ignore_t

Definition at line 120 of file edit.c.

Collaboration diagram for fr_edit_ignore_t:

Data Fields
fr_dlist_t	entry
fr_pair_list_t *	list	list to ignore (never dereferenced)

fr_edit_list_s

struct fr_edit_list_s

Track a series of edits.

Definition at line 102 of file edit.c.

Collaboration diagram for fr_edit_list_s:

Data Fields
fr_pair_list_t	deleted_pairs
fr_edit_t *	e	so we don't have to loop over parent edits on abort
fr_dlist_head_t	ignore	lists to ignore
fr_edit_list_t *	parent	for nested transactions
fr_dlist_head_t	undo

fr_edit_t

struct fr_edit_t

Track one particular edit.

Definition at line 79 of file edit.c.

Collaboration diagram for fr_edit_t:

Data Fields
union fr_edit_t	__unnamed__
fr_dlist_t	entry	linked list of edits
fr_edit_op_t	op	edit operation to perform
fr_pair_t *	vp	pair edited, deleted, or inserted

fr_edit_t.__unnamed115__

union fr_edit_t.__unnamed115__

Definition at line 85 of file edit.c.

Data Fields
__unnamed115__	__unnamed__
__unnamed115__	__unnamed__

fr_edit_t.__unnamed115__.__unnamed117__

union fr_edit_t.__unnamed115__.__unnamed117__

Definition at line 86 of file edit.c.

Data Fields
fr_edit_list_t *	child_edit
fr_pair_list_t	children	original child list, for "clear"
fr_value_box_t	data	original data

fr_edit_t.__unnamed115__.__unnamed119__

struct fr_edit_t.__unnamed115__.__unnamed119__

Definition at line 92 of file edit.c.

Data Fields
fr_pair_list_t *	list	parent list
fr_pair_t *	ref	reference pair for delete, insert before/after

Macro Definition Documentation

COPY [1/2]

#define COPY

(

_x

)

Value:

                        do { if (copy) { \
                        c = fr_pair_copy(dst, _x); \
                        if (!c) return -1; \
                      } else { \
                        c = talloc_steal(dst, _x); \
                        fr_pair_remove(src, c); \
                      } \
                 } while (0)

Definition at line 1009 of file edit.c.

COPY [2/2]

#define COPY

Value:

                    do { if (copy) { \
                    fr_pair_list_init(&list); \
                    if (fr_pair_list_copy(dst, &list, src) < 0) return -1;\
                    src = &list; \
                  } else { \
                    fr_pair_list_steal(dst, src); \
                  } \
        } while (0)

Definition at line 1009 of file edit.c.

NEXT_A

#define NEXT_A   do { a = an; an = fr_pair_list_next(&dst->children, a); } while (0)

Definition at line 1018 of file edit.c.

NEXT_B

#define NEXT_B   do { b = bn; bn = fr_pair_list_next(src, b); } while (0)

Definition at line 1019 of file edit.c.

Enumeration Type Documentation

fr_edit_op_t

enum fr_edit_op_t

Enumerator
FR_EDIT_INVALID
FR_EDIT_DELETE	delete a VP
FR_EDIT_VALUE	edit a VP in place
FR_EDIT_CLEAR	clear the children of a structural entry.
FR_EDIT_INSERT	insert a VP into a list, after another one.
FR_EDIT_CHILD	child edit list

Definition at line 55 of file edit.c.

Function Documentation

_edit_list_destructor()

static int _edit_list_destructor ( fr_edit_list_t *  el )

static

Finalize the edits when we destroy the edit list.

Which in large part means freeing the VPs which have been deleted, or saved, and then deleting the edit list.

Definition at line 736 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

edit_record()

static int edit_record ( fr_edit_list_t *  el, fr_edit_op_t  op, fr_pair_t *  vp, fr_pair_list_t *  list, fr_pair_t *  ref  )

static

Record one particular edit.

For INSERT / DELETE, this function will also insert / delete the VP.

For VALUE changes, this function must be called BEFORE the value is changed. Once this function has been called, it is then safe to edit the value in place.

Note that VALUE changes for structural types are allowed ONLY when using T_OP_SET, which over-writes previous values. For every other modification to structural types, we MUST instead call insert / delete on the vp_group.

Definition at line 247 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

edit_undo()

static int edit_undo ( fr_edit_t *  e )

static

Undo one particular edit.

Definition at line 133 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_abort()

void fr_edit_list_abort

(

fr_edit_list_t *

el

)

Abort the entries in an edit list.

After this call, the input list(s) are unchanged from before any edits were made.

the caller does not have to call talloc_free(el);

Definition at line 194 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_alloc()

fr_edit_list_t* fr_edit_list_alloc	(	TALLOC_CTX *	ctx,
		int	hint,
		fr_edit_list_t *	parent
	)

Allocate an edit list.

Edit lists can be nested. If the child list commits, then it does nothing until the parent list commits. On the other hand, if the child list aborts, then the parent list might continue.

Parameters

ctx	talloc context. Ignored if parent!=NULL
hint	how many edits we are likely to allocate
parent	a parent edit list

Definition at line 790 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_apply_list_assignment()

int fr_edit_list_apply_list_assignment	(	fr_edit_list_t *	el,
		fr_pair_t *	dst,
		fr_token_t	op,
		fr_pair_list_t *	src,
		bool	copy
	)

Apply operators to lists.

= is "if found vp, do nothing. Otherwise call fr_edit_list_insert_pair_tail()

The src list is sorted, but is otherwise not modified.

Definition at line 1487 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_apply_pair_assignment()

int fr_edit_list_apply_pair_assignment	(	fr_edit_list_t *	el,
		fr_pair_t *	vp,
		fr_token_t	op,
		fr_value_box_t const *	in
	)

Apply operators to pairs.

:= is "if found vp, call fr_edit_list_pair_replace(). Otherwise call fr_edit_list_insert_pair_tail() = is "if found vp, do nothing. Otherwise call fr_edit_list_insert_pair_tail()

Definition at line 976 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_commit()

void fr_edit_list_commit

(

fr_edit_list_t *

el

)

Commit an edit list.

If there are nested transactions, then this transaction is committed only when the parent transaction has been committed.

Definition at line 841 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_delete_list()

static int fr_edit_list_delete_list ( fr_edit_list_t *  el, fr_pair_list_t *  list, fr_pair_list_t *  to_remove  )

static

Removes elements matching a list.

O(N^2) unfortunately.

Definition at line 931 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_empty()

static bool fr_edit_list_empty ( fr_edit_list_t *  el )

static

Definition at line 126 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_free_pair_children()

int fr_edit_list_free_pair_children	(	fr_edit_list_t *	el,
		fr_pair_t *	vp
	)

Free children of a structural pair.

This function mirrors fr_pair_replace().

After this function returns, the new VP has replaced the old one, and the new one can be edited.

Definition at line 709 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_insert_list_after()

int fr_edit_list_insert_list_after	(	fr_edit_list_t *	el,
		fr_pair_list_t *	list,
		fr_pair_t *	pos,
		fr_pair_list_t *	to_insert
	)

Notes.

Unlike "update" sections, edits are not hierarchical. If we're editing values a list, then the list has to exist. If we're inserting pairs in a list, then we find the lowest existing pair, and add pairs there.

The functions tmpl_extents_find() and tmpl_extents_build_to_leaf_parent() should help us figure out where the VPs exist or not.

The overall "update" algorithm is now:

alloc(edit list)

foreach entry in the things to do
    expand LHS if needed to local TMPL
    expand RHS if needed to local box / cursor / TMPL

    use LHS/RHS cursors to find VPs
    edit VPs, recording edits

free temporary map
commit(edit list)

Insert a list after a particular point in another list.

This function mirrors fr_pair_list_append(), but with a bit more control over where the to_insert list ends up.

There's nothing magical about this function, it's just easier to have it here than in multiple places in the code.

Definition at line 888 of file edit.c.

Here is the call graph for this function:

fr_edit_list_insert_pair_after()

int fr_edit_list_insert_pair_after	(	fr_edit_list_t *	el,
		fr_pair_list_t *	list,
		fr_pair_t *	pos,
		fr_pair_t *	vp
	)

Insert a new VP after an existing one.

This function mirrors fr_pair_insert_after().

After this function returns, the new VP has been inserted into the list.

Definition at line 562 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_pair_delete()

int fr_edit_list_pair_delete	(	fr_edit_list_t *	el,
		fr_pair_list_t *	list,
		fr_pair_t *	vp
	)

Delete a VP.

This function mirrors fr_pair_delete()

After this function returns, the VP has been removed from the list.

Definition at line 575 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_pair_delete_by_da()

int fr_edit_list_pair_delete_by_da	(	fr_edit_list_t *	el,
		fr_pair_list_t *	list,
		fr_dict_attr_t const *	da
	)

Delete VPs with a matching da.

This function mirrors fr_pair_delete_by_da()

Definition at line 594 of file edit.c.

Here is the call graph for this function:

fr_edit_list_replace_pair()

int fr_edit_list_replace_pair	(	fr_edit_list_t *	el,
		fr_pair_list_t *	list,
		fr_pair_t *	to_replace,
		fr_pair_t *	vp
	)

Replace a pair with another one.

This function mirrors fr_pair_replace().

After this function returns, the new VP has replaced the old one, and the new one can be edited.

Definition at line 658 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

fr_edit_list_replace_pair_value()

int fr_edit_list_replace_pair_value	(	fr_edit_list_t *	el,
		fr_pair_t *	vp,
		fr_value_box_t *	box
	)

Write a new value to the fr_value_box_t.

After this function returns, the value has been updated.

Definition at line 635 of file edit.c.

Here is the call graph for this function:

fr_edit_list_save_pair_value()

int fr_edit_list_save_pair_value	(	fr_edit_list_t *	el,
		fr_pair_t *	vp
	)

Record the value of a leaf fr_value_box_t.

After this function returns, it's safe to edit the pair.

Definition at line 622 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

list_intersection()

static int list_intersection ( fr_edit_list_t *  el, fr_pair_t *  dst, fr_pair_list_t *  src  )

static

A INTERSECTION B.

Definition at line 1375 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

list_merge_lhs()

static int list_merge_lhs ( fr_edit_list_t *  el, fr_pair_t *  dst, fr_pair_list_t *  src, bool  copy  )

static

A MERGE B.

with priority to A

Definition at line 1164 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

list_merge_rhs()

static int list_merge_rhs ( fr_edit_list_t *  el, fr_pair_t *  dst, fr_pair_list_t *  src, bool  copy  )

static

A MERGE B.

with priority to B.

Definition at line 1268 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function:

list_union()

static int list_union ( fr_edit_list_t *  el, fr_pair_t *  dst, fr_pair_list_t *  src, bool  copy  )

static

A UNION B.

Definition at line 1025 of file edit.c.

Here is the call graph for this function:

Here is the caller graph for this function: