diff mbox series

libsepol: hashtab: save one comparison on hit

Message ID 20240608171923.136765-1-cgoettsche@seltendoof.de (mailing list archive)
State Accepted
Commit a3332e574168
Delegated to: Petr Lautrbach
Headers show
Series libsepol: hashtab: save one comparison on hit | expand

Commit Message

Christian Göttsche June 8, 2024, 5:19 p.m. UTC 
From: Christian Göttsche <cgzones@googlemail.com>

When the comparison function returns 0, avoid a repeated call to it.

Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
---
 libsepol/src/hashtab.c | 53 +++++++++++++++++++++++++-----------------
 1 file changed, 32 insertions(+), 21 deletions(-)

Comments

James Carter June 11, 2024, 5:14 p.m. UTC | #1 
On Sat, Jun 8, 2024 at 1:19 PM Christian Göttsche
<cgoettsche@seltendoof.de> wrote:
>
> From: Christian Göttsche <cgzones@googlemail.com>
>
> When the comparison function returns 0, avoid a repeated call to it.
>
> Signed-off-by: Christian Göttsche <cgzones@googlemail.com>

Acked-by: James Carter <jwcart2@gmail.com>

> ---
>  libsepol/src/hashtab.c | 53 +++++++++++++++++++++++++-----------------
>  1 file changed, 32 insertions(+), 21 deletions(-)
>
> diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
> index 2af3a9bf..399582b1 100644
> --- a/libsepol/src/hashtab.c
> +++ b/libsepol/src/hashtab.c
> @@ -112,15 +112,17 @@ int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
>         hashtab_check_resize(h);
>
>         hvalue = h->hash_value(h, key);
> -       prev = NULL;
> -       cur = h->htable[hvalue];
> -       while (cur && h->keycmp(h, key, cur->key) > 0) {
> -               prev = cur;
> -               cur = cur->next;
> -       }
>
> -       if (cur && (h->keycmp(h, key, cur->key) == 0))
> -               return SEPOL_EEXIST;
> +       for (prev = NULL, cur = h->htable[hvalue]; cur; prev = cur, cur = cur->next) {
> +               int cmp;
> +
> +               cmp = h->keycmp(h, key, cur->key);
> +               if (cmp > 0)
> +                       continue;
> +               if (cmp == 0)
> +                       return SEPOL_EEXIST;
> +               break;
> +       }
>
>         newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
>         if (newnode == NULL)
> @@ -151,14 +153,19 @@ int hashtab_remove(hashtab_t h, hashtab_key_t key,
>                 return SEPOL_ENOENT;
>
>         hvalue = h->hash_value(h, key);
> -       last = NULL;
> -       cur = h->htable[hvalue];
> -       while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
> -               last = cur;
> -               cur = cur->next;
> +
> +       for (last = NULL, cur = h->htable[hvalue]; cur; last = cur, cur = cur->next) {
> +               int cmp;
> +
> +               cmp = h->keycmp(h, key, cur->key);
> +               if (cmp > 0)
> +                       continue;
> +               if (cmp == 0)
> +                       break;
> +               return SEPOL_ENOENT;
>         }
>
> -       if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
> +       if (cur == NULL)
>                 return SEPOL_ENOENT;
>
>         if (last == NULL)
> @@ -183,14 +190,18 @@ hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
>                 return NULL;
>
>         hvalue = h->hash_value(h, key);
> -       cur = h->htable[hvalue];
> -       while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
> -               cur = cur->next;
> -
> -       if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
> -               return NULL;
> +       for (cur = h->htable[hvalue]; cur; cur = cur->next) {
> +               int cmp;
> +
> +               cmp = h->keycmp(h, key, cur->key);
> +               if (cmp > 0)
> +                       continue;
> +               if (cmp == 0)
> +                       return cur->datum;
> +               break;
> +       }
>
> -       return cur->datum;
> +       return NULL;
>  }
>
>  void hashtab_destroy(hashtab_t h)
> --
> 2.45.1
>
>
James Carter June 14, 2024, 2:10 p.m. UTC | #2 
On Tue, Jun 11, 2024 at 1:14 PM James Carter <jwcart2@gmail.com> wrote:
>
> On Sat, Jun 8, 2024 at 1:19 PM Christian Göttsche
> <cgoettsche@seltendoof.de> wrote:
> >
> > From: Christian Göttsche <cgzones@googlemail.com>
> >
> > When the comparison function returns 0, avoid a repeated call to it.
> >
> > Signed-off-by: Christian Göttsche <cgzones@googlemail.com>
>
> Acked-by: James Carter <jwcart2@gmail.com>
>

Merged.
Thanks,
Jim

