Find free interleaving indexes for the ACISM backend using a dedicated search.

1 files changed, 57 insertions, 14 deletions

diff --git a/src/analysis/scan/patterns/backends/acism.c b/src/analysis/scan/patterns/backends/acism.c
index d517168..aa462a7 100644
--- a/src/analysis/scan/patterns/backends/acism.c
+++ b/src/analysis/scan/patterns/backends/acism.c
@@ -813,13 +813,16 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
     size_t last_free_state;                 /* Dernier emplacement dispo.  */
     size_t full_size;                       /* Cartographie entière        */
     bitfield_t *global_usage;               /* Cartographie des usages     */
+#ifndef NDEBUG
+    size_t pops[3];                         /* Décomptes individuels       */
+    size_t bsum;                            /* Somme de tous les bits      */
+#endif
     bitfield_t *usage;                      /* Cartographie locale         */
     acism_trie_node_t *node;                /* Noeud en cours de traitement*/
+    size_t highest;                         /* Poids du bit le plus fort   */
     acism_trie_node_t *iter;                /* Boucle de parcours #2       */
+    size_t first_freedom_word;              /* Premier mot avec des dispos.*/
     size_t free_state;                      /* Emplacement libre trouvé    */
-    bool found;                             /* Bilan de recherche          */
-
-    size_t bsum;
 
     /* Préparation de la liste de noeuds à inscrire */
 
@@ -841,8 +844,16 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
     full_size = last_free_state + 257;
     global_usage = create_bit_field(full_size, false);
 
+#ifndef NDEBUG
+
+    pops[0] = 0;
+    pops[1] = 0;
+    pops[2] = 0;
+
     bsum = 0;
 
+#endif
+
     usage = create_bit_field(257, false);
 
     for (i = 0; i < backend->nodes_used; i++)
@@ -855,26 +866,49 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
         /* Préparation du masque du noeud */
 
+        truncate_bit_field(&usage, 257);
+
         reset_all_in_bit_field(usage);
 
         set_in_bit_field(usage, 0, 1);
 
+#ifndef NDEBUG
+        pops[0]++;
+#endif
+
+        highest = 0;
+
         for (iter = node->child; iter != NULL; iter = iter->sibling)
+        {
             set_in_bit_field(usage, iter->code, 1);
 
+#ifndef NDEBUG
+            pops[0]++;
+#endif
+
+            if (iter->code > highest)
+                highest = iter->code;
+
+        }
+
+#ifndef NDEBUG
+        pops[1] += popcount_for_bit_field(usage);
+#endif
+
         assert(popcount_for_bit_field(usage) == (node->children_count + 1));
 
+        truncate_bit_field(&usage, ++highest);
+
         /* Recherche d'une position idéale */
 
         if (i == 0)
+        {
+            first_freedom_word = 0;
             free_state = 0;
+        }
 
         else
-            for (free_state = 1; free_state < last_free_state; free_state++)
-            {
-                found = test_zeros_within_bit_field(global_usage, free_state, usage);
-                if (found) break;
-            }
+            free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word);
 
         /* Suivi global */
 
@@ -882,8 +916,10 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
         or_bit_field_at(global_usage, usage, free_state);
 
+#ifndef NDEBUG
         bsum += node->children_count + 1;
         assert(popcount_for_bit_field(global_usage) == bsum);
+#endif
 
         node->state_index = free_state;
 
@@ -898,6 +934,15 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
     /* Sotie encadrée */
 
+#ifndef NDEBUG
+
+    pops[2] = popcount_for_bit_field(global_usage);
+
+    assert(pops[0] == pops[1]);
+    assert(pops[0] == pops[2]);
+
+#endif
+
     backend->bitmap_usage = global_usage;
 
     delete_bit_field(usage);
@@ -934,10 +979,10 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
     bitfield_t *usage;                      /* Cartographie locale         */
     size_t rd_pos;                          /* Tête de lecture             */
     size_t wr_pos;                          /* Tête d'écriture             */
+    size_t first_freedom_word;              /* Premier mot avec des dispos.*/
     acism_trie_node_t *node;                /* Noeud à traiter             */
     acism_trie_node_t *iter;                /* Boucle de parcours          */
     size_t free_state;                      /* Emplacement libre trouvé    */
-    bool found;                             /* Bilan de recherche          */
 
     max_pos = backend->nodes_used;
 
@@ -970,6 +1015,8 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
     rd_pos++;
 
+    first_freedom_word = 0;
+
     /* Suivi des liens déjà en place */
 
     while (rd_pos < max_pos)
@@ -994,11 +1041,7 @@ static void g_acism_backend_prepare_interleave_array(GAcismBackend *backend)
 
         /* Recherche d'une position idéale */
 
-        for (free_state = 1; free_state < last_free_state; free_state++)
-        {
-            found = test_zeros_within_bit_field(global_usage, free_state, usage);
-            if (found) break;
-        }
+        free_state = find_interleaving_index_for_acism(global_usage, usage, &first_freedom_word);
 
         /* Suivi global */