[nft,4/4] segtree: Refactor ei_insert()
diff mbox series

Message ID 20200123143049.13888-5-phil@nwl.cc
State Changes Requested
Delegated to: Pablo Neira
Headers show
Series
  • Covscan-induced review of ei_insert()
Related show

Commit Message

Phil Sutter Jan. 23, 2020, 2:30 p.m. UTC
With all simplifications in place, reorder the code to streamline it
further. Apart from making the second call to ei_lookup() conditional,
debug output is slightly enhanced.

Signed-off-by: Phil Sutter <phil@nwl.cc>
---
 src/segtree.c | 63 +++++++++++++++++++++++----------------------------
 1 file changed, 28 insertions(+), 35 deletions(-)

Comments

Pablo Neira Ayuso Jan. 28, 2020, 12:23 p.m. UTC | #1
On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
> With all simplifications in place, reorder the code to streamline it
> further. Apart from making the second call to ei_lookup() conditional,
> debug output is slightly enhanced.
> 
> Signed-off-by: Phil Sutter <phil@nwl.cc>
> ---
>  src/segtree.c | 63 +++++++++++++++++++++++----------------------------
>  1 file changed, 28 insertions(+), 35 deletions(-)
> 
> diff --git a/src/segtree.c b/src/segtree.c
> index 3c0989e76093a..edec9f4ebf174 100644
> --- a/src/segtree.c
> +++ b/src/segtree.c
> @@ -192,48 +192,41 @@ static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
>  {
>  	struct elementary_interval *lei, *rei;
>  
> -	/*
> -	 * Lookup the intervals containing the left and right endpoints.
> -	 */
>  	lei = ei_lookup(tree, new->left);
> -	rei = ei_lookup(tree, new->right);
> -
> -	if (segtree_debug(tree->debug_mask))
> -		pr_gmp_debug("insert: [%Zx %Zx]\n", new->left, new->right);
> -
> -	if (lei != NULL && rei != NULL && lei == rei) {
> -		if (!merge)
> -			goto err;
> -
> -		ei_destroy(new);
> +	if (lei == NULL) {
> +		/* no overlaps, just add the new interval */
> +		if (segtree_debug(tree->debug_mask))
> +			pr_gmp_debug("insert: [%Zx %Zx]\n",
> +				     new->left, new->right);
> +		__ei_insert(tree, new);
>  		return 0;
> -	} else {
> -		if (lei != NULL) {
> -			if (!merge)
> -				goto err;
> -			/*
> -			 * Left endpoint is within lei, adjust it so we have:
> -			 *
> -			 * [lei_left, new_right]
> -			 */
> -			if (segtree_debug(tree->debug_mask)) {
> -				pr_gmp_debug("adjust left [%Zx %Zx]\n",
> -					     lei->left, lei->right);
> -			}
> +	}
>  
> -			mpz_set(lei->right, new->right);
> -			ei_destroy(new);
> -			return 0;
> -		}
> +	if (!merge) {
> +		errno = EEXIST;
> +		return expr_binary_error(msgs, lei->expr, new->expr,
> +					 "conflicting intervals specified");
>  	}

Not your fault, but I think this check is actually useless given that
the overlap check happens before (unless you consider to consolidate
the insertion and the overlap checks in ei_insert).

> -	__ei_insert(tree, new);
> +	/* caller sorted intervals, so rei is either equal to lei or NULL */
> +	rei = ei_lookup(tree, new->right);
> +	if (rei != lei) {

Isn't this always true? I mean rei != lei always stands true?

> +		/*
> +		 * Left endpoint is within lei, adjust it so we have:
> +		 *
> +		 * [lei_left, new_right]
> +		 */
> +		if (segtree_debug(tree->debug_mask))
> +			pr_gmp_debug("adjust right: [%Zx %Zx]\n",
> +				     lei->left, lei->right);
> +		mpz_set(lei->right, new->right);
> +	} else if (segtree_debug(tree->debug_mask)) {
> +		pr_gmp_debug("skip new: [%Zx %Zx] for old: [%Zx %Zx]\n",
> +			     new->left, new->right, lei->left, lei->right);
> +	}
>  
> +	ei_destroy(new);
>  	return 0;
> -err:
> -	errno = EEXIST;
> -	return expr_binary_error(msgs, lei->expr, new->expr,
> -				 "conflicting intervals specified");
>  }
>  
>  /*
> -- 
> 2.24.1
>
Phil Sutter Jan. 28, 2020, 2:14 p.m. UTC | #2
Hi Pablo,

On Tue, Jan 28, 2020 at 01:23:12PM +0100, Pablo Neira Ayuso wrote:
> On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
[...]
> > +	if (!merge) {
> > +		errno = EEXIST;
> > +		return expr_binary_error(msgs, lei->expr, new->expr,
> > +					 "conflicting intervals specified");
> >  	}
> 
> Not your fault, but I think this check is actually useless given that
> the overlap check happens before (unless you consider to consolidate
> the insertion and the overlap checks in ei_insert).

That's interesting, indeed. What's more interesting is how
interval_cmp() works: I assumed it would just sort by start element when
in fact interval size is the prominent aspect. In practice, this means
my changes work only as long as all intervals are of equal or decreasing
size. Does it make sense to uphold this ordering scheme?

> > -	__ei_insert(tree, new);
> > +	/* caller sorted intervals, so rei is either equal to lei or NULL */
> > +	rei = ei_lookup(tree, new->right);
> > +	if (rei != lei) {
> 
> Isn't this always true? I mean rei != lei always stands true?

Not if the second interval is entirely contained within the first one,
something like { 10-20, 12-14 }.

Cheers, Phil
Pablo Neira Ayuso Jan. 28, 2020, 3:42 p.m. UTC | #3
On Tue, Jan 28, 2020 at 03:14:16PM +0100, Phil Sutter wrote:
> Hi Pablo,
> 
> On Tue, Jan 28, 2020 at 01:23:12PM +0100, Pablo Neira Ayuso wrote:
> > On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
> [...]
> > > +	if (!merge) {
> > > +		errno = EEXIST;
> > > +		return expr_binary_error(msgs, lei->expr, new->expr,
> > > +					 "conflicting intervals specified");
> > >  	}
> > 
> > Not your fault, but I think this check is actually useless given that
> > the overlap check happens before (unless you consider to consolidate
> > the insertion and the overlap checks in ei_insert).
> 
> That's interesting, indeed. What's more interesting is how
> interval_cmp() works: I assumed it would just sort by start element when
> in fact interval size is the prominent aspect.

I overlook that this is ordered by the size.

> In practice, this means my changes work only as long as all
> intervals are of equal or decreasing size. Does it make sense to
> uphold this ordering scheme?

I think if you change the ordering scheme to use the left side
(instead of the size) your new logic will work fine. It will also make
it probably easier to check for overlaps in the end.
Phil Sutter Jan. 28, 2020, 3:55 p.m. UTC | #4
On Tue, Jan 28, 2020 at 04:42:17PM +0100, Pablo Neira Ayuso wrote:
> On Tue, Jan 28, 2020 at 03:14:16PM +0100, Phil Sutter wrote:
> > Hi Pablo,
> > 
> > On Tue, Jan 28, 2020 at 01:23:12PM +0100, Pablo Neira Ayuso wrote:
> > > On Thu, Jan 23, 2020 at 03:30:49PM +0100, Phil Sutter wrote:
> > [...]
> > > > +	if (!merge) {
> > > > +		errno = EEXIST;
> > > > +		return expr_binary_error(msgs, lei->expr, new->expr,
> > > > +					 "conflicting intervals specified");
> > > >  	}
> > > 
> > > Not your fault, but I think this check is actually useless given that
> > > the overlap check happens before (unless you consider to consolidate
> > > the insertion and the overlap checks in ei_insert).
> > 
> > That's interesting, indeed. What's more interesting is how
> > interval_cmp() works: I assumed it would just sort by start element when
> > in fact interval size is the prominent aspect.
> 
> I overlook that this is ordered by the size.

Me too. %)

> > In practice, this means my changes work only as long as all
> > intervals are of equal or decreasing size. Does it make sense to
> > uphold this ordering scheme?
> 
> I think if you change the ordering scheme to use the left side
> (instead of the size) your new logic will work fine. It will also make
> it probably easier to check for overlaps in the end.

I wondered if this sorting may be used (or even necessary) for prefixes
or something. If it's not mandatory, I think sorting differently would
indeed help. Anyway, it means back to drawing board for me and self-NACK
this series.

Thanks, Phil

Patch
diff mbox series

diff --git a/src/segtree.c b/src/segtree.c
index 3c0989e76093a..edec9f4ebf174 100644
--- a/src/segtree.c
+++ b/src/segtree.c
@@ -192,48 +192,41 @@  static int ei_insert(struct list_head *msgs, struct seg_tree *tree,
 {
 	struct elementary_interval *lei, *rei;
 
-	/*
-	 * Lookup the intervals containing the left and right endpoints.
-	 */
 	lei = ei_lookup(tree, new->left);
-	rei = ei_lookup(tree, new->right);
-
-	if (segtree_debug(tree->debug_mask))
-		pr_gmp_debug("insert: [%Zx %Zx]\n", new->left, new->right);
-
-	if (lei != NULL && rei != NULL && lei == rei) {
-		if (!merge)
-			goto err;
-
-		ei_destroy(new);
+	if (lei == NULL) {
+		/* no overlaps, just add the new interval */
+		if (segtree_debug(tree->debug_mask))
+			pr_gmp_debug("insert: [%Zx %Zx]\n",
+				     new->left, new->right);
+		__ei_insert(tree, new);
 		return 0;
-	} else {
-		if (lei != NULL) {
-			if (!merge)
-				goto err;
-			/*
-			 * Left endpoint is within lei, adjust it so we have:
-			 *
-			 * [lei_left, new_right]
-			 */
-			if (segtree_debug(tree->debug_mask)) {
-				pr_gmp_debug("adjust left [%Zx %Zx]\n",
-					     lei->left, lei->right);
-			}
+	}
 
-			mpz_set(lei->right, new->right);
-			ei_destroy(new);
-			return 0;
-		}
+	if (!merge) {
+		errno = EEXIST;
+		return expr_binary_error(msgs, lei->expr, new->expr,
+					 "conflicting intervals specified");
 	}
 
-	__ei_insert(tree, new);
+	/* caller sorted intervals, so rei is either equal to lei or NULL */
+	rei = ei_lookup(tree, new->right);
+	if (rei != lei) {
+		/*
+		 * Left endpoint is within lei, adjust it so we have:
+		 *
+		 * [lei_left, new_right]
+		 */
+		if (segtree_debug(tree->debug_mask))
+			pr_gmp_debug("adjust right: [%Zx %Zx]\n",
+				     lei->left, lei->right);
+		mpz_set(lei->right, new->right);
+	} else if (segtree_debug(tree->debug_mask)) {
+		pr_gmp_debug("skip new: [%Zx %Zx] for old: [%Zx %Zx]\n",
+			     new->left, new->right, lei->left, lei->right);
+	}
 
+	ei_destroy(new);
 	return 0;
-err:
-	errno = EEXIST;
-	return expr_binary_error(msgs, lei->expr, new->expr,
-				 "conflicting intervals specified");
 }
 
 /*