> > ---
> >  libsepol/src/hashtab.c | 53 +++++++++++++++++++++++++-----------------
> >  1 file changed, 32 insertions(+), 21 deletions(-)
> >
> > diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
> > index 2af3a9bf..399582b1 100644
> > --- a/libsepol/src/hashtab.c
> > +++ b/libsepol/src/hashtab.c
> > @@ -112,15 +112,17 @@ int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
> >         hashtab_check_resize(h);
> >
> >         hvalue = h->hash_value(h, key);
> > -       prev = NULL;
> > -       cur = h->htable[hvalue];
> > -       while (cur && h->keycmp(h, key, cur->key) > 0) {
> > -               prev = cur;
> > -               cur = cur->next;
> > -       }
> >
> > -       if (cur && (h->keycmp(h, key, cur->key) == 0))
> > -               return SEPOL_EEXIST;
> > +       for (prev = NULL, cur = h->htable[hvalue]; cur; prev = cur, cur = cur->next) {
> > +               int cmp;
> > +
> > +               cmp = h->keycmp(h, key, cur->key);
> > +               if (cmp > 0)
> > +                       continue;
> > +               if (cmp == 0)
> > +                       return SEPOL_EEXIST;
> > +               break;
> > +       }
> >
> >         newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
> >         if (newnode == NULL)
> > @@ -151,14 +153,19 @@ int hashtab_remove(hashtab_t h, hashtab_key_t key,
> >                 return SEPOL_ENOENT;
> >
> >         hvalue = h->hash_value(h, key);
> > -       last = NULL;
> > -       cur = h->htable[hvalue];
> > -       while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
> > -               last = cur;
> > -               cur = cur->next;
> > +
> > +       for (last = NULL, cur = h->htable[hvalue]; cur; last = cur, cur = cur->next) {
> > +               int cmp;
> > +
> > +               cmp = h->keycmp(h, key, cur->key);
> > +               if (cmp > 0)
> > +                       continue;
> > +               if (cmp == 0)
> > +                       break;
> > +               return SEPOL_ENOENT;
> >         }
> >
> > -       if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
> > +       if (cur == NULL)
> >                 return SEPOL_ENOENT;
> >
> >         if (last == NULL)
> > @@ -183,14 +190,18 @@ hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
> >                 return NULL;
> >
> >         hvalue = h->hash_value(h, key);
> > -       cur = h->htable[hvalue];
> > -       while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
> > -               cur = cur->next;
> > -
> > -       if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
> > -               return NULL;
> > +       for (cur = h->htable[hvalue]; cur; cur = cur->next) {
> > +               int cmp;
> > +
> > +               cmp = h->keycmp(h, key, cur->key);
> > +               if (cmp > 0)
> > +                       continue;
> > +               if (cmp == 0)
> > +                       return cur->datum;
> > +               break;
> > +       }
> >
> > -       return cur->datum;
> > +       return NULL;
> >  }
> >
> >  void hashtab_destroy(hashtab_t h)
> > --
> > 2.45.1
> >
> >
diff mbox series

Patch

diff --git a/libsepol/src/hashtab.c b/libsepol/src/hashtab.c
index 2af3a9bf..399582b1 100644
--- a/libsepol/src/hashtab.c
+++ b/libsepol/src/hashtab.c
@@ -112,15 +112,17 @@  int hashtab_insert(hashtab_t h, hashtab_key_t key, hashtab_datum_t datum)
 	hashtab_check_resize(h);
 
 	hvalue = h->hash_value(h, key);
-	prev = NULL;
-	cur = h->htable[hvalue];
-	while (cur && h->keycmp(h, key, cur->key) > 0) {
-		prev = cur;
-		cur = cur->next;
-	}
 
-	if (cur && (h->keycmp(h, key, cur->key) == 0))
-		return SEPOL_EEXIST;
+	for (prev = NULL, cur = h->htable[hvalue]; cur; prev = cur, cur = cur->next) {
+		int cmp;
+
+		cmp = h->keycmp(h, key, cur->key);
+		if (cmp > 0)
+			continue;
+		if (cmp == 0)
+			return SEPOL_EEXIST;
+		break;
+	}
 
 	newnode = (hashtab_ptr_t) malloc(sizeof(hashtab_node_t));
 	if (newnode == NULL)
@@ -151,14 +153,19 @@  int hashtab_remove(hashtab_t h, hashtab_key_t key,
 		return SEPOL_ENOENT;
 
 	hvalue = h->hash_value(h, key);
-	last = NULL;
-	cur = h->htable[hvalue];
-	while (cur != NULL && h->keycmp(h, key, cur->key) > 0) {
-		last = cur;
-		cur = cur->next;
+
+	for (last = NULL, cur = h->htable[hvalue]; cur; last = cur, cur = cur->next) {
+		int cmp;
+
+		cmp = h->keycmp(h, key, cur->key);
+		if (cmp > 0)
+			continue;
+		if (cmp == 0)
+			break;
+		return SEPOL_ENOENT;
 	}
 
-	if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
+	if (cur == NULL)
 		return SEPOL_ENOENT;
 
 	if (last == NULL)
@@ -183,14 +190,18 @@  hashtab_datum_t hashtab_search(hashtab_t h, const_hashtab_key_t key)
 		return NULL;
 
 	hvalue = h->hash_value(h, key);
-	cur = h->htable[hvalue];
-	while (cur != NULL && h->keycmp(h, key, cur->key) > 0)
-		cur = cur->next;
-
-	if (cur == NULL || (h->keycmp(h, key, cur->key) != 0))
-		return NULL;
+	for (cur = h->htable[hvalue]; cur; cur = cur->next) {
+		int cmp;
+
+		cmp = h->keycmp(h, key, cur->key);
+		if (cmp > 0)
+			continue;
+		if (cmp == 0)
+			return cur->datum;
+		break;
+	}
 
-	return cur->datum;
+	return NULL;
 }
 
 void hashtab_destroy(hashtab_t h)