Reduce explicitely recursion

When evaluating permissions, the recursive
algorithm is replaced with an algorithm
that eliminates the tail recursion.

Change-Id: I3298c42fa658498a954f4bf7dedfad87f00ab736
Signed-off-by: José Bollo <jose.bollo@iot.bzh>

diff --git a/src/afb-perm.c b/src/afb-perm.c
index b4d2b5e..ca83c7a 100644 (file)
--- a/src/afb-perm.c
+++ b/src/afb-perm.c
@@ -136,27 +136,23 @@ static void node_free(struct node *node)
  */
 static int node_check(struct node *node, int (*check)(void *closure, const char *name), void *closure)
 {
-       int rc;
-
-       switch (node->type) {
-       case Text:
-               rc = check(closure, node->text);
-               break;
-       case And:
-               rc = node_check(node->children[0], check, closure);
-               if (rc)
-                       rc = node_check(node->children[1], check, closure);
-               break;
-       case Or:
-               rc = node_check(node->children[0], check, closure);
-               if (!rc)
-                       rc = node_check(node->children[1], check, closure);
-               break;
-       case Not:
-               rc = !node_check(node->children[0], check, closure);
-               break;
+       for(;;) {
+               switch (node->type) {
+               case Text:
+                       return check(closure, node->text);
+               case And:
+                       if (!node_check(node->children[0], check, closure))
+                               return 0;
+                       break;
+               case Or:
+                       if (node_check(node->children[0], check, closure))
+                               return 1;
+                       break;
+               case Not:
+                       return !node_check(node->children[0], check, closure);
+               }
+               node = node->children[1];
        }
-       return rc;
 }
 
 /*********************************************************************

diff --git a/src/tests/test-perm/test-perm.c b/src/tests/test-perm/test-perm.c
index 8d63e3c..c9b6047 100644 (file)
--- a/src/tests/test-perm/test-perm.c
+++ b/src/tests/test-perm/test-perm.c
@@ -108,12 +108,13 @@ void mke(int value, int bits, char *buffer)
                case 3: add(buffer, "(%c or not %c) ", c, c); break;
                }
        } else if (val0 != val1) {
+               if (val0 && val1)
+                       add(buffer, "(");
                if (val0) {
                        add(buffer, "not %c", c);
                        if (val0 != smask) {
-                               add(buffer, " and (");
+                               add(buffer, " and ");
                                mke(val0, bits - 1, buffer);
-                               add(buffer, ")");
                        }
                }
                if (val0 && val1)
@@ -121,11 +122,12 @@ void mke(int value, int bits, char *buffer)
                if (val1) {
                        add(buffer, "%c", c);
                        if (val1 != smask) {
-                               add(buffer, " and (");
+                               add(buffer, " and ");
                                mke(val1, bits - 1, buffer);
-                               add(buffer, ")");
                        }
                }
+               if (val0 && val1)
+                       add(buffer, ")");
        } else {
                mke(val0, bits - 1, buffer);
        }
@@ -150,10 +152,11 @@ int fulltest()
        for (i = 0 ; i < 65536 ; i++) {
                makeexpr(i, buffer);
                j = test(buffer);
-               printf("[[[ %d %s %d ]]]\n", i, i==j?"==":"!=", j);
+               printf("[[[ %d %s %d ]]] %d %s\n", i, i==j?"==":"!=", j, (int)strlen(buffer), buffer);
                if (i != j)
                        r = 1;
        }
+       return r;
 }
 
 int main